Skip to main content
2 of 2
Fixed errors noted by Ville Salo in comments
Ronnie Pavlov
  • 2.6k
  • 10
  • 15

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

Ronnie Pavlov
  • 2.6k
  • 10
  • 15