A geometric simulation theorem on direct products of finitely generated groups

A geometric simulation theorem on direct products of finitely generated groups, Discrete Analysis 2019:9, 25 pp.

In 1961, the mathematician and philosopher Hao Wang introduced the notion that we now call a Wang tiling of $\mathbb Z^2$. Each tile is a unit square with edges marked in a certain way, and two tiles can be placed next to each other if and only if the adjacent edges have the same marking. (Also, tiles are not allowed to be rotated.)

Wang observed that if every set of Wang tiles admits a periodic tiling, then there is an algorithm for deciding whether any given finite set of Wang tiles can tile the plane, since if it cannot, then by an easy compactness argument there is some finite subset of the plane that cannot be tiled, whereas if it can, then one can do a brute-force search for a fundamental domain of the tiling. Wang believed that every tiling should be periodic, but his student Robert Berger showed in his PhD thesis in 1964 that the the tiling problem could be used to encode the halting problem, thereby proving that there was no algorithm for solving the former, which yielded the first known example of a set of tiles that could tile the plane but only aperiodically. (The result appeared in paper form in 1966.)

The notions of Wang tilings and aperiodicity have been fruitfully generalized from $\mathbb Z^2$ to more general groups, as follows. Let $G$ be a group (which will be infinite) and let $\mathcal A$ be a set of symbols, which we can think of as our “tiles”. Define a pattern to be a function $p:X\to\mathcal A$, where $X$ is some finite subset of $G$. Given a function $\omega:G\to\mathcal A$, say that the pattern $p$ occurs in $\omega$ if there exists some $g\in G$ such that $\omega(gx)=p(x)$ for every $x\in X$. Now let $P$ be a finite set of forbidden patterns. The set of all functions $\omega$ such that no pattern $p\in P$ occurs in $\omega$ is called the subshift of finite type determined by $P$. The functions $\omega$ that satisfy this condition are called configurations. Note that the set of tilings of the plane with a given set of Wang tiles is a subshift of finite type determined by the rules that stipulate when two tiles may be placed next to each other, each of which is given by a forbidden pattern of size 2.

Note that $G$ acts on a subshift of finite type in an obvious way: if $h\in G$ and $\omega$ is a configuration, then so is the function $\omega_h$ defined by $\omega_h(g)=\omega(h^{-1}g)$. The map $(h,\omega)\mapsto\omega_h$ is easily checked to be an action. The subshift is called strongly aperiodic if this action is free: that is, if no non-trivial group element takes any configuration to itself. In the case of Wang tiles, the subshift is strongly aperiodic if and only if no tiling with the given set of tiles is periodic.

This paper is about so-called simulation theorems. A basic example of such a theorem is the following result mentioned by the authors. A group is said to be recursively presented if it is countably generated and there is an algorithm for determining whether any given word in the generators is a relation. It is known that every subgroup of a finitely presented group is recursively presented, and a theorem of Graham Higman states the converse: that every recursively presented group can be embedded into a finitely presented group.

The interesting feature of this theorem is that a rather complicated object – a recursively presented group – can be embedded into a much simpler one – a finitely presented group. In this paper, a theorem of a similar kind is proved for dynamical systems. It can be shown that if the shift action of a subshift of finite type is restricted to a subgroup, the resulting action need not be a subshift of finite type. However it has the important property of being effectively closed. This means, roughly speaking, that there is an algorithm that determines, for any group element $g$, any pair $\omega,\omega'$ of configurations, and any pair $N_1,N_2$ of basic open neighbourhoods of $\omega_g$ and $\omega'$ (in the product topology), whether $N_1$ and $N_2$ are disjoint. Even more roughly, it is effectively closed if there is an algorithm that allows one to approximate the action arbitrarily well.

One can now ask whether an effectively closed subshift can be embedded, in a suitable sense, into a subshift of finite type. The main result of this paper is a result of exactly this type. It has a number of interesting consequences, of which a notable one is that the Grigorchuk group (the famous group that exhibits growth that is intermediate between polynomial and exponential) admits a non-empty strongly aperiodic subshift of finite type. The proof builds on a number of deep ideas due to Mike Hochman and Tom Meyerovitch, and the author and Mathieu Sablik. An unusual feature of the argument is that it obtains aperiodic tilings by first obtaining computational simulations, rather than first obtaining aperiodic tilings and then extracting computational corollaries from them.