Computable absolutely normal numbers and discrepancies

Scheerer, Adrian-Maria

doi:10.1090/mcom/3189

Computable absolutely normal numbers and discrepancies
HTML articles powered by AMS MathViewer

by Adrian-Maria Scheerer PDF

Math. Comp. 86 (2017), 2911-2926 Request permission

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

Nicolás Alvarez and Verónica Becher, M. Levin’s construction of absolutely normal numbers with very low discrepancy, arXiv:1510.02004.
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 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
É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)., DOI 10.1007/BF03019651
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
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
L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 0419394
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
Manfred G. Madritsch, Adrian-Maria Scheerer, and Robert F. Tichy, Absolutely Pisot Normal Numbers, Preprint.
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, On normal numbers, Pacific J. Math. 10 (1960), 661–672. MR 117212
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
Wolfgang M. Schmidt, Irregularities of distribution. VII, Acta Arith. 21 (1972), 45–50. MR 319933, DOI 10.4064/aa-21-1-45-50
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.
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
Donald D. Wall, NORMAL NUMBERS, ProQuest LLC, Ann Arbor, MI, 1950. Thesis (Ph.D.)–University of California, Berkeley. MR 2937990