text:
# Rational sequences for the conductance in quantum wires from affine Toda field theories

## 1 Introduction

The quantum  and in particular the fractional  quantum Hall effect have attracted an enormous amount of attention both from theorist  and experimentalists (for some very recent experiments see e.g. ). The key observation is that when subjecting an electron gas confined to two space dimensions to a strong uniform magnetic field, the transverse (Hall) conductance takes on preferably certain characteristic values $`G=e^2/h\nu `$, whereas the longitudinal conductance vanishes at these plateaux in complete analogy to the classical Hall effect . The filling fractions $`\nu `$ are distinct universal, in the sense that they are independent of the geometry or type of the material, rational numbers, which can be determined experimentally to an extremely high precision. Many, but not all, of the experimentally observed filling fractions are part of Jain’s famous sequence (see  and references therein)

$$\nu =\frac{m}{mp\pm 1}m,p/2=1,2,3,\mathrm{}$$
(1)
which results as a theoretical prediction from a composite Fermion theory.

In the following we will show that remarkably multiples of these universal numbers also quantize the conductance of quantum wires when described by minimal affine Toda field theories (ATFT) . However, no claims are made here that the systems studied actually correspond to any concrete description of the real quantum Hall effect. Nonetheless, one may speculate as there is a well defined way to reduce from a Chern-Simons type theory (an established description of the quantum Hall effect) to ATFT, see e.g. .

## 2 Conductance in the high temperature regime

Let us briefly recall  how to compute the conductance $`G`$ within the framework of the Landauer-Büttiker transport theory  as a function of the temperature $`T`$ and elaborate on that expression. Let us consider a one dimensional quantum wire within the Landauer-Büttiker transport theory. In order to compute $`G`$ we simply have to determine the difference of the static charge distribution at the left and right constriction of the wire, which we assume to be at the potentials $`\mu _i^l`$ and $`\mu _i^r`$, respectively. Then, to obtain the direct current $`I_i`$ for each particle of type $`i`$ with charge $`q_i`$, we have to integrate the density distribution functions $`\rho _i^r(\theta ,T,\mu _i)`$ of occupied states over the full range of the rapidities $`\theta `$ and the total conductance simply reads

$`G(1/T)`$ $`=`$ $`{\displaystyle \underset{i}{}}G_i={\displaystyle \underset{i}{}}\underset{\mathrm{\Delta }\mu _i0}{lim}{\displaystyle \frac{1}{\mathrm{\Delta }\mu _i}}I_i(1/T,\mathrm{\Delta }\mu _i=\mu _i^l\mu _i^r)`$ (2)
$`=`$ $`{\displaystyle \underset{i}{}}\underset{\mathrm{\Delta }\mu _i0}{lim}{\displaystyle \frac{q_i}{2\mathrm{\Delta }\mu _i}}{\displaystyle \underset{\mathrm{}}{\overset{\mathrm{}}{}}}𝑑\theta \left[\rho _i^r(\theta ,T,\mu _i^l)\rho _i^r(\theta ,T,\mu _i^r)\right].`$ (3)
where $`G_i`$ denotes the contribution to the conductance of each particle $`i`$, and the sums above run both over particles and antiparticles. That explains the factor of $`1/2`$ in (3) wich accounts for the double counting. Hence, the main task in this approach is to determine the density distribution functions $`\rho _i^r(\theta ,T,\mu _i)`$ of occupied states. It is remarkable that in the context of integrable models, despite the fact that these functions are neither Fermi-Dirac nor Bose-Einstein, there exist approaches in which they can be computed non-perturbatively, i.e. the thermodynamic Bethe ansatz (TBA) .

We briefly recall how this is possible. The central equations of the TBA relate the total density of available states $`\rho _i(\theta ,r)`$ for particles of type $`i`$ with mass $`m_i`$ as a function of the inverse temperature $`r=1/T`$ to the density of occupied states $`\rho _i^r(\theta ,r)`$

$$\rho _i(\theta ,r)=\frac{m_i}{2\pi }\mathrm{cosh}\theta +\underset{j}{}[\phi _{ij}\rho _j^r](\theta ).$$
(4)
By $`\left(fg\right)(\theta )`$ $`:=1/(2\pi )𝑑\theta ^{}f(\theta \theta ^{})g(\theta ^{})`$ we denote as usual the convolution of two functions. There are only two inputs into the entire TBA analysis: first the dynamical interaction, which enters via the logarithmic derivative of the scattering matrix $`\phi _{ij}(\theta )=id\mathrm{ln}S_{ij}(\theta )/d\theta `$ and an assumption on the statistical interaction $`g_{ij}`$ amongst the particles $`i`$ and $`j`$ on which we comment further below. For the moment we chose this interaction to be of fermionic type. The mutual ratio of the two types of densities serves as the definition of the so-called pseudo-energies $`\epsilon _i(\theta ,r)`$

$$\frac{\rho _i^r(\theta ,r)}{\rho _i(\theta ,r)}=\frac{e^{\epsilon _i(\theta ,r)}}{1+e^{\epsilon _i(\theta ,r)}},$$
(5)
which have to be positive and real. At thermodynamic equilibrium they can be computed from the non-linear integral equations

$$rm_i\mathrm{cosh}\theta =\epsilon _i(\theta ,r,\mu _i)+r\mu _i+\underset{j}{}[\phi _{ij}\mathrm{ln}(1+e^{\epsilon _j})](\theta ),$$
(6)
where $`r=m/T`$, $`m_lm_l/m`$, $`\mu _i\mu _i/m`$, with $`m`$ being the mass of the lightest particle in the model and chemical potential $`\mu _i<1`$. As pointed out already in  (here just with the small modification of a chemical potential), the comparison between (6) and (4) leads to the useful relation

$$\rho _i(\theta ,r,\mu _i)=\frac{1}{2\pi }\left(\frac{d\epsilon _i(\theta ,r,\mu _i)}{dr}+\mu _i\right)\frac{1}{2\pi r}ϵ(\theta )\frac{d\epsilon _i(\theta ,r,\mu _i)}{d\theta }.$$
(7)
Here $`ϵ(\theta )=\mathrm{\Theta }(\theta )\mathrm{\Theta }(\theta )`$ is the unit step function, i.e. $`ϵ(\theta )=1`$ for $`\theta >0`$ and $`ϵ(\theta )=1`$ for $`\theta <0`$. In equation (5), we assume that in the large rapidity regime the density $`\rho _i^r(\theta ,r,\mu _i)`$ is dominated by the last expression in (7) and in the small rapidity regime by the Fermi distribution function. Therefore, from (5) follows

$`\rho _i^r(\theta ,r,\mu _i)`$ $`=`$ $`{\displaystyle \frac{e^{\epsilon _i(\theta ,r,\mu _i)}}{1+e^{\epsilon _i(\theta ,r,\mu _i)}}}\rho _i(\theta ,r,\mu _i)`$ (8)
$``$ $`{\displaystyle \frac{1}{2\pi r}}ϵ(\theta ){\displaystyle \frac{d}{d\theta }}\mathrm{ln}\left[1+\mathrm{exp}(\epsilon _i(\theta ,r,\mu _i))\right].`$ (9)
Using this expression in equation (3), we can approximate the direct current in the ultraviolet by

$$\underset{r0}{lim}I_i(r,\mathrm{\Delta }\mu _i)\frac{q_i}{4\pi r}\underset{\mathrm{}}{\overset{\mathrm{}}{}}𝑑\theta \mathrm{ln}\left[\frac{1+\mathrm{exp}(\epsilon _i(\theta ,r,\mu _i^l))}{1+\mathrm{exp}(\epsilon _i(\theta ,r,\mu _i^r))}\right]\frac{dϵ(\theta )}{d\theta },$$
(10)
after a partial integration. Taking now the potentials at the end of the wire to be $`\mu _i^r=\mu _i^l=\mu _i/2`$ we carry out the limit $`\mathrm{\Delta }\mu _i0`$ in (3) with the help l’Hôpital rule and the conductance becomes

$$\underset{r0}{lim}G_i(r)\frac{q_i}{2\pi r}\underset{\mathrm{}}{\overset{\mathrm{}}{}}𝑑\theta \frac{1}{1+\mathrm{exp}[\epsilon _i(\theta ,r,0)]}\frac{d\epsilon _i(\theta ,r,\mu _i/2)}{d\mu _i}|_{\mu _i=0}\frac{dϵ(\theta )}{d\theta }.$$
(11)
Noting that $`dϵ(\theta )/d\theta =2\delta (\theta )`$, we obtain

$$\underset{r0}{lim}G_i(r)\frac{q_i}{\pi r}\frac{1}{1+\mathrm{exp}\epsilon _i(0,r,0)}\frac{d\epsilon _i(0,r,\mu _i/2)}{d\mu _i}|_{\mu _i=0}.$$
(12)
The derivative $`d\epsilon _i(0,r,\mu _i/2)/d\mu _i`$ can be obtained by solving

$$\frac{d\epsilon _i(0,r,\mu _i/2)}{d\mu _k}=\frac{r}{2}\delta _{ik}+\underset{j}{}N_{ij}\frac{1}{1+\mathrm{exp}\epsilon _j(0,r,\mu _i/2)]}\frac{d\epsilon _j(0,r,\mu _j/2)}{d\mu _k},$$
(13)
which results from performing a constant TBA analysis on the $`\mu _k`$-derivative of (6) in the spirit of . At this point only the asymptotic phases of the scattering matrix enter via

$$N_{ij}=\frac{1}{2\pi i}\underset{\theta \mathrm{}}{lim}[\mathrm{ln}[S_{ij}(\theta )/S_{ij}(\theta )]].$$
(14)
In principle we have now all quantities needed to compute the conductance, but to solve (13) for the derivatives of the pseudo-energies is somewhat cumbersome, see  for such a computation. Nonetheless, we can elaborate more on equation (13) and simplify the procedure further. For this purpose we introduce the quantity

$$Y_{ij}:=\frac{1}{r(1+e^{\epsilon _i})}\frac{d\epsilon _i}{d\mu _j},$$
(15)
such that we can re-write equation (13) equivalently as

$$M_{ij}Y_{jk}=\frac{\delta _{ik}}{2}\text{with }M_{ij}:=N_{ij}(1+e^{\epsilon _i})\delta _{ij}$$
(16)
where the pseudoenergies satisfy the constant TBA equations

$$e^{\epsilon _i}=\underset{j}{}(1+e^{\epsilon _j})^{N_{ij}}.$$
(17)
Returning now to dimensionful variables, i.e. replacing $`1/2\pi e^2/h`$, the conductance at high temperature in terms of the filling fraction $`\nu `$ then simply results to

$$G(0)=\frac{e^2}{h}\nu \text{with }\nu =2\underset{i,j}{}q_i(M^1)_{ij}.$$
(18)
This means we have reduced the entire problem to compute filling fractions simply to the task of finding and inverting the matrix $`M`$. This is done in two steps: First from the asymptotic phases of the scattering matrix we compute $`N_{ij}`$ and subsequently we solve the constant TBA equations (17). Then it is a simple matter of inverting the matrix (16) and performing the sums in (18).

In the context of the fractional quantum Hall effect one encounters very often particles which obey some exotic (anyonic) statistics. So far we have assumed our particles to obey fermionic type statistics as this choice is most natural for the investigated theories . However, one can easily implement more general statistics by adding a matrix $`g_{ij}`$ to the $`N`$-matrix .

The formula (18) reminds of course on the well-known expressions for the conductance as may be found for instance in . In that context it was found  that Jain’s sequence (1) can be obtained simply from the $`(m\times m)`$-matrix

$$M_{ij}=p\pm \delta _{ij}.$$
(19)
For this we have to take $`q_i=1/2`$ $`i`$ in our expression (18). We will now demonstrate that a sequence closely related to (1) can also be obtained in a more surprising way from fairly complicated matrices, even with non-rational entries, which result directly in the way indicated above, namely from a TBA analysis of minimal affine Toda field theories . Each Toda theory is associated to a Lie algebra g of rank $`\mathrm{}`$ and it is well known  that in that case $`N`$ is an $`(\mathrm{}\times \mathrm{})`$-matrix which is of the general form

$$N_{ij}=\delta _{ij}2(K_𝐠^1)_{ij},$$
(20)
where $`K_𝐠`$ is the Cartan matrix related to g  (see e.g. ). The solutions to the constant TBA equations are also known  for most cases. In the ultraviolet limit these theories possess Virasoro central charge $`c=2\mathrm{}/(H+2)`$, with $`H`$ being the Coxeter number of the Lie algebra g.

## 3 Fractional filling fractions from minimal affine Toda field theory

### 3.1 The $`4m/(2m+1)`$-sequence

Let us start with some concrete examples to illustrate the working of our formulae. Specializing the general expression (20) to the $`A_3`$-case, the solutions to the constant TBA equations (17) are simply

$$e^{\epsilon _1}=e^{\epsilon _3}=2,e^{\epsilon _2}=3.$$
(21)
Then, the inverse of the $`M`$-matrix

$$M_{ij}=\delta _{ij}2(K_{A_3}^1)_{ij}\delta _{ij}(1+e^{\epsilon _i})$$
(22)
is computed to

$$M^1=\frac{1}{36}\left(\begin{array}{ccc}11& 2& 1\\ 2& 8& 2\\ 1& 2& 11\end{array}\right).$$
(23)
From the fact that the $`A_{\mathrm{}}`$-minimal affine Toda field theories can also be viewed as complex sine-Gordon models , we know  that the charges in this theory are $`q_1=q_3=1`$, $`q_2=2`$, such that (18) yields

$$\nu _{A_3}=4/3.$$
(24)
The next example, i.e. $`A_5`$-minimal affine Toda field theory, yields a less expected answer, even more since the $`M`$-matrix contains non-rational entries. With (20) for $`A_5`$ the solutions to the constant TBA equations are

