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

HAL
open science

# New examples of words for which the binomial complexities and the subword complexity coincide

Léo Vivion

► To cite this version:

Léo Vivion. New examples of words for which the binomial complexities and the subword complexity coincide. 2025. hal-05251499

HAL Id: hal-05251499

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

Preprint submitted on 12 Sep 2025

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
New examples of words for which the binomial complexities
and the subword complexity coincide

Léo Vivion*¹

¹Laboratoire de Mathématiques Pures et Appliquées Joseph Liouville, Université du Littoral Côte d'Opale, UR 2597, F-62100 Calais, France.

**Abstract**

The complexity of an infinite word can be measured in several ways, the two most common measures being the subword complexity and the abelian complexity. In 2015, Rigo and Salimov introduced a family of intermediate complexities indexed by $k \in \mathbb{N}_{>0}$: the *k*-binomial complexities. These complexities scale up from the abelian complexity, with which the 1-binomial complexity coincides, to the subword complexity, to which they converge pointwise as $k$ tends to $\infty$. In this article, we provide four classes of *d*-ary infinite words – namely, *d*-ary 1-balanced words, words with subword complexity $n \in \mathbb{N}_{>0} \mapsto n + (d-1)$ (which form a subclass of quasi-Sturmian words), hypercubic billiard words, and words obtained by coloring a Sturmian word with another Sturmian word – for which this scale “collapses”, that is, for which all *k*-binomial complexities, for $k \ge 2$, coincide with the subword complexity. This work generalizes a result of Rigo and Salimov, established in their seminal 2015 paper, which asserts that the *k*-binomial complexity of any Sturmian word coincides with its subword complexity whenever $k \ge 2$.

**Keywords:** Binomial complexities · Hypercubic billiard words · *d*-ary balanced words · Sturmian colored sequences · Quasi-Sturmian words

# 1 Introduction

The subword complexity and the abelian complexity are two very classical ways to measure
how “complicated” an infinite word is. In 2015, Rigo and Salimov introduced a family of
complexities forming a scale between the abelian complexity and the subword complexity:
the *k*-binomial complexities [RS15]. These complexities are parameterized by the integer
$k \in \mathbb{N}_{>0}$ and are defined via a family of equivalence relations called *k*-binomial equiva-
lences. For $k = 1$, this relation corresponds to the *abelian equivalence*, and the 1-binomial
complexity is the same as the *abelian complexity*. The ($k+1$)-binomial equivalence is
a refinement of the *k*-binomial one, and as $k$ increases, the *k*-binomial equivalence gets
progressively closer to equality between finite words. Consequently, the *k*-binomial com-
plexities form a scale from the abelian complexity to the subword complexity, and the
*k*-binomial complexity of a given word converges pointwise to its subword complexity as
$k \to \infty$.

<footnote>*lvivion.math@gmail.com</footnote>
Since 2015, k-binomial complexities have been the subject of several papers [LLR20, LRR20b, LCWW24, RSW24, GRW24]. Interested readers may also consult [RSW23, RRW25] for variations on k-binomial complexities and [LRR20a, Whi21] for recent articles on k-binomial equivalence relations.

Sturmian words constitute a central class in Combinatorics on Words. Their subword complexity is given by the function $n \in \mathbb{N} \mapsto n+1$ [MH40], while their abelian complexity is the constant function $n \in \mathbb{N}_{>0} \mapsto 2$ [CH73]. In their seminal paper, Rigo and Salimov proved that Sturmian words satisfy the following remarkable combinatorial property: the 2-binomial complexity of any Sturmian word is $n \in \mathbb{N} \mapsto n+1$, i.e., it coincides with their subword complexity. Note that, since the k-binomial complexities form a scale between the abelian complexity and the subword complexity, if the k-binomial complexity of a word coincides with its subword complexity, then this property also holds for all its l-binomial complexities with $l \ge k$.

This article contributes to the study of words for which, similarly to Sturmian words, their k-binomial complexity coincides with their subword complexity for some small integer $k$. Although we focus mainly on the case $k=2$, several of our results also hold for arbitrary integer $k$ (see Lemmas 8 and 9 below).

Words whose 1-binomial complexity (i.e., abelian complexity) coincides with their subword complexity can be easily characterized. Indeed, this condition is so restrictive that very few words satisfy it.

**Proposition 1** ([RSW24] Remark 7.1). The 1-binomial complexity of an infinite word $w$ coincides with its subword complexity if and only if there exist $d$ distinct letters $a_1, \dots, a_d$ and $(d-1)$ positive integers $k_1, \dots, k_{d-1}$ such that

$$w = a_1^{k_1} a_2^{k_2} \dots a_{d-1}^{k_{d-1}} a_d^{\omega},$$

where $a_d^{\omega}$ denotes the constant infinite word $a_d a_d a_d a_d \dots$.

In contrast, characterizing words whose 2-binomial complexity coincides with their subword complexity is considerably more difficult and remains an open problem. In the literature, apart from the Sturmian case and the case of words whose 1-binomial complexity coincides with their subword complexity, the only other known example is the Tribonacci word [Rau82], which is the most famous and widely studied Arnoux-Rauzy word [AR91].

**Proposition 2** ([LRR20b]). The 2-binomial complexity of the Tribonacci word coincides with its subword complexity.

It is worth mentioning that the proof provided by Lejeune, Rigo and Rosenfeld is computer-assisted. At the time of writing, obtaining a non-computer-assisted proof of this result remains an open problem.

Arnoux-Rauzy words (and, more generally, strict episturmian words [DJP01, GJ09]) form a class of ternary (resp. d-ary) infinite words that can be viewed as a combinatorial and arithmetic generalization of Sturmian words. Lejeune, Rigo and Rosenfeld conjectured that all Arnoux-Rauzy words have their 2-binomial complexity equal to their subword complexity (see [LRR20b] and [Lej21, Chapter 4, Section 4.4 and Appendix B]; see also Section 7 of this article where some numerical experiments are discussed).

**Conjecture 3** (Lejeune, Rigo, Rosenfeld). The 2-binomial complexity of any Arnoux-Rauzy word coincides with its subword complexity.
Although the Tribonacci word is the only known example of an Arnoux-Rauzy word satisfying this property, the computer-assisted proof developed for it could potentially be applied to other purely morphic Arnoux-Rauzy words to determine whether this property holds in those cases as well (see [LRR20b, Section 6]).

Our main contributions are summarized in the following theorem, which provides several new and broad classes of words whose 2-binomial complexity coincides with their subword complexity.

**Theorem 1.** Let $d \ge 2$.

(i) If $w$ is a 1-balanced $d$-ary word, then its 2-binomial complexity is equal to its subword complexity.

(ii) If $w$ is a word with subword complexity $n \in \mathbb{N}_{>0} \mapsto n + (d-1)$, then its 2-binomial complexity is equal to its subword complexity.

(iii) If $w$ is a hypercubic billiard word in dimension $d$, then its 2-binomial complexity is equal to its subword complexity.

(iv) If $w$ is obtained as the coloring of a Sturmian word with another Sturmian words [DMP24], then its 2-binomial complexity is equal to its subword complexity.

Interestingly, all these examples can be thought of as generalizations of Sturmian words. At the time of writing, apart from the trivial case described above where the 1-binomial complexity coincides with the subword complexity, we are not aware of any word genuinely unrelated to Sturmian words and whose 2-binomial complexity coincides with its subword complexity.

The proof of Theorem 1 relies on the two key Lemmas 7 and 9 stated in Section 3. These lemmas provide sufficient conditions for the 2-binomial complexity of a word to coincide with its subword complexity, and can be regarded as a first step toward a characterization of words satisfying this property. More precisely:

- Statements (i)–(iii) of Theorem 1 follow from Lemma 7, which states that if all the binary projections of a given word are 1-balanced, then its 2-binomial complexity coincides with its subword complexity.

- Statement (iv) of Theorem 1 follows from Lemma 9, which asserts that words whose $k$-binomial complexity equals their subword complexity are stable under a coloring process.

