Nivat's conjecture after Cyr-Kra

Posted by: matheuscmss | January 27, 2013

Nivat’s conjecture after Cyr-Kra

Bryna Kra gave a talk (last Thursday (January 24, 2013)) at Orsay about her joint work with Van Cyr on Nivat’s conjecture. The talk was peculiar in several aspects: despite the remarkable fact that Bryna was speaking in French while writing in English at the blackboard (at normal pace without mixing up the languages!), she was able to successfully explains some of the dynamical ideas behind her joint paper with V. Cyr. In particular, I thought that the readers of this blog who missed Bryna’s talk(s) on this subject could benefit from my notes that I’ll transcript below.

1. Introduction

Let ${\mathcal{A}}$ be a finite alphabet and ${\eta:\mathbb{Z}\rightarrow\mathcal{A}}$ a (bi-infinite) word, ${\eta=(\eta_n)_{n\in\mathbb{Z}}=(\eta(n))_{n\in\mathbb{Z}}\in\mathcal{A}^{\mathbb{Z}}}$ .

We define ${P_{\eta}(n)}$ as the number of configurations (words) in ${\eta}$ of length ${n}$ . Intuitively, the quantities ${P_{\eta}(n)}$ measure how complicated the word ${\eta}$ at finite scales, and this is why ${P_{\eta}(n)}$ is called complexity function.

We say that ${\eta}$ is periodic if there exists ${m\in\mathbb{N}}$ (called a period of ${\eta}$ ) such that ${\eta(n+m)=\eta(n)}$ for all ${n\in\mathbb{Z}}$ .

Theorem 1 (Morse-Hedlund (1940)) A word ${\eta\in\mathcal{A}^{\mathbb{Z}}}$ is periodic if and only if there exists ${n_0}$ such that ${P_{\eta}(n_0)\leq n_0}$ .

Below we will present the proof of this result (originally proved here) because it is not specially hard and it contains an ingredient that we will encounter later in this post.

Proof: If ${\eta}$ is periodic, then it is not hard to convince oneself that ${P_{\eta}(n_0)\leq n_0}$ whenever ${n_0}$ is a period of ${\eta}$ .

Conversely, we note that we can assume that ${P_{\eta}(1)\geq 2}$ . Indeed, if ${P_{\eta}(1)=1}$ , then ${\eta}$ is a constant word and the desired result is obvious. Next, we observe that ${P_{\eta}(n)\leq P_{\eta}(n+1)}$ for all ${n\in\mathbb{N}}$ (by definition). Therefore, the assumption that ${P_{\eta}(n_0)\leq n_0}$ implies that there exists ${0<k<n_0}$ such that ${P_{\eta}(k)=P_{\eta}(k+1)}$ .

By definition, the equality ${P_{\eta}(k)=P_{\eta}(k+1)}$ means that given any subword ${w}$ of ${\eta}$ of length ${k}$ , there exists an unique way to select a letter ${a\in\mathcal{A}}$ in order to extend ${w}$ into a sub-word ${wa}$ of ${\eta}$ of length ${k+1}$ . In order words, the knowledge of any word of length ${k}$ permits to reconstruct ${\eta}$ . From this, it is not hard to see that ${\eta}$ is periodic: indeed, since ${P_{\eta}(k)\leq P_{\eta}(n_0)\leq n_0}$ , we see that there is a word ${w_0}$ of length ${k}$ appearing twice in ${\eta}$ (it suffices to consider the ${n_0}$ -first translates by ${k}$ of any word of length ${k}$ and observe that there must be a repetition somewhere because we dispose only of ${P_{\eta}(k)\leq n_0}$ distinct patterns for words of length ${k}$ ); since there is an unique way to extend ${w_0}$ , we see that ${\eta}$ consists of a repetition of the letters between two consecutives appearances of ${w_0}$ , and, a fortiori, ${\eta}$ is periodic. $\Box$

As you just saw, an important aspect in the last part of the proof of Morse-Hedlund theorem is the recurrence of words (i.e., finite subwords appear infinitely often). In fact there is a whole literature dedicated to recurrent words, but we will not mention it here. Instead, let us just mention that, if ${\eta}$ is recurrent, then the following statements are equivalent:

