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

HAL
open science

# About Δ-numeration

Bastien Laboureix, Eric Domenjoud

► To cite this version:

Bastien Laboureix, Eric Domenjoud. About Δ-numeration. WORDS 2025, Guilhem Gamard, Jun 2025, Nancy, France. hal-05071820

HAL Id: hal-05071820

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

Submitted on 17 May 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.

Public Domain
# About $\Delta$-numeration

Bastien Laboureix¹ and Eric Domenjoud²

¹ Centre Borelli, ENS Paris-Saclay, Université Paris-Saclay
bastien.laboureix@ens-paris-saclay.fr

² Université de Lorraine, CNRS, LORIA, 54000 Nancy, France
eric.domenjoud@loria.fr

**Abstract.** In this article we study a numeration system previously used to prove combinatorial properties in discrete geometry: the $\Delta$-numeration. Since this system, introduced via the fully subtractive algorithm, has been seen mainly as a tool, we propose here to study it from the point of view of numeration systems. In particular, we make the link with $\beta$-numeration and Cantor real bases. We reintroduce the rewriting system introduced to calculate in $\Delta$-numeration. This systems is based on the properties of the fully subtractive algorithm and is normalising. Finally, we study the ultimately periodic case, a special case of alternate bases, and show that the ultimately periodic words represent exactly the elements of $\mathbb{Q}[\beta]$ where $\beta$ is the inverse of a Pisot number.

**Keywords:** numeration systems · normalising rewriting system · fully subtractive algorithm · ultimately periodic words · real Cantor bases.

## 1 Introduction

The first real base numeration systems were introduced in the middle of the 20th century by A. Rényi in [12]. The idea was to generalise the well-known notions of whole-base numeration, for any real number $\beta > 1$. A number $x \in [0, 1]$ is represented by $\sum_{n=1}^{\infty} \frac{w_n}{\beta^n}$ where $w$ is an infinite word over the alphabet $[0, \lceil \beta \rceil - 1]$. Since then, many numeration systems have been studied, from the point of view of word combinatorics, symbolic dynamics or rewriting. We refer the reader to [13] for an overview of the various definitions and usual properties in the field.

In 2021 and 2023, E. Charlier and C. Cisternino introduced Cantor real bases and alternate bases in [5] and [4]. Given a sequence $(\beta_n)_{n \in \mathbb{N}^*}$, the word $w \in \mathbb{N}^\omega$ represents, under the hypothesis of convergence of the series, the real number
$$x = \sum_{n=1}^{\infty} (w_n / \prod_{k=1}^{n} \beta_k).$$

In parallel and in a completely different field, E. Domenjoud, X. Provençal and L. Vuillon introduced in 2015 the foundations of a system that they called $\Delta$-numeration [8]. This system was initially created with the aim of studying the structure of certain arithmetic hyperplanes in discrete geometry, by expressing them as a palindromic closure linked to this system. In 2019, in [6], a further study of this numeration system made it possible to define rewriting operations
on it with the aim of obtaining a convergent rewriting system and to deduce
properties on the facet connectedness of arithmetic hyperplanes. However, the
main aim of the paper in question was to prove properties of discrete geometry,
using numeration bases as a simple tool to achieve this goal.

In this article, we propose to study the properties of this numeration sys-
tem for itself. After recalling the general principle of Δ-numeration, we show in
particular that it is a special case of Cantor real bases studied a few years later
by E. Charlier and characterise the differences between these two numeration
systems. In particular, we look at the expansion/reduction rewriting system in
Δ-numeration and recall that it converges. Finally, we study the ultimately pe-
riodic case, which is close to E. Charlier’s alternate bases. Most of the results
obtained are presented in the last chapter of B. Laboureix’s PhD thesis [11].

## 2 Fully Subtractive Algorithm

We begin by presenting the fully subtractive algorithm introduced by F. Schweiger in [15]. This is a subtractive Euclidean algorithm in dimension $d \ge 2$ very strongly related to continued fractions. Since we are primarily interested in the dynamics of this algorithm, the version we present has no output and does not terminate. To simplify matters, we present a version that loops as soon as the vector under consideration contains a zero coordinate, which differs from Euclid's algorithm. The algorithm constructs an infinite word $\Delta = (\delta_n)_{n \in \mathbb{N}^*}$ over the alphabet $[1, d]$, a decreasing real sequence $(\theta_n)_{n \in \mathbb{N}^*}$ and a sequence $(v^{(n)})_{n \in \mathbb{N}^*}$ of vectors of $\mathbb{R}^d$. The sequence $\theta$ allows us to define the $\Delta$-numeration and we show that, in the framework we are interested in, the knowledge of $\Delta$ and $\theta$ are equivalent.

**Algorithm:** Fully subtractive algorithm [15]

**Input:** $v$ a non negative vector of $\mathbb{R}^d$

**Output:** constructs an infinite word $\Delta$ and an infinite sequence $\theta$

$n \leftarrow 0;$

while TRUE do

$n \leftarrow n + 1;$

$i \leftarrow$ index of the minimum coordinate of $v$ (in the event of non-uniqueness, the smallest possible value of $i$ is taken);

$\delta_n \leftarrow i;$

$\theta_n \leftarrow v_i;$

$v^{(n)} \leftarrow v;$

$v \leftarrow v - v_i (1 - e_i)$ where $1 \stackrel{\text{def}}{=} (1, \dots, 1);$

end

The dynamics of the fully subtractive algorithm were studied in a completely
different context by C. Kraaikamp and R. Meester in [10] who were interested
in a percolation model. Since the fully subtractive algorithm had not yet been
defined at the time of their research, we take the liberty of describing their
results using the notations and definitions previously introduced. Their study
<table><caption>**Table 1.** Fully subtractive algorithm for the example (17, 7, 19).</caption><thead><tr><th><i>v</i><sup>(<i>n</i>)</sup></th><th>δ<sub><i>n</i></sub></th><th>θ<sub><i>n</i></sub></th></tr></thead><tbody><tr><td>(17,7,19)</td><td>2</td><td>7</td></tr><tr><td>(10,7,12)</td><td>2</td><td>7</td></tr><tr><td>(3,7,5)</td><td>1</td><td>3</td></tr><tr><td>(3,4,2)</td><td>3</td><td>2</td></tr><tr><td>(1,2,2)</td><td>1</td><td>1</td></tr><tr><td>(1,1,1)</td><td>1</td><td>1</td></tr><tr><td>(1,0,0)</td><td>2</td><td>0</td></tr><tr><td>(1,0,0)</td><td>2</td><td>0</td></tr><tr><td>(1,0,0)</td><td>2</td><td>0</td></tr><tr><td>⋮</td><td>⋮</td><td>⋮</td></tr></tbody></table>