Finally, let us mention that for every $k \ge 3$, it is known that there exist words whose $k$-binomial complexity, but not their $(k-1)$-binomial complexity, coincides with their subword complexity. This was proved by Rigo, Stipulanti and Whiteland in [RSW24], where they showed that the image of any Sturmian word under $(k-2)$ iterations of the Thue-Morse substitution satisfies this property, see [RSW24, Theorems 7.2 and 7.4].

**Outline.** This paper is organized as follows. We recall the necessary definitions and the notation in Section 2. In Section 3, we present the general structure of the proof of Theorem 1. In particular, we state the two key Lemmas 7 and 9 mentioned above, and discuss the optimality of each assertion. Then, in Section 4, we prove that the 2-binomial complexity of any binary 1-balanced word is equal to its subword complexity. This covers statements (i)–(iii) of Theorem 1 in the case $d=2$. Section 5 is devoted to the proof of Lemma 8 (a generalization of Lemma 7), as well as to statements (i)–(iii) of Theorem 1 (for $d \ge 3$). Section 6 is dedicated to the proof of Lemma 9 and statement (iv) of Theorem 1. Finally, we gather some open questions in Section 7.
## 2 Definitions and notation

**Basics.** Let $\mathcal{A}$ be a finite set, referred to as an *alphabet*. A finite word $w$ written over the alphabet $\mathcal{A}$ is an element of $\mathcal{A}^* := \bigcup_{i=0}^{\infty} \mathcal{A}^i$, where $\mathcal{A}^0 = \{\epsilon\}$ with $\epsilon$ denoting the empty word. For any $k \in \mathbb{N}_{>0}$, we write $\mathcal{A}^{\le k} := \bigcup_{i=0}^{k} \mathcal{A}^i$ for the set of all finite words of length at most $k$. A (right) *infinite word* $w$ written over the alphabet $\mathcal{A}$ is an element of $\mathcal{A}^\mathbb{N}$.

A factor or contiguous subword $u$ of length $n$ of a word $w$ is a finite word formed of $n$ consecutive letters of $w$, while a scattered subword of length $n$ of $w$ is a word consisting of $n$, not necessarily consecutive, letters of $w$. For instance, if $w = 11212$, then 11 is a factor (and therefore also a scattered subword) of $w$, 22 is a scattered subword but not a factor of $w$, and 221 is neither a factor nor a scattered subword of $w$. The language of $w$, denoted $\mathcal{L}(w)$, is the set of all factors of $w$. We also denote by $\mathcal{L}_n(w) := \mathcal{L}(w) \cap \mathcal{A}^n$ the set of length $n$ factors of $w$.

We write $w[n]$ for the letter occurring at position $n$ in the word $w$ (the indexation starts at 0), and $w[n : m]$ for the length $m-n+1$ factor of $w$ starting at position $n$ and ending at position $m$, both included.

For a finite word $w \in \mathcal{A}^*$, we denote by $|w|$ its length, and by $|w|_a$ the number of occurrences of the letter $a \in \mathcal{A}$ in $w$. More generally, for a finite word $u \in \mathcal{A}^*$, we denote by $|w|_u$ the number of occurrences of $u$ in $w$ as a factor, and by $\binom{w}{u}$ the number of its occurrences in $w$ as a scattered subword. For instance, if $w = 11212$, then $|w| = 5$, $|w|_1 = 3$, $|w|_{12} = 2$, and $\binom{w}{12} = 5$. Note that the empty word has length zero: $|\epsilon| = 0$.

**Remark 4.** (i) Counting how many times a letter $a \in \mathcal{A}$ appears in $w$, either as a factor or as a scattered subword, is the same. Hence, $\binom{w}{a} = |w|_a = \binom{|w|_a}{1}$, where the last term refers to the usual binomial coefficient over the integers.

(ii) More generally, for a word of the form $a^m$ with $m \in \mathbb{N}_{>0}$ (i.e., the word consisting of $m$ consecutive occurrences of $a$), we have $\binom{w}{a^m} = \binom{|w|_a}{m}$. Indeed, there are $\binom{|w|_a}{m}$ different ways to choose $m$ distinct occurrences of $a$ in $w$, each corresponding to one occurrence of $a^m$ in $w$ as a scattered subword.

(iii) Since by convention $a^0 := \epsilon$ for any letter $a \in \mathcal{A}$, it is natural to adopt the convention that $\binom{w}{\epsilon} = \binom{|w|_a}{0} = 1$ for every finite word $w \in \mathcal{A}^*$.

We say that a word $w$ is *c-balanced* ($c \in \mathbb{N}$) if, for every equally long factors $u, v$ of $w$, and for every letter $a \in \mathcal{A}$, we have $||u|_a - |v|_a| \le c$. For example, the word $w = 11212$ is 1-balanced while the word $w' = 11122$ is 2-balanced but not 1-balanced (in [And21a, And21b, AV23, AV24], the optimal constant of balancedness is termed *imbalance*). An infinite word is said to be *unbalanced* if it is not *c-balanced* for any $c \in \mathbb{N}$.

Given two alphabets $\mathcal{A}$ and $\mathcal{B}$, a substitution $\sigma : \mathcal{A} \to \mathcal{B}^*$ is a letters to words application, which we extend to a morphism over $\mathcal{A}^*$ (seen as the free monoid for the concatenation). For instance, if $\sigma : \{0,1\} \to \{0,1\}^*$ is defined by $\sigma : 0 \mapsto 01, 1 \mapsto 0$, then $\sigma(010) = \sigma(0)\sigma(1)\sigma(0) = 01001$. More generally, substitutions are also extended over the set of infinite words in the following standard way: if $w = a_0a_1a_2a_3\dots$ where each $a_i$ is a letter from the alphabet $\mathcal{A}$, then $\sigma(w) := \sigma(a_0)\sigma(a_1)\sigma(a_2)\sigma(a_3)\dots$.

**Complexities.** Two finite words $u, v \in \mathcal{A}^*$ are said to be *abelian equivalent* (resp. $k$-binomially equivalent, where $k \in \mathbb{N}_{>0}$ is a parameter) when, for every letter $a \in \mathcal{A}$, $|u|_a = |v|_a$ (resp. when, for every finite word $x \in \mathcal{A}^{\le k}$, $\binom{u}{x} = \binom{v}{x}$). In such cases, we write $u \sim_{\text{ab}} v$ (resp. $u \sim_k v$). For example, if $u = 121221$ and $v = 211221$, then $u \sim_{\text{ab}} v$ and $u \sim_2 v$, but $u \not\sim_3 v$.
by erasing from $w$ all the letters $a \in A \setminus B$. Formally, $\pi_B : A \to B^*$ is the substitution defined by $a \in A \setminus B \mapsto \epsilon$ and $b \in B \mapsto b$. For instance, if $w = aabaca$, then $\pi_{a,b}(w) = aabaa$. We say that $w$ has 1-balanced binary projections when all its binary projections are 1-balanced, i.e., when for every pair of distinct letters $a, b \in A$, the projection $\pi_{a,b}(w)$ is 1-balanced.

Words with 1-balanced binary projections generalize the ternary words with Sturmian erasures introduced in [DGK04]. As we will show later, 1-balanced words, d-ary words with subword complexity $n \in \mathbb{N}_{>0} \mapsto n + (d-1)$, and hypercubic billiard words all have 1-balanced binary projections (see Lemmas 11, 13, 14 and 15).

**Hypercubic billiard words.** In dimension $d \ge 1$, a hypercubic billiard word is an infinite $d$-ary word that encodes the sequence of hyperfaces (i.e., $(d-1)$-dimensional faces) successively hit by a billiard ball moving in the unit hypercube of $\mathbb{R}^d$, where parallel hyperfaces are labeled by the same letter (see Figure 1). In what follows, the parameter $\theta$ denotes the initial momentum of the ball and the parameter $x$ denotes its initial position.

<figure><img src="image_3.png" /><figcaption>Figure 1: The ball, initially located in $x$ with a momentum $\theta$, generates the infinite word $w = 1211212112...$</figcaption></figure>

