---
abstract: 'Using results relating the complexity of a two dimensional subshift to its periodicity, we obtain an application to the well-known conjecture of Furstenberg on a Borel probability measure on $[0,1)$ which is invariant under both $x\mapsto px \pmod 1$ and $x\mapsto qx \pmod 1$, showing that any potential counterexample has a nontrivial lower bound on its complexity.'
address:
- 'Bucknell University, Lewisburg, PA 17837 USA'
- 'Northwestern University, Evanston, IL 60208 USA'
author:
- Van Cyr
- Bryna Kra
title: 'Free ergodic ${\mathbb{Z}}^2$-systems and complexity'
---

[^1]

Introduction
============

Complexity and periodicity
--------------------------

For a one dimensional symbolic system $(X, \sigma)$, meaning that $X\subset{\mathcal{A}}^{\mathbb{Z}}$ is a closed set, where ${\mathcal{A}}$ is a finite alphabet, that is closed under the left shift $\sigma\colon{\mathcal{A}}^{\mathbb{Z}}\to{\mathcal{A}}^{\mathbb{Z}}$, the Morse-Hedlund Theorem gives a simple relation between the complexity of the system and periodicity. Namely, if $P_X(n)$ denotes the complexity function, which counts the number of nonempty cylinder sets of length $n$ in $X$, then $(X, \sigma)$ is periodic if and only if there exists $n\in{\mathbb{N}}$ such that $P_X(n)\leq n$. Both periodicity and complexity have natural generalizations to higher dimensional systems. For example, for a two dimensional system $(X, \sigma, \tau)$, meaning that $X\subset{\mathcal{A}}^{{\mathbb{Z}}^2}$ is a closed set that is invariant under the left and down shifts $\sigma, \tau\colon {\mathcal{A}}^{{\mathbb{Z}}^2}\to{\mathcal{A}}^{{\mathbb{Z}}^2}$, the two dimensional complexity $P_X(n,k)$ is the number of nonempty $n$ by $k$ cylinder sets. In a partial solution to Nivat's Conjecture @Niv, the authors @CK showed that if $(X, \sigma, \tau)$ is a transitive ${\mathbb{Z}}^2$-subshift and there exist $n,k\in{\mathbb{N}}$ such that $P_{X}(n,k)\leq nk/2$, then there exists $(i,j)\in{\mathbb{Z}}^2\setminus\{(0,0)\}$ such that $\sigma^i\tau^jx=x$ for all $x\in X$. In this note, we give an application of this theorem to Furstenberg's well-known "$\times p, \times q$ problem."

The $\times p, \times q$ problem
--------------------------------

Let $S,T\colon[0,1)\to[0,1)$ denote the maps $Sx:=px \pmod 1$ and $Tx:=qx \pmod 1$, where $p,q\geq 1$ are multiplicatively independent integers (meaning that $p$ and $q$ are not both powers of the same integer). In the 1960's, Furstenberg @Fur proved that any closed subset of $[0,1)$ that is invariant under both $S$ and $T$ is either all of $[0,1)$ or is finite. He asked whether a similar statement holds for measures:

\[Furstenberg\] Let $\mu$ be a Borel probability measure on $[0,1)$ that is invariant under both $S$ and $T$ and is ergodic for the joint action of $S$ and $T$. Then either $\mu$ is Lebesgue measure or $\mu$ is atomic.

Progress was made in the 1980's with the work of Lyons @Lyons, followed soon thereafter by Rudolph's proof that positive entropy $h_\mu(\cdot)$ of the measure $\mu$ with respect to one of the transformations implies the result for relatively prime $p$ and $q$. This was generalized to multiplicatively independent integers by Johnson:

\[Rudolph @Rud and Johnson @johnson\] Let $\mu$ be a Borel probability measure on $[0,1)$ that is invariant under both $S$ and $T$ and is ergodic for the joint action of $S$ and $T$. If $h_{\mu}(S)>0$ (or equivalently $h_{\mu}(T)> 0$), then $\mu$ is Lebesgue measure.

One way to interpret this theorem is that the set of $\langle S,T\rangle$-ergodic measures experiences an entropy gap with respect to the one-dimensional action generated by $S$ (or equivalently by $T$). Informally, if $\mu$ has <span>*high entropy*</span> (in this case meaning that $h_{\mu}(S)>0$), then its entropy with respect to $S$ is actually $\log p$ and $\mu$ is Lebesgue measure. Our main theorem is that the set of $\langle S,T\rangle$-ergodic measures also experiences a <span>*complexity gap*</span>, in a sense we make precise. We show (Theorem \[thm:main\]) that if $\mu$ has <span>*low complexity*</span> (meaning that a certain function grows subquadratically), then it actually has <span>*bounded complexity*</span> (meaning that this function is bounded) and $\mu$ is atomic. Moreover, all atomic measures have bounded complexity.

Rephrasing $\times p, \times q$ in symbolic terms
-------------------------------------------------

We begin by recasting Furstenberg's Conjecture and the Rudolph-Johnson Theorem as statements about symbolic dynamical systems. We start by setting some terminology and notation.

A <span>*(measure preserving) system*</span> $(X, \mathcal{X}, \mu, G)$ is a measure space $X$ with an associated $\sigma$-algebra $\mathcal X$, probability measure $\mu$, and an abelian group $G$ of measurable, measure preserving transformations. If the context is clear, we omit the $\sigma$-algebra from the notation, writing $(X, \mu, G)$, and call it a <span>*system*</span>. The system $(X, \mu, G)$ is <span>*free*</span> if the set $\{x\in X\colon gx=x\}$ has measure $0$ for every $g\in G$ and the system is <span>*ergodic*</span> if the only sets invariant under the action of $G$ have either trivial or full measure. It follows that if $(X, \mu, G)$ is an ergodic system with an abelian group $G$ of transformations, then the action of $G$ is free if $g_1^{n_1}\circ\ldots\circ g_k^{n_k}\neq{{\rm Id}}$ for any $g_1, \ldots, g_k\in G$ and $(n_1, \ldots, n_k)\neq (0, \ldots, 0)$.

