×

Numeration and discrete dynamical systems. (English) Zbl 1269.11009

From the abstract: “This survey aims at giving both a dynamical and computer arithmetic-oriented presentation of several classical numeration systems, by focusing on the discrete dynamical systems that underly them: this provides simple algorithmic generation processes, information on the statistics of digits, on the mean behavior, and also on periodic expansions (whose study is motivated, among other things, by finite machine simulations).”
Emphasis is put on continued fractions and on beta-numeration systems (extending the usual integer base systems). The usefulness of the dynamical approach is illustrated first for the description of the periodic orbits. Then, notions of ergodicity, chaoticity are presented for the Gauss map \(x\mapsto \{1/x\}\) related to continued fractions. Numerical simulations of dynamical systems are discussed by considering a floating-point version of the Gauss map. In the next section, Loch’s theorem about the significance of classical decimal expansions (knowing the first decimals) versus continued fraction expansions (knowing the first partial quotients) is presented. Finally, allusion to a multidimensional framework (possible extensions of the Gauss map) is concluding this survey.

MSC:

11A63 Radix representation; digital problems
11J70 Continued fractions and generalizations
37B10 Symbolic dynamics
11K16 Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc.

Software:

SLEEF
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akiyama S, Barat G, Berthé V, Siegel A (2008) Boundary of central tiles associated with Pisot beta-numeration and purely periodic expansions. Monatsh Math 155: 377–419 · Zbl 1190.11005 · doi:10.1007/s00605-008-0009-7
[2] Arnold VI (1998) Higher-dimensional continued fractions. Regul Chaotic Dyn 3: 10–17 · Zbl 1044.11596 · doi:10.1070/rd1998v003n03ABEH000076
[3] Avizienis A (1961) Signed-digit number representations for fast parallel arithmetic. IEEE Trans EC-10: 389–400
[4] Bajard J-C, Muller J-M (eds) (2004) Calcul et arithmétique des ordinateurs, Traité IC2, série Informatique et Systèmes d’Information, Hermes Sciences
[5] Baladi V, Vallée B (2005) Euclidean algorithms are Gaussian. J Number Theory 110: 331–386 · Zbl 1114.11092 · doi:10.1016/j.jnt.2004.08.008
[6] Barat G, Liardet P (2004) Dynamical systems originated in the Ostrowski alpha-expansion. Ann Univ Sci Budapest Sect Comput 24: 133–184 · Zbl 1109.37010
[7] Barat G, Berthé V, Liardet P, Thuswaldner JM (2006) Dynamical directions in numeration. Ann Inst Fourier (Grenoble) 56: 1987–2092 · Zbl 1138.37005 · doi:10.5802/aif.2233
[8] Barreira L, Godofredo I (2008) Partial quotients of continued fractions and {\(\beta\)}-expansions. Nonlinearity 21: 2211–2219 · Zbl 1154.37327 · doi:10.1088/0951-7715/21/10/001
[9] Berthé V (2001) Autour du système de numération d’Ostrowski. Bull Belg Math Soc Simon Stevin 8: 209–239
[10] Berthé V (2011) Multidimensional Euclidean algorithms, numeration and substitutions. Integers (to appear)
[11] Berthé V, Imbert L (2009) Diophantine approximation, Ostrowski numeration and the double-base number system. Discret Math Theor Comput Sci 11: 153–172 · Zbl 1221.11017
[12] Berthé V, Nakada H (2000) On continued fraction expansions in positive characteristic: equivalence relations and some metric properties. Expo Math 18: 257–284 · Zbl 1024.11050
[13] Berthé V, Rigo M (2005) Abstract numeration systems and tilings. In: Proceedings of the 30th international symposium: mathematical foundations of computer science (Gdańsk 2005). Lecture Notes in Computer Science 3618, pp 131–143 · Zbl 1156.68443
[14] Bertrand A (1977) Développements en base de Pisot et répartition modulo 1. C R Acad Sci Paris Sér A-B 285(6): A419–A421 · Zbl 0362.10040
[15] Billingsley P (1965) Ergodic theory and information. Wiley, New York · Zbl 0141.16702
[16] Blanchard F (2009) Topological chaos: what may this mean?. J Differ Equ Appl 15: 23–46 · Zbl 1253.37013 · doi:10.1080/10236190802385355
[17] Boese G (1982) An a priori estimate for the truncation error of a continued fraction expansion to the Gaussian error function. Computing 29: 135–152 · Zbl 0482.33001 · doi:10.1007/BF02249937
[18] Bosma W (2001) Signed bits and fast exponentiation. J Théor Nombres Bordeaux 13: 27–41 · Zbl 1060.11082 · doi:10.5802/jtnb.301
[19] Bosma W, Dajani K, Kraaikamp C (2006) Entropy quotients and correct digits in number-theoretic expansions, dynamics and stochastics. IMS Lect Notes Monogr Ser 48: 176–188 · Zbl 1128.11039 · doi:10.1214/074921706000000202
[20] Brentjes AJ (1981) Multi-dimensional continued fraction algorithms. Mathematical Centre Tracts. Matematisch Centrum, Amsterdam · Zbl 0471.10024
[21] Broise A (1996) Fractions continues multidimensionnelles et lois stables. Bull Soc Math France 124: 97–139 · Zbl 0857.11035
[22] Broise-Alamichel A, Guivarc’h Y (2001) Exposants caractéristiques de l’algorithme de Jacobi-Perron et de la transformation associée. Ann Inst Fourier (Grenoble) 51: 565–686 · Zbl 1012.11060 · doi:10.5802/aif.1832
[23] Cesaratto E, Clément J, Daireaux B, Lhote L, Maume-Deschamps V, Vallée B (2009) Regularity of the Euclid algorithm; application to the anaysis of fast GCD algorithms. J Symb Comput 44: 726–767 · Zbl 1179.11049 · doi:10.1016/j.jsc.2008.04.018
[24] Choe GH (2005) Computational ergodic theory. Algorithms and Computation in Mathematics. Springer, Berlin · Zbl 1064.37004
[25] Corless RM (1992) Continued fractions and chaos. Am Math Mon 99: 203–215 · Zbl 0758.58020 · doi:10.2307/2325053
[26] Corless RM (1994) What good are numerical simulations of chaotic dynamical systems?. Comput Math Appl 28: 107–121 · Zbl 0813.65101 · doi:10.1016/0898-1221(94)00188-X
[27] Corless RM, Frank GW, Monroe JG (1990) Chaos and continued fractions. Phys D 46: 241–253 · Zbl 0723.58037 · doi:10.1016/0167-2789(90)90038-Q
[28] Cuyt A, Verdonk B, Waadeland H (2006) Efficient and reliable multiprecision implementation of elementary and special functions. SIAM J Sci Comput 28: 1437–1462 · Zbl 1132.33342 · doi:10.1137/050629203
[29] Dajani K, Fieldsteel A (2001) Equipartition of interval partitions and an application to number theory. Proc Am Math Soc 129: 3453–3460 · Zbl 0999.11041 · doi:10.1090/S0002-9939-01-06299-2
[30] Dajani K, Kraaikamp C (2002) Ergodic theory of numbers. The Mathematical Association of America, Washington, DC · Zbl 1033.11040
[31] Devaney RL (1989) An introduction to chaotic dynamical systems. Addison–Wesley studies in nonlinearity, Redwood City
[32] Faivre C (1997) On decimal and continued fraction expansions of a real number. Acta Arith 82: 119–128 · Zbl 0881.11063
[33] Faivre C (1998) A central limit theorem related to decimal and continued fraction expansion. Arch Math (Basel) 70: 455–463 · Zbl 0921.11041 · doi:10.1007/s000130050219
[34] Faivre C (2001) On calculating a continued fraction expansion from a decimal expansion. Acta Sci Math (Szeged) 67: 505–519 · Zbl 1017.11040
[35] Flajolet P, Odlyzko AM (1990) Random mapping statistics, EUROCRYPT’ 89. Lect Notes Comput Sci 434: 329–354 · Zbl 0747.05006 · doi:10.1007/3-540-46885-4_34
[36] Flajolet P, Vallée B (2000) Continued fractions, comparison algorithms, and fine structure constants. In: CMS Conference Proceedings, vol 27. American Mathematical Society, Providence, pp 53–82 · Zbl 1006.11087
[37] Flajolet P, Vallée B (1998) Continued fraction algorithms, functional operators, and structure constants. Theoret Comput Sci 194: 1–34 · Zbl 0981.11044 · doi:10.1016/S0304-3975(97)00123-0
[38] Frougny Ch (2002) Numeration systems. Encyclopedia of Mathematics and its Applications, vol 90, chap 7. Cambridge University Press, Cambridge, pp 230–268
[39] Frougny Ch (2003) On-line digit set conversion in real base. Theoret Comput Sci 292: 221–235 · Zbl 1063.68066 · doi:10.1016/S0304-3975(01)00224-9
[40] Frougny Ch (2000) On-the-fly algorithms and sequential machines. IEEE Trans Comput 49: 859–863 · doi:10.1109/12.868030
[41] Frougny Ch (1999) On-line finite automata for addition in some numeration systems. Theor Inf Appl 33: 79–101 · Zbl 0927.68052 · doi:10.1051/ita:1999107
[42] Frougny Ch (1997) On the sequentiality of the successor function. Inf Comput 139: 17–38 · Zbl 0892.68065 · doi:10.1006/inco.1997.2650
[43] Frougny Ch, Sakarovitch J (2010) Number representation and finite automata. Encyclopedia of Mathematics and its Applications, vol 135, chap 2. Cambridge University Press, Cambridge, pp 34–107 · Zbl 1216.68142
[44] Galatolo S, Hoyrup M, Rojas C (2010) Effective symbolic dynamics, random points, statistical behavior, complexity and entropy. Inf Comput 208: 23–41 · Zbl 1185.68368 · doi:10.1016/j.ic.2009.05.001
[45] Góra P, Boyarsky A (1988) Why computers like Lebesgue measure. Comput Math Appl 16: 321–329 · Zbl 0668.28008 · doi:10.1016/0898-1221(88)90148-4
[46] Góra P, Paweł , Boyarsky A, Shafiqul IMd, Bahsoun W (2006) Absolutely continuous invariant measures that cannot be observed experimentally. SIAM J Appl Dyn Syst 5:84–90 · Zbl 1090.37041
[47] Gosper W (1972) Continued fraction arithmetic, HAKMEM Item 101B. MIT Artificial Intelligence Memo 239. MIT
[48] Grabner PJ, Heuberger C (2006) On the number of optimal base 2 representations of integers. Des Codes Cryptogr 40: 25–39 · Zbl 1261.11003 · doi:10.1007/s10623-005-6158-y
[49] Grabner PJ, Liardet P, Tichy RF (1995) Odometers and systems of numeration. Acta Arith LXX.2: 103–123 · Zbl 0822.11008
[50] Grabner PJ, Heuberger C, Prodinger H, Thuswaldner JM (2005) Analysis of linear combination algorithms in cryptography. ACM Trans Algorithms 1: 123–142 · Zbl 1321.68514 · doi:10.1145/1077464.1077473
[51] Hardy GH, Wright EM (1979) An introduction to the theory of numbers. Oxford Science Publications, Oxford
[52] Heuberger C, Prodinger H. (2001) On minimal expansions in redundant number systems: Algorithms and quantitative analysis. Computing 66: 377–393 · Zbl 1030.11003 · doi:10.1007/s006070170021
[53] Ito S (1986) Some skew product transformations associated with continued fractions and their invariant measures. Tokyo J Math 9: 115–133 · Zbl 0606.10042 · doi:10.3836/tjm/1270150981
[54] Ito S, Nakada H (1988) Approximations of real numbers by the sequence {n{\(\alpha\)}} and their metrical theory. Acta Math Hung 52: 91–100 · Zbl 0657.10034 · doi:10.1007/BF01952484
[55] Jones WB, Thron WJ (1980) Continued fractions. Encyclopedia of Mathematics and its Applications, vol 11. Addison–Wesley Publishing Co, Reading
[56] Kátai I, Szabó J (1975) Canonical Number Systems for Complex Integers. Acta Sci Math (Szeged) 37: 255–260 · Zbl 0297.12003
[57] Khintchine AY (1963) Continued fractions (translated by P. Wynn). P. Noordhoff Ltd, Groningen
[58] Kitchens BP (1998) Symbolic dynamics, One-sided, two-sided and countable state Markov shifts (Universitext). Springer, Berlin · Zbl 0892.58020
[59] Knuth DE (1998) The art of computer programming. Seminumerical algorithms. Addison–Wesley, Reading · Zbl 0895.65001
[60] Kornerup P, Matula D (1995) LCF: a lexicographic binary representation of the rationals. J Univ Comput Sci 1: 484–503 · Zbl 0961.68004
[61] Lagarias JC (1982) Best simultaneous diophantine approximations. I. Growth rates of best approximation denominators. Trans Am Math Soc 272: 545–554 · Zbl 0495.10021
[62] Lagarias JC (1982) Best simultaneous diophantine approximations. II. Behavior of consecutive best approximations. Pac J Math 102: 61–88 · Zbl 0497.10025 · doi:10.2140/pjm.1982.102.61
[63] Lagarias JC (1985) The computational complexity of simultaneous Diophantine approximation problems. SIAM J Comput 14: 196–209 · Zbl 0563.10025 · doi:10.1137/0214016
[64] Lefèvre V (2005) New results on the distance between a segment and $${\(\backslash\)mathbb{Z}\^{2}}$$ . Application to exact rounding. In: Proceedings of the 17th IEEE symposium on computer arithmetic, pp 68–75
[65] Lefèvre V, Muller J-M, Tisserand A (1998) Towards correctly rounded transcendentals. IEEE Trans Comput 47: 1235–1243 · doi:10.1109/12.736435
[66] Lester DR (2001) Effective continued fractions. In: Burgess N, Ciminiera L (eds) 15th IEEE Symposium on Computer Arithmetic: ARITH-15, pp 163–172
[67] Li B, Wu J (2008) Beta-expansion and continued fraction expansion over formal Laurent series. Finite Fields Appl 14: 635–647 · Zbl 1165.11066 · doi:10.1016/j.ffa.2007.09.005
[68] Li B, Wu J (2008) Beta-expansion and continued fraction expansion. J Math Anal Appl 339: 1322–1331 · Zbl 1137.11053 · doi:10.1016/j.jmaa.2007.07.070
[69] Lind D, Marcus B (1995) An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge · Zbl 1106.37301
[70] Lochs G (1964) Vergleich der Genauigkeit von Dezimalbruch und Kettenbruch. Abh Math Sem Univ Hamburg 27: 142–144 · Zbl 0124.28003 · doi:10.1007/BF02993063
[71] Lochs G (1963) Die ersten 968 Kettenbruchnenner von {\(\pi\)}. Monatsh Math 67: 311–316 · Zbl 0145.05002 · doi:10.1007/BF01299581
[72] Lhote L, Vallée B (2008) Gaussian laws for the main parameters of the Euclid algorithms. Algorithmica 50: 497–554 · Zbl 1142.11085 · doi:10.1007/s00453-007-9009-6
[73] Ménissier-Morain V (1994) Arithmétique exacte, conception, algorithmique et performances d’une implémentation informatique en précision arbitraire, Thèse, Université Paris 7
[74] Muller J-M (1989) Arithmétique des Ordinateurs. Masson, Paris
[75] Muller J-M (1997) Elementary functions, algorithms and implementation. Birkhäuser Boston Inc., Boston · Zbl 0892.65005
[76] Muller J-M (1994) Some characterizations of functions computable in on-line arithmetic. IEEE Trans Comput 43: 752–755 · Zbl 1042.68503 · doi:10.1109/12.286308
[77] Muller J-M, Brisebarre N, de Dinechin F, Jeannerod C-P, Lefèvre V, Melquiond G, Revol N, Stehlé D, Torres S (2010) Handbook of floating-point arithmetic. Birkhäuser Boston Inc, Boston · Zbl 1197.65001
[78] Niederreiter H (1987) Continued fractions for formal power series, pseudorandom numbers, and linear complexity. Contributions to general algebra, 5 (Salzburg, 1986). Hölder-Pichler-Tempsky, Vienna, pp 221–233
[79] Niederreiter H (1995) Low-discrepancy sequences and non-Archimedean Diophantine approximations. Stud Sci Math Hung 30: 111–122 · Zbl 0852.11033
[80] Niederreiter H (1988) Sequences with almost perfect linear complexity profile. In: Chaum D, Price WL (eds) Advances in cryptology: Proc. EUROCRYPT’87”. Springer, Berlin, pp 37–51 · Zbl 0651.94003
[81] Niqui M (2007) Exact arithmetic on the Stern-Brocot tree. J Discret algorithms 5: 356–379 · Zbl 1127.68029 · doi:10.1016/j.jda.2005.03.007
[82] Nguyen, PQ, Vallée, B (eds) (2010) The LLL algorithm, survey and applications. Information Security and Cryptography. Springer, Dordrecht
[83] Parry W, Pollicott M (1990) Zeta functions and the periodic orbit structure of hyperbolic dynamics, Astérisque, pp 187–188 · Zbl 0726.58003
[84] Pilyugin SY (1999) Shadowing in dynamical systems. Lecture Notes in Mathematics 1706. Springer, Berlin
[85] Pollicott M (1986) Distribution of closed geodesics on the modular surface and quadratic irrationals. Bull Soc Math France 114: 431–446 · Zbl 0624.58019
[86] Raney GN (1973) On continued fractions and finite automata. Math Ann 206: 265–283 · Zbl 0258.10015 · doi:10.1007/BF01355980
[87] Rényi A (1957) Representations for real numbers and their ergodic properties. Acta Math Acad Sci Hung 8: 477–493 · Zbl 0079.08901 · doi:10.1007/BF02020331
[88] Schmidt K (1980) On periodic expansions of Pisot numbers and Salem numbers. Bull Lond Math Soc 12: 269–278 · Zbl 0494.10040 · doi:10.1112/blms/12.4.269
[89] Schweiger F (2000) Multi-dimensional continued fractions. Oxford Science Publications, Oxford Univ. Press, Oxford · Zbl 0981.11029
[90] Sidorov N et al (2003) Arithmetic dynamics. In: Bezuglyi S (eds) Topics in dynamics and ergodic theory. London Mathematical Society Lecture Note Series, vol 310. Cambridge University Press, Cambridge, pp 145–189 · Zbl 1051.37007
[91] Skokos Ch (2010) The Lyapunov Characteristic Exponents and their Computation. Lect Notes Phys 790: 63–135 · doi:10.1007/978-3-642-04458-8_2
[92] Tamura J-I, Yasutomi S-I (2009) A new multidimensional continued fraction algorithm. Math Comput 78: 2209–2222 · Zbl 1217.11067 · doi:10.1090/S0025-5718-09-02217-0
[93] Vallée B (2006) Euclidean dynamics. Discret Contin Dyn Syst 15: 281–352 · Zbl 1110.68052 · doi:10.3934/dcds.2006.15.281
[94] Vuillemin J (1990) Exact real computer arithmetic with continued fractions. IEEE Trans Comput 39: 1087–1105 · doi:10.1109/12.57047
[95] V’yugin VV (1998) Ergodic theorems for individual random sequences. Theor Comput Sci 207: 343–361 · Zbl 0915.68092 · doi:10.1016/S0304-3975(98)00072-3
[96] Wall HS (1948) Analytic theory of continued fractions. D. Van Nostrand Company, Inc., New York · Zbl 0035.03601
[97] Walters P (1982) An introduction to ergodic theory. Springer, New York · Zbl 0475.28009
[98] Wu J (2006) Continued fraction and decimal expansions of an irrational number. Adv Math 206: 684–694 · Zbl 1156.11033 · doi:10.1016/j.aim.2005.10.007
[99] Wu J (2008) An iterated logarithm law related to decimal and continued fraction expansions. Monatsh Math 153: 83–87 · Zbl 1136.11050 · doi:10.1007/s00605-007-0486-0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.