It is well known that a square billiard word generated by a momentum $\theta$ whose co-ordinates are rationally independent is a Sturmian word [MH40]. More generally, any square billiard word is 1-balanced. Thus, since any projection of a hypercubic billiard word is itself a lower-dimensional hypercubic billiard word, it follows that all the binary projections of a hypercubic billiard words are 1-balanced (see Lemmas 14 and 15).

**Coloring of words.** Given two infinite words $w_0 \in A^\mathbb{N}$ and $w_1 \in B^\mathbb{N}$ written over disjoint alphabets $(A \cap B = \emptyset)$, we define, for every letter $a \in A$, a new infinite word $\text{color}(w_0, a, w_1) \in (A \sqcup B \setminus \{a\})^\mathbb{N}$ obtained as the coloring of the letter $a$ in $w_0$ by $w_1$. Formally, we set

$$ \text{color}(w_0, a, w_1)[n] := \begin{cases} w_0[n] & \text{if } w_0[n] \neq a, \\ w_1[k-1] & \text{if } w_0[n] = a \text{ and } |w_0[0:n]|_a = k. \end{cases} $$

For example, the coloring of the letter $a$ in the Fibonacci word $w_0 \in \{0, a\}^\mathbb{N}$ by the
**Proposition 6.** If $w$ is a binary 1-balanced word, then its 2-binomial complexity coincides with its subword complexity.

According to the terminology introduced by Morse and Hedlund in [MH40], this generalization also applies to *periodic* and *skew Sturmian* words. As described in their work, these words have a combinatorial structure very similar to that of Sturmian words. Thus, this proposition represents only a slight extension of Rigo and Salimov's result. However, since it is the first step toward the proof of Theorem 1 – and for the sake of self-containedness– we provide a detailed proof in Section 4.

The converse of Proposition 6 is false. Indeed, it is easy to see that the eventually constant binary word $w = 11222222\dots$ is 2-balanced but not 1-balanced, and yet its 2-binomial complexity coincides with its subword complexity (cf Proposition 1). More generally, for every integer $m \ge 2$, the eventually constant word $1^m222222\dots$ is $m$-balanced but not $(m-1)$-balanced, and its 2-binomial complexity coincides with its subword complexity.

Furthermore, Proposition 6 does not admit any straightforward generalization. Indeed, the Thue-Morse word $w_{\text{tm}} = 0110100110010110\dots$ is binary and 2-balanced, but its 2-binomial complexity is strictly smaller than its subword complexity (it suffices to notice that $0110, 1001 \in \mathcal{L}(w_{\text{tm}})$ and $0110 \sim_2 1001$). This shows that the assumption “$w$ is 1-balanced” in Proposition 6 cannot be weakened to “$w$ is 2-balanced”. More generally, since for every $k \in \mathbb{N}_{>0}$, the $k$-binomial complexity of the Thue-Morse word never coincides with its subword complexity (indeed, the $k$-binomial complexity of any fixed point of a *Parikh-constant substitution* is bounded, see [RS15, Theorem 13]), it follows that even the weaker statement –“if $w$ is a binary 2-balanced word, then there exists an integer $k$ such that its $k$-binomial complexity coincides with its subword complexity”– does not hold.

## 3.2 Words with binary 1-balanced projections

The following key lemma provides a sufficient condition for a word to have its 2-binomial complexity equal to its subword complexity.

**Lemma 7.** Let $d \ge 2$ and $w \in \{1, \dots, d\}^N$. If all the binary projections of $w$ are 1-balanced, then its 2-binomial complexity is equal to its subword complexity.

This result is a special instance of the following more general lemma.

**Lemma 8.** Let $d \ge 2$, $k \in \mathbb{N}_{>0}$ and $w \in \{1, \dots, d\}^N$. If, for every pair of distinct letters $i, j \in \{1, \dots, d\}$, $b_{\pi_{i,j}(w)}^k = p_{\pi_{i,j}(w)}$, then the $k$-binomial complexity of $w$ coincides with its subword complexity.

*Proof of Lemma 7.* Thanks to Proposition 6, if all the binary projections of a given word $w$ are 1-balanced, then the 2-binomial complexity of each binary projection coincides with its subword complexity. As a result, Lemma 7 follows from Lemma 8 applied with $k=2$. $\square$

The proof of Lemma 8 is given in Section 5, where we also establish statements (i)–(iii) of Theorem 1 by showing that all the binary projections of any of the following words are 1-balanced:

- $d$-ary 1-balanced words (Lemma 11),

- $d$-ary words with subword complexity $n \in \mathbb{N}_{>0} \mapsto n + (d-1)$ (Lemma 13),

- hypercubic billiard words in dimension $d$ (Lemmas 14 and 15).
Note that statement (ii) of Theorem 1 (words with subword complexity $n \in \mathbb{N}_{>0} \mapsto n + (d-1)$) cannot be extended to all quasi-Sturmian words. Indeed, consider the substitution $\sigma: 1 \mapsto 1221$, $2 \mapsto 2112$. Then, according to the characterization by Cassaigne (see [Cas97, Proposition 8]), for every Sturmian word $w_0 \in \{1, 2\}^N$, the image word $w := \sigma(w_0)$ is a quasi-Sturmian word. Since $1221 \sim_2 2112$, it is clear that $b_w^2 \neq p_w$.

It is worth mentioning that the result for hypercubic billiard words holds for every such word: no additional assumption on the initial momentum $\theta$ of the ball is required. This contrasts with the expression of their subword complexity [Bar95, Béd09], which only holds under additional hypotheses on the momentum $\theta$. Thus, even when no explicit expression for the subword complexity is known, the 2-binomial complexity of these words is still equal to their subword complexity.

The converses of Lemmas 7 and 8 do not hold: the Tribonacci word

$$w_{\text{tribo}} = 121312112131212131211213121312112121212121211213121\dots$$

provides a counterexample. For instance, its 2-binomial complexity coincides with its subword complexity; however, none of its three binary projections is 1-balanced. Indeed, one can check that

$$u = 1121121121121, v = 21211211211212 \in \mathcal{L}_{14}(\pi_{1,2}(w_{\text{tribo}})) \quad \text{and} \quad |u|_1 - |v|_1 = 2,$$

$$u = 1111, v = 3113 \in \mathcal{L}_4(\pi_{1,3}(w_{\text{tribo}})) \quad \text{and} \quad |u|_1 - |v|_1 = 2,$$

$$u = 22322322322322, v = 32322322322323 \in \mathcal{L}_{14}(\pi_{2,3}(w_{\text{tribo}})) \quad \text{and} \quad |u|_2 - |v|_2 = 2,$$

which proves that the converse of Lemma 7 is false. More generally, none of the three binary projections of the Tribonacci word has its 2-binomial complexity equal to its subword complexity. Indeed, one can check that

$$u = 21121121121121121, v = 1212112112112121 \in \mathcal{L}_{16}(\pi_{1,2}(w_{\text{tribo}})) \quad \text{and} \quad u \sim_2 v,$$

$$u = 311113, v = 131131 \in \mathcal{L}_6(\pi_{1,3}(w_{\text{tribo}})) \quad \text{and} \quad u \sim_2 v,$$

$$u = 322322322322322323, v = 2323223223223232 \in \mathcal{L}_{16}(\pi_{2,3}(w_{\text{tribo}})) \quad \text{and} \quad u \sim_2 v,$$

which shows that the converse of Lemma 8 is false.

### 3.3 Stability by coloring

We now present our second key lemma, which establishes a stability result under coloring for words whose k-binomial complexity coincides with their subword complexity. Its proof is given in Section 6. Note that, since Sturmian words have their 2-binomial complexity equal to their subword complexity, statement (iv) of Theorem 1 is a special case of this more general statement.