Two systems $(X_1,\mathcal{X}_1,\mu_1,G)$ and $(X_2,\mathcal{X}_2,\mu_2,G)$ are <span>*(measure theoretically) isomorphic*</span> if there exist $X_1^{\prime}\in \mathcal{X}_1$ and $X_2^{\prime}\in\mathcal{X}_2$ with $\mu_1(X_1') = \mu_2(X_2') = 1$ such that $gX_1'\subset X_1'$ for all $g\in G$ and $gX_2'\subset X_2'$ for all $g\in G$, and there is an invertible bimeasurable transformation $\pi\colon X_1^{\prime}\to X_2^{\prime}$ such that $\pi_*\mu_1=\mu_2$ and $\pi g(x)=g\pi(x)$ for all $x\in X_1'$, $g\in G$.

We are particularly interested in the ${\mathbb{Z}}^2$-system generated by the two commuting, measure preserving transformations $S$ and $T$. In this case, we write $(X, \mathcal X, \mu, S, T)$ for the ${\mathbb{Z}}^2$-system.

A <span>*(topological) system*</span> $(X, G)$, is a compact metric space $X$ and a group $G$ of homeomorphisms mapping $X$ to itself. If it is clear from the context that we are referring to a topological system, we call $(X,G)$ a <span>*system*</span>. A system is said to be <span>*minimal*</span> if for any $x\in X$, the orbit $\{gx\colon g\in G\}$ is dense in $X$. By the Krylov-Bogolyubov Theorem, every system $(X,G)$ admits an invariant Borel probability measure and if this measure is unique, we say that $(X,G)$ is <span>*uniquely ergodic*</span>. A system $(X,G)$ is <span>*strictly ergodic*</span> if it is both minimal and uniquely ergodic.

Let ${\mathcal{A}}$ denote a finite alphabet and let ${\mathcal{A}}^{{\mathbb{Z}}^2}$ be the set of ${\mathcal{A}}$-colorings of ${\mathbb{Z}}^2$. For $x\in{\mathcal{A}}^{{\mathbb{Z}}^2}$ and $\vec u\in{\mathbb{Z}}^2$, we denote the element of ${\mathcal{A}}$ that $x$ assigns to $\vec u$ by $x(\vec u)$. With respect to the metric $$d(x,y):=2^{-\inf\{|\vec u|\colon x(\vec u)\neq y(\vec u)\}},$$ ${\mathcal{A}}^{{\mathbb{Z}}^2}$ is compact and the leftward and downward shift maps $\sigma,\tau\colon{\mathcal{A}}^{{\mathbb{Z}}^2}\to{\mathcal{A}}^{{\mathbb{Z}}^2}$ given by $$\begin{aligned}
\label{eq:left}
(\sigma x)(i,j)&:=&x(i+1,j), \\ 
\label{eq:down}
(\tau x)(i,j)&:=&x(i,j+1) \end{aligned}$$ are homeomorphisms. A closed set $X\subset{\mathcal{A}}^{{\mathbb{Z}}^2}$ which is invariant under the joint action of $\langle\sigma,\tau\rangle$ is called a <span>*${\mathbb{Z}}^2$-subshift*</span>. (The analogous definitions hold for ${\mathbb{Z}}^d$-subshifts.)

A uniquely ergodic topological system $({\widehat}X,\nu, G)$ is said to be a <span>*topological model*</span> for the measure preserving system $(X, \mathcal{X}, \mu, G)$ if there exists a measure theoretic isomorphism between $({\widehat}X,\nu,G)$ and $(X, \mu, G)$. Again, we are mainly interested in topological systems generated by two transformations, and in this case we denote the topological system by $({\widehat}X, \sigma, \tau)$.

The Jewett-Krieger Theorem @jewett [@krieger] states that any ergodic ${\mathbb{Z}}$-system has a strictly ergodic topological model, meaning that the system is measure theoretically isomorphic to a minimal, uniquely ergodic topological system. This was generalized to cover ergodic ${\mathbb{Z}}^d$-systems by Weiss @weiss, and further refined by Rosenthal (we only state it for ${\mathbb{Z}}^2$, as this is the only case relevant for our purposes):

\[Rosenthal @rosenthal\]\[thm:rosenthal\] Let $(X,\mathcal{X},\mu,S,T)$ be an ergodic, free ${\mathbb{Z}}^2$-system with entropy less than $\log k$. Then there exists a minimal, uniquely ergodic subshift ${\widehat}X\subset\{1,\dots,k\}^{{\mathbb{Z}}^2}$ such that if $\sigma,\tau\colon{\widehat}X\to{\widehat}X$ denote the horizontal and vertical shifts (respectively) and if $\nu$ is the unique invariant Borel probability on ${\widehat}X$ and $\mathcal{B}$ denotes the Borel $\sigma$-algera, then $({\widehat}X,\mathcal{B},\nu,\sigma,\tau)$ is a topological model for $(X,\mathcal{X},\mu,S,T)$.

We note that in @rosenthal, the proof given shows that ${\widehat}X\subset\{1,\dots,k+1\}^{{\mathbb{Z}}^2}$ and the result that the shift alphabet can be taken to have only $k$ letters is stated without proof. However, the size of the alphabet is not relevant for our purposes, other than the fact that it is a finite number.

The subshift ${\widehat}X\subset\{1,\dots,k\}^{{\mathbb{Z}}^2}$ in the conclusion of Theorem \[thm:rosenthal\] is not uniquely defined, and so we make the following definition:

Let $(X,\mathcal{X},\mu,S,T)$ be an ergodic ${\mathbb{Z}}^2$-system. A minimal, uniquely ergodic ${\mathbb{Z}}^2$-subshift that is measure theoretically isomorphic to $(X,\mathcal{X},\mu,S,T)$ is called a <span>*Jewett-Krieger model for $(X,\mathcal{X},\mu,S,T)$*</span>.