focused in particular on the case where the sequence $(v^{(n)})_{n \in \mathbb{N}^*}$ converges to 0. They characterise this by looking at whether the vector is balanced or not, in the sense given by the Theorem 2.2 below.

**Definition 2.1 (Totally irrational vector)** A vector $v$ is said to be totally irrational iff its coordinates form a free family on $\mathbb{Q}$.

**Theorem 2.2 (Kraaikamp-Meester [10, Theorem 2], [7, Lemma 11])** Let $v$ be a totally irrational vector. The following propositions are equivalent:

1. $\lim_{n \to +\infty} v^{(n)} = 0$;

2. $\forall n \in \mathbb{N}^*, \|v^{(n)}\|_1 \ge (d-1) \|v^{(n)}\|_{\infty}$;

3. each letter in $\llbracket 1, d \rrbracket$ appears infinitely many times in $\Delta$.

*Proof.* The equivalence between (1) and (2) is Theorem 2 in [10]. The implication (1) ⇒ (3) is Lemma 11 in [7]. For (3) ⇒ (1), consider a vector $v$ such that each letter in $\llbracket 1, d \rrbracket$ appears infinitely many times in $\Delta$. Since $(v^{(n)})_{n \in \mathbb{N}}$ is a positive decreasing sequence, it converges to a vector $u \ge 0$. Let us assume by contradiction that there exists $i \in \llbracket 1, d \rrbracket$ such that $u_i > 0$ and let $A \stackrel{\text{def}}{=} \{n \in \mathbb{N}^* | \delta_n = i\}$. Since $A$ is infinite, $A = \{f(m)\}_{m \in \mathbb{N}}$ where $f$ is a strictly increasing function. Let $j \ne i$. We have

$$v_j^{f(m+1)} \le v_j^{f(m)+1} = v_j^{f(m)} - v_i^{f(m)} \le v_j^{f(m)} - u_i.$$

By an immediate induction, we deduce $\forall m \in \mathbb{N}, v_j^{f(m)} \le v_j^{(f(0))} - m u_i$, which contradicts the positivity of $(v^{(n)})_{n \in \mathbb{N}}$. Hence $u = 0$, which is exactly (1). □

**Definition 2.3 (Kraaikamp-Meester set [10])** A vector $v \in \mathbb{R}^d$ is said to be Kraaikamp-Meester iff $v$ is totally irrational and the fully subtractive algorithm on $v$ generates a sequence $(v^{(n)})_{n \in \mathbb{N}^*}$ of vectors of $\mathbb{R}^d$ such that $\lim_{n \to +\infty} v^{(n)} = 0$. Let $K_d$ be the set of $d$-dimensional Kraaikamp-Meester vectors.
The set $\mathcal{K}_2$ consists exactly of the vectors $(a, b) \in \mathbb{R}^{*2}$ where $\frac{a}{b}$ is irrational and C. Kraaikamp and R. Meester have shown that $\mathcal{K}_d$ is Lebesgue-negligible for all $d \ge 3$. We give in Figure 1 a normalised and projected representation of $\mathcal{K}_3$ which is isometric to the Rauzy gasket studied in [1].

<figure><img src="image_2.png" /><figcaption>Fig. 1. A normalised representation of the set $\mathcal{K}_3$. On the left, the coloured triangles represent the 3 zones corresponding to the 3 possible values of $\delta_1$. The figure on the right shows the first triangles $T_k$ used to build a vector $v$ associated with a word $\Delta = 12123...$.</figcaption></figure>

The characterisation of the vectors in $\mathcal{K}_d$ makes it easy to establish a link between the vector $v$ and the sequence $\Delta$. Given $v \in \mathcal{K}_d$, by Theorem 2.2, the infinite word $\Delta$ associated with $v$ contains infinitely many occurrences of each letter in $[1, d]$. Conversely, any $\Delta$ with infinitely many occurrences of each letter comes from a single vector $v \in \mathcal{K}_d$, up to a multiplicative factor. Moreover, this single vector $v$ can be calculated from $\Delta$. To do this, let us call $T$ the set $\{v \in \mathbb{R}^d \mid v \ge 0, \|v\|_1 = 1\}$ which is compact. Since we are seeking a vector $v$ of $\mathcal{K}_d$, it satisfies $\|v\|_1 \ge (d-1) \|v\|_{\infty}$. We are therefore interested in $T_0 \stackrel{\text{def}}{=} \{v \in T \mid \|v\|_1 \ge (d-1) \|v\|_{\infty}\}$. The simplex $T_0$ is represented in Figure 1 in the case where $d=3$. The first letter $\delta_1$ of $\Delta$ is used to divide $T_0$ into 3 parts according to the value of $\delta_1$. Consider the set $T_1$ of vectors $v$ of $T_0$ the minimum coordinate of which is the one of index $\delta_1$ and satisfying $\|v^{(1)}\|_1 \ge (d-1) \|v^{(1)}\|_{\infty}$ where $v^{(1)} \stackrel{\text{def}}{=} \gamma_{\delta_1}(v)$ and $\gamma_i \stackrel{\text{def}}{=} x \mapsto x - (1-e_i)x_i$. In Figure 1 (left), the triangle $T_1$ is thus one of the 3 sub-triangles of $T_0$ (in red if $\delta_1 = 1$, in green if $\delta_1 = 2$ and in blue if $\delta_1 = 3$). Repeat the construction to build a sequence $(T_k)_{k \in \mathbb{N}}$ where $T_{k+1}$ is the set of vectors $v$ of $T_k$ such that the smallest coordinate of $v^{(k)}$ is that of index $\delta_{k+1}$ and satisfying $\|v^{(k+1)}\|_1 \ge (d-1) \|v^{(k+1)}\|_{\infty}$ with $v^{(k+1)} \stackrel{\text{def}}{=} \gamma_{\delta_{k+1}}(v^{(k)})$. Figure 1 (right) shows the first triangles $T_k$ in the case $\Delta = 12123...$. Thus, $(T_k)_{k \in \mathbb{N}}$ is a decreasing sequence of compacts the diameter of which tends towards 0. So this sequence converges to a single point $v$. The constraint that each letter must appear infinitely many times in $\Delta$ ensures that $v \in \mathcal{K}_d$. We have thus constructed a unique $v \in \mathcal{K}_d$ of norm 1 associated with $\Delta$. All vectors in $\mathcal{K}_d$ associated with $\Delta$ are given by $\lambda v$ for $\lambda \in \mathbb{R}_+^*.$
### 3 Definition of the Δ-numeration