**Lemma 9.** Let $w_0 \in \mathcal{A}^N$ and $w_1 \in \mathcal{B}^N$ be two infinite words written over disjoint alphabets. If there exists $k \in \mathbb{N}_{>0}$ such that $b_{w_0}^k = p_{w_0}$ and $b_{w_1}^k = p_{w_1}$, then, for every letter $a \in \mathcal{A}$, the k-binomial complexity of color($w_0, a, w_1$) coincides with its subword complexity.

As an immediate consequence, Lemma 9 furnishes an inductive method to construct words whose k-binomial complexity is equal to their subword complexity over increasingly larger alphabets.
The converse of Lemma 9 is trivially true: any word $w$ whose $k$-binomial complexity coincides with its subword complexity can be expressed as $\mathbf{color}(w_0, a, w_1)$, where $w_0$ and $w_1$ are two infinite words over disjoint alphabets such that $b_{w_0}^k = p_{w_0}$ and $b_{w_1}^k = p_{w_1}$. Indeed, the simple choice $w_0 = 111111...$, $a = 1$ and $w_1 = w$ suffices. However, the more interesting converse statement – requiring that both $w_0$ and $w_1$ are defined over alphabets of **strictly smaller** size than $p_w(1)$ (the number of distinct letters occurring in $w$) – does not hold. The Tribonaci word is again a counterexample to such a statement. Indeed, its 2-binomial complexity coincides with its subword complexity but, as already seen, none of its three binary projections satisfies this property. In particular, this shows that the Tribonaci word cannot be obtained as the coloring of two binary words such that both of them have their 2-binomial complexity equal to their subword complexity.

# 4 Proof of Proposition 6

This section is devoted to the proof of Proposition 6: the 2-binomial complexity of any binary 1-balanced word coincides with its subword complexity. As already mentioned, the case of Sturmian words was treated by Rigo and Salimov in [RS15]. Following the terminology of Morse and Hedlund [MH40], it remains only to consider the cases of periodic and skew Sturmian words. Morse and Hedlund showed that these words have a combinatorial structure closely similar to that of Sturmian words, and the proof of Rigo and Salimov can be extended straightforwardly to these two cases. However, for the reader's convenience and to ensure this article remains self-contained, we provide a complete proof of Proposition 6. Although our proof is, in spirit, essentially the same as that of Rigo and Salimov, we take this opportunity to present it in a more “elementary form” – that is, requiring no prerequisites beyond the definition of 1-balanced words.

*Proof of Proposition 6.* We proceed by contrapositive and consider an infinite word $w \in \{1, 2\}^\mathbb{N}$ such that there exists $m \in \mathbb{N}_{>0}$ for which $b_w^2(m) < p_w(m)$, i.e., such that there exists two factors $u, v \in \mathcal{L}_m(w)$ for which $u \neq v$ and $u \sim_{2\text{-bin}} v$. Our goal is to prove that such word $w$ is not 1-balanced.

Since $u \neq v$, there exists $p, u', v', s \in \mathcal{L}(w)$ with $u', v' \neq \epsilon$ such that $u = pu's, v = pv's$ and the first (resp. the last) letter of $u'$ differs from that of $v'$. We claim that $u'$ and $v'$ are 2-binomially equivalent (this result is called the *cancellation property* in [RSW24, Lemma 2.2]). Indeed, for every $i \in \{1, 2\}$ one immediately verifies that

$$ \binom{u}{i} = \binom{pu's}{i} = \binom{p}{i} + \binom{u'}{i} + \binom{s}{i} \quad \text{and} \quad \binom{v}{i} = \binom{pv's}{i} = \binom{p}{i} + \binom{v'}{i} + \binom{s}{i}, $$

and the equality $\binom{u}{i} = \binom{v}{i}$ yields $\binom{u'}{i} = \binom{v'}{i}$. Moreover, for every $i, j \in \{1, 2\}$ (possibly equal), we have:

$$ \begin{aligned} \binom{u}{ij} = \binom{pu's}{ij} &= \binom{p}{ij} + \binom{p}{i}\binom{u's}{j} + \binom{u's}{ij} \\ &= \binom{p}{ij} + \binom{p}{i}\left[\binom{u'}{j} + \binom{s}{j}\right] + \binom{u'}{ij} + \binom{u'}{i}\binom{s}{j} + \binom{s}{ij}, \end{aligned} $$

and

