# Imbalances in Hypercubic Billiard Words (II) (extended abstract)

Mélodie Andrieu, Léo Vivion

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

## To cite this version:

Mélodie Andrieu, Léo Vivion. Imbalances in Hypercubic Billiard Words (II) (extended abstract). 19Th Mons Theoretical Computer Science Days, Université Côte d'Azur, Sep 2024, Nice, France. hal-04902345

HAL Id: hal-04902345

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

Submitted on 20 Jan 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
Imbalances in Hypercubic Billiard Words (II)
(extended abstract)

Mélodie Andrieu¹ and Léo Vivion¹

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

**Abstract**

We explore the set of imbalances of hypercubic billiard words with *rationally dependent* letter frequencies.

# 1 Introduction

A *cubic billiard word in dimension d* is an infinite *d*-ary word denoting the sequence of the faces successively hit by a billiard ball moving inside the unit cube of $\mathbb{R}^d$, where two parallel faces are encoded by the same letter. These words are parameterized by the initial position $x \in [0, 1]^d$, and the initial momentum $\theta \in \mathbb{R}^d \setminus \{0\}$, of the ball.

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

Here, the billiard word $w(x_0, \theta)$ starts with 211212...

Hypercubic billiard words have been studied in [Rau83, AMST94, Bar95, Bor07, BH07, Béd09] (computation of their complexity), in [BR05] (palindromic complexity), in [Vui03] (upper bound for the imbalance), and more recently by the present authors, in [AV22, AV23] (imbalance and abelian complexity).

In the present work, we are again interested in their imbalance. The *imbalance* is a combinatorial quantity that measures how evenly the letters are distributed in an infinite word. By definition, the imbalance of *w* is the maximal difference in the number of occurrences of a same letter in equally long subwords of *w*:

$$ \mathrm{Imb}(w) = \sup\{|u|_i - |v|_i \mid i \text{ is a letter, and } u, v \text{ are subwords of } w \text{ with the same length}\}, $$
where $|u|_i$ counts the number of occurrences of the letter $i$ in $u$. In other words, the imbalance is the *smallest* constant $C$ for which the word $w$ is $C$-balanced. In dimension 2, cubic (square) billiard words are characterized by their imbalance [MH40].
In a previous work, the authors completely described the set of imbalances of hypercubic billiard words whose momenta have rationally independent coordinates. The aim of the present abstract is to explore what happens in the case of rationally dependent coordinates.

## 2 Previous works and questions

We start by recalling the seminal results of Vuillon.

**Proposition 1** (Vuillon, 2003 [Vui03]). Let $d \in \mathbb{N}_{>0}$. In dimension $d$: - the imbalance of any cubic billiard word, whose momentum has rationally independent entries, is bounded above by $d-1$;

- there exists a cubic billiard word whose momentum has rationally independent entries, and whose imbalance is exactly $d-1$.

In [AV22], the authors of the present work further announced that:

* For $d \in \{1, \dots, 4\}$, the imbalance of any cubic billiard word generated by a momentum with rationally independent entries is exactly $d-1$.

* For $d \ge 5$, the set of imbalances of cubic billiard words generated by momenta with rationally independent entries is $\{3, \dots, d-1\}$.

These assertions follow directly from the result below.

**Proposition 2** (Andrieu, Vivion, 2022 [AV22]). Let $d \ge 3$. Let $\theta \in \mathbb{R}^d$ with rationally independent entries. The imbalance of any cubic billiard word $w$ generated by the momentum $\theta$ is:

$$ \mathrm{Imb}(w) = 2 + \max_{i \in \{1, \dots, d\}} |\mathrm{pref}_{d-3} w(0, \theta)|_i, $$

where the notation $\mathrm{pref}_n(w)$ stands for the prefix of length $n$ of $w$.

Proposition 2 also describes the geometrical shape of the set of momenta which lead to a specified imbalance $k$. In the sequel, and with no loss of generality, we choose to work with momenta that lie within the simplex:

$$ \Delta := \left\{ (\theta_1, \dots, \theta_d) \in (\mathbb{R}_>0)^d \mid \sum_{i \in \{1, \dots, d\}} \theta_i = 1 \right\}. $$

(Under this renormalization, the frequencies of the letters are exactly the coordinates of $\theta$.) Now, for every $k$, Proposition 2 gives an explicit system of inequalities on the entries of $\theta$ to generate cubic billiard words with an imbalance equal to $k$. In other words, the simplex $\Delta$ is partitioned into polytopes, on each of which the imbalance is constant for all momenta with rationally independent entries. For instance for $d=5$ (the reader will immediately check, with the remark preceding Proposition 2, that the partition is trivial for smaller $d$), the imbalance takes the value 4 in the region

