# Minimal Complexities for Infinite Words Written with d Letters

Mélodie Andrieu, Léo Vivion

► To cite this version:

Mélodie Andrieu, Léo Vivion. Minimal Complexities for Infinite Words Written with d Letters. Combinatorics on Words - 14th International Conference, WORDS, Jun 2023, Umeå, Sweden. pp.3–13, 10.1007/978-3-031-33180-0_1 . hal-04291983

HAL Id: hal-04291983

https://hal.science/hal-04291983v1

Submitted on 21 Nov 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Minimal Complexities for Infinite Words
Written with $d$ Letters

Mélodie Andrieu¹ and Léo Vivion²

¹Université du Littoral Côte d'Opale, France

²Aix-Marseille Université, France

Abstract

In this extended abstract, we discuss the minimal subword complexity and the minimal abelian complexity functions for infinite $d$-ary words. This leads us to answer a question of Rauzy from 1983: cubic billiard words are a good generalization of Sturmian words for the abelian complexity.

# 1 General motivation

Sturmian words (1940) form a class of infinite words over the binary alphabet, which sheds light on the remarkable interactions between combinatorics, dynamical systems, and number theory. These interactions are reflected in the various ways to define them (see the historic paper [MH40], or refer to the book [Lot97] for a modern introduction). For instance, Sturmian words are equivalently

* words with subword complexity $n+1$, i.e., admitting exactly $n+1$ factors of length $n$ for all $n$ (a factor of $w$ of length $n$ is a subword of $w$ consisting of $n$ consecutive letters);

* binary aperiodic words with imbalance equal to 1: all factors of a given length contain, up to one, the same number of occurrences of 1s (and thus, up to one as well, the same number of 2s);

* the symbolic trajectories of a ball in a square billiard, launched with a momentum with rationally independent components.

They give rise to several generalizations over the $d$-letter alphabet for $d \ge 3$, depending on the considered definition: Arnoux-Rauzy ([AR91]) and episturmian words ([JP02], [GJ09]), other words associated with $d$-dimensional continued fraction algorithms (see [Sch00], [Ber11], [BD14]), interval exchange transformations ([Via06], [Yoc07]), polygonal ([Tab05], [CHT02] and references therein) or cubic billiard words ([AMST94a]). A large program, initiated by Rauzy in the 80s ([Rau83, Rau84, Rau85]), is to determine which properties are still equivalent in higher dimensions, and which are not.

The present manuscript is part of this program. It mostly focuses on one of the dynamical representations of Sturmian words: as words generated by a billiard on a square table, which generalizes itself to a billiard in the cube, and in the cube of dimension $d$;
and on two combinatorial quantities which characterize Sturmian words: the subword complexity and the abelian complexity. The manuscript is directed by the question: are the subword and abelian complexities of cubic billiard words in dimension $d$ minimal among the complexities of $d$-ary words, as is the case when $d = 2$?

The manuscript is organized as follows. Hypercubic billiard words are defined in Section 2. Section 3 is devoted to the subword complexity. Section 4 is devoted to the abelian complexity.

## 2 Hypercubic billiard words

We start by defining cubic billiard words in dimension $d$, which we generically call hypercubic billiard words.

Let $d \ge 1$. The set $\mathbb{R}^d$ is equipped with the usual inner product and canonical basis $(e_1, ..., e_d)$. We are interested in the sequence of the faces successively hit by a billiard ball, initially located in $x \in [0, 1]^d$, which is given an initial momentum $\theta = (\theta_1, ..., \theta_d) \in (\mathbb{R}\setminus\{0\})^d$. We will use the letter $k$ to code a hit against one of the two faces orthogonal to the vector $e_k$. The sequence that we thus obtain, denoted by $w(x, \theta)$, is an infinite word over the alphabet $\{1, ..., d\}$, that we call a *cubic billiard word in dimension d*.

<figure><img src="image_2.png" /><figcaption>Figure 1: The billiard word $w(x, \theta)$ starts with 11211121...</figcaption></figure>

