Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

M. Levin's construction of absolutely normal numbers with very low discrepancy


Authors: Nicolás Álvarez and Verónica Becher
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
Published electronically: March 29, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Milton Abramowitz and Irene A. Stegun (eds.), Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, Reprint of the 1972 edition, Dover Publications, Inc., New York, 1992. MR 1225604
  • [2] 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, https://doi.org/10.1007/s00208-015-1209-9
  • [3] 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, https://doi.org/10.1016/S0304-3975(01)00170-0
  • [4] 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, https://doi.org/10.1016/j.tcs.2007.02.022
  • [5] 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, https://doi.org/10.1090/mcom/2964
  • [6] 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, https://doi.org/10.1016/j.ic.2013.08.013
  • [7] 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, https://doi.org/10.1112/jlms/jdu035
  • [8] 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, https://doi.org/10.1090/S0273-0979-1989-15750-9
  • [9] É. Borel, Les probabilités d'enombrables et leurs applications arithmétiques, Supplemento di Rendiconti del Circolo Matematico di Palermo 27 (1909), 247-271.
  • [10] Yann Bugeaud, Distribution Modulo One and Diophantine Approximation, Cambridge Tracts in Mathematics, vol. 193, Cambridge University Press, Cambridge, 2012. MR 2953186
  • [11] D. G. Champernowne, The construction of decimals normal in the scale of ten, J. London Math. Soc. S1-8, no. 4, 254. MR 1573965, https://doi.org/10.1112/jlms/s1-8.4.254
  • [12] Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288
  • [13] Michael Drmota and Robert F. Tichy, Sequences, Discrepancies and Applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456
  • [14] 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
  • [15] J. F. Koksma, Some Theorems on Diophantine Inequalities, Scriptum no. 5, Math. Centrum Amsterdam, 1950. MR 0038379
  • [16] L. Kuipers and H. Niederreiter,
    Uniform Distribution of Sequences,
    Dover Publications, Inc., New York, 2006.
  • [17] 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
  • [18] M. B. Levin, Absolutely normal numbers, Vestnik Moskov. Univ. Ser. I Mat. Mekh. 1 (1979), 31-37, 87 (Russian, with French summary). MR 525299
  • [19] M. B. Levin, On the discrepancy estimate of normal numbers, Acta Arith. 88 (1999), no. 2, 99-111. MR 1700240
  • [20] M. Madritsch and R. Tichy, Dynamical systems and uniform distribution of sequences, arXiv:1501.07411v1, 2015.
  • [21] A.-M. Scheerer, Computable absolutely normal numbers and discrepancies, Math. Comp., to appear, DOI: 10.1090/mcom/3189.
  • [22] Johann Schiffer, Discrepancy of normal numbers, Acta Arith. 47 (1986), no. 2, 175-186. MR 867496
  • [23] Wolfgang M. Schmidt, Über die Normalität von Zahlen zu verschiedenen Basen, Acta Arith. 7 (1961/1962), 299-309 (German). MR 0140482
  • [24] 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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11K16, 11K38, 68-04, 11-04

Retrieve articles in all journals with MSC (2010): 11K16, 11K38, 68-04, 11-04


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
Email: vbecher@dc.uba.ar

DOI: https://doi.org/10.1090/mcom/3188
Keywords: Normal numbers, discrepancy, algorithms
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.
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society