# A geometric point of view on the synchronization of three-Christoffel words

Lama Tarsissi, Ahmed A.Menaa, Laurent Vuillon, Laurent Najman

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

## To cite this version:

Lama Tarsissi, Ahmed A.Menaa, Laurent Vuillon, Laurent Najman. A geometric point of view on the synchronization of three-Christoffel words. 2023. hal-04234364

HAL Id: hal-04234364

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

Preprint submitted on 11 Oct 2023

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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>
A geometric point of view on the
synchronization of three-Christoffel words

Lama Tarsissi<sup>1,2</sup>, Ahmed A. Menaa<sup>2</sup>, Laurent Vuillon<sup>3</sup>, and Laurent Najman<sup>1</sup>

¹ Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, France

² Dept. Sciences and Engineering, University Sorbonne Abu Dhabi.

³ Univ. Savoie Mont Blanc, CNRS, LAMA, 73000 Chambéry, France

**Abstract.** We study the synchronization of three Christoffel words (i.e., superimposition of words with same length) from a geometric point of view. We provide a geometrical interpretation of the synchronization in terms of Reveilles' discrete lines. We introduce for the synchronization a technique based on algebra, arithmetic, and Cayley graphs. We define the orbital matrix, based on the vertices of the Cayley graph, for each Christoffel word. We provide a characterization of a vector, called the seed, which is a vector that synchronizes the edges of the three Cayley graphs. After synchronization, we show that each Christoffel word is replaced by a 4-connected Reveilles 2D segment whose parameter is given by the seed.

**Keywords:** Christoffel words · Cayley graphs · Reveilles' Discrete lines

# 1 Introduction

Christoffel words are fundamental objects in combinatorics [2,3], which have an interpretation in terms of Cayley graph. In discrete geometry, Christoffel words are coding of discrete segments on a square grid [11]. We consider the definition of a segment given by Reveilles [12]. Using the binary alphabet {0, 1}, synchronizing two, three or $n$ Christoffel words of the same length means applying a specific number of circular shifts on each binary word, in such a way that, for each position, one and only one word has a letter 1. From a geometric point of view, this means that, if we draw the segments corresponding to each shifted word, we have one and only one vertical step at each position. These shifted lines are nothing but the discrete 2D Reveilles' segments, for a particular parameter called *seed*. The aim of this paper is to provide a complete characterization of such a *seed*. It shall be noted that this work is a combinatorics on words and discrete geometry reformulation, with new proofs, of the results in [9,13].

The paper is organized as follows. In Sec. 2, we provide the definition of Christoffel words from a geometric point of view, and we read the word using the Reveilles discrete segment definition. In Sec. 3, we give our definition of synchronization, and we introduce it from a geometric point of view. In Sec. 4, we give some properties on the positions of letter 1 for the conjugates of Christoffel
words. In Sec. 5, we introduce the vertical invariant, and we give some of its
properties. Sec. 6 is dedicated to the main results of this paper, characterizing
algebraically a seed vector that synchronizes two and three generators. Such
a seed vector determines exactly the number of shifts needed. We show that
the elements of such seed vector correspond to the parameters of the Reveilles
discrete segments. Finally, we conclude in Sec. 7.

To ease the reading of this paper, the full proofs of all the lemmas, properties,
and theorems of the present paper can be found in the Appendix.

## 2 A geometric point of view on Christoffel words

Let $a, b$ be two integers in the set of non-negative integers $\mathbb{N}$. We denote $a \equiv b \pmod n$ if and only if $a - b$ is divisible by $n$. An **Alphabet A** is a finite set of symbols. An element of $A$ is a **letter**. A **word w** over an alphabet $A$ is a sequence of letters over $A$. We denote by $A^*$ the set of all the words formed by the alphabet $A$. The identity element of $A^*$ is the **empty word** $\varepsilon$. The concatenation of the word $w, n$ times, is written $w^n = www\cdots w \in A^*$. For all $w \in A^*$, the length of a word is the number of letters in $w$, and it is denoted $|w|$. The number of occurrences of the letter $a$ in $w$ is $|w|_a$, where $a \in A$. Hence, we have: $|w| = \sum_{a \in A} |w|_a$. If there exists $p, f, s \in A^*$ such that $w = pfs$, we say that $f$ is a **factor** of $w$. Given two words $w, w' \in A^*$, we say that $w$ is a **conjugate** of $w'$ if there exists $u, v \in A^*$ such that $w = uv$ and $w' = vu$. The set of all the conjugates of a word $w$ is denoted by $\mathcal{L}(w)$.

Two numbers $a$ and $b$ are **relatively prime** (written $a \perp b$) if the greatest common divisor between them is 1; i.e., $\gcd(a, b) = 1$.

Suppose $a, b \in \mathbb{N}$ and $a \perp b$, the **Christoffel path** of slope $\frac{b}{a}$ is the path from $(0, 0)$ to $(a, b)$ in the integer lattice $\mathbb{Z} \times \mathbb{Z}$, that satisfies the following two conditions [8].

(i) The path lies below the line segment that begins at the origin and ends at $(a, b)$.

(ii) The region in the plane enclosed by the path and the line segment contains no other points of $\mathbb{Z} \times \mathbb{Z}$ besides those of the path.

From a geometric point of view, we see the Christoffel path as the digitization of
a segment with a rational slope in $\mathbb{Z} \times \mathbb{Z}$. Let $a \perp b$, we consider the **Cayley graph**
of $\mathbb{Z}/(a+b)\mathbb{Z}$, which is a cycle, with vertices $0, b, 2b, \dots, a, 0 \pmod{a+b}$.

Starting from 0 and proceeding in the order listed above,

(i) label those edges $(s, t)$ satisfying $s > t$ by 1, named *decreasing*;

(ii) label those edges $(s, t)$ satisfying $s < t$ by 0, named *increasing*;

(iii) read edge-label in the prescribed order, i.e., $0 \xrightarrow{0} b \xrightarrow{?} \dots \xrightarrow{?} a \xrightarrow{1} 0$.

The (**lower**) Christoffel word of slope $\frac{b}{a}$ over the alphabet $\{0,1\}$, is obtained by reading the edges of the **Cayley graph** of $\mathbb{Z}/(a+b)\mathbb{Z}$ starting from 0. The vertices of the **Cayley graph** are called the **orbit** of the Christoffel word. The values on each vertex of the **Cayley graph** is called a **label**.

In other words, a Christoffel word is determined by encoding, with a Freeman
chain code [6], the discretization of a line segment of rational slope [1]. We recall
<figure><img src="image_3.png" /><figcaption>**Fig. 1.** On the left side, the Reveilles standard segment $D[3, 5, 0]$, whose Freeman code is the Christoffel word of slope $\frac{3}{5}$. On the right side, the representation as Cayley graphs for each row of $C_O(G, V)$, for $G = (5, 3)$. The synchronization of $D[3, 5, 0]$ and $D[5, 3, 0]$, obtained by some cyclic permutations, gives as a resultant: $w = 21211211$.</figcaption></figure>

that a Freeman chain code is defined, in this case, over an alphabet of two letters $\{0, 1\}$, which are associated to the right and up steps, respectively. We now introduce Christoffel words using a different, geometric point of view, based on the Reveilles discrete 2D line [4,12].

**Definition 1 ([12]).** The Reveilles discrete line $D(a, b, \mu, \omega)$, with parameters $(a, b, \mu)$ and arithmetic thickness $\omega$, is defined as the set of integer points $(x, y)$ verifying the double inequality: $\mu \le ax - by < \mu + \omega$

- where $a, b, \mu, \omega \in \mathbb{Z}$,

- $a \perp b$, $b \neq 0$ and the discrete line is of slope $\frac{a}{b}$.

In our work, we are only interested in standard 4-connected 2D lines, which verify $\omega = a + b$. This standard line, with slope $\frac{a}{b}$ and lower limit $\mu$, is denoted $D(a, b, \mu)$, and is infinite. Furthermore, in the following, we focus on the standard 4-connected 2D segment, $D[a, b, \mu]$, which is exactly the first $a+b$ integer points of the Reveilles discrete line $D(a, b, \mu)$, starting from the origin $(0, 0)$. See Fig. 1, left, for $D(3, 5, 0)$.

We denote by $\mathcal{R}(D[a, b, .])$ the set of all Reveilles discrete 2D segments obtained for different values of $\mu$. Let $a \perp b$, and $\mu \in \mathbb{Z}$. It is easy to show that the set $\mathcal{R}(D[a, b, .])$ is finite and is of cardinality $a + b$. Furthermore, as shown in [7, Lemma 4.5], the Freeman chain code of the discrete segment $D[a, b, 0]$ is the Christoffel word of slope $\frac{a}{b}$.

