Lower bounds for pattern complexity of aperiodic subshifts

Question

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, 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$?

Answer 1

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$.

Answer 2

There are a few things to clarify here.

First of all, the two-dimensional version of Morse-Hedlund, i.e. that whenever $X$ contains a point with no period vector, $p_{m,n}(X) \geq mn+1$ holds for all $m,n$, is called the Nivat conjecture, and is still open!

There has been huge progress recently, including a wonderful paper of Kari-Moutot, which proves that if $X$ has ONLY aperiodic points, then for all $m,n$, $p_{m,n}(X) \geq mn+1$. This also implies that if $X$ is minimal, i.e. the orbit closure of any of its points, then Nivat holds. But it leaves open the possible case that $X$ has an aperiodic configuration whose orbit closure contains periodic configurations, and that $p_{m,n}(X) \leq mn$ for all $m,n$.

The paper you referenced proves Nivat for a subclass of subshifts defined by substitutions; there are a few papers proving special cases like this, including another paper by Kari and Moutot which relates Nivat to some so-called algebraic subshifts (see Ville's comment below), but does not provide a complete resolution.

I should mention two other partial Nivat results. The first is by Kari and Szabados, and proves that if $X$ contains an aperiodic configuration, there are at most finitely many $m,n$ so that $p_{m,n}(X) \leq mn$; this uses Hilbert's Nullstellensatz! The second is by Cyr and Kra, who proved that if you replace $mn$ by $mn/2$, then Nivat holds (i.e. if $X$ has an aperiodic configuration, then $p_{m,n}(X) > mn/2$ for all $m,n$.

As far as $d > 2$, the general consensus is that Nivat-type results are false. Indeed, consider a configuration $x$ in $\{0,1\}^{\mathbb{Z}^3}$ which is $0$ except for two biinfinite lines of $1$s which are non-parallel and do not intersect (for instance, $x(i,j,k) = 1$ iff $i, j = 0$ or $i, k = 10$), and take $X$ to be the orbit closure of $x$. Then $x$ is aperiodic, and yet it's not hard to check that for large $n$, $p_{n,n,n}(X) \approx C n^2$.

There is an annoying point here; even though $x$ is not technically periodic, it certainly feels 'almost periodic' in a sense. There is a paper by Durand and Rigo which pursues this idea, showing that if complexity is low for ANY $d$, then the points of $X$ are `simple' in the sense of being describable in something called the Presburger arithmetic. I'm not aware of any other progress for $d > 2$.