Normal numbers with digit dependencies
HTML articles powered by AMS MathViewer
- by Christoph Aistleitner, Verónica Becher and Olivier Carton PDF
- Trans. Amer. Math. Soc. 372 (2019), 4425-4446 Request permission
Abstract:
We give metric theorems for the property of Borel normality for real numbers under the assumption of digit dependencies in their expansion in a given integer base. We quantify precisely how much digit dependence can be allowed such that almost all real numbers are normal. Our theorem states that almost all real numbers are normal when at least slightly more than $\log \log n$ consecutive digits with indices starting at position $n$ are independent. As the main application, we consider the Toeplitz set $T_P$, which is the set of all sequences $a_1a_2 \ldots$ of symbols from $\{0, \ldots , b-1\}$ such that $a_n$ is equal to $a_{pn}$ for every $p$ in $P$ and $n=1,2,\ldots$. Here $b$ is an integer base and $P$ is a finite set of prime numbers. We show that almost every real number whose base $b$ expansion is in $T_P$ is normal to base $b$. In the case when $P$ is the singleton set $\{2\}$ we prove that more is true: almost every real number whose base $b$ expansion is in $T_P$ is normal to all integer bases. We also consider the Toeplitz transform which maps the set of all sequences to the set $T_P$, and we characterize the normal sequences whose Toeplitz transform is normal as well.References
- Christoph Aistleitner, Metric number theory, lacunary series and systems of dilated functions, Uniform distribution and quasi-Monte Carlo methods, Radon Ser. Comput. Appl. Math., vol. 15, De Gruyter, Berlin, 2014, pp. 1–16. MR 3287357
- Robert B. Ash, Information theory, Dover Publications, Inc., New York, 1990. Corrected reprint of the 1965 original. MR 1088248
- Alan Baker, Transcendental number theory, Cambridge University Press, London-New York, 1975. MR 0422171, DOI 10.1017/CBO9780511565977
- Verónica Becher and Olivier Carton, Normal numbers and computer science, Sequences, groups, and number theory, Trends Math., Birkhäuser/Springer, Cham, 2018, pp. 233–269. MR 3799929, DOI 10.1007/978-3-319-69152-7_{7}
- Verónica Becher, Olivier Carton, and Pablo Ariel Heiber, Finite-state independence, Theory Comput. Syst. 62 (2018), no. 7, 1555–1572. MR 3832108, DOI 10.1007/s00224-017-9821-6
- Bernard Bercu, Bernard Delyon, and Emmanuel Rio, Concentration inequalities for sums and martingales, SpringerBriefs in Mathematics, Springer, Cham, 2015. MR 3363542, DOI 10.1007/978-3-319-22099-4
- E. Borel. Les probabilités dénombrables et leurs applications arithmétiques. Rendiconti del Circolo Matematico di Palermo, 27 (1909) 247–271.
- Yann Bugeaud, Distribution modulo one and Diophantine approximation, Cambridge Tracts in Mathematics, vol. 193, Cambridge University Press, Cambridge, 2012. MR 2953186, DOI 10.1017/CBO9781139017732
- J. W. S. Cassels, On a problem of Steinhaus about normal numbers, Colloq. Math. 7 (1959), 95–101. MR 113863, DOI 10.4064/cm-7-1-95-101
- Thomas M. Cover and Joy A. Thomas, Elements of information theory, 2nd ed., Wiley-Interscience [John Wiley & Sons], Hoboken, NJ, 2006. MR 2239987
- Harry Furstenberg, Disjointness in ergodic theory, minimal sets, and a problem in Diophantine approximation, Math. Systems Theory 1 (1967), 1–49. MR 213508, DOI 10.1007/BF01692494
- Konrad Jacobs and Michael Keane, $0-1$-sequences of Toeplitz type, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 13 (1969), 123–131. MR 255766, DOI 10.1007/BF00537017
- Calvin T. Long, Note on normal numbers, Pacific J. Math. 7 (1957), 1163–1165. MR 91959, DOI 10.2140/pjm.1957.7.1163
- Walter Philipp, Empirical distribution functions and strong approximation theorems for dependent random variables. A problem of Baker in probabilistic number theory, Trans. Amer. Math. Soc. 345 (1994), no. 2, 705–727. MR 1249469, DOI 10.1090/S0002-9947-1994-1249469-5
- S. S. Pillai, On normal numbers, Proc. Indian Acad. Sci., Sect. A. 12 (1940), 179–184. MR 0002324, DOI 10.1007/BF03173913
- Wolfgang M. Schmidt, Über die Normalität von Zahlen zu verschiedenen Basen, Acta Arith. 7 (1961/62), 299–309 (German). MR 140482, DOI 10.4064/aa-7-3-299-309
- Eric V. Slud, Distribution inequalities for the binomial law, Ann. Probability 5 (1977), no. 3, 404–412. MR 438420, DOI 10.1214/aop/1176995801
- R. Tijdeman, On integers with many small prime factors, Compositio Math. 26 (1973), 319–330. MR 325549
- Donald D. Wall, NORMAL NUMBERS, ProQuest LLC, Ann Arbor, MI, 1950. Thesis (Ph.D.)–University of California, Berkeley. MR 2937990
Additional Information
- Christoph Aistleitner
- Affiliation: Institute of Analysis and Number Theory, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria
- Email: aistleitner@math.tugraz.at
- Verónica Becher
- Affiliation: Departamento de Computación and ICC CONICET, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellón I, Ciudad Universitaria, C1428EGA Buenos Aires, Argentina
- MR Author ID: 368040
- Email: vbecher@dc.uba.ar
- Olivier Carton
- Affiliation: Institut de Recherche en Informatique Fondamentale, Université Paris Diderot, Case 7014, 75205 Paris Cedex 13, France
- MR Author ID: 359872
- Email: olivier.carton@irif.fr
- Received by editor(s): April 9, 2018
- Received by editor(s) in revised form: June 26, 2018, and September 4, 2018
- Published electronically: November 26, 2018
- Additional Notes: The first author is supported by the Austrian Science Fund (FWF), projects Y-901 and F-5512-N26.
The second and third authors are members of the Laboratoire International Associé INFINIS, CONICET/Universidad de Buenos Aires–CNRS/Université Paris Diderot, and they are supported by the ECOS project PA17C04.
The third author is also partially funded by the DeLTA project (ANR-16-CE40-0007). - © Copyright 2018 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 372 (2019), 4425-4446
- MSC (2010): Primary 11K16; Secondary 68R15
- DOI: https://doi.org/10.1090/tran/7706
- MathSciNet review: 4009433