On the Stern–Brocot expansion of real numbers
Journal de Théorie des Nombres de Bordeaux, Tome 31 (2019) no. 3, pp. 697-722.

Le développement de Stern–Brocot d’un nombre réel est une suite finie ou infinie de symboles l,r, signifiant « gauche » et « droite », qui représente le chemin dans l’arbre de Stern–Brocot déterminé par ce nombre. On montre que ce développement est périodique si et seulement si le nombre est quadratique, positif, avec conjugué négatif ; dans ce cas la représentation de l’opposé du conjugué est obtenue par image miroir. Les pentes des suites sturmiennes morphiques sont exactement ces nombres. Deux nombres ont le même développement à partir d’un certain rang si et seulement s’ils sont équivalents sous l’action de SL 2 (). On obtient une relation d’adjacence pour les formes quadratiques binaires indéfinies, qui mène à un variante de la théorie des cycles de Gauss. Une bijection entre l’ensemble des mots de Lyndon sur deux lettres et les classes d’équivalence de ces formes est obtenue.

The Stern–Brocot expansion of a real number is a finite or infinite sequence of symbols r,l, meaning “right” and “left”, which represents the path in the Stern–Brocot tree determined by this number. It is shown that the expansion is periodic if and only if the number is positive quadratic with a negative conjugate; in this case the conjugate opposite’s expansion is obtained by reversal. The slopes of morphic Sturmian sequences are these quadratic numbers. Two numbers have ultimately the same exapansion if and only they are SL 2 ()-equivalent. A related neighbouring relation for indefinite binary quadratic forms leads to a variant of the Gauss theory of cycles. A bijection is obtained between the set of binary Lyndon words and SL 2 ()-equivalence of these quadratic forms.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : https://doi.org/10.5802/jtnb.1104
Classification : 11E16,  11A55
Mots clés : Stern–Brocot tree, continued fractions, quadratic forms, quadratic numbers, Sturmian sequences
@article{JTNB_2019__31_3_697_0,
     author = {Christophe Reutenauer},
     title = {On the {Stern{\textendash}Brocot} expansion of real numbers},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {697--722},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {31},
     number = {3},
     year = {2019},
     doi = {10.5802/jtnb.1104},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1104/}
}
Christophe Reutenauer. On the Stern–Brocot expansion of real numbers. Journal de Théorie des Nombres de Bordeaux, Tome 31 (2019) no. 3, pp. 697-722. doi : 10.5802/jtnb.1104. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1104/

[1] Martin Aigner Markov’s Theorem and 100 years of the Uniqueness Conjecture, a mathematical journey from irrational numbers to perfect matchings, Springer, 2013 | Zbl 1276.0006

[2] Cyril Allauzen Une caractérisation simple des nombres de Sturm, J. Théor. Nombres Bordeaux, Volume 10 (1998) no. 2, pp. 237-241 | Article | Numdam | Zbl 0930.11051

[3] Jean-Paul Allouche; Jeffrey Shallit Automatic sequences. Theory, applications, generalizations, Cambridge University Press, 2003 | Zbl 1086.11015

[4] Jean Berstel; Patrice Séébold Morphismes de Sturm, Bull. Belg. Math. Soc. Simon Stevin, Volume 1 (1994) no. 2, pp. 175-189 | Article | MR 1318967 | Zbl 0803.68095

[5] Jean-Pierre Borel Image par homographie de mots de Christoffel, Bull. Belg. Math. Soc. Simon Stevin, Volume 8 (2001) no. 2, pp. 241-255 | Article | MR 1838932 | Zbl 0994.68101

[6] Jean-Pierre Borel; François Laubie Quelques mots sur la droite projective réelle, J. Théor. Nombres Bordeaux, Volume 5 (1993) no. 1, pp. 23-51 | Article | Numdam | Zbl 0839.11008

[7] Thomas C Brown A characterization of the quadratic irrationals, Can. Math. Bull., Volume 34 (1991) no. 1, pp. 36-41 | Article | MR 1108926 | Zbl 0688.10007

[8] Duncan A. Buell Binary quadratic forms. Classical theory and modern computations, Springer, 1989 | Zbl 0698.10013

[9] Elwin B. Christoffel Lehrsätze über arithmetische Eigenschaften der Irrationalzahlen, Annali di Mat., Volume XV (1887), pp. 253-276 | Article | Zbl 20.0068.01

