Farey fractions and permutations generated by fractional parts $\{i\alpha\}$

A. V. Shutov

Čebyševskij sbornik, Tome 15 (2014) no. 1, pp. 195-203.

Résumé

Let $\alpha\in(0;1)$ be an irrational number. Study of the distribution of fractional parts $\{i\alpha\}$ on the interval $(0;1)$ is a classical question in number theory. In particular, H. Weyl proved that this sequence is uniformity distributed modulo 1. Since this work, various estimates for the remainder term of the asymptotic formula for the number of the sequence of points belonging to a given interval are actively investigated. Another type of problems about considered sequence are problems associated with the famous three lenghts theorem (Steinhaus conjecture), which state that a tiling of the unit interval generated by the points of the sequence, composed of intervals of two or three different lengths. Moreover, in the second case the length of the greatest inteval exactly equals the sum of the lengths of two other intervals. It was find out that the geometry of these tilings is closely connected with the first return maps for circle rotations, Hecke–Kesten problem on bounded remainder sets, combinatorics of Sturmian sequences, dynamics of two-color rotations of the circle, and some other problems. This paper deals to combinatorial properties of the sequence $\{i\alpha\}$, such as permutations $\pi_{\alpha,n}$, generated by the points $\{i\alpha\}$, $1\leq i\leq n$. It is proved that there is a one-to-one correspondence between these permutations and the intervals of Farey tilings of the level $n$. Here Farey tiling of the level $n$ is a tiling of the interval $ [0;1]$ generated by irreducible rational fractions of the form $ \frac{a}{b}$ with denominator $0$. The proof is based on one theorem of V. T. Sos, that allows to compute the permutation $\pi_{\alpha, n}$ using only $\pi_{\alpha,n}(1)$ and $\pi_{\alpha, n}(n)$. Also we use the fact that the ends of intervals of the Farey coincide with the points of discontinuity of the functions $\{k\alpha\}-\{l\alpha\}$. As an application it is proved that there are exactly $1+\sum_{k = 2}^n \varphi(k)$ different permutations $\pi_{\alpha,n}$ for any fixed $n$. Another our result states that the permutation $\pi_{\alpha,n}$ uniquely determines permutations $\pi_{\alpha,m} $ with $n$ and does not uniquely determine the permutation $\pi_{\alpha,m} $ with $m=\pi_{\alpha,n}(1)+\pi_{\alpha,n}(n)$.

Détail

Keywords: fractional parts, permutations, Farey sequence.

Bibliographie

[1] Bukhshtab A. A., Teoriya chisel, Prosveschenie, M., 1966 | Zbl

[2] Zhuravlev V. G., “Dvukhtsvetnye povoroty edinichnoi okruzhnosti”, Izv. RAN. Ser. Mat., 73:1 (2009), 79–120 | DOI | MR | Zbl

[3] Zhuravlev V. G., “Odnomernye razbieniya Fibonachchi”, Izv. RAN. Ser. Mat., 71:2 (2007), 89–122 | DOI | MR | Zbl

[4] Manuilov N. N., Shutov A. V., “Globalnyi poryadok razbieniya okruzhnosti”, Molodezh. Obrazovanie. Ekonomika, Sbornik nauchnykh statei uchastnikov 5-oi Vserossiiskoi nauchno-prakticheskoi konferentsii molodykh uchenykh, aspirantov i studentov (4 maya 2004), Izd. Remder, Yaroslavl, 2004, 314–320

[5] Martynov A. V., “Otnoshenie poryadka diofantovogo tipa”, Chebyshevskii sbornik, 2 (2001), 61–72 | MR | Zbl

[6] Shutov A. V., “Neodnorodnye diofantovy priblizheniya i raspredelenie drobnykh dolei”, Fundamentalnaya i prikladnaya matematika, 16:6 (2010), 189–202