*Remark.* This definition omits to specify what happens when the trajectory of the ball intersects several faces *simultaneously* (for instance, for $d = 2$, when the ball hits a corner of the square). It has no importance: first, once the momentum $\theta$ is set up, the set of all starting positions $x \in [0, 1]^d$ for which such an event occurs has Lebesgue measure 0; secondly, for these rare "bad" starting positions, there still exists a reasonable coding strategy (not detailed here) that endows the words obtained with the same properties as regular hypercubic billiard words. In particular, all the results stated in this manuscript (noticeably Theorems 2, 3, 8, 9, and Corollary 1) *are true for all hypercubic billiard words*, including those generated by "bad" starting positions.

In the sequel, we focus on the billiard words generated by momenta $\theta$ with **rationally independent components**. The reason for this choice is that square billiard words generated by momenta with rationally independent components *are exactly* Sturmian words. Note that the rational independence of the momentum's components is equivalent to the *minimality* of one/all trajectories: balls launched with such momenta pass arbitrarily close to every point in the hypercube.
## 3 Subword complexity of hypercubic billiard words

Most of the literature defines *Sturmian words* as right-infinite words with subword complexity $p: n \mapsto n + 1$. We recall that the *subword complexity* of $w$ (often simply called *complexity*) is the function that counts the number of factors of length $n$ in $w$. This function is intricately linked with the notion of **entropy in dynamics**, which measures how well a trajectory can be predicted from the knowledge of a small portion of it. A fundamental fact is that $n \mapsto n + 1$ is the **smallest complexity** function for a "non-trivial" word.

**Theorem 1** (Morse and Hedlund, 1938 [MH38]). Let $w$ be an infinite word. If there exists an integer $m$ such that $p(m) \le m$, then the word $w$ is ultimately periodic, and its subword complexity $p$ is ultimately constant.

The particular equality $p(1) = 2$ tells us that Sturmian words are written with exactly 2 letters. A natural question, when it comes to generalizing Sturmian words, is the following one.

**Question 1.** Let $d \ge 3$. What is the subword complexity of cubic billiard words in dimension $d$? Is this function the smallest subword complexity for non-ultimately periodic words written with exactly $d$ letters?

### 3.1 Subword complexity of hypercubic billiard words

The first part of the question has been fully answered by Arnoux, Mauduit, Shiokawa, Tamura, Baryshnikov, and Bédaride between 1994 and 2009. First, when $d = 3$, we have the following expression, which was originally conjectured by Rauzy in 1983 ([Rau83]).

**Theorem 2** (Arnoux, Mauduit, Shiokawa, and Tamura, 1994 [AMST94a] [AMST94b]; corrected by Bédaride [Béd03]). Let $x \in [0, 1]^3$, and $\theta \in \mathbb{R}^3$ with rationally independent components. If the inverses $\theta_1^{-1}, \theta_2^{-1}$ and $\theta_3^{-1}$ are also rationally independent, then the number of distinct factors of length $n$ in the cubic billiard word $w(x, \theta)$ is

$$n^2 + n + 1.$$

This formula extends itself to arbitrary dimensions in the following way.

**Theorem 3** (Bédaride [Béd09]). Let $d \ge 1$, $x \in [0, 1]^d$, and $\theta \in \mathbb{R}^d$ with rationally independent components. If $d \ge 3$, assume, moreover, that for any three indices $i, j, k$, the numbers $\theta_i^{-1}, \theta_j^{-1}$ and $\theta_k^{-1}$ are rationally independent (♣). Then the number of distinct factors of length $n$ in the billiard word $w(x, \theta)$ is

$$\sum_{k=0}^{\min(n,d-1)} k! \binom{n}{k} \binom{d-1}{k}.$$

Borel [Bor06] and Bédaride [Béd07] showed that the condition (♣) is necessary.

This general formula was first conjectured by Arnoux, Mauduit, Shiokawa, and Tamura in [AMST94a], and proved one year later, in 1995, under a strictly stronger – and thereby non optimal – condition by Baryshnikov [Bar95].
## 3.2 Minimal subword complexity for d-ary words