$$ \mathcal{R}_4 := \bigcup_{i \neq j} \{(\theta_1, \dots, \theta_d) \in \Delta \mid \theta_i \ge 2\theta_j\}, $$

and the value 3 in the rest of the simplex.

In the sequel, we will continue to denote by $\mathcal{R}_k$ (more precisely, $\mathcal{R}_k(d)$) the closure of the set of rationally independent momenta in $\Delta$ which generate cubic billiard words (in dimension $d$) with an imbalance $k$.
Now, let $w$ be a cubic billiard word whose momentum $\theta$ admits rational dependencies. Our questions are the following: Does (and if so, how much) the imbalance of $w$ depend on the region(s) $\mathcal{R}_k$ to which the momentum belongs? Does (and if so, how much) the imbalance of $w$ depend on the rational dimension of the coordinates of $\theta$?

### 3 New results

Our first general result asserts that “most of” cubic billiard words behave like their rationally independent neighbors. By the term “most of”, we do not mean “almost all” (for the Lebesgue measure on the simplex $\Delta$) – such a statement is already satisfied by the sole rationally independent momenta–, but something topologically stronger.

**Theorem 1.** Let $d \ge 1$, and $k \ge 1$.

(1) The imbalance of any cubic billiard word $w$ with momentum in $\mathcal{R}_k$ satisfies:

$$ \mathrm{Imb}(w) \le k. $$

(2) Around each $\theta \in \mathcal{R}_k$ with rationally independent entries, there exists a neighborhood $N_\theta$ (with respect to the subspace topology on $\Delta$), such that all cubic billiard word $w$ whose momentum belongs to $N_\theta$ has an imbalance

$$ \mathrm{Imb}(w) = k. $$

However, along with the regularity emphasized by Theorem 1, some exotic behaviors appear.

The reader may have noticed that, so far, the imbalance of cubic billiard words depended only on the momentum $\theta$, and not on the initial position $x$ of the ball. This is not true in general. Therefore, two quantities are of interest: the maximal, and the minimal, imbalances among cubic billiard words whose momentum $\theta$ is specified.

In the first direction, our main result asserts that the maximal imbalance for a cubic billiard word with momentum $\theta$ can be lower than, but is never too far from, that of its rationally independent neighbors.

**Theorem 2.** Let $d \ge 1$, and $k \ge 1$. For every $\theta \in \mathcal{R}_k$, there exists a cubic billiard word $w$ with momentum $\theta$, which satisfies:

$$ \mathrm{Imb}(w) \ge k - 2. $$

We are furthermore able to construct examples of momenta $\theta$, in the interior of some $\mathcal{R}_k$, for which the imbalance never exceeds $k - 2$.

In the second direction, we confirm, and quantify, the intuition whereby, if the imbalance of a billiard word with momentum in $\mathcal{R}_k$ is much lower than $k$, then this momentum admits many rational dependencies.

**Theorem 3.** Let $d \ge 3$, and $k \ge 1$. Let $\theta \in \mathcal{R}_k$ with rationally dependent entries, and denote by $\delta < d$ the rational dimension of its coordinates. Then, every cubic billiard word $w$ with momentum $\theta$ satisfies:

$$ \mathrm{Imb}(w) \ge \max \left( \frac{k-2}{q+1}, \frac{k-2-r}{q} \right), $$

where $q$ and $r$ stands for the quotient and remainder in the euclidean division of $2d-3-\delta$ by $\max(\delta - 1, 1)$.
For instance, set the parameters $d = 30, k = 29$, and $\delta = 20$. Theorem 3 guarantees that any momentum $\theta \in \mathbb{R}^{30} \cap \mathbb{R}_{29}$, with rational dimension at least 20, will generate cubic billiard words whose imbalance is at least 14. It turns out that, for these specific parameters, the lower bound is optimal: we are indeed able to construct one such cubic billiard word whose imbalance is exactly 14. Further numerical computations suggest that, in general, the lower bound provided by Theorem 3 is of good quality.

## References

[AMST94] 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.

[AV22] Mélodie Andrieu and Léo Vivion. Imbalances in hypercubic billiard words. *Mons Theoretical Computer Science Days, Prague*, 2022.

[AV23] Mélodie Andrieu and Léo Vivion. Minimal complexities for infinite words written with $d$ letters. In *Combinatorics on Words*. Springer International Publishing, 2023.

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

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

[BH07] Nicolas Bédaride and Pascal Hubert. Billiard complexity in the hypercube. *Annales de l'Institut Fourier*, 57(3):719–738, 2007.

[Bor07] Jean-Pierre Borel. A geometrical characterization of factors of multidimensional billiard words and some applications. *Theoretical Computer Science*, 380(3):286–303, 2007.

[BR05] Jean-Pierre Borel and Christophe Reutenauer. Palindromic factors of billiard words. *Theoretical Computer Science*, 340(2):334–348, 2005.

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

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

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