Positionality of Dumont–Thomas numeration systems for integers Savinien Kreczman, Manon Stipulanti, Sébastien Labbé Abstract Introduced in 2001 by Lecomte and Rigo, abstract numeration systems provide a way of expressing natural numbers with words from a language L L accepted by a finite automaton. As it turns out, these numeration systems are not necessarily positional, i.e., we cannot always find a sequence U = ( U i ) i ≥ 0 U=(U_{i})_{i\geq 0} of integers such that the value of every word in the language L L is determined by the position of its letters and the first few values of U U . Finding the conditions under which an abstract numeration system is positional seems difficult in general. In this paper, we thus consider this question for a particular sub-family of abstract numeration systems called Dumont–Thomas numeration systems. They are derived from substitutions and were introduced in 1989 by Dumont and Thomas. We exhibit conditions on the underlying substitution so that the corresponding Dumont–Thomas numeration is positional. We first work in the most general setting, then particularize our results to some practical cases. Finally, we link our numeration systems to existing literature, notably properties studied by Rényi in 1957, Parry in 1960, Bertrand-Mathis in 1989, and Fabre in 1995. Keywords: morphism, substitution, periodic points, numeration system, positionality, Bertrand property, Fabre substitution. 1 Introduction The need of representing natural numbers (or expressing them in writing) has occupied humans for centuries. In its most general form, this leads to so-called abstract numeration systems , introduced by Lecomte and Rigo in 2001 [ 12 ] (see also [ 2 , Chapter 3] for a general presentation). Such a numeration system is defined by a triple S=(L,A,\prec) where A is an alphabet ordered by the total order \prec and L is an infinite regular language over A (i.e., accepted by a deterministic finite automaton). We say that L is the numeration language of S . When we order the words of L with the genealogical order (i.e., first by length, then using the dictionary order) induced by \prec , we obtain a one-to-one correspondence \rep_{S} between \N and L . The ( S -)representation of the non-negative integer n is then the (n+1) st word of L , and the inverse map, called the ( S -)evaluation map , is denoted by \val_{S} . A simple example is given by the abstract numeration system S built on the language L=\texttt{1}^{*}\texttt{2}^{*} over the ordered alphabet \{\texttt{1},\texttt{2}\} . The first few words in the language are \varepsilon,\texttt{1},\texttt{2},\texttt{11},\texttt{12},\texttt{22},\texttt{111} . For instance, \rep_{S}(5)=\texttt{22} and \val_{S}(\texttt{111})=6 . In general, a numeration system S=(L,A,S) is positional if the underlying alphabet A is a set of consecutive integers \{\texttt{0},\texttt{1},\ldots,\texttt{c}\} for some \texttt{c}\in\N and if there exists a sequence (U_{i})_{i\geq 0} of non-negative integers such that the evaluation map is of the form \val_{S}\colon A^{*}\to\N,w_{k-1}\cdots w_{0}\mapsto\sum_{i=0}^{k-1}w_{i}U_{i} . We use the term positional because the positions of letters in representations are used to generate numbers. Observe that the numeration system built on L=\texttt{1}^{*}\texttt{2}^{*} cannot be positional: indeed, we have \rep_{S}(3)=\texttt{11} and \rep_{S}(5)=\texttt{22} , so there is no hope to find an integer sequence (U_{i})_{i\geq 0} such that 3=1\cdot U_{1}+1\cdot U_{0} and 5=2\cdot U_{1}+2\cdot U_{0} (see also [ 2 , Example 3.1.12] ). We thus raise the following question: Question A . What are the conditions for an abstract numeration system to be positional? See also [ 2 , Exercise 3.13] . As this question seems difficult to answer in its full generality, we consider a particular case with Question B below. Roughly, we consider numeration systems that are derived from substitutions , i.e., maps sending sequences to sequences and satisfying some mild properties. These numeration systems are due to Dumont and Thomas [ 6 ] in 1989. (Note that to properly state the weaker version of Question A , we introduce some notation and definitions in Section 2 .) Since then, Dumont–Thomas numeration systems have been used to solve various problems as they provide a nice framework to work with. As the literature is quite vast, we focus on some recent papers from the 2020’s only. For instance, as Question B already testifies, Dumont–Thomas numerations fail to satisfy natural properties that are however somewhat desirable for numeration systems. In addition, they are typically neither greedy nor addable , i.e., addition is not computable by a finite automaton. The latter condition is needed in particular if one wants to make use of the theorem-prover Walnut [ 16 , 20 ] . Recently, a characterization of such addable numeration systems was found [ 4 ] . Generalizations of Dumont–Thomas numeration systems as numeration systems per se can be found in [ 11 , 21 ] . In [ 8 , 9 ] , classical Dumont–Thomas numeration systems are used to find string attractors for infinite words. In [ 15 ] , the authors use extensions of Dumont–Thomas numeration systems to the setting of random substitutions. In [ 14 ] , the specific case of the Thue–Morse substitution is used to establish uniform bounds for the twisted correlations for all elements in the Thue–Morse subshift. In this paper, we exhibit conditions on the underlying substitution for the corresponding Dumont–Thomas numeration for \Z to be positional. The outline of the paper is as follows. In Section 2 , we present the necessary background and preliminary results. In particular, we present the original generalization of Dumont–Thomas numerations to all integers in Section 2.1 , then generalize it further in Section 2.2 by letting the lengths of representations vary. In Section 3 , we study which Dumont–Thomas numeration systems are positional to answer Question B . We start with a sketch in Section 3.1 , then we prove our main result in Section 3.2 . We turn to particular cases in Section 3.3 and we finish by discussing the properties of our Dumont–Thomas numeration systems related to existing literature, e.g., the property of a numeration system to be Bertrand [ 3 , 5 ] . 2 Preliminaries General combinatorics on words . An alphabet A is a finite set and its elements are called letters . A ( finite or infinite ) word over A is a (finite or infinite) sequence of letters belonging to A . For a finite word w over A , we let |w| denote its length , i.e., the number of letters it is made of. The empty word is denoted by \varepsilon . For a word w over A , a factor of w is a word y such that there exist words x,z such that w=xyz . A prefix (resp. suffix ) is a factor y such that x (resp. z ) is empty. If w=ps for some words p,s , then we write p^{-1}w=s and ws^{-1}=p . For a word w we let w_{i} denote its i -th letter. We use the notation of intervals to indicate portions of words: if I is an interval of integers, we let w_{I} denote the factor (w_{i})_{i\in I} of w . (Recall the difference between parentheses and square brackets to denote intervals.) We let A^{*} denote the set of all finite words over the alphabet A and A^{+} the set of all non-empty words over A (note that A^{+}=A^{*}\setminus\{\varepsilon\} ). For \D\in\{\N,\Z,\Z_{<0}\} , we let A^{\D} the set of words indexed over \D . We call u_{0}u_{1}u_{2}\cdots\in A^{\N} a right-infinite word and \cdots u_{-3}u_{-2}u_{-1}\in A^{\Z_{<0}} a left-infinite word. A two-sided word is a word indexed over \Z . For convenience, we separate by a vertical bar its -1 -th and 0 -th elements to indicate the origin, i.e., u=\cdots u_{-3}u_{-2}u_{-1}|u_{0}u_{1}u_{2}\cdots . If the alphabet A is totally ordered by \prec , we define the lexicographic order on A^{*} and A^{\N} as follows. For two words u,v\in A^{*} , we write u\prec_{\text{lex}}v if u is a proper prefix of v or if there exist p,s,s^{\prime}\in A^{*} and a,a^{\prime}\in A such that u=pas , v=pa^{\prime}s^{\prime} , and a\prec a^{\prime} . For two words u,v\in A^{\N} , we write u\prec_{\text{lex}}v if there exist p\in A^{*} , x,x^{\prime}\in A^{\N} , and a,a^{\prime}\in A such that u=pax , v=pa^{\prime}x^{\prime} , and a\prec a^{\prime} . For finite or infinite words u,v , we write u\preccurlyeq_{\text{lex}}v if u\prec_{\text{lex}}v or u=v . Morphisms and substitutions . Given alphabets A,B , a morphism is a map \mu\colon A^{*}\to B^{*} such that \mu(uv)=\mu(u)\mu(v) for all words u,v\in A^{*} . A morphism is entirely determined by the images of the letters of A . A substitution is a morphism \mu\colon A^{*}\to A^{*} such that the image \mu(a) is non-empty for every letter a\in A and there exists a growing letter a\in A , i.e., \lim_{n\to+\infty}|\mu^{n}(a)|=+\infty . A morphism \mu\colon A^{*}\to A^{*} is primitive if there exists an integer k\in\N such that for all a,b\in A , the letter a appears in \mu^{k}(b) . Note that, if we consider the classical adjacency matrix M of \mu\colon A^{*}\to A^{*} , \mu is primitive if and only if M is primitive. From the theory of primitive matrices, we then deduce that if a morphism is primitive, then there exists an integer k\in\N such that for all a,b\in A and for all \ell\geq k , the letter a appears in \mu^{\ell}(b) . With a morphism \mu\colon A^{*}\to A^{*}, we can associate a directed graph in the following way: the nodes are the letters of A and for every a\in A , if we write \mu(a)=c_{0}\cdots c_{\ell} with c_{i}\in A for every i\in\{0,\ldots,\ell\} , then we draw an arrow labeled by i from a to c_{i} for every i\in\{0,\ldots,\ell\} . This directed graph encodes the images of letters under \mu . Similarly, we may unfold the directed graph into a directed tree starting with some fixed vertex that is then called the root of the tree. Given a\in A , we define the tree \mathcal{T}_{\mu,a} as follows: its root is labeled by a , and if a node of the tree is labeled by x and \mu(x)=y_{0}\cdots y_{\ell} then that node has \ell+1 children labeled from y_{0} to y_{\ell} , with the edge from x to y_{i} being labeled by i . Observe that the k -th level of \mathcal{T}_{\mu,a} stores the k -th iteration of \mu on the letter a . We say that a node of the tree is in column n if there are n nodes of the same level to its left. Substitutions can naturally be applied to two-sided words by setting \mu(\cdots u_{-3}u_{-2}u_{-1}|u_{0}u_{1}u_{2}\cdots)=\cdots\mu(u_{-3})\mu(u_{-2})\mu(u_{-1})|\mu(u_{0})\mu(u_{1})\mu(u_{2})\cdots Let \D\in\{\N,\Z,\Z_{<0}\} and consider a substitution \mu over A . A word u\in A^{\D} is a periodic point of \mu if there exists an integer p\geq 1 such that \mu^{p}(u)=u . In this case, p is called a period of the periodic point u . The smallest such integer is called the period of u . A periodic point of \mu with period p=1 is called a fixed point of \mu . We let \Per_{\D}(\mu)=\{u\in A^{\D}\mid\mu^{p}(u)=u\text{ for some $p\geq 1$}\} denote the set of periodic points of \mu . If u\in\Per_{\Z}(\mu) , then the seed of u is the pair of letters u_{-1}|u_{0} ; see [ 1 , §4.1] . If both letters of the seed of a two-sided periodic point are growing, then the periodic point is defined entirely by its seed. More precisely, we have u=\lim_{n\to+\infty}\mu^{np}(u_{-1})|\lim_{n\to+\infty}\mu^{np}(u_{0}) , where p is a period of u . By extension of the tree associated with a substitution and a letter as in the previous paragraph, we consider two-sided trees as follow. For a substitution \mu over A and two letters a,b\in A , the tree \mathcal{T}_{\mu,b|a} is obtained by setting a start root having two children: the left one is reached with an edge of label 1 and is the root of the tree \mathcal{T}_{\mu,b} , and the right one is reached with an edge of label 0 and is the root of the tree \mathcal{T}_{\mu,a} . We say that a node is in column n if either n\geq 0 , the node is the right subtree and there are n nodes on the same level to its left in the right subtree, or n<0 , the node is in the left subtree and there are -n-1 nodes on the same level to its right in the left subtree. Examples of such trees are given later in the paper. Numeration systems . A numeration system over the domain \D\in\{\N,\Z_{<0},\Z\} is a pair of maps between \D and a set of words, i.e., the representation map \rep\colon\D\to A^{*} for some alphabet A , and the evaluation map \val\colon L\to\D , where \rep(\D)\subset L\subset A^{*} , such that \val\circ\rep=id_{\D} . The set \rep(\D) is the language of the numeration system, while L contains some additional, non-canonical representations. In general, a numeration system over \D=\N is positional if the underlying alphabet A is a set of consecutive integers \{\texttt{0},\texttt{1},\ldots,\texttt{c}\} for some \texttt{c}\in\N and the evaluation map is of the form \val\colon A^{*}\to\N,w_{k-1}\cdots w_{0}\mapsto\sum_{i=0}^{k-1}w_{i}U_{i} for some sequence U=(U_{i})_{i\geq 0}\in\N^{\N} . Over \D=\Z , a numeration system is positional if the underlying alphabet A is a set of consecutive integers \{\texttt{0},\texttt{1},\ldots,\texttt{c}\} for some \texttt{c}\in\N and the evaluation map is of the form \val\colon A^{*}\to\Z,w_{k-1}\cdots w_{0}\mapsto\sum_{i=0}^{k-2}w_{i}U_{i}-w_{k-1}V_{k-1} for some sequences U=(U_{i})_{i\geq 0},V=(V_{i})_{i\geq 0}\in\N^{\N} . The sequences U and V are the sequences of weights of the numeration system. Every position has a given weight, while the presence of an additional sequence V helps deal with the representation of negative numbers, in a fashion similar to the usual two’s complement numeration system described in the next example. {example} The two’s complement numeration system allows representations of all integers in a binary system using powers of 2 . Let A=\{\texttt{0},\texttt{1}\} . The evaluation map is defined as follows: for a word w=w_{k-1}w_{k-2}\cdots w_{0} over A , we set \val_{2c}(w)=-w_{k-1}2^{k-1}+\sum_{i=0}^{k-2}w_{i}2^{i} . Observe now that, for any word w over A , we have \val_{2c}(\texttt{00}w)=\val_{2c}(\texttt{0}w) and \val_{2c}(\texttt{11}w)=\val_{2c}(\texttt{1}w) . So for any integer n\in\Z , there exists a unique word w\in A^{*}\setminus(\texttt{00}A^{*}\cup\texttt{11}A^{*}) such that n=\val_{2c}(w) . We let \rep_{2c}(n) denote this unique word and we call it the two’s complement representation of n . The first few two’s complement representations of integers are (\rep_{2c}(n))_{-4\leq n\leq 4}=\texttt{100},\texttt{101},\texttt{10},\texttt{1},\varepsilon,\texttt{01},\texttt{010},\texttt{011},\texttt{0100} . Observe that the two’s complement numeration system is positional: we may use the sequence of powers of 2 as weights. 2.1 Dumont–Thomas numeration systems In this section, we expose the theory of Dumont and Thomas on numeration systems [ 6 ] . Roughly, a substitution \mu defines a numeration system where the representation of n is the label of a path from the root to column n in a tree associated with \mu . We first recall the notion of admissible sequences for a substitution. Let \mu\colon A^{*}\to A^{*} be a substitution. Fix a letter a\in A and an integer k . For every i\in\{0,\ldots,k\} , we consider a pair (m_{i},a_{i})\in A^{*}\times A . The sequence ((m_{i},a_{i}))_{i=0,\dots,k} is admissible with respect to \mu if for every i\in\{1,\ldots,k\} , m_{i-1}a_{i-1} is a prefix of \mu(a_{i}) . This sequence is a -admissible with respect to \mu if it is admissible with respect to \mu and m_{k}a_{k} is a prefix of \mu(a) . When the context is clear, we simply say admissible or a -admissible without specifying the substitution. See Fig. 1 for an illustration. \mu^{0}(a) a \mu(a) m_{2} a_{2} \mu^{2}(a) \mu(m_{2}) m_{1} a_{1} \mu^{3}(a) \mu^{2}(m_{2}) \mu(m_{1}) m_{0} a_{0} Figure 1 : An illustration of what it means for a sequence ((m_{i},a_{i}))_{0\leq i\leq 2} to be a -admissible with respect to a substitution \mu . {example} Consider the Tribonacci substitution \tau\colon a\mapsto ab,b\mapsto ac,c\mapsto a . The tree \mathcal{T}_{\tau,a} in Fig. 2 is defined as in Section 2 and allows us to compute a -admissible sequences. For instance, the sequence (m_{0},a_{0})=(\varepsilon,a),(m_{1},a_{1})=(\varepsilon,a),(m_{2},a_{2})=(a,b) is a -admissible and corresponds to the path in bold in \mathcal{T}_{\tau,a} . Note that the sequences (a,c),(a,b) and (a,c),(a,b),(\varepsilon,a) are also a -admissible and lead to nodes labeled by c and colored (in orange) in \mathcal{T}_{\tau,a} , both in column 3 . a b c 0 1 0 1 0 (a) a a b a b a c a b a c a b a 0 1 2 3 4 5 6 0 1 0 1 0 1 0 1 0 1 0 1 0 (b) Figure 2 : On the left, the directed graph associated with the Tribonacci substitution \tau\colon a\mapsto ab,b\mapsto ac,c\mapsto a . On the right, the tree \mathcal{T}_{\tau,a} displays all a -admissible sequences of length at most 3 for the Tribonacci substitution \tau and growing letter a . As illustrated in Section 2.1 , given a right-infinite fixed point of a substitution, multiple paths in the corresponding tree can lead to nodes in the same column. However, there is a unique path starting from the root of the tree and labeled by a word not starting with 0 . The following result, shown by Dumont and Thomas, essentially formalizes this and states that there is a unique admissible sequence for every prefix of the fixed point. 2.1 . [ 6 , Theorem 1.5] Let a\in A and let \mu:A^{*}\to A^{*} be a substitution. Let u be a right-infinite fixed point of \mu with growing seed u_{0}=a . For every integer n\geq 1 , there exist a unique integer k=k(n) and a unique sequence ((m_{i},a_{i}))_{i=0,\dots,k-1} such that the sequence is a -admissible, m_{k-1}\neq\varepsilon , and u_{0}u_{1}\cdots u_{n-1}=\mu^{k-1}(m_{k-1})\mu^{k-2}(m_{k-2})\cdots\mu^{0}(m_{0}) . Theorem 2.1 allows to define a numeration system for non-negative integers as defined below. {definition} Let \mu\colon A^{*}\to A^{*} be a substitution, a be a growing letter, and u be a right-infinite fixed point of \mu with seed u_{0}=a . Set \texttt{c}=\max_{b\in A}|\mu(b)|-1 and define the set D=\{\texttt{0},\texttt{1},\ldots,\texttt{c}\} . We define the map \rep_{\mu,a}\colon\N\to D^{*},n\mapsto\rep_{\mu,a}(n) by \rep_{\mu,a}(n)=\begin{cases}\varepsilon,&\text{if $n=0$};\\ |m_{k-1}|\cdot|m_{k-2}|\cdots|m_{0}|,&\text{if $n\geq 1$};\end{cases} where k=k(n) is the unique integer and ((m_{i},a_{i}))_{i=0,\dots,k-1} is the unique sequence from Theorem 2.1 . This numeration system is called the Dumont–Thomas numeration system associated with \mu and u . Note that we use a special font for the digits representing numbers to distinguish them from integers. Note also that \rep_{\mu,a}(n) is the label of the shortest path from the root to a node in column n in the tree \mathcal{T}_{\mu,a} . {example} We resume Section 2.1 . The representation of the first few non-negative integers for the Tribonacci substitution \tau and growing letter a are given in Table 1 . Table 1 : The representation of the first few non-negative integers in the Dumont–Thomas numeration system for \tau and a , where \tau\colon a\mapsto ab,b\mapsto ac,c\mapsto a is the Tribonacci substitution. n 0 1 2 3 4 5 6 \rep_{\tau,a}(n) \varepsilon 1 10 11 100 101 110 In [ 11 ] , the authors proposed an extension of the numeration system given in Section 2.1 to all integers. The next two results generalize Theorem 2.1 to right- and left-infinite periodic points of substitutions with a growing letter. 2.2 . [ 11 , Theorem 4.1] Let \mu:A^{*}\to A^{*} be a substitution with growing letter a\in A . Consider a right-infinite periodic point u\in\Per_{\N}(\mu) with u_{0}=a and period p\geq 1 . For every integer n\geq 1 , there exist a unique integer k=k(n) such that p divides k and a unique sequence ((m_{i},a_{i}))_{i=0,\dots,k-1} such that the sequence is a -admissible, m_{k-1}m_{k-2}\cdots m_{k-p}\neq\varepsilon , and u_{0}u_{1}\cdots u_{n-1}=\mu^{k-1}(m_{k-1})\mu^{k-2}(m_{k-2})\cdots\mu^{0}(m_{0}) . 2.3 . [ 11 , Theorem 4.2] Let \mu:A^{*}\to A^{*} be a substitution with growing letter b\in A . Consider a left-infinite periodic point u\in\Per_{\Z_{<0}}(\mu) with u_{-1}=b and period p\geq 1 . For every integer n\leq-2 , there exist a unique integer k=k(n) such that p divides k and a unique sequence ((m_{i},a_{i}))_{i=0,\dots,k-1} such that the sequence is b -admissible, \mu^{p-1}(m_{k-1})\mu^{p-2}(m_{k-2})\cdots\mu^{0}(m_{k-p})a_{k-p}\neq\mu^{p}(b), and u_{-|\mu^{k}(b)|}\cdots u_{n-2}u_{n-1}=\mu^{k-1}(m_{k-1})\mu^{k-2}(m_{k-2})\cdots\mu^{0}(m_{0}) . Similarly to Section 2.1 , the combination of Theorems 2.2 and 2.3 allows to define a numeration system for all integers as defined below. {definition} [ 11 , Definition 4.3] Let \mu\colon A^{*}\to A^{*} be a substitution and let u\in\Per_{\Z}(\mu) be a two-sided periodic point with growing seed u_{-1}|u_{0} and period p\geq 1 . Define \texttt{c}=\max_{a\in A}|\mu(a)|-1 and the set D=\{\texttt{0},\texttt{1},\ldots,\texttt{c}\} . We define the map \rep_{u}\colon\Z\to\{\texttt{0},\texttt{1}\}D^{*},n\mapsto\rep_{u}(n) by \rep_{u}(n)=\begin{cases}\texttt{0}\cdot|m_{k-1}|\cdot|m_{k-2}|\cdots|m_{0}|,&\text{if $n\geq 1$};\\ \texttt{0},&\text{if $n=0$};\\ \texttt{1},&\text{if $n=-1$};\\ \texttt{1}\cdot|m_{k-1}|\cdot|m_{k-2}|\cdots|m_{0}|,&\text{if $n\leq-2$};\end{cases} where if n\geq 1 (resp., n\leq-2 ), k=k(n) is the unique integer and ((m_{i},a_{i}))_{i=0,\dots,k-1} is the unique sequence obtained from Theorem 2.2 (resp., Theorem 2.3 ) applied on the right-infinite periodic point u|_{\N}=u_{0}u_{1}\cdots (resp., the left-infinite periodic point u|_{\Z_{<0}}=\cdots u_{-2}u_{-1} ) with period p . This numeration system is called the Dumont–Thomas complement numeration system associated with u . Observe that all representations of non-negative integers start with a letter 0 while those of negative integers start with a letter 1 . Again, we use a special font for the digits in the representations of integers. Also note that, if we get rid of the initial letter, the lengths of all representations are multiples of p . Using the tree interpretation, this generalization corresponds to using the tree \mathcal{T}_{\mu,u_{-1}|u_{0}} to accommodate negative numbers, and using only paths of length one plus a multiple of p to manage periodicity. {example} Consider the substitution \mu\colon a\mapsto abc,b\mapsto c,c\mapsto ac and the two-sided periodic point u\in\Per_{\Z}(\mu) with growing seed c|a . (Note that the period of u is 1 , so it is actually a fixed point.) The corresponding tree \mathcal{T}_{\mu,c|a} is depicted in while the corresponding Dumont–Thomas numeration system is illustrated in . For instance, the paths 02 and 002 lead to the nodes in orange, which both project onto n=2 on the horizontal line below the tree. To represent this integer n=2 , we need to take the path leading to the earliest level having a node projecting onto n=2 , so \rep_{u}(2)=\texttt{02} . start a a b c a b c c a c c a c a b c a c -5 -4 -3 -2 -1 0 1 2 3 4 5 0 1 0 1 2 0 1 2 0 0 1 0 1 0 1 2 0 1 (a) n path \rep_{u}(n) -5 100 100 -4 101 101 -3 102 102 -2 110 10 -1 111 1 0 000 0 1 001 01 2 002 02 3 010 010 4 020 020 5 021 021 (b) Figure 3 : On the left, the tree associated \mathcal{T}_{\mu,c|a} with the two-sided periodic point u of the substitution \mu\colon a\mapsto abc,b\mapsto c,c\mapsto ac with growing seed c|a . On the right, the representations of the first few integers in the corresponding Dumont–Thomas complement numeration system. In the next example, we consider two substitutions associated with the same real number. The key observation is that one gives rise to a numeration system that is positional, and the numeration system for the other is not. This example is already present in Lepšová’s PhD thesis [ 13 ] . {example} [ 13 , Example 6.5.6] Consider the silver mean \beta=1+\sqrt{2} . We define the substitutions \mu\colon a\mapsto aab,b\mapsto a and \rho\colon a\mapsto abb,b\mapsto ab . The characteristic polynomials of the corresponding adjacency matrices of \mu and \rho are equal and have dominant root \beta . We now consider the two-sided periodic points u\in\Per_{\Z}(\mu) with growing seed b|a and period 2 and v\in\Per_{\Z}(\rho) with growing seed b|a and period 1 . The representations of the few integers in the corresponding Dumont–Thomas numeration systems with r=0 are given in Table 2 . We observe that the first numeration system is positional while the second is not. Indeed, if it were, there would be an evaluation map \val such that \val(\rep_{v,0}(n))=n for all integers n . Since \rep_{v,0}(3)=\texttt{010} , we must have U_{1}=3 , but then \val(\rep_{v,0}(5))=\val(\texttt{020})=6\neq 5 , a contradiction. Table 2 : The representations of the first few integers in the Dumont–Thomas numeration system associated with u\in\Per_{\Z}(\mu) and v\in\Per_{\Z}(\rho) and r=0 where \mu\colon a\mapsto aab,b\mapsto a and \rho\colon a\mapsto abb,b\mapsto ab , both with seed b|a . n -5 -4 -3 -2 -1 0 1 2 3 4 5 \rep_{u,0}(n) 10112 10120 100 101 1 0 001 002 010 011 012 \rep_{v,0}(n) 100 101 102 10 1 0 01 02 010 011 020 As suggested by the previous example, Dumont–Thomas numeration systems for \Z corresponding to periodic points of substitution are not always positional. Therefore, Lepšová raised the following natural question [ 13 ] . Question B . [ 13 , Question 6.5.7] What are the conditions for a complement Dumont–Thomas numeration system to be positional? 2.2 Changing the lengths in the numeration language As already observed, Theorems 2.2 and 2.3 both provide a numeration language whose words are of length multiple of the period p of the considered infinite word. In this section, we show that this is a superfluous restriction and we show that all lengths can be attained modulo p , a fact which is clear when considering the tree interpretation. We start with right-infinite periodic points. 2.4 . Let \mu:A^{*}\to A^{*} be a substitution with growing letter a\in A . Consider a right-infinite periodic point u\in\Per_{\N}(\mu) with u_{0}=a and period p\geq 1 . Fix a residue r\in\{0,1,\ldots,p-1\} modulo p and define v_{r}=\mu^{r}(u) . For every integer n\geq 0 , there exist a unique integer k=k(n) with k\equiv r\bmod p and a unique sequence ((m_{i},a_{i}))_{i=0,\dots,k-1} such that the sequence is a -admissible, m_{k-1}m_{k-2}\cdots m_{k-p}\neq\varepsilon\text{ if }k\geq p, (1) and (v_{r})_{[0,n-1]}=\mu^{k-1}(m_{k-1})\mu^{k-2}(m_{k-2})\cdots\mu^{0}(m_{0}) . The proof of Theorem 2.4 mimics that of Theorem 2.2 but we choose to present it for the sake of completeness. Some intermediate results are necessary, which we recall too. {lemma} [ 6 , Lemma 1.1] Let \mu\colon A^{*}\to A^{*} be a substitution and let k\geq 0 be an integer. If ((m_{i},a_{i}))_{i=0,\dots,k} in an admissible sequence, then \sum_{i=0}^{k}\left|\mu^{i}(m_{i})\right|<\left|\mu^{k}(m_{k}a_{k})\right| . {lemma} [ 11 , Lemma 3.9] Let \mu\colon A^{*}\to A^{*} be a substitution and let k\geq 0 be an integer. Let also m\in A^{*} and a\in A be such that m is a proper prefix of \mu^{k}(a) . Then there exists a unique a -admissible sequence ((m_{i},a_{i}))_{i=0,\dots,k-1} such that m=\mu^{k-1}(m_{k-1})\mu^{k-2}(m_{k-2})\cdots\mu^{0}(m_{0}) . Proof of Theorem 2.4 . Since a is a growing letter, the sequence (\left|\mu^{\ell p+r}(a)\right|)_{\ell\geq 0} is (strictly) increasing. Note that, for every r\in\{0,1,\ldots,p-1\} , the word v_{r} is also a periodic point of \mu with period p . Let n\geq 0 be an integer. Setting \left|\mu^{-p+r}(a)\right|=0 by convention, there exists a unique integer \ell=\ell(n)\geq 0 such that \left|\mu^{(\ell-1)p+r}(a)\right|\leq n<\left|\mu^{\ell p+r}(a)\right| . Let k=k(n)=\ell p+r be such that \left|\mu^{k-p}(a)\right|\leq n<\left|\mu^{k}(a)\right|. (2) Now the word m=v_{r,0}v_{r,1}\cdots v_{r,n-1} of length n is a proper prefix of \mu^{k}(a) (for a visualization, recall that the k -th level of the tree \mathcal{T}_{\mu,a} is a prefix of v_{r} since k\equiv r\bmod p ). By Section 2.2 , there exists a unique a -admissible sequence ((m_{i},a_{i}))_{i=0,\dots,k-1} such that m=\mu^{k-1}(m_{k-1})\cdots\mu^{0}(m_{0}) . It remains to show that m_{k-1}m_{k-2}\cdots m_{k-p}\neq\varepsilon if k\geq p . Towards a contradiction, we assume that k\geq p and m_{k-1}m_{k-2}\cdots m_{k-p}=\varepsilon . By inspecting the definition of admissible sequences with periodic points, it means that a_{k-p}=a . Then Section 2.2 implies that \displaystyle n \displaystyle=\left|m\right|=\sum_{j=0}^{k-1}\left|\mu^{j}(m_{j})\right|=\sum_{j=0}^{k-p-1}\left|\mu^{j}(m_{j})\right| \displaystyle<\left|\mu^{k-p-1}(m_{k-p-1}a_{k-p-1})\right|\leq\left|\mu^{k-p-1}(\mu(a_{k-p}))\right|=\left|\mu^{k-p}(a)\right|, which contradicts Eq. 2 . Consequently, m_{k-1}m_{k-2}\cdots m_{k-p}\neq\varepsilon , which finishes the proof of existence. For uniqueness, we already know that the sequence ((m_{i},a_{i}))_{i=0,\ldots,k-1} constructed above is the only a -admissible sequence of length k that satisfies the conditions of the statement. It remains to show that other lengths do not lead to more such sequences. First, suppose that ((m^{\prime}_{i},a^{\prime}_{i}))_{i=0,\ldots,k^{\prime}-1} is an a -admissible sequence of length k^{\prime} with k^{\prime}k , we note that the sequence obtained by prefixing (m_{k^{\prime}-1},a_{k^{\prime}-1})=(\varepsilon,\mu(a)_{0}),(m_{k^{\prime}-2},a_{k^{\prime}-2})=(\varepsilon,\mu^{2}(a)_{0}),\ldots,(m_{k},a_{k})=(\varepsilon,\mu^{k^{\prime}-k}(a)_{0}) to the sequence ((m_{i},a_{i}))_{i=0,\ldots,k-1} produces an a -admissible sequence of length k^{\prime} which is such that m=\mu^{k^{\prime}-1}(m_{k^{\prime}-1})\cdots\mu^{0}(m_{0}) . By Section 2.2 , this is the only such sequence of length k^{\prime} . But this sequence starts with m_{k^{\prime}-1}=\cdots=m_{k^{\prime}-p}=\varepsilon , and thus it does not satisfy the statement. Thus the uniqueness is shown. ∎ We now move to left-infinite periodic points. 2.5 . Let \mu:A^{*}\to A^{*} be a substitution with growing letter b\in A . Consider a left-infinite periodic point u\in\Per_{\Z_{<0}}(\mu) with u_{-1}=b and period p\geq 1 . Fix a residue r\in\{0,1,\ldots,p-1\} modulo p and define v_{r}=\mu^{r}(u) . For every integer n\leq-1 , there exist a unique integer k=k(n) with k\equiv r\bmod p and a unique sequence ((m_{i},a_{i}))_{i=0,\dots,k-1} such that the sequence is b -admissible, \mu^{p-1}(m_{k-1})\mu^{p-2}(m_{k-2})\cdots\mu^{0}(m_{k-p})a_{k-p}\neq\mu^{p}(b)\text{ if }k\geq p, (3) and (v_{r})_{[-|\mu^{k}(b)|,n-1]}=\mu^{k-1}(m_{k-1})\mu^{k-2}(m_{k-2})\cdots\mu^{0}(m_{0}) . Proof. Note that, for every r\in\{0,1,\ldots,p-1\} , the word v_{r} is also a periodic point of \mu with period p . Since b is a growing letter, the sequence (-\left|\mu^{\ell p+r}(b)\right|)_{\ell\geq 0} is (strictly) decreasing. Let n\leq-1 be an integer. Setting \left|\mu^{-p+r}(b)\right|=0 by convention, there exists a unique integer \ell=\ell(n) such that -\left|\mu^{\ell p+r}(b)\right|\leq n<-\left|\mu^{(\ell-1)p+r}(b)\right| . Let k=k(n)=\ell p+r be such that -\left|\mu^{k}(b)\right|\leq n<-\left|\mu^{k-p}(b)\right|. (4) Now the word m=v_{r,-\left|\mu^{k}(b)\right|}\cdots v_{r,n-2}v_{r,n-1} of length \left|m\right|=\left|\mu^{k}(b)\right|+n<\left|\mu^{k}(b)\right|-\left|\mu^{k-p}(b)\right|\leq\left|\mu^{k}(b)\right| (5) is a proper prefix of \mu^{k}(b) . Using Section 2.2 , there exists a unique b -admissible sequence ((m_{i},a_{i}))_{i=0,\dots,k-1} such that m=\mu^{k-1}(m_{k-1})\mu^{k-2}(m_{k-2})\cdots\mu^{0}(m_{0}) . We now show that Eq. 3 holds. Towards a contradiction, we assume that Eq. 3 is actually an equality. Then we have a_{k-p}=b . Writing m=\mu^{k-p}(\mu^{p-1}(m_{k-1})\cdots\mu^{0}(m_{k-p}))\mu^{k-p-1}(m_{k-p-1})\cdots\mu^{0}(m_{0}), we obtain from Eq. 3 that \left|m\right|=\left|\mu^{k-p}(\mu^{p}(b))\right|-\left|\mu^{k-p}(a_{k-p})\right|+\sum_{j=0}^{k-p-1}\left|\mu^{j}(m_{j})\right|\geq\left|\mu^{k}(b)\right|-\left|\mu^{k-p}(b)\right| which contradicts Eq. 5 . Consequently, Eq. 3 is a non-equality, which finishes the proof of existence. For uniqueness, we already know that the sequence ((m_{i},a_{i}))_{i=0,\ldots,k-1} constructed above is the only b -admissible sequence of length k that satisfies the conditions of the statement. It remains to show that other lengths do not lead to more such sequences. First for k^{\prime}>k , we note that when k\equiv r\bmod p the sequence obtained by prefixing \displaystyle(m_{k^{\prime}-1},a_{k^{\prime}-1}) \displaystyle=(\mu(b)_{[0,\left|\mu(b)\right|-1)},\mu(b)_{\left|\mu(b)\right|-1}), \displaystyle(m_{k^{\prime}-2},a_{k^{\prime}-2}) \displaystyle=(\mu(a_{k^{\prime}-1})_{[0,\left|\mu(a_{k^{\prime}-1})\right|-1)},\mu(a_{k^{\prime}-1})_{\left|\mu(a_{k^{\prime}-1})\right|-1}), \displaystyle(m_{k},a_{k}) \displaystyle=(\mu(a_{k+1})_{[0,\left|\mu(a_{k+1})\right|-1)},\mu(a_{k+1})_{\left|\mu(a_{k+1})\right|-1}) to the sequence ((m_{i},a_{i}))_{i=0,\ldots,k-1} produces a b -admissible sequence of length k^{\prime} which is such that v_{[-\left|\mu^{k^{\prime}}(b)\right|,n-1]}=\mu^{k^{\prime}-1}(m_{k^{\prime}-1})\cdots\mu^{0}(m_{0}) . By Section 2.2 , this is the only such sequence of length k^{\prime} . But this sequence violates Eq. 3 . For the case k^{\prime}1 , then we add c to E_{j} if it was not already present. If \left|\mu^{p-j}(d)\right|=1 and j\leq r

