On the distribution of partial quotients of reduced fractions with fixed denominator

Aistleitner, Christoph; Borda, Bence; Hauke, Manuel

doi:10.1090/tran/9065

On the distribution of partial quotients of reduced fractions with fixed denominator
HTML articles powered by AMS MathViewer

by Christoph Aistleitner, Bence Borda and Manuel Hauke;

Trans. Amer. Math. Soc. 377 (2024), 1371-1408

DOI: https://doi.org/10.1090/tran/9065

Published electronically: November 8, 2023

HTML | PDF | Request permission

Abstract:

In this paper, we study distributional properties of the sequence of partial quotients in the continued fraction expansion of fractions $a/N$, where $N$ is fixed and $a$ runs through the set of mod $N$ residue classes which are coprime with $N$. Our methods cover statistics such as the sum of partial quotients, the maximal partial quotient, the empirical distribution of partial quotients, Dedekind sums, and much more. We prove a sharp concentration inequality for the sum of partial quotients, and sharp tail estimates for the maximal partial quotient and for Dedekind sums, all matching the tail behavior in the limit laws which are known under an extra averaging over the set of possible denominators $N$. We show that the distribution of partial quotients of reduced fractions with fixed denominator gives a very good fit to the Gauß–Kuzmin distribution. As corollaries we establish the existence of reduced fractions with a small sum of partial quotients resp. a small maximal partial quotient.

References