Regarding the second part of Question 1 ("is this function the minimal subword complexity for non-ultimately periodic words written with exactly *d* letters?"), one quickly convinces oneself that the question is poorly stated. Indeed, the *uninteresting ternary* word $w = 3 \cdot w'$, where $w'$ is any Sturmian word on the alphabet $\{1, 2\}$, is non-ultimately periodic, and has subword complexity $n \mapsto n + 2$. It is not difficult to prove that this complexity is the lowest for a non-ultimately periodic ternary word. Note that there exist other families of words with subword complexity $n \mapsto n + 2$. They are classified in [Ale95] (see also the reference [KT07], which is easier to find.)

In our opinion, an essential property of Sturmian words is that their letter frequencies are **rationally independent** (this is a manifestation of the action of the continued fraction). We recall that the *frequency* of a letter *a* in a right-infinite word *w* is the limit, if it exists, of the proportion of *as* in growing prefixes of *w*. By contrast to Sturmian words, the frequencies of letters of ultimately periodic words are rational, and thereby, as soon as there are at least two letters, rationally dependent. Thus, Sturmian words are exactly words with minimal complexity function among binary words whose letter frequencies – which exist by a classical argument of [Bos84] – are rationally independent. From this perspective, our question can be better formulated.

**Question 2.** Let $d \ge 3$. What is the smallest subword complexity for a $d$-ary word with rationally independent frequencies of letters?

This question was answered by Tijdeman in a mostly forgotten article from 1999.

**Theorem 4** (Tijdeman, 1999, [Tij99]). Let $d \ge 1$.

(1) Let $w$ be a $d$-ary word that admits frequencies of letters. If there exists an integer $m$ such that $p(m) \le (d-1)m$, where $p$ denotes the subword complexity of $w$, then the frequencies of letters in $w$ are rationally dependent.

(2) There exist $d$-ary words, with rationally independent letter frequencies, whose subword complexity is $p: n \mapsto (d-1)n + 1$.

In other words, the smallest subword complexity of $d$-ary words, with rationally independent letter frequencies, is $p: n \mapsto (d-1)n + 1$.

To our knowledge, there is no classification of the words, with rationally independent letter frequencies, which realize this minimal complexity. However, some families of such words are known, as illustrated below.

On the first hand, one finds the words associated with the interval exchange transformations defined by a partition of $[0,1)$ into $d$ sub-intervals, with rationally independent lengths, and by the cyclic permutation $(2, 3, ..., d, 1)$ (this is the example exhibited in [Tij99]). To learn more about interval exchange transformations, we refer to the lectures [Via06], [Yoc07].

On the other hand, there are the words associated with certain multidimensional continued fraction algorithms. Noticeably, for $d=3$, one finds the primitive C-adic words ([CLL17]), and the Arnoux-Rauzy words, for which the rational independence of the letter frequencies was only proven two years ago (see [And21b] or [DHS22]). More generally, for $d \ge 2$, one finds the strict episturmian words over the $d$-letter alphabet.

**Theorem 5** (Andrieu, in preparation, but a proof can be found in [And21a]). Let $d \ge 2$. The frequencies of letters of any strict episturmian word over the $d$-letter alphabet are rationally independent.
Note that the fact that strict episturmian words have subword complexity $n \mapsto (d-1)n+1$ stems from their definition. To learn more about episturmian words (starting with their definition), we refer to the survey [GJ09].

Coming back to billiard words and to Question 1, one observes that:
- the frequencies of letters of a hypercubic billiard word are rationally independent if, and only if, the components of its momentum $\theta$ are rationally independent. Indeed, these two vectors are equal up to a dilatation, and a change in the signs of some components.
- BUT its subword complexity function is far from being minimal when $d \ge 3$. Indeed, one checks that the complexity of a cubic billiard word in dimension $d$, under the assumption (♣), is polynomial with degree $d-1$.