Theorem \[thm:rosenthal\] guarantees that any free ergodic ${\mathbb{Z}}^2$ system of finite entropy has a Jewett-Krieger model. However the definition is still valid for non-free, ergodic ${\mathbb{Z}}^2$ systems; the only difference is that Rosenthal's Theorem no longer guarantees that such a model exists. For the case of interest to us, we show (in the proof of Theorem \[thm:main\]) that if $\mu$ is $\langle S,T\rangle$-ergodic, then either $\mu$ is atomic or the action of $\langle S,T\rangle$ is free. This motives us to make the following observation: a finite, ergodic ${\mathbb{Z}}^2$-system cannot be free, but it has a Jewett-Krieger model in a trivial way, obtained by partitioning the system into individual points.

Using this language, we can rephrase Furstenberg's Conjecture and the Rudolph-Johnson Theorem as equivalent statements about Jewett-Krieger models. Fix the transformations $S,T\colon[0,1)\to[0,1)$ to be the maps $Sx:=px \pmod 1$ and $Tx:=qx \pmod 1$, where $p,q\geq 1$ are multiplicatively independent integers. By the natural extension, we mean the invertible cover (see Section \[sec:natural-extension\]).

\[Symbolic Furstenberg Conjecture\] Let $\mu$ be a Borel probability measure on $[0,1)$ with Borel $\sigma$-algebra $\mathcal B$ that is invariant under both $S$ and $T$ and ergodic for the joint action. If ${\widehat}X\subset\{0,1\}^{{\mathbb{Z}}^2}$ is a Jewett-Krieger model for the natural extension of $([0,1),\mathcal{B},\mu,S,T)$, then either ${\widehat}X$ is finite or $\mu$ is Lebesgue measure.

\[Symbolic Rudolph-Johnson Theorem\]\[Rud-symbolic\] Let $\mu$ be a Borel probability measure on $[0,1)$ with Borel $\sigma$-algebra $\mathcal B$ which is invariant under both $S$ and $T$ and is ergodic for the joint action. Let ${\widehat}X\subset\{0,1\}^{{\mathbb{Z}}^2}$ be a Jewett-Krieger model for the natural extension of $([0,1),\mathcal{B},\mu,S,T)$ and let $\sigma,\tau\colon{\widehat}X\to{\widehat}X$ denote the horizontal and vertical shifts (respectively). If either $h_{\nu}(\sigma)>0$ or $h_{\nu}(\tau)>0$, then $\mu$ is Lebesgue measure.

An isomorphism of the ${\mathbb{Z}}^2$-systems $(X,\mathcal{X},\mu,S,T)$ and $({\widehat}X,\mathcal{B},\nu,\sigma,\tau)$ restricts to an isomorphism of the ${\mathbb{Z}}$-systems $(X,\mathcal{X},\mu,S)$ and $({\widehat}X,\mathcal{B},\nu,\sigma)$, and so $h_{\mu}(S)=h_{\nu}(\sigma)$. Similarly $h_{\mu}(T)=h_{\nu}(\tau)$. The statement then follows immediately from the Rudolph-Johnson Theorem.

Combinatorial rephrasing of measure theoretic entropy
-----------------------------------------------------

The appeal of Theorem \[Rud-symbolic\] is that the hypothesis that $h_{\nu}(\sigma)>0$ (or equivalently that $h_{\nu}(\tau)>0$) can be phrased purely as a combinatorial statement about the frequency with which words in the language of ${\widehat}X$ occur in larger words in the language of ${\widehat}X$. To explain this, we start with some definitions.

If $X\subset{\mathcal{A}}^{\mathbb{Z}}$ is a subshift over the finite alphabet ${\mathcal{A}}$, we write $x = (x(n)\colon n\in{\mathbb{Z}})$. A <span>*word*</span> is a defined to be a finite sequence of symbols contained consecutively in some $x$ and we let $|w|$ denote the number of symbols in $w$ (it may be finite or infinite). A word $w$ is a <span>*subword*</span> of a word $u$ if the symbols in the word $w$ occur somewhere in $u$ as consecutive symbols. The <span>*language ${\mathcal{L}}= {\mathcal{L}}(X)$*</span> of $X$ is defined to be the collection of all finite subwords that arise in elements of $X$. If $w\in{\mathcal{L}}(X)$, let $[w]$ denote the <span>*cylinder set*</span> it determines, meaning that $$[w] = \{u\in{\mathcal{L}}\colon u(n) = w(n) \text{ for } 1\leq n\leq |w|\}.$$

These definitions naturally generalize to a two dimensional subshift $X\subset{\mathcal{A}}^{{\mathbb{Z}}^2}$, and for $x\in{\mathcal{A}}^{{\mathbb{Z}}^2}$ we write $x = (x(\vec u)\colon\vec u\in{\mathbb{Z}}^2)$. A <span>*word*</span> is a finite, two dimensional configuration that is convex and connected (as a subset of ${\mathbb{Z}}^2$), and a <span>*subword*</span> is a configuration contained in another word. If $F\subset{\mathbb{Z}}^2$ is finite and $\beta\in{\mathcal{A}}^F$, then the <span>*cylinder set of shape $F$ determined by $\beta$*</span> is defined to be the set $$[F;\beta]:=\{x\in{\mathcal{A}}^{{\mathbb{Z}}^2}\colon x(\vec u)=\beta(\vec u)\text{ for all }\vec u\in F\}.$$

\[lemma:compute\] Let $({\widehat}X,\mathcal{B},\nu,\sigma,\tau)$ be a strictly ergodic ${\mathbb{Z}}^2$-subshift. Let $w$ be a $(2n+1)\times (2n+1)$ word in the language of ${\widehat}X$ and let $[w]$ denote the cylinder set determined by placing the word $w$ centered at $(0,0)$. Let $u_1,u_2,u_3,\dots$ be words in the language of ${\widehat}X$ such that $u_i$ is a square of size $(2n+2i+1)\times(2n+2i+1)$. If $N(w,u_i)$ denotes the number of times $w$ occurs as a subword of $u_i$, then $$\nu[w]=\lim_{i\to\infty}N(w,u_i)/(2i+1)^2.$$

By unique ergodicity, the Birkhoff averages of a continuous function converge uniformly to the integral of the function. In particular, this applies to the continuous function $1_{[w]}$, so the limit exists and is independent of the sequence $\{u_i\}_{i=1}^{\infty}$.

