M. Levin’s construction of absolutely normal numbers with very low discrepancy
HTML articles powered by AMS MathViewer
- by Nicolás Álvarez and Verónica Becher PDF
- Math. Comp. 86 (2017), 2927-2946 Request permission
Abstract:
Among the currently known constructions of absolutely normal numbers, the one given by Mordechay Levin in 1979 achieves the lowest discrepancy bound. In this work we analyze this construction in terms of computability and computational complexity. We show that, under basic assumptions, it yields a computable real number. The construction does not give the digits of the fractional expansion explicitly, but it gives a sequence of increasing approximations whose limit is the announced absolutely normal number. The $n$-th approximation has an error less than $2^{-2^{n}}$. To obtain the $n$-th approximation the construction requires, in the worst case, a number of mathematical operations that is doubly exponential in $n$. We consider variants on the construction that reduce the computational complexity at the expense of an increment in discrepancy.References
- Milton Abramowitz and Irene A. Stegun (eds.), Handbook of mathematical functions with formulas, graphs, and mathematical tables, Dover Publications, Inc., New York, 1992. Reprint of the 1972 edition. MR 1225604
- Verónica Becher, Yann Bugeaud, and Theodore A. Slaman, On simply normal numbers to different bases, Math. Ann. 364 (2016), no. 1-2, 125–150. MR 3451383, DOI 10.1007/s00208-015-1209-9
- Verónica Becher and Santiago Figueira, An example of a computable absolutely normal number, Theoret. Comput. Sci. 270 (2002), no. 1-2, 947–958. MR 1871106, DOI 10.1016/S0304-3975(01)00170-0
- Verónica Becher, Santiago Figueira, and Rafael Picchi, Turing’s unpublished algorithm for normal numbers, Theoret. Comput. Sci. 377 (2007), no. 1-3, 126–138. MR 2323391, DOI 10.1016/j.tcs.2007.02.022
- Verónica Becher, Pablo Ariel Heiber, and Theodore A. Slaman, A computable absolutely normal Liouville number, Math. Comp. 84 (2015), no. 296, 2939–2952. MR 3378855, DOI 10.1090/mcom/2964
- Verónica Becher, Pablo Ariel Heiber, and Theodore A. Slaman, A polynomial-time algorithm for computing absolutely normal numbers, Inform. and Comput. 232 (2013), 1–9. MR 3132518, DOI 10.1016/j.ic.2013.08.013
- Verónica Becher and Theodore A. Slaman, On the normality of numbers to different bases, J. Lond. Math. Soc. (2) 90 (2014), no. 2, 472–494. MR 3263961, DOI 10.1112/jlms/jdu035
- Lenore Blum, Mike Shub, and Steve Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.) 21 (1989), no. 1, 1–46. MR 974426, DOI 10.1090/S0273-0979-1989-15750-9
- É. Borel, Les probabilités d’enombrables et leurs applications arithmétiques, Supplemento di 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
- D. G. Champernowne, The Construction of Decimals Normal in the Scale of Ten, J. London Math. Soc. 8 (1933), no. 4, 254–260. MR 1573965, DOI 10.1112/jlms/s1-8.4.254
- Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288, DOI 10.1007/978-0-387-68441-3
- Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456, DOI 10.1007/BFb0093404
- S. Gaal and L. Gál, The discrepancy of the sequence $\{(2^{n}x)\}$, Nederl. Akad. Wetensch. Proc. Ser. A 67 = Indag. Math. 26 (1964), 129–143. MR 0163089
- J. F. Koksma, Some theorems on Diophantine inequalities, Scriptum no. 5, Math. Centrum, Amsterdam, 1950. MR 0038379
- L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences, Dover Publications, Inc., New York, 2006.
- M. B. Levin, The uniform distribution of the sequence $\{\alpha \lambda ^{x}\}$, Mat. Sb. (N.S.) 98(140) (1975), no. 2 (10), 207–222, 333 (Russian). MR 0406947
- M. B. Levin, Absolutely normal numbers, Vestnik Moskov. Univ. Ser. I Mat. Mekh. 1 (1979), 31–37, 87 (Russian, with French summary). MR 525299
- M. B. Levin, On the discrepancy estimate of normal numbers, Acta Arith. 88 (1999), no. 2, 99–111. MR 1700240, DOI 10.4064/aa-88-2-99-111
- M. Madritsch and R. Tichy, Dynamical systems and uniform distribution of sequences, arXiv:1501.07411v1, 2015.
- A.-M. Scheerer, Computable absolutely normal numbers and discrepancies, Math. Comp., to appear, DOI: 10.1090/mcom/3189.
- Johann Schiffer, Discrepancy of normal numbers, Acta Arith. 47 (1986), no. 2, 175–186. MR 867496, DOI 10.4064/aa-47-2-175-186
- 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
- A. M. Turing, Pure mathematics, Collected Works of A. M. Turing, North-Holland Publishing Co., Amsterdam, 1992. Edited and with an introduction and postscript by J. L. Britton; With a preface by P. N. Furbank. MR 1150052
Additional Information
- Nicolás Álvarez
- Affiliation: Departamento de Ciencias e Ingeniería de la Computación, ICIC, Universidad Nacional del Sur-CONICET, Bahía Blanca, Argentina
- Email: naa@cs.uns.edu.ar
- Verónica Becher
- Affiliation: Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires & CONICET, Argentina
- MR Author ID: 368040
- Email: vbecher@dc.uba.ar
- Received by editor(s): September 28, 2015
- Received by editor(s) in revised form: March 28, 2016, and May 9, 2016
- Published electronically: March 29, 2017
- Additional Notes: The first author was supported by a doctoral fellowship from CONICET, Argentina.
The second author was supported by Agencia Nacional de Promoción Científica y Tecnológica and CONICET, Argentina. - © Copyright 2017 American Mathematical Society
- Journal: Math. Comp. 86 (2017), 2927-2946
- MSC (2010): Primary 11K16, 11K38, 68-04; Secondary 11-04
- DOI: https://doi.org/10.1090/mcom/3188
- MathSciNet review: 3667031