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
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
- Received by editor(s): January 19, 2016
- Received by editor(s) in revised form: May 15, 2016
- Published electronically: May 17, 2017
- © Copyright 2017 American Mathematical Society
- Journal: Math. Comp. 86 (2017), 2911-2926
- MSC (2010): Primary 11K16; Secondary 11Y16
- DOI: https://doi.org/10.1090/mcom/3189
- MathSciNet review: 3667030