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.
Let be a finite alphabet and a (bi-infinite) word, .
We define as the number of configurations (words) in of length . Intuitively, the quantities measure how complicated the word at finite scales, and this is why is called complexity function.
We say that is periodic if there exists (called a period of ) such that for all .
Theorem 1 (Morse-Hedlund (1940)) A word is periodic if and only if there exists such that .
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 is periodic, then it is not hard to convince oneself that whenever is a period of .
Conversely, we note that we can assume that . Indeed, if , then is a constant word and the desired result is obvious. Next, we observe that for all (by definition). Therefore, the assumption that implies that there exists such that .
By definition, the equality means that given any subword of of length , there exists an unique way to select a letter in order to extend into a sub-word of of length . In order words, the knowledge of any word of length permits to reconstruct . From this, it is not hard to see that is periodic: indeed, since , we see that there is a word of length appearing twice in (it suffices to consider the -first translates by of any word of length and observe that there must be a repetition somewhere because we dispose only of distinct patterns for words of length ); since there is an unique way to extend , we see that consists of a repetition of the letters between two consecutives appearances of , and, a fortiori, is periodic.
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 is recurrent, then the following statements are equivalent:
- is periodic
- the complexity function is bounded
- there exists such that
2. Nivat’s conjecture
Let us consider words indexed by , , i.e., elements of where is our preferred alphabet.
Note that, for , the notion of periodicity can be generalized in several ways. For her purposes, Bryna considered the following two notions:
Definition 2 We say that is periodic if there exists such that . In other words, is periodic if the restriction of to some line (-dimensional subspace) is periodic. Similarly, we say that is fully periodic if it is periodic along a set of linearly independent lines.
Analogously to the case of words in , we can introduce complexity functions counting the number of configurations of a rectangle , or, more generally, given , we can define as the number of configurations obtained after translating around .
The next proposition says that the characterization of full periodicity is very similar to the case of :
Proposition 3 is fully periodic if and only if the complexity function is bounded.
Proof: It is clear that if is fully periodic then is bounded.
Conversely, if is bounded, the idea is that we can reduce our task to the Morse-Hedlund theorem: indeed, if , then, it is not hard to convince oneself that is a period for .
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 :
Nivat’s conjecture (1997). Let . If there are such that , then is periodic.
Note that Nivat’s conjecture is “optimal” in the following sense: by taking and by letting be the aperiodic word given by and elsewhere, then .
Also, Nivat’s conjecture is a “two-dimensional conjecture”: Tijdeman observed that, for and , the aperiodic word given by , and otherwise (where is fixed) satisfies ; furthemore, given and , Sander and Tijdeman constructed aperiodic words in such that .
Currently, we dispose of some results towards Nivat’s conjecture:
- Sander and Tijdeman (2002) showed that if or for some , then is periodic.
- Epifanio, Koskas and Mignosi (2003) proved that if for some , then is periodic.
- Quas and Zamboni (2004) improved the result of the previous item by showing that if for some , then is periodic.
The main result of Bryna’s talk was the following theorem joint with V. Cyr:
Theorem 4 (Cyr-Kra) If for some , then 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.
for each . Note that, for our choice of topology, is continuous.
Given , let us denote by the closure of the orbit of , i.e.,
As it is well-known, the orbit closure is intimately related to the combinatorial properties of . For example, the reader is invited to check that is periodic if and only if doesn’t act faithfully on , and, for , is fully (i.e., doubly) periodic if and only if is finite.
Besides the shift dynamics, we will also need the notion of (non-)expansive subspaces for a action. In order to motivate this definition, let us firstly recall the notion of expansiveness in the sense of R. Bowen:
Definition 5 Let be a compact metric space and a homeomorphism of . We say that is expansive if there exists such that if for all then . In other words, is expansive if we can “reasonably separate” (from a fixed amount ) any pair of distinct points by iterating them.
In 1997, Boyle and Lind generalized this notion for -actions:
Definition 6 (Boyle and Lind) Let be a compact metric space and a continuous -action on . We say that is expansive if there are a expansiveness radius and a expansiveness constant such that if
for all with , then . (Here, is the Euclidean distance.) In other words, is expansive if we can reasonaly separate any pair of distinct point by iterating them using elements of approximatively pointing in the direction of .
For our preferred example , we have that is expansive if there exists such that if for all , then .
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 and consider the subset of consisting of all such that
In the literature, the shift dynamics on 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:
After this example, it is time to state some abstract results:
Theorem 7 (Boyle and Lind) If is an infinite compact metric space with a continuous action, then, for each , there exists a non-expansive subspace of of dimension .
By taking and , one has the following corollary:
Corollary 8 For , is doubly (i.e., fully) periodic is finite every -dimensional subspace of is expansive.
In this context, V. Cyr and B. Kra actually show the following result:
Theorem 9 (Cyr and Kra) Let be a word such that . Assume that there exists an unique non-expansive subspace of dimension for the shift dynamics on . Then, is periodic (but not doubly periodic).
The basic idea behind this theorem is that all periods of 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 :
Theorem 10 (Cyr and Kra) Let be a word such that for some . Then, there is at most one non-expansive direction.
In summary, for :
- is doubly periodic if and only if there is no non-expansive -dimensional subspaces.
- if there is an unique non-expansive -dimensional subspace, then is periodic but not doubly periodic.
- in order to rule out the possible existence of at least two non-expansive -dimensional subspaces, one needs the assumption .
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 , then , and one looks for so that this inequality “stabilizes”.
Secondly, she made the previous paragraph a little more precise by introducing the notion of discrepancy
and by recalling the following lemma (cf. the proof of Lemma 2.1 in Cyr-Kra paper):
Lemma 11 If and , then either
or every -coloring of uniquely extends to a -coloring of .
Also, she noticed that the hypothesis of Nivat’s conjecture gives a rectangle such that , and, by definition, .
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 such that, for all , every -coloring of extends uniquely to a -coloring of .
Finally, Bryna mentioned that this set plays the role of the interval in the proof of Morse-Hedlund theorem, but, in order to be able to use in the same that we used , Bryna told us that one needs to control the geometry of . In particular, she told that Cyr and her shows that is convex and, from the assumption , it is possible to prove that occupies more than half of the rectangle , and she concluded the talk by saying that essentially the convexity and the largeness of (inside ) are sufficient to conclude the their results.