[10] David Crisp; William Moran; Andrew Pollington; Peter Shiue Substitution invariant cutting sequences, J. Théor. Nombres Bordeaux, Volume 5 (1993) no. 1, pp. 123-137 | Article | Numdam | MR 1251232 | Zbl 0786.11041

[11] Leonard E. Dickson Introduction to the theory of numbers, Dover Publications, 1957 | Zbl 0084.26901

[12] Xavier Droubay; Jacques Justin; Giuseppe Pirillo Episturmian words and some contructions of de Luca and Rauzy, Theor. Comput. Sci., Volume 255 (2001) no. 1-2, pp. 539-553 | Article | Zbl 0981.68126

[13] Pierre Fatou Sur l’approximation des incommensurables et les séries trigonométriques, C. R. Math. Acad. Sci. Paris, Volume 139 (1904), pp. 1019-1021 | Zbl 35.0275.02

[14] Substitutions in Dynamics, Arithmetics and Combinatorics (N. Pytheas Fogg; Valérie Berthé; Sébastien Ferenczi; Christian Mauduit; A. Siegel, eds.), Lecture Notes in Mathematics, Volume 1794, Springer, 2002 | MR 1970385 | Zbl 1014.11015

[15] John H. Grace The classification of rational approximations, Proc. Lond. Math. Soc., Volume 17 (1918), pp. 247-258 | Article | MR 1575573

[16] Ronald L. Graham; Donald E. Knuth; Oren Patashnik Concrete mathematics, Addison-Wesley Publishing Group, 1994 | Zbl 0836.00001

[17] Adolf Hurwitz Ueber die angenäherte Darstellung der Zahlen durch rationale Brüche, Math. Ann., Volume 44 (1894), pp. 417-436 | Article | Zbl 25.0322.04

[18] Adolf Hurwitz Ueber die Reduction der binären quadratischen Formen, Math. Ann., Volume 45 (1894), pp. 85-117 | Article | Zbl 25.0313.01

[19] Shunji Ito; Shin-ichi Yasutomi On continued fractions, substitutions and characteristic sequences [nx+y]-[(n-1)x+y], Jap. J. Math., Volume 16 (1990), pp. 287-306 | MR 1091163 | Zbl 0721.11009

[20] Jacques Justin; Giuseppe Pirillo Episturmian words and episturmian morphisms, Theor. Comput. Sci., Volume 276 (2002) no. 1-2, pp. 281-313 | Article | MR 1896357 | Zbl 1002.68116

[21] Takao Komatsu; Alfred J. van der Poorten Substitution invariant Beatty sequences, Jap. J. Math., Volume 22 (1996) no. 2, pp. 349-354 | Article | MR 1432380 | Zbl 0868.11015

[22] M. Lothaire Algebraic combinatorics on words, Encyclopedia of Mathematics and Its Applications, Volume 90, Cambridge University Press, 2002 | MR 1905123 | Zbl 1001.68093

[23] Marston Morse; Gustav A. Hedlund Symbolic dynamics II: Sturmian Trajectories, Am. J. Math., Volume 62 (1940), pp. 1-42 | Article | MR 745 | Zbl 0022.34003

[24] Milad Niqui Exact arithmetic on the Stern–Brocot tree, J. Discrete Algorithms, Volume 5 (2007) no. 2, pp. 356-379 | Article | MR 2317038 | Zbl 1127.68029

[25] Bruno Parvaix Propriétés d’invariance des mots sturmiens, J. Théor. Nombres Bordeaux, Volume 9 (1997) no. 2, pp. 351-369 | Article | MR 1617403 | Zbl 0904.11008

[26] George N. Raney On continued fractions and finite automata, Math. Ann., Volume 206 (1973), pp. 265-283 | Article | MR 340166 | Zbl 0251.10024

[27] Patrice Séébold Sturmian images of non Sturmian words and standard morphisms, Theor. Comput. Sci., Volume 711 (2018), pp. 92-104 | Article | MR 3778827 | Zbl 1393.68145

[28] Joseph-Alfred Serret Cours d’algèbre supérieure. I., éditions Jacques Gabay, 1992 | MR 1190472 | Zbl 17.0053.01

[29] A. Muhammed Uludaǧ; Ayberk Zeytin; Merve Durmuş Binary quadratic forms as dessins, J. Théor. Nombres Bordeaux, Volume 29 (2017) no. 2, pp. 445-469 | Article | MR 3682475 | Zbl 1420.11096

[30] Don B. Zagier Zetafunktionen und quadratische Körper, Eine Einführung in die Zahlentheorie, Springer, 1981 | Zbl 0459.10001