$$e^{\epsilon _1}=e^{\epsilon _5}=1+\sqrt{2},e^{\epsilon _2}=e^{\epsilon _4}=2+2\sqrt{2},e^{\epsilon _3}=3+2\sqrt{2}.$$
(25)
Assembling this into the $`M`$-matrix, it is clear that it will contain non-rational entries. Evidently this matrix is not of the form (19) and certainly falls out of the classification scheme based on integral lattices . Nonetheless, it will lead to a distinct rational value for $`\nu `$. We compute the inverse of $`M`$ to

$$M^1=\left(\begin{array}{ccccc}\left(\frac{35}{4}6\sqrt{2}\right)& \left(\frac{31}{2\sqrt{2}}11\right)& \left(\frac{75\sqrt{2}}{4}\right)& \left(6\frac{17}{2\sqrt{2}}\right)& \left(3\sqrt{2}\frac{17}{4}\right)\\ \left(\frac{31}{2\sqrt{2}}11\right)& \left(15\frac{21}{\sqrt{2}}\right)& \left(\frac{7\sqrt{2}10}{4}\right)& \left(6\sqrt{2}\frac{17}{2}\right)& \left(6\frac{17}{2\sqrt{2}}\right)\\ \left(\frac{75\sqrt{2}}{4}\right)& \left(\frac{7\sqrt{2}10}{4}\right)& \left(\frac{9}{4}\frac{3}{\sqrt{2}}\right)& \left(\frac{7\sqrt{2}10}{4}\right)& \left(\frac{75\sqrt{2}}{4}\right)\\ \left(6\frac{17}{2\sqrt{2}}\right)& \left(6\sqrt{2}\frac{17}{2}\right)& \left(\frac{7\sqrt{2}10}{4}\right)& \left(15\frac{21}{\sqrt{2}}\right)& \left(\frac{31}{2\sqrt{2}}11\right)\\ \left(3\sqrt{2}\frac{17}{4}\right)& \left(6\frac{17}{2\sqrt{2}}\right)& \left(\frac{75\sqrt{2}}{4}\right)& \left(\frac{31}{2\sqrt{2}}11\right)& \left(\frac{35}{4}6\sqrt{2}\right)\end{array}\right).$$
(26)
Remarkably when taking into account that  $`q_1=q_5=1`$, $`q_2=q_4=2`$, $`q_3=3`$, we obtain by evaluating (18) for the matrix (26) the simple ratio

$$\nu _{A_5}=3/2.$$
(27)
We will now turn to the generic case. Taking the general solutions of the constant TBA equations into account  and using a generic expression for the inverse of the Cartan matrix $`K_A_{\mathrm{}}^1=\mathrm{min}(i,j)ij/(\mathrm{}+1)`$ in (20), the M-matrix for an $`A_{2\mathrm{}+1}`$-minimal affine Toda field theory can be written generically as

$$M_{ij}=\frac{ij}{\mathrm{}+1}2\mathrm{min}(i,j)\delta _{ij}\frac{\mathrm{sin}\left(\frac{i\pi }{2\mathrm{}+4}\right)\mathrm{sin}\left(\frac{(i+2)\pi }{2\mathrm{}+4}\right)}{\mathrm{sin}^2\left(\frac{\pi }{2\mathrm{}+4}\right)}.$$
(28)
As already indicated by the previous example this matrix is not of the form (19) and does not fit into the classification scheme proposed in . According to  we have the charges

$$q_i=q_{2\mathrm{}+2i}\text{and }q_i=i\text{for }i\mathrm{}+1.$$
(29)
As can be guessed from (26), it is not evident how to express the inverse in terms of a simple closed expression. We can, however, invert (28) case-by-case up to very high rank and we obtain from (18) together with (29) the sequence

$$\nu _{A_{2\mathrm{}+1}}=\frac{2\mathrm{}+2}{\mathrm{}+2}.$$
(30)
In view of (28), it is remarkable that the outcome is rational. Note for $`\mathrm{}=0`$, that is $`A_1`$ we recover the free case with $`\nu =1`$. Taking now $`\mathrm{}=2m1`$, we obtain as a subsequence of this four times the most stable part of Jain’s sequence (1) with $`p=2`$

$$\nu _{A_{4m1}}=\frac{4m}{2m+1}.$$
(31)
In summary: *The conductance of a quantum wire which is described by a massive* $`A_{2\mathrm{}+1}`$*-minimal affine Toda field theory possesses in the high temperature regime, in which the model turns into a conformal field theory with Virasoro central* $`c=(2\mathrm{}+1)/(\mathrm{}+2)`$*, a filling fraction equal to (30). In particular for* $`\mathrm{}=2m1`$*, we obtain the sequence (31).*

### 3.2 The $`2m/(2m+1)`$-sequence

We proceed now similarly as in the preceding section, but now for the $`D_{2\mathrm{}+1}`$-minimal affine Toda field theories, which all possess Virasoro central charge $`c=1`$ in the ultraviolet limit. We label the particles in consecutive order along the Dynkin diagram (see e.g.  for more properties), starting from the not splitted end. Taking in (20) g=$`D_{2\mathrm{}+1}`$ the solutions to the constant TBA equations are simply

$`e^{\epsilon _i}`$ $`=`$ $`i(i+2)1i2\mathrm{}1`$ (32)
$`e^{\epsilon _{2\mathrm{}+1}}`$ $`=`$ $`e^{\epsilon _2\mathrm{}}=2\mathrm{}.`$ (33)
Since these entries are all integer valued, we are not very surprised when we obtain rational values for the filling fraction, but what is not obvious is that the outcome is one of Jain’s sequences. The $`M`$-matrix is computed to

$$M_{ij}=2(K_{D_{2\mathrm{}+1}}^1)_{ij}\delta _{ij}e^{\epsilon _i},$$
(34)
with the values (32) and (33). From these data we evaluate a simple expression for the determinant

$$detM=\frac{(2\mathrm{}+1)^2(2\mathrm{}+1)!(2\mathrm{})!}{2},$$
(35)
and the inverse of this matrix

$`(M^1)_{ij}`$ $`=`$ $`(M^1)_{ji}={\displaystyle \frac{2}{3j(1+j)(2+j)}}2i<j2\mathrm{}1`$ (36)
$`(M^1)_{ii}`$ $`=`$ $`{\displaystyle \frac{(3i+1)}{3i(1+i)(2+i)}}1i2\mathrm{}1`$ (37)
$`(M^1)_{i(2\mathrm{}+1)}`$ $`=`$ $`(M^1)_{i(2\mathrm{})}={\displaystyle \frac{1}{6\mathrm{}(2\mathrm{}+1)}}1i2\mathrm{}1`$ (38)
$`(M^1)_{(2\mathrm{}+1)i}`$ $`=`$ $`(M^1)_{(2\mathrm{})i}={\displaystyle \frac{1}{6\mathrm{}(2\mathrm{}+1)}}1i2\mathrm{}1`$ (39)
$`(M^1)_{(2\mathrm{}+1)(2\mathrm{}+1)}`$ $`=`$ $`(M^1)_{(2\mathrm{})(2\mathrm{})}={\displaystyle \frac{10\mathrm{}+1}{12\mathrm{}(2\mathrm{}+1)}}`$ (40)
$`(M^1)_{(2\mathrm{}+1)(2\mathrm{})}`$ $`=`$ $`(M^1)_{(2\mathrm{})(2\mathrm{}+1)}={\displaystyle \frac{2\mathrm{}1}{12\mathrm{}(2\mathrm{}+1)}}`$ (41)
Taking then the charges of the particles to be

$$q_{2\mathrm{}+1}=q_2\mathrm{}=\mathrm{}/2\text{and }q_i=i\text{for }i2\mathrm{}1,$$
(42)
the computation of (18) yields

$$\nu _{D_{2\mathrm{}+1}}=\frac{2\mathrm{}}{2\mathrm{}+1}.$$
(43)
Similarly as in the previous subsection, the sequence (43)gives twice the Jain sequence (1) with $`p=2.`$

In summary: *The conductance of a quantum wire which is described by a massive* $`D_{2\mathrm{}+1}`$*-minimal affine Toda field theory possesses in the high temperature regime, in which all models turn into conformal field theories with Virasoro central charge* $`c=1`$*, a filling fraction equal to (43) which is twice the principal Jain sequence (1).*

### 3.3 The $`4m/(6m+1)`$-sequence

This sequence can be obtained similarly just by altering the values of the two charges at the very end of the Dynkin diagram. Considering now the $`D_{6m+2}`$-minimal affine Toda field theories we can employ the same $`M`$-matrix as in the previous subsection, but we take the charges of the particles to be

$$q_{6m+2}=q_{6m+1}=m/(2m+1)\text{and }q_i=i\text{for }i6m.$$
(44)
Evaluating then the expression for the filling fractions (18) gives

$$\nu _{D_{6m+2}}=\frac{4m}{6m+1},$$
(45)
which is four times the Jain’s sequence (1) with $`p=6`$.

## 4 Conclusions

Within a Landauer-Büttiker transport theory picture we have analyzed the expression for the conductance of a quantum wire which is described by an integrable quantum field theory. The final expression for the conductance in the high temperature regime is very simple (18) and involves the sum over the entries of the inverse of a certain matrix $`M`$ as defined in (16). This matrix is constructed from the knowledge of the asymptotic phases of the scattering matrix and the solutions of the constant TBA equations (17).

When evaluating this matrix for some concrete minimal affine Toda field theories, we obtain values for the filling fraction which coincide with multiples of several subsequences of Jain’s series (1) and are therefore rational numbers. The fact that we obtain this special rational values is extremely surprising, in particular as for the $`A_{2\mathrm{}+1}`$-minimal affine Toda theories the related $`M`$-matrix has non-rational entries. One should note, however, that one does not always get these nice rational values. We did not report all examples here which we have computed, but for instance in general the $`A_2\mathrm{}`$ and the $`D_2\mathrm{}`$-minimal affine Toda theories lead to non-rational values for $`\nu `$.

Our findings pose several interesting questions: As it is clear that the $`M`$-matrices obtained are beyond the classification scheme carried out in  on the basis of integral lattices, one may attempt a new type of classification based on the Lie algebraic systematics which underlies the formulation of integrable quantum field theories. In order to do this we have to enlarge our considerations  to other algebras such as the $`E`$-series, non-simply laced Lie algebras and also to theories which are related to a pair of Lie algebras. It would also be interesting to perform an analysis based on a different expression from (3) for the conductance, such as the Kubo formula, and compare the findings similar as in .

Acknowledgments: We are grateful to the Deutsche Forschungsgemeinschaft (Sfb288), for financial support.


format: text

text:
# 1 Introduction

## 1 Introduction

Exactly solvable models play an important role in the developing of all branches of physics as well as persist to be a genuine challenge to our understanding of nature beauty and simplicity. Comprehensive analysis of underlying reasons of solvability is still a dream today even in such developed field as quantum mechanics, whereas solvable models known in all other branches of physics, could be easily enumerate by hands.

Among the most developed approaches to solvability problem in quantum mechanics is supersymmetric quantum mechanics (SUSY QM) approach that has much in common with the early Infeld & Hull factorization . It was developed by E. Witten  originally in the context of quantum field theory, but later gathered a lot of attention especially after L. Genderstein introduction of the concept of self-similar potential . Today the SUSY QM approach has clearly outlined the region of its applicability as well as its connection with other analytical tools and methods. Some interesting new results on the topic were obtained in the way of generalization of SUSY approach on matrix models, higher order symmetries and can be found in -).

The another type of approaches of the solvability problem have to be mentioned, which were developed separately though been and becoming more and more closer to SUSY QM, are numerous algebraic approaches. In this context we would like to mention only a few papers, firstly relatively old classical papers , with extensive reference lists therein and some recent ones - discussing different aspects of the problem.

There are also analytical ways of attacking the problem which are also very numerous and we only cite some recent papers -,  demonstrating some new ideas but been away out of the topics discussed in the present work.

For Fokker-Planck equations solvable problems are still very rear events as well as developed approaches to this problem. Some recent results have been obtained for the generalization of SUSY QM approach on this situation  (see also the references therein).

The goal of the present paper is to establish close relations between the above mentioned equations based on the SUSY approach developed in . As it will be demonstrated, the set of exactly solvable potentials for the Fokker-Planck equation is at least not poorer than that of Schrödinger one.

## 2 Diffusion equation and Superpotential

The diffusion (Fokker-Planck) equation for the distribution function $`f(𝐱,t)`$ for a system in an external potential $`U(𝐱)`$ has the following form

$`{\displaystyle \frac{f(𝐱,t)}{t}}=\widehat{𝒟}f(𝐱,t)+\left(f(𝐱,t)U(𝐱)\right)`$ (1)
where $`𝐱`$ are some space co-ordinates for the system, $`\widehat{𝒟}`$ is a diffusion tensor and we assume in subsequent that both diffusion tensor and external field potential do not depend on time explicitly.

In literature, it is commonly accepted that the only difference of diffusion equation (for spherically symmetric particles,when $`\widehat{𝒟}_{ij}=D\delta _{ij}`$) and Schrödinger’s one is imaginary time on respect to real time (Vick’s rotation). Though it is evidently true for the case of a free particle, for the problem in an external field the only sight on the second equation

$`i\mathrm{}{\displaystyle \frac{\psi (𝐱,t)}{t}}={\displaystyle \frac{\mathrm{}^2}{2m}}^2\psi (𝐱,t)+U(𝐱)\psi (𝐱,t)`$ (2)
immediately demonstrates that the external field is incorporated into the equation (2) in a different way on respect to that in the diffusion case (1).

The prominent feature of the eq.(1) is the existence of zero-mode (stationary or steady-state) solution $`f_s(𝐱)`$, which simply corresponds to generalization of known Boltzmann distribution $`f_s(𝐱)=C\mathrm{exp}\left(U(𝐱)\right)`$ (valid when diffusion tensor is spherical). Appropriate first order system of differential equations can be obtained from eq.(1) as

$`\widehat{𝒟}f_s(𝐱)+\left(f_s(𝐱)U(𝐱)\right)=\left(\widehat{𝒟}f_s(𝐱)+f_s(𝐱)U(𝐱)\right)=0`$
$`\widehat{𝒟}f_s(𝐱)+f_s(𝐱)U(𝐱)=\mathrm{𝐫𝐨𝐭}𝐛(𝐱)`$ (3)
where $`𝐛(𝐱)`$ is some vector function that should be chosen in a way to allow a non-trivial solution of (3) satisfying proper boundary conditions.

