In the setting of symbolic dynamics over $\mathbb{Z}^d$, one can define for the $n$-th pattern complexity of a given a subshift $\Omega\subseteq \mathcal{A}^{\mathbb{Z}^d}$ as


$$ c\_n(\Omega):= \Big\vert \{P\in \mathcal{A}^{Q\_n}: P= \omega\vert\_{Q\_n} \; \text{for some} \; \omega\in \Omega \} \Big\vert $$


with $Q\_n:=\{0,...,n-1\}^d$. I know by Morse-Hedlund theorem that if $d=1$ and $\Omega$ contains an aperiodic configuration $\omega\in \mathcal{A}^{\mathbb{Z}}$, then $c\_n(\Omega)\geq n+1$ for all $n$. I found [this recent paper](https://arxiv.org/pdf/2105.00784.pdf), stating that if $d=2$ and $\Omega$ has an aperiodic configuration, then $c\_n(\Omega)\geq n^2+1$.


I was trying to find what is known in general dimensions $d\geq 3$? I am actually interested whether a weaker version of this sort of claim holds. i.e., if there exists a constant $C\_d>0$, such that $\Omega\subseteq \mathcal{A}^{\mathbb{Z}^d}$ is a subshift containing an aperiodic configuration implies that $c\_n(\Omega)\geq C\_d \cdot n^d$?


I am assuming this might be more commonly referred to in a terminology I am not aware of, but I assume that this should be known. Does anyone know of a work or survey in this direction for general $d$?



Lower bounds for pattern complexity of aperiodic subshifts
The answer is no in a very strong sense: there does not exist such $C\_d$ for $d \geq 3$ even for aperiodic minimal subshifts.


As far as finding lower bounds goes, complexities of subshifts containing aperiodic configurations are more or less the same as complexities of individual aperiodic configurations, namely a subshift containing aperiodic $x$ has at least the complexity of $x$, and conversely an aperiodic $x$ will have orbit closure with exactly the complexity of $x$.


In
<https://eventos.cmm.uchile.cl/sdynamics20208/wp-content/uploads/sites/111/2021/01/cassaigne.pdf>
Julien Cassaigne attributes to Lagarias and Peasants the conjecture that $\limsup\_n c\_n(x)/n^d > \infty$ for any $d$-dimensional aperiodic configuration $x$, i.e. that your $C\_d$ would exist in the lim sup sense, and to Lagarias, Peasants, Sander and Tijdeman the result that there exists an $x$ with $\liminf\_n c\_n(x)/n^d = 0$, i.e. your $C\_d$ does not exist in the lim inf sense. I did not follow up on the references.


He then proves the following theorem:



> 
> Theorem. Let $f : \mathbb{N} \to \mathbb{N}$ tend to infinity. Then for any $d \geq 3$ there exists an aperiodic uniformly recurrent $d$-dimensional configuration $x \in A^{\mathbb{Z}^d}$ such that $c\_n(x) = O(n^2 f(n))$.
> 
> 
> 


In particular the orbit closure is a minimal subshift where all configurations are aperiodic and the complexity is as above. He leaves open whether $O(n^2)$ complexity is possible in dimension $d \geq 3$.