${\eta}$ is periodic
the complexity function ${P_{\eta}(n)}$ is bounded
there exists ${n_0}$ such that ${P_{\eta}(n_0)\leq n_0}$

Also, a recurrent word ${\eta}$ such that ${P_{\eta}(n)=n+1}$ is called Sturmian word, and the so-called Thue-Morse sequence is a famous example of (uniformly) recurrent word that is not periodic (nor eventually periodic).

2. Nivat’s conjecture

Let us consider words indexed by ${\mathbb{Z}^d}$ , ${d\geq 1}$ , i.e., elements of ${\mathcal{A}^{\mathbb{Z}^d}}$ where ${\mathcal{A}}$ is our preferred alphabet.

Note that, for ${d\geq 2}$ , the notion of periodicity can be generalized in several ways. For her purposes, Bryna considered the following two notions:

Definition 2 We say that ${\eta\in\mathcal{A}^{\mathbb{Z}^d}}$ is periodic if there exists ${\overline{m}\neq \overline{0}}$ such that ${\eta(\overline{n})=\eta(\overline{n}+\overline{m})}$ . In other words, ${\eta}$ is periodic if the restriction of ${\eta}$ to some line ( ${1}$ -dimensional subspace) is periodic. Similarly, we say that ${\eta}$ is fully periodic if it is periodic along a set of ${d}$ linearly independent lines.

Analogously to the case of words in ${\mathcal{A}^{\mathbb{Z}}}$ , we can introduce complexity functions ${P_{\eta}(n_1,\dots,n_d)}$ counting the number of configurations of a rectangle ${[0,n_1-1]\times\dots\times [0,n_d-1]}$ , or, more generally, given ${S\subset\mathbb{Z}^d}$ , we can define ${P_{\eta}(S)}$ as the number of configurations obtained after translating ${S}$ around ${\mathbb{Z}^d}$ .

The next proposition says that the characterization of full periodicity is very similar to the case of ${\mathcal{A}^{\mathbb{Z}}}$ :

Proposition 3 ${\eta\in\mathcal{A}^{\mathbb{Z}^d}}$ is fully periodic if and only if the complexity function ${P_{\eta}(n_1,\dots,n_d)}$ is bounded.

Proof: It is clear that if ${\eta}$ is fully periodic then ${P_{\eta}(n_1,\dots,n_d)}$ is bounded.

Conversely, if ${P_{\eta}(n_1,\dots,n_d)}$ is bounded, the idea is that we can reduce our task to the Morse-Hedlund theorem: indeed, if ${P_{\eta}(1,\dots, 1,n,1\dots,1)\leq M}$ , then, it is not hard to convince oneself that ${M d!}$ is a period for ${\eta}$ . $\Box$

On the other hand, the characterization of periodicity is a more subtle task, and, in fact, Nivat’s conjecture concerns the following partial characterization of periodicity for words in ${\mathcal{A}^{\mathbb{Z}^2}}$ :

Nivat’s conjecture (1997). Let ${\eta\in\mathcal{A}^{\mathbb{Z}^2}}$ . If there are ${n, k}$ such that ${P_{\eta}(n,k)\leq nk}$ , then ${\eta}$ is periodic.

Note that Nivat’s conjecture is “optimal” in the following sense: by taking ${\mathcal{A}=\{0,1\}}$ and by letting ${\eta\in\mathcal{A}^{\mathbb{Z}^2}}$ be the aperiodic word given by ${\eta(0,0)=1}$ and ${\eta(n,m)=0}$ elsewhere, then ${P_{\eta}(n,k)=nk+1}$ .

Also, Nivat’s conjecture is a “two-dimensional conjecture”: Tijdeman observed that, for ${\mathcal{A}=\{0,1\}}$ and ${d=3}$ , the aperiodic word ${\eta\in\mathcal{A}^{\mathbb{Z}^3}}$ given by ${\eta_{i,0,0}=1}$ , ${\eta_{0,j,k_0}=1}$ and ${\eta_{i,j,k}=0}$ otherwise (where ${k_0\neq 0}$ is fixed) satisfies ${P_{\eta}(n,n,n)\leq n^3}$ ; furthemore, given ${d\geq 3}$ and ${n\in\mathbb{N}}$ , Sander and Tijdeman constructed aperiodic words ${\eta}$ in ${\mathcal{A}^{\mathbb{Z}^d}}$ such that ${P_{\eta}(n,\dots,n)=2n^{d-1}+1}$ .