[7] Shutov A. V., “O raspredelenii drobnykh dolei”, Chebyshevskii sbornik, 5:3 (2004), 112–121 | MR | Zbl

[8] Shutov A. V., “O raspredelenii drobnykh dolei, II”, Mezhvuz. sb. nauch. tr., Issledovaniya po algebre, teorii chisel, funktsionalnomu analizu i smezhnym voprosam, 3, Iz-vo Saratovskogo Universiteta, Saratov, 2005, 146–158

[9] Shutov A. V., “Posledovatelnosti shturma: grafy Rozi i forsing”, Chebyshevskii sbornik, 8:2 (2007), 128–139 | MR | Zbl

[10] Shutov A. V., “Proizvodnye povorotov okruzhnosti i podobie orbit”, Zapiski nauchnykh seminarov POMI, 314 (2004), 272–284 | MR | Zbl

[11] Shutov A. V., “Sistemy schisleniya i mnozhestva ogranichennogo ostatka”, Chebyshevskii sbornik, 7:3 (2006), 110–128 | MR | Zbl

[12] Alessandri P., Berthe V., “Three distance theorems and combinatorics on words”, L'Enseignement Mathematique, 44 (1998), 103–132 | MR | Zbl

[13] Baxa C., “Comparing the distribution of $(n\alpha)$-sequences”, Acta Arithmetica, 94 (2002), 345–363 | MR

[14] Behnke H., “Zur Theorie der diophantischen Approximationen, I”, Abh. Math. Sem. Hamburg, 3 (1924), 261–318 | DOI | MR | Zbl

[15] Boyd D. W., Steele J. M., “Monotone subsequences in the sequence of fractional parts of multiplies of ann irrational”, J. Reine Angew. Math., 1979, no. 306, 49–59 | MR | Zbl

[16] O'Bryant K., “Sturmian Words and the Permutation that Orders Fractional Parts”, Journal of Algebraic combinatoric, 19:1 (2004), 91–115 | DOI | MR

[17] Farey J., “On a Curious Property of Vulgar Fractions”, London, Edinburgh and Dublin Phil. Mag., 47 (1816), 385

[18] Hardy G. H., Wright E. M., An introduction to the theory of numbers, Clarendon press, Oxford, 1975

[19] Hecke E., “Eber Analytische Funktionen und die Verteilung van Zahlen mod Eins”, Math. Sem. Hamburg Univ., 5 (1921), 54–76

[20] Kesten H., “On a conjecture of Erdös and Szüsz related to uniform distribution $\mod 1$”, Acta Arithmetica, 12 (1966), 193–212 | MR | Zbl

[21] Van Ravenstein T., “The three gap theorem (Steinhaus conjecture)”, Journal of the Australian Mathematical Society, 45:3 (1988), 360–370 | DOI | MR | Zbl

[22] Slater N. B., “Gaps and steps for the sequence $n\theta\bmod 1$”, Proc. Cambridge Phil. Soc., 63 (1967), 1115–1123 | DOI | MR | Zbl

[23] Swierczkowski S., “On successive settings of an arc on the circumference of a circle”, Fundam. Math., 46 (1958), 187–189 | MR

[24] Shutov A. V., “New estimates in the Hecke–Kesten problem”, Anal. Probab. Methods Number Theory, ed. E. Manstavičisus et al., TEV, Vilnius, 2007 | MR | Zbl

[25] Sos V. T., “A lánktörtek egy geometriai interpretációja és alkalmazásai”, Mat. Lapok., 8 (1957), 248–263 | MR

[26] Walfisz A., Weyl'sche Exponentialsummen in der neueren Zahlentheorie, Ch. 5, Deutscher Verlag der Wissenschaften, Berlin, 1963 | MR | Zbl

[27] Weyl H., “Über die Gibbs'sche Erscheinung und verwandte Konvergenzphänomene”, Rendicontidel Circolo Mathematico di Palermo, 30 (1910), 377–407 | DOI | Zbl