On the Stern–Brocot expansion of real numbers
Reutenauer, Christophe1
1 Université du Québec à Montréal CP 8888 succ. Centre-Ville, Montréal, H3C 3P8 Canada
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 SL2(ℤ). 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 SL2(ℤ)-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 SL2(ℤ)-equivalence of these quadratic forms.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/jtnb.1104
Classification : 11E16, 11A55
Mots-clés : Stern–Brocot tree, continued fractions, quadratic forms, quadratic numbers, Sturmian sequences
Reutenauer, Christophe 1

1 Université du Québec à Montréal CP 8888 succ. Centre-Ville, Montréal, H3C 3P8 Canada 
@article{JTNB_2019__31_3_697_0,
     author = {Reutenauer, Christophe},
     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://www.numdam.org/articles/10.5802/jtnb.1104/}
}
TY  - JOUR
AU  - Reutenauer, Christophe
TI  - On the Stern–Brocot expansion of real numbers
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2019
SP  - 697
EP  - 722
VL  - 31
IS  - 3
PB  - Société Arithmétique de Bordeaux
UR  - https://www.numdam.org/articles/10.5802/jtnb.1104/
DO  - 10.5802/jtnb.1104
LA  - en
ID  - JTNB_2019__31_3_697_0
ER  - 
%0 Journal Article
%A Reutenauer, Christophe
%T On the Stern–Brocot expansion of real numbers
%J Journal de théorie des nombres de Bordeaux
%D 2019
%P 697-722
%V 31
%N 3
%I Société Arithmétique de Bordeaux
%U https://www.numdam.org/articles/10.5802/jtnb.1104/
%R 10.5802/jtnb.1104
%G en
%F JTNB_2019__31_3_697_0
Reutenauer, Christophe. 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://www.numdam.org/articles/10.5802/jtnb.1104/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cité par Sources :