Finally, as it was noticed by J. Cassaigne, and Berthé and Vuillon, there is no converse to Nivat’s conjecture: there are periodic words ${\eta}$ in ${\mathcal{A}^{\mathbb{Z}^2}}$ such that ${P_{\eta}(n,k)=2^{n+k-1}}$ for all ${n,k\in\mathbb{N}}$ .

Currently, we dispose of some results towards Nivat’s conjecture:

Sander and Tijdeman (2002) showed that if ${P_{\eta}(2,n)\leq 2n}$ or ${P_{\eta}(n,2)\leq 2n}$ for some ${n\in\mathbb{N}}$ , then ${\eta}$ is periodic.
Epifanio, Koskas and Mignosi (2003) proved that if ${P_{\eta}(n,k)\leq nk/144}$ for some ${n,k\in\mathbb{N}}$ , then ${\eta}$ is periodic.
Quas and Zamboni (2004) improved the result of the previous item by showing that if ${P_{\eta}(n,k)\leq nk/16}$ for some ${n,k\in\mathbb{N}}$ , then ${\eta}$ is periodic.

The main result of Bryna’s talk was the following theorem joint with V. Cyr:

Theorem 4 (Cyr-Kra) If ${P_{\eta}(n,k)\leq nk/2}$ for some ${n,k\in\mathbb{N}}$ , then ${\eta}$ is periodic.

As Bryna pointed out, the proof of this result is dynamical in nature, and, thus, we will need to introduce a couple of definitions.

Let us equip our finite alphabet ${\mathcal{A}}$ with the discrete topology, and let us equip ${X=\mathcal{A}^{\mathbb{Z}^d}}$ with the product topology. We denote by ${T}$ the shift dynamics of ${\mathbb{Z}^d}$ on ${X}$ :

$\displaystyle T^{\overline{u}}\eta(\overline{n}):=\eta(\overline{n}+\overline{u})$

for each ${\overline{u}\in\mathbb{Z}^d}$ . Note that, for our choice of topology, ${T^{\overline{u}}:X\rightarrow X}$ is continuous.

Given ${\eta\in X}$ , let us denote by ${X_{\eta}}$ the closure of the orbit of ${\eta}$ , i.e.,

$\displaystyle X_{\eta}=\overline{\mathcal{O}(\eta)}:=\overline{\{T^{\overline{u}}(\eta): \overline{u}\in\mathbb{Z}^d\}}$

As it is well-known, the orbit closure ${X_{\eta}}$ is intimately related to the combinatorial properties of ${\eta}$ . For example, the reader is invited to check that ${\eta}$ is periodic if and only if ${T^{\overline{u}}}$ doesn’t act faithfully on ${X_{\eta}}$ , and, for ${d=2}$ , ${\eta}$ is fully (i.e., doubly) periodic if and only if ${X_{\eta}}$ is finite.

Besides the shift dynamics, we will also need the notion of (non-)expansive subspaces for a ${\mathbb{Z}^d}$ action. In order to motivate this definition, let us firstly recall the notion of expansiveness in the sense of R. Bowen:

Definition 5 Let ${(X,d)}$ be a compact metric space and ${T}$ a homeomorphism of ${X}$ . We say that ${T}$ is expansive if there exists ${\delta>0}$ such that if ${d(T^n(x),T^n(y))\leq\delta}$ for all ${n\in\mathbb{Z}}$ then ${x=y}$ . In other words, ${T}$ is expansive if we can “reasonably separate” (from a fixed amount ${\delta>0}$ ) any pair of distinct points by iterating them.

In 1997, Boyle and Lind generalized this notion for ${\mathbb{Z}^d}$ -actions:

