A new complexity function, repetitions in Sturmian words, and irrationality exponents of Sturmian numbers

Bugeaud, Yann; Kim, Dong Han

doi:10.1090/tran/7378

A new complexity function, repetitions in Sturmian words, and irrationality exponents of Sturmian numbers
HTML articles powered by AMS MathViewer

by Yann Bugeaud and Dong Han Kim PDF

Trans. Amer. Math. Soc. 371 (2019), 3281-3308 Request permission

Abstract:

We introduce and study a new complexity function in combinatorics on words, which takes into account the smallest second occurrence time of a factor of an infinite word. We characterize the eventually periodic words and the Sturmian words by means of this function. Then, we establish a new result on repetitions in Sturmian words and show that it is best possible. Let $b \ge 2$ be an integer. We deduce a lower bound for the irrationality exponent of real numbers whose sequence of $b$-ary digits is a Sturmian sequence over $\{0, 1, \ldots , b-1\}$ and we prove that this lower bound is best possible. As an application, we derive some information on the $b$-ary expansion of $\log (1 + \frac {1}{a})$ for any integer $a \ge 34$.

References

Boris Adamczewski, On the expansion of some exponential periods in an integer base, Math. Ann. 346 (2010), no. 1, 107–116. MR 2558889, DOI 10.1007/s00208-009-0391-z
Boris Adamczewski and Yann Bugeaud, Dynamics for $\beta$-shifts and Diophantine approximation, Ergodic Theory Dynam. Systems 27 (2007), no. 6, 1695–1711. MR 2371591, DOI 10.1017/S0143385707000223
Boris Adamczewski and Yann Bugeaud, On the complexity of algebraic numbers. I. Expansions in integer bases, Ann. of Math. (2) 165 (2007), no. 2, 547–565. MR 2299740, DOI 10.4007/annals.2007.165.547
Boris Adamczewski and Yann Bugeaud, Nombres réels de complexité sous-linéaire: mesures d’irrationalité et de transcendance, J. Reine Angew. Math. 658 (2011), 65–98 (French, with English summary). MR 2831513, DOI 10.1515/CRELLE.2011.061
Boris Adamczewski, Yann Bugeaud, and Florian Luca, Sur la complexité des nombres algébriques, C. R. Math. Acad. Sci. Paris 339 (2004), no. 1, 11–14 (French, with English and French summaries). MR 2075225, DOI 10.1016/j.crma.2004.04.012
William W. Adams and J. L. Davison, A remarkable class of continued fractions, Proc. Amer. Math. Soc. 65 (1977), no. 2, 194–198. MR 441879, DOI 10.1090/S0002-9939-1977-0441879-4
K. Alladi and M. L. Robinson, Legendre polynomials and irrationality, J. Reine Angew. Math. 318 (1980), 137–155. MR 579389
Jean-Paul Allouche, Nouveaux résultats de transcendance de réels à développement non aléatoire, Gaz. Math. 84 (2000), 19–34 (French). MR 1766087
Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences, Cambridge University Press, Cambridge, 2003. Theory, applications, generalizations. MR 1997038, DOI 10.1017/CBO9780511546563
Masaaki Amou and Yann Bugeaud, Exponents of Diophantine approximation and expansions in integer bases, J. Lond. Math. Soc. (2) 81 (2010), no. 2, 297–316. MR 2602997, DOI 10.1112/jlms/jdp070
Pierre Arnoux, Sébastien Ferenczi, and Pascal Hubert, Trajectories of rotations, Acta Arith. 87 (1999), no. 3, 209–217. MR 1668554, DOI 10.4064/aa-87-3-209-217
A. Baker, Approximations to the logarithms of certain rational numbers, Acta Arith. 10 (1964), 315–323. MR 171749, DOI 10.4064/aa-10-3-315-323
Verónica Becher and Pablo Ariel Heiber, On extending de Bruijn sequences, Inform. Process. Lett. 111 (2011), no. 18, 930–932. MR 2849850, DOI 10.1016/j.ipl.2011.06.013
Valérie Berthé, Charles Holton, and Luca Q. Zamboni, Initial powers of Sturmian sequences, Acta Arith. 122 (2006), no. 4, 315–347. MR 2234421, DOI 10.4064/aa122-4-1
Yann Bugeaud, Approximation by algebraic numbers, Cambridge Tracts in Mathematics, vol. 160, Cambridge University Press, Cambridge, 2004. MR 2136100, DOI 10.1017/CBO9780511542886
Yann Bugeaud, Diophantine approximation and Cantor sets, Math. Ann. 341 (2008), no. 3, 677–684. MR 2399165, DOI 10.1007/s00208-008-0209-4
Yann Bugeaud, Distribution modulo one and Diophantine approximation, Cambridge Tracts in Mathematics, vol. 193, Cambridge University Press, Cambridge, 2012. MR 2953186, DOI 10.1017/CBO9781139017732
Yann Bugeaud, On the expansions of a real number to several integer bases, Rev. Mat. Iberoam. 28 (2012), no. 4, 931–946. MR 2990128, DOI 10.4171/RMI/697
Yann Bugeaud, Automatic continued fractions are transcendental or quadratic, Ann. Sci. Éc. Norm. Supér. (4) 46 (2013), no. 6, 1005–1022 (English, with English and French summaries). MR 3134686, DOI 10.24033/asens.2208
Yann Bugeaud, Expansions of algebraic numbers, Four faces of number theory, EMS Ser. Lect. Math., Eur. Math. Soc., Zürich, 2015, pp. 31–75. MR 3468302
Yann Bugeaud and Jan-Hendrik Evertse, On two notions of complexity of algebraic numbers, Acta Arith. 133 (2008), no. 3, 221–250. MR 2434602, DOI 10.4064/aa133-3-3
Yann Bugeaud and Dong Han Kim, On the $b$-ary expansions of $\log (1+\frac 1a)$ and $\textrm {e}$, Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) 17 (2017), no. 3, 931–947. MR 3726831
Yann Bugeaud, Dalia Krieger, and Jeffrey Shallit, Morphic and automatic words: maximal blocks and Diophantine approximation, Acta Arith. 149 (2011), no. 2, 181–199. MR 2805629, DOI 10.4064/aa149-2-7
Julien Cassaigne, On a conjecture of J. Shallit, Automata, languages and programming (Bologna, 1997) Lecture Notes in Comput. Sci., vol. 1256, Springer, Berlin, 1997, pp. 693–704. MR 1616227, DOI 10.1007/3-540-63165-8_{2}23
J. Cassaigne, Sequences with grouped factors, in DLT’97, Developments in Language Theory III, Thessaloniki, Aristotle University of Thessaloniki, 1998, pp. 211–222.
Larry J. Cummings and Doug Wiedemann, Embedded de Bruijn sequences, Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986), 1986, pp. 155–160. MR 885244
L. V. Danilov, Rational approximations of some functions at rational points, Mat. Zametki 24 (1978), no. 4, 449–458, 589 (Russian). MR 513647
Sébastien Ferenczi and Christian Mauduit, Transcendence of numbers with a low complexity expansion, J. Number Theory 67 (1997), no. 2, 146–161. MR 1486494, DOI 10.1006/jnth.1997.2175
N. J. Fine and H. S. Wilf, Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc. 16 (1965), 109–114. MR 174934, DOI 10.1090/S0002-9939-1965-0174934-9
N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, vol. 1794, Springer-Verlag, Berlin, 2002. Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. MR 1970385, DOI 10.1007/b13861
Antal Iványi, On the $d$-complexity of words, Ann. Univ. Sci. Budapest. Sect. Comput. 8 (1987), 69–90 (1988). MR 974183
Teturo Kamae and Dong Han Kim, A characterization of eventual periodicity, Theoret. Comput. Sci. 581 (2015), 1–8. MR 3332838, DOI 10.1016/j.tcs.2015.02.039
Dong Han Kim, Return time complexity of Sturmian sequences, Theoret. Comput. Sci. 412 (2011), no. 29, 3413–3417. MR 2839687, DOI 10.1016/j.tcs.2011.02.004
Takao Komatsu, A certain power series and the inhomogeneous continued fraction expansions, J. Number Theory 59 (1996), no. 2, 291–312. MR 1402610, DOI 10.1006/jnth.1996.0099
M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 90, Cambridge University Press, Cambridge, 2002.
Marston Morse and Gustav A. Hedlund, Symbolic dynamics II. Sturmian trajectories, Amer. J. Math. 62 (1940), 1–42. MR 745, DOI 10.2307/2371431
Carl Pomerance, John Michael Robson, and Jeffrey Shallit, Automaticity. II. Descriptional complexity in the unary case, Theoret. Comput. Sci. 180 (1997), no. 1-2, 181–201. MR 1453865, DOI 10.1016/S0304-3975(96)00189-2
D. Ridout, Rational approximations to algebraic numbers, Mathematika 4 (1957), 125–131. MR 93508, DOI 10.1112/S0025579300001182
K. F. Roth, Rational approximations to algebraic numbers, Mathematika 2 (1955), 1–20; corrigendum, 168. MR 72182, DOI 10.1112/S0025579300000644