### 3.3 A long-standing conjecture

We conclude this section with a long-standing conjecture, which aims at generalizing Theorem 1 to bi-dimensional words (instead of $d$-ary words, as we did).

<figure><img src="image_3.png" /><figcaption>Figure 2: Example of a bi-dimensional word over the alphabet $\{\square, \blacksquare\}$.</figcaption></figure>

**Conjecture 1** (Nivat, 1997, [Niv97]). Let $\mathcal{A}$ be an alphabet, and $w$ an infinite bi-dimensional word over $\mathcal{A}$, i.e., an element of $\mathcal{A}^{\mathbb{Z}^2}$. If there exist $n, m \in \mathbb{N}$ such that the number of distinct $n \times m$ patterns is at most nm, then the word $w$ is periodic in some direction.

Here, "periodic in some direction" means that there exists $t \in \mathbb{Z}^2$ such that for every $z \in \mathbb{Z}^2$, the letters at positions $z$ and $z+t$ coincide. A lot of efforts have been, and continue to be, given towards Conjecture 1, which remains *unsolved* at the time of writing ([ST02], [EKM03], [QZ04], [CK15], [CK16], [KS20], [KM19]).

## 4 Abelian complexity of hypercubic billiard words

In this section, we consider a variation in the definition of complexity.

Two finite words $u$ and $v$ are *abelian equivalent* if $u$ is the anagram of $v$ (e.g., *twelveplusone* and *elevenplustwo*). The *abelian complexity* of an infinite word $w$ is the function that counts the number of non-abelian equivalent factors of length $n$, for all $n$. For instance, for $n \ge 1$, the ultimately constant word $w = 2122222...$ admits exactly two non abelian-equivalent factors of length $n$: the one which contains 1, and the one written with the letter 2 only. For an introduction to abelian complexity, or, more generally, to abelian combinatorics on words, we refer to the recent survey [FP23].

It turns out that Sturmian words are also characterized by a remarkable abelian complexity.
**Theorem 6** (derived from Coven and Hedlund, 1973, [CH73]). A word is Sturmian if and only if its abelian complexity is constant, equal to 2, for all lengths $n \ge 1$, and if its frequencies of letters (which exist) are rationally independent.

Interestingly, this is the smallest abelian complexity for non-periodic words. Indeed, it is not difficult to see that if, in an infinite word $w$, all factors of length $n$ are abelian equivalent, then $w$ is periodic with period $n$.

Thus, a natural question, first asked by Rauzy in 1983, is the following: does there exist a generalization of Sturmian words (among which are Arnoux-Rauzy and episturmian words, words associated with other multidimensional continued fractions, hypercubic billiard words, etc.), which somewhat preserves such a nice abelian complexity.

**Question 3** (Rauzy, 1983, [Rau83] (Section 6), free translation from French). Does there exist a class of infinite words over the alphabet $\{1, 2, 3\}$ whose abelian complexity is constant, equal to 3? It seems that no, except perhaps for very particular frequencies of letters. What is, then, the "good" generalization of the Coven and Hedlund's theorem?

## 4.1 Proving the conjecture of Rauzy

Question 3 splits into a conjecture, and a question. We start by examining the conjecture.

**Conjecture 2.** Under a condition $\mathfrak{A}$ (to be determined), there exists no ternary word $w$ with abelian complexity equal to 3 for all $n \ge 1$.

With no condition $\mathfrak{A}$, Conjecture 2 is false. Indeed, one readily checks that the ternary words:

$$w_1 = 1233333333... \quad \text{and} \quad w_2 = 1 \cdot w'_2,$$

where $w'_2$ is any Sturmian word over the alphabet $\{2, 3\}$, admit exactly 3 non-abelian equivalent factors of length $n$, for all $n \ge 1$. One may ask the word $w$ to be uniformly recurrent (a word $w$ is uniformly recurrent if each factor appears infinitely often, with bounded gaps). The motivation for choosing this condition is that Sturmian words are uniformly recurrent. Furthermore, with this additional condition, the trivial counterexamples $w_1$ and $w_2$ are eliminated.

