An experimental investigation of the normality of irrational algebraic numbers

Nielsen, Johan; Simonsen, Jakob

doi:10.1090/S0025-5718-2013-02675-0

An experimental investigation of the normality of irrational algebraic numbers

Authors: Johan Sejr Brinch Nielsen and Jakob Grue Simonsen
Journal: Math. Comp. 82 (2013), 1837-1858
MSC (2010): Primary 11-04, 11Y60, 65-04, 65-05
DOI: https://doi.org/10.1090/S0025-5718-2013-02675-0
Published electronically: March 20, 2013
Supplement: Table supplement to this article.
MathSciNet review: 3042587
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We investigate the distribution of digits of large prefixes of the expansion of irrational algebraic numbers to different bases.

We compute $2\cdot 3^{18}$ bits of the binary expansions (corresponding to $2.33 \cdot 10^8$ decimals) of the 39 least Pisot-Vijayaraghavan numbers, the 47 least known Salem numbers, the least 20 square roots of positive integers that are not perfect squares, and 15 randomly generated algebraic irrationals. We employ these to compute the generalized serial statistics (roughly, the variant of the $\chi ^2$ -statistic apt for distribution of sequences of characters) of the distributions of digit blocks for each number to bases 2, 3, 5, 7 and 10, as well as the maximum relative frequency deviation from perfect equidistribution. We use the two statistics to perform tests at significance level $\alpha = 0.05$ , respectively, maximum deviation threshold $\alpha = 0.05$ .

Our results suggest that if Borel's conjecture--that all irrational algebraic numbers are normal--is true, then it may have an empirical base: The distribution of digits in algebraic numbers appears close to equidistribution for large prefixes of their expansion. Of the 121 algebraic numbers studied, all numbers passed the maximum relative frequency deviation test in all considered bases for digit block sizes 1, 2, 3, and 4; furthermore, 92 numbers passed all tests up to block size in all bases considered.

