Fall 2009 Distinguished Lecture Abstracts

Computing the Entropy of Two-dimensional Shifts of Finite Type

Dr. Brian Marcus,
Professor
Department of Mathematics
University of British Columbia

4:10 p.m., Wednesday November 11, 2009
Room 124, Bright Building

Abstract

A one-dimensional shift of finite type (SFT) is the set of infinite sequences that do not contain, as a sub-word, any finite word in a given finite list. The simplest example is the golden mean shift, which is defined as the set of all infinite binary sequences which do not contain the word "11" (i.e.., 1's are isolated). SFT's are ubiquitous as models of dynamical systems and also as constraints imposed on sequences to improve the performance of data recording systems. Perhaps the most fundamental quantity associated to an SFT is its entropy (called "topological entropy" in dynamical systems and "capacity" in information theory); entropy is defined as the asymptotic growth rate of the number of allowed finite words in the system. The entropy is easily computable as the log of the largest eigenvalue of a nonnegative integer matrix. For instance, the entropy of the golden mean shift is the log of the golden mean.

A two-dimensional SFT is defined as the set of tilings of the integer lattice that do not contain as a sub-array any finite array in a given finite list. Two-dimensional SFT's are much less understood than their one-dimensional counterparts. In particular, there is no known closed-form expression for the entropy, which is defined as the asymptotic growth rate of the number of allowed arrays in the system. Even for the simple case of the two-dimensional golden mean shift (also known as the hard square model), which is defined as the set of all binary tilings that do not contain two adjacent 1's, horizontally or vertically, there is no known explicit formula.

In this talk, we present recent results in joint work with Erez Louidor and Ronnie Pavlov. These include improved numerical approximations to entropy of specific SFT's and their cousins (sofic shifts), numerical approximation schemes which are provably exponentially accurate for a class of SFT's including the two-dimensional golden mean shift, and a few new exact computations of entropy.

Biography

Brian Marcus received his BA from Pomona College and PhD from UC Berkeley, both in Mathematics. His main research interests are in symbolic dynamics and information theory. He has been on the faculty of the University of North Carolina at Chapel Hill and the Research Staff of the IBM Almaden Research Center. He has held visiting and adjunct positions at several universities, including UC Berkeley and Stanford University. He has been Professor of Mathematics at the University of British Columbia since 2002, serving as Head of the Mathematics Department from 2002 to 2007. He is an IEEE Fellow, was co-recipient of the IEEE Leonard G. Abraham Prize Paper Award, co-author of "An Introduction to Symbolic Dynamics and Coding" (Cambridge University Press), has published extensively in Mathematics and Engineering journals and holds twelve US patents.

Faculty Contact: Dr. Anxiao (Andrew) Jiang (ajiang [at] cse.tamu.edu)