However, even with the condition $\mathfrak{A}$: "$w$ must be uniformly recurrent", Conjecture 2 remains false [RSZ11], and the counterexamples exhibited by Richomme, Saari, and Zamboni are no good generalizations of Sturmian words.

For the reason stated in Section 3, on the strength of Tijdeman's theorem (Theorem 4), and following our reformulation of Coven and Hedlund's theorem (Theorem 6), we think that the condition $\mathfrak{A}$ should be: "the frequencies of letters are rationally independent". Under this condition $\mathfrak{A}$, Conjecture 2 turns out to be true.

**Theorem 7** (Andrieu, Vivion, in preparation). Let $w \in \{1, 2, 3\}^N$ be a word with rationally independent letter frequencies. Then there exists an integer $n \ge 1$ such that $w$ admits at least 4 non-abelian equivalent factors of length $n$.

It remains to answer the second part of Question 3: what is, then, the good generalization of the Morse and Hedlund's theorem? We could, for instance, look for a class of ternary words with rationally independent letter frequencies and abelian complexity constant, equal to 4. Of course, this would only be possible for $n \ge 2$.
## 4.2 Abelian complexity of hypercubic billiard words

Abelian complexity has been extensively studied since 2007 ([KT07]), in particular after the progress of Richomme, Saari, and Zamboni towards Question 3 ([RSZ11]), see for instance [Saa09], [RSZ10], [CR11], [BBT11], [MR13], [Tur13], [BSFR14], [BSCRF14], [Tur15], [BSSW16], [LCWW17], [CW19], [KR19], [Whi19], [Sha21], etc. Experience showed that, even for friendly words (for instance, the Tribonacci word), the abelian complexity can be a surprisingly tricky function, and one generally obtains bounds instead of exact values.

**Question 4.** What can be said of the abelian complexity of hypercubic billiard words? Can we explicitly compute this function for some easy instances?

The answer is positive, beyond hope: not only is it possible to compute the abelian complexity of all hypercubic billiard words generated by momenta with rationally independent components, but this function, remarkably simple, turns out to be the same for all of them (which is, remember the condition (♣), noticeably not the case for the subword complexity, whenever $d \ge 3$).

**Theorem 8** (Andrieu, Vivion, in preparation). Let $d \ge 1$, $x \in [0, 1]^d$, and $\theta \in \mathbb{R}^d$ with rationally independent components. Let $n \in \mathbb{N}$. The number of non-abelian equivalent factors of length $n$ in the billiard word $w(x, \theta)$ is

$$ \sum_{k=0}^{\min(n,d-1)} \binom{d-1}{k} $$

**Corollary 1.** Let $d \ge 1$, $x \in [0, 1]^d$, and $\theta \in \mathbb{R}^d$ with rationally independent components. Let $n \ge d-1$. There are exactly $2^{d-1}$ non-abelian equivalent factors of length $n$ in $w(x, \theta)$.

In other words, the abelian complexity of cubic billiard words in dimension $d$ is ultimately constant, equal to $2^{d-1}$. For $d=3$, cubic billiard words have an abelian complexity constant, equal to 4, for all $n \ge 2$. This result answers Question 3: cubic billiard words generated by momenta with rationally independent components (or, equivalently, and very interestingly, those with rationally independent letter frequencies) are a “good” generalization of Sturmian words, from the point of view of abelian complexity.

We conclude this subsection with a stronger result: not only do we know the number of non-abelian equivalent factors of length $n$ of a hypercubic billiard word, but we are in fact able to compute them easily.

**Theorem 9** (Andrieu, Vivion, in preparation). Let $d \ge 1$, $x \in [0, 1]^d$, and $\theta \in \mathbb{R}^d$ with rationally independent components. Let $n \in \mathbb{N}$. The set of equivalence classes of length $n$ factors of $w(x, \theta)$, for the relation “being abelian equivalent”, can be computed from the sole knowledge of the first $n-1$ letters of the billiard word $w(0, \theta)$.

