Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Computable absolutely normal numbers and discrepancies


Author: Adrian-Maria Scheerer
Journal: Math. Comp. 86 (2017), 2911-2926
MSC (2010): Primary 11K16; Secondary 11Y16
DOI: https://doi.org/10.1090/mcom/3189
Published electronically: May 17, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We analyze algorithms that output absolutely normal numbers digit-by-digit with respect to quality of convergence to normality of the output, measured by the discrepancy. We consider explicit variants of algorithms by Sierpinski, by Turing and an adaption of constructive work on normal numbers by Schmidt. There seems to be a trade-off between the complexity of the algorithm and the speed of convergence to normality of the output.


References [Enhancements On Off] (What's this?)

  • [1] Nicolás Alvarez and Verónica Becher, M. Levin's construction of absolutely normal numbers with very low discrepancy, arXiv:1510.02004.
  • [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 polynomial-time algorithm for computing absolutely normal numbers, Inform. and Comput. 232 (2013), 1-9. MR 3132518
  • [6] 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
  • [7] Émile Borel, Les probabilités dénombrables et leurs applications arithmétiques, Rendiconti del Circolo Matematico di Palermo 27 (1909), no. 1, 247-271 (French)., https://doi.org/10.1007/BF03019651
  • [8] Yann Bugeaud, Distribution Modulo One and Diophantine Approximation, Cambridge Tracts in Mathematics, vol. 193, Cambridge University Press, Cambridge, 2012. MR 2953186
  • [9] Michael Drmota and Robert F. Tichy, Sequences, Discrepancies and Applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456
  • [10] 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
  • [11] L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Pure and Applied Mathematics. MR 0419394
  • [12] M. B. Levin, Absolutely normal numbers, Vestnik Moskov. Univ. Ser. I Mat. Mekh. 1 (1979), 31-37, 87. MR 525299
  • [13] M. B. Levin, On the discrepancy estimate of normal numbers, Acta Arith. 88 (1999), no. 2, 99-111. MR 1700240
  • [14] Manfred G. Madritsch, Adrian-Maria Scheerer, and Robert F. Tichy, Absolutely Pisot Normal Numbers, Preprint.
  • [15] Johann Schiffer, Discrepancy of normal numbers, Acta Arith. 47 (1986), no. 2, 175-186. MR 867496
  • [16] Wolfgang M. Schmidt, On normal numbers, Pacific J. Math. 10 (1960), 661-672. MR 0117212
  • [17] Wolfgang M. Schmidt, Über die Normalität von Zahlen zu verschiedenen Basen, Acta Arith. 7 (1961/1962), 299-309 (German). MR 0140482
  • [18] Wolfgang M. Schmidt, Irregularities of distribution. VII, Acta Arith. 21 (1972), 45-50. MR 0319933
  • [19] Waclaw Sierpinski, Démonstration élémentaire du théorème de M. Borel sur les nombres absolument normaux et détermination effective d'un tel nombre, Bulletin de la Société Mathématique de France 45 (1917), 127-132.
  • [20] A. M. Turing, Collected Works, Collected Works of A. M. Turing, North-Holland Publishing Co., Amsterdam, 1992. Mechanical intelligence; Edited and with an introduction by D. C. Ince; With a preface by P. N. Furbank. MR 1150053
  • [21] Donald D. Wall, Normal Numbers, ProQuest LLC, Ann Arbor, MI, 1950. Thesis (Ph.D.)-University of California, Berkeley. MR 2937990

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11K16, 11Y16

Retrieve articles in all journals with MSC (2010): 11K16, 11Y16


Additional Information

Adrian-Maria Scheerer
Affiliation: Institute of Analysis and Number Theory, Graz University of Technology , Kopernikusgasse 24/II, 8010 Graz, Austria
Email: scheerer@math.tugraz.at

DOI: https://doi.org/10.1090/mcom/3189
Received by editor(s): January 19, 2016
Received by editor(s) in revised form: May 15, 2016
Published electronically: May 17, 2017
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society