Numeration And Discrete Dynamical Systems

This survey aims at giving both a dynamical and computer arithmetic-orientedpresentation of several classical numeration systems, by focusing on the discretedynamical systems underlying them. This provides simple algorithmic generationprocesses, information on the statistics of digits, on the mean behavior, on periodicexpansions and so on.More precisely, Chaper1is devoted to illustrate the background of dynamical systemand the applications of discrete dynamical system in the numeration. In Chaper2, we willillustrate the use of dynamical methods for describing periodic orbits and thus producingGalois’ type theorems. We then will use as a guideline the Gauss map and contiunedfractions in Chaper3in oder to introduce and discuss the notions of ergodic, chaoticity,and of numerical simuations of dynamical systems through a floating-point version of theGauss map. Chaper4is devoted to the classic Lochs’ theorem which can be summarizedunder the following form: contiuned fraction expansions are not significantly moreefficient at representing real numbers than the decimal expansion. We conclude this surveyby alluding to the multidimensional case in Chaper5.In this paper, we consider numeration systems in a broad sense, that is, representationsystems of numbers that also include continued fraction expansions. These numerationsystems might be positional or not, provide unique expansions or be redundant. Specialattention will be payed to β-numeration (one expands a positive real number with respectto the baseβ>1), to continued fractions, and to their Lyapounov exponents.In particular,we will compare both representation systems with respect to the number of significantdigits required to go from one type of expansion to the other one, through the discussionof extensions of Lochs’theorem.