Morse-Hedlund\Coven-Hedlund theorem for non-Abelian groups

Question

There is a well know theorem by Coven and Hedlund, in Sequences with minimal block growth, stating that the complexity function of an aperiodic sequence\configuration $\omega\in \mathcal{A}^{\mathbb{Z}}$ is at least linear, where the complexity function $c_\omega(\cdot):\mathbb{N}\to \mathbb{N}$ of $\omega$, is the number of distinct words of given length occurring in $\omega$. I saw that it is referred to sometimes as the Morse-Hedlund complexity gap as well.

Since we can define configurations in a Bernoulli shift $\mathcal{A}^G$ for general groups $G$, I was wondering whether there are known results for complexity gaps of this form, for more general groups. Something like if $G$ contains an element of infinite order, then there exists a strictly monotonic function $g:[0,\infty)\to [1,\infty)$ satisfying $g(r)\overset{r\to \infty}{\to}\infty$, such that any configuration $\omega\in \mathcal{A}^G$ whose stabilizer is trivial must have complexity satisfying $c_\omega(r)=O\big( g(r) \big)$.

This seems like a natural question and I was wondering whether there is literature relating to that in certain non-Abelian cases?

Answer 1

Your motivation is about aperiodicity implying high complexity, but you ask whether aperiodicity implies an upper bound on complexity, which is a little strange. Probably there is a typo, and $O(g(r))$ should be $\Omega(g(r))$?

In any case, I'll give a simple generalization of the Morse-Hedlund theorem to all groups.

Definition. Let $G$ be any group, and let $D_1, D_2, D_3, ...$ be a family of finite subsets of $G$, such that $|D_i| \geq 1$. We say $(D_i)_i$ satisfies property (C) (for "connected") if the following holds: For $i \geq 1$, define a graph $\mathcal{G}_i$ with nodes $G$, and an edge between $g$ and $h$ if and only if $gD_i \cup hD_i \subset kD_{i+1}$ for some $k \in G$. Then for all $i$, the graph $\mathcal{G}_i$ is connected.

For $G = \mathbb{Z}$, we can take $D_i = [1,i]$. For general groups we can take balls of increasing radius $r$ with respect to any finite symmetric generating set.

Let $X \subset A^G$ be any subshift (closed set invariant under $G$-translations). Then we can measure complexity of $X$ by counting the finite sets $P_i = \{x|_{D_i} \;|\; x \in X\}$.

Theorem. If $X$ is an infinite subshift, $(D_i)_i$ have property (C), and $P_i$ are the associated pattern sets, then $|P_n| \geq n+1$ for all $n$.

Proof. Clearly $|P_1| \geq 2$. Otherwise, since $|D_1| \geq 1$, in particular all configurations in $X$ have the same symbol at the origin, thus $|X| \leq 1$ and $X$ is not infinite.

We now show $|P_{i+1}| > |P_i|$, from which $|P_n| \geq n+1$ immediately follows by induction.

Suppose the contrary, that $|P_{i+1}| \leq |P_i|$ for some $i$. Since $D_i \subset D_{i+1}$, we actually have $|P_{i+1}| = |P_i|$, and we see that by shift-invariance that for any $x \in X$, the restriction $x|_{gD_i}$ uniquely determines $x|_{hD_{i+1}}$ whenever $gD_i \subset hD_{i+1}$.

I claim that then $x|_{D_i}$ uniquely determines $x$ for all $x \in X$. This is more or less immediate from (C): Write $N \subset \mathcal{G}_i$ for all $g$ such that $x|_{D_i}$ determines $x|_{gD_i}$ uniquely. Note that ``$x|_{aD_i}$ determines $x|_{bD_i}$ uniquely'' is a transitive relation.

By definition $N$ contains $1_G$. It is also a connected component of $\mathcal{G}$: if we have the edge $(g, h)$ then $gD_i \cup hD_i \subset kD_{i+1}$ for some $k \in G$, thus $x|_{gD_i}$ determines $x|_{kD_{i+1}}$, in particular $x|_{gD_i}$ determines $x|_{hD_i}$. Square.

In the case of $\mathbb{Z}$, with the choice $D_i = [1, i]$ this precisely recovers the Morse-Hedlund theorem. In the case of $\mathbb{Z}^2$ if we use rectangles for $D_i$ that grow alternately in the two dimensions, then this gives only a linear lower bound on complexity of squares, so it falls far behind what is known about Nivat's conjecture.