1 . The only case where the equality can hold is if p_{i}c=m_{i} and s_{i}=a_{i} . Next, remember that the sequence ((m_{i},a_{i}))_{i=0,\ldots,k-1} must satisfy \mu^{p-1}(m_{k-1})\mu^{p-2}(m_{k-2})\cdots\mu^{0}(m_{k-p})a_{k-p}\neq\mu^{p}(b) . Thus, the equality can only occur if k-i

1 , otherwise we would have \displaystyle\mu^{k-i-1}(m_{k-1})\cdots\mu^{0}(m_{i})a_{i}=\mu^{k-i}(b) \displaystyle\Rightarrow \displaystyle\mu^{p-k+i}\left(\mu^{k-i-1}(m_{k-1})\cdots\mu^{0}(m_{i})a_{i}\right)=\mu^{p}(b) \displaystyle\Rightarrow \displaystyle\mu^{p-1}(m_{k-1})\cdots\mu^{p-k+i}(m_{i})\mu^{p-k+i}(a_{i})=\mu^{p}(b) \displaystyle\Rightarrow \displaystyle\mu^{p-1}(m_{k-1})\mu^{p-2}(m_{k-2})\cdots\mu^{0}(m_{k-p})a_{k-p}=\mu^{p}(b) as \mu^{p-k+i-1}(m_{i-1})\cdots a_{k-p} is a prefix of length at least 1 of \mu^{p-k+i}(a_{i}) , which has length 1 . The last equality we obtain is a contradiction, so k-i