Definition 6 (Boyle and Lind) Let ${(X,d)}$ be a compact metric space and ${T}$ a continuous ${\mathbb{Z}^d}$ -action on ${X}$ . We say that ${V\subset\mathbb{R}^d}$ is expansive if there are a expansiveness radius ${r>0}$ and a expansiveness constant ${\delta>0}$ such that if

$\displaystyle d(T^{\overline{u}}(x), T^{\overline{u}}(y))\leq \delta$

for all ${\overline{u}}$ with ${dist(\overline{u}, V)\leq r}$ , then ${x=y}$ . (Here, ${dist}$ is the Euclidean distance.) In other words, ${V}$ is expansive if we can reasonaly separate any pair of distinct point by iterating them using elements of ${\mathbb{Z}^d}$ approximatively pointing in the direction of ${V}$ .

For our preferred example ${X=\mathcal{A}^{\mathbb{Z}^d}}$ , we have that ${V\subset \mathbb{R}^d}$ is expansive if there exists ${r>0}$ such that if ${x(\overline{n})=y(\overline{n})}$ for all ${n\in V^r=\{\overline{u}: dist(\overline{u},V)\leq r\}}$ , then ${x=y}$ .

In what follows, we will be interested in non-expansive subspaces.

Before passing to abstract results, let us give the following concrete (and instructive) example. Consider ${\mathcal{A}=\mathbb{Z}/2\mathbb{Z}}$ and consider the subset ${X}$ of ${\mathcal{A}^{\mathbb{Z}^2}}$ consisting of all ${x(i,j)\in \mathcal{A}^{\mathbb{Z}^2}}$ such that

$\displaystyle x(i,j)+x(i+1,j)+x(i,j-1)=0 (\textrm{mod }2)$

In the literature, the shift dynamics on ${X}$ is known as Ledrappier’s 3-dots systems. This dynamical system has several interesting properties (see, e.g, this blog post of Terence Tao for the relationship between this example and Rokhlin’s mixing problem), but, for the sake of her talk, Bryna mentioned just that it has three non-expansive lines, namely:

$\displaystyle \{(x,y)\in\mathbb{R}^2: y=0\}, \, \{(x,y)\in\mathbb{R}^2: x=0\}, \, \{(x,y)\in\mathbb{R}^2: x+y=1\}$

After this example, it is time to state some abstract results:

Theorem 7 (Boyle and Lind) If ${X}$ is an infinite compact metric space with a continuous ${\mathbb{Z}^d}$ action, then, for each ${0\leq k<d}$ , there exists a non-expansive subspace of ${\mathbb{R}^d}$ of dimension ${k}$ .

By taking ${d=2}$ and ${X=X_{\eta}=\overline{\mathcal{O}(\eta)}\subset\mathcal{A}^{\mathbb{Z}^2}}$ , one has the following corollary:

Corollary 8 For ${d=2}$ , ${\eta}$ is doubly (i.e., fully) periodic ${\iff}$ ${X_{\eta}}$ is finite ${\iff}$ every ${1}$ -dimensional subspace of ${\mathbb{R}^2}$ is expansive.

In this context, V. Cyr and B. Kra actually show the following result:

Theorem 9 (Cyr and Kra) Let ${\eta\in\mathcal{A}^{\mathbb{Z}^2}}$ be a word such that ${P_{\eta}(n,k)\leq nk}$ . Assume that there exists an unique non-expansive subspace of dimension for the shift dynamics on ${X_{\eta}=\overline{\mathcal{O}(\eta)}\subset \mathcal{A}^{\mathbb{Z}^2}}$ . Then, ${\eta}$ is periodic (but not doubly periodic).

The basic idea behind this theorem is that all periods of ${\eta}$ belong to the unique non-expansive line.

Anyhow, from this theorem, one can deduce Nivat’s conjecture if we can show that there is at most one non-expansive subspace. In order to show this last property, Cyr and Kra need the hypothesis ${P_{\eta}(n,k)\leq nk/2}$ :

Theorem 10 (Cyr and Kra) Let ${\eta\in\mathcal{A}^{\mathbb{Z}^2}}$ be a word such that ${P_{\eta}(n,k)\leq nk/2}$ for some ${n,k\in\mathbb{N}}$ . Then, there is at most one non-expansive direction.