This contrasts sharply with the difficulty of listing the factors of a given length in a hypercubic billiard word. For instance, in dimension 3, and for the parameters $x = (0, 0, 0)$ and $\theta = (\sqrt{2}, \sqrt{3}, \sqrt{5})$, we know that the billiard word $w(x, \theta)$ admits 43 factors of length 6 (it is a quick computation from Theorem 3); nonetheless, they do not all appear in the prefix of length 10000000 of $w(x, \theta)$ ([AL22]).
## 4.3 Another old question

We conclude this extended abstract with a long-standing question, first asked by Arnoux, Mauduit, Shiokawa, and Tamura in 1994: *why* is the formula of the subword complexity (given in Theorem 3) symmetric in *n* (length of factors) and *d*−1 (cardinal of the alphabet minus one)?

**Question 5** (Arnoux, Mauduit, Shiokawa, Tamura, 1994, [AMST94a]). *Can we give a meaningful bijective map between the factors of length *n* of a hypercubic billiard word over the alphabet {1, ..., *d*}, and the factors of length *d* − 1 of a particular/any hypercubic billiard word over the alphabet {1, ..., *n* + 1}?*

To our knowledge, this question is still open at the time of writing.

**Acknowledgements** We would like to express our gratitude to Boris Solomyak and to Julien Cassaigne for numerous exciting discussions on this topic; and to Shalom Eliahou for his kind help in improving the quality of the manuscript.

## References

[AL22] Mélodie Andrieu and Sébastien Labbé. Sagemath function "billiard_nd". https://gitlab.com/seblabbe/slabbe/-/blob/develop/slabbe/billiard_nd.py, 2022. Accessed: 2022-12-01.

[Ale95] Pascal Alessandri. Classification et représentation des mots de complexité n + 2. *Rapport technique, Université Aix-Marseille II*, 1995.

[AMST94a] Pierre Arnoux, Christian Mauduit, Iekata Shiokawa, and Jun-Ichi Tamura. Complexity of sequences defined by billiard in the cube. *Bulletin de la Société Mathématique de France*, 122(1):1–12, 1994.

[AMST94b] Pierre Arnoux, Christian Mauduit, Iekata Shiokawa, and Jun-Ichi Tamura. Rauzy's conjecture on billiards in the cube. *Tokyo Journal of Mathematics*, 17(1):211–218, 1994.

[And21a] Mélodie Andrieu. Exceptional trajectories in the symbolic dynamics of multidimensional continued fraction algorithms (chapter 4). *PhD dissertation, Aix-Marseille Université*, 2021.

[And21b] Mélodie Andrieu. A Rauzy fractal unbounded in all directions of the plane. *Comptes Rendus. Mathématique*, 359:399–407, 2021.

[AR91] Pierre Arnoux and Gérard Rauzy. Représentation géométrique de suites de complexité 2n+1. *Bulletin de la Société Mathématique de France*, 119:199–215, 1991.

[Bar95] Yuliv Baryshnikov. Complexity of trajectories in rectangular billiards. *Communications in Mathematical Physics*, 174(1):43–56, 1995.

[BBT11] L'ubomíra Balkovà, Karel Břinda, and Ondřej Turek. Abelian complexity of infinite words associated with quadratic Parry numbers. *Theoretical Computer Science*, 412(45):6252–6260, 2011.

[BD14] Valérie Berthé and Vincent Delecroix. Beyond substitutive dynamical systems: S-adic expansions. In *Lecture note 'Kokyuroku Bessatu', pages 81–123, 2014*.

[Béd03] Nicolas Bédaride. Billiard complexity in rational polyhedra. *Regular and Chaotic Dynamics*, 8(1):97–104, 2003.

[Béd07] Nicolas Bédaride. Classification of rotations on the torus $T^2$. *Theoretical Computer Science*, 385(1):214–225, 2007.
[Béd09] Nicolas Bédaride. Directional complexity of the hypercubic billiard. *Discrete Mathematics*, 309(8):2053-2066, 2009.