**Proposition 1.** Let $a \perp b$, and let $w$ be the Christoffel word of slope $\frac{a}{b}$. The set of Freeman chain codes of the elements of $\mathcal{R}(D[a, b, .])$ is in bijection with $\mathcal{L}(w)$.

Suppose that $a$ and $b$ are not relatively prime, and let $d = \gcd(a, b)$. In this case, the Christoffel word $w$ of slope $\frac{a}{b}$ is obtained from the Christoffel word $w'$ of slope $\frac{a}{d}$, by setting $w = w'^d$.

# 3 Synchronization of Christoffel words

In our work, we use explicitly some properties of Christoffel words, in order to synchronize 2 and 3 Christoffel words. At the same time, we show a geometric perspective on this synchronization. We define the following two matrices:
**Definition 2.** Let $G = (g_1, g_2, \dots, g_\ell)$, and $V = (v_1, v_2, \dots, v_\ell)$ be two vectors of strictly positive integers, and set $n = g_1 + \dots + g_\ell$. We define the Orbital matrix $O(G, V)$ and the Christoffel conjugate matrix $C_O(G, V)$ as $O(G, V) = (o_{i,j})_{\substack{i=1..\ell \\ j=0..n}}$ and $C_O(G, V) = (c_{i,j})_{\substack{i=1..\ell \\ j=0..n-1}}$, defined as: $o_{i,j} = (v_i + jg_i) \mod n$ and $c_{i,j} = \begin{cases} i & \text{if } o_{i,j} > o_{i,j+1} \\ 0 & \text{otherwise.} \end{cases}$

We call $G$ the generator vector, the $g_i$ being the generators. We set $V_0$ to be the zero vector.

**Definition 3.** A vector $V$ synchronizes the generator $G$ vector if each column of the matrix $C_O(G, V)$ contains exactly $\ell - 1$ occurrences of the letter 0 and one occurrence of a letter in $\{1, 2, \dots, \ell\}$. Such a vector is called a *seed*.

The first aim of this paper is to find a specific seed $V$, that synchronizes a generator $G$ of length 2 or 3. In other words, synchronizing the matrix $C_O(G, V_0)$ means finding a vector $V$ for which $C_O(G, V)$ has one and only one letter in each of its columns, i.e., one and only one decrease in each column. Once synchronized, any column of $O(G, V)$ can be considered as a seed vector. In this paper, we will choose a specific one, that relates us to the geometric definition of synchronization.

**Definition 4.** Given $\ell$ Christoffel words, written respectively over the alphabets $\{0, 1\}, \dots, \{0, \ell\}$, a synchronization provides a word over the alphabet $\{1, \dots, \ell\}$. The synchronized word is the word obtained by concatenating the non zero letters of each column of the synchronized matrix $C_O(G, V)$.

This notion is closely related to the **superimposition** (a lighter version of synchronization) defined in [10], with the difference that we do not only require the words to have no collision with the letter $\{1, 2, \dots, \ell\}$, we also require that there is a letter among $\{1, 2, \dots, \ell\}$ at each position. To rephrase it, the final word does not contain any occurrences of the letter 0.

*Example 1.* For the vectors $G = (5, 3)$ and $V_0 = (0, 0)$, we have $O(G, V_0)$ and $C_O(G, V)$ given respectively as follows:

$$O(G, V_0) = \begin{pmatrix} 0 & 5 & 2 & 7 & 4 & 1 & 6 & 3 & 0 \\ 0 & 3 & 6 & 1 & 4 & 7 & 2 & 5 & 0 \end{pmatrix} \qquad C_O(G, V_0) = \begin{pmatrix} 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 2 & 0 & 0 & 2 & 0 & 2 \end{pmatrix}$$

The seed $V = (0, 7)$ synchronizes $G$ and gives the word $w = 21211211$ (Fig. 1).

$$O(G, V) = \begin{pmatrix} 0 & 5 & 2 & 7 & 4 & 1 & 6 & 3 & 0 \\ 7 & 2 & 5 & 0 & 3 & 6 & 1 & 4 & 7 \end{pmatrix} \qquad C_O(G, V) = \begin{pmatrix} 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 2 & 0 & 2 & 0 & 0 & 2 & 0 & 0 \end{pmatrix}$$

*Synchronization from a geometric point of view:* We want to answer the following question. Is it possible to draw $\ell$ digital line segments, in such a way that each vertical move on these segments is separated from the others? More precisely, if $F_p$ is the Freeman chain code of the $p$th segment over the alphabet $\{0, p\}$, we would like to have, for all $1 \le k \le n$, $F_p[k] \ne 0$ implies $F_q[k] = 0$ for $p \ne q$. In other words, we want to synchronize $\ell$ digital line segments. The Freeman chain code for each of the $\ell$ segments gives us $C_O(G, V)$, where $G = (g_1, \dots, g_\ell)$, $\frac{g_i}{n-g_i}$
is the slope of the $i^{th}$ line segment, and $n = \sum_{i=1}^{l} g_i$. The seed vector is to be determined.

# 4 Positions of letter 1 for conjugates of Christoffel words

Let $w$ be a Christoffel word of slope $\frac{a}{b}$, where $a \perp b$. The orbit of $w$, called $O(w)$, is made of all the vertices of the Cayley graph of $\mathbb{Z}/(a+b)\mathbb{Z}$, starting from the label 0. Let $w'$ be the conjugate of $w$. We know that the orbit of $w'$, $O(w')$, is a shifted sequence of $O(w)$ starting from a certain label $p$, where $p$ is multiple of $a \mod a+b$. In this section, we are interested in determining the positions of the letter 1 for the Christoffel word $w$ or any of its conjugates based on their starting label of their orbits. The Christoffel word $w$ and its conjugate have exactly $a$ letters of 1 and $b$ letters of 0.

**Definition 5.** Let $w$ be a Christoffel word of slope $\frac{a}{b}$. We let $w'$ be a conjugate of $w$ such that $O(w')$ starts from the label $p$. The set of positions, denoted $P(a, b, p)$, is: $P(a, b, p) = \{1 \le i \le n \mid w[i] = 1\}$.

If $a \perp b$, the set $P(a, b, p)$ is calculated as follows:

**Proposition 2.** Let $w$ be a Christoffel word of slope $\frac{a}{b}$, where $a \perp b$. We let $w'$ be a conjugate of $w$ such that $O(w')$ starts from the label $p$. We set $\alpha$ as $\alpha a \equiv -1 \mod n$ and we have:

$$P(a, b, p) = \{(i\alpha + x) \mod n \mid i = 1 \dots a\}, \text{ where } xa \equiv -p \mod n.$$

In particular if $p = 0$, we are determining the positions of the letters 1 in the Christoffel word $w$. This specific result can be deduced using [10, Corollary 3.2].

*Example 2.* Let $w$ be a Christoffel word of slope $\frac{3}{5}$. The set of the indices of the letters 1 is $P(3, 5, 0) = \{(5i + 0 \mod 8) \mid i = 1 \dots 3\} = \{2, 5, 7\}$. We can write $w$ as $w = 00100101$.

To generalize the case, we consider $a$ and $b$ not relatively prime, and we have:

**Lemma 1.** Let $w$ be a Christoffel word of slope $\frac{a}{b}$, and we set $d = \gcd(a, b)$. We let $w'$ be a conjugate of $w$, such that $O(w')$ starts from the label $p$. The set of positions is given by: $P(a, b, p) = \cup_{j=0}^{d-1} \{(i\alpha + x) + j\frac{n}{d} \mod n; i = 1, \dots, \frac{n}{d}\}$, where $n = a + b, \alpha a \equiv -d \mod n, xa \equiv -p \mod n$.

*Example 3.* Let $w$ be the Christoffel word of slope $\frac{3}{6}$, and $w'$ its conjugate such that $O(w')$ starts from the label 3. We have $d = 3$ and $n = 9$. The set of the positions for the letters 1 is $P(3, 6, 3) = \cup_{j=0}^{2} \{(2i + x) + 3j \mod 9\}; i = 1\} = \{1, 4, 7\}$, where $\alpha = 2$ and $x = 2$. Hence, $w' = 010010010$.
# 5 Vertical invariant

We now define the vertical invariant to prove that any three generators, that are not pairwise distinct, can be synchronized.