In summary, for ${\eta\in\mathcal{A}^{\mathbb{Z}^2}}$ :

${\eta}$ is doubly periodic if and only if there is no non-expansive ${1}$ -dimensional subspaces.
if there is an unique non-expansive ${1}$ -dimensional subspace, then ${\eta}$ is periodic but not doubly periodic.
in order to rule out the possible existence of at least two non-expansive ${1}$ -dimensional subspaces, one needs the assumption ${P_{\eta}(n,k)\leq nk/2}$ .

At this point, Bryna used the few minutes left to say a few words about the proofs of these results. Firstly, she mentioned that, similarly to the strategy used in the proof of Morse-Hedlund theorem, the basic idea is: one notices that if ${S_1\subset S_2\subset\mathbb{Z}^2}$ , then ${P_{\eta}(S_1)\leq P_{\eta}(S_2)}$ , and one looks for ${S}$ so that this inequality “stabilizes”.

Secondly, she made the previous paragraph a little more precise by introducing the notion of discrepancy

$\displaystyle D_{\eta}(S):=P_{\eta}(S)-|S|$

and by recalling the following lemma (cf. the proof of Lemma 2.1 in Cyr-Kra paper):

Lemma 11 If ${S\subset\mathbb{Z}^2}$ and ${x\in S}$ , then either

$\displaystyle D_{\eta}(S-\{x\})\leq D_{\eta}(S)$

or every ${\eta}$ -coloring of ${S-\{x\}}$ uniquely extends to a ${\eta}$ -coloring of ${S}$ .

Also, she noticed that the hypothesis of Nivat’s conjecture gives a rectangle ${R=[0,n-1]\times[0,k-1]}$ such that ${D_{\eta}(R)\leq 0}$ , and, by definition, ${D_{\eta}(\{x\})\leq|\mathcal{A}|-1}$ .

Then, she said that these properties combine “in a way similar to the proof of Morse-Hedlund theorem” to give the proposition:

Proposition 12 There exists ${S\subset\mathbb{Z}^2}$ such that, for all ${x\in S}$ , every ${\eta}$ -coloring of ${S-\{x\}}$ extends uniquely to a ${\eta}$ -coloring of ${S}$ .

Finally, Bryna mentioned that this set ${S}$ plays the role of the interval ${[0,k-1]}$ in the proof of Morse-Hedlund theorem, but, in order to be able to use ${S}$ in the same that we used ${[0,k-1]}$ , Bryna told us that one needs to control the geometry of ${S}$ . In particular, she told that Cyr and her shows that ${S}$ is convex and, from the assumption ${P_{\eta}(n,k)\leq nk/2}$ , it is possible to prove that ${S}$ occupies more than half of the rectangle ${R=[0,n-1]\times [0,k-1]}$ , and she concluded the talk by saying that essentially the convexity and the largeness of ${S}$ (inside ${R}$ ) are sufficient to conclude the their results.

About these ads

Posted in expository, math.CO, math.DS, Mathematics | Tags: Francois Ledrappier, discrepancy, Bryna Kra, Van Cyr, 3-dots system, Nivat's conjecture, complexity function, Mike Boyle, D. Lind, expansive systems, expansive subspaces, periodic words

Responses

Those of us who know Bryna are not surprised by such feats of simultaneity. What you didn’t notice was that, during the talk, she was also thinking about what wine she was going to drink in the evening while also tapping out the Kreutzer sonata with her foot.
By: galoisrepresentations on February 6, 2013
at 4:59 am

Reply

M	T	W	T	F	S	S
« Dec				Feb »
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

	Yale on A criterion for the simplicity…
	matheuscmss on IPAM’s program “In…
	Terence Tao on IPAM’s program “In…
	matheuscmss on Ergodicity of conservative dif…
	Andrés Navas on CF1: uniform distribution and…

Disquisitiones Mathematicae

Nivat’s conjecture after Cyr-Kra

Like this:

Responses

Leave a Reply Cancel reply

Categories

Archives

Mathematics

politics

Recent Posts

Tags

Top Posts

Recent Comments

Follow “Disquisitiones Mathematicae”