For $m,n\in{\mathbb{N}}$, let $\mathcal{P}(m,n)$ be the partition of ${\widehat}X$ according to cylinder sets of shape $[0,m-1]\times[-n+1,n-1]$. Observe that (recall that $\sigma$, as defined in , denotes the left shift) $$\mathcal{P}(m,n)=\bigvee_{i=0}^k\sigma^{-i}\mathcal{P}(1,n)$$ and that $\bigvee_{i=-k}^k\sigma^i\mathcal{P}(1,n)$ is the partition of ${\widehat}X$ into symmetric $(2m+1)\times(2n+1)$-cylinders centered at the origin. Therefore, $\{\mathcal{P}(1,n)\}_{n=1}^{\infty}$ is a sufficient (in the sense of Definition 4.3.11 in @KH) family of partitions to generate the Borel $\sigma$-algebra of the system $({\widehat}X,\mathcal{B},\nu,\sigma)$, where we view this as a ${\mathbb{Z}}$-system with respect to the horizontal shift $\sigma$. Let $h_\nu(\sigma,\mathcal Q)$ denote the measure theoretic entropy of the system $({\widehat}X,\mathcal{B}, \nu, \sigma)$ with respect to the partition $\mathcal Q$ and let $h_\nu(\sigma)$ denote the measure theoretic entropy of the system. It follows that $$\begin{aligned}
h_{\nu}(\sigma)&=&\sup_n h_{\nu}(\sigma,\mathcal{P}(1,n)) \\ 
&=&\lim_{n\to\infty}h_{\nu}\left(\sigma,\mathcal{P}(1,n)\right) \\ 
&=&-\lim_{n\to\infty}\lim_{m\to\infty}\frac{1}{m}\sum_{w\in\mathcal{P}(m,n)}\nu[w]\log\nu[w] \\ 
&=&-\lim_{n\to\infty}\lim_{m\to\infty}\lim_{i\to\infty}\frac{1}{m}\sum_{w\in\mathcal{P}(m,n)}\frac{N(w,u_i)}{(2i+1)^2}\cdot\log\frac{N(w,u_i)}{(2i+1)^2}\end{aligned}$$ by Lemma \[lemma:compute\]. In other words, the Rudolph-Johnson Theorem is equivalent to:

\[Combinatorial Rudolph-Johnson Theorem\]\[Rud:comb\] Let $\mu$ be a Borel probability measure on $[0,1)$ with Borel $\sigma$-algebra $\mathcal B$ and assume that $\mu$ is invariant under both $S$ and $T$, and ergodic for the joint action. Let ${\widehat}X$ be a Jewett-Krieger model for the natural extension of $([0,1),\mathcal{B},\mu,S,T)$ and without loss suppose the horizontal shift on ${\widehat}X$ is intertwined with $S$ under this isomoprhism. If $$-\lim_{n\to\infty}\lim_{m\to\infty}\lim_{i\to\infty}\frac{1}{m}\sum_{w\in\mathcal{P}(m,n)}\frac{N(w,u_i)}{(2i+1)^2}\cdot\log\frac{N(w,u_i)}{(2i+1)^2}>0,$$ then the value of this limit is $\log p$ and $\mu$ is Lebesgue measure.

Complexity of subshifts
-----------------------

If $X\subset{\mathcal{A}}^{{\mathbb{Z}}^2}$ is a nonempty subshift, then its <span>*complexity function*</span> is the function $P_X\colon\{\text{finite subsets of ${\mathbb{Z}}^2$}\}\to{\mathbb{N}}$ given by $$P_X(F):=\bigl\vert\{\beta\in{\mathcal{A}}^F\colon[F;\beta]\cap X\neq\emptyset\}\bigr\vert.$$ Let $R_n:=\{(i,j)\in{\mathbb{Z}}^2\colon1\leq i,j\leq n\}$ denote the $n\times n$ rectangle in ${\mathbb{Z}}^2$. A standard notion of the complexity of a subshift $X\subset{\mathcal{A}}^{Z^2}$ is the asymptotic growth rate of $P_X(R_n)$. Observe that $P_X(R_n)$ is bounded (in $n$) if and only if $X$ is finite. Moreover, $P_X(R_n)$ grows exponentially if and only if $(X,\sigma,\tau)$ has positive topological entropy.

We are now in a position to state our main technical result.

\[thm:main\] Let $\mu$ be a Borel probability measure on $[0,1)$ with Borel $\sigma$-algebra $\mathcal B$. Assume that $\mu$ is invariant under both $S$ and $T$ and ergodic for the joint action, and let ${\widehat}X\subset\{0,1\}^{{\mathbb{Z}}^2}$ be a Jewett-Krieger model for the natural extension of $([0,1),\mathcal{B},\mu,S,T)$. If there exists $n\in{\mathbb{N}}$ such that $P_{{\widehat}X}(R_n)\leq\frac{1}{2} n^2$, then $P_{{\widehat}X}(R_n)$ is bounded (independent of $n$) and ${\widehat}X$ is finite. In particular, $\mu$ is atomic.

This gives a nontrivial complexity gap for the set of $\langle S,T\rangle$-ergodic probability measures, which is our main result:

\[Complexity gap\]\[cor:gap\] Let $\mu$ be a Borel probability measure on $[0,1)$ which is invariant under both $S$ and $T$ and ergodic for the joint action, and let ${\widehat}X\subset\{0,1\}^{{\mathbb{Z}}^2}$ be a Jewett-Krieger model for the natural extension of $([0,1),\mathcal{B},\mu,S,T)$. Then either $P_{{\widehat}X}(R_n)$ is bounded (and $\mu$ is atomic) or $$\liminf_{n\to\infty}\frac{P_{{\widehat}X}(R_n)}{n^2}\geq\frac{1}{2}.$$

This gap is nontrivial in the following sense: there exist aperiodic, strictly ergodic ${\mathbb{Z}}^2$-subshifts whose complexity function grows subquadratically. The statement made by Corollary \[cor:gap\] is that any such subshift cannot be a Jewett-Krieger model of any $\langle\times p,\times q\rangle$-ergodic measure on $[0,1)$.