**Definition 6.** Let $O(G, V)$ be the orbital matrix for a generator vector G of length $\ell \ge 2$ and a seed vector V. We set $n = \sum_{k=1}^{\ell} g_k$ and we define the vertical sum, for all $j \in \{0, \dots, n\}$, as the vector $A = (a_j)_{j=0}^{n}$, where $a_j = \sum_{i=1}^{\ell} o_{i,j}$.

The vertical sum $A$ of $O(G, V)$ is a constant vector when we choose the seed vector $V$ which synchronizes the generator vector $G$.

**Theorem 1.** The vertical sum is a constant vector if and only if there exists a unique decrease from one column to another.

*Proof.* ⇒ Let $O(G, V)$ be the orbital matrix for the generator vector G of length $\ell$, where $n = \sum_{k=1}^{\ell} g_k$. We let $A = (a_j)_{j=0}^{n}$ be the vertical sum, where $a_j = \sum_{i=1}^{\ell} o_{i,j}$ be a constant vector, where all the $a_j$ are equal to $u$. We fix a column $t$ of $O(G, V)$ and we let all the elements of the next column be greater than the $o_{i,t}$, but smaller than $n$. In this case, all the elements of the $t^{th}$ column of $C_O(G, V)$, i.e. $c_{i,t}$, are 0. This means there are no decreases in this column.

We have $o_{1,t+1} = o_{1,t} + g_1 < n$, $o_{2,t+1} = o_{2,t} + g_2 < n$, ..., and $o_{\ell,t+1} = o_{\ell,t} + g_\ell < n$. The sum of the elements of the column $t+1$ is equal to: $a_{j+1} = \sum_{i=1}^{\ell} o_{i,t+1} = \sum_{i=1}^{\ell} o_{i,t} + g_1 + g_2 + \dots + g_\ell = a_t + n = u + n \neq u$.

Suppose now that we have two decreasing positions at row $k$ and $\ell$ such that $k < \ell$, respecting all the previous conditions. We obtain the following: $o_{1,t+1} = o_{1,t} + g_1 < n$, ..., $o_{k,t+1} = o_{k,t} + g_k > n = o_{k,t} + g_k - n$, ..., and $o_{\ell,t+1} = o_{\ell,t} + g_\ell < n$.

Then, the elements of $c_{i,j}$ are all 0, unless $c_{k,t} = k$ and $c_{\ell,t} = \ell$. By calculating $a_{t+1} = \sum_{i=1}^{\ell} o_{i,t+1} = \sum_{i=1}^{\ell} o_{i,t} + g_1 + g_2 + \dots + g_{\ell-n} - n = a_j + n - 2n = u - n \neq u$. Hence, the vertical sum is not constant when we have more than one decrease. The same result is obtained if we have $p$ decreases, instead of two. In this case, $o_{i,t+1} = u - (p-1)n$, which is a contradiction.

⇒ Let $V$ be a seed vector that synchronizes $G$. We fix a column $t$ of $O(G, V)$ and we have: $o_{1,t} = o_{1,0} + tg_1$, ..., $o_{\ell,t} = o_{\ell,0} + tg_\ell$. Hence, $a_t = a_0 + tn$. By hypothesis, we know that we have exactly one decrease from one column to another. To reach the $t^{th}$ column, we have to remove $n$ $t$ times. Hence, we get: $a_t = a_0 = u \ \forall t \in \{0, \dots, n\}$. $\square$

When $A$ is a constant vector, we call the value of any element of $A$, the Vertical invariant, and we denote it by $I_{n,\ell}$, where $n$ is the sum of all the generators and $\ell$ is their number. Let us denote $d_i$ the greatest common denominator between each generator and $n$. We obtain $d_i = \gcd(g_i, n)$, for all $1 \le i \le n$. We can easily show that $\ell \le \sum_{i=1}^{\ell} d_i \le n$.

The vertical invariant can be calculated, as we can see in Proposition 3.
**Proposition 3.** $I_{n,l} = \frac{\ell n}{2} - \frac{1}{2} \sum_{i=1}^{\ell} d_i$, where $d_i = \gcd(g_i, n)$.

*Proof.* Let $g_i$ be the $i$-th generator of the vector $G$ and let $d_i = \gcd(g_i, n)$. Let $V$ be the seed vector that synchronizes $G$. $C_O(G, V_0)[i]$ is a Christoffel word of slope $\frac{g_i/d_i}{(n_i-g_i)/d_i}$ repeated $d_i$ times. $C_O(G, V)[i]$ is a conjugate $C_O(G, V_0)[i]$. The sum of the values of the $i$-th lines is $d_i \sum_{j=1}^{n/d_i-1} jd_i$ and so, the sum of the $k$-th lines is $\sum_{i=1}^{\ell} (d_i \sum_{j=1}^{n/d_i-1} jd_i)$. Since the sum of each of the $n$ columns is equal, we obtain $I_{n,l} = \frac{\sum_{i=1}^{\ell} (d_i \sum_{j=1}^{n/d_i-1} jd_i)}{n} = \frac{\sum_{i=1}^{\ell} (d_i^2 \sum_{j=1}^{n/d_i-1} j)}{n} = \frac{1}{n} \sum_{i=1}^{\ell} d_i^2 \frac{\binom{n}{i}-1}{2} = \frac{1}{n} \sum_{i=1}^{\ell} \frac{n^2-n d_i}{2} = \frac{\ell n}{2} - \frac{1}{2} \sum_{i=1}^{\ell} d_i$. $\square$

For $\ell = 2$, we have $I_{n,2} = n - d$, where $d = \gcd(g_1, g_2)$. If $g_1 \perp g_2$, then $I_{n,2} = n - 1$.

*Example 4.* In Example 1, the seed vector $V = (0,7)$ synchronizes the generator vector $G = (3,5)$. By computation, $I_{8,2} = n - 1 = 8 - 1 = 7$, as we can see in each column of $C_O(G, V)$, see Figure 1 right.

# 6 Seeds for two and three generators

Paquin and Reutenauer [10] have proved that two generators can always be synchronized for all $n$, in particular when $n$ is equal to their sum. To rewrite the result in our language, we notice that for $G = (g_1, g_2)$, the two discrete segments are of inverse slopes: $\frac{g_1}{g_2}$ and $\frac{g_2}{g_1}$. If we calculate the value of the vertical invariant, we obtain $I_{n,2} = n - d$; $d = \gcd(g_1, g_2)$. With some simple properties on Christoffel words, we can show that the seed vector for two generators is always of the form: $V = (0, n-d) = (0, I_{n,2})$. See Example 1.

For the rest of this section, we consider the generator vector $G = (g_1, g_2, g_3)$ of length 3, with $n = g_1 + g_2 + g_3$. We explicitly check the synchronization for all the possible cases, and we characterize the corresponding seed vectors. We show the link of this particular seed vector with the Reveilles 2D discrete line.

*Geometric formulation:* We are dealing with three discrete segments of the following form: $D[g_1, n-g_1, 0]$, $D[g_2, n-g_2, 0]$ and $D[g_3, n-g_3, 0]$. Clearly, the first and last steps in their Freeman code, do not respect our geometric constraint. We now look at the sets of Reveilles 2D discrete segments $\mathcal{R}(D[g_1, n-g_1, .])$, $\mathcal{R}(D[g_2, n-g_2, .])$ and $\mathcal{R}(D[g_3, n-g_3, .])$. We search for a $\mu$ (if it exists) that satisfies our condition, for each discrete Reveilles segment.

We remark that all the segments have the same digital length, $n$. For better illustrations, and only in the figures of the paper, after synchronization, we apply the morphism $\sigma$ from $A^*$ to $A^*$, such that $\sigma(0) = 0$ and $\sigma(i) = i0$, for $i \in \{1, 2, 3\}$. This morphism spreads the segments over the $x$-axis, and then the segments all have a horizontal length equals to $n$. Thus, we will be able to easily check that, on each vertical line, we have only one vertical step.
To study the synchronization of a generator vector of length 3, we must consider three cases. The first one is where any two of the three generators have the same value. The second one is where the three generators are identical. The last one is where the three generators are distinct.

**First case** – Without loss of generality, we assume that $g_1 = g_2 = g$, and we leave $g_3$ to be distinct from $g$. Let $n = 2g + g_3$, and $g \perp g_3$.

In order to determine the seed that synchronizes the generator vector $G = (g, g, g_3)$, we need to check the parity of $n$. If $n$ is an odd number, we have several properties which lead us to determine the exact seed. With some arithmetic computations left for the reader, we can show the following:

