There is a well know theorem by Coven and Hedlund, in [Sequences with minimal block growth](https://link.springer.com/article/10.1007/BF01762232), 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?



Morse-Hedlund\Coven-Hedlund theorem for non-Abelian groups
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.