$$ \binom{v}{ij} = \binom{p}{ij} + \binom{p}{i}\left[\binom{v'}{j} + \binom{s}{j}\right] + \binom{v'}{ij} + \binom{v'}{i}\binom{s}{j} + \binom{s}{ij}. $$
Since $\binom{u}{ij} = \binom{v}{ij}$, $\binom{u'}{i} = \binom{v'}{i}$, and $\binom{u'}{j} = \binom{v'}{j}$, the two previous relations yield $\binom{u'}{ij} = \binom{v'}{ij}$.
We have proved that, for every $x \in \{1, 2\}^{\le 2}$, $\binom{u'}{x} = \binom{v'}{x}$, i.e., $u'$ and $v'$ are 2-binomially equivalent. In particular, note that $|u'| = |v'| \ge 2$. Indeed, they must be equally long because they are 2-binomially equivalent, and they cannot be reduced to a single letter since their first letters differ and they have the same number of occurrences of each letter.

Up to renaming the letters if necessary, it suffices to consider the following two cases (recall that $|u'| = |v'| \ge 2$):

- Case 1: $u' = 1u''1$ and $v' = 2v''2$,

- Case 2: $u' = 1u''2$ and $v' = 2v''1$.

In the first case, we have $|u''|_2 - |v''|_2 = |u'|_2 - (|v'|_2 - 2) = 2$, and $w$ is not 1-balanced. We now consider the second case. Since $m := |u'|_1 = |v'|_1 \ge 1$, there exist $2m$ integers $k_1, \dots, k_m, l_1, \dots, l_m \in \mathbb{N}$ with $k_m \ge 1$ and $l_1 \ge 1$, such that

$$u' = 12^{k_1} 12^{k_2} \dots 12^{k_m} \quad \text{and} \quad v' = 2^{l_1} 12^{l_2} \dots 12^{l_m} 1.$$

Using this decomposition of $u'$ and $v'$, we can compute $\binom{u'}{12}$ and $\binom{v'}{12}$ as follows. Since

$$\begin{aligned} \binom{u'}{12} &= \binom{12^{k_1} 12^{k_2} \dots 12^{k_m}}{12} = \binom{1}{1} \binom{2^{k_1} 12^{k_2} \dots 12^{k_m}}{2} + \binom{2^{k_1} 12^{k_2} \dots 12^{k_m}}{12} \\ &= \left(\sum_{i=1}^{m} k_i\right) + \binom{12^{k_2} \dots 12^{k_m}}{12}, \end{aligned}$$

we obtain inductively:

$$\binom{u'}{12} = \left(\sum_{i=1}^{m} k_i\right) + \left(\sum_{i=2}^{m} k_i\right) + \dots + \left(\sum_{i=m}^{m} k_i\right),$$

that we rewrite:

$$\binom{u'}{12} = \left(\sum_{i=1}^{m-1} k_i\right) + \left(\sum_{i=2}^{m-1} k_i\right) + \dots + \left(\sum_{i=m-1}^{m} k_i\right) + mk_m = \sum_{j=1}^{m-1} \left(\sum_{i=j}^{m-1} k_i\right) + mk_m.$$

Similarly:

$$\binom{v'}{12} = \left(\sum_{i=2}^{m} l_i\right) + \left(\sum_{i=3}^{m} l_i\right) + \dots + \left(\sum_{i=m}^{m} l_i\right) = \sum_{j=2}^{m} \left(\sum_{i=j}^{m} l_i\right) = \sum_{j=1}^{m-1} \left(\sum_{i=j+1}^{m} l_i\right),$$

and we eventually obtain:

$$\binom{u'}{12} = \binom{v'}{12} \implies mk_m = \sum_{j=1}^{m-1} \left[ \left( \sum_{i=j+1}^{m} l_i \right) - \left( \sum_{i=j}^{m-1} k_i \right) \right].$$

We distinguish two subcases:

- Case 2a: For every $j \in \{1, \dots, m-1\}$, $\left(\sum_{i=j+1}^{m} l_i\right) - \left(\sum_{i=j}^{m-1} k_i\right) \le 1$.

- Case 2b: There exists $j \in \{1, \dots, m-1\}$ such that $\left(\sum_{i=j+1}^{m} l_i\right) - \left(\sum_{i=j}^{m-1} k_i\right) \ge 2$.
Case 2a cannot occur. Indeed, since $k_m \ge 1$, we would have the following contradiction:

$$m \le mk_m = \sum_{j=1}^{m-1} \left[ \left( \sum_{i=j+1}^{m} l_i \right) - \left( \sum_{i=j}^{m-1} k_i \right) \right] \le \sum_{j=1}^{m-1} 1 = m-1.$$

In case 2b, consider the factors $x = 12^{k_j} 1 \dots 12^{k_{m-1}} 1 \in \mathcal{L}(u')$ and $y = 2^{l_{j+1}} 1 \dots 12^{l_m} \in \mathcal{L}(v')$. These satisfy $|x|_1 = |y|_1 + 2$ and $|y|_2 \ge |x|_2 + 2$, hence $|y| \ge |x|$. Therefore, any factor $y'$ of $y$ of length $|x|$ satisfies $|x|_1 - |y'|_1 \ge |x|_1 - |y|_1 = 2$, which shows that $w$ is not 1-balanced. $\square$

## 5 Proof of Lemma 8 and of Theorem 1, assertions (i)–(iii)

We begin by stating and proving (since the proof is short) a known reconstruction lemma (see [Lot97, Lemma 6.2.19]).

**Lemma 10.** Let $d \ge 2$ and $u \in \{1, \dots, d\}^*$. The word $u$ is uniquely determined by the set of its binary projections $\{\pi_{i,j}(u) \mid i, j \in \{1, \dots, d\} \text{ and } i \neq j\}$.

*Proof.* We argue by contradiction and assume that there exists $v \in \{1, \dots, d\}^*$ such that $v \neq u$ and yet $\pi_{i,j}(v) = \pi_{i,j}(u)$ for every pair of distinct letters $i, j \in \{1, \dots, d\}$. Since $v \neq u$, there must exist $p, u', v' \in \{1, \dots, d\}^*$ and two distinct letters $i, j \in \{1, \dots, d\}$ such that $u = piu'$ and $v = pjv'$. However, the equality $\pi_{i,j}(v) = \pi_{i,j}(u)$ implies that $\pi_{i,j}(p) i \pi_{i,j}(v') = \pi_{i,j}(p) j \pi_{i,j}(u')$, which leads to the contradiction $i = j$. Therefore, $u$ and $v$ must be equal, completing the proof. $\square$

*Proof of Lemma 8.* Let $w \in \{1, \dots, d\}^N$ with $d \ge 2$, and assume that there exists $k \in \mathbb{N}_{>0}$ such that, for every distinct letters $i, j \in \{1, \dots, d\}$, the $k$-binomial complexity of $\pi_{i,j}(w)$ coincides with its subword complexity. We aim to prove that $w$ fulfills the same property, i.e., that every factor of $w$ is alone in its $k$-binomial equivalence class. Let $u, v \in \mathcal{L}(w)$ be two factors of $w$ such that $u \sim_k v$. Our goal is to prove that $u = v$.

First, for every distinct letters $i, j \in \{1, \dots, d\}$, and for every finite word $x \in \{i, j\}^{\le k} \subseteq \{1, \dots, d\}^{\le k}$, we have $\binom{u}{x} = \binom{v}{x}$. Moreover, in such a case we also have

$$\binom{\pi_{i,j}(u)}{x} = \binom{u}{x} \quad \text{and} \quad \binom{\pi_{i,j}(v)}{x} = \binom{v}{x}. \qquad (2)$$

Indeed, the number of occurrences of $x \in \{i, j\}^*$ in $u$ (resp. $v$), as a scattered subword, does not depend on how many letters from $\{1, \dots, d\} \setminus \{i, j\}$ appear in $u$ (resp. $v$), nor on their positions.

Gathering these relations, we have shown that for every $x \in \{i, j\}^{\le k}$, $\binom{\pi_{i,j}(u)}{x} = \binom{\pi_{i,j}(v)}{x}$, i.e., $\pi_{i,j}(u) \sim_k \pi_{i,j}(v)$. Since both projections $\pi_{i,j}(u)$ and $\pi_{i,j}(v)$ are factors of $\pi_{i,j}(w)$, and since $b_{\pi_{i,j}(w)}^k = p_{\pi_{i,j}(w)}$, we have that $\pi_{i,j}(u) = \pi_{i,j}(v)$. As this equality holds for every pair of distinct letters $i, j \in \{1, \dots, d\}$, Lemma 10 allows us to conclude that $u = v$. $\square$

The proof of Theorem 1, statement (i) relies on the following lemma.

**Lemma 11.** Let $d \ge 2$ and $w \in \{1, \dots, d\}^N$. If $w$ is c-balanced, then for every pair of distinct letters $i, j \in \{1, \dots, d\}$, the binary projection $\pi_{i,j}(w)$ is also c-balanced.
**Proof.** We proceed by contradiction and assume that there exist two distinct letters $i, j \in \{1, \dots, d\}$ such that $\pi_{i,j}(w)$ is not $c$-balanced. Then there exist two equally long factors $u, v \in \mathcal{L}(\pi_{i,j}(w))$ and a letter $a \in \{i, j\}$ such that $||u|_a - |v|_a| \ge c + 1$. Moreover, since $\pi_{i,j}(w)$ is a binary word, and since $u$ and $v$ have the same length, we have

$$|u|_i - |v|_i = |v|_j - |u|_j,$$

and the previous inequality holds for both $a = i$ and $a = j$. Without loss of generality, we assume that the letter $i$ has more occurrences in $u$ than in $v$, so (the letter $j$ occurs more in $v$ than $u$ and)

$$|u|_i - |v|_i = |v|_j - |u|_j \ge c + 1.$$

We now consider factors $u', v' \in \mathcal{L}(w)$ of $w$ such that $\pi_{i,j}(u') = u$ and $\pi_{i,j}(v') = v$. If $|u'| \le |v'|$, then writing $v' = ps$ with $|p| = |u'|$, we have

$$|u'|_i - |p|_i \ge |u'|_i - |v'|_i = |\pi_{i,j}(u')|_i - |\pi_{i,j}(v')|_i \ge c + 1,$$

which contradicts the $c$-balancedness of $w$. Symmetrically, the case $|u'| > |v'|$ leads to a similar contradiction. $\square$

**Proof of Theorem 1, (i).** Lemma 11 implies that all the binary projections of any $d$-ary 1-balanced word are 1-balanced. The result then follows immediately from Lemma 7. $\square$

The proof of Theorem 1, statement (ii) comes from the following characterization of words with subword complexity $n \in \mathbb{N}_{>0} \mapsto n + (d - 1)$. We refer the reader to [FM97, Lemma 1 and Lemma 4] for a proof of this result.

**Lemma 12** (Ferenczi, Mauduit, 97). Let $\mathcal{A}$ be a $d$-ary alphabet with $d \ge 3$, and let $w \in \mathcal{A}^{\mathbb{N}}$ be a word with subword complexity $n \in \mathbb{N}_{>0} \mapsto n + (d - 1)$.

(i) If $w$ is recurrent (i.e., every factor of $w$ occurs infinitely often in $w$), then there exist:
- a Sturmian word $w_0 \in \{1, 2\}^{\mathbb{N}}$,

- a partition $\mathcal{A} = \mathcal{B} \sqcup \mathcal{C} \sqcup \mathcal{D}$ where $\mathcal{B} = \{b_1, \dots, b_{N_{\mathcal{B}}}\}$, $\mathcal{C} = \{c_1, \dots, c_{N_{\mathcal{C}}}\}$ and $\mathcal{D} = \{d_1, \dots, d_{N_{\mathcal{D}}}\}$, with both $\mathcal{B} \ne \emptyset$ and $\mathcal{C} \sqcup \mathcal{D} \ne \emptyset$,

such that $pw = \sigma(w_0)$, where $\sigma: \{1, 2\} \to \mathcal{A}^*$ is the substitution

$$1 \mapsto b_1 \dots b_{N_{\mathcal{B}}} c_1 \dots c_{N_{\mathcal{C}}}, \quad 2 \mapsto b_1 \dots b_{N_{\mathcal{B}}} d_1 \dots d_{N_{\mathcal{D}}}$$

and where $p$ is a (possibly empty) prefix of $\sigma(1)$ or $\sigma(2)$.

(ii) If $w$ is not recurrent, then there exist $1 \le d' < d$, a $d'$-letter subalphabet $\mathcal{B} \subset \mathcal{A}$, and a recurrent word $w_0 \in \mathcal{B}^{\mathbb{N}}$ with subword complexity $n \in \mathbb{N}_{>0} \mapsto n + (d' - 1)$ such that

$$w = a_1 \dots a_{d-d'} w_0,$$

where the letters $a_i$ are the $d - d'$ distinct elements of $\mathcal{A} \setminus \mathcal{B}$.

This characterization has the following consequence.

**Lemma 13.** Let $d \ge 3$ and let $w$ be a $d$-ary word. If $p_w(n) = n + (d - 1)$ for every $n \in \mathbb{N}_{>0}$, then all the binary projections of $w$ are 1-balanced.

**Proof.** Let $w \in \mathcal{A}^{\mathbb{N}}$ be a $d$-ary word with subword complexity $p_w(n) = n + (d - 1)$ for every $n \ge 1$. We distinguish two cases.

**Case 1.** The word $w$ is recurrent. We write $w$ as in Lemma 12, item (i). Our goal is to prove that, for every pair of distinct letters $a, b \in \mathcal{A}$, the projection $\pi_{a,b}(w)$ is 1-balanced.
First, if $a$ and $b$ belong to the same subalphabet $\mathcal{B}$, $\mathcal{C}$, or $\mathcal{D}$, then $\pi_{a,b}(w)$ is purely periodic, with period $ab$ or $ba$. Indeed, $\pi_{a,b}(\sigma(1))$ and $\pi_{a,b}(\sigma(2))$ are equal to $ab$, $ba$, or the empty word $\epsilon$, depending on the subalphabet (note that $ab$ and $ba$ cannot both occur). In particular, $\pi_{a,b}(w)$ is 1-balanced.

Secondly, if $a, b \in \mathcal{C} \sqcup \mathcal{D}$ but belong to different subalphabets – say $a \in \mathcal{C}$ and $b \in \mathcal{D}$ – then $\pi_{a,b}(\sigma(1)) = a$ and $\pi_{a,b}(\sigma(2)) = b$. Thus, up to replace the letters 1 by $a$ and the letters 2 by $b$ in $w_0$, we have $\pi_{a,b}(w) = w_0$ or $S(w_0)$, where $S$ is the shift operator acting on infinite words $(S(w)[n] = w[n+1])$. Consequently $\pi_{a,b}(w)$ is Sturmian and, in particular, 1-balanced.

Finally, if $a \in \mathcal{B}$ and $b \in \mathcal{C} \sqcup \mathcal{D}$ – say $b \in \mathcal{C}$ – then $\pi_{a,b}(\sigma(1)) = ab$ and $\pi_{a,b}(\sigma(2)) = a$. In this case, $\pi_{a,b}(w) = \tau(w_0)$ or $S(\tau(w_0))$ or $\tau(S(w_0))$, where $\tau : \{1,2\} \to \{a,b\}^*$ is the substitution defined by $\tau(1) = ab$ and $\tau(2) = a$. It is well known that such a substitution maps Sturmian words to Sturmian words, see [Lot02, Chapter 2, Section 2.3]. Thus, $\pi_{a,b}(w)$ is 1-balanced.

**Case 2.** The word $w$ is not recurrent. According to Lemma 12, we have $w = a_1 \dots a_{d-d'}w_0$, where $w_0 \in \mathcal{B}^N$ is a recurrent word whose subword complexity is $n \in \mathbb{N}_{>0} \mapsto n + (d' - 1)$, and where the letters $a_i \in \mathcal{A} \setminus \mathcal{B}$ are distinct and do not occur in $w_0$. Thus, for every pair of distinct letters $a, b \in \mathcal{A}$, $\pi_{a,b}(w)$ is either equal to $ab$ (both $a$ and $b$ belong to $\mathcal{A} \setminus \mathcal{B}$), or $ab^\omega$ ($a \in \mathcal{A} \setminus \mathcal{B}$ and $b \in \mathcal{B}$), or $\pi_{a,b}(w_0)$ (both $a$ and $b$ belong to $\mathcal{B}$). In the first two cases $\pi_{a,b}(w)$ is clearly 1-balanced, while the third case has already been treated in Case 1. $\square$

*Proof of Theorem 1, (ii).* Let $d \ge 2$ and $w$ be a $d$-ary word with subword complexity $n \in \mathbb{N}_{>0} \mapsto n + (d-1)$. If $d=2$, then $w$ is Sturmian and the result is already known. If $d \ge 3$, then according to Lemma 13 all the binary projections of $w$ are 1-balanced. The result is then an immediate consequence of Lemma 7. $\square$

We conclude this section with the proof of Theorem 1, statement (iii). This result relies on the following two well-known lemmas.

**Lemma 14.** Let $d \ge 2$, and let $w \in \{1, \dots, d\}^N$ be a hypercubic billiard word in dimension $d$. Then, for every subalphabet $\mathcal{B} \subset \{1, \dots, d\}$, the projection $\pi_{\mathcal{B}}(w)$ is a hypercubic billiard word in dimension $\#\mathcal{B}$.

*Sketch of proof.* To see this, consider a ball moving inside a $d$-dimensional hypercubic billiard table. The projection of its trajectory onto any hyperface of the table corresponds to the trajectory of a ball moving inside a $(d-1)$-dimensional hypercubic billiard table. Moreover, one can verify that the codings of these two trajectories are related: the second coding is obtained from the first by erasing the letter corresponding to the label of the hyperface onto which the original trajectory is projected. The result then follows by an immediate induction on the dimension $d$. $\square$

The second lemma follows from the characterization of 1-balanced words by Morse and Hedlund [MH40]. Interested readers may consult [Vui03, Section 6] and [AV22, AV24] for results concerning the balancedness constants of hypercubic billiard words in arbitrary dimensions.

**Lemma 15.** Square billiard words are 1-balanced.

*Sketch of Proof.* The usual unfolding procedure shows that square billiard words can equivalently be obtained as cutting words. The connection between cutting words, mechanical words, codings of rotations and Sturmian words is fully detailed in [Lot02, Chapter 2,
Section 2.1], see in particular Theorem 2.1.13 and Lemmas 2.1.14 and 2.1.15 in that reference. □

*Proof of Theorem 1, (iii).* Lemmas 14 and 15 imply that all the binary projections of any hypercubic billiard words are 1-balanced. The result then follows once more from Lemma 7. □

# 6 Proof of Lemma 9 and Theorem 1, assertion (iv)

We now prove Lemma 9, which asserts that words whose k-binomial complexity coincides with their subword complexity remain stable under the coloring process described in Section 2. As already mentioned in Section 3, since Sturmian words have their 2-binomial complexity equal to their subword complexity, statement (iv) of Theorem 1 follows immediately from this result.

*Proof of Lemma 9.* Let $w_0 \in \mathcal{A}^N$ and $w_1 \in \mathcal{B}^N$ be two infinite words defined over disjoint finite alphabets. Let $a \in \mathcal{A}$ and $w := \text{color}(w_0, a, w_1)$ be the coloring of the letter $a$ in $w_0$ by $w_1$. We assume that $b_{w_0}^k = p_{w_0}$ and $b_{w_1}^k = p_{w_1}$ for some $k \in \mathbb{N}_{>0}$ and aim to prove that $b_w^k = p_w$. To this end, consider two factors $u, v \in \mathcal{L}(w)$ such that $u \sim_k v$. Our goal is to show that $u = v$.

We denote by $\sigma$ the substitution that maps $w$ back to $w_0$:

$$ \sigma: \begin{array}{rcl} \mathcal{A} \sqcup \mathcal{B} \setminus \{a\} & \to & \mathcal{A} \\ i & \mapsto & \left\{ \begin{array}{ll} i & \text{if } i \in \mathcal{A}, \\ a & \text{if } i \in \mathcal{B}. \end{array} \right. \end{array} $$

Clearly, $\sigma(w) = w_0$, $\sigma(u), \sigma(v) \in \mathcal{L}(w_0)$, $\pi_{\mathcal{B}}(w) = w_1$ and $\pi_{\mathcal{B}}(u), \pi_{\mathcal{B}}(v) \in \mathcal{L}(w_1)$. Moreover,

$$ u = \text{color}(\sigma(u), a, \pi_{\mathcal{B}}(u)) \quad \text{and} \quad v = \text{color}(\sigma(v), a, \pi_{\mathcal{B}}(v)). $$

Therefore, to prove that $u = v$ it is sufficient to prove that $\pi_{\mathcal{B}}(u) = \pi_{\mathcal{B}}(v)$ and $\sigma(u) = \sigma(v)$ (it is even equivalent). Thanks to a reasoning similar to that used in the proof of Lemma 8, we have $\pi_{\mathcal{B}}(u) \sim_k \pi_{\mathcal{B}}(v)$ (see equation (2) in Section 5), and then $\pi_{\mathcal{B}}(u) = \pi_{\mathcal{B}}(v)$. We now prove that $\sigma(u) = \sigma(v)$. To begin with, we claim that for any $x \in \mathcal{A}^*$

$$ \binom{\sigma(u)}{x} = \sum_{\substack{y \in (\mathcal{A} \sqcup \mathcal{B} \setminus \{a\})^{|x|} \\ \sigma(y) = x}} \binom{u}{y}. \qquad (3) $$

We temporarily postpone the proof of this claim. Since $u \sim_k v$, we have $\binom{u}{y} = \binom{v}{y}$ for every $y \in (\mathcal{A} \sqcup \mathcal{B} \setminus \{a\})^{\le k}$. Combined with (3), this yields $\binom{\sigma(u)}{x} = \binom{\sigma(v)}{x}$ for every $x \in \mathcal{A}^{\le k}$, i.e., $\sigma(u) \sim_k \sigma(v)$. Finally, since both $\sigma(u)$ and $\sigma(v)$ belong to $\mathcal{L}(w_0)$, and since the k-binomial complexity of $w_0$ coincides with its subword complexity, we have that $\sigma(u) = \sigma(v)$.

To conclude, it only remains to prove relation (3). Writing $u = u_1 u_2 \dots u_p$ with each $u_i$ a letter, we have $\sigma(u) = \sigma(u_1)\sigma(u_2)\dots\sigma(u_p)$ where each $\sigma(u_i)$ is again a letter. Therefore, by definition of binomial coefficients of words, we have

$$ \binom{\sigma(u)}{x} := \#\{(i_1, i_2, \dots, i_{|x|}) \mid 1 \le i_1 < i_2 < \dots < i_{|x|} \le p \text{ and } \sigma(u_{i_1})\sigma(u_{i_2})\dots\sigma(u_{i_{|x|}}) = x\}, $$

$$ \binom{u}{y} := \#\{(j_1, j_2, \dots, j_{|y|}) \mid 1 \le j_1 < j_2 < \dots < j_{|y|} \le p \text{ and } u_{j_1} u_{j_2} \dots u_{j_{|y|}} = y\}. $$
Hence, the identity (3) is an immediate consequence of the set equality

$$E(u, x) = \bigcup_{\substack{y \in (A \sqcup B \setminus \{a\})^{|x|} \\ \sigma(y)=x}} F(u, y) \qquad (4)$$

where

$$\begin{aligned} E(u, x) &:= \{(i_1, i_2, \dots, i_{|x|}) \mid 1 \le i_1 < i_2 < \dots < i_p \le p \text{ and } \sigma(u_{i_1})\sigma(u_{i_2})\dots\sigma(u_{i_{|x|}}) = x\}, \\ F(u, y) &:= \{(j_1, j_2, \dots, j_{|y|}) \mid 1 \le j_1 < j_2 < \dots < j_p \le p \text{ and } u_{j_1}u_{j_2}\dots u_{j_{|y|}} = y\}. \end{aligned}$$

Let us prove that (4) holds. First, it is clear that the sets $(F(u, y))_y$ are disjoint. Indeed, if there exist $y, z \in (A \sqcup B \setminus \{a\})^{|x|}$ such that $F(u, y) \cap F(u, z) \neq \emptyset$, then there exists $(j_1, \dots, j_{|x|})$ such that $y = u_{j_1} \dots u_{j_{|x|}} = z$. Secondly, if $(i_1, \dots, i_{|x|}) \in E(u, x)$, then $\sigma(u_{i_1}) \dots \sigma(u_{i_{|x|}}) = x$. Consequently, $y := u_{i_1} \dots u_{i_{|x|}}$ belongs to $(A \sqcup B \setminus \{a\})^{|x|}$ and satisfies $\sigma(y) = x$. In other words

$$(i_1, \dots, i_{|x|}) \in F(u, y) \subseteq \bigcup_{\substack{z \in (A \sqcup B \setminus \{a\})^{|x|} \\ \sigma(z)=x}} F(u, z).$$

Finally, if $(j_1, \dots, j_{|x|}) \in F(u, y)$ for some $y \in (A \sqcup B \setminus \{a\})^{|x|}$ satisfying $\sigma(y) = x$, then

$$x = \sigma(y) = \sigma(u_{j_1} \dots u_{j_{|x|}}) = \sigma(u_{j_1}) \dots \sigma(u_{j_{|x|}}),$$

which means that $(j_1, \dots, j_{|x|})$ belongs to $E(u, x)$. This completes the proof. $\square$

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

# 7 Open questions

We established a sufficient condition and a stability result for words whose 2-binomial complexity is equal to their subword complexity. These two results allowed us to show that several families of words, such as d-ary 1-balanced words, d-ary words with subword complexity $n \in \mathbb{N}_{>0} \mapsto n + (d-1)$, hypercubic billiard words, and colorings of Sturmian words by Sturmian words, all share this property. All these classes of words can be thought of as generalizations of Sturmian words.

However, we have also shown that the combinatorial structure of the Tribonacci word does not fall within this framework, and a fully non-computer-assisted proof that its 2-binomial complexity coincides with its subword complexity is still missing. In this direction, even a non-computer-assisted proof that the k-binomial complexity of the Tribonacci word coincides with its subword complexity for some $k \ge 3$ would already be of interest.

We recall that, more generally, Lejeune, Rigo and Rosenfeld conjectured that the 2-binomial complexity of any Arnoux-Rauzy word is equal to its subword complexity. Some modest numerical experiments carried out by the author of this paper agreed with this conjecture.

**Proposition 16.** Up to length $n = 99$, each factor of an Arnoux-Rauzy word generated by a periodic directive sequence with period at most 5 is alone in its 2-binomial class (for a definition of directive sequence, see for instance the proposition in [AR91, Section 2]).

Since Arnoux-Rauzy words are themselves a generalization of Sturmian words, this raises the following open questions.
**Question 1.** Is there a natural class of words that can be seen as a *genuine generalization of Sturmian words*, for which the 2-binomial complexity of at least one (resp. all) of its elements differs from its subword complexity?

For example, Cassaigne-Selmer words (also known as *C*-adic words, [CLL17, CLL22]) are also a fair arithmetic generalization of Sturmian words, and some modest numerical experiments carried out by the author of this paper suggest that their 2-binomial complexity also coincides with their subword complexity.

**Proposition 17.** Up to length $n = 99$, each factor of a Cassaigne-Selmer word generated by a periodic directive sequence with period at most 5 is alone in its 2-binomial class.

Since both Arnoux-Rauzy words and Cassaigne-Selmer words belong to the broader class of dendric words [BDFD$^+$15, BDD$^+$18], it would also be interesting to investigate whether there exists a subclass of dendric words for which none of its elements satisfies this property.

**Question 2.** In the opposite direction, is there a class of words, genuinely unrelated to Sturmian words, such that the 2-binomial complexity, but not the 1-binomial complexity, of at least one (resp. all) of its elements coincides with its subword complexity?

Our last comment concerns the binary case. Proposition 6 states that the 2-binomial complexity of any binary 1-balanced word coincides with its subword complexity. Moreover, we saw that the converse does not hold. Indeed, words of the form $1^m2^\omega$ (with $m \ge 2$) are *m*-balanced but not ($m-1$)-balanced and their 2-binomial complexity coincides with their subword complexity. However, the 1-binomial complexity of these words also coincides with their subword complexity, and it would be interesting to determine whether other counterexamples exist.

**Question 3.** Does the converse of Proposition 6 hold when restricted to words for which their 1-binomial complexity does not coincide with their subword complexity?

**Acknowledgments.** The author would like to thank Mélodie Andrieu for having introduced him to Combinatorics on Words and for her enthusiasm for this work.

## References

[AMST94a] P. Arnoux, Ch. Mauduit, I. Shiokawa, and J.I. 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] P. Arnoux, Ch. Mauduit, I. Shiokawa, and J.I. Tamura. Rauzy’s conjecture on billiards in the cube. *Tokyo Journal of Mathematics*, 17(1):211–218, 1994.

[And21a] M. Andrieu. *Exceptional trajectories in the symbolic dynamics of multidimensional continued fraction algorithms*. PhD thesis, Aix-Marseille Université, 2021.

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

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

[AV22] M. Andrieu and L. Vivion. Imbalances in hypercubic billiard words. *18th Mons Computer Science Days*, Prague, Czech Republic, 2022.
[AV23] M. Andrieu and L. Vivion. Minimal complexities for infinite words written with *d* letters. In A. Frid and R. Mercaş, editors, *Combinatorics on Words*, pages 3–13, Cham, 2023. Springer Nature Switzerland.

[AV24] M. Andrieu and L. Vivion. Imbalances in hypercubic billiard words (II). *19th Mons Computer Science Days*, Nice, France, 2024.

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

[BDD$^{+}$18] V. Berthé, F. Dolce, F. Durand, J. Leroy, and D. Perrin. Rigidity and substitutive dendric words. *International Journal of Foundations of Computer Science*, 29(5):705–720, 2018.

[BDFD$^{+}$15] V. Berthé, C. De Felice, F. Dolce, J. Leroy, D. Perrin, Ch. Reutenauer, and G. Rindone. Acyclic, connected and tree sets. *Monatshefte für Mathematik*, 176(4):521–550, 2015.

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

[Béd09] N. Bédaride. Directional complexity of the hypercubic billiard. *Discrete Mathematics*, 309(8):2053–2066, 2009.

[Cas97] J. Cassaigne. Sequences with grouped factors. In *Developments in language theory*, pages 211–222, 3rd International Conference, DLT 1997, Aristotle University of Thessaloniki, Greece, 1997.

[CH73] E.M. Coven and G.A. Hedlund. Sequences with minimal block growth. *Mathematical systems theory*, 7(2):138–153, 1973.

[CLL17] J. Cassaigne, S. Labbé, and J. Leroy. A set of sequences of complexity $2n + 1$. In S. Brlek, F. Dolce, Ch. Reutenauer, and É. Vandomme, editors, *Combinatorics on Words*, pages 144–156, Cham, 2017. Springer International Publishing.

[CLL22] J. Cassaigne, S. Labbé, and J. Leroy. Almost everywhere balanced sequences of complexity $2n+1$. *Moscow Journal of Combinatorics and Number Theory*, 11(4):287–333, 2022.

[DGK04] F. Durand, A. Guerziz, and M. Koskas. Words and morphisms with sturmian erasures. *Bulletin of the Belgian Mathematical Society-Simon Stevin*, 11(4):575–588, 2004.

[DJP01] X. Droubay, J. Justin, and G. Pirillo. Episturmian words and some constructions of de Luca and Rauzy. *Theoretical Computer Science*, 255(1):539–553, 2001.

[DMP24] L. Dvořáková, Z. Masáková, and E. Pelantová. 2-balanced sequences coding rectangle exchange transformation. *Theory of Computing Systems*, 68:1537–1555, 2024.

[FM97] S. Ferenczi and Ch. Mauduit. Transcendence of numbers with a low complexity expansion. *Journal of Number Theory*, 67(2):146–161, 1997.

[GJ09] A. Glen and J. Justin. Episturmian words: a survey. *RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications*, 43(3):403–442, 2009.

[Gra73] R.L. Graham. Covering the positive integers by disjoint sets of the form $\{[n\alpha + \beta]: n = 1, 2, \dots\}$. *Journal of Combinatorial Theory, Series A*, 15(3):354–358, 1973.

[GRW24] M. Golafshan, M. Rigo, and M.A. Whiteland. Computing the *k*-binomial complexity of generalized Thue-Morse words. *Preprint*, arXiv:2412.18425, 2024.

[Hub00] P. Hubert. Suites équilibrées. *Theoretical Computer Science*, 242(1):91–108, 2000.

[LCWW24] X.T. Lü, J. Chen, Z.X. Wen, and W. Wu. On the 2-binomial complexity of the generalized Thue-Morse words. *Theoretical Computer Science*, 986:114342, 2024.

[Lej21] M. Lejeune. *On the k-binomial equivalence of finite words and k-binomial complexity of infinite words*. PhD thesis, Université de Liège, 2021.
[LLR20] M. Lejeune, J. Leroy, and M. Rigo. Computing the *k*-binomial complexity of the Thue-Morse word. *Journal of Combinatorial Theory, Series A*, 176:105284, 2020.

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

[Lot02] M. Lothaire. *Algebraic Combinatorics on Words*. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2002.

[LRR20a] M. Lejeune, M. Rigo, and M. Rosenfeld. The binomial equivalence classes of finite words. *International Journal of Algebra and Computation*, 30(07):1375-1397, 2020.

[LRR20b] M. Lejeune, M. Rigo, and M. Rosenfeld. Templates for the k-binomial complexity of the tribonacci word. *Advances in Applied Mathematics*, 112:101947, 2020.

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

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

[Rau82] G. Rauzy. Nombres algébriques et substitutions. *Bulletin de la Société Mathématique de France*, 110:147-178, 1982.

[RRW25] A. Renard, M. Rigo, and M.A. Whiteland. Introducing *q*-deformed binomial coefficients of words. *Journal of Algebraic Combinatorics*, 61(2), 2025.

[RS15] M. Rigo and P. Salimov. Another generalization of abelian equivalence: Binomial complexity of infinite words. *Theoretical Computer Science*, 601:47-57, 2015.

[RSW23] M. Rigo, M. Stipulanti, and M.A. Whiteland. Gapped binomial complexities in sequences. In *2023 IEEE International Symposium on Information Theory (ISIT)*, pages 1294-1299, Taipei, Taiwan, 2023.

[RSW24] M. Rigo, M. Stipulanti, and M.A. Whiteland. Characterizations of families of morphisms and words via binomial complexities. *European Journal of Combinatorics*, 118:103932, 2024.

[Vui03] L. Vuillon. Balanced words. *Bulletin of the Belgian Mathematical Society - Simon Stevin*, 10(5):787-805, 2003.

[Whi21] M.A. Whiteland. Equations over the *k*-binomial monoids. In T. Lecroq and S. Puzynina, editors, *Combinatorics on Words*, pages 185-197, Cham, 2021. Springer International Publishing.