In opposite, for the Schrödinger equation (2) the ground state is typically unknown and of most interest.

This, as we will see at least for one dimensional problems, is due to the fact that after transformation of the diffusion equation into the form of the Schrödinger one, we obtain the last in the supersymmetric quantum mechanics ( SUSY) form directly and the proper partner Hamiltonian is just $`H_{}`$ .

Let us follow the way, similar to  and concentrate in the subsequent on 1D problems only (so that $`𝐱x`$) . We also assume the units’ choice such that $`\mathrm{}=1,m=1,D=1/2`$. It is worth to note that steady state solution reads $`f_s(x)=\mathrm{exp}(2U(x))`$ with this units’ choice.

Then, after substitution $`f(x)=\mathrm{exp}\left\{U(x)Et\right\}\psi (x)`$ into

$`{\displaystyle \frac{f(x,t)}{t}}={\displaystyle \frac{1}{2}}{\displaystyle \frac{^2f(x,t)}{t^2}}+{\displaystyle \frac{}{x}}\left(f(x,t)U^{}(x)\right)`$ (4)
we get the Schrödinger equation in the form

$`{\displaystyle \frac{1}{2}}\psi ^{\prime \prime }(x)+\left(EV_q(x)\right)\psi (x)=0`$ (5)
with a ”quantum potential” $`V_q(x)`$ given

$`V_q(x)={\displaystyle \frac{1}{2}}U^{}(x)^2{\displaystyle \frac{1}{2}}U^{\prime \prime }(x)`$ (6)
It is important to note that steady state solution of (4) reads $`f_0(x)=\mathrm{exp}(2U(x))`$ in our case

The last equation is just in the form of SUSY QM approach with the superpotential given by $`W(x)=U^{}(x)`$  and the Hamiltonian operator having the factorized form

$`\widehat{H}_{}=\widehat{A}^{}\widehat{A}={\displaystyle \frac{1}{\sqrt{2}}}\left({\displaystyle \frac{d}{dx}}+U^{}(x)\right){\displaystyle \frac{1}{\sqrt{2}}}\left({\displaystyle \frac{d}{dx}}+U^{}(x)\right)`$ (7)
It is worth to remark that quantum potentials for partner Hamiltonians $`\widehat{H}_\pm `$  now correspond simply to $`X`$-axis reflection images of the original diffusion potential $`U(x)`$.

It is immediately follows from the (5) and (7) that the state $`E=0`$ is the eigenstate of $`H_{}`$.

The last clarifies the principal difference between the Schrödinger and diffusion equations. Whereas it can be highly nontrivial problem to construct an explicit factorization of a given Hamiltonian and find as a result the ground state of a quantum system, for a diffusion equation (at least for one-dimensional one) this is not a problem at all, as it can be always done in the way been outlined.

To construct solvable cases for a 1-D diffusion equation, one can exploit the supersymmetric form directly, considering known shape-invariant partner potentials .

We will choose another way, namely we try to answer the following question:

> what superpotential $`W(x)=U^{}(x)`$ should be that leads to exactly-solvable potentials for the eq.(5)

provided we use most general form of a 1D quantum potential allowing polynomial anzatz for a wave function .

Denoting a solvable quantum potential in (5) by $`V_s(x)`$, we consider now (6) as the Ricatti equation for superpotential $`W(x)`$

$`W^{}(x)W(x)^2=2V_s(x)`$ (8)
Here it worth to point out the following. We could split the energy parameter $`E`$ in (5) as $`E=E_1+E_2`$ that leads to the appearance of one term e.g., $`E_2`$ in the right side of (8), that will be used in subsequent.

Now, we perform the known trick. Based on the correspondence of Ricatti and Schrödinger equation we introduce substitution

$$W(x)=\mathrm{\Psi }^{}(x)/\mathrm{\Psi }(x))$$
(9)
and rewrite (8) in the form of the Schrödinger equation for a function $`\mathrm{\Psi }(x)`$

$`{\displaystyle \frac{1}{2}}\mathrm{\Psi }^{\prime \prime }(x)+\left(E_2V_s(x)\right)\mathrm{\Psi }(x)=0`$ (10)
The last simply means that every eigenstate $`\mathrm{\Psi }_n(x)`$ of a quantum solvable potential $`V_s(x)`$ gives a superpotential through the relation (9) that after integration gives for the the diffusion equation potential $`U(x)`$ a simple formula