Let $X\subset\{0,1\}^{{\mathbb{Z}}}$ be a Sturmian shift (see @MH for the definition). Then $X$ is strictly ergodic and $P_X(n)=n+1$ for all $n\in{\mathbb{N}}$. Let $Y\subset\{0,1\}^{{\mathbb{Z}}^2}$ be the subshift whose points are obtained by placing each $x\in X$ along the $x$-axis in ${\mathbb{Z}}^2$ and then copying vertically (i.e. each point in $Y$ is vertically constant and its restriction to the $x$-axis is an element of $X$). It follows that $Y$ is strictly ergodic and that $P_Y(R_n)=n+1$ for all $n\in{\mathbb{N}}$. Corollary \[cor:gap\] shows that $Y$ is not a Jewett-Krieger model for any $\langle\times p,\times q\rangle$-ergodic measure on $[0,1)$.

Remarks on complexity growth
----------------------------

We conclude our introduction with a few brief remarks on Theorem \[thm:main\] and Corollary \[cor:gap\]. We show (Lemma \[lemma:finite\]) that any Jewett-Krieger model ${\widehat}X$ for an atomic $\langle S,T\rangle$-ergodic measure is a strictly ergodic ${\mathbb{Z}}^2$-subshift containing only doubly periodic ${\mathbb{Z}}^2$-colorings, meaning that there are only finitely many points in ${\widehat}X$. From this, it is easy to deduce that $P_{{\widehat}X}(R_n)$ is bounded independently of $n$ (by the number of points in ${\widehat}X$). Moreover, we show that if ${\widehat}X$ is a Jewett-Krieger model for $\mu$ and if ${\widehat}X$ contains only doubly periodic ${\mathbb{Z}}^2$-colorings, then $\mu$ is atomic.

A strategy for proving Theorem \[thm:main\] is therefore to find a nontrivial growth rate of $P_{{\widehat}X}(R_n)$ which implies that ${\widehat}X$ contains only doubly periodic ${\mathbb{Z}}^2$-colorings. A simple example of such a rate follows from the classical Morse-Hedlund Theorem @MH: if there exists $n\in{\mathbb{N}}$ such that $P_{{\widehat}X}(R_n)\leq n$, then ${\widehat}X$ contains only doubly periodic ${\mathbb{Z}}^2$-colorings (see e.g. the proof of Theorem 1.2 in @PO). In fact this bound is sharp: there exist ${\mathbb{Z}}^2$-colorings that are not doubly periodic and yet satisfy $P_{{\widehat}X}(R_n)=n+1$ for all $n\in{\mathbb{N}}$. Many other subquadratic growth rates can also be realized by strictly ergodic ${\mathbb{Z}}^2$-subshifts that do not contain doubly periodic points (see, for example, @pansiot). Therefore, a weak version of Theorem \[thm:main\] that replaces the assumption that there exists $n\in{\mathbb{N}}$ such that $P_{{\widehat}X}(R_n)\leq\frac{1}{2}\cdot n^2$ with the stronger assumption that there exists $n\in{\mathbb{N}}$ such that $P_{{\widehat}X}(R_n)\leq n$, follows from the Morse-Hedlund Theorem. However, this weak theorem relies on the fact that there are simply no strictly ergodic ${\mathbb{Z}}^2$-subshifts for which $P_{{\widehat}X}(R_n)$ is unbounded but for which $P_{{\widehat}X}(R_n)\leq n$ (for some $n$). The complexity gap provided by this weak theorem is therefore trivial in the sense that there are no strictly ergodic ${\mathbb{Z}}^2$-subshifts whose complexity function lies in this gap.

On the other hand, there do exist strictly ergodic ${\mathbb{Z}}^2$-subshifts with unbounded complexity and such that $P_{{\widehat}X}(R_n)<\frac{1}{2}\cdot n^2$. This is the interest in Theorem \[thm:main\] and Corollary \[cor:gap\]. The content of the theorem is that although such ${\mathbb{Z}}^2$-systems exist, they can not be Jewett-Krieger models of $\langle S,T\rangle$-ergodic measures on $[0,1)$. This is analogous to Theorem \[Rud:comb\], which says that although there are strictly ergodic ${\mathbb{Z}}^2$-subshifts that have small but positive entropy, they are not Jewett-Krieger models of $\langle S,T\rangle$-ergodic measures on $[0,1)$. Moreover, analogous to the hypothesis of Corollary \[cor:gap\] which relies on the growth rate of $P_{{\widehat}X}(\cdot)$, the hypothesis of Theorem \[Rud:comb\] is a condition on the growth rate of the relative complexity function $N(\cdot,\cdot)$ of Lemma \[lemma:compute\], with respect to the action of the horizontal shift (a similar statement holds for the vertical shift).

Proof of Theorem \[thm:main\]
=============================

Throughout this section, we assume that $p, q\geq 2$ are multiplicatively independent integers and that $\mu$ is a Borel probability measure on $[0,1)$ which is invariant under both $$\begin{aligned}
Sx&:=&px\text{ (mod $1$)}; \\ 
Tx&:=&qx\text{ (mod $1$)} \end{aligned}$$ and is ergodic with respect to the joint action $\langle S,T\rangle$. Let $\mathcal{B}$ denote the associated Borel $\sigma$-algebra on $[0,1)$

