Sturmian Words and the Permutation that Orders Fractional Parts
Kevin O'Bryant
University of California, San Diego, USA
DOI: 10.1023/B:JACO.0000022568.96268.12
Abstract
A Sturmian word is a map W : \mathbb N {\mathbb{N}} \mathbb N {\mathbb{N}} } has cardinality exactly n + 1 for each positive integer n. Our main result is that the volume of the simplex whose n + 1 vertices are the n + 1 points in F n( W) does not depend on W. Our proof of this motivates studying algebraic properties of the permutation 
, n (where is any irrational and n is any positive integer) that orders the fractional parts { }, {2 },...,{ n }, i.e., 0 <> , n (1) } <> , n (2) } < ;;;=""> <> , n ( n) } < 1.="" we="" give="" a="" formula="" for="" the="" sign="" of=""> , n , and prove that for every irrational there are infinitely many n such that the order of , n (as an element of the symmetric group S n) is less than n.
, n (where is any irrational and n is any positive integer) that orders the fractional parts { }, {2 },...,{ n }, i.e., 0 <> , n (1) } <> , n (2) } < ;;;=""> <> , n ( n) } < 1.="" we="" give="" a="" formula="" for="" the="" sign="" of=""> , n , and prove that for every irrational there are infinitely many n such that the order of , n (as an element of the symmetric group S n) is less than n.Pages: 91–115
Keywords: Sturmian word; Beatty sequence; quasi crystal; sos permutation
Full Text: PDF
References
1. P. Alessandri and V. Berthé, “Three distance theorems and combinatorics on words,” Enseign. Math. (2) 44(1/2) (1998), 103-132.
2. D.W. Boyd and J.M. Steele, “Monotone subsequences in the sequence of fractional parts of multiples of an irrational,” J. Reine Angew. Math. 306 (1979), 49-59.
3. T.C. Brown, “Descriptions of the characteristic sequence of an irrational,” Canad. Math. Bull. 36 (1) (1993), 15-21.
4. J.N. Cooper, “Quasirandom permutations,” arXiv:math.CO/0211001, 2002.
5. H. Eves, A Survey of Geometry, revised edition, Allyn and Bacon Inc., Boston, Mass., 1972.
6. M. Lothaire, Algebraic Combinatorics on Words, 1st edn., Cambridge University Press, Cambridge, U.K.,
2002. Currently available online at http://www-igm.univ-mlv.fr/\sim berstel/Lothaire/.
7. B.E. Sagan, The Symmetric Group, 2nd edn., Springer-Verlag, New York,
2001. Representations, combinatorial algorithms, and symmetric functions.
8. J. Schoißengeier, On the discrepancy of (nα), Acta Arith. 44(3) (1984), 241-279.
9. M. Senechal, Quasicrystals and Geometry, Cambridge University Press, Cambridge, 1995.
10. N.B. Slater, “Gaps and steps for the sequence nθmod 1,” Proc. Cambridge Philos. Soc. 63(1967), 1115-1123.
11. V.T. Sós, “A lánct\ddot ortek egy geometriai interpretációja és alkalmazásai [On a geometrical theory of continued fractions],” Mat. Lapok 8 (1957), 248-263.
12. K.B. Stolarsky, “Beatty sequences, continued fractions, and certain shift operators,” Canad. Math. Bull. 19(4) (1976), 473-482,.
13. J.-P. Sydler, “Conditions nécessaires et suffisantes pour l'équivalence des poly`edres de l'espace euclidien `a trois dimensions,” Comment. Math. Helv. 40 (1965), 43-80.
14. R. Tijdeman, “Exact covers of balanced sequences and Fraenkel's conjecture,” in Algebraic Number Theory and Diophantine Analysis (Graz, 1998), de Gruyter, Berlin, 2000, pp. 467-483.
2. D.W. Boyd and J.M. Steele, “Monotone subsequences in the sequence of fractional parts of multiples of an irrational,” J. Reine Angew. Math. 306 (1979), 49-59.
3. T.C. Brown, “Descriptions of the characteristic sequence of an irrational,” Canad. Math. Bull. 36 (1) (1993), 15-21.
4. J.N. Cooper, “Quasirandom permutations,” arXiv:math.CO/0211001, 2002.
5. H. Eves, A Survey of Geometry, revised edition, Allyn and Bacon Inc., Boston, Mass., 1972.
6. M. Lothaire, Algebraic Combinatorics on Words, 1st edn., Cambridge University Press, Cambridge, U.K.,
2002. Currently available online at http://www-igm.univ-mlv.fr/\sim berstel/Lothaire/.
7. B.E. Sagan, The Symmetric Group, 2nd edn., Springer-Verlag, New York,
2001. Representations, combinatorial algorithms, and symmetric functions.
8. J. Schoißengeier, On the discrepancy of (nα), Acta Arith. 44(3) (1984), 241-279.
9. M. Senechal, Quasicrystals and Geometry, Cambridge University Press, Cambridge, 1995.
10. N.B. Slater, “Gaps and steps for the sequence nθmod 1,” Proc. Cambridge Philos. Soc. 63(1967), 1115-1123.
11. V.T. Sós, “A lánct\ddot ortek egy geometriai interpretációja és alkalmazásai [On a geometrical theory of continued fractions],” Mat. Lapok 8 (1957), 248-263.
12. K.B. Stolarsky, “Beatty sequences, continued fractions, and certain shift operators,” Canad. Math. Bull. 19(4) (1976), 473-482,.
13. J.-P. Sydler, “Conditions nécessaires et suffisantes pour l'équivalence des poly`edres de l'espace euclidien `a trois dimensions,” Comment. Math. Helv. 40 (1965), 43-80.
14. R. Tijdeman, “Exact covers of balanced sequences and Fraenkel's conjecture,” in Algebraic Number Theory and Diophantine Analysis (Graz, 1998), de Gruyter, Berlin, 2000, pp. 467-483.