'Trivial' lower bounds for pattern complexity of aperiodic subshifts

Question

I recently asked in this thread about lower bounds on the complexity in the case where we have an aperiodic subshift. If I denote $c_n(\Omega)$ as the number of possible patterns on $Q_n= \big\{ 0,...,n-1 \big \}^d$, Ville Salo mentioned a paper\slides by Julien Cassaigne showing contrary to what I thought. Namely, that for $d\geq 3$ and any $f:\mathbb{N}\to \infty$ satisfying $\lim f(n)=\infty$, we have some aperiodic subshift $\Omega_f\subseteq \mathcal{A}^{\mathbb{Z}^d}$, such that

$$ c_n(\Omega_f)=O(n^2 f). $$

I was hoping that $\liminf \frac{c_n(\Omega)}{n^d}\geq C_d$. My subsequent question is whether we can say for $d\geq 3$, that for an aperiodic subshift, $\Omega\subseteq \mathcal{A}^{\mathbb{Z}^d}$, we have

$$ \liminf \frac{c_n(\Omega)}{n^2}\geq C_d \quad \text{or even} \quad \liminf \frac{c_n(\Omega)}{n}\geq C_d .$$

It seems to me that this should be true if we take an aperiodic configuration $\omega \in \mathcal{A}^{\mathbb{Z}^d}$ and project them to a $2$-dimensional or $1$-dimensional subspaces by the standard basis this should work. i.e., one of these projected configurations would have to be aperiodic and we can use the results in the $2$/$1$-dimensional cases.

Since I am not well versed in the subject of complexity estimations and my intuition has already been wrong, I thought that there may be a fault in this logic or a known counter-example. I would appreciate any comments on whether this question should have an obvious answer.

Answer 1

I'll try to do three dimensions for simplicity. I am on the bus and have to be very quick.

Theorem. Suppose $X \subset A^{\mathbb{Z}^3}$ is a subshift, such that $\liminf_n \frac{P(n)}{n^2} = 0$. Then every point in $X$ is periodic.

Lou look at two-dimensional slices of your configuration, and use (for example) the Cyr-Kra bound $P(n) < \frac{n^2}{2} \implies \mbox{periodic}$. We get that the horizontal double slice subshift $Y = \{x|_{\mathbb{Z^2} \times \{0, 1\}} \;|\; x \in X\} \subset (A^2)^{\mathbb{Z}^2}$ has only periodic configurations.

Now we recall a result from [1]:

Theorem. If $Y$ is a two-dimensional subshift with only periodic points, then $Y$ is a finite union of subshifts $Y_i$ such that for some nonzero vector $v_i$, $Y_i$ is globally fixed by the $v_i$-translation.

In particular the horizontal double slice subshift $Y$ has this form, so in any configuration, all the double slices have one of finitely many periods $v_1, ..., v_n$. If this period never changes, we are done. Otherwise, we get a doubly periodic slice (of height one).

Now apply the same argument to slices in another direction; now we have w.l.o.g. that the horizontal slice through the origin (the plane where z-coordinate = 0) is doubly periodic, and another slice $S$ (say y-coordinate = 0) is also.

Now, if you look at any "z-coordinate = n" slice, it actually must have period parallel to S: either this holds directly for its period, or we can move to the doubly periodic slice S along its period, move in the direction parallel to S, and go back.

So the entire point is periodic in a direction parallel to $S$. Square.

Reference(s):

[1] Anael Grandjean, Benjamin Hellouin de Menibus, Pascal Vanier