**Proposition 4.** Let $G = (g, g, g_3)$ be a generator vector with $n = 2g + g_3$.

1. $n$ is an odd number $\iff \gcd(n, g) = 1$, and $\gcd(n, g_3) = 1$.

2. $n$ is an even number $\iff \gcd(n, g) = 1$ and $\gcd(n, g_3) = 2$.

By applying the arithmetic definition of the vertical invariant, we obtain:

**Lemma 2.** Let $G = (g, g, g_3)$ be a generator vector with $n = 2g + g_3$.

1. If $n$ is an odd number, then $I_{n,3} = \frac{3}{2}(n-1)$.

2. If $n$ is an even number, then $I_{n,3} = \frac{3}{2}n - 2 = \frac{3n-4}{2}$.

The seed $S$ which synchronizes the generator vector $G = (g, g, g_3)$ is of the following form.

**Theorem 2.** Let $G = (g, g, g_3)$ be a generator vector such that $n = 2g + g_3$, and $g \perp g_3$. The seed vector $V$ which synchronizes $G$ is:

1. If $n$ is odd, the seed vector is: $V = (n - 1, \frac{n-1}{2}, 0)$.

2. If $n$ is even, the seed vector is: $V = (n - 1, \frac{n-2}{2}, 0)$.

In both cases, the seed element $0$ is always dedicated to the distinct generator.

*Proof. (Sketch)* Let $G = (g, g, g_3)$ be a generator vector such that $n = 2g + g_3$, and $g \perp g_3$. The two Christoffel words, $w_1, w_2$, obtained are of slopes: $\frac{g}{n-g}$ and $\frac{g_3}{n-g_3}$. In both cases, to show that the seed vector $V = (v_1, v_2, 0)$ synchronizes $G$, we define the three sets $A, B, C$ to be the sets of positions for the letters 1 for two conjugates of $w_1$ and for $w_2$ respectively. The orbits of the conjugate words of $w_1$ start with the labels $v_1$, and $v_2$, respectively. Hence, we have:

$$A = P(g, n - g, v_1) = \{i\alpha + x; i = 1 \dots g\}$$

$$B = P(g, n - g, v_2) = \{i\alpha + y; i = 1 \dots g\}$$

$$C = P(g_3, n - g_3, 0) = \{i\beta; i = 1 \dots g_3\},$$

where: $\alpha, \beta, x$ and $y$ are defined as in Section 4. To prove the theorem, we need to show that the sets $A, B$, and $C$ are pairwise disjoint, hence we can not get any two positions for the letters 1, 2, or 3 on the same column. $\square$

**Proposition 5.** Let $G = (g_1, g_2, g_3)$ and $V = (v_1, v_2, v_3)$ be the seed vector which synchronizes $G$. By encoding $D[g_1, n - g_1, -v_1]$, $D[g_2, n - g_2, -v_2]$ and $D[g_3, n - g_3, -v_3]$ using the Freeman Chain code, we obtain the exact lines of the matrix $C_O(G, V)$.
<figure><img src="image_4.png" /><figcaption>**Fig. 2.** 2D Graphical representation of the Christoffel Word matrix for $G = (4, 4, 3)$. From left to write: the original 3 segments, the synchronized segments, and the synchronized segments after morphism.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Fig. 3.** 2D Graphical representation of the Christoffel Word matrix for $G = (3, 3, 4)$. From left to write: the original 3 segments, the synchronized segments, and the synchronized segments after morphism.</figcaption></figure>

*Example 5.* Let $G = (4, 4, 3)$ with $n = 2.g + g_3 = 11$. By Lemma 2, we have $I_{n,3} = \frac{3.n-3}{2} = \frac{3.11-3}{2} = 15$. By Theorem 2, we have $V = (10, 5, 0)$ synchronizes $G$. The orbital matrix $O(G, V)$ and the Christoffel conjugate matrix $C_O(G, V)$ are given by:

$$O(G, V) = \begin{pmatrix} 10 & 3 & 7 & 0 & 4 & 8 & 1 & 5 & 9 & 2 & 6 & 10 \\ 5 & 9 & 2 & 6 & 10 & 3 & 7 & 0 & 4 & 8 & 1 & 5 \\ 0 & 3 & 6 & 9 & 1 & 4 & 7 & 10 & 2 & 5 & 8 & 0 \end{pmatrix} \quad C_O(G, V) = \begin{pmatrix} 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 2 & 0 & 0 & 2 & 0 & 2 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 & 0 & 0 & 0 & 3 & 0 & 0 & 3 \end{pmatrix}.$$

We note that:

$$D[4, 7, -10] = C_O(G, V)[0], D[4, 7, -5] = C_O(G, V)[1], \text{ and } D[3, 8, 0] = C_O(G, V)[2]. \\ \text{The synchronized word formed is } w = 12132123123, \text{ see Figure 2.}$$

*Example 6.* Let $G = (3, 3, 4)$ with $n = 2.g + g_3 = 10$. By Lemma 2, we have $I_{n,3} = \frac{3.n-4}{2} = \frac{3.10-4}{2} = 13$. By Theorem 2, we have $V = (9, 4, 0)$ synchronizes $G$. The orbital matrix $O(G, V)$ and the Christoffel conjugate matrix $C_O(G, V)$ are given by:

$$O(G, V) = \begin{pmatrix} 9 & 2 & 5 & 8 & 1 & 4 & 7 & 0 & 3 & 6 & 9 \\ 4 & 7 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 \\ 0 & 4 & 8 & 2 & 6 & 0 & 4 & 8 & 2 & 6 & 0 \end{pmatrix}; \quad C_O(G, V) = \begin{pmatrix} 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 & 2 & 0 & 0 & 2 & 0 \\ 0 & 0 & 3 & 0 & 3 & 0 & 0 & 3 & 0 & 3 \end{pmatrix};$$

We note that:

$$D[3, 7, -9] = C_O(G, V)[0], D[3, 7, -4] = C_O(G, V)[1], \text{ and } D[4, 6, 0] = C_O(G, V)[2]. \\ \text{The synchronized word formed is } w = 1231321323, \text{ see Figure 3.}$$
<figure><img src="image_6.png" /><figcaption>**Fig. 4.** 2D Graphical representation of the Christoffel Word matrix for $G = (3,3,6)$. From left to write: the original 3 segments, the synchronized segments, and the synchronized segments after morphism.</figcaption></figure>

**Second case** – Before checking the second case, where all the generators are identical, we need to study the case where $g$ and $g_3$ are not relatively prime.