The natural extension {#sec:natural-extension}
---------------------

Let $X$ be the natural extension of the ${\mathbb{N}}^2$-system $([0,1),\mathcal{B},\mu,S,T)$. Specifically (following @Pet), let $$X:=\left\{y\in[0,1)^{{\mathbb{Z}}^2}\colon y(i+1,j)=Sy(i,j)\text{ and }y(i,j+1)=Ty(i,j)\text{ for all }i,j\in{\mathbb{Z}}\right\},$$ and for $(i,j)\in{\mathbb{Z}}^2$ let $\pi_{(i,j)}\colon X\to[0,1)$ be the map $\pi_{(i,j)}(y)=y(i,j)$. Define a countably additive measure $\mu_X$ on the $\sigma$-algebra $$\bigcup_{i=0}^{\infty}\pi_{(-i,-i)}^{-1}\mathcal{B}$$ by setting $\mu_X(\pi_{(-i,-i)}^{-1}A):=\mu(A)$. Let $\mathcal{X}$ be the completion of this $\sigma$-algebra with respect to $\mu_X$. Let $S_X,T_X\colon X\to X$ be the left shift and the down shift, respectively. Thus $\pi_{(0,0)}$ defines a measure theoretic factor map from $(X,\mathcal{X},\mu_X,S_X,T_X)$ to $([0,1),\mathcal{B},\mu,S,T)$. Moreover, $\mu_X$ is ergodic if and only if $\mu$ is ergodic. By construction, $h_{\mu}(S)=h_{\mu_X}(S_X)$, $h_{\mu}(T)=h_{\mu_X}(T_X)$, and $h_{\mu}(\langle S,T\rangle)=h_{\mu_X}(\langle S_X, T_X\rangle)$.

The advantage of working with $(X,\mathcal{X},\mu_X,S_X,T_X)$ instead of the original system is that the natural extension is an ergodic ${\mathbb{Z}}^2$-system.

Jewett-Krieger models and periodicity
-------------------------------------

If the two dimensional entropy of a system is positive, then the entropy of every one dimensional subsystem is infinite (for a proof, see, for example, @Sinai). In our setting, since $h_{\mu}(S)\leq h_{\text{top}}(S)=\log(p)$ (and $h_{\mu}(T)\leq h_{\text{top}}(T)=\log(q)$), it follows that the measure theoretic entropy of the joint action generated by $\langle S,T\rangle$ on $[0,1)$ with respect to $\mu$ is also zero. It follows that the measure theoretic entropy with respect to $\mu_X$ of the joint action on $X$ generated by $\langle S_X,T_X\rangle$ is zero. Therefore, by Theorem \[thm:rosenthal\], there exists a strictly ergodic subshift ${\widehat}X\subset\{0,1\}^{{\mathbb{Z}}^2}$ such that $(X,\mathcal{X},\mu_X,S_X,T_X)$ is measure theoretically isomorphic to $({\widehat}X,{\widehat}{\mathcal{X}},\nu,\sigma,\tau)$, where ${\widehat}{\mathcal{X}}$ is the Borel $\sigma$-algebra on ${\widehat}X$, $\sigma,\tau\colon{\widehat}X\to{\widehat}X$ denote the left shift and down shift (respectively), and $\nu$ is the unique $\langle\sigma,\tau\rangle$-invariant Borel probability measure. Note that the choice of ${\widehat}X$ is not necessarily unique.

\[lemma:finite\] If $(X,\mathcal{X},\mu_X,S_X,T_X)$ is an atomic system, then any Jewett-Krieger model $({\widehat}X,{\widehat}{\mathcal{X}},\nu,\sigma,\tau)$ for $(X,\mathcal{X},\mu_X,S_X,T_X)$ is finite.

Let $\pi\colon ({\widehat}X,{\widehat}{\mathcal{X}},\nu,\sigma,\tau)\to (X,\mathcal{X},\mu_X,S_X,T_X)$ be an isomorphism and let $x\in X$ be an atom. Then there exist full measure sets ${\widehat}X_1\subset{\widehat}X$ and $X_1\subset X$ such that $\pi\colon{\widehat}X_1\to X_1$ is a bijection which interwines the ${\mathbb{Z}}^2$ actions. Every atom in $X$ is contained in $X_1$, and if $x\in X_1$ is an atom then there exists unique $y\in{\widehat}X_1$ such that $\pi(y)=x$. It follows that $\nu(\{y\})=\mu_X(\{x\})>0$ and so $y$ is an atom in ${\widehat}X$. By the Poincaré Recurrence Theorem, there exists $(i,j)\in{\mathbb{Z}}^2\setminus\{(0,0)\}$ such that $S_X^iT_X^jy=y$. Let $V_y:=\{(i,j)\in{\mathbb{Z}}^2\setminus\{(0,0)\}\colon S_X^iT_X^jy=y\}$ be the (nonempty) set of nontrivial period vectors for $y$. If $\text{dim}(\text{Span}(V_y))=1$, then $$\lim_{N\to\infty}\frac{1}{(2N+1)^2}\sum_{-N\leq i,j\leq N}1_{\{y\}}(S_X^iT_X^jy)=0<\nu(\{y\}),$$ which contradicts the pointwise ergodic theorem. Therefore $\text{dim}(\text{Span}(V_y))=2$ and $y\in{\mathcal{A}}^{{\mathbb{Z}}^2}$ is doubly periodic. Moreover, for $\nu$-a.e. $z\in{\widehat}X$ we have $S_X^iT_X^jz=y$ for some $(i,j)\in{\mathbb{Z}}^2$ and so $z$ is also doubly periodic (with periods equal to those of $y$). Thus there are only finitely many points $z\in{\widehat}X$.

Since ${\widehat}X$ is minimal, and hence transitive, we can use the following tool for studying the dynamics of $(X,\mathcal{X},\mu_X,S_X,T_X)$:

\[Cyr & Kra @CK\]\[thm:CK\] If $(X, \sigma, \tau)$ is a transitive ${\mathbb{Z}}^2$-subshift and there exist $n,k\in{\mathbb{N}}$ such that $P_{X}(n,k)\leq nk/2$, then there exists $(i,j)\in{\mathbb{Z}}^2\setminus\{(0,0)\}$ such that $\sigma^i\tau^jx=x$ for all $x\in X$.

\[lem:intermediate\] If there exists $(i,j)\in{\mathbb{Z}}^2\setminus\{(0,0\}$ such that $\sigma^i\tau^j x  = x$ for every $x\in {\widehat}X$, then $S_X^iT_X^j x=x$ for $\mu$-almost every $x\in X$.

Let $\psi\colon{\widehat}X\to X$ be an isomorphism. Thus there exist ${\widehat}X_1\subset{\widehat}X$ and $X_1\subset X$ such that $\nu({\widehat}X_1)=\mu_X(X_1)=1$, $\psi\colon{\widehat}X_1\to X_1$ is a bi-measurable bijection, $\psi_*\nu=\mu_X$, $\psi\circ\sigma=S_X\circ\psi$, and $\psi\circ\tau=T_X\circ\psi$. Let $E=\{x\in X_1\colon S_X^iT_X^jx\neq x\}$. Since $\psi^{-1}(E)=\{y\in{\widehat}X_1\colon\sigma^i\tau^jy\neq y\}$, it follows that $\mu_X(E)=\nu(\psi^{-1}(E))=0$.

\[th:one-to-all\] If there exist $n,k\in{\mathbb{N}}$ such that $P_{{\widehat}X}(n,k)\leq nk/2$, then $\mu$ is atomic. Moreover, if ${\widehat}Y$ is any other Jewett-Krieger model for $([0,1),\mathcal{B},\mu,S,T)$, then $P_{{\widehat}Y}(n,k)$ is bounded independent of $n,k\in{\mathbb{N}}$.

Combining Theorem \[thm:CK\] and Lemma \[lem:intermediate\], there exist $(i,j)\in{\mathbb{Z}}^2\setminus\{(0,0\}$ such that $S_X^iT_X^jx=x$ for $\mu_X$-a.e. $x\in X$. Therefore $(S_X^iT_X^jx)(0,0)=x(0,0)$ for $\mu_X$-a.e. $x\in X$. It is immediate that we also have $(S_X^{-i}T_X^{-j}x)(0,0)=x(0,0)$ for $\mu_X$-a.e. $x\in X$. So there are two cases to consider, depending on the the sign of $i\cdot j$.

### Case 1 {#case-1 .unnumbered}

Suppose $i\cdot j\geq0$. Then, replacing by $-i$ and $-j$ if necessary, we can assume that both $i$ and $j$ are nonnegative. Set $E:=\{y\in[0,1)\colon S^iT^jy\neq y\}$ and let $y\in E$. Then if $x\in\pi^{-1}(y)$, we have that $S_X^iT_X^jx\neq x$. Thus $\mu(E)=\mu_X(\pi^{-1}(E))=0$ and so $S^iT^jy=y$ for $\mu$-a.e. $y\in[0,1)$.

Now observe that $S^iT^jy=y$ is equivalent to the statement that $$p^iq^jy=y\text{ (mod $1$)},$$ which only has finitely many solutions in the interval $[0,1)$. Therefore, $\mu$ is supported on a finite set. Since $\mu$ is $\langle S,T\rangle$-invariant, this set must be $S$- and $T$-invariant. Therefore there exist $a,b\in{\mathbb{N}}$ such that $S^a$ and $T^b$ are both equal to the identity $\mu$-almost everywhere.

### Case 2 {#case-2 .unnumbered}

Suppose $i\cdot j<0$. Again, replacing by $-i$ and $-j$ if necessary, we can assume that $i<0$ and $j>0$. Now set $E:=\{y\in[0,1)\colon S^{|i|}y\neq T^jy\}$. Thus if $y\in E$ and $x\in\pi^{-1}(y)$, then $x(-i,j)\neq x(0,0)=y$ as $S^{|i|}(x(-i,j))=x(0,j)=T^j(x(0,0))$ by construction. Therefore $S^iT^jx\neq x$ and so $\mu(E)=\mu_X(\pi^{-1}(E))=0$. It follows that $S^{|i|}y=T^jy$ for $\mu$-a.e. $y\in[0,1)$.

Finally observe that $S^{|i|}y=T^jy$ is equivalent to $$p^{|i|}y=q^jy\text{ (mod $1$)}.$$ As $p$ and $q$ are multiplicatively independent, there are only finitely many solutions in the interval $[0,1)$. Therefore, again, $\mu$ is supported on a finite set and there exist $a,b\in{\mathbb{N}}$ such that $S^a$ and $T^b$ are both equal to the identity $\mu$-almost everywhere.

This establishes the first claim of the theorem. By Lemma \[lemma:finite\], any Jewett-Krieger model of an atomic system is finite, and the second statement follows.

We use this to complete the proof of Theorem \[thm:main\]:

\[Proof of Theorem \[thm:main\]\] Let $\mu$ be a Borel probability measure on $[0,1)$ that is $\langle S,T\rangle$-ergodic. If this two dimensional action is not free, arguing as in the proof of Theorem \[th:one-to-all\] that $\mu$ is an atomic measure, we are done. Thus we can assume that the action is free, and similarly the action for the natural extension is also free.

Let $({\widehat}X,{\widehat}{\mathcal{X}},\nu,\sigma,\tau)$ be a Jewett-Krieger model for the natural extension of the system $([0,1),\mathcal{B},\mu,S,T)$. If there is no such model satisfying the additional property that there exist $n,k\in{\mathbb{N}}$ satisfying $P_{{\widehat}X}(n,k)\leq nk/2$, then the conclusion of the Theorem holds vacuously. Thus it suffices to assume that there exists a Jewett-Krieger model $({\widehat}X,{\widehat}{\mathcal{X}},\nu,\sigma,\tau)$ with the property that there exist $n,k\in{\mathbb{N}}$ satisfying $P_{{\widehat}X}(n,k)\leq nk/2$. By Theorem \[th:one-to-all\], $([0,1),\mathcal{B},\mu,S,T)$ is atomic.

Higher dimensions
=================

Theorem \[thm:main\] shows that if $\mu$ is any nonatomic $\times p$, $\times q$ ergodic measure then the natural extension of $([0,1),\mathcal{X},\mu,S,T)$ cannot be measurably isomorphic to any ${\mathbb{Z}}^2$-subshift of whose complexity function satisfies $P_X(n,n)=o(n^2)$. It is natural to ask whether this result can be generalized to higher dimensions. In particular, if $p_1,\dots,p_d$ are a multiplicatively independent set of integers and $\mu$ is a nonatomic $\times p_1,\dots,\times p_d$ ergodic measure, we can ask if the natural extension of $(X,\mathcal{X},\mu,\times p_1,\dots,\times p_d)$ could have a topological model whose complexity function is $o(n^d)$.

The same method used in the two dimensional case suggests a path to proving this result. If one could show that any free, strictly ergodic ${\mathbb{Z}}^d$-subshift whose complexity function is $o(n^d)$ is periodic, then it would follow that no such topological model for $\mu$ exists. However, the analog of Theorem \[thm:CK\] in dimension $d>2$ is false. Julien Cassaigne @Cas has shown that for $d>2$, there exists a minimal ${\mathbb{Z}}^d$-subshift $X$ whose elements are not periodic in any direction, and is such that for any $\varepsilon>0$ we have $P_X(n,n,\dots,n)=o(n^{2+\varepsilon})$. On the other hand, the authors have recently shown @CK2 that the analog of Theorem \[thm:CK\] does hold for dimension $d>2$ if a certain expansiveness assumption is imposed on the subshift.

If $Y\subset{\mathcal{A}}^{{\mathbb{Z}}^d}$ is a subshift, then we say that the $x$-axis in ${\mathbb{Z}}^d$ is <span>*strongly expansive*</span> if whenever $x,y\in X$ have the same restriction to the $x$-axis, we have $x=y$. In this case, if $X\subset{\mathcal{A}}^{{\mathbb{Z}}}$ is the subshift obtained by restricting elements of $Y$ to the $x$-axis, then there exist homeomorphisms $\tau_1,\dots,\tau_{d-1}\colon X\to X$ which commute pairwise and with the shift $\sigma$ and are such that for any $y\in Y$ we have $y(i_1,i_2,\dots,i_d)=\left(\tau_1^{i_1}\tau_2^{i_2}\cdots\tau_{d-1}^{i_{d-1}}\sigma^{i_d}\pi_X(y)\right)(0)$ for all $i_1,\dots,i_d\in{\mathbb{Z}}^d$, where $\pi_X(y)$ denotes the restriction of $y$ to the $x$-axis. In previous work, we have shown that:

\[Cyr & Kra @CK2\] Let $X\subset{\mathcal{A}}^{{\mathbb{Z}}}$ be a minimal subshift and let $\tau_1,\dots,\tau_{d-1}\colon X\to X$ be homeomorphisms of $X$ that commute with the shift $\sigma$. If $\langle\sigma,\tau_1,\dots,\tau_{d-1}\rangle\cong{\mathbb{Z}}^d$, then $\liminf_{n\to\infty}P_X(n)/n^d>0$.

With some additional effort, the same result can be shown if the assumption that $(X,\sigma)$ is minimal (as a ${\mathbb{Z}}$-system) is relaxed to only require that $(X,\sigma,\tau_1,\dots,\tau_d)$ is minimal (as a ${\mathbb{Z}}^d$-system). Thus, the only obstruction to generalizing Theorem \[thm:main\] to the higher dimensional setting is the following:

For every nonatomic Borel probability $\mu$ on $[0,1)$ which is ergodic for the joint action of $\times p_1,\dots,\times p_d$, there is a strongly expansive, minimal topological model for $(X,\mathcal{X},\mu,\times p_1,\dots,\times p_d)$.

If this conjecture holds, then if follows that any such system is measurably isomorphic to a subshift whose complexity function grows on the order of $n^d$.

<span>99</span> A counterexample to a conjecture of Lagarias and Pleasants. (2006).

Nonexpansive ${\mathbb{Z}}^2$-subdynamics and Nivat's conjecture. <span>*Trans. Amer. Math. Soc.*</span> <span>**367**</span> (2015), no. 9, 6487–6537.

The automorphism group of a minimal shift of stretched exponential growth. arXiv: 1509.08493.

. Disjointness in ergodic theory, minimal sets, and a problem in diophantine approximation. <span>*Math. Sys. Theory*</span> <span>**1**</span> (1967), 1-49.

. The prevalence of uniquely ergodic systems. <span>*J. Math. Mech.*</span> <span>**19**</span> 1969/1970 717-729.

. Measures on the circle invariant under multiplication by a nonlacunary subsemigroup of the integers. <span>*Isr. J. Math.*</span> <span>**77**</span> (1992), 211–240.

. Introduction to the modern theory of dynamical systems. Encyclopedia of Mathematics and its Applications, 54. Cambridge University Press, Cambridge, 1995.

. On unique ergodicity. Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. II: Probability theory, pp. 327-346, Univ. California Press, Berkeley, Calif., 1972.

. On measures simultaneously $2$- and $3$-invariant. <span>*Israel J. Math*</span> <span>**61**</span> (1988), no. 2, 219-224.

. Symbolic dynamics II. Sturmian trajectories. <span>*Amer. J. Math.*</span> <span>**62**</span> (1940) 1–42.

. Invited talk at ICALP, Bologna, 1997.

. Complexité des facteurs des mots infinis engendrés par morphismes itérés. Automata, languages and programming (Antwerp, 1984), 380–389, Lecture Notes in Comput. Sci., 172, Springer, Berlin, 1984.

. Extender sets and multidimensional subshifts. <span>*Ergod. Th. Dyn. Sys.*</span> (2016) http://dx.doi.org/10.1017/etds.2014.71.

. Ergodic theory. Cambridge Studies in Advanced Mathematics, 2. Cambridge University Press, Cambridge, 1983.

. Finite uniform generators for ergodic, finite entropy, free actions of amenable groups. <span>*Probab. Theory Related Fields*</span> <span>**77**</span> (1988), no. 2, 147-166.

. $\times2$ and $\times3$ invariant measures and entropy. <span>*Ergod. Th. Dyn. Sys.*</span> <span>**10**</span> (1990), no. 2, 395-406.

Ya. Sinai. Topics in ergodic theory. Princeton Mathematical Series, 44. Princeton University Press, Princeton, NJ, 1994

. Strictly ergodic models for dynamical systems. <span>*Bull. Amer. Math. Soc. (N.S.)*</span> <span>**13**</span> (1985), no. 2, 143-146.

[^1]: The second author was partially supported by NSF grant 1500670.

{'source': 'arXiv_out/1602'}