$$U_n(x)=U_0+\mathrm{log}\left|\mathrm{\Psi }_n(x)\right|$$
(11)
Most important fact here is that the set of $`U_n(x)`$ leads to the same Schrödinger equation (5) (with different splitting of the constant $`E`$, but of course gives different solutions for original diffusion equation (1).

One more comment worth to be done is though representation in the form () looks very known from the point of view of I Inverse Scattering Transform theory (see, e.g. ) as well as the formulae (8,11) are valid in all cases, but only for solvable quantum potentials we obtain a closed form solution of the original problem. Indeed, logarithm of some $`n`$-th eigenfunction of a solvable potential $`V_s(x)`$ gives diffusion potential (eq.(11)) whereas eigenfunctions modified by exponential factor (written before eq.(4)) give the eigenfunctions of the diffusion problem itself.

Finally, we express the main result of the paper as follows. The i-th eigenstate for some exactly solvable diffusion potential $`U_n(x)`$ (given by above written formula ()) reads

$$f_i(x,t)=\mathrm{\Psi }_n(x)\mathrm{exp}\left((E_i+\mathrm{\Delta }E)t\right)\mathrm{\Psi }_i(x)i=0,1,\mathrm{},n\mathrm{}$$
(12)
where $`E_i`$ is eigenenergy of the appropriate quantum potential () and $`\mathrm{\Delta }E=E_0`$ is the constant energy shift introduce to give proper energy of the ground state ($`E=0`$ ) for the diffusion equation.

## 3 Conclusion

Simple construction we discussed opens a new sight on interrelation of Fokker-Planck and associate Schrödinger problems. Having a significantly large number of exactly solvable quantum potentials (see, e.g. list in ) one can construct at least measure similar list of solvable diffusion cases having possibility to choose one appropriate to approximate some practical problems.

## 4 Acknowledgement

Author would like to thank Prof. Dr. Marko Robnik for numerous and stimulating discussions of this and related problems. This work has been support in parts by the Fund of Fundamental Researches of the Republic of Belarus (Project F00-158), and Swiss Science Foundation (Project SCOPES 7BYPJ065731).


text:
# Real numbers having ultimately periodic representations in abstract numeration systems

## 1. Introduction

Enumerating the words of an infinite regular language $`L`$ over a totally ordered alphabet $`(\mathrm{\Sigma },<)`$ by genealogical ordering gives a one-to-one correspondence between $``$ and $`L`$. This observation was the starting point of the study of the so-called abstract numeration systems which are a natural generalization of classical positional numeration systems like the Fibonacci system or the $`k`$-ary system. More generally, abstract systems generalize positional numeration systems where representations of integers are computed by the greedy algorithm and where the set of all the representations is a regular language . We were first interested in the representation of non-negative integers and in the syntactical properties of sets of representations .

In  we extended these systems to the representation of real numbers. Mimicking the case of positional systems, a real number $`x`$ is represented by an infinite word $`w`$ which is the limit of a sequence $`(w_n)_n`$ of words in $`L`$. Each finite word $`w_n`$ of the sequence corresponding to a numerical approximation of $`x`$, the longer the common prefix of $`w`$ and $`w_n`$ is, the more accurate the approximation of $`x`$ is. The ability of representing not only integers but also real numbers in abstract systems lead to several applications and generalizations like the study of the asymptotic properties of summatory functions of additive functions like the “sum-of-digits” function  or the description of properties of generalized adding machines, i.e., “odometers” .

Real numbers having an ultimately periodic representations are of particular interest. First, from the point of view of computational aspects, the amount of data needed to store completely such a number is finite (the information is given exactly by the aperiodic part and one period). Next, we shall see that the set of ultimately periodic representations is dense in the set of all the representations, so studying this subset of representations is relevant when dealing with approximations of real numbers. As an example, for the $`k`$-ary system, it is well-known that the numbers having an ultimately periodic representation is $``$ which is dense in $``$ and therefore various number-theoretic problems concerning rational approximations of real numbers can arise. Finally, for classical systems (more precisely, for $`\beta `$-expansions when $`\beta `$ is a Pisot number) the set of real numbers having an ultimately periodic representation is exactly the field-extension $`(\beta )`$ . To be able to represent real numbers in a generalized numeration system, we consider some assumptions about the counting function of the language, namely $`𝐮(n):=\mathrm{\#}(L\mathrm{\Sigma }^n)P(n)\theta ^n`$ for some polynomial $`P`$ and $`\theta >1`$. Therefore the problem of relating this number $`\theta `$ to the set of numbers having an ultimately periodic representation clearly appears in the case of abstract systems.

This paper has the following organization. First we recall definitions and notation about abstract numeration systems and the representation of real numbers. Next we recall the general assumptions we consider when dealing with the representation of real numbers. As stated before, these assumptions are related to the asymptotic behavior of the counting functions of the languages accepted from the different states of the minimal automaton of $`L`$. The reader could already note that we have slightly simplified the presentation given in . The aim of Sections 2 and 3 is to give a summary of the relevant facts given in .

In Section 4 we study the syntactical properties of the ultimately periodic representations. We show that the corresponding language of infinite words is $`\omega `$-rational. This section has an automata theory flavor and can be read separately from the rest of the paper.

In Section 5, we obtain formulas for computing effectively the numerical value of an ultimately periodic representation. Moreover we show that the language made up of the ultimately periodic representations is dense in the set of all the representations. In , it is explained that for an abstract system built upon an arbitrary regular language $`L`$, a real number can have one, a finite number or even an infinite number of representations and the situation can be completely determined from the language $`L`$ (actually, from the asymptotic behavior of the counting functions associated to the different states). In Section 6, we show how to modify the language $`L`$ to obtain a new numeration system having exactly the same representations except that in this new system a number has at most two representations. Roughly speaking, we remove from the minimal automaton of $`L`$ the useless states which are giving redundant representations.

In Section 7, we use some intervals $`I_w`$ (a real number $`x`$ belongs to $`I_w`$ if $`x`$ has a representation having $`w`$ as prefix) to obtain a characterization of the real numbers having an ultimately periodic representation. From the ideas given in this result and its proof, we derive two algorithms for computing the representation of an arbitrary real number. These algorithms can be viewed as a generalization of the greedy algorithm used to compute $`\beta `$-expansions  and rely on the use of some affine functions completely defined by the minimal automaton of the language. We also present a dynamical system built upon those affine functions, the points having an ultimately periodic orbit in this dynamical system being exactly the real numbers having an ultimately periodic representation (this system is a generalization of the intervals exchange transformation ). In Section 8, thanks to our algorithm of representation, we obtain another characterization of the real numbers having an ultimately periodic representation, these numbers are the fixed points of composition of some affine functions. Moreover, this composition can actually be viewed as a word belonging to a regular language over a finite alphabet of functions.

In the last section, we consider a Pisot number $`\theta `$. To this number, corresponds a unique linear Bertrand numeration system . If $`L`$ is the language of representations of the integers in this latter Bertrand system then the representations of the real numbers in the abstract system built upon $`L`$ and the classical $`\theta `$-developments are the same. So thanks to a famous result of Klaus Schmidt, in this particular case, we know precisely the structure of the set of real numbers having an ultimately periodic representation. This set is $`(\theta )`$.

## 2. Preliminaries

Let us precise notation and definitions. Let $`\mathrm{\Sigma }`$ be a finite alphabet. We denote by $`\mathrm{\Sigma }^{}`$ the free monoid generated by $`\mathrm{\Sigma }`$ with identity $`\epsilon `$. Let $`L`$ be an infinite regular language and $`_L=(Q,q_0,\mathrm{\Sigma },\delta ,F)`$ be its minimal automaton having $`Q`$ as set of states, $`q_0`$ as initial state, $`F`$ as set of final states. The transition function $`\delta :Q\times \mathrm{\Sigma }Q`$ of this automaton is naturally extended to $`Q\times \mathrm{\Sigma }^{}`$ and we often write $`q.w`$ as a shorthand for $`\delta (q,w)`$, $`qQ`$, $`w\mathrm{\Sigma }^{}`$. (For more about automata theory see for instance .) If $`qQ`$, we denote by $`L_q`$ the language accepted in $`_L`$ from the state $`q`$, i.e.,

$$L_q=\{w\mathrm{\Sigma }^{}q.wF\}.$$

In particular, $`L_{q_0}=L`$. In this paper, we shall extensively use the following linear recurrent sequences defined for each $`qQ`$ by

$$𝐮_q(n)=\mathrm{\#}(L_q\mathrm{\Sigma }^n),𝐯_q(n)=\mathrm{\#}(L_q\mathrm{\Sigma }^n).$$

Since the initial state $`q_0`$ plays a special role, if $`q=q_0`$ then we simply write $`𝐮(n)`$ and $`𝐯(n)`$ (in the literature, $`𝐮(n)`$ is often called the growth function, the counting function or even the complexity of the language $`L`$).

Let $`(\mathrm{\Sigma },<)`$ be a totally ordered alphabet. The genealogical ordering (or radix ordering) is defined as follows. Let $`u`$, $`v`$ be two words over $`\mathrm{\Sigma }`$, $`u<_{gen}v`$ if $`|u|<|v|`$ or if the words have the same length and $`u`$ is lexicographically less than $`v`$ (the lexicographic ordering is the usual order of the dictionary). If the context is clear, we write $`u<v`$ instead of $`u<_{gen}v`$.

In  we introduced numeration systems generalizing classical numeration systems in which the set of representations of all the integers is a regular language. An abstract numeration system is a triple $`S=(L,\mathrm{\Sigma },<)`$ where $`L`$ is infinite regular language over the totally ordered alphabet $`(\mathrm{\Sigma },<)`$. The genealogical ordering of $`L`$ induced by the ordering of $`\mathrm{\Sigma }`$ gives a one-to-one correspondence between $``$ and $`L`$. If $`wL`$, we denote by $`\mathrm{val}_S(w)`$ the position of $`w`$ in the genealogically ordered language $`L`$ (positions are counted from zero). The number $`\mathrm{val}_S(w)`$ is said to be the numerical value of $`w`$. Conversely, let $`n`$, if $`w`$ is the $`(n+1)`$th word in the genealogically ordered language $`L`$, then $`w`$ is the $`S`$-representation of $`n`$ and is denoted by $`\mathrm{rep}_S(n)`$ (so $`\mathrm{rep}_S=\mathrm{val}_S^1`$). In particular, these abstract systems generalize the well known class of positional linear numeration systems built upon a Pisot number . These latter systems are constructed on a strictly increasing sequence of integers satisfying a linear recurrence relation whose characteristic polynomial is the minimal polynomial of a Pisot number (a Pisot number is an algebraic integer $`\theta >1`$ whose Galois conjugates have modulus less than one).

A numeration system has to be able to represent not only integers but also real numbers. So in  we described how to obtain the representations of the elements belonging to an interval of real numbers of the form $`[1/\theta ,1]`$ in an abstract numeration system (and therefore using some conventions we can represent $`[0,1]`$). Let $`k\{0,1\}`$. In the $`k`$-ary numeration system, a real number $`x(0,1)`$ is represented by an infinite word $`w=w_0w_1w_2\mathrm{}`$. On the one hand, we have finite prefixes $`w_0\mathrm{}w_{n1}`$ of $`w`$ converging to the infinite word $`w`$. On the other hand, each prefix $`w_0\mathrm{}w_{n1}`$ gives rise to a numerical approximation

(1)
$$\frac{_{i=0}^{n1}w_ik^{ni1}}{k^n}$$

and the sequence of these numerical approximations is converging to the real number $`x`$. Actually, the numerator in (1) is the numerical value in base $`k`$ of $`w_0\mathrm{}w_{n1}`$ and the denominator is the number of words of length at most $`n`$ in the language $`\{\epsilon \}\{1,\mathrm{},k1\}\{0,\mathrm{},k1\}^{}`$ associated to the $`k`$-ary system. Having in mind these two kinds of convergence, we proceed in the same way for an abstract system built upon a regular language $`L`$ and consider sequences of words in $`L`$ converging to an infinite word. Mimicking the formula (1), the numerical approximation given by a word $`wL\mathrm{\Sigma }^n`$ is

$$\frac{\mathrm{val}_S(w)}{𝐯(n)}.$$

Under suitable assumptions, a sequence of numerical approximations is convergent whenever the corresponding sequence of words is convergent .

## 3. Framework for the representation of real numbers

To represent real numbers in an abstract numeration system, we consider converging sequences of words in $`L`$. So we introduce the following notation

$$_{\mathrm{}}=\{w\mathrm{\Sigma }^\omega (w_n)_nL^{}:\underset{n\mathrm{}}{lim}w_n=w\}.$$

This set dedicated to be the set of the representations of the considered real numbers (the interval of real numbers that we are able to represent will be make explicit soon). Therefore $`_{\mathrm{}}`$ has to be uncountable (because we want to represent an interval of real numbers which is uncountable). In , to be able to prove the convergence of the numerical approximations, we considered the following work hypothesis concerning the asymptotic behavior of the sequences $`𝐮_q(n)`$’s.

Hypothesis. The set $`_{\mathrm{}}`$ is uncountable and for all states $`q`$ of $`_L`$, either

* $`N_q:`$ $`n>N_q`$, $`𝐮_q(n)=0`$ or
* there exist $`\theta _q1`$, $`P_q(x)[x]`$ and $`b_q>0`$ such that

$$\underset{n\mathrm{}}{lim}\frac{𝐮_q(n)}{P_q(n)\theta _q^n}=b_q.$$

Since $`_{\mathrm{}}`$ is uncountable, it can be shown that the language $`L`$ has an exponential growth and therefore $`\theta =\theta _{q_0}>1`$.

By choosing the coefficient of the dominant term in $`P_{q_0}`$ (or in the same way by replacing $`P_{q_0}`$ with $`P_{q_0}/b_{q_0}`$), we may assume in what follows that

$$\underset{n\mathrm{}}{lim}\frac{𝐮_{q_0}(n)}{P_{q_0}(n)\theta ^n}=1.$$

For all states $`q`$ of $`_L`$, the following limit exists

$$\underset{n\mathrm{}}{lim}\frac{𝐮_q(n)}{P_{q_0}(n)\theta ^n}$$

and we denote by $`a_q0`$ its value ($`a_{q_0}=1`$). For details, see .

###### Remark 1.

If a state $`q`$ is such that $`d(P_q)<d(P_{q_0})`$ or $`\theta _q<\theta `$ then $`a_q=0`$.

###### Proposition 2.

\[11, Corollary 7\] If $`(w_n)_nL^{}`$ is converging to an infinite word $`w_{\mathrm{}}`$ then

$$\underset{n\mathrm{}}{lim}\frac{\mathrm{val}_S(w_n)}{𝐯(|w_n|)}=\frac{\theta 1}{\theta ^2}\underset{qQ}{}a_q\underset{j=0}{\overset{\mathrm{}}{}}\beta _{q,j}\theta ^j=x$$

where the coefficients $`\beta _{q,j}`$ depends only on $`w`$.

In this latter proposition, the infinite word $`w`$ is said to be a representation of the real number $`x`$. In the same way, $`x`$ is said to be the numerical value of $`w`$. Each real number in $`[1/\theta ,1]`$ has at least one representation in $`_{\mathrm{}}`$. Conversely, each infinite word in $`_{\mathrm{}}`$ is the representation of a unique number in $`[1/\theta ,1]`$.

###### Remark 3.

We know precisely what are the coefficients $`\beta _{q,j}`$’s introduced in Proposition 2. If the infinite word $`w`$ is written $`w_0w_1\mathrm{}`$ then for all states $`q`$

$$\beta _{q,j}=\mathrm{\#}\{\sigma <w_jq_0.w_0\mathrm{}w_{j1}\sigma =q\}+\delta _{q,q_0}$$

where $`\delta `$ is the Kronecker’s symbol. As noticed in , those coefficients can be computed by a transducer $`𝒯`$ built upon $`_L`$. If $`Q=\{q_0,q_1,\mathrm{},q_r\}`$ and if in $`_L`$, $`p.\sigma =p^{}`$ then in $`𝒯`$, the directed edge between $`p`$ and $`p^{}`$ is labeled by $`(\sigma ,n_0,n_1,\mathrm{},n_r)`$ where

$$n_i=\mathrm{\#}\{\tau <\sigma p.\tau =q_i\}+\delta _{i,0}.$$

The reading in $`𝒯`$ of the $`n`$th letter of a word $`w=w_0w_1\mathrm{}`$ gives the $`(r+1)`$-uple $`(\beta _{q_0,n},\mathrm{},\beta _{q_r,n})`$ corresponding to $`w`$, $`n0`$.

###### Example 4.

Consider the language made up of the words containing an even number of $`a`$’s (we assume that $`a<b`$). The transducer computing simultaneously the coefficients $`\beta _{q_0,n}`$ and $`\beta _{q_1,n}`$ is given in Figure 1.

## 4. Syntactical properties of the periods in $`_{\mathrm{}}`$

In this section, we are interested in the syntactical properties of the ultimately periodic representations of real numbers. Namely, if $`uv^\omega `$ is an element in $`_{\mathrm{}}`$ then what can be said about the syntax of $`u`$ or $`v`$ ? Are the words $`u`$ and $`v`$ related in some way to $`L`$ ?

###### Definition 5.

Let $`X`$ be a set of infinite words. The set of the periods of the ultimately periodic words in $`X`$ is denoted $`\mathrm{per}(X)`$ and is defined by

$$v\mathrm{per}(X)u\mathrm{\Sigma }^{}:uv^\omega X.$$

In the same way, we can also define the set $`\mathrm{aper}(X)`$ of the aperiodic parts of the ultimately periodic words in $`X`$,

$$u\mathrm{aper}(X)v\mathrm{\Sigma }^+:uv^\omega X.$$

###### Example 6.

The periodic and aperiodic parts of a word are not necessarily unique. Consider the word

$$w=aba(ab)^\omega ,$$

we have $`\mathrm{per}(\{w\})=\{(ab)^ii>0\}`$ and $`\mathrm{aper}(\{w\})`$ contains any prefix of $`w`$ of length at least $`3`$. Nevertheless, the minimal aperiodic prefix is $`aba`$ and to this prefix is corresponding the period $`ab`$ of minimal length.

The first aim of this section is to show that $`\mathrm{per}(_{\mathrm{}})\mathrm{\Sigma }^{}`$ is a regular language. Next we shall see that $`\mathrm{aper}(_{\mathrm{}})\mathrm{\Sigma }^{}`$ is also regular.

In the following lemma, we are interested in the states reached in $`_L`$ when reading an ultimately periodic word.

###### Lemma 7.

Let $`(x_n)_n=uv^\omega `$ be an ultimately periodic word of $`_{\mathrm{}}`$, the word

$$\xi =(q_0,x_0)(q_0.x_0,x_1)(q_0.x_0x_1,x_2)\mathrm{}(q_0.x_0\mathrm{}x_n,x_{n+1})\mathrm{}(Q\times \mathrm{\Sigma })^\omega $$

is ultimately periodic of period $`t|v|`$ for some $`t\mathrm{\#}Q`$.

###### Proof.

We use the same kind of reasoning as in the proof of the classical pumping lemma (\[19, Lemma 4.1\]). If $`\mathrm{\#}Q=r`$ then, for any $`qQ`$, at least two states of the following list of $`r+1`$ states are the same

$$q,q.v,\mathrm{},q.v^r.$$

So for $`q=q_0.u`$, there exist $`i`$, $`j`$, $`0i<jr`$, such that $`q^{}=q.v^i=q.v^j`$. Thus in $`_L`$ after reading $`v^{ji}`$ from this state $`q^{}`$, we are back in $`q^{}`$ and we have still to read $`v^\omega `$. The deterministic behavior of $`_L`$ leads to the conclusion. Notice that the period of $`\xi `$ is bounded by $`(ji)|v|\mathrm{\#}Q|v|`$. ∎

We now present the construction of an automaton $`𝔐`$ that will be used to show that $`\mathrm{per}(_{\mathrm{}})`$ is regular.

###### Definition 8.

Let us define a set $`𝒞2^Q\{\mathrm{}\}`$. A set $`C=\{p_1,\mathrm{},p_k\}`$ of states belongs to $`𝒞`$ if and only if the following two conditions are satisfied

1. $`C`$ is a cycle in $`_L`$ : there exists a word $`w=w_1\mathrm{}w_{\mathrm{}}\mathrm{\Sigma }^{\mathrm{}}`$, $`\mathrm{}k`$, such that

* $`p_1.w=p_1`$,
    * $`i\mathrm{}`$, $`p_1.w_1\mathrm{}w_iC`$,
    * $`ik`$, $`j\mathrm{}`$: $`p_1.w_1\mathrm{}w_j=p_i`$.
2. $`C`$ is coaccessible : there exist $`p_iC`$ and $`w\mathrm{\Sigma }^{}`$ such that $`p_i.wF`$.

###### Remark 9.

Let $`C𝒞`$. The set $`C`$ is also accessible. Indeed, since $`_L`$ is minimal, it is accessible. So for each state $`pC`$, there exists a word $`w`$ such that $`q_0.w=p`$.

Another observation is the following. In Definition 8, the cycle given by the word $`w=w_1\mathrm{}w_{\mathrm{}}`$ is not necessarily an Hamiltonian circuit.

It is clear that $`𝒞`$ is ordered by inclusion. We denote by $`C_1,\mathrm{},C_t`$ the maximal elements of $`(𝒞,)`$. (As a consequence of the maximality, for $`ij`$, $`C_iC_j=\mathrm{}`$. Indeed, if a state belongs to $`C_iC_j`$ then $`C_iC_j`$ belongs to $`𝒞`$ because we can find a longer cycle in $`_L`$ and therefore neither $`C_i`$ nor $`C_j`$ is maximal.)

Let $`i\{1,\mathrm{},t\}`$, $`C_i=\{p_1^{(i)},\mathrm{},p_{r_i}^{(i)}\}`$ ($`r_i1`$) and $`j\{1,\mathrm{},r_i\}`$. For each such indices $`i`$ and $`j`$, we define a NFA $`_{i,j}`$ in the following way,

$$_{i,j}=(C_i,p_j^{(i)},\mathrm{\Sigma },\delta |_{C_i\times \mathrm{\Sigma }\times C_i},\{p_j^{(i)}\}),$$

the set of states is $`C_i`$, the initial state is $`p_j^{(i)}`$ and the transition relation is the restriction of the transition function $`\delta `$ of $`_L`$ to the states belonging to $`C_i`$ : $`\delta (p,\sigma )=q`$ with $`p,qC_i`$ iff $`(p,\sigma ,q)`$ belongs to $`\delta |_{C_i\times \mathrm{\Sigma }\times C_i}`$. The state $`p_j^{(i)}`$ is the unique final state of $`_{i,j}`$. (Observe that the automaton $`_{i,j}`$ is non-deterministic only because the function $`\delta `$ is not necessarily complete.)

Let $`𝔐`$ be the NFA obtained as the union of the different $`_{i,j}`$’s. In this construction we assume that the sets of states of two distinct automata $`_{i,j}`$’s are disjoint. To obtain the union, we only have to consider a set of initial states instead of a single one.

###### Example 10.

Let us consider the trim minimal automaton depicted in Figure 2 (the sink has not been represented, this state is never coaccessible so it never belong to a set in $`𝒞`$).

Here $`𝒞=\{\{3,4\},\{2,3,4\}\}`$ and we have a single maximal element $`C_1=\{2,3,4\}`$ in $`(𝒞,)`$. The corresponding NFA $`𝔐`$ is given in Figure 3. (We have three initial states.) With our notation, this automaton is built (from left to right in Figure 3) upon the automata $`_{1,2}`$, $`_{1,4}`$ and $`_{1,3}`$.

Let $`k>0`$. Recall that a word $`u`$ belongs to the $`k`$th-root $`\sqrt[k]{L}`$ of a language $`L`$ if and only if $`u^k`$ belongs to $`L`$. If $``$ is an automaton (deterministic or not), the language accepted by $``$ is denoted $`L()`$.

###### Proposition 11.

We have

$$\mathrm{per}(_{\mathrm{}})=\underset{k=1}{\overset{\mathrm{\#}Q}{}}\sqrt[k]{L(𝔐)}.$$

In particular $`\mathrm{per}(_{\mathrm{}})`$ is regular.

###### Proof.

Let $`w^kL(𝔐)`$ for some $`k\mathrm{\#}Q`$. This means that $`w^k`$ is accepted by some $`_{i,j}`$ and $`p_j^{(i)}.w^k=p_j^{(i)}`$. By definition of $`𝒞`$ and $`_{i,j}`$, it is clear that in $`_L`$, there exist $`x`$ and $`y`$ in $`\mathrm{\Sigma }^{}`$ such that $`q_0.x=p_j^{(i)}`$ and $`p_j^{(i)}.yF`$. Therefore, we have

$$n,xw^{kn}yL$$

and $`xw^\omega _{\mathrm{}}`$ since $`xw^{kn}yxw^\omega `$ if $`n`$ tends to infinity. So $`w`$ is a period of an ultimately periodic word in $`_{\mathrm{}}`$.

Let $`w`$ be an element of $`\mathrm{per}(_{\mathrm{}})`$. There exists an ultimately periodic word $`u=vw^\omega =u_0u_1u_2\mathrm{}_{\mathrm{}}`$ having $`w`$ as period. By Lemma 7

$$\xi =(q_0,u_0)(q_0.u_0,u_1)(q_0.u_0u_1,u_2)\mathrm{}(q_0.u_0\mathrm{}u_n,u_{n+1})\mathrm{}$$

is ultimately periodic of period $`t|w|`$ for some $`t\mathrm{\#}Q`$. We can write $`\xi =\alpha \beta ^\omega `$.

After an initial mess $`\alpha `$, the periodic part $`\beta ^\omega `$ of $`\xi `$ begins. In this latter part, there is a position $`(q,\sigma )`$ corresponding to the first reading of the beginning of $`w`$. (Imagine that the words $`u`$ and $`\xi `$ are written on two tapes which are read simultaneously by a single head one element at a time, so to the $`n`$th letter of $`u`$ corresponds exactly the $`n`$th element of $`\xi `$. This situation is depicted schematically in Figure 4.) By periodicity of $`\xi `$, after reading $`t|w|`$ letters, we are again in the same position $`(q,\sigma )`$ and by periodicity of $`(u_n)_n`$, we are ready to read the beginning of a new occurrence of $`w`$. This means that we have in $`_L`$ a cycle containing $`q`$ and such that $`q.w^t=q`$. So clearly $`w^t`$ is accepted by some previously defined automaton $`_{i,j}`$ having $`q`$ as initial state. In other words, since $`t\mathrm{\#}Q`$,

$$w\sqrt[t]{L(𝔐)}\underset{k=1}{\overset{\mathrm{\#}Q}{}}\sqrt[k]{L(𝔐)}.$$

We can conclude, applying Lemma 12 below. ∎

###### Lemma 12.

If $`L`$ is a regular language then for $`k1`$, $`\sqrt[k]{L}`$ is also regular.

For the sake of completeness, we recall the proof of Lemma 12.

###### Proof.

If $`q=q_0.w`$ is a state of $`_L`$ then

$$q=w^1.L=\{v\mathrm{\Sigma }^{}wvL\}$$

is a regular language. For the properties of the minimal automaton of a language, we refer to \[3, III.5\]. We define the language

$$𝒮(q)=\{m\mathrm{\Sigma }^{}q=m^1.L\}.$$

This language is also regular. If $`Q`$ is the finite set of states of $`_L`$, then for $`k>0`$ the following formula holds

$$\sqrt[k+1]{L}=\underset{qQ}{}(𝒮(q)\sqrt[k]{q}).$$

Hence we obtain the conclusion by using an easy induction argument. ∎

We can now show that $`\mathrm{aper}(_{\mathrm{}})`$ is regular.

If $`q`$ is a state belonging to a maximal element $`C_i`$ of $`𝒞`$ then we denote by $`_q`$ the DFA $`_q=(Q,q_0,\mathrm{\Sigma },\delta ,\{q\})`$ built upon the minimal automaton of $`L`$ where the set of final states is replaced by $`\{q\}`$. The following proposition is obvious.

###### Proposition 13.

If the maximal elements of $`𝒞`$ are $`C_1,\mathrm{},C_t`$ then

$$\mathrm{aper}(_{\mathrm{}})=\underset{qC_1\mathrm{}C_t}{}L(_q)$$

and this language is therefore regular.

###### Proposition 14.

The language $`\mathrm{uper}(_{\mathrm{}})\mathrm{\Sigma }^\omega `$ of the ultimately periodic words in $`_{\mathrm{}}`$ is $`\omega `$-rational.

###### Proof.

If the maximal elements of $`𝒞`$ are $`C_1,\mathrm{},C_t`$ then, using the previous notation for the automata $`_q`$, we have

$$\mathrm{uper}(_{\mathrm{}})=\underset{i=1}{\overset{t}{}}\left[\underset{qC_i}{}L(_q)\left(\underset{k=1}{\overset{\mathrm{\#}C_i}{}}\sqrt[k]{L(_{i,q})}\right)^\omega \right]$$

where $`_{i,q}`$ is the NFA having $`C_i`$ as set of states and $`q`$ as initial and final state. In this formula, the dot “$``$” represents the concatenation. Hence the conclusion, using classical results on $`\omega `$-rational languages . ∎

## 5. Computing the values of ultimately periodic representations

Thanks to Proposition 2, the numerical value of an ultimately periodic word in $`_{\mathrm{}}`$ can be easily computed. As a consequence of Remark 3, if $`w`$ is an infinite ultimately periodic word with a period of length $`\mathrm{}`$ then the corresponding sequence $`(\beta _{q,n})_n`$ is ultimately periodic with a period of length bounded by $`\mathrm{\#}Q.\mathrm{}`$.

The following lemma is obvious.

###### Lemma 15.

If $`(\alpha _n)_n`$ is an ultimately periodic sequence of real numbers of the form $`\alpha _0,\mathrm{},\alpha _{r1},(\alpha _r,\mathrm{},\alpha _{r+p1})^\omega `$ then

$$\underset{j=0}{\overset{\mathrm{}}{}}\alpha _j\theta ^j=\underset{j=0}{\overset{r1}{}}\alpha _j\theta ^j+\frac{\theta ^p}{\theta ^p1}\underset{j=r}{\overset{r+p1}{}}\alpha _j\theta ^j.$$

If $`(\beta _{q,n})_n`$ is ultimately periodic, we denote by $`r_q`$ the minimal length of its aperiodic part and by $`p_q`$ the length of the corresponding minimal period of the sequence. As a consequence of Proposition 2 and Lemma 15, if $`(w_n)_nL^{}`$ is converging to an ultimately periodic word $`w`$ corresponding to ultimately periodic sequences $`(\beta _{q,n})_n`$, then we have

(2)
$$\underset{n\mathrm{}}{lim}\frac{\mathrm{val}_S(w_n)}{𝐯(|w_n|)}=\frac{\theta 1}{\theta ^2}\underset{qQ}{}a_q\left(\underset{j=0}{\overset{r_q1}{}}\beta _{q,j}\theta ^j+\frac{\theta ^{p_q}}{\theta ^{p_q}1}\underset{j=r_q}{\overset{r_q+p_q1}{}}\beta _{q,j}\theta ^j\right).$$

If $`r=\mathrm{max}_{qQ}r_q`$ and $`p=\mathrm{lcm}_{qQ}p_q`$ then

(3)
$$\underset{n\mathrm{}}{lim}\frac{\mathrm{val}_S(w_n)}{𝐯(|w_n|)}=\frac{\theta 1}{\theta ^2}\left(\underset{j=0}{\overset{r1}{}}(\underset{qQ}{}a_q\beta _{q,j})\theta ^j+\frac{\theta ^p}{\theta ^p1}\underset{j=r}{\overset{r+p1}{}}(\underset{qQ}{}a_q\beta _{q,j})\theta ^j\right).$$

###### Remark 16.

The coefficients $`_{qQ}a_q\beta _{q,j}`$ could also be computed by a transducer built in a similar way as $`𝒯`$.

With formulas (2) or (3), we can compute easily the real number represented by an ultimately periodic word.

Moreover, $`\theta `$ is an eigenvalue of the adjacency matrix $`A`$ of $`_L`$ and $`\stackrel{}{a}=(a_{q_0},a_{q_1},\mathrm{},a_{q_r})`$ is one of its eigenvectors (recall that if $`p,qQ`$ then the adjacency matrix is defined by $`A_{p,q}=\mathrm{\#}\{\sigma \mathrm{\Sigma }p.\sigma =q\}`$). For $`n1`$ and $`pQ`$, it is obvious that

$$𝐮_p(n)=\underset{qQ}{}A_{p,q}𝐮_q(n1).$$

Dividing both sides by $`P_{q_0}(n)\theta ^n`$ and letting $`n`$ tend to infinity, we obtain

$$a_p=\frac{1}{\theta }\underset{qQ}{}A_{p,q}a_q.$$

So $`A\stackrel{}{a}=\theta \stackrel{}{a}`$. This latter observation could be useful to determine in a practical way the value of $`\stackrel{}{a}`$ (remember that we have chosen $`a_{q_0}`$ to be equal to $`1`$).

To conclude this section, we show that the set of ultimately periodic words in $`_{\mathrm{}}`$ is dense in $`_{\mathrm{}}`$. This can be related to the classical fact that for the base $`10`$ system, $``$ is exactly the set of numbers having an ultimately periodic representation and $``$ is dense in $``$.

###### Proposition 17.

The set $`\mathrm{uper}(_{\mathrm{}})\mathrm{\Sigma }^\omega `$ of the ultimately periodic words in $`_{\mathrm{}}`$ is dense in $`_{\mathrm{}}`$

###### Proof.

Let $`w_{\mathrm{}}`$. By definition of the set, there exists a sequence $`(w_n)_n`$ of words in $`L`$ such that $`w_nw`$. For any $`\mathrm{}>0`$ there exist $`N`$ such that $`w`$ and $`w_N`$ have a common prefix of length $`\mathrm{}`$ and $`|w_N|\mathrm{}+\mathrm{\#}Q`$. When reading the suffix of length $`\mathrm{\#}Q`$ of $`w_N`$ in $`_L`$ we go at least twice through the same state $`q`$ and let $`u`$ be the corresponding factor of $`w_N`$ such that $`q.u=q`$. Therefore, $`w_N`$ can be written $`xuz`$ with $`|x|l`$ and it is clear that $`xu^nzL`$ for all $`n1`$. So $`xu^\omega _{\mathrm{}}`$ and has a prefix of length $`\mathrm{}`$ in common with $`w`$. We can therefore build a sequence of ultimately periodic words converging to $`w`$. ∎

## 6. Simplifying the language

In the first part of this section, we explain how a real number can have more than one representation and even an infinite number of representations. Next, we explain, how we can slightly change the language to avoid this situation of having an infinite number of representations but without altering the other representations.

In , we gave a partition of the interval $`[1/\theta ,1]`$ into intervals $`I_w`$. These intervals will play a central role in what follows so let us recall their definition. First consider the $`k`$-ary system. In this system, the representation of a real number $`x[1/10,1]`$ has a prefix $`w=w_0\mathrm{}w_n`$ ($`w_00`$) if $`x`$ belongs to the interval

$$I_w=[\frac{_{i=0}^{n1}w_ik^{ni1}}{k^n},\frac{1+_{i=0}^{n1}w_ik^{ni1}}{k^n}]$$

Observe that the endpoints of the intervals $`I_w`$ are the only numbers having two representations. For instance, if $`k=10`$ then $`2/10`$ can be written $`0,1999\mathrm{}`$ and $`2/10`$ is the upper bound of $`I_1`$ but it can also be written $`0,2000\mathrm{}`$ and is the lower bound of $`I_2`$. For an abstract numeration system, we have the following definition.

###### Definition 18.

A real number $`x[1/\theta ,1]`$ belongs to $`I_w`$ if there exist a representation of $`x`$ having $`w`$ as prefix.

For an arbitrary regular language $`L`$, the set $`_{\mathrm{}}`$ can contains an infinite number of words having $`w`$ as prefix even if the length of the interval $`I_w`$ is zero. In this situation, all the elements of $`_{\mathrm{}}`$ having $`w`$ as prefix are representing the same real number $`x`$ and $`I_w=[x,x]`$. Therefore $`x`$ has an infinite number of representations. To avoid this situation, we proceed as follows.

We can only consider the states $`q`$ such that $`a_q>0`$. We have the following rules

* If $`a_q0`$ and there exists $`w`$ such that $`p.w=q`$, then $`a_p0`$.
* If $`a_q=0`$ and there exists $`w`$ such that $`q.w=p`$, then $`a_p=0`$.

Indeed, in the first case, if $`p.w=q`$ then $`𝐮_n(p)𝐮_{n|w|}(q)`$. In the second case, if $`q.w=p`$ then $`𝐮_n(q)𝐮_{n|w|}(p)`$. Hence we obtain the conclusion by dividing both sides by $`P_{q_0}(n)\theta ^n`$.

We can split the set of states of $`_L`$ into two subsets $`Q_0=\{qa_q=0\}`$ and $`Q_{>0}=\{qa_q>0\}`$. If we consider only the states of $`Q_{>0}`$ and the corresponding edges connecting those states, we obtain a new automaton accepting a new language $`L^{}`$. Representations of real numbers for the numeration system built upon $`L`$ or $`L^{}`$ are the same except that for the system built on $`L^{}`$ a real number has at most two representations (only when it is the endpoint of some interval $`I_w`$).

###### Example 19.

We consider the language $`L`$ accepted by the automaton depicted in Figure 5. This language is such that the number of words beginning with $`b`$ (resp. $`a`$ or $`c`$) has a polynomial (resp. exponential) behavior.

This means that the length of the interval $`I_b`$ is zero (computations are given in \[11, Example 6\]). Therefore the greatest word in the lexicographical ordering of $`_{\mathrm{}}`$ beginning with $`a`$ represents the same real number $`x`$ as any word in $`_{\mathrm{}}`$ beginning with $`b`$ or the smallest word beginning with $`c`$. Removing the states of $`Q_0`$, gives a new language $`L^{}`$. In the numeration system built upon $`L^{}`$, the number $`x`$ has exactly two representations: the greatest word beginning with $`a`$ and the smallest one beginning with $`c`$. In this latter system, if $`w`$ is prefix of an infinite number of words in $`L`$ then the length of the interval $`I_w`$ is strictly positive.

In the following of this paper, we shall assume that $`a_q>0`$ for all states $`q`$ in $`_L`$ except possibly for the sink state.

## 7. Determining the numbers having an ultimately periodic representation

Let us have a closer look at those intervals $`I_w`$ (for the details, the reader is referred to ). If $`w\mathrm{\Sigma }^{\mathrm{}}`$ is prefix of an infinite number of words in $`L`$ then the interval $`I_w`$ is given by

(4)
$$[\underset{n\mathrm{}}{lim}\left(\frac{𝐯(n1)}{𝐯(n)}+\underset{\begin{array}{c}m\mathrm{\Sigma }^{\mathrm{}}\\ m<w\end{array}}{}\frac{𝐮_{q_0.m}(n\mathrm{})}{𝐯(n)}\right),\underset{n\mathrm{}}{lim}\left(\frac{𝐯(n1)}{𝐯(n)}+\underset{\begin{array}{c}m\mathrm{\Sigma }^{\mathrm{}}\\ mw\end{array}}{}\frac{𝐮_{q_0.m}(n\mathrm{})}{𝐯(n)}\right)]$$

Using the fact that (see \[11, Proposition 5\])

(5)
$$\{\begin{array}{c}lim_n\mathrm{}𝐯_q(n)/𝐯(n)=a_q\hfill \\ lim_n\mathrm{}𝐮_q(n)/𝐯_q(n)=(\theta 1)/\theta \hfill \end{array}$$

the interval $`I_w`$ be rewritten as

(6)
$$[\frac{1}{\theta }+\frac{\theta 1}{\theta ^{\mathrm{}+1}}\underset{\begin{array}{c}m\mathrm{\Sigma }^{\mathrm{}}\\ m<w\end{array}}{}a_{q_0.m},\frac{1}{\theta }+\frac{\theta 1}{\theta ^{\mathrm{}+1}}\underset{\begin{array}{c}m\mathrm{\Sigma }^{\mathrm{}}\\ mw\end{array}}{}a_{q_0.m}].$$

Notice that this formulation differs slightly from  because we have here $`a_{q_0}=1`$ and the others $`a_q`$’s are strictly positive (except for the sink). Observe also that the length of $`I_w`$ is $`\frac{\theta 1}{\theta ^{\mathrm{}+1}}a_{q_0.w}>0`$.

###### Remark 20.

Notice that if $`w\mathrm{\Sigma }^{}`$ is prefix of an infinite number of words in $`L`$ then $`q_0.w`$ is a coaccessible state (so it cannot be the sink) and with our assumptions, $`a_{q_0.w}>0`$.

###### Example 21.

Consider the numeration system associated to the language accepted by the automaton depicted in Figure 6.

Here, easy computations show that $`\theta =2`$, $`a_{q_0}=a_{q_2}=1`$ and $`a_{q_1}=2`$ (to obtain the $`a_q`$’s, one has only to compute the eigenvectors of the eigenvalue $`\theta `$ of the adjacency matrix). Any word in $`_{\mathrm{}}`$ begins with $`a`$, so $`I_a=[1/2,1]`$ (instead of this reasoning, formula (6) could also be used to compute the values of the endpoints of $`I_a`$). This interval is partitioned into three parts,

$$I_{aa}=[1/2,5/8],I_{ab}=[5/8,3/4],I_{ac}=[3/4,1].$$

Thus if a real number $`x`$ belongs to $`I_{a\sigma }`$ then we have an infinite word representing $`x`$ beginning with $`a\sigma `$, $`\sigma \mathrm{\Sigma }`$. For the next step, we have

$$I_{aac}=I_{aa}=[1/2,5/8],I_{aba}=I_{ab}=[5/8,3/4]$$

and $`I_{ac}`$ is split into three parts

$$I_{aca}=[3/4,5/6],I_{acb}=[5/6,7/8],I_{aca}=[7/8,1].$$

Actually the form of the partition of an interval $`I_w`$ into intervals $`I_{w\sigma }`$ depends only on the state $`q_0.w`$ and not on the word $`w`$ itself.

###### Definition 22.

If $`0\lambda <\mu 1`$, the strictly increasing function

$$f_{[\lambda ,\mu ]}:[\lambda ,\mu ][0,1]:x\frac{x\lambda }{\mu \lambda }$$

maps the interval $`[\lambda ,\mu ]`$ onto $`[0,1]`$. If $`z`$ belongs to $`[\lambda ,\mu ]`$ then we say that $`f_{[\lambda ,\mu ]}(z)`$ is the relative position of $`z`$ inside $`[\lambda ,\mu ]`$. We denote by $`L_w`$ (resp. $`U_w`$) the lower (resp. upper) bound of the interval $`I_w`$.

Roughly speaking, the next proposition states that two intervals corresponding to the same state are homothetic. But first, we need a technical lemma.

###### Lemma 23.

We have, for all states $`q`$,

$$\underset{\sigma \mathrm{\Sigma }}{}a_{q.\sigma }=\theta a_q$$

in particular, $`_{\sigma \mathrm{\Sigma }}a_{q_0.\sigma }=\theta `$.

###### Proof.

Clearly, $`I_w=_{\sigma \mathrm{\Sigma }}I_{w\sigma }`$ and the length of $`I_w`$ is equal to $`_{\sigma \mathrm{\Sigma }}|I_{w\sigma }|`$. The conclusion follows directly from (6). ∎

###### Proposition 24.

Let $`m`$ and $`w`$ be two words such that $`q_0.m=q_0.w`$. For all $`\sigma \mathrm{\Sigma }`$, the interval $`I_{m\sigma }`$ exists<sup>1</sup><sup>1</sup>1An interval $`I_w`$ exists if there exists a word in $`_{\mathrm{}}`$ having $`w`$ as prefix. This means that $`w`$ is prefix of an infinite number of words in $`L`$. iff $`I_{w\sigma }`$ exists and the relative position of $`L_{m\sigma }`$ (resp. $`U_{m\sigma }`$) inside $`I_m`$ is equal to the relative position of $`L_{w\sigma }`$ (resp. $`U_{w\sigma }`$) inside $`I_w`$.

###### Proof.

The interval $`I_{m\sigma }`$ exists if $`a_{q_0.m\sigma }>0`$. Since $`q_0.m=q_0.w`$ then for all $`\sigma \mathrm{\Sigma }`$, $`a_{q_0.m\sigma }>0`$ iff $`a_{q_0.w\sigma }>0`$. Using (6), the relative position of $`L_{m\sigma }`$ inside $`I_m`$ is given by

$$\left(L_{m\sigma }\frac{1}{\theta }\frac{\theta 1}{\theta ^{|m|+1}}\underset{\begin{array}{c}u\mathrm{\Sigma }^{|m|}\\ u<m\end{array}}{}a_{q_0.u}\right)/\left(\frac{\theta 1}{\theta ^{|m|+1}}a_{q_0.m}\right)$$

this can be rewritten as

$$\frac{\theta ^{|m|}}{(\theta 1)a_{q_0.m}}(\theta L_{m\sigma }1)\underset{\begin{array}{c}u\mathrm{\Sigma }^{|m|}\\ u<m\end{array}}{}\frac{a_{q_0.u}}{a_{q_0.m}}$$

and using the definition of $`L_{m\sigma }`$, we get

(7)
$$\frac{1}{a_{q_0.m}}\left(\frac{1}{\theta }\underset{\begin{array}{c}u\mathrm{\Sigma }^{|m|+1}\\ u<m\sigma \end{array}}{}a_{q_0.u}\underset{\begin{array}{c}u\mathrm{\Sigma }^{|m|}\\ u<m\end{array}}{}a_{q_0.u}\right).$$

First notice that the sum over the words $`u`$ of length $`|m|+1`$ and lexicographically less than $`m\sigma `$ can be split into two subsets: the words $`m\tau `$ with $`\tau <\sigma `$ and the words having a prefix of length $`|m|`$ lexicographically less than $`m`$. So (7) can be written

$$\frac{1}{a_{q_0.m}}\left[\frac{1}{\theta }\left(\underset{\begin{array}{c}\tau \mathrm{\Sigma }\\ \tau <\sigma \end{array}}{}a_{q_0.m\tau }+\underset{\begin{array}{c}u\mathrm{\Sigma }^{|m|+1}\\ pref_{|m|}(u)<m\end{array}}{}a_{q_0.u}\right)\underset{\begin{array}{c}u\mathrm{\Sigma }^{|m|}\\ u<m\end{array}}{}a_{q_0.u}\right]$$

where $`pref_{|m|}(u)<m`$ means that the prefix of length $`|m|`$ of $`u`$ is lexicographically less than $`m`$. To conclude the proof, notice that

$$\underset{\begin{array}{c}u\mathrm{\Sigma }^{|m|+1}\\ pref_{|m|}(u)<m\end{array}}{}a_{q_0.u}=\underset{\begin{array}{c}u^{}\mathrm{\Sigma }^{|m|}\\ u^{}<m\end{array}}{}\underset{\sigma \mathrm{\Sigma }}{}a_{q_0.u^{}\sigma }$$

and using Lemma 23, we have

$$\frac{1}{\theta }\underset{\begin{array}{c}u\mathrm{\Sigma }^{|m|+1}\\ pref_{|m|}(u)<m\end{array}}{}a_{q_0.u}\underset{\begin{array}{c}u\mathrm{\Sigma }^{|m|}\\ u<m\end{array}}{}a_{q_0.u}=\frac{1}{\theta }\underset{\begin{array}{c}u^{}\mathrm{\Sigma }^{|m|}\\ u^{}<m\end{array}}{}\theta a_{q_0.u^{}}\underset{\begin{array}{c}u\mathrm{\Sigma }^{|m|}\\ u<m\end{array}}{}a_{q_0.u}=0.$$

So the relative position of $`L_{m\sigma }`$ inside $`I_m`$ is

(8)
$$\frac{1}{\theta a_{q_0.m}}\underset{\begin{array}{c}\tau \mathrm{\Sigma }\\ \tau <\sigma \end{array}}{}a_{q_0.m\tau }$$

and depends only on the state $`q_0.m`$. ∎

###### Example 25.

Continuing Example 21. We have $`q_0.a=q_0.ac=q_1`$. Observe that $`I_a`$ is split into three parts ($`I_{aa}`$, $`I_{ab}`$ and $`I_{ac}`$) and the relative positions of $`5/8`$ and $`3/4`$ inside $`I_a`$ are respectively $`1/4`$ and $`1/2`$. In the same way, $`I_{ac}`$ is split into three parts ($`I_{aca}`$, $`I_{acb}`$ and $`I_{acc}`$) the relative positions of $`5/6`$ and $`7/8`$ inside $`I_{ac}`$ are also respectively $`1/4`$ and $`1/2`$.

###### Theorem 26.

A real number $`x`$ has an ultimately periodic representation if and only if there exist two words $`m`$ and $`w`$ such that

1. $`m`$ is a prefix of $`w`$,
2. $`x`$ belongs to $`I_wI_m`$,
3. $`q_0.m=q_0.w`$,
4. the relative position of $`x`$ inside $`I_m`$ is equal to the relative position of $`x`$ inside $`I_w`$.

###### Proof.

The condition is sufficient. If $`x`$ belongs to $`I_m`$ then a representation of $`x`$ has $`m`$ has prefix. The following letter of the representation depends only on the relative position of $`x`$ inside $`I_m`$. Assume that this letter is $`\sigma `$ (i.e., $`xI_{m\sigma }`$). Thanks to Proposition 24, since $`q_0.m=q_0.w`$ and the relative position of $`x`$ inside $`I_m`$ is equal to the relative position of $`x`$ inside $`I_w`$, it is clear that $`x`$ belongs to $`I_{w\sigma }`$. The same arguments can be used with $`I_{m\sigma }`$ and $`I_{w\sigma }`$ and so on. Actually, if $`w=mv`$ then the representation of $`x`$ is $`mv^\omega `$.

Assume now that $`x`$ has an ultimately periodic representation $`w=w_0w_1\mathrm{}=uv^\omega `$. It is well known that $`I_{w_0\mathrm{}w_j}I_{w_0\mathrm{}w_i}`$ for $`i<j`$. Since the automaton $`_L`$ is finite, there exist infinitely many indices $`i_1<i_2<\mathrm{}`$ and a constant $`C`$ such that

$$q_0.w_0\mathrm{}w_{i_1}=q_0.w_0\mathrm{}w_{i_2}=\mathrm{},i_1|u|\text{and}k1,i_{k+1}i_k=C|v|.$$

Assume that for any pair $`i_j<i_k`$ of such indices the relative position of $`x`$ inside $`I_{w_0\mathrm{}w_{i_j}}`$ is different from its relative position inside $`I_{w_0\mathrm{}w_{i_k}}`$. To conclude the proof, we have to show that the representation of $`x`$ is not ultimately periodic. If $`x`$ belongs to some $`I_W`$ ($`W=w_0\mathrm{}w_{i_j}`$), then $`x`$ has a representation beginning with $`W`$ and to determine the following letter of this representation, the interval $`I_W`$ is divided into intervals $`I_{W\sigma }`$. This process of dividing intervals into smaller intervals is repeated continuously and we already know that the length of $`I_W`$ is $`\frac{\theta 1}{\theta ^{|W|+1}}a_{q_0.W}𝒪(\theta ^{|W|})`$. Since relative positions of $`x`$ inside $`I_{w_0\mathrm{}w_{i_j}}`$ and $`I_{w_0\mathrm{}w_{i_k}}`$ are different, by Proposition 24 there exist $`n`$ and $`\sigma \tau `$ such that

$$xI_{w_0\mathrm{}w_{i_j}w_{i_j+1}\mathrm{}w_{i_j+n}\sigma }\text{a}ndxI_{w_0\mathrm{}w_{i_k}w_{i_k+1}\mathrm{}w_{i_k+n}\tau }.$$

Therefore $`w`$ is not ultimately periodic. ∎

Since the form of the intervals $`I_w`$ depends only on the states of $`_L`$, we can define some dynamical system.

###### Definition 27.

For each $`qQ`$, we define a partition of $`A_q=[0,1]`$ into intervals $`A_{q,\sigma }^{}`$ in the following way. Since $`_L`$ is accessible, there exists $`w`$ such that $`q=q_0.w`$. For each $`\sigma \mathrm{\Sigma }`$ such that $`I_{w\sigma }`$ exists consider the relative position $`\mathrm{}_{q,\sigma }`$ (resp. $`u_{q,\sigma }`$) of $`L_{w\sigma }`$ (resp. $`U_{w\sigma }`$) inside $`I_w`$. We denote

$$A_{q,\sigma }^{}=[\mathrm{}_{q,\sigma },u_{q,\sigma }).$$

(If $`\sigma `$ is the largest letter such that $`I_{w\sigma }`$ exists then $`A_{q,\sigma }^{}=[\mathrm{}_{q,\sigma },u_{q,\sigma }]=[\mathrm{}_{q,\sigma },1]`$.)

Let us define a function $`h:Q\times [0,1]Q\times [0,1]:(q,x)(q^{},x^{})`$ in the following manner. Since we have a partition of $`A_q`$, there exists a unique letter $`\sigma `$ such that $`xA_{q,\sigma }^{}`$ and therefore

$$\{\begin{array}{c}q^{}=q.\sigma \hfill \\ x^{}=f_{A_{q,\sigma }^{}}(x)\hfill \end{array}$$

where $`f_{A_{q,\sigma }^{}}(x)`$ denotes the relative position of $`x`$ inside $`A_{q,\sigma }^{}`$. (For the interested reader, this dynamical system looks like up to some extend to interval exchange transformations .)

###### Example 28.

Continuing Example 21. The interval $`A_{q_0}=[0,1]`$ is partitioned into a single interval $`A_{q_0,a}^{}=[0,1]`$. The interval $`A_{q_1}=[0,1]`$ is partitioned into $`A_{q_1,a}^{}=[0,1/4)`$, $`A_{q_1,b}^{}=[1/4,1/2)`$ and $`A_{q_1,c}^{}=[1/2,1]`$. Finally $`A_{q_2}=[0,1]`$ is partitioned into a single interval $`A_{q_2,c}^{}=[0,1]`$.

Let us now present two equivalent algorithms for computing the representation of a real number. We recall that $`I_\epsilon =[1/\theta ,1]`$. We denote by $`f_I(x)`$ the relative position of $`x`$ inside the interval $`I`$.

###### Algorithm 29.

Let $`x[1/\theta ,1]`$
Initialization
$`qq_0`$
$`w\epsilon `$
$`yf_{I_w}(x)`$
repeat
Determine the letter $`\sigma \mathrm{\Sigma }`$ such that $`yA_{q,\sigma }^{}`$.
$`qq.\sigma `$
$`w`$ concat$`(w,\sigma )`$
$`yf_{I_w}(x)`$
until a stop condition.

The stop condition of the algorithm can be a fixed number of $`k`$ iterations to determine the first $`k`$ letters of a representation. One could check if a representation is ultimately periodic. Indeed, if we denote by $`q_n`$ and $`y_n`$ the values of the variables $`q`$ and $`y`$ during the $`n`$th iteration of the algorithm then thanks to Theorem 26, a representation is ultimately periodic if there exist $`ij`$ such that $`q_i=q_j`$ and $`y_i=y_j`$. A variant of this algorithm is the following one.

###### Algorithm 30.

Let $`x[1/\theta ,1]`$
Initialization
$`qq_0`$
$`w\epsilon `$
$`I[1/\theta ,1]`$
$`xf_I(x)`$
repeat
Determine the letter $`\sigma \mathrm{\Sigma }`$ such that $`xA_{q,\sigma }^{}`$.
$`qq.\sigma `$
$`w`$ concat$`(w,\sigma )`$
$`IA_{q,\sigma }^{}`$
$`xf_I(x)`$
until a stop condition.

In this latter algorithm, a periodicity in the representation is found when $`q_i=q_j`$ and $`x_i=x_j`$.

###### Example 31.

Continuing Example 21. We can try to obtain the representation of $`x=4/7`$ using Algorithm 29. The computations are given in Table 1. At each step of the procedure, the intervals $`I_w`$ are given below their corresponding $`A_{q,\sigma }^{}`$. Observe that at two steps $`i<j`$ of the algorithm, if we have the same state $`q`$ then the intervals $`A_{q,\sigma }^{}`$ are the same but the intervals $`I_w`$ are getting smaller.

Thanks to Theorem 26, $`4/7`$ is represented by $`a(acc)^\omega `$. The iteration of the function $`h`$ introduced in Definition 27 can also be used to find the real numbers having an ultimately periodic representation, indeed here we have

$$(q_0,1/7)\stackrel{h}{}\underset{¯}{(q_1,1/7)}\stackrel{h}{}(q_2,4/7)\stackrel{h}{}(q_1,4/7)\stackrel{h}{}\underset{¯}{(q_1,1/7)}.$$

## 8. A characterization

With the abstraction of the previous section, we can summarize the informations needed to compute representations of real numbers: a finite number of partitions $`A_q=A_{q,\sigma }^{}`$ of the interval $`[0,1]`$ and the transition function of $`_L`$. The aim of this section is to give a characterization of the real numbers having an ultimately periodic representation in terms of composition of some affine functions.

###### Definition 32.

Let us consider the automaton $`_L`$ defined as follows

* The set of states is $`\{A_qqQ\}`$.
* If $`A_q`$ is partitioned into $`A_{q,\sigma _1}^{}\mathrm{}A_{q,\sigma _t}^{}`$ then we have an edge labeled by $`f_{A_{q,\sigma _i}^{}}`$ from $`A_q`$ to $`A_{q.\sigma _i}`$ (where the dot in $`q.\sigma _i`$ denotes the transition function of $`_L`$) for $`i=1,\mathrm{},t`$.
* All the states are final.

Except that the initial state is not important in what follows and that the labels of the edges have changed, $`_L`$ is more or less a copy of $`_L`$.

###### Example 33.

Continuing Example 21. Here, $`f_{A_{q_0,a}^{}}=f_{A_{q_2,c}^{}}=id`$ and

$$\{\begin{array}{cccc}f_{A_{q_1,a}^{}}:\hfill & \hfill [0,1/4][0,1]& \hfill :x& 4x,\hfill \\ f_{A_{q_1,b}^{}}:\hfill & \hfill [1/4,1/2][0,1]& \hfill :x& 4x1,\hfill \\ f_{A_{q_1,c}^{}}:\hfill & \hfill [1/2,1][0,1]& \hfill :x& 2x1.\hfill \end{array}$$

The automaton $`_L`$ is depicted in Figure 7. For the sake of simplicity, $`f_{A_{q_1,\sigma }^{}}`$ is denoted by $`f_\sigma `$, for $`\sigma =a,b,c`$ (since it does not lead to any confusion). We also put an index $`a`$ or $`c`$ to $`id`$ to remember the corresponding letter.

A path $`f_1\mathrm{}f_t`$ in $`_L`$ corresponds to the composition of affine functions $`f_t\mathrm{}f_1`$ in reversed order. Through $`_L`$, we can determine the real numbers having ultimately periodic representations.

Indeed, if we consider a cycle $`f_1\mathrm{}f_t`$ in $`_L`$ starting in $`A_{q_0}`$ then, in view of Algorithm 30, if the unique fixed point of the corresponding function $`F=f_t\mathrm{}f_1`$ is $`x`$ then $`f_I^1(x)`$, with $`f_I:x\frac{\theta x1}{\theta 1}`$ and $`f_I^1(y)=\frac{(\theta 1)y+1}{\theta }`$, has an ultimately periodic representation (we are back in the initial state $`q_0`$ and since $`x=F(x)`$, we have the same initial value; due to the initialization step in Algorithm 30, we have to apply $`f_I^1`$ once). As an example, the fixed points of $`f_bid_a`$, $`f_bid_cf_aid_a`$ and $`f_bf_cid_cf_aid_a`$ are respectively $`1/3`$, $`1/15`$ and $`5/31`$ and therefore $`2/3`$, $`8/15`$ and $`18/31`$ have ultimately periodic representations. From the path in $`_L`$, we also know these representations: $`(ab)^\omega `$, $`(aacb)^\omega `$ and $`(aaccb)^\omega `$.

We can also consider a cycle $`f_1\mathrm{}f_t`$ in $`_L`$ starting in $`A_{q_1}`$ instead of $`A_{q_0}`$ and a path $`g_1\mathrm{}g_s`$ from $`A_{q_0}`$ to $`A_{q_1}`$. Once again, let $`x`$ be the fixed point of $`F=f_t\mathrm{}f_1`$. From Algorithm 30, the number $`f_I^1g_1^1\mathrm{}g_s^1(x)`$ has an ultimately periodic representation. As an example, consider $`F=f_cid_cf_af_c`$ having $`3/5`$ has fixed point. A trivial path from $`A_{q_0}`$ to $`A_{q_1}`$ is given by $`id_a`$, so $`f_I^1(3/5)=4/5`$ has an ultimately periodic representation: $`a(cacc)^\omega `$. Another path in $`_L`$ from $`A_{q_0}`$ to $`A_{q_1}`$ is $`(id_a,f_a,id_c)`$, so $`f_I^1f_a^1(3/5)=23/40`$ is represented by $`aac(cacc)^\omega `$.

Let us introduce some notation. Let

$$\varphi _q=\{w\delta _{}(A_q,w)=A_q\},$$

where $`\delta _{}`$ is the transition function of $`_L`$. If $`w=f_1\mathrm{}f_t`$ belongs to $`\varphi _q`$, we denote by $`F_{q,w}`$ the composed function (in reversed order) $`f_t\mathrm{}f_1`$ corresponding to $`w`$. Let

$$\nu _q=\{w\delta _{}(A_{q_0},w)=A_q\},$$

If $`w=f_1\mathrm{}f_s`$ belongs to $`\nu _q`$, we denote by $`(F_{q,w})^1`$ the composition of the inverse functions $`f_1^1\mathrm{}f_s^1`$ corresponding to $`w`$.

###### Theorem 34.

Let $`L`$ be a regular language satisfying our basic assumptions. Set

$$f_I^1:y\frac{(\theta 1)y+1}{\theta }.$$

The set of real numbers having an ultimately periodic representation is given by

$$\{f_I^1(F_{q,w})^1(x)qQ,z\varphi _q,w\nu _q:x=F_{q,z}(x)\}.$$

###### Proof.

This is a direct consequence of Algorithm 30. ∎

###### Remark 35.

For all states $`q`$, the languages $`\varphi _q`$ and $`\nu _q`$ over a finite alphabet of functions are regular.

## 9. Equivalence with $`\theta `$-development

Let $`\theta >1`$ be a Pisot number. To this number corresponds a unique positional and linear Bertrand number system $`U_\theta =(U_n)_n`$ having its characteristic polynomial equal to the minimal polynomial of $`\theta `$ . We denote by $`L`$ the language $`\rho _U()`$ of all the normalized representations computed by the greedy algorithm (without leading zeroes) . In this section we show that this latter language $`L`$ satisfies the hypotheses given in Section 3. We also prove that the representations of real numbers in the abstract numeration system built upon $`L`$ and the classical $`\theta `$-developments of the numbers in $`[\frac{1}{\theta },1]`$ coincide. (For a presentation of the $`\theta `$-development, we refer the reader to \[13, Chapter 7\] or .)

###### Definition 36.

Recall that a positional numeration system $`U=(U_n)_n`$ is said to be a Bertrand numeration system if

$$n,w\mathrm{\hspace{0.17em}0}^n\rho _U()w\rho _U().$$

As an example, the $`k`$-ary number system is a Bertrand system.

###### Example 37.

The golden ration $`\tau =\frac{1+\sqrt{5}}{2}`$ is a Pisot number, indeed its minimal polynomial is $`P(X)=X^2X1`$ and the other root of $`P`$ has modulus less than one. The polynomial $`P`$ is also the characteristic polynomial of the linear recurrence relation defined by

$$U_{n+2}=U_{n+1}+U_n,n.$$

If we consider the initial conditions $`U_0=1`$ and $`U_1=2`$, then as a consequence of the greedy algorithm, the set of representations of the integers is $`\rho _U()=\{\epsilon \}1\{0,01\}^{}`$. Due to the particular form of the language $`\rho _U()`$, it is clear that this system (namely the Fibonacci system) is the linear Bertrand number system associated to $`\tau `$.

Consider an arbitrary Pisot number $`\theta `$. It is well known that the $`\theta `$-development of one is finite or ultimately periodic . In the first case, $`e_\theta (1)=t_1\mathrm{}t_m`$ and we define, as usual,

$$e_\theta ^{}(1)=(t_1\mathrm{}t_{m1}(t_m1))^\omega .$$

It is clear that we still have

$$1=\frac{t_1}{\theta }+\frac{t_2}{\theta ^2}+\mathrm{}+\frac{t_m1}{\theta ^m}+\frac{t_1}{\theta ^{m+1}}+\mathrm{}.$$

Let $`\beta >1`$ be a real number. The set $`D_\beta `$ of $`\beta `$-developments of numbers in $`[0,1)`$ is characterized as follows.

###### Theorem 38.

 Let $`\beta >1`$ be a real number. A sequence $`(x_n)_{n1}`$ belongs to $`D_\beta `$ if and only if for all $`i`$, the shifted sequence $`(x_{n+i})_{n1}`$ is lexicographically less than the sequence $`e_\beta (1)`$ or $`e_\beta ^{}(1)`$ whenever $`e_\beta (1)`$ is finite.

For any real number $`\beta >1`$, we denote by $`F(D_\beta )`$, the set of finite factors of the sequences in $`D_\beta `$. Bertrand numeration systems are characterized by the theorem of Bertrand given below. Notice that $`U`$ is not necessarily linear.

###### Theorem 39.

 Let $`U=(U_n)_n`$ be a positional numeration system. Then $`U`$ is a Bertrand numeration system if and only if there exists a real number $`\beta >1`$ such that $`0^{}\rho _U()=F(D_\beta )`$. In this case, if $`e_\beta (1)=(d_n)_{n1}`$ (or $`e_\beta ^{}(1)=(d_n)_{n1}`$ whenever $`e_\beta (1)`$ is finite) then $`U_0=1`$ and

$$U_n=d_1U_{n1}+d_2U_{n2}+\mathrm{}+d_nU_0+1,n1.$$

Let $`\theta >1`$ be a Pisot number. First we assume that $`e_\theta (1)`$ is ultimately periodic; there exist minimal integers $`N0`$, $`p1`$ such that

$$e_\theta (1)=t_1\mathrm{}t_N(t_{N+1}\mathrm{}t_{N+p})^\omega .$$

The Bertrand numeration system $`U_\theta =(U_n)_n`$ belonging to the class of positional systems related to $`\theta `$ is a linear numeration system satisfying the recurrence relation

$`U_n`$ $`=`$ $`t_1U_{n1}+\mathrm{}+t_{p1}U_{np+1}+(t_p+1)U_{np}`$
$`+(t_{p+1}t_1)U_{np1}+\mathrm{}+(t_{N+p}t_N)U_{nNp},nN+p.`$
(In other words, $`(U_n)_n`$ satisfies the canonical beta polynomial of $`\theta `$ .) In what follows, $`\theta `$ is given and we denote $`U_\theta `$ simply by $`U`$.

The main point is the following. Since $`\theta `$ is a Pisot number, the set $`F(D_\theta )=0^{}\rho _U()`$ is recognizable by a finite automaton $`𝒜`$  (i.e., the $`\theta `$-shift is sofic). This automaton has $`N+p`$ states $`q_1,\mathrm{},q_{N+p}`$. For each $`i\{1,\mathrm{},N+p\}`$, there are edges labeled by $`0,1,\mathrm{},t_i1`$ from $`q_i`$ to $`q_1`$, and an edge labeled $`t_i`$ from $`q_i`$ to $`q_{i+1}`$ if $`i<N+p`$. Finally, there is an edge labeled $`t_{N+p}`$ from $`q_{N+p}`$ to $`q_{N+1}`$. All states are final and $`q_1`$ is the initial state. The set $`F(D_\theta )`$ is recognized by the automaton depicted in Figure 8 (the sink is not represented).

In an abstract numeration system, allowing leading zeroes changes the representations (indeed, $`0w`$ is genealogically greater than $`w`$ then $`\mathrm{val}_S(0w)>\mathrm{val}_S(w)`$, see for instance \[10, Example 1\]). Therefore, we modify slightly the automaton $`𝒜`$ to obtain an automaton $`𝒜^{}`$ recognizing exactly $`\rho _U()`$ (i.e., without leading zeroes). To that end, we add a new state $`q_0`$. There are edges labeled by $`1,\mathrm{},t_11`$ from $`q_0`$ to $`q_1`$ and an edge labeled $`t_1`$ from $`q_0`$ to $`q_2`$. This state $`q_0`$ is the initial state of $`𝒜^{}`$ and is also final. The automaton $`𝒜^{}`$ is sketched in Figure 9.

So we consider the abstract system built upon $`L=\rho _U()`$. To be able to compute the intervals $`I_w`$ related to this system with formula (4), our task is now to determine the different sequences $`𝐮_{q_i}(n)`$. To that end, we use the specific form of $`𝒜^{}`$. The first word of length $`n+1`$ in $`\rho _U()`$ is $`1(0)^n`$ and its numerical value is $`U_n`$. In the same way, $`1(0)^{n1}`$ is the first word of length $`n`$. Therefore,

(9)
$$𝐮_{q_0}(n)=U_nU_{n1}.$$

Since $`q_0`$ is the initial state of $`𝒜^{}`$, as usual we write $`𝐮(n)`$ and $`𝐯(n)`$ instead of $`𝐮_{q_0}(n)`$ and $`𝐯_{q_0}(n)`$.

Since $`\theta `$ is a Pisot number and the characteristic polynomial of $`U`$ is the minimal polynomial of $`\theta `$, there exists a real number $`\gamma `$ such that

$$U_n\gamma \theta ^n.$$

For $`n1`$, from the form of $`𝒜^{}`$ we deduce that

$$𝐮(n)=(t_11)𝐮_{q_1}(n1)+𝐮_{q_2}(n1)$$

and

(10)
$$𝐮_{q_1}(n)=t_1𝐮_{q_1}(n1)+𝐮_{q_2}(n1)=𝐮(n)+𝐮_{q_1}(n1).$$

As a consequence of (10), since all the states are final $`𝐮_{q_1}(0)=𝐮(0)=1`$, we find

$$𝐮_{q_1}(n)=\underset{i=1}{\overset{n}{}}𝐮(i)+𝐮_{q_1}(0)=𝐯(n).$$

From (10) we also have $`𝐮_{q_2}(n1)=𝐮_{q_1}(n)t_1𝐮_{q_1}(n1)`$ and thus $`𝐮_{q_2}(n)=𝐯(n+1)t_1𝐯(n)`$. But considering the path in $`𝒜^{}`$, we get $`𝐮_{q_2}(n)=t_2𝐮_{q_1}(n1)+𝐮_{q_3}(n1)`$. So we find $`𝐮_{q_3}(n)=𝐯(n+2)t_1𝐯(n+1)t_2𝐯(n)`$. Continuing this way, for $`iN+p`$

$$𝐮_{q_i}(n)=𝐯(n+i1)t_1𝐯(n+i2)t_2𝐯(n+i3)\mathrm{}t_{i1}𝐯(n).$$

We are now able to determine the endpoints of the intervals $`I_w`$. It is clear from (9) that $`𝐯(n)=U_n\gamma \theta ^n`$. Since $`𝐯(n1)=𝐯(n)𝐮(n)`$ using (5), it is clear that $`𝐯(n1)/𝐯(n)1/\theta `$ if $`n\mathrm{}`$ and therefore, for $`i`$

$$\underset{n\mathrm{}}{lim}\frac{𝐮_{q_1}(ni)}{𝐯(n)}=\underset{n\mathrm{}}{lim}\frac{𝐯(ni)}{𝐯(ni+1)}\frac{𝐯(ni+1)}{𝐯(ni+2)}\mathrm{}\frac{𝐯(n1)}{𝐯(n)}=\theta ^i.$$

In the same manner,

$$\underset{n\mathrm{}}{lim}\frac{𝐮_{q_2}(ni)}{𝐯(n)}=\theta ^{1i}t_1\theta ^i.$$

Continuing this way, for $`jN+p`$ and $`i`$

$$\underset{n\mathrm{}}{lim}\frac{𝐮_{q_j}(ni)}{𝐯(n)}=\theta ^{ji1}t_1\theta ^{ji2}\mathrm{}t_{j1}\theta ^i.$$

We can now compute the different intervals $`I_w`$. The first words in $`\rho _U()`$ are

$$1,\mathrm{},(t_11),t_1,10,\mathrm{},1t_1,20,\mathrm{},(t_11)t_1,t_10,\mathrm{},t_1t_2,100\mathrm{}$$

Using (4) we have the intervals corresponding to words of length one

$$I_j=[\frac{j}{\theta },\frac{j}{\theta }+\underset{n\mathrm{}}{lim}\frac{𝐮_{q_1}(n1)}{𝐯(n)}]=[\frac{j}{\theta },\frac{j+1}{\theta }],1j<t_1$$

and

$$I_{t_1}=[\frac{t_1}{\theta },\frac{t_1}{\theta }+\underset{n\mathrm{}}{lim}\frac{𝐮_{q_2}(n1)}{𝐯(n)}]=[\frac{t_1}{\theta },1].$$

For the words of length two, if $`1j<t_1`$ and $`0k<t_1`$ then

$$I_{jk}=[\frac{j}{\theta }+\frac{k}{\theta ^2},\frac{j}{\theta }+\frac{k}{\theta ^2}+\underset{n\mathrm{}}{lim}\frac{𝐮_{q_1}(n2)}{𝐯(n)}]=[\frac{j}{\theta }+\frac{k}{\theta ^2},\frac{j}{\theta }+\frac{k+1}{\theta ^2}]$$

and

$$I_{jt_1}=[\frac{j}{\theta }+\frac{t_1}{\theta ^2},\frac{j}{\theta }+\frac{t_1}{\theta ^2}+\underset{n\mathrm{}}{lim}\frac{𝐮_{q_2}(n2)}{𝐯(n)}]=[\frac{j}{\theta }+\frac{t_1}{\theta ^2},\frac{j+1}{\theta }].$$

For the words of length two beginning with $`t_1`$, we have

$$I_{t_1j}=[\frac{t_1}{\theta }+\frac{j}{\theta ^2},\frac{t_1}{\theta }+\frac{j+1}{\theta ^2}],0j<t_2$$

and

$$I_{t_1t_2}=[\frac{t_1}{\theta }+\frac{t_2}{\theta ^2},\frac{t_1}{\theta }+\frac{t_2}{\theta ^2}+\underset{n\mathrm{}}{lim}\frac{𝐮_{q_3}(n2)}{𝐯(n)}]=[\frac{t_1}{\theta }+\frac{t_2}{\theta ^2},1].$$

Continuing this way, it is straightforward computation to see that we have three situations:

1. if $`w=w_0\mathrm{}w_r`$ with $`q_i=q_0.w_0\mathrm{}w_{r1}`$ and $`w_r<t_i`$ then

$$I_w=[\underset{i=0}{\overset{r}{}}w_i\theta ^{i1},\underset{i=0}{\overset{r}{}}w_i\theta ^{i1}+\theta ^{r1}]$$
2. if $`w=w_0\mathrm{}w_rw_{r+1}\mathrm{}w_{r+s}`$ is such that $`q_i=q_0.w_0\mathrm{}w_{r1}`$, $`w_r<t_i`$ and $`w_{r+1}\mathrm{}w_{r+s}`$ is the maximal word read from $`q_0.w_0\mathrm{}w_r`$ in $`𝒜^{}`$ (in other words, $`q_0.w_0\mathrm{}w_r=q_1`$ and $`w_{r+1}\mathrm{}w_{r+s}`$ is the prefix of length $`s`$ of $`e_\theta (1)`$) then

$$I_w=[\underset{i=0}{\overset{r+s}{}}w_i\theta ^{i1},\underset{i=0}{\overset{r}{}}w_i\theta ^{i1}+\theta ^{r1}].$$
3. finally, if $`w=w_0\mathrm{}w_r`$ is a prefix of $`e_\theta (1)`$ then

$$I_w=[\underset{i=0}{\overset{r}{}}w_i\theta ^{i1},1].$$

Now instead of considering the abstract numeration system built upon $`L=\rho _U()`$, we can consider the classical $`\theta `$-development of a real number $`x[1/\theta ,1]`$. The first digit of $`e_\theta (x)`$ is an integer $`j`$ belonging to $`\{1,2,\mathrm{},t_1\}`$. Since $`\theta `$-developments are computed through the greedy algorithm, it is clear that the first digit is $`j<t_1`$ if and only if $`xI_j^{}=[j/\theta ,(j+1)/\theta )`$ and it is $`t_1`$ if and only if $`xI_{t_1}^{}=[t_1/\theta ,1]`$. So the interval $`I_j`$ for the abstract numeration systems considered above and the intervals $`I_j^{}`$ corresponding to the greedy algorithm are the same for the first step (except that in the abstract system, a real number can have two representations but we can avoid this ambiguity by considering intervals of the form $`[a,b)`$ and therefore the two intervals $`I_j`$ and $`I_j^{}`$ will coincide exactly). By application of the greedy algorithm, we can compute intervals $`I_w^{}`$ such that $`x`$ belongs to $`I_w^{}`$ if $`e_\theta (x)`$ has $`w`$ as prefix. Clearly those intervals $`I_w^{}`$ coincide with the intervals $`I_w`$ and therefore, the classical $`\theta `$-developments are the same as the representation obtained in the framework of the abstract numeration systems (naturally, under the extra assumptions of this section corresponding to regular languages associated to Pisot number).

Now we can use a result of Klaus Schmidt concerning ultimately periodic $`\theta `$-developments  and state the following result.

###### Theorem 40.

If $`L`$ is the language of all the representations of the integers in a linear Bertrand numeration system associated to a Pisot number $`\theta `$ then the set of real numbers having an ultimately periodic representation in the abstract system built upon $`L`$ is exactly

$$(\theta )[1/\theta ,1].$$

###### Remark 41.

In this section, we have only considered the case $`e_\theta (1)`$ ultimately periodic. If $`e_\theta (1)=t_1\mathrm{}t_m`$ is finite ($`t_m0`$) then the same situation holds. The construction of the automaton $`𝒜`$ is the same as before but with $`N=m`$ and $`p=0`$. All the edges from $`q_m`$ lead to $`q_1`$ and are labeled by $`0,\mathrm{},t_m1`$. The automaton $`𝒜`$ is depicted in Figure 10.