Let $G = (g, g, g_3)$ be a generator vector, with $n = 2g + g_3$ and $\gcd(g, g_3) = d$. We have $g = d \cdot g', g_3 = d \cdot g'_3$ and $n = d \cdot n'$. We clearly see that: $O(G, V_0)[i] = d \cdot O(G, V_0)'[i]^d$, and $C_O(G, V_0)[i] = C_O(G, V_0)'[i]^d$, where $O(G, V_0)'$ and $C_O(G, V_0)'$ corresponds to the generator vector $G' = (g', g', g'_3)$.

**Example 7.** Let $G = (1, 1, 2)$ with $n = 4$ and the seed vector $V = (3, 1, 0)$. we have $I_{n,3} = 4$ and the Orbital Matrix is given by: $O(G, V) = \begin{pmatrix} 3 & 0 & 1 & 2 & 3 \\ 1 & 2 & 3 & 0 & 1 \\ 0 & 2 & 0 & 2 & 0 \end{pmatrix}$. For the vector $G' = (3, 3, 6)$, we can calculate immediately $V' = 3 \cdot V = (9, 3, 0)$, and both $O(G', V')$ and $C_O(G', V')$ can be deduced from $O(G, V)$ and $C_O(G, V)$:

$$O(G', V') = \begin{pmatrix} 9 & 0 & 3 & 6 & 9 & 0 & 3 & 6 & 9 & 0 & 3 & 6 & 9 \\ 3 & 6 & 9 & 0 & 3 & 6 & 9 & 0 & 3 & 6 & 9 & 0 & 3 \\ 0 & 6 & 0 & 6 & 0 & 6 & 0 & 6 & 0 & 6 & 0 & 6 & 0 & 0 \end{pmatrix}, C_O(G', V') = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 2 & 0 \\ 0 & 3 & 0 & 3 & 0 & 3 & 0 & 3 & 0 & 3 & 0 & 3 & 0 & 3 \end{pmatrix}.$$

The synchronized word is $w = (1323)^3$, see Figure 4, where $I_{12,3} = 12 = 3 \cdot I_{4,3}$.

Now, we reach the case where the generator vector $G = (g, g, g)$ is composed of three identical generators. We have:

**Theorem 3.** Let $G = (g, g, g) = g \cdot (1, 1, 1)$ where $I_{n,3} = 3g$. The seed vector $V$ that synchronizes $G$ is given by: $V = (2g, g, 0) = g \cdot (2, 1, 0)$. The orbital matrix is given by: $O(G, V) = g \begin{pmatrix} 2 & 0 & 1 \\ 1 & 2 & 0 \\ 0 & 1 & 2 \end{pmatrix}^g$. The synchronized word formed is $w = (321)^g$.

See Figure 5 for the example $G = (3, 3, 3)$, having as a seed vector $V = (6, 3, 0)$.

**Third case** – The last case to study is when the three generators are pairwise distinct. This case is covered by the Fraenkel's conjecture (see [5,14]) for $k = 3$. It states the uniqueness of synchronization for pairwise distinct generators when $g_i = 2^{i-1}, \forall i \in \{1, \dots, k\}$ that was proved for $3 \le k \le 7$. Hence, there exists a unique synchronized word on $3 \le k$ letters, with pairwise distinct generators obtained from the triplet $(1, 2, 4) \bmod 7$ which is the unique solution for this case. The orbital matrix and Christoffel conjugate matrix are given as follows:
<figure><img src="image_7.png" /><figcaption>**Fig. 5.** 2D Graphical representation of the Christoffel Word matrix for $G = (3, 3, 3)$. From left to write: the original 3 segments, the synchronized segments, and the synchronized segments after morphism.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>**Fig. 6.** 2D Graphical representation of the Christoffel Word matrix for $G = (1, 2, 4)$. From left to write: the original 3 segments, the synchronized segments, and the synchronized segments after morphism.</figcaption></figure>

$$O(G, V) = \begin{pmatrix} 3 & 4 & 5 & 6 & 0 & 1 & 2 & 3 \\ 3 & 5 & 0 & 2 & 4 & 6 & 1 & 3 \\ 3 & 0 & 4 & 1 & 5 & 2 & 6 & 3 \end{pmatrix}, C_O(G, V) = \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 & 2 & 0 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \end{pmatrix},$$

where the synchronized word is: $w = 3231323$, see Figure 6. The vertical invariant is equal to $I_{7,3} = \frac{3n-3}{2} = \frac{21-3}{2} = 9$.

In the following theorem, we give the general form of a seed vector for any generator vector having $2^i$, $\forall i \in \{0, \dots, m\}$ as generators.

**Theorem 4.** *The seed vector* $V = (\frac{I_{n,\ell}}{\ell}, \dots, \frac{I_{n,\ell}}{\ell})$, *synchronizes the generator vector* $G = (1, 2, \dots, 2^{\ell-1})$.

*Remark 1.* All the generator vectors $G'$ that are multiples of $G = (1, 2, 4)$ are also synchronized. Indeed, we can write: $O(G', V_0)[i] = d \cdot O(G, V_0)'[i]^d$, and $C_O(G', V_0)[i] = C_O(G, V_0)'[i]^d$, where $d$ is the greatest common divisor between the three pairwise distinct generators.

# 7 Conclusion and perspectives

In this paper, we present a new approach for the synchronization of three Christoffel words, related to discrete geometry. Given a generator vector $G = (g_1, g_2, g_3)$, we consider three Reveilles discrete 2D segments, of slopes $\frac{g_i}{n-g_i}$, where $n$ is the sum of all the generators. We show that the elements of the seed vector $V(v_1, v_2, v_3)$, which synchronizes the words, are specific parameters for
each of the three Reveilles discrete segments. This provides a geometric interpretation for the synchronization of three Christoffel words. Relying on this new perspective, we aim to tackle the Fraenkel's conjecture [5,14], and generalizes the study of the synchronization of *k* Christoffel words.

Python code to reproduce the result of this paper is available at:
https://github.com/lamaydt1986/Synchronization-of-Christoffel-words.

## References

1. Berstel, J., De Luca, A.: Sturmian words, Lyndon words and trees. Theoretical Computer Science 178(1), 171–203 (1997)

2. Berstel, J., Lauve, A., Reutenauer, C., Saliola, F.: Combinatorics on words: Christoffel words and repetition in words, vol. 27. CRM monograph series and American Mathematical Society (2008)

3. Christoffel, E.: Observatio arithmetica. Annali di Matematica Pura ed Applicata (1867-1897) 6(1), 148–152 (1873)

4. Debled-Rrennesson, I., Reveillès, J.P.: A linear algorithm for segmentation of digital curves. International Journal of Pattern Recognition and Artificial Intelligence 9(04), 635–662 (1995)

5. Fraenkel, A., Levitt, J., Shimshoni, M.: Characterization of the set of values $f(n)=[na]$, $n=1, 2, ...$. Discrete Mathematics 2(4), 335–345 (1972)

6. Freeman, H.: On the encoding of arbitrary geometric configurations. IRE Transactions on Electronic Computers 2, 260–268 (1961)

7. Labbé, S.: Structure des pavages, droites discrètes 3D et combinatoire des mots. Ph.D. thesis, Université du Québec à Montréal and Université Paris Diderot (2012)

8. Lothaire, M.: Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 90. Cambridge University Press, Cambridge (2002)

9. Morikawa, R.: Disjoint sequences generated by the bracket function. Bull. Faculty of Liberal Arts, Nagasaki Univ., (Natural Science 26(1), 1–13 (1985))

10. Paquin, G., Reutenauer, C.: On the superimposition of Christoffel words. Theoretical Computer Science 412(4), 402–418 (2011)

11. Provençal, X., Vuillon, L.: Discrete segments of $Z^3$ constructed by synchronization of words. Discrete Applied Mathematics (2014)

12. Reveillès, J.P.: Géométrie discrete, calcul en nombres entiers et algorithmique. Ph.D. thesis, Université Louis Pasteur (1991)

13. Simpson, J.: Disjoint Beatty sequences. Integers: Electronic Journal of Combinatorial Number Theory 4(A12), A12 (2004)

14. Tijdeman, R.: Exact covers of balanced sequences and Fraenkel's conjecture. In: Algebraic number theory and Diophantine analysis (Graz, 1998), pp. 467–483. de Gruyter, Berlin (2000)
# 8 Appendix

**Lemma.** For all $G = (g_1, g_2)$ and $n = g_1 + g_2$, we have $I_{n,2} = n - d$, where $d = \gcd(g_1, g_2)$.

*Proof.* Let $(g_1, g_2) \bmod n$ where $n = g_1 + g_2$ with $d = \gcd(g_i, n)$ $\forall i \in \{1, 2\}$, we get:

$$I_{n,2} = \frac{k \cdot n}{2} - \frac{1}{2} \left( \sum_{i=1}^{2} \gcd(n, g_i) \right) = \frac{2n}{2} - \frac{1}{2} (d + d) = n - d.$$

□

**Proposition.** [Repeat from Prop. 2] Let $w$ be a Christoffel word of slope $\frac{a}{b}$, where $a \perp b$. We let $w'$ be a conjugate of $w$ such that $O(w')$ starts from the label $p$. We set $\alpha$ as $\alpha a \equiv -1 \bmod n$ and we have:

$$P(a, b, p) = \{(i\alpha + x) \bmod n \mid i = 1 \dots a\}, \text{ where } xa \equiv -p \bmod n.$$

*Proof.* From [10, Corollary 3.2], see also [9,13], we know that the set of positions for the letters 0 in a Christoffel word of slope $\frac{b}{a}$, where $a \perp b$ and starting from the label $n-1$ of its orbit is: $C(n, b, n-1) = \{i\alpha' + x; i = 0, \dots, n-b-1\}; n-b \cdot \alpha' \equiv -1 \bmod n$ and $x \cdot b \equiv -(n-1) \bmod n$. By the definition of the construction of the Christoffel word $w'$ of slope $\frac{a}{b}$ [2,8], we know that if the $O(w')$ starts at 0, the positions of the letters 1 are the same as the positions of the letter 0 for $w$ if its orbit starts at $n-1$. Therefore $P(a, b, 0) = C(n, b, n-1) = \{i\alpha' + x; i = 0, \dots, a-1\}; a \cdot \alpha' \equiv -1 \bmod n$ and $x = 0$. In fact, $x$ is exactly the number of shifts needed to start from the label $n-1$. For that, to generalize the set for any label $p$ of the orbit of $w'$, we get: $P(a, b, p) = C(n, b, n-1) = \{i\alpha' + x; i = 0, \dots, a-1\}; a \cdot \alpha' \equiv -1 \bmod n$ and $x \cdot b \equiv -p \bmod n$. The step $x$ that must be used to start from label $p$ instead of 0 is calculated as follows:

$$\begin{aligned} p + x \cdot a &\equiv 0 \bmod n \\ xa &\equiv -p \bmod n \end{aligned}$$

□

**Proposition.** [Repeat from Prop. 4] Let $G = (g, g, g_3)$ be a generator vector with $n = 2g + g_3$.

1. $n$ is an odd number $\iff \gcd(n, g) = \gcd(n, g_3) = 1$.

2. $n$ is an even number $\iff \gcd(n, g) = 1$ and $\gcd(n, g_3) = 2$.

*Proof.* For all $n$, since $g \perp g_3$, then by the Euclidean Algorithm, we have $\gcd(n, g) = \gcd(g, g_3) = 1$.

1. “ $\iff$ ” For $G = (g, g, g_3)$ and $n = 2g + g_3$, we can write $n = 2k$ if $n$ is an even number, then $g$ and $g_3$ are odd numbers since they are relatively prime with $n$. Therefore, as $2g$ is even and $g_3$ is odd, the sum should be odd. Contradiction.
“ $\implies$ ” Let $d = \gcd(n; g_3)$, then $d|n$ and $d|g_3$, hence $d|2g$. Since $n$ is odd, and $n = 2g + g_3$, we have that $g_3$ is odd and $d|g_3$, so we get $d$ odd.
$d|2g$ then $\exists k \in \mathbb{N}; 2g = kd$. Since $2g$ is even and $d$ is odd, then $k$ is even, and we can write $g = \frac{k}{2}d$, hence $d|g$. Now $d|g; d|n$ and $\gcd(n, g) = 1$ therefore $d = 1$.

2. “ $\Leftarrow$ ” $2g$ even and $\gcd(n, g_3) = 2$ then $2|n$ and $n$ is even.
“ $\implies$ ” Since $n$ is even and $n = 2g + g_3$ then $g_3$ is even.
Since $g_3$ is even and $n$ is even, hence $2|g_3$ and $2|n$.
Let $d \neq 1$ be another divisor of $g_3$ and $n$; $d|g_3$ and $d|n$, hence $d|2g$.
If $d \nmid 2$ then $d|g$, contradiction, since $\gcd(n, g) = 1$.
Therefore, $d|2$, this means $d = 2$ or $d = 1$ and since by hypothesis, $d \neq 1$ then certainly $d = 2$.

□

**Lemma.** [*Repeat from Lemma. 2*] Let $G = (g, g, g_3)$ be a generator vector with $n = 2g + g_3$.

1. If $n$ is an odd number then $I_{n,3} = \frac{3}{2}(n-1)$.

2. If $n$ is an even number then $I_{n,3} = \frac{3}{2}n - 2 = \frac{3n-4}{2}$.

*Proof.* 1. Since $n$ is an odd number then $\gcd(n, g) = \gcd(n, g_3) = 1$

$$I_{n,3} = \frac{3 \cdot n}{2} - \frac{1}{2} \left( \sum_{i=1}^{3} \gcd(n, g_i) \right) = \frac{3n}{2} - \frac{1}{2} \left( \sum_{i=1}^{3} 1 \right) = \frac{3n}{2} - \frac{3}{2} = \frac{3}{2}(n-1).$$

2. Since $n$ is even, then $\gcd(n, g) = 1$ and $\gcd(n, g_3) = 2$.

$$I_{n,3} = \frac{3 \cdot n}{2} - \frac{1}{2} \left( \sum_{i=1}^{3} \gcd(n, g_i) \right) = \frac{3n}{2} - \frac{1}{2} (1 + 1 + 2) = \frac{3n-4}{2} = \frac{3}{2}n - 2.$$

□

Let $G = (g, g, g_3)$ be a generator vector where $n = 2g + g_3$ and $\gcd(g, g_3) = d$. We have $g = d \cdot g', g_3 = d \cdot g'_3$ and $n = d \cdot n'$. We clearly can see that: $O(G, V_0)[i] = d \cdot O(G, V_0)'[i]^d$ and $C_O(G, V_0)[i] = C_O(G, V_0)'[i]^d$, where $O(G, V_0)'$ and $C_O(G, V_0)'$ corresponds to the generator vector $G' = (g', g', g'_3)$.

*Proof.* Let the triplet $G' = (g', g', g'_3)$ mod $n'$ such that $n' = 2g' + g'_3$ and the triplet $G = (g, g, g_3)$ mod $n$ such that $n = 2g + g_3$ where $g = g'.d$; $g_3 = g'_3.d$, $n = n'.d$.

Hence, the orbits of the Christoffel words of slopes $\frac{g'}{n'-g'}$ and $\frac{g'_3}{n'-g'_3}$ in $\mathbb{Z}/n'\mathbb{Z}$ are:

$$g' : 0 \to g' \to 2g' \to \dots \to (n' - 1)g' \to 0$$

$$g'_3 : 0 \to g'_3 \to 2g'_3 \to \dots \to (n' - 1)g'_3 \to 0.$$

By multiplying by $d$, we get:
$$
\begin{align*}
d.g' : 0 \to g'.d \to 2g'.d \to \dots \to (n' - 1)g'.d \to 0 \\
d.g'_3 : 0 \to g'_3.d \to 2g'_3.d \to \dots \to (n' - 1)g'_3.d \to 0
\end{align*}
$$
$$
\begin{align*}
g : 0 \to g \to 2g \to \dots \to (n-1)g \to 0 \\
g : 0 \to g \to 2g \to \dots \to (n-1)g \to 0 \\
g_3 : 0 \to g_3 \to 2g_3 \to \dots \to (n-1)g_3 \to 0,
\end{align*}
$$