[Ber11] Valérie Berthé. Multidimensional Euclidean algorithms, numeration and substitutions. *Integers* [electronic only], 2011.

[Bor06] Jean-Pierre Borel. Complexity of degenerated three dimensional billiard words. *Developments in Language Theory*, pages 386-396, 2006.

[Bos84] Michael Boshernitzan. A unique ergodicity of minimal symbolic flows with linear block growth. *Journal d'Analyse Mathématique*, 44:77-96, 1984.

[BSCRF14] Francine Blanchet-Sadri, James Currie, Narad Rampersad, and Nathan Fox. Abelian complexity of fixed point of morphism $0 \mapsto 012, 1 \mapsto 02, 2 \mapsto 1$. *Integers*, 14, 2014.

[BSFR14] Francine Blanchet-Sadri, Nathan Fox, and Narad Rampersad. On the asymptotic abelian complexity of morphic words. *Advances in Applied Mathematics*, 61:46-84, 2014.

[BSSW16] Francine Blanchet-Sadri, Daniel Seita, and David Wise. Computing abelian complexity of binary uniform morphic words. *Theoretical Computer Science*, 640:41-51, 2016.

[CH73] Ethan M. Coven and Gustav A. Hedlund. Sequences with minimal block growth. *Mathematical systems theory*, 7:138-153, 1973.

[CHT02] Julien Cassaigne, Pascal Hubert, and Serge Troubetzkoy. Complexity and growth for polygonal billiards. *Annales de l'Institut Fourier*, 52(3):835-847, 2002.

[CK15] Van Cyr and Bryna Kra. Nonexpansive $\mathbb{Z}^2$-subdynamics and Nivat's conjecture. *Transactions of the American Mathematical Society*, 367(9):6487-6537, 2015.

[CK16] Julien Cassaigne and Idrissa Kaboré. Abelian complexity and frequencies of letters in infinite words. *International Journal of Foundations of Computer Science*, 27(05):631-649, 2016.

[CLL17] Julien Cassaigne, Sébastien Labbé, and Julien Leroy. A set of sequences of complexity $2n+1$. In *WORDS 2017 Proceedings*, pages 144-156. Springer, 2017.

[CR11] James Currie and Narad Rampersad. Recurrent words with constant abelian complexity. *Advances in Applied Mathematics*, 47(1):116-124, 2011.

[CW19] Jin Chen and Zhi-Xiong Wen. On the abelian complexity of generalized Thue-Morse sequences. *Theoretical Computer Science*, 780:66-73, 2019.

[DHS22] Ivan Dynnikov, Pascal Hubert, and Alexandra Skripchenko. Dynamical systems around the Rauzy gasket and their ergodic properties. *International Mathematics Research Notices*, 2022.

[EKM03] Chiara Epifanio, Michel Koskas, and Filippo Mignosi. On a conjecture on bidimensional words. *Theoretical Computer Science*, 299:123-150, 2003.

[FP23] Gabriele Fici and Svetlana Puzynina. Abelian combinatorics on words: a survey. *Computer Science Review*, 47:100532, 2023.

[GJ09] Amy Glen and Jacques Justin. Episturmian words: a survey. *RAIRO - Theoretical Informatics and Applications*, 43(3):403-442, 2009.

[JP02] Jacques Justin and Giuseppe Pirillo. Episturmian words and episturmian morphisms. *Theoretical Computer Science*, 276(1):281-313, 2002.

[KM19] Jarkko Kari and Etienne Moutot. Nivat's conjecture and pattern complexity in algebraic subshifts. *Theoretical Computer Science*, 777:379-386, 2019.

[KR19] Ian Kaye and Narad Rampersad. The abelian complexity of infinite words and the Frobenius problem. *arxiv.1907.08247*, 2019.
[KS20] Jarkko Kari and Michal Szabados. An algebraic geometric approach to Nivat's conjecture. *Information and Computation*, 271:104481, 2020.

