A pattern of the sparse square grid.

Surface entropy of subshifts of finite type

Consider subshifts of finite type (SFTs), ie. sets of colorings over \(\mathbb{Z}^2\) defined by finite families of forbidden patterns. These objects enjoy a deep link with computability theory. This link was uncovered by the characterization of entropies of SFTs as the right recursively enumerable numbers by Hochman and Meyerovitch.

Here, we focus on the related notion of surface entropy introduced in Dennis Pace's thesis. If the number of \(n \times n\) patterns of the subshift grows as \(e^{hn^2+2Cn}\), then \(h\) is the classical topological entropy while \(C\) is the surface entropy. In this talk, we prove that the surface entropies of \(\mathbb{Z}^2\) SFTs are exactly the \(\Pi^0_3\) real numbers of the arithmetical hierarchy of real numbers.

To obtain this characterization, we introduce the sparse squares, a construction which realizes linear terms (instead of the usual quadratic terms) in the complexity function.

For more details, you can read the associated article!