and since we multiplied by $d$ so we are now working in $\mathbb{Z}/n\mathbb{Z}$ so each row must be
of length $n$ which means to repeat each row $d$ times to reach the length $n$. Hence,
we have: $O(w) = d \cdot O(w')^d$ and we can write $O(G, V_0)[i] = d \cdot O(G, V_0)'[i]^d$ and
$C_O(G, V_0)[i] = C_O(G, V_0)'[i]^d$. $\square$

**Theorem.** [*Repeat from Th. 3*] Let $G = (g, g, g) = g \cdot (1, 1, 1)$ where $I_{n,3} = 3g$.
The seed vector $V$ that synchronizes $G$ is given by: $V = (2g, g, 0) = g \cdot (2, 1, 0)$.
The orbital matrix is given by: $O(G, V) = g \begin{pmatrix} 2 & 0 & 1 \\ 1 & 2 & 0 \\ 0 & 1 & 2 \end{pmatrix}^g$. The synchronized word
formed is $w = (321)^g$.

Proof. For equal generators, we have $G = (g, g, g) \bmod 3g$. Since $g$ is a unique generator, we remark that by factoring with $g$, we get: $G = g$ (012). Hence, it is sufficient to synchronize the generator vector $G' = (1, 1, 1)$ then to apply $O(G, V_0)[i] = d \cdot O(G, V_0)'[i]^d$ and $C_O(G, V_0)[i] = C_O(G, V_0)'[i]^d$. To accomplish the synchronization, we do a $k-1$ circular permutation $\forall k \in \{1, 2, 3\}$,
hence we get: $O(G, V_0) = g \begin{pmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \\ 2 & 0 & 1 \end{pmatrix}^g$ and the word formed is: $(321)^g$. Since
the synchronization matrix is of the form $V = g \begin{pmatrix} 0 & 1 & 2 \\ 1 & 2 & 0 \\ 2 & 0 & 1 \end{pmatrix}^g$, then the seed in
this case has always the form: $S = \begin{pmatrix} 0 \\ g \\ 2g \end{pmatrix}$. Since $I_{n,3}$ is the vertical sum of the
elements of each column so in particular we can get the value from the seed,
hence $I_{n,3} = 0 + g + 2g = 3g$. Or simply by computing:

$$
I_{n,3} = \frac{k \cdot n}{2} - \frac{1}{2} \left( \sum_{i=1}^{3} \gcd(n, g_i) \right) = \frac{9g}{2} - \frac{1}{2} (g + g + g) = \frac{6g}{2} = 3g.
$$

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

**Theorem.** [*Repeat from Th. 2*] Let $G = (g, g, g_3)$ be a generator vector such that $n = 2g + g_3$, and $g \perp g_3$. The seed vector $V$ which synchronizes $G$ is:

1. If $n$ is odd, the seed vector is: $V = (n - 1, \frac{n-1}{2}, 0)$.

2. If $n$ is even, the seed vector is: $V = (n - 1, \frac{n-2}{2}, 0)$.

In both cases, the seed element 0 is always dedicated to the distinct generator.
Proof. 1. Let $G = (g, g, g_3)$ be a generator vector such that $n = 2g + g_3$, and $g \perp g_3$. The two Christoffel words, $w_1, w_2$, obtained are of slopes: $\frac{g}{n-g}$ and $\frac{g_3}{n-g_3}$. Since $n$ is odd, then we have $\gcd(g, n) = \gcd(g_3, n) = 1$. To show that the seed vector $V = (n-1, \frac{n-1}{2}, 0)$ synchronizes $G$, we define the three sets $A, B, C$ to be the sets of positions for the letters 1 for two conjugates of $w_1$, and for $w_2$, respectively. The orbits of the conjugate words of $w_1$ start with the labels $n-1$, and $\frac{n-1}{2}$, respectively. Hence, we have:

$$A = P(g, n - g, n - 1) = \{i\alpha + x; i = 1 \dots g\}$$

$$B = P(g, n - g, \frac{n-1}{2}) = \{i\alpha + y; i = 1 \dots g\}$$

$$C = P(g_3, n - g_3, 0) = \{i\beta; i = 1 \dots g_3\},$$

where: $\alpha g \equiv -1 \mod n$; $\beta g_3 \equiv -1 \mod n$ and $xg \equiv 1 \mod n$ and $2yg \equiv 1 \mod n$ since $gy \equiv -\frac{n-1}{2} \mod n$.

We need to prove that the sets $A, B, C$ are pairwise disjoint, hence we can not get any two decreasing positions on the same column.

$$A \cap B = \emptyset$$

Let $a \in A, b \in B$, we have $a := i\alpha + x$ and $b := j\alpha + y$ for some $i \in \{1 \dots g\}$ and $j \in \{1 \dots g\}$

By contradiction, suppose $a - b \equiv 0$, then:

$$(i - j)\alpha + x - y \equiv 0 \mod n$$

$$2(i - j)g\alpha \equiv 2yg - 2gx \mod n$$

$$2(i - j) \equiv 1 \mod n.$$

Hence $2(i - j) = ln + 1; \ell \in \mathbb{Z}$. This leads to a contradiction since we know that: $i - j \in \{1 - g, \dots, g - 1\}$, If

$$- \ell = 0; 2(i - j) = 1 \text{ contradiction.}$$

$$- \ell > 0; 2(i - j) > n + 1 \text{ contradiction.}$$

$$- \ell < 0; 2(i - j) < -n + 1 \text{ contradiction.}$$

therefore $A \cap B = \emptyset$.

$$A \cap C = \emptyset$$

We let $a \in A$ and $c \in C$; $a := i\alpha + x$ and $c := k\beta$, for some $i \in \{1, \dots, g\}$ and $k \in \{1, \dots, g_3\}$.

By contradiction, suppose $a - c \equiv 0 \mod n$ then:

$$i\alpha + x - k\beta \equiv 0 \mod n$$

$$i\alpha g + xg - k\beta(\frac{n-g_3}{2}) \equiv 0 \mod n$$

$$-id + d - \frac{k\beta n}{2} - \frac{k}{2} \equiv 0 \mod n$$

$$-2i + 2 - k\beta n - k \equiv 0 \mod n$$

$$-2i + 2 - k \equiv 0 \mod n$$

$$2(1 - i) - k \equiv 0 \mod n,$$
this result leads to a contradiction since:

$$ 
\begin{array}{l}
1 \le i \le g \\
1 - g \le (1-i) \le 0 \quad \text{and} \quad -g_3 \le -k \le -1 \\
2 - 2g \le 2(1-i) \le 0.
\end{array}
$$

By adding both inequalities, we get: $-n < 2 - n \le 2(1 - i) - k \le -1 < 0$. Therefore the two sets A and C are disjoint.

### $B \cap C = \emptyset$:

We let $b \in B$ and $c \in C$; $b := i\alpha + y$ and $c := k\beta$, for some $i = 1...g$ and $k = 1...g_3$.

By contradiction, suppose $b - c \equiv 0 \mod n$ then:

$$ 
\begin{align*}
i\alpha + y - k\beta &\equiv 0 \mod n \\
i\alpha g + yg - k\beta\left(\frac{n-g_3}{2}\right) &\equiv 0 \mod n \\
2i\alpha g + 2yg - k\beta n + k\beta g_3 &\equiv 0 \mod n \\
-2i + 1 - k\beta n - k &\equiv 0 \mod n \\
-2i + (1-k) &\equiv 0 \mod n,
\end{align*}
$$

this result leads to a contradiction since:

$$ 
\begin{array}{l}
1 \le i \le g \\
-2g \le -2i \le -2 \quad \text{and} \quad 1 - g_3 \le (1-k) \le 0.
\end{array}
$$

By adding both inequalities, we get: $-n < d - n \le -2id + d(1-k) \le -2d < 0$. Therefore B and C are disjoint.

2. When $n$ is an even number, we have: $\text{gcd}(g, n) = 1$ and $\text{gcd}(g_3, n) = 2$. The sets A, B, C become:

$$ 
\begin{align*}
A &= P(g, n-g, n-1) = \{i\alpha + x; i = 1, \dots, g\} \\
B &= P(g, n-g, \frac{n-2}{2}) = \{i\alpha + y; i = 1, \dots, g\} \\
C &= P(g_3, n-g_3, 0) = C_0 \cup C_1,
\end{align*}
$$

where $C_0 = \{i\beta\}$ and $C_1 = \{i\beta + \frac{n}{2}\}$; $i = 1, \dots, \frac{g_3}{2}$, $\alpha.g \equiv -1 \mod n$, $\beta.g_3 \equiv -2 \mod n$ and $x.g \equiv 1 \mod n$, $y.g \equiv 1 + m \mod n$ where $n = 2m$, since:

$$ 
\begin{align*}
y.g &\equiv -\frac{n-2}{2} \mod n \\
y.g &\equiv -\frac{2m-2}{2} \mod n \\
y.g &\equiv 1-m \mod n \\
y.g &\equiv 1+m \mod n \quad (\text{since, } n-m=m)
\end{align*}
$$

Now, we prove that three sets are pairwise distinct starting with A and B:
$A \cap B = \emptyset:$

Let $a \in A, b \in B$, they are defined as: $a := i\alpha + x$ and $b := j\alpha + y$ where $i, j \in \{1, \dots, g\}$

By contradiction, suppose $a - b \equiv 0 \mod n$ then:

$$i\alpha + x - j\alpha - y \equiv 0 \mod n$$

$$i\alpha.g + x.g - j\alpha.g - y.g \equiv 0 \mod n$$

$$-i + 1 + j - 1 - m \equiv 0 \mod n$$

$$(j - i) - m \equiv 0 \mod n.$$

This congruence leads to a contradiction since:

$$1 - g \le (j - i) \le g - 1$$

$$1 - g - m \le (j - i) - m \le g - 1 - m$$

$$-n < 1 - g - m \le (j - i) - m \le g - 1 - m < 0,$$

knowing that $m = \frac{n}{2} > g$. Hence $A \cap B = \emptyset$.

$A \cap C = \emptyset:$

In this part, we divide our work into two parts since C is a union of two sets and we prove that A is disjoint with both subsets of C. We let $a \in A, c_j \in C_j \forall j \in \{0, 1\}$, they are defined as: $a := i\alpha + x$ and $c_0 := j\beta, c_1 = j\beta + \frac{n}{2}$ where $i \in \{1, \dots, g\}, j \in \{1, \dots, \frac{g_3}{2}\}$

By contradiction, suppose $a - c_j \equiv 0 \mod n$ then:

$$a - c_0 \equiv 0 \mod n$$

$$i\alpha + x - j\beta \equiv 0 \mod n$$

$$i\alpha.g + x.g - j\beta \cdot \frac{n - g_3}{2} \equiv 0 \mod n$$

$$2i\alpha.g + 2x.g - j\beta.n + j\beta.g_3 \equiv 0 \mod n$$

$$-2i + 2 - 2jd \equiv 0 \mod n$$

$$2 - 2(i + j) \equiv 0 \mod n.$$

For $c_1$ we get:

$$a - c_1 \equiv 0 \mod n$$

$$i\alpha + x - j\beta - \frac{n}{2} \equiv 0 \mod n$$

$$i\alpha.g + x.g - j\beta \cdot \frac{n - g_3}{2} - \frac{n}{2} \cdot g \equiv 0 \mod n$$

$$2i\alpha.g + 2x.g - j\beta.n + j\beta.g_3 - ng \equiv 0 \mod n$$

$$-2i + 2 - 2j \equiv 0 \mod n$$

$$2 - 2(i + j) \equiv 0 \mod n.$$
These two congruences lead to a contradiction:

$$ 
\begin{array}{l}
2 \le (i+j) \le g + \frac{g_3}{2} \\
4d \le 2(i+j) \le n \\
-n < 2-n \le 2-2(i+j) \le -2 < 0
\end{array}
$$

Hence $A \cap C = \emptyset$.

$B \cap C = \emptyset:$

Finally for $B$ and $C$, we will repeat the same work by letting $b \in B$ and $c_j \in C_j \forall j \in \{0, 1\}$, they are defined as: $b := i\alpha + y$ and $c_0 := j\beta, c_1 = j\beta + \frac{n}{2}$ where $i \in \{1, \dots, g\}, j \in \{1, \dots, \frac{g_3}{2}\}$.

By contradiction, suppose $b - c_j \equiv 0 \mod n$ then:

$$ 
\begin{array}{l}
b - c_0 \equiv 0 \mod n \\
i\alpha + y - j\beta \equiv 0 \mod n \\
i\alpha.g + y.g - j\beta \cdot \frac{n-g_3}{2} \equiv 0 \mod n \\
2i\alpha.g + 2y.g - j\beta.n + j\beta.g_3 \equiv 0 \mod n \\
-2i + 2(1+m) - 2j \equiv 0 \mod n \\
-2i + 2 + 2m - 2jd \equiv 0 \mod n \\
2 - 2(i+j) \equiv 0 \mod n. \quad (\text{since } 2m = n)
\end{array}
$$

For $c_1$ we get:

$$ 
\begin{array}{l}
b - c_1 \equiv 0 \mod n \\
i\alpha + y - j\beta - \frac{n}{2} \equiv 0 \mod n \\
i\alpha.g + y.g - j\beta \cdot \frac{n-g_3}{2} - \frac{n}{2} \cdot g \equiv 0 \mod n \\
2i\alpha.g + 2y.g - j\beta.n + j\beta.g_3 - ng \equiv 0 \mod n \\
-2i + 2(1+m) - 2j \equiv 0 \mod n \\
-2i + 2 + 2m - 2j \equiv 0 \mod n \\
2 - 2(i+j) \equiv 0 \mod n. \quad (\text{since } 2m = n)
\end{array}
$$

These two equivalences are the same as the previous case hence we get a contradiction too and the sets $B$ and $C$ are disjoint.

□

**Theorem.** [Repeat from Th. 4] The seed vector $V = (\frac{I_{n,\ell}}{\ell}, \dots, \frac{I_{n,\ell}}{\ell})$, synchronizes the generator vector $G = (1, 2, \dots, 2^{\ell-1})$.

*Proof.* Let $G$ be the sequence of generators of the form $2^i, \forall i \in \{0, \dots, m\}$ and $n = 2^{m+1} - 1$ their sum.
We define the sets A and B of decreasing position for the two generators: $g_\ell = 2^\ell$ and $g_s = 2^s$ where $\ell < s \le m$. The labels, $v_i$, of the orbits of the conjugate Christoffel words are equal to $\frac{I_{n,m+1}}{m+1}$ and respect all the conditions given in the previous sections by the following:

We know that: $I_{n,m+1} = \frac{(m+1)n}{2} - \frac{1}{2}(m+1) = \frac{(m+1)(n-1)}{2}$ hence:

$$v_i = \frac{I_{n,m+1}}{m+1} = \frac{n-1}{2} \quad \forall i \in \{0, \dots, m\} \quad \text{where} \quad \frac{n-1}{2} = 2^m - 1.$$

$$A = \{i\alpha + x; i = 1 \dots 2^\ell\}$$

$$B = \{j\beta + y; j = 1 \dots 2^s\},$$

where: $\alpha 2^\ell \equiv -1 \mod n$; $\beta 2^s \equiv -1 \mod n$ and $x.2^\ell \equiv 1 - 2^m \mod n$ and $y.2^s \equiv 1 - 2^m \mod n$. We need to prove that the sets A, B are disjoint, hence we can't get any two letters on the same column.

$$A \cap B = \emptyset$$

Let $a \in A, b \in B$ we have $a := i\alpha + x$ and $b := j\beta + y$ for some $i \in \{1 \dots 2^\ell\}$ and $j \in \{1 \dots 2^s\}$

By contradiction, suppose $a - b \equiv 0$ then:

$$i\alpha + x - j\beta - y \equiv 0 \mod n$$

$$2^s i\alpha + 2^s x - 2^s j\beta - 2^s y \equiv 0 \mod n$$

$$-2^{s-\ell}i + 2^{s-\ell}(1 - 2^m) + j - 1 + 2^m \equiv 0 \mod n$$

$$-2^{s-\ell}i + 2^{s-\ell} - 2^{m+s-\ell} + j - 1 + 2^m \equiv 0 \mod n$$

$$2^{s-\ell}(1-i) - 2^{m+s-\ell} + j - 1 + 2^m \equiv 0 \mod n,$$

where:

$$\begin{gathered} 1 \le i \le 2^\ell \\ 2^{s-\ell} - 2^s \le 2^{s-\ell}(1-i) \le 0 \quad \text{and} \quad 0 \le j-1 \le 2^s - 1. \end{gathered}$$

By adding both inequalities with the constant term in $a-b$ we get:

$$2^m - 2^{m+s-\ell} - 2^s + 2^{s-\ell} \le a - b \le 2^s - 1 + 2^m - 2^{m+s-\ell}.$$

Let P, and Q be the lower and upper bounds of $a-b$ respectively. Our aim is to reach a contradiction by bounding the two terms A and B of this inequality by two consecutive multiples of n and hence the term $a-b$ who is bounded by $P \le a-b \le Q$ can't be null.

The power $m+s-\ell$ is the highest power in the two terms of P and Q, $m+1$ is the power found in n. We let $p = (m+s-\ell) - (m+1) = s-\ell-1$ and $k = 2^p$, we will prove that: $-k.n < P \le a-b \le Q < (-k+1).n$
First, $-k.n = -2^{s-\ell-1} \cdot (2^{m+1} - 1) = -2^{m+s-\ell} + 2^{s-\ell-1}$, then $-k.n < P$ will give us the following:

$$ 
\begin{aligned}
& -2^{m+s-\ell} + 2^{s-\ell-1} < 2^m - 2^{m+s-\ell} - 2^s + 2^{s-\ell} \\
& 2^{s-\ell-1} - 2^m + 2^s - 2^{s-\ell} < 0 \\
& 2^{s-\ell}(2^{-1} - 1) - 2^m + 2^s < 0 \\
& -2^{s-\ell-1} - 2^m + 2^s < 0.
\end{aligned}
$$

This is always true since $l < s \le m$.

Now, we prove that $Q < (-k+1).n$ by calculating at the beginning the value of $(-k+1).n$, we get the following:

$$ (-k+1).n = (-2^{s-\ell-1} + 1)(2^{m+1} - 1) = -2^{s-\ell+m} + 2^{s-\ell-1} + 2^{m+1} - 1 \text{ then,} $$

$$ 
\begin{aligned}
& -2^{s-\ell+m} + 2^{s-\ell-1} + 2^{m+1} - 1 > 2^s - 1 + 2^m - 2^{m+s-\ell} \\
& 2^{s-\ell-1} + 2^{m+1} - 2^s - 2^m > 0 \\
& 2^{s-\ell-1} - 2^s + 2^m > 0,
\end{aligned}
$$

which is always true since:

$$ 
\begin{aligned}
& 2^\ell < 2^s \le 2^m \\
& -2^m \le -2^s < -2^\ell \quad \text{and} \quad 2^0 \le 2^{s-\ell-1} < 2^m,
\end{aligned}
$$

by adding these two inequalities we get: $1 - 2^m \le 2^{s-\ell-1} - 2^s < 2^m - 2^\ell < 2^m$ which confirms the positivity of $2^{s-\ell-1} - 2^s + 2^m$.

Hence, a contradiction, and the term $a-b$ can not be equivalent to $0 \mod n$.

□