[KT07] Idrissa Kaboré and Théodore Tapsoba. Combinatoire de mots récurrents de complexité $n + 2$. *RAIRO - Theoretical Informatics and Applications*, 41(4):425-446, 2007.

[LCWW17] Xiaotao Lü, Jin Chen, Zhi-Xiong Wen, and Wen Wu. On the abelian complexity of the Rudin-Shapiro sequence. *Journal of Mathematical Analysis and Applications*, 451(2):822-838, 2017.

[Lot97] Lothaire. *Combinatorics on Words*. Cambridge Mathematical Library. 2nd edition, 1997.

[MH38] Marston Morse and Gustav A. Hedlund. Symbolic dynamics. *American Journal of Mathematics*, 60(4):815-866, 1938.

[MH40] Marston Morse and Gustav A. Hedlund. Symbolic dynamics II. Sturmian trajectories. *American Journal of Mathematics*, 62(1):1-42, 1940.

[MR13] Blake Madill and Narad Rampersad. The abelian complexity of the paperfolding word. *Discrete Mathematics*, 313(7):831-838, 2013.

[Niv97] Maurice Nivat. *Invited talk at ICALP, Bologna*, 1997.

[QZ04] Anthony Quas and Luca Zamboni. Periodicity and local complexity. *Theoretical Computer Science*, 319:229-240, 2004.

[Rau84] Gérard Rauzy. Des mots en arithmétique. *Publications du Département de mathématiques (Lyon)*, 6B:103-113, 1984.

[Rau85] Gérard Rauzy. Mots infinis en arithmétique. In M. Nivat and D. Perrin, editors, *Automata on Infinite Words*, pages 164-171. Springer Berlin Heidelberg, 1985.

[Rau83] Gérard Rauzy. Suites à termes dans un alphabet fini. *Séminaire de Théorie des Nombres de Bordeaux*, pages 1-16, 1982-83.

[RSZ10] Gwénaël Richomme, Kalle Saari, and Luca Q. Zamboni. Balance and abelian complexity of the Tribonacci word. *Advances in Applied Mathematics*, 45(2):212-231, 2010.

[RSZ11] Gwénaël Richomme, Kalle Saari, and Luca Q. Zamboni. Abelian complexity of minimal subshifts. *Journal of the London Mathematical Society*, 83(1):79-95, 2011.

[Saa09] Aleksi Saarela. Ultimately constant abelian complexity of infinite words. *Journal of Automata, Languages and Combinatorics*, 14(3):255-258, 2009.

[Sch00] Fritz Schweiger. *Multidimensional Continued Fractions*. Oxford University Press, 2000.

[Sha21] Jeffrey Shallit. Abelian complexity and synchronization. *Integers*, 21, 2021.

[ST02] J. W. Sander and R. Tijdeman. The rectangle complexity of functions on two-dimensional lattices. *Theoretical Computer Science*, 270:857-863, 2002.

[Tab05] Sergei Tabachnikov. *Geometry and Billiards*. Mathematics Advanced Study Semesters. Providence, R.I.: American Mathematical Society, 2005.

[Tij99] Robert Tijdeman. On the minimal complexity of infinite words. *Indagationes Mathematicae*, 10:123-129, 1999.

[Tur13] Ondřej Turek. Abelian complexity and abelian co-decomposition. *Theoretical Computer Science*, 469:77-91, 2013.

[Tur15] Ondřej Turek. Abelian complexity function of the Tribonacci word. *Journal of Integer Sequences*, 18:15.3.4, 2015.
[Via06] Marcelo Viana. Ergodic theory of interval exchange maps. *Revista Matemática Complutense*, 19, 2006.

[Whi19] Markus A. Whiteland. Asymptotic abelian complexities of certain morphic binary words. *Journal of Automata, Languages and Combinatorics*, 24(1):89–114, 2019.

[Yoc07] Jean-Christophe Yoccoz. Interval exchange maps and translation surfaces. *Lecture (Pisa)*, 2007.