1 . Thus, we have proven that c belongs to E_{k-i\bmod p} in all cases. From there, we get that n=-\left|\mu^{k}(b)\right|+\sum_{i=0}^{k-1}\left|\mu^{i}(m_{i})\right|=-\left|\mu^{k}(b)\right|+\sum_{i=0}^{k-1}\left|m_{i}\right|U_{i}, where the second equality follows because all the letters of m_{i} are in E_{k-i\bmod p} . Due to Eq. 16 , we get that the numeration system is positional with sequences U,V of weights as defined above. Case 3 . Only the case where n=-1 remains. Here, we have a sequence ((m_{i},a_{i}))_{i=0,\ldots,r-1} with \mu^{r-1}(m_{r-1})\cdots\mu^{0}(m_{0})a_{0}=\mu^{r}(b) . All the letters of m_{i} except the last one are guaranteed to be in E_{k-i\bmod p} as in the previous case. For the last letter of m_{i} , either it is in E_{k-i\bmod p} or condition Eq. 7 applies. In any case, we have \left|\mu^{i}(c)\right|=U_{i} , and the rest of the argument is as for Case 2. In all three cases, we have shown the numeration system to be positional: for every i\geq 0 , the weights U_{i} are defined by the constant value of c\mapsto\left|\mu^{i}(c)\right| over E_{r-i\bmod p} , while the weights V_{i} are equal to \left|\mu^{i}(b)\right| . This concludes the proof of the main result. ∎ {remark} Note that replacing the substitution by one of its powers may lead to lose the positionality of the corresponding numeration system. For instance, consider the substitution \mu\colon a\mapsto ccd,b\mapsto cd,c\mapsto ab,d\mapsto a from Section 2.2 and its square renamed \nu\colon a\mapsto ababa,b\mapsto aba,c\mapsto ccdcd,d\mapsto ccd . From before, we already know that the Dumont–Thomas numeration system associated with \mu and the periodic point of \mu starting with a of period 2 is positional. However, that associated with \nu and its fixed point starting with a is not. Indeed, drawing the first two levels of the tree \mathcal{T}_{\nu,a} we obtain that the representation of 5 is 10 and that of 8 is 20 , making it impossible to find a suitable evaluation map for the numeration system to be positional. This is as expected from our Theorem 3.1 as a and b are both in E_{0} but have images of different lengths. 3.3 Particular cases In this section, we highlight some general cases where the technicalities of Section 3.2 do not occur, leading to results that are more concise and legible. We also discuss possible simplifications of the substitution at play, as well as a parallel to Bertrand numeration systems. From now on, we assume that the alphabet A of the substitution \mu is minimal, i.e, all the letters in A are present in \mu^{n}(b|a) for some n , where b|a designates the seed of the periodic point u of \mu . Given a substitution \mu , we say that a letter c is non-final if there exist d\in A , x\in A^{*} , and y\in A^{+} such that \mu(d)=xcy . We let E_{\mu} denote the set of non-final letters of \mu . When there is no ambiguity, we drop the subscript. We start with the case where the domain \D is equal to \N and the substitution \mu has a fixed point. In this case, the period p is equal to 1 and there is only one sequence of weights, with no particular care given to the most significant digit in a representation. {corollary} Let \mu\colon A^{*}\to A^{*} be a substitution and u=u_{0}u_{1}\cdots be a right-infinite fixed point of \mu with growing seed a . Then the Dumont–Thomas numeration system (for \N ) associated with \mu , u and r=0 is positional if and only if the map c\mapsto\left|\mu^{\ell}(c)\right| is constant over E_{\mu} for every \ell , in which case the sequence of weights is equal to U_{\ell}=\left|\mu^{\ell}(a)\right| for every \ell\geq 0 . Proof. Note that since a is the growing seed of a fixed point of \mu , we must have \mu(a)=ay for some non-empty word y , so a\in E_{\mu} . Note also that since the domain is \N , Section 3.2 does not apply. It then suffices to apply the proof of Theorem 3.1 restricted to the domain \N , taking into account that, since p=1 and r=0 in our case, the set E_{\mu} is equal to the set E_{0} of Theorem 3.1 , which is the only set for which we have conditions to check. ∎ Another special case is that of primitive substitutions, even on the complete domain \D=\Z . Recall that the definition of primitive substitutions was given in Section 2 , where we mentioned that if \mu is primitive then there exists k such that a\in\mu^{\ell}(b) for all a,b\in A and \ell\geq k . {corollary} Let \mu\colon A^{*}\to A^{*} be a primitive substitution and let u\in\Per_{\Z}(\mu) be a two-sided periodic point with growing seed b|a and period p\geq 1 . The Dumont–Thomas complement numeration system associated with \mu , u , and r is positional if and only if the map c\mapsto\left|\mu^{\ell}(c)\right| is constant over E_{\mu} for every \ell\geq 0 . In this case, for every \ell\geq 0 , U_{\ell} is the constant value of \left|\mu^{\ell}(\cdot)\right| over E_{\mu} and V_{\ell}=\left|\mu^{\ell}(b)\right| . Proof. Let k be an integer such that, for all letters c,d\in A , for all \ell>k , c appears in \mu^{\ell}(d) . We then know that every letter appears at every sufficiently large level in the tree \mathcal{T}_{\mu,a} . In particular, b appears in \mu^{k}(a) , so \mathcal{T}_{\mu,b} appears as a subtree of \mathcal{T}_{\mu,a} . Therefore, any letter that appears with a younger sibling on column -2 also appears with a younger sibling on some column with non-negative index. As a result, Section 3.2 can be skipped when determining the sets E_{j} and condition Eq. 7 is never relevantly added to any letter. Next, we show that, for every j\in\{0,\ldots,p-1\} , E_{j}=E_{\mu} . Fix some j\in\{0,\ldots,p-1\} . As the inclusion E_{j}\subseteq E_{\mu} is clear by Section 3.2 we show the other one. If c\in E_{\mu} , there exist d\in A , x\in A^{*} , and y\in A^{+} such that \mu(d)=xcy . Since \mu is primitive, d appears in \mu^{j-1+\ell p}(a) for some sufficiently large \ell , so c appears with a younger sibling at some level j+\ell p in the tree \mathcal{T}_{\mu,b|a} . This implies that c\in E_{j} , as desired. Finally, notice that since a is a growing letter of \mu , at least one letter must have an image by \mu that is of length at least 2 , thus E_{\mu} is nonempty. Now that we have shown that E_{j}=E_{\mu}\neq\emptyset for every j\in\{0,\ldots,p-1\} and that condition Eq. 7 is not relevant to any letter, applying Theorem 3.1 leads to the statement. ∎ The substitutions that generate the positional Dumont–Thomas numeration systems discussed in the two corollaries above turn out to have a special form as we will see. This form lends itself well to simplifications and will allow us to link these positional numeration systems to some known families of numeration systems. The following lemma shows that these substitutions are equivalent (in the sense that they generate the same Dumont–Thomas numeration system) to a substitution that contains only one non-final letter. {lemma} Let \mu\colon A^{*}\to A^{*} be a substitution such that the map c\mapsto\left|\mu^{\ell}(c)\right| is constant over E_{\mu} for every integer \ell\geq 0 . Then there exist an alphabet B\subseteq A , a substitution \nu\colon B^{*}\to B^{*} such that \left|E_{\nu}\right|=1 and some letters a^{\prime},b^{\prime}\in B such that the trees \mathcal{T}_{\mu,b|a} and \mathcal{T}_{\nu,b^{\prime}|a^{\prime}} differ only by their labeling. Proof. Before showing that the statement holds, we start with some notation. For an integer k\geq 0 and a letter a\in A , we let \mathcal{T}_{\mu,a}^{\leq k} denote the first k levels of the tree \mathcal{T}_{\mu,a} (agreeing that the root is on level 0 ). Additionally, we extend our definition of trees associated with substitutions to forests associated with substitutions: if w=w_{1}\ldots w_{n} is a word over A , then \mathcal{T}_{\mu,w} is the ordered forest where the first tree is \mathcal{T}_{\mu,w_{1}} , the second tree is \mathcal{T}_{\mu,w_{2}} , and so on. We define similarly \mathcal{T}_{\mu,w}^{\leq k} for any integer k\geq 0 . Now we prove the following claim: for every integer k\geq 0 and for every pair of letters c,d\in E_{\mu} , the trees \mathcal{T}_{\mu,c}^{\leq k} and \mathcal{T}_{\mu,d}^{\leq k} differ only by their labeling. Proving this for every k will also show it for the entire trees. We proceed by induction on k\geq 0 . The case k=0 is trivial as we start with letters. The case k=1 is obtained directly from the hypothesis for \ell=1 . Indeed, c and d must have the same number of children as they are both in E_{\mu} by assumption. Now, assume that the claim holds for k and let us prove it for k+1 . We inductively define \mu(c)=x_{1}c_{1} and \mu(c_{i})=x_{i+1}c_{i+1} for every i\geq 1 , where x_{i}\in A^{*} and c_{i}\in A for every i\geq 1 (see Fig. 7 ). Similarly, we define \mu(d)=y_{1}d_{1} and \mu(d_{i})=y_{i+1}d_{i+1} for every i\geq 1 with the same constraints on y_{i} and d_{i} . The induction hypothesis ensures that \mathcal{T}_{\mu,c}^{\leq k} and \mathcal{T}_{\mu,d}^{\leq k} only differ by their labeling. Still from the induction hypothesis, the same is true for \mathcal{T}_{\mu,x_{1}}^{\leq k} and \mathcal{T}_{\mu,y_{1}}^{\leq k} and, more generally, for \mathcal{T}_{\mu,x_{i}}^{\leq k+1-i} and \mathcal{T}_{\mu,y_{i}}^{\leq k+1-i} with i\in\{1,\ldots,k\} (letters of the words x_{i},y_{i} are non-final by definition). See Fig. 7 for a more visual explanation. c x_{1} c_{1} \mu(x_{1}) x_{2} c_{2} \mu^{2}(x_{1}) \mu(x_{1}) x_{3} c_{3} \vdots \vdots \vdots \vdots \ddots \ddots x_{k} c_{k} \mu^{k}(x_{1}) \mu^{k-1}(x_{2}) \mu^{k-2}(x_{3}) \mu(x_{k}) x_{k+1} c_{k+1} Figure 7 : In the proof of Section 3.3 , given a letter c , we inductively define \mu(c)=x_{1}c_{1} and \mu(c_{i})=x_{i+1}c_{i+1} for every i\geq 1 , where x_{i} is a word and c_{i} is a letter for every i\geq 1 . We draw the tree \mathcal{T}_{\mu,c}^{\leq k+1} as defined in the proof of Section 3.3 . Black rectangles correspond to words (note that we do not give information on the length here) and black circles to letters. The induction hypothesis tells us that, up to labeling, every color-framed subtree is equal to its corresponding subtree in \mathcal{T}_{\mu,d}^{\leq k+1} . As a result, to conclude the proof of the claim, we only need to check that c_{k} and d_{k} have the same number of children, i.e., \left|\mu(c_{k})\right|=\left|\mu(d_{k})\right| . Since \left|\mu^{k+1}(c)\right|=\sum_{i=1}^{k}\left|\mu^{k+1-i}(x_{i})\right|+\left|\mu(c_{k})\right|\quad\text{ and }\quad\left|\mu^{k+1}(d)\right|=\sum_{i=1}^{k}\left|\mu^{k+1-i}(y_{i})\right|+\left|\mu(d_{k})\right|, we have \left|\mu(c_{k})\right|=\left|\mu^{k+1}(c)\right|-\sum_{i=1}^{k}\left|\mu^{k+1-i}(x_{i})\right|=\left|\mu^{k+1}(d)\right|-\sum_{i=1}^{k}\left|\mu^{k+1-i}(y_{i})\right|=\left|\mu(d_{k})\right|, where the second equality results from our hypothesis (all the letters in x_{i} and y_{i} belong to E_{\mu} , as do c and d ). Thus the claim is proved. Now that we have proven that \mathcal{T}_{\mu,c} and \mathcal{T}_{\mu,d} only differ by their labeling, we may replace every instance of the letter d in an image of \mu by the letter c and this will only change the labeling of the tree \mathcal{T}_{\mu,b|a} , not its shape. If we proceed like this for every letter d in E_{\mu}\setminus\{c\} and then remove any such superfluous letter from the alphabet A , we will have constructed the desired substitution \nu . ∎ {example} Consider the primitive substitution \mu\colon a\mapsto ab,b\mapsto ba (often referred to as the Thue–Morse substitution). We note that both a,b are non-final letters and \left|\mu^{\ell}(c)\right|=2^{\ell} for c\in\{a,b\} and for every \ell\geq 0 . Applying our result gives the substitution \nu\colon a\mapsto a^{2} . The corresponding Dumont–Thomas numeration system (over \N ) is the usual binary system. As a consequence, when considering positional Dumont–Thomas numeration systems associated with either primitive substitutions or fixed points on the domain \N (namely, the assumptions of Sections 3.3 and 3.3 ) we may look only at substitutions having one single non-final letter e by Section 3.3 . In such a substitution, the image of a letter is determined by the number of repetitions of the non-final letter e and the choice of final letter. If we let a be the seed of the periodic point u , it must be that \mu^{\ell}(a) starts with e for some \ell . In order for u to be a periodic point, we must have either e=a (Case 1) or a chain of letters that all have images of length 1 , say e\mapsto b_{1}\mapsto b_{2}\mapsto\cdots\mapsto b_{k}\mapsto a (Case 2). In all other cases, no iterated image of e starts with a , and u cannot be a periodic point as a result. In what follows, we will try to link these substitutions to established literature on numeration systems. However, note that in most common systems, representations may take any length, which corresponds in our case to the substitution having a fixed point, and therefore to Case 1 above. As a result, we will solely focus on this case where e=a is both the seed of the periodic point and the only non-final letter. In this case, with the extra condition to operate on the minimal alphabet, the substitution is equivalent to one of the form \mu:a_{1}\mapsto a_{1}^{d_{1}}a_{2},a_{2}\mapsto a_{1}^{d_{2}}a_{3},\ldots,a_{n}\mapsto a_{1}^{d_{n}}a_{k}, (17) where n is a non-negative integer, \{a_{1},\ldots,a_{n}\} is the alphabet of the substitution, k\in\{1,\ldots,n\} , d_{1}>0 and d_{i} is a non-negative integer for every i\in\{1,\ldots,n\} . An example of such a substitution is the Fibonacci (resp. , Tribonacci) substitution given by \varphi\colon a\mapsto ab,b\mapsto a (resp., \tau\colon a\mapsto ab,b\mapsto ac,c\mapsto a ), for which n=2 , a_{1}=a , a_{2}=b , d_{1}=1 , d_{2}=0 , and k=1 (resp., n=3 , a_{1}=a , a_{2}=b , a_{3}=c , d_{1}=d_{2}=1 , d_{3}=0 , and k=1 ). See also their generalization to generic n -bonacci substitutions in [ 18 , Ex 2.11] . The similarity with the substitutions studied by Fabre in [ 7 ] is striking, so we will call Fabre-like the substitutions of the form Eq. 17 . We will now study this particular class of substitutions in additional detail. First, we note the following property. {proposition} Let \mu and \mu^{\prime} be Fabre-like substitutions and consider their respective fixed points u and u^{\prime} with respective seeds a and a^{\prime} . If the Dumont–Thomas numeration systems over \N corresponding to u and u^{\prime} respectively and r=0 have the same sequence of weights, then every natural number has the same representation in both numeration systems. In a sense, the weight sequence completely determines the numeration system provided that it is based on a Fabre-like substitution. In what follows, we will call two numeration systems over \N equal if every natural number is represented by the same word in both systems. Note that this property does not hold in general as shown in the next example. {example} Consider the substitutions \mu\colon a\mapsto bcd,\,b\mapsto ef,\,c\mapsto e^{2}g,\,d\mapsto d,\,e\mapsto ad,\,f\mapsto a^{2}d,\,g\mapsto a and \mu^{\prime} defined in the same way but with \mu^{\prime}(a)=cbd instead of bcd . Then, if u and u^{\prime} are the periodic points of period p=3 starting with a of \mu and \mu^{\prime} respectively and r=0 , the corresponding Dumont–Thomas numeration systems associated with u and r and with u^{\prime} and r have the same sequence of weights, but the representations of some numbers differ: for example, we have \rep_{u,0}(4)=\texttt{012} , \rep_{u^{\prime},0}(4)=\texttt{020} , \rep_{u,0}(9)=\texttt{120} , and \rep_{u^{\prime},0}(9)=\texttt{112} . Sketch of the proof of Section 3.3 . From the equality of the weight sequences, we deduce that \left|\mu^{\ell}(a)\right|=\left|\mu^{\prime\ell}(a^{\prime})\right| for every integer \ell as a\in E_{\mu} and a^{\prime}\in E_{\mu^{\prime}} . Then, we prove that, for every k\geq 0 , the pair of trees \mathcal{T}_{\mu,a}^{\leq k} and \mathcal{T}_{\mu^{\prime},a^{\prime}}^{\leq k} differ only by their labeling, using the same method as for the claim in Section 3.3 . Since the two trees differ only by their labeling, \rep_{u,0}(n)=\rep_{u^{\prime},0}(n) for every natural number n . ∎ Let us quickly recall some other milestones of numeration systems. For the reader not familiar with the classical theory and definitions, see, for instance, [ 2 , Chapter 2] and [ 18 , Chapter 2] . In 1957, Rényi [ 19 ] introduced \beta -numeration systems, a way to represent positive real numbers with the help of a real base \beta>1 . Among all non-negative real numbers, 1 is the most distinguishable, and the notation d_{\beta}(1) is used for its representation in base \beta . Additionally, we define its quasi-greedy representation d_{\beta}^{*}(1) to be equal to (d_{1}\cdots d_{\ell-1}(d_{\ell}-1))^{\omega} if d_{\beta}(1)=d_{1}\cdots d_{\ell}0^{\omega} , and d_{\beta}(1) otherwise. Of particular interest are the so-called Parry numbers , which are real numbers \beta such that d_{\beta}(1) is either finite ( \beta is then a simple Parry number) or ultimately periodic [ 17 ] . In an article of Bertrand-Mathis [ 3 ] , later corrected by Charlier, Cisternino and Stipulanti [ 5 ] , a link is made between Rényi numeration systems and some greedy positional numeration systems for natural numbers (numeration systems over \N that are positional in our sense, with the extra condition that the representation can be computed by a greedy algorithm). If we write d_{\beta}^{*}(1)=d_{1}d_{2}\cdots , we define the sequence of weights (U_{i})_{i\geq 0} by U_{0}=1 and the relation U_{i}=d_{1}U_{i-1}+d_{2}U_{i-2}+\ldots+d_{i}U_{0}+1 for each i\geq 1 . In the case where \beta is a Parry number, this relation can be simplified to a linear recurrence relation for (U_{i})_{i\geq 0} . This weight sequence, when combined with a greedy algorithm, defines a positional numeration system called a canonical Bertrand numeration system , which enjoys properties such as the numeration language having the same set of factors as the language of the Rényi numeration system with base \beta . Two other notable properties of such numeration systems are the following: Property 1 . A word w is the representation of some natural number if and only if w0 is. Property 2 . The lexicographically greatest representations of every length are all prefixes of one another. However, these properties characterize Bertrand numeration systems only if we consider all Bertrand numeration systems: in addition to canonical ones, we consider the non-canonical Bertrand numeration systems, obtained just like the canonical ones but with the word d_{\beta}^{*}(1) replaced by d_{\beta}(1) , and the trivial Bertrand numeration system based on the weights U_{i}=i+1 , with i\geq 0 . This is the nature of the correction brought by Charlier et al. in [ 5 ] . A few of years after Bertrand-Mathis’ paper, Fabre [ 7 ] introduced another way to view canonical Bertrand numeration systems. If \beta is a Parry number with d_{\beta}^{*}(1)=d_{1}\cdots d_{n}(d_{n+1}\cdots d_{n+m})^{\omega} for some m,n , we introduce the substitution \displaystyle\mu_{\beta}\colon 1\mapsto 1^{d_{1}}2,\,2\mapsto 1^{d_{2}}3,\ldots,(n+m-1)\mapsto 1^{d_{n+m-1}}(n+m),(n+m)\mapsto 1^{d_{n+m}}(n+1). (18) Note that Fabre defines his substitutions not by using the word d_{\beta}^{*}(1) like we do but using the word d_{\beta}(1) . Still, the substitution in Eq. 18 is the same as the one defined by Fabre. The case where d_{\beta}(1) is finite corresponds to the case where n=0 with our notation. Fabre then shows that |\mu_{\beta}^{\ell}(1)| is the integer U_{\ell} defined for the canonical Bertrand numeration system, and his [ 7 , Theorem 2] establishes the equality between the Dumont–Thomas numeration system associated with \mu_{\beta} and the canonical Bertrand numeration system associated with \beta . As an aside, we note that the term “conjugate substitutions” used by Fabre in [ 7 , Section 3.1] can be thought of in terms of the trees associated with those substitutions. Following Fabre’s notation, for two substitutions \mu\colon A^{*}\to A^{*} and \nu\colon B^{*}\to B^{*} with seeds a\in A and b\in B respectively, we write \mu\rightarrow\nu if there exists a morphism h\colon A^{*}\to B^{*} such that h(a)=b and h(\mu(c))=\nu(h(c)) for every c\in A . We then say that \mu and \nu are conjugates if there exists a third substitution \tau such that \tau\rightarrow\mu and \tau\rightarrow\nu . {proposition} Two substitutions \mu\colon A^{*}\to A^{*} and \nu\colon B^{*}\to B^{*} with respective seeds a and b are conjugate exactly when the trees \mathcal{T}_{\mu,a} and \mathcal{T}_{\nu,b} are equal up to relabeling. Proof. On the one hand, if the trees \mathcal{T}_{\mu,a} and \mathcal{T}_{\nu,b} are equal up to relabeling, we may construct a tree with the same graph structure but with labels in A\times B obtained by simply joining the labels of the corresponding nodes in the two trees. Then, this new tree gives a substitution \mu\times\nu on A\times B that is such that \mu\times\nu\rightarrow\mu and \mu\times\nu\rightarrow\nu , which implies that \mu and \nu are conjugate. On the other hand, if \tau\rightarrow\mu for some substitution \tau , applying the morphism h on the label of every node in the tree associated with \tau gives the tree associated with \mu (which must have the same shape since we only have changed the labels). By applying this result twice, we conclude that the trees associated with two conjugate substitutions have the same shape and differ only by their labeling. ∎ With these milestones recalled, let us go back to the study of our Dumont–Thomas numeration systems based on Fabre-like substitutions. We first note that all Bertrand numeration systems associated with Parry numbers are a particular case of Dumont–Thomas numeration systems (and not just the canonical ones as proven by Fabre). {proposition} Every Bertrand numeration system associated with a Parry number is equal to some Dumont–Thomas numeration system associated with a Fabre-like substitution. Proof. It is clear that the substitution \mu_{\beta} in Eq. 18 introduced by Fabre is Fabre-like when \beta is a Parry number (note that the first digit of d_{\beta}^{*}(1) is nonzero, so d_{1}>1 as expected). Therefore, the canonical Bertrand numeration systems can all be seen as special cases of our Dumont–Thomas numeration systems. The non-canonical Bertrand numeration systems introduced in [ 5 ] also fall in this framework. If d_{\beta}^{*}(1)=(d_{1}\cdots d_{m})^{\omega} , we create \mu_{\beta}^{\prime} from \mu_{\beta} by adding the letter m+1 to the alphabet, setting \mu_{\beta}^{\prime}(m)=1^{d_{m}+1}(m+1) instead of \mu_{\beta}(m)=1^{d_{m}+1} , and setting \mu_{\beta}^{\prime}(m+1)=(m+1) . In a sense, this corresponds to improperly setting d_{\beta}^{*}(1)=d_{1}\cdots d_{m-1}(d_{m}+1)0^{\omega} , then defining a Fabre substitution from this ultimately periodic expansion. Since the trivial Bertrand numeration system based on the weight sequence (i+1)_{i\geq 0} is the Dumont–Thomas numeration system associated with the substitution \mu\colon a\mapsto ab,\,b\mapsto b , which is Fabre-like, we conclude the proof of the statement. ∎ Although our Dumont–Thomas numeration systems clearly verify the two Properties 1 and 2 that characterize Bertrand numeration systems, the converse of Section 3.3 is not true, as we see in the following example. {example} Consider the Fabre-like substitution \mu\colon a\mapsto aab,\,b\mapsto aaaa with fixed point u=aabaabaaaa\cdots . The corresponding Dumont–Thomas numeration system is positional, with the sequence of weights starting by 1,3,10,32,\ldots . We note that \rep_{u,0}(9)=\texttt{23} , but this cannot happen in a Bertrand numeration system as the representation of 9 would be 30 with the given sequence of weights. The catch, of course, is that Dumont–Thomas numeration systems, while positional, do not represent numbers by applying a greedy algorithm on the sequence of weights, but rather by applying a greedy algorithm on the factorization of their fixed point, which can lead to different results. This can be understood with an adaptation of the Parry condition . To recall, this condition (first seen in [ 17 ] , Corollary 1) states that a word d_{1}d_{2}\cdots is equal to d_{\beta}(1) for some \beta>1 if, and only if, d_{1}d_{2}\cdots\succ 10^{\omega} and d_{1}d_{2}\cdots\succ d_{i}d_{i+1}\cdots for every i\geq 1 . In the case of Section 3.3 , if the substitution \mu were the Fabre substitution associated with some Parry number \beta , we would have d_{\beta}^{*}(1)=(23)^{\omega} and d_{\beta}(1)=240^{\omega} , which contradicts the Parry condition. Thus the system cannot be equal to a Bertrand numeration system. In fact, the Parry condition (adapted for use with d_{\beta}^{*}(1) instead of d_{\beta}(1) ) is all that is necessary to guarantee that the system is greedy and therefore equal to a Bertrand numeration system, as we will see in the following result. {proposition} Let \mu be a Fabre-like substitution as in Eq. 17 . Construct the word d_{1}d_{2}\cdots=d_{1}\cdots d_{k-1}(d_{k}\cdots d_{n})^{\omega} . The Dumont–Thomas numeration system associated with \mu and the seed a_{1} is equal to a Bertrand numeration system if and only if we have d_{i}d_{i+1}\cdots\preccurlyeq_{\text{lex}}d_{1}d_{2}\cdots for each i\geq 1 . Proof. Assume first that d_{i}d_{i+1}\cdots\succ_{\text{lex}}d_{1}d_{2}\cdots for some i\geq 1 . In this case, we must have d_{i}\cdots d_{j-1}\succ_{\text{lex}}d_{1}\cdots d_{j-i} for some i,j . However, it is not hard to see that the lexicographically greatest representations of length j and j-i in our numeration system must be d_{1}\cdots d_{j} and d_{1}\cdots d_{j-i} respectively. Since the suffix of length j-i of the former word is lexicographically greater than the latter, our system cannot be equal to a greedy positional numeration system (it is not suffix-closed), and therefore cannot be equal to a Bertrand numeration system. For the other direction, assume that d_{i}d_{i+1}\cdots\preccurlyeq_{\text{lex}}d_{1}d_{2}\cdots,\quad\forall i\geq 1. (19) holds. We consider two cases depending on the periodicity of d_{1}d_{2}\cdots . As a first case, if d_{1}d_{2}\cdots is not purely periodic, the inequality sign can be replaced by a strict inequality in Eq. 19 (which corresponds to the Parry condition). If d_{1}d_{2}\cdots=10^{\omega} , then \mu\colon a\mapsto ab,\,b\mapsto b and our Dumont–Thomas system is equal to the trivial Bertrand numeration system associated with weights (i+1)_{i\geq 0} . If d_{1}d_{2}\cdots ends with 0^{\omega} and is not 10^{\omega} , then d_{1}d_{2}\cdots is equal to d_{\beta}(1) for some simple Parry number \beta . Then, \mu is equal to the Fabre substitution \mu_{\beta}^{\prime} modified to fit the non-canonical Bertrand system (as in the proof of Section 3.3 ) and our Dumont–Thomas numeration system is equal to the non-canonical Bertrand numeration system associated with \beta . Finally, if d_{1}d_{2}\cdots does not end in 0^{\omega} , then it is equal to d_{\beta}(1)=d_{\beta}^{*}(1) for some non-simple Parry number \beta . In this case, \mu=\mu_{\beta} and our Dumont–Thomas numeration system is equal to the canonical Bertrand numeration system associated with \beta . As a second case, if d_{1}d_{2}\cdots is purely periodic with minimal period \ell and is equal to (d_{1}\cdots d_{\ell})^{\omega} , then d_{1}\cdots d_{\ell-1}(d_{\ell}+1)0^{\omega} also verifies Eq. 19 , this time with a strict inequality (see [ 5 , Lemma 4] ). This new word is equal to d_{\beta}(1) for some simple Parry number \beta , thus d_{1}d_{2}\cdots is equal to d_{\beta}^{*}(1) for the same \beta , our \mu is the associated Fabre substitution, and our numeration system is the canonical Bertrand numeration system associated with \beta . In all cases, we have shown that the Dumont–Thomas numeration system associated with \mu is equal to some Bertrand numeration system, as desired. ∎ 4 Open problems We end this article by presenting three open problems related to our topic. First, we ask about the practical aspects of the results presented here. Can the results in this paper be turned into an algorithmic process and, if so, what would its algorithmic complexity be? Second, we note that abstract numeration systems may be defined using trees (by representing a number using the label of a path in a tree) even when those trees are not defined using an underlying substitution. This process corresponds to abstract numeration systems whose language is prefix-closed and right-extendable. Can our methods be adapted to this case, which would lead us one step closer to a characterization of positionality for general abstract numeration systems? Finally, we have used the term Dumont–Thomas complement numeration systems by analogy with the two’s complement numeration system. What properties are shared between our systems and two’s complement? In particular, can the addition of integers be performed similarly to the addition of natural numbers? For the analogue of the two’s complement numeration system in the Fibonacci context, this question was answered positively in [ 10 ] .