2009 Probability Seminar - 05

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.