The sequences generated by the fully subtractive algorithm allow us to define Δ-numeration in the Kraaikamp-Meester case, which is essential for establishing the properties of our system. We therefore fix $v \in K_d$ for the rest of this article and consider the Δ and $\theta$ sequences associated with $v$ in the fully subtractive algorithm.

**Definition 3.1** Let $w \in \mathbb{Z}^\omega$. We say that $w$ represents the real number $\varphi(w) \stackrel{\text{def}}{=} \sum_{n=1}^\infty w_n \theta_n$ provided that the sum converges.

**Remark 3.2** We are often interested in particular words $w$, usually bounded or with values in $\{0, 1\}$. In this case, the sum converges, a result of [10] ensuring that $\Omega \stackrel{\text{def}}{=} \varphi(1^\omega) = \sum_{n=1}^\infty \theta_n = \frac{\|v\|_1}{d-1}$. Moreover, we are also interested in finite words. We then artificially extend the finite word $w$ into $w0^\omega$. In the following we will freely confuse $w$ with $w0^\omega$.

A first simple example of Δ-numeration was studied in 2014 in [3] for the specific Tribonacci case. The authors consider the single real root $\alpha$ of the polynomial $X^3+X^2+X-1$ and the vector $v \stackrel{\text{def}}{=} (\alpha, \alpha+\alpha^2, 1)$. The flow of the algorithm on $v$ is given in Table 2. We then obtain $\Delta = (123)^\omega$ and $\forall n \in \mathbb{N}^*, \theta_n = \alpha^n$. This is a simple case of β-numeration in base $\frac{1}{\alpha}$.

$$ v^{(n)} = \begin{array}{c|c} v = (\alpha, \alpha + \alpha^2, 1) & \delta_n \begin{array}{c|c} \theta_n \\ \hline 1 & \alpha \\ 2 & \alpha^2 \\ 3 & \alpha^3 \\ 1 & \alpha^4 \end{array} \\ (\alpha, \alpha^2, 1 - \alpha) & \\ (\alpha - \alpha^2, \alpha^2, \alpha^3) & \\ (\alpha^4, \alpha^4 + \alpha^5, \alpha^3) = \alpha^3 v & \\ \vdots & \vdots \end{array} $$

<caption>**Table 2.** Fully subtractive algorithm on the vector $v = (\alpha, \alpha + \alpha^2, 1)$ where $\alpha$ satisfies $\alpha + \alpha^2 + \alpha^3 = 1$.</caption>

### 4 Expansions and reductions

In this section, we define a convergent rewriting system that makes it easy to calculate in Δ-numeration. This system comes from the linear recurrence relations satisfied by $\theta$ which we obtain via the fully subtractive algorithm. We call this property, derived from [9], the liaison Theorem.

**Theorem 4.1 (liaison [9, Lemmas 5 and 6])**

1) If the letter $k$ has its first occurrence in $\Delta$ at position $n$ then $v_k = \sum_{i=1}^n \theta_i$.

2) If the letter $k$ has 2 successive occurrences in $\Delta$ at positions $m$ and $n$ with $m < n$ then $\theta_m = \sum_{i=m+1}^n \theta_i$.

The liaison theorem makes it possible to establish, by immediate recurrence, that the $\theta_n$ belong to $\text{Vect}_Z(v)$, the subgroup of $\mathbb{R}$ generated by the coordinates of $v$. Moreover, the linking relations between the $\theta_n$ allow us to expose expansion and reduction relations on $w$ which preserve $\varphi(w)$.
**Definition 4.2 (Reduction/Expansion [7])** Let $w \in \mathbb{Z}^{\omega}$. We assume that the letter $k \in [1, d]$ has 2 successive occurrences at positions $m$ and $n$ in $\Delta$, meaning that $\delta_m = \delta_n = k$ and $\delta_i \neq k$ for all $i \in [m+1, n-1]$. The transformation of $w$ consisting in incrementing $w_m$ and decrementing $w_i$ for $i \in [m+1, n]$ to obtain a new word $w'$ is called reduction. The reverse operation is called expansion.

<table><thead><tr><th></th><th>Δ</th><th>...</th><th>k</th><th>(≠ k)</th><th>(≠ k)</th><th>(≠ k)</th><th>k</th><th>...</th></tr></thead><tbody><tr><td><strong>Reduction :</strong></td><td>w</td><td>...</td><td>w<sub>m</sub></td><td>w<sub>m+1</sub>+1</td><td>w<sub>m+2</sub>+1</td><td>...</td><td>w<sub>n</sub>+1</td><td>...</td></tr><tr><td></td><td>w'</td><td>...</td><td>w<sub>m</sub>+1</td><td>w<sub>m+1</sub></td><td>w<sub>m+2</sub></td><td>...</td><td>w<sub>n</sub></td><td>...</td></tr><tr><td><strong>Expansion :</strong></td><td>w</td><td>...</td><td>w<sub>m</sub>+1</td><td>w<sub>m+1</sub></td><td>w<sub>m+2</sub></td><td>...</td><td>w<sub>n</sub></td><td>...</td></tr><tr><td></td><td>w'</td><td>...</td><td>w<sub>m</sub></td><td>w<sub>m+1</sub>+1</td><td>w<sub>m+2</sub>+1</td><td>...</td><td>w<sub>n</sub>+1</td><td>...</td></tr></tbody></table>

