Pacific Institute for the Mathematical Sciences - PIMS

Estimating the entropy of a Z^d shift of finite type with probabilistic methods

In symbolic dynamics, a Z^d shift of finite type (or SFT) is the set of
all ways to assign elements from a finite alphabet A to all sites of
Z^d, subject to rules about which elements of A are allowed to appear
next to each other. A simple example of an SFT is the Z^d golden mean
shift, which is the set of all ways to assign zeroes and ones to sites
of Z^d such that no two ones are adjacent (for d=2, this example is
also known as the hard square model.) Any Z^d SFT has an associated
topological entropy (or entropy), which is a real number measuring the
exponential growth rate, as n goes to infinity, of the number of
configurations in A^({1,...,n}^d) which satisfy the SFT adjacency
rules. For d=1, the entropy of any SFT is easy to compute: it is always
the log of the largest eigenvalue of an easily defined integer-valued
matrix associated with the SFT; for the golden mean shift, the entropy
is the log of the golden mean. For d>1, the computation is much more
difficult. For instance, there is no known explicit closed form for the
entropy of the Z^2 golden mean shift. And the standard ways to
approximate the entropy of a Z^d SFT appear to converge very slowly.
For the Z^2 golden mean shift, we give a sequence of computable upper
and lower bounds which converge exponentially fast to the entropy.
Empirical data suggested that these particular numbers approach the
entropy some time ago, but it has been an open problem to prove the
convergence. Surprisingly, the methods we use to solve this
combinatorially defined problem come mostly from measure theory and
probability. We use concepts and techniques from the theory of
interacting particle systems, including stochastic domination of
measures and uniqueness of Gibbs states. Some results from percolation
theory are also used to prove the exponential rate of convergence.

3:00pm-4:00pm, WMAX 216