On the Stern–Brocot expansion of real numbers
Christophe Reutenauer1
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 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 : 10.5802/jtnb.1104
Classification : 11E16, 11A55
Mots clés : Stern–Brocot tree, continued fractions, quadratic forms, quadratic numbers, Sturmian sequences
Christophe Reutenauer 1

1 Université du Québec à Montréal CP 8888 succ. Centre-Ville, Montréal, H3C 3P8 Canada
Licence : CC-BY-ND 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@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},
     mrnumber = {4102624},
     zbl = {1454.11067},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1104/}
}
TY  - JOUR
AU  - Christophe Reutenauer
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://jtnb.centre-mersenne.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 Christophe Reutenauer
%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://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1104/
%R 10.5802/jtnb.1104
%G en
%F JTNB_2019__31_3_697_0
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

[2] Cyril Allauzen 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] Jean-Paul Allouche; Jeffrey Shallit Automatic sequences. Theory, applications, generalizations, Cambridge University Press, 2003 | Zbl

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

[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 | DOI | MR | Zbl

[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 | DOI | Numdam | Zbl

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

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

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

[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 | DOI | Numdam | MR | Zbl

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

[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 | DOI | Zbl

[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

[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, 1794, Springer, 2002 | MR | Zbl

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

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

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

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

[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 | Zbl

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

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

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

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

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

[25] Bruno Parvaix 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] George N. Raney On continued fractions and finite automata, Math. Ann., Volume 206 (1973), pp. 265-283 | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

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

Cité par Sources :