M. O. Avdeeva and V. A. Bykovskiĭ, Statistical properties of finite continued fractions with a fixed denominator, Dokl. Akad. Nauk 449 (2013), no. 3, 255–258 (Russian); English transl., Dokl. Math. 87 (2013), no. 2, 160–163. MR 3114015, DOI 10.1134/s1064562413020117
Viviane Baladi and Brigitte Vallée, Euclidean algorithms are Gaussian, J. Number Theory 110 (2005), no. 2, 331–386. MR 2122613, DOI 10.1016/j.jnt.2004.08.008
Philippe Barkan, Sur les sommes de Dedekind et les fractions continues finies, C. R. Acad. Sci. Paris Sér. A-B 284 (1977), no. 16, A923–A926. MR 434934
Sandro Bettin and Sary Drappeau, Limit laws for rational continued fractions and value distribution of quantum modular forms, Proc. Lond. Math. Soc. (3) 125 (2022), no. 6, 1377–1425. MR 4524220, DOI 10.1112/plms.12485
Jean Bourgain and Alex Kontorovich, On Zaremba’s conjecture, Ann. of Math. (2) 180 (2014), no. 1, 137–196. MR 3194813, DOI 10.4007/annals.2014.180.1.3
V. A. Bykovskiĭ, An estimate for the dispersion of lengths of finite continued fractions, Fundam. Prikl. Mat. 11 (2005), no. 6, 15–26 (Russian, with English and Russian summaries); English transl., J. Math. Sci. (N.Y.) 146 (2007), no. 2, 5634–5643. MR 2204419, DOI 10.1007/s10958-007-0378-9
V. A. Bykovskiĭ and D. A. Frolenkov, On the average length of finite continued fractions with fixed denominator, Mat. Sb. 208 (2017), no. 5, 63–102 (Russian, with Russian summary); English transl., Sb. Math. 208 (2017), no. 5-6, 644–683. MR 3646487, DOI 10.4213/sm8718
Mei-Chu Chang, Partial quotients and equidistribution, C. R. Math. Acad. Sci. Paris 349 (2011), no. 13-14, 713–718 (English, with English and French summaries). MR 2825927, DOI 10.1016/j.crma.2011.06.007
T. W. Cusick, Zaremba’s conjecture and sums of the divisor function, Math. Comp. 61 (1993), no. 203, 171–176. MR 1189517, DOI 10.1090/S0025-5718-1993-1189517-7
Ofir David and Uri Shapira, Equidistribution of divergent orbits and continued fraction expansion of rationals, J. Lond. Math. Soc. (2) 98 (2018), no. 1, 149–176. MR 3847236, DOI 10.1112/jlms.12128
Josef Dick, Peter Kritzer, and Friedrich Pillichshammer, Lattice rules—numerical integration, approximation, and discrepancy, Springer Series in Computational Mathematics, vol. 58, Springer, Cham, [2022] ©2022. With an appendix by Adrian Ebert. MR 4472208, DOI 10.1007/978-3-031-09951-9
Dmitry Dolgopyat, On decay of correlations in Anosov flows, Ann. of Math. (2) 147 (1998), no. 2, 357–390. MR 1626749, DOI 10.2307/121012
Dmitrii A. Frolenkov and Igor D. Kan, A strengthening of a theorem of Bourgain-Kontorovich II, Mosc. J. Comb. Number Theory 4 (2014), no. 1, 78–117. MR 3284129
Douglas Hensley, The largest digit in the continued fraction expansion of a rational number, Pacific J. Math. 151 (1991), no. 2, 237–255. MR 1132388, DOI 10.2140/pjm.1991.151.237
Dean Hickerson, Continued fractions and density results for Dedekind sums, J. Reine Angew. Math. 290 (1977), 113–116. MR 439725, DOI 10.1515/crll.1977.290.113
Edmund Hlawka, Uniform distribution modulo $1$ and numerical analysis, Compositio Math. 16 (1964), 92–105 (1964). MR 175278
ShinnYih Huang, An improvement to Zaremba’s conjecture, Geom. Funct. Anal. 25 (2015), no. 3, 860–914. MR 3361774, DOI 10.1007/s00039-015-0327-6
Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 286318
N. M. Korobov, Teoretiko-chislovye metody v priblizhennom analize, Gosudarstv. Izdat. Fiz.-Mat. Lit., Moscow, 1963 (Russian). MR 157483
Dimitris Koukoulopoulos, The distribution of prime numbers, Graduate Studies in Mathematics, vol. 203, American Mathematical Society, Providence, RI, [2019] ©2019. MR 3971232, DOI 10.1090/gsm/203
L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 419394
Gerhard Larcher, On the distribution of sequences connected with good lattice points, Monatsh. Math. 101 (1986), no. 2, 135–150. MR 843297, DOI 10.1007/BF01298926
Bernhard Liehl, Über die Teilnenner endlicher Kettenbrüche, Arch. Math. (Basel) 40 (1983), no. 2, 139–147 (German). MR 720904, DOI 10.1007/BF01192762
N. Moshchevitin, B. Murphy, and I. Shkredov, On Korobov bound concerning Zaremba’s conjecture, arXiv:2212.14646.
Nikolay G. Moshchevitin and Dmitrii M. Ushanov, On Larcher’s theorem concerning good lattice points and multiplicative subgroups modulo $p$, Unif. Distrib. Theory 5 (2010), no. 1, 45–52. MR 2804661
Harald Niederreiter, Dyadic fractions with small partial quotients, Monatsh. Math. 101 (1986), no. 4, 309–315. MR 851952, DOI 10.1007/BF01559394
Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
A. A. Panov, The mean for a sum of elements in a class of finite continued fractions, Mat. Zametki 32 (1982), no. 5, 593–600, 747 (Russian). MR 684601
J. W. Porter, On a theorem of Heilbronn, Mathematika 22 (1975), no. 1, 20–28. MR 498452, DOI 10.1112/S0025579300004459
Hans Rademacher and Emil Grosswald, Dedekind sums, The Carus Mathematical Monographs, No. 16, Mathematical Association of America, Washington, DC, 1972. MR 357299, DOI 10.5948/UPO9781614440161
M. G. Rukavishnikova, A probability estimate for the sum of incomplete partial quotients with fixed denominator, Chebyshevskiĭ Sb. 7 (2006), no. 4(20), 113–121 (Russian, with English and Russian summaries). MR 2455630
M. G. Rukavishnikova, The law of large numbers for the sum of partial quotients of a rational number with a fixed denominator, Mat. Zametki 90 (2011), no. 3, 431–444 (Russian, with Russian summary); English transl., Math. Notes 90 (2011), no. 3-4, 418–430. MR 2868371, DOI 10.1134/S0001434611090100
A. V. Ustinov, On the number of solutions of the congruence $xy\equiv l\pmod q$ under the graph of a twice continuously differentiable function, Algebra i Analiz 20 (2008), no. 5, 186–216 (Russian, with Russian summary); English transl., St. Petersburg Math. J. 20 (2009), no. 5, 813–836. MR 2492364, DOI 10.1090/S1061-0022-09-01074-7
Ilan Vardi, Dedekind sums have a limiting distribution, Internat. Math. Res. Notices 1 (1993), 1–12. MR 1201746, DOI 10.1155/S1073792893000017
Andrew C. Yao and Donald E. Knuth, Analysis of the subtractive algorithm for greatest common divisors, Proc. Nat. Acad. Sci. U.S.A. 72 (1975), no. 12, 4720–4722. MR 417041, DOI 10.1073/pnas.72.12.4720
S. K. Zaremba, Good lattice points modulo composite numbers, Monatsh. Math. 78 (1974), 446–460. MR 371845, DOI 10.1007/BF01295488