1. Forman S. Acton, Numerical methods that work, Mathematical Association of America, Washington, DC, 1990. Corrected reprint of the 1970 edition. MR 1074173
2. Boris Adamczewski, Yann Bugeaud, and Florian Luca, Sur la complexité des nombres algébriques, C. R. Math. Acad. Sci. Paris 339 (2004), no. 1, 11–14 (French, with English and French summaries). MR 2075225, https://doi.org/10.1016/j.crma.2004.04.012
3. Boris Adamczewski and Yann Bugeaud, On the complexity of algebraic numbers. I. Expansions in integer bases, Ann. of Math. (2) 165 (2007), no. 2, 547–565. MR 2299740, https://doi.org/10.4007/annals.2007.165.547
4. B. Adamczewski and N. Rampersad, On patterns occurring in binary algebraic numbers, Proc. Amer. Math. Soc. 136 (2008), no. 9, 3105–3109. MR 2407073, https://doi.org/10.1090/S0002-9939-08-09319-2
5. Jean-Paul Allouche and Luca Q. Zamboni, Algebraic irrational binary numbers cannot be fixed points of non-trivial constant length or primitive morphisms, J. Number Theory 69 (1998), no. 1, 119–124. MR 1611101, https://doi.org/10.1006/jnth.1997.2207
6. David H. Bailey, Jonathan M. Borwein, Richard E. Crandall, and Carl Pomerance, On the binary expansions of algebraic numbers, J. Théor. Nombres Bordeaux 16 (2004), no. 3, 487–518 (English, with English and French summaries). MR 2144954
7. David H. Bailey and Richard E. Crandall, On the random character of fundamental constant expansions, Experiment. Math. 10 (2001), no. 2, 175–190. MR 1837669
8. David H. Bailey and Richard E. Crandall, Random generators and normal numbers, Experiment. Math. 11 (2002), no. 4, 527–546 (2003). MR 1969644
9. David H. Bailey and Michał Misiurewicz, A strong hot spot theorem, Proc. Amer. Math. Soc. 134 (2006), no. 9, 2495–2501. MR 2213726, https://doi.org/10.1090/S0002-9939-06-08551-0
10. 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
11. 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
12. M.-J. Bertin and David W. Boyd, A characterization of two related classes of Salem numbers, J. Number Theory 50 (1995), no. 2, 309–317. MR 1316825, https://doi.org/10.1006/jnth.1995.1024
13. M.-J. Bertin, A. Decomps-Guilloux, M. Grandet-Hugot, M. Pathiaux-Delefosse, and J.-P. Schreiber, Pisot and Salem numbers, Birkhäuser Verlag, Basel, 1992. With a preface by David W. Boyd. MR 1187044
14. W. A. Beyer, N. Metropolis, and J. R. Neergaard, The generalized serial test applied to expansions of some irrational square roots in various bases, Math. Comp. 24 (1970), 745–747. MR 273773, https://doi.org/10.1090/S0025-5718-1970-0273773-8
15. W. A. Beyer, N. Metropolis, and J. R. Neergaard, Statistical study of digits of some square roots of integers in various bases, Math. Comp. 24 (1970), 455–473. MR 272129, https://doi.org/10.1090/S0025-5718-1970-0272129-1
16. Patrick Billingsley, Asymptotic distributions of two goodness of fit criteria, Ann. Math. Statist. 27 (1956), 1123–1129. MR 82770, https://doi.org/10.1214/aoms/1177728078
17. D. Bini and G Fiorentino, MPSolve benchmarks, http://www.dm.unipi.it/cluster-pages/mpsolve/bench.htm, Retrieved 2009-11-11, 5.55PM GMT.
18. Dario Andrea Bini and Giuseppe Fiorentino, Design, analysis, and implementation of a multiprecision polynomial rootfinder, Numer. Algorithms 23 (2000), no. 2-3, 127–173. MR 1772050, https://doi.org/10.1023/A:1019199917103
19. E. Borel, Les probabilités dénombrables et leurs applications arithmétiques, Rendiconti del Circolo Matematico di Palermo 27 (1909), 247-271.
20. Émile Borel, Sur les chiffres décimaux de √2 et divers problèmes de probabilités en chaîne, C. R. Acad. Sci. Paris 230 (1950), 591–593 (French). MR 34544
21. David W. Boyd, Small Salem numbers, Duke Math. J. 44 (1977), no. 2, 315–328. MR 453692
22. David W. Boyd, Pisot and Salem numbers in intervals of the real line, Math. Comp. 32 (1978), no. 144, 1244–1260. MR 491587, https://doi.org/10.1090/S0025-5718-1978-0491587-8
23. D.G. Champernowne, The Construction of Decimals Normal in the Scale of Ten, J. London Math. Soc. s1-8 (1933), no. 4, 254-260.
24. Arthur H. Copeland and Paul Erdös, Note on normal numbers, Bull. Amer. Math. Soc. 52 (1946), 857–860. MR 17743, https://doi.org/10.1090/S0002-9904-1946-08657-7
25. H. Davenport and P. Erdös, Note on normal decimals, Canad. J. Math. 4 (1952), 58–63. MR 47084, https://doi.org/10.4153/cjm-1952-005-3
26. Y. Dodge, A natural random number generator, International Statistical Review / Revue Internationale de Statistique 64 (1996), no. 3, 329-344.
27. Artūras Dubickas, Sumsets of Pisot and Salem numbers, Expo. Math. 26 (2008), no. 1, 85–91. MR 2384277, https://doi.org/10.1016/j.exmath.2007.06.002
28. William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery, Numerical recipes, 3rd ed., Cambridge University Press, Cambridge, 2007. The art of scientific computing. MR 2371990
29. Steven Fortune, An iterated eigenvalue algorithm for approximating roots of univariate polynomials, J. Symbolic Comput. 33 (2002), no. 5, 627–646. Computer algebra (London, ON, 2001). MR 1919907, https://doi.org/10.1006/jsco.2002.0526
30. Eknath Ghate and Eriko Hironaka, The arithmetic and geometry of Salem numbers, Bull. Amer. Math. Soc. (N.S.) 38 (2001), no. 3, 293–314. MR 1824892, https://doi.org/10.1090/S0273-0979-01-00902-8
31. I.J. Good and T.N. Gover, The generalized serial test and the binary expansion of $\sqrt 2$ , Journal of the Royal Statistical Society. Series A (General) 130 (1967), no. 1, 102-107.
32. -, Corrigendum: The generalized serial test and the binary expansion of $\sqrt {2}$ , Journal of the Royal Statistical Society. Series A (General) 131 (1968), no. 3, 434.
33. A.K. Gupta and A.K. Mittal, Symbolic computation of the roots of any polynomial with integer coefficients, Unpublished; available at http://arxiv.org/abs/math.GM/0001144, 2000.
34. Glyn Harman, One hundred years of normal numbers, Number theory for the millennium, II (Urbana, IL, 2000) A K Peters, Natick, MA, 2002, pp. 149–166. MR 1956249
35. Bruce R. Johnson and David J. Leeming, A study of the digits of 𝜋,𝑒 and certain other irrational numbers, Sankhyā Ser. B 52 (1990), no. 2, 183–189. MR 1178904
36. Tomi Kärki, Transcendence of numbers with an expansion in a subclass of complexity 2𝑁+1, Theor. Inform. Appl. 40 (2006), no. 3, 459–471. MR 2269204, https://doi.org/10.1051/ita:2006034
37. Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
38. 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
39. D. Lai and M.-F. Danca, Fractal and statistical analysis on digits of irrational numbers, Chaos, Solitons and Fractals 36 (2008), no. 2, 246-252.
40. H. Lebesgue, Sur certaines démonstrations d’existence, Bull. Soc. Math. France 45 (1917), 132–144 (French). MR 1504765
41. Ehud Lehrer, The game of normal numbers, Math. Oper. Res. 29 (2004), no. 2, 259–265. MR 2065976, https://doi.org/10.1287/moor.1030.0087
42. Manfred G. Madritsch, Jörg M. Thuswaldner, and Robert F. Tichy, Normality of numbers generated by the values of entire functions, J. Number Theory 128 (2008), no. 5, 1127–1145. MR 2406483, https://doi.org/10.1016/j.jnt.2007.04.005
43. W. Sierpinski, Démonstration élémentaire du théorème de M. Borel sur les nombres absolument normaux et détermination effective d’une tel nombre, Bull. Soc. Math. France 45 (1917), 125–132 (French). MR 1504764
44. R. G. Stoneham, A study of 60,000 digits of the transcendental “𝑒”, Amer. Math. Monthly 72 (1965), 483–500. MR 179871, https://doi.org/10.2307/2314118
45. S.J. Tu and E. Fischbach, A study on the randomness of the digits of Pi, International Journal of Modern Physics C 16 (2005), no. 2, 281-294.
46. Edgardo Ugalde, An alternative construction of normal numbers, J. Théor. Nombres Bordeaux 12 (2000), no. 1, 165–177 (English, with English and French summaries). MR 1827846
47. Stan Wagon, Is 𝜋 normal?, Math. Intelligencer 7 (1985), no. 3, 65–67. MR 795541, https://doi.org/10.1007/BF03025811
48. Klaus Weihrauch, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction. MR 1795407