For example, consider the word $w = 004$ and $\Delta$ of the form 12132313... By means of reductions and expansions (see Figure 2 (left)), we get a word $w'$ over the alphabet $\{0, 1\}$ equivalent to $w$, in the sense that $\varphi(w) = \varphi(w')$. Most often, working with words over the alphabet $\mathbb{N}$, we restrict the reduction and expansion operations as follows:

- reductions are only performed towards a $w_m$ such that $w_m = 0$;

- expansions are only performed from a $w_m$ such that $w_m + 1 \ge 2$.

These restrictions ensure that the word $w'$ in the example is in normal form and, as we show below, give a canonical word in $\{0, 1\}^{\omega}$ to represent each real number in $[0, \Omega]$.

In order to demonstrate the normalisation property of our system, we still have to deal with the case of the improper writing of a number, equivalent in $\Delta$-numeration to the identity $0.9999\cdots = 1$ in base ten numeration. Let us take a finite word $w$ and apply successive expansions from its last 1. Figure 2 (right) shows a construction of the improper writing of $w = 1$ for $\Delta = 12131231...$ At the limit, we obtain an infinite word $w' = (\alpha_n)_{n \in \mathbb{N}} \in \{0, 1\}^{\omega}$ such that $\forall n \in \mathbb{N}, \alpha_n = 1$ iff $\delta_n \neq 1$. The words $w$ and $w'$ are equivalent because $\varphi(w) = \varphi(w')$ but both in normal form for the expansion/reduction relations. We therefore add an infinite carry rule to avoid this problem.

<table><caption>**Fig. 2.** Left: reduction of $w \stackrel{\text{def}}{=} 004$ in the $\Delta$-numeration system associated with $\Delta \stackrel{\text{def}}{=} 12132313...$. Expansion positions are marked in red, reduction positions in blue. We obtain a word $w' = 101001100$ which represents the same value as $w$. Right: constructing the improper writing of a word from a finite word.</caption><thead><tr><th>1</th><th>2</th><th>1</th><th>3</th><th>2</th><th>3</th><th>1</th><th>3</th><th>...</th></tr></thead><tbody><tr><td>0</td><td>0</td><td>4</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>0</td><td>0</td><td>3</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><td>0</td><td>1</td><td>2</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>2</td><td>2</td><td>0</td><td>0</td></tr><tr><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>2</td><td>2</td><td>0</td><td>0</td></tr><tr><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td></tr></tbody></table><table><thead><tr><th>1</th><th>2</th><th>1</th><th>3</th><th>1</th><th>2</th><th>3</th><th>1</th><th>...</th></tr></thead><tbody><tr><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>...</td></tr><tr><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>...</td></tr><tr><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>...</td></tr><tr><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>...</td></tr></tbody></table>
**Definition 4.3 (Improper writing)**. Let $w \in \{0, 1\}^\omega$. We say that $w$ is in improper writing iff there exist $r \in \mathbb{N}$, $u \in \{0, 1\}^r$, $v \in 0\{0, 1\}^\omega$ and $k \in [1, d]$ such that $w = uv$ and $\forall n \in \mathbb{N}^*, v_n = 0$ iff $\delta_{n+r} = k$. For such an $w$, we add the infinite carry rewrite rule $w \to u1$.

**Definition 4.4 (Greedy writing)** Let $x \in [0, \Omega]$. The greedy writing of $x$ is the word $w \in \{0, 1\}^\omega$ obtained from the greedy algorithm, defined by recurrence as follows:

$$ 
\begin{array}{l@{\qquad}l}
-x_1 = x & \\
-x \text{ for all } n \in \mathbb{N}^*, \text{ let } w_n \stackrel{\text{def}}{=} \begin{cases} 1 & \text{if } x_n \ge \theta_n \\ 0 & \text{if } x_n < \theta_n \end{cases} \quad \text{and} \quad x_{n+1} = x_n - w_n\theta_n.
\end{array}
$$

We define a normalisation property expressing the behaviour of the Δ-numeration. For finite words, the system is convergent. For infinite words, it is necessary to allow a potentially infinite number of reductions.

**Definition 4.5 (Normalisation)** We say that a rewriting system $\to$ is normalising on $A^\omega$ iff:

1. $\to$ is strongly normalising for finite words, i.e. the restriction of $\to$ to $A^*$ is well founded.

2. $\to$ is weakly normalising for infinite words, i.e. for all $u_0 \in A^\omega$, there exists a sequence $(u_n)_{n \in \mathbb{N}}$ decreasing for $\to$ and converging in the Cantor set $A^\omega$ to a limit in normal form.

**Theorem 4.6 (normalisation [7, Theorem 16], [6, Section 2])**

1. the rewriting system associated with the expansion/reduction/infinite carry rules is normalising and confluent;

2. $\varphi(\{0, 1\}^\omega) = [0, \Omega]$ and any real number $x \in [0, \Omega]$ is uniquely written as $\varphi(w)$ for a $w \in \{0, 1\}^\omega$ in normal form for the expansion/reduction/infinite carry system;

3. with the previous notations, $w$ is the greedy representation of $x$.

Note that this normalisation property is very strong and is found in very few numeration systems. However, its presence can be explained by the very strong constraints on the $\theta$ sequence. In particular, it allows comparisons, additions and subtractions to be carried out easily in our numeration system. For comparisons, all we have to do is put the words $w, w'$ to be compared in normal form and then compare the normal forms lexicographically. For additions, we sum $w$ and $w'$ term by term and then normalise. Note that if $\varphi(w) + \varphi(w')$ falls outside the interval $[0, \Omega]$, it is still possible to calculate the sum by extending $\Delta$ to the left and $\theta$ accordingly. Finally, for subtractions, if $\varphi(w) \ge \varphi(w')$, we can subtract the 2 words term by term to obtain a word over the alphabet $\{-1, 0, 1\}$. By allowing expansions from 1 and reductions towards $-1$, we then get a word over the alphabet $\{0, 1\}$ in normal form representing $\varphi(w) - \varphi(w')$.
**5 Link with $\beta$-numeration and Cantor bases**

We have already shown an example, for $\Delta = (123)^\omega$ and the Tribonacci number, where $\Delta$-numeration meets $\beta$-numeration. In fact, this is the only case where these two systems coincide, up to a generalisation to $d$-dimensions. Let us start with a technical lemma before proving this property.

**Lemma 5.1** Let $k,r \in \mathbb{N}^*$ such that $\theta_k = \sum_{i=1}^r \theta_{k+i}$. Then $\delta_k = \delta_{k+r}$ and $\delta_{k+r}$ is the next occurrence of $\delta_k$ in $\Delta$.

*Proof.* Should we modify the initial vector $v$, we can assume without loss of generality that $k=1$ and $\delta_k=1$. Let us call $q \stackrel{\text{def}}{=} \min\{i \ge 2 \mid \delta_i = 1\}$ the next occurrence of 1 in $\Delta$. By the liaison theorem 4.1, we have $\sum_{i=2}^q \theta_i = \theta_1 = \sum_{i=2}^r \theta_i$. By subtracting, we obtain that $\sum_{i=\min(q,r)+1}^{\max(q,r)} \theta_i = 0$. Since $v \in \mathcal{K}_d$, $\theta_i$'s are positive so that $q=r$. $\square$

**Proposition 5.2** Let $v \in \mathcal{K}_d$ and $\beta > 1$ be such that the $\Delta$-numeration system associated with $v$ is base $\beta$ numeration. Then $\beta$ is the Pisot number root of $X^d - \sum_{k=0}^{d-1} X^k$ and, up to a permutation of the coordinates, $\Delta = (123...d)^\omega$ and $v$ is proportional to $(\sum_{i=1}^k \frac{1}{\beta^i})_{k \in [1,d]}$.

*Proof.* Let $v \in \mathcal{K}_d$ and $\Delta, \theta$ be the sequences associated by the fully subtractive algorithm. It is assumed that there exists $\beta > 1$ such that $\forall n \in \mathbb{N}^*, \theta_n = \beta^{-n}$. Should we permute the coordinates of $v$, we can assume without loss of generality that $v$ is increasing and therefore that $\delta_1 = 1$. Since $\Delta$ admits infinitely many occurrences of each letter, $1$ appears infinitely many times in $\Delta$. In particular, let $r \stackrel{\text{def}}{=} \min\{n \ge 2 \mid \delta_n = 1\} - 1$ be the second occurrence of $1$ in $\Delta$. Then, by the liaison theorem, $\frac{1}{\beta} = \theta_1 = \sum_{i=2}^{r+1} \theta_i = \sum_{i=2}^{r+1} \frac{1}{\beta^i}$. Multiplying by $\beta^{r+1}$, we find that $\beta$ is a root of $P \stackrel{\text{def}}{=} X^r - \sum_{i=0}^{r-1} X^i$.

Let $k \in \mathbb{N}^*$. Since $\beta$ is a root of $P$, $\beta^{-k} = \sum_{i=1}^r \beta^{-(i+k)}$ and hence $\theta_k = \sum_{i=1}^r \theta_{i+k}$. By Lemma 5.1, we deduce that the next occurrence of $\delta_k$ in $\Delta$ is $\delta_{k+r}$. Since $\Delta$ admits infinitely many occurrences of each letter, this imposes $r=d$ and $\delta = (123...d)^\omega$ because $v$ is increasing. By posing $v_0 \stackrel{\text{def}}{=} (\sum_{i=1}^k \frac{1}{\beta^i})_{k \in [1,d]}$, we can easily check, like in [3], that $v_0 \in \mathcal{K}_d$ has $\Delta$ as associated word. It suffices to note that a step in the fully subtractive algorithm applied to $v_0$ gives the vector $\frac{1}{\beta}v_0$, up to the permutation of the coordinates by the cycle $(d...321)$. By uniqueness, we deduce that $v$ is proportional to $v_0$. $\square$

**Definition 5.3 (Real Cantor bases [5])** Let $(\beta_n)_{n \in \mathbb{N}^*}$ be a sequence of real numbers in $[1, +\infty[$ such that $\prod_{k=1}^\infty \beta_k = +\infty$. The word $w \in \mathbb{N}^\omega$ represents for real Cantor bases the real number $\sum_{n=1}^\infty (w_n/\prod_{k=1}^n \beta_k)$, provided that the sum exists.

We can easily create a link between real Cantor bases and $\Delta$-numeration, simply by looking for a sequence $\beta$ such that $\forall n \in \mathbb{N}^*, \theta_n = 1/\prod_{k=1}^n \beta_k$. If we
have such a relationship, we can state $\frac{\theta_n}{\theta_{n+1}} = \frac{\left(\prod_{k=1}^{n+1} \beta_k\right)}{\left(\prod_{k=1}^{n} \beta_k\right)} = \beta_{n+1}$.
Thus, given a sequence $\theta$ given by the fully subtractive algorithm, it suffices to
put $\beta_1 \stackrel{\text{def}}{=} \frac{1}{\theta_1}$ and $\forall n \in \mathbb{N}^*, \beta_{n+1} \stackrel{\text{def}}{=} \frac{\theta_n}{\theta_{n+1}}$ to see $\Delta$-numeration as a special case
of Cantor real bases. The reals $\beta_n$ (for $n \ge 2$) are indeed in $[1, +\infty[$ because $\theta$ is
weakly decreasing, and $\forall n \in \mathbb{N}^*, \prod_{k=1}^n \beta_k = \frac{1}{\theta_n} \xrightarrow{n \to +\infty} +\infty$ because $\theta$ converges
to 0. As for $\beta_1 = \frac{1}{\theta_1}$, we cannot be sure that it belongs to $[1, +\infty[$ but, since
$\Delta$-numeration is defined up to a multiplicative constant, we can always return
to the case where $\beta \in [1, +\infty[$.

While Δ-numeration can be seen as a special case of Cantor real bases, the converse is false. First of all, finite words in Δ-numeration all represent reals in Vect<sub>Z</sub>(v) which is a module of finite type. Cantor real bases do not have this type of constraint. Moreover, Cantor real bases generalise numeration in base β > 1, whereas Δ-numeration is limited to very particular β, as explained in Proposition 5.2. Cantor real bases therefore offer a much more general framework than Δ-numeration. However, this generality prevents these bases from being equipped with an efficient normalisation system, such as expansion/reduction. The linking relations on the θₙ are therefore what restricts our system the most, but also what makes the calculations in it so simple.

**6 The (ultimately) periodic case**

We are interested here in the case where the word $\Delta$ is periodic. Let us first note
that the reasoning in this section is stable by any finite left extension of $\Delta$, so
that these results generalise without difficulty to the ultimately periodic case.
For the sake of simplicity, however, we restrict ourselves here to the periodic case,
where $\Delta = \pi^\omega$ where $\pi \in [1, d]^*$ is of length $p$. The properties of $\Delta$-numeration
in the periodic case were first set out in [6], as a tool for solving a discrete
geometry problem. In parallel, they were studied by E. Charlier [4] in the more
general context of alternate bases, the periodic case of real Cantor bases. Both
papers independently involve a Pisot number $\beta$ and the number field $\mathbb{Q}[\beta]$.

**Theorem 6.1 (periodicity [6, Section 6])** Let us note, for $i \in [1, d]$, $\gamma_i \stackrel{\text{def}}{=} x \mapsto x - (1 - e_i)x_i$ the transformations of the fully subtractive algorithm, where $1 \stackrel{\text{def}}{=} (1, \dots, 1)$. Let $\Gamma \stackrel{\text{def}}{=} \gamma_{\pi_p} \circ \dots \circ \gamma_{\pi_2} \circ \gamma_{\pi_1}$. Then

- there exists a real number $\beta$ such that $\forall n \in \mathbb{N}^{*}, \theta_{n+p} = \beta\theta_n;$

- the vector $v$ is an eigenvector of $\Gamma$ associated with the eigenvalue $\beta$;

- $\Gamma^{-1}$ is a cyclic endomorphism (in a $\mathbb{K}$-vectorial space $E$, $u \in \mathcal{L}(E)$ is called cyclic iff $\exists x \in E, E = \mathbb{K}[u]x$) product of Pisot matrices [2];

- $\frac{1}{\beta}$ is a Pisot number of degree $d$, with minimal polynomial equal to the minimal (and characteristic) polynomial of $\Gamma$.

The previous theorem thus allows us to easily find the vector $v$ from the
period $\pi$ of $\Delta$. In the case where $\Delta = (123)^\omega$, the vector $v$ can be found as
the eigenvector of $\gamma_3 \circ \gamma_2 \circ \gamma_1$ the matrix of which is
$$ \begin{pmatrix} 2 & 0 & -1 \\ -1 & 2 & -1 \\ 0 & -1 & 1 \end{pmatrix} $$
This matrix has a single real eigenvalue $\alpha^3$ (which is the inverse of a Pisot number), where $\alpha$ is the single real root of $X^3 + X^2 + X - 1$, and an associated eigenvector is $v = (\alpha, \alpha + \alpha^2, 1)$. This gives us the Tribonacci vector studied in [3].

In the case where $\Delta = (1213)^\omega$, the example we will use later, the vector $v$ can be found as the eigenvector of $\gamma_3 \circ \gamma_1 \circ \gamma_2 \circ \gamma_1$ the matrix of which is
$$ \begin{pmatrix} 4 & -1 & -1 \\ -1 & 2 & -1 \\ -2 & 0 & 1 \end{pmatrix} $$

The characteristic polynomial of this matrix is $X^3 - 7X^2 + 11X - 1$ which has 3 real roots. Only one of them has modulus < 1, which is called $\beta$. In particular, $\beta \approx 0.09678807$ is the inverse of a Pisot number. An eigenvector $v$ associated with the eigenvalue $\beta$ is $(2, -\beta^2 + 4\beta + 3, \beta^2 - 6\beta + 5)$.

Note that, in the ultimately periodic case where $\Delta = u\pi^\omega$, it is also possible to calculate $v$ easily. We start by calculating $v'$, the vector associated with $\pi^\omega$. Then, by posing $A \stackrel{\text{def}}{=} \gamma_{u_k} \circ \dots \circ \gamma_{u_1}$, we obtain $Av = v'$. Since $A$ is invertible, we deduce $v = A^{-1}v'$.

The periodicity theorem can also be used to demonstrate the link with alternate Cantor bases. The property $\forall n \in \mathbb{N}^*, \theta_{n+p} = \beta\theta_n$ shows the periodicity of the associated sequence $(\beta_n)_{n \in \mathbb{N}^*}: \forall n \in \mathbb{N}^*, \beta_{n+1+p} = \frac{\theta_{n+p}}{\theta_{n+1+p}} = \frac{\beta\theta_{n+1}}{\beta\theta_n} = \beta_{n+1}$. To prove $\beta_{p+1} = \beta_1$, however, it is necessary to set $\theta_p = \beta$, which is the same as setting $v$. Finally, the periodic character of $\Delta$ allows us to characterise the image by $\varphi$ of the set of ultimately periodic words.

**Corollary 6.2** $\forall n \in \mathbb{N}^*, \theta_n \in v_1\mathbb{Q}[\beta]$.

**Theorem 6.3** If we set $U \stackrel{\text{def}}{=} \{\sigma \in \mathbb{Z}^\omega \mid \sigma \text{ is ultimately periodic}\}$, we have
$\varphi(U) = v_1\mathbb{Q}[\beta]$.

Before proving the result, let us note that analogous proofs of this result are proposed in [4] for alternate bases and in [14] for Rényi bases. However, our proof has an effective side which makes it easier to perform calculations in our numeration system.

*Proof.* Let us first show that $\varphi(U) \subset v_1\mathbb{Q}[\beta]$. Recall that $v_1\mathbb{Q}[\beta]$ is stable by sum and by product by an element of $\mathbb{Q}[\beta]$. Since $\beta$ is algebraic, we also know that $\mathbb{Q}[\beta]$ is a field. Since all $\theta_n$ live in $v_1\mathbb{Q}[\beta]$ which is closed by sum, every finite word has its image by $\varphi$ in $v_1\mathbb{Q}[\beta]$. Let us now look at ultimately periodic words in general. Let us call $p$ the period of $\Delta$ and take $\sigma \in U$. Since $\sigma$ is ultimately periodic, there are $u, w \in \{0, 1\}^*$ such that $\sigma = uw^\omega$. Should we increase the sizes of $u$ and $w$, we can assume without loss of generality that $|u|$ and $|w|$ are multiples of $p$. Let $k$ and $n$ be such that $|u| = kp$ and $|w| = np$, where $|\cdot|$ denotes the word length function. Note finally that $\sigma$ is ultimately periodic and therefore bounded, and that $(\theta_n)_{n \in \mathbb{N}}$ is summable so that $\varphi(\sigma)$ exists. Thus, since $\varphi(u)$
and $\varphi(w)$ are in $v_1\mathbb{Q}[\beta]$,

$$ \varphi(\sigma) = \varphi(u) + \beta^k \varphi(w^\omega) = \varphi(u) + \beta^k \left( \sum_{j=0}^{\infty} \varphi(w) \beta^{jn} \right) = \varphi(u) + \frac{\beta^k}{1 - \beta^n} \varphi(w) \in v_1\mathbb{Q}[\beta] $$

Let us now show that every element of $v_1\mathbb{Q}[\beta]$ is the image of an element of $U$. Note that $U$ is stable by sum so that $\varphi(U)$ also is. Since $U$ is stable by shift, $\varphi(U)$ is stable by multiplication by $\beta$. It therefore remains to show that $(\frac{v_1}{b})$ for $b \in \mathbb{N}^*$ are representable by words in $U$. Let us reason by analysis-synthesis. We are looking for $\lambda \in \mathbb{Z}^\omega$ periodic of period $np$ such that (note that the family $(\lambda_k \beta^k)_{k \in \mathbb{N}}$ is summable because $\lambda$ is periodic and therefore bounded):

$$ \begin{aligned} \frac{1}{b} &= \sum_{k=0}^{+\infty} \lambda_k \beta^k = \sum_{m=0}^{+\infty} \sum_{q=0}^{np-1} \lambda_{mnp+q} \beta^{mnp+q} = \sum_{m=0}^{+\infty} \beta^{mnp} \sum_{q=0}^{np-1} \lambda_q \beta^q \\ &= \frac{P(\beta)}{1 - \beta^{np}} \quad \text{where } P(\beta) \stackrel{\text{def}}{=} \sum_{q=0}^{np-1} \lambda_q \beta^q \in \mathbb{Z}[\beta] \end{aligned} $$

From now on, we wish to find $P \in \mathbb{Z}[X]$ and $n \in \mathbb{N}^*$ such that $1 - \beta^{np} = bP(\beta)$. Let us consider $A = \mathbb{Z}[X]/(\mu_\beta, b)$, the quotient ring of $\mathbb{Z}[X]$ by the ideal generated by $\mu_\beta$ and $b$. $A$ is a finite ring. Since $\mu_\beta$ is unitary, by the isomorphism theorem, we have the ring isomorphisms $\mathbb{Z}[X]/(\mu_\beta, b) \simeq \mathbb{Z}_{d-1}[X]/(b) \simeq (\mathbb{Z}/b\mathbb{Z})_{d-1}[X]$ which is finite. Recall then that $\mu_\beta$ is the characteristic polynomial of a product matrix of $\gamma_i \stackrel{\text{def}}{=} x \mapsto x - (\mathbf{1} - e_i)x_i$. Since $\forall i \in [1, d]$, $\det(\gamma_i) = 1$, the constant coefficient of $\mu_\beta$ is then $(-1)^d$. Thus, there exists $Q \in \mathbb{Z}[X]$ such that $\mu_\beta = XQ + (-1)^d$. Passing to the quotient in $A$, we obtain $0 = XQ + (-1)^d$ from which $X((-1)^{d+1}Q) = 1$. $X$ is therefore invertible in $A$. Since the multiplicative group $A^\times$ is finite, by Lagrange's theorem there exists $n \in \mathbb{N}^*$ such that $X^n = 1$ in $A$, hence $X^{np} = 1$ in $A$. Thus, there exists $P, R \in \mathbb{Z}[X]$ such that $X^{np} = 1 + R\mu_\beta - bP$. Evaluating in $\beta$, we then find $\beta^{np} = 1 - bP(\beta)$ so $1 - \beta^{np} = bP(\beta)$ which was the equality we were looking for.

The fractions $\frac{v_1}{b}$ are thus representable by words of $U$, and since $\varphi(U)$ is closed by sum and by product by $\beta$, we get the reciprocal inclusion $v_1\mathbb{Q}[\beta] \subset \varphi(U)$. $\square$

The effective nature of the proof of Theorem 6.3 means that, when $v_1 \in \mathbb{Q}[\beta]$, we can effectively perform new operations in $\Delta$-numeration, in particular multiplication and division. In fact, we can move from $U$ to $\mathbb{Q}[\beta]$ effectively and vice versa. As it is simple to perform the usual operations in $\mathbb{Q}[\beta]$, we can perform them without difficulty in $U$.

Let us illustrate the effectiveness of the proof using the example of $\Delta = (1213)^\omega$. The word $\Delta$ has the associated Pisot inverse $\beta \approx 0,09678807$ which is the root of the polynomial $\mu_\beta = X^3 - 7X^2 + 11X - 1$. We obtain $v \stackrel{\text{def}}{=} (2, -\beta^2 + 4\beta + 3, \beta^2 - 6\beta + 5)$ as the vector associated with $\Delta$ and we can
calculate the sequence $\theta$ by the liaison theorem 4.1,

$$ 
\left\{ 
\begin{array}{lcl}
\theta_1 & = & v_1 \\
\theta_2 & = & v_2 - \theta_1 \\
\theta_3 & = & \theta_1 - \theta_2 \\
\theta_4 & = & v_3 - \theta_1 - \theta_2 - \theta_3
\end{array}
\right.
\qquad = 2 \\
\qquad = -\beta^2 + 4\beta + 1 \\
\qquad = \beta^2 - 4\beta + 1 \\
\qquad = \beta^2 - 6\beta + 1
$$
and $\forall n \in \mathbb{N}^*, \theta_{n+4} = \beta\theta_n$.

Let us take the example $\sigma \stackrel{\text{def}}{=} 10(1201)^\omega \in U$. We begin by writing $\sigma$ in blocks of period 4 as in the proof of the previous theorem: $\sigma = uw^\omega$ with $u \stackrel{\text{def}}{=} 1012$ and $w \stackrel{\text{def}}{=} 0112$. Thus,

$$ 
\left\{ 
\begin{array}{l}
\varphi^v(u) = \theta_1 + \theta_3 + 2\theta_4 = 3\beta^2 - 16\beta + 5 \\
\varphi^v(w) = \theta_1 + 2\theta_2 + \theta_4 = -\beta^2 + 2\beta + 5
\end{array}
\right.
$$

hence

$$ \varphi^v(\sigma) = \varphi^v(u) + \frac{\beta}{1-\beta}\varphi^v(w) = \frac{13\beta^2 - 102\beta + 21}{4} \in \mathbb{Q}[\beta]. $$

To obtain all the polynomials in $\beta$ as elements of $\varphi^v(U)$, let us start by noting that $v_1 = 2$. So $\varphi^v(1) = 2$ and $\varphi^v(0^4n1) = 2\beta^n$. So we already have $2\mathbb{Z}[\beta] \subset \varphi^v(U)$. To obtain $\mathbb{Q}[\beta] \subset \varphi^v(U)$, it remains to obtain codes for $\frac{2}{b}$ with $b \in \mathbb{N}^*$. For example, let us take $b = 2$. We place ourselves in $A \stackrel{\text{def}}{=} \mathbb{Z}[X]/(\mu_\beta, 2)$ and look at the order of $X$ in $A^\times$. By definition of $A$, $0 = X^3 - 7X^2 + 11X - 1 = X^3 + X^2 + X + 1$. Hence $X^3 = X^2 + X + 1$ and $X^4 = X^3 + X^2 + X = 1$ so $X$ is of order 4 in $A^\times$. We then divide $X^4 - 1$ by $\mu_\beta$: $X^4 - 1 = Q\mu_\beta + 2(19X^2 - 38X + 3)$ so $\beta^4 - 1 = 2(19\beta^2 - 38\beta + 3)$ and, posing $P \stackrel{\text{def}}{=} -19X^2 + 38X - 3$, we obtain:

$$ \frac{1}{2} = \frac{P(\beta)}{1 - \beta^4} = P(\beta) \sum_{k=0}^{\infty} \beta^{4k} $$

We can therefore encode $\frac{2}{2}$ by the word $(( - 3 ) 0 0 0 ( 3 8 ) 0 0 0 ( - 1 9 ) 0 0 0 0 0 0 )^\omega$ which we can then normalise to $(0011001000001101)^\omega$. So the normalised code for $\frac{2}{2}$ is $(0011001000001101)^\omega$.

# 7 Conclusion

This article reviews the known properties of $\Delta$-numeration from the point of view of numeration systems. We make the link with $\beta$-numeration and with Cantor real bases. While $\Delta$-numeration is a special case of Cantor bases, the linear constraints induced by the fully subtractive algorithm make it possible to define expansion/reduction operations and to obtain normalisation properties for this system. Finally, we look at the ultimately periodic case, analogous in $\Delta$-numeration to alternating bases, where the inverse $\beta$ of a Pisot number appears. We then characterise the set of numbers represented by ultimately periodic words. After multiplication by a scalar, this is the number field $\mathbb{Q}[\beta]$,
which makes it possible to perform additions, subtractions, multiplications and
divisions on the ultimately periodic words. Beyond the ultimately periodic case,
it would be interesting to look at more general cases of Δ words, in the case
of words resulting from substitution processes for example, or even for general
uniformly recurrent words. Although the linking relations between θ_n are of
bounded size, they nevertheless seem much more difficult to exploit without the
periodicity hypothesis.

References

1. P. Arnoux and S. Starosta. The rauzy gasket. In *Further developments in fractals and related fields: Mathematical foundations and connections*. Springer, 2013.

2. A. Avila and V. Delecroix. Some monoids of pisot matrices. In *New Trends in One-Dimensional Dynamics: IMPA 2016, Rio de Janeiro*. Springer, 2019.

3. V. Berthé, E. Domenjoud, D. Jamet, and X. Provençal. Fully subtractive algorithm, tribonacci numeration and connectedness of discrete planes. *RIMS Lecture notes 'Kokyuroku Bessatu',* 46:159–174, 2014.

4. E. Charlier. Alternate base numeration systems. In *International Conference on Combinatorics on Words*, pages 14–34. Springer, 2023.

5. E. Charlier and C. Cisternino. Expansions in cantor real bases. *Monatshefte für Mathematik*, 195(4):585–610, 2021.

6. E. Domenjoud, B. Laboureix, and L. Vuillon. Facet connectedness of arithmetic discrete hyperplanes with non-zero shift. In *DGCI*. Springer, 2019.

7. E. Domenjoud, X. Provençal, and L. Vuillon. Facet connectedness of discrete hyperplanes with zero intercept: The general case. In *DGCI*. Springer, 2014.

8. E. Domenjoud, X. Provençal, and L. Vuillon. Palindromic language of thin discrete planes. *Theoretical Computer Science*, 624:101–108, 2016.

9. E. Domenjoud and L. Vuillon. Geometric palindromic closure. *Uniform distribution theory*, 7(2):109–140, 2012.

10. C. Kraaikamp and R. Meester. Ergodic properties of a dynamical system arising from percolation theory. *Ergodic Theory and Dynamical Systems*, 1995.

11. B. Laboureix. *Hyperplans arithmétiques: connexité, reconnaissance & transformations*. PhD thesis, Université de Lorraine, 2024.

12. A. Rényi. Representations for real numbers and their ergodic properties. *Acta Math. Acad. Sci. Hungar*, 8(3-4):477–493, 1957.

13. M. Rigo. Numeration systems: a link between number theory and formal language theory. In *International Conference on Developments in Language Theory*, pages 33–53. Springer, 2010.

14. K. Schmidt. On periodic expansions of pisot numbers and salem numbers. *Bulletin of the London Mathematical Society*, 12(4):269–278, 1980.

15. F. Schweiger. *Multidimensional continued fractions*. Oxford University, 2000.