Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

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

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 $ 4$ in all bases considered.


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

  • 1. F.S. Acton, Numerical methods that work, Mathematical Association of America, 1990. MR 1074173 (92a:65002)
  • 2. B. Adamczewski and Y. Bugeaud, Sur la complexité des nombres algébriques, Comptes Rendus Mathématique. Académie des Sciences. Paris 339 (2004), no. 1, 11-14. MR 2075225 (2005g:11033)
  • 3. -, On the complexity of algebraic numbers i: Expansions in integer bases, Annals of Mathematics 165 (2007), no. 2, 547-565. MR 2299740 (2008a:11130)
  • 4. B. Adamczewski and B. Rampersad, On patterns occurring in binary algebraic numbers, Proceedings of the American Mathematical Society 136 (2008), 3105-3109. MR 2407073 (2009b:11128)
  • 5. J.-P. Allouche and L.Q. Zamboni, Algebraic irrational binary numbers cannot be fixed points of non-trivial constant length or primitive morphisms, Journal of Number Theory 69 (1998), no. 1, 119-124. MR 1611101 (99e:11104)
  • 6. D.H. Bailey, J.M. Borwein, R.E. Crandall, and C. Pomerance, On the binary expansions of algebraic numbers, Journal de théorie des nombres de Bordeaux 16 (2004), no. 3, 487-518. MR 2144954 (2006f:11088)
  • 7. D.H. Bailey and R.E. Crandall, On the random character of fundamental constant expansions, Experimental Mathematics 10 (2001), no. 2, 175-190. MR 1837669 (2002h:11067)
  • 8. -, Random generators and normal numbers, Experimental Mathematics 11 (2002), 527-546. MR 1969644 (2004c:11135)
  • 9. D.H. Bailey and M. Misiurewicz, A strong hot spot theorem, Proceedings of the American Mathematical Society 134 (2006), 2495-2501. MR 2213726 (2007b:11108)
  • 10. V. Becher and S. Figueira, An example of a computable absolutely normal number, Theoretical Computer Science 270 (2002), no. 1-2, 947-958. MR 1871106 (2002m:11070)
  • 11. V. Becher, S. Figueira, and R. Picchi, Turing's unpublished algorithm for normal numbers, Theoretical Computer Science 377 (2007), no. 1-3, 126-138. MR 2323391 (2008j:03064)
  • 12. M.J. Bertin and D.W. Boyd, A characterization of two related classes of Salem numbers, Journal of Number Theory 50 (1995), no. 2, 309 - 317. MR 1316825 (96b:11139)
  • 13. M.J. Bertin, A. Decomps-Guilloux, M. Grandet-Hugot, and J.P. Pathiaux-Delefosse, Pisot and Salem numbers, Birkhäuser, Verlag, Basel 1992.MR 1187044 (93k:11095)
  • 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, Mathematics of Computation 24 (1970), no. 111, 745-747. MR 0273773 (42:8649)
  • 15. -, Statistical study of digits of some square roots of integers in various bases, Mathematics of Computation 24 (1970), no. 110, 455-473. MR 0272129 (42:7010)
  • 16. P. Billingsley, Asymptotic distributions of two goodness of fit criteria, Annals of Mathematical Statistics 27 (1995), 1123-1129. MR 0082770 (18:607e)
  • 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. D. Bini and G. Fiorentino, Design, analysis and implementation of a multiprecision polynomial rootfinder, Numerical Algorithms 23 (2000), 127-173. MR 1772050 (2001h:26019)
  • 19. E. Borel, Les probabilités dénombrables et leurs applications arithmétiques, Rendiconti del Circolo Matematico di Palermo 27 (1909), 247-271.
  • 20. É Borel, Sur les chiffres décimaux de $ \sqrt {2}$ et divers problèmes de probabilités en chaîne, Comptes Rendus Mathématique. Académie des Sciences. Paris 230 (1950), 591-593. MR 0034544 (11:605d)
  • 21. D.W. Boyd, Small Salem numbers, Duke Mathematical Journal 44 (1977), no. 2, 315-328. MR 0453692 (56:11952)
  • 22. -, Pisot and Salem numbers in intervals of the real line, Mathematics of Computation 32 (1978), no. 144, 1244-1260. MR 0491587 (58:10812)
  • 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. A.H. Copeland and P. Erdös, Note on normal numbers, Bulletin of the American Mathematical Society 52 (1946), 857-860. MR 0017743 (8:194b)
  • 25. H. Davenport and P. Erdös, Note on normal decimals, Canadian Journal of Mathematics 4 (1952), 58-63. MR 0047084 (13:825g)
  • 26. Y. Dodge, A natural random number generator, International Statistical Review / Revue Internationale de Statistique 64 (1996), no. 3, 329-344.
  • 27. A. Dubickas, Sumsets of Pisot and Salem numbers, Expositiones Mathematicae 26 (2008), no. 1, 85-91. MR 2384277 (2008m:11210)
  • 28. B.P. Flannery, Numerical recipes, 3rd ed., Cambridge University Press, 2007. MR 2371990 (2009b:65001)
  • 29. S. Fortune, An iterated eigenvalue algorithm for approximating roots of univariate polynomials, Journal of Symbolic Computation 33 (2002), no. 5, 627-646. MR 1919907 (2003e:13039)
  • 30. E. Ghate and E. Hironaka, The arithmetic and geometry of Salem numbers, Bulletin of the American Mathematical Society 38 (2001), no. 3, 293-314. MR 1824892 (2002c:11137)
  • 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. G. Harman, One hundred years of normal numbers, Surveys in Number Theory: Papers from the Milennial Conference on Number Theory (M.A. Bennett, ed.), A.K. Peters, Ltd., 2002, pp. 59-74. MR 1956249 (2003k:11124)
  • 35. B.R. Johnson and D.J. Leeming, A study of the digits of $ \pi $, e and certain other irrational numbers, Sankhyā: The Indian Journal of Statistics, Series B 52 (1990), no. 2, 183-189. MR 1178904 (93e:65010)
  • 36. T. Kärki, Transcendence of numbers with an expansion in a subclass of complexity 2n, Theoretical Informatics and Applications 40 (2006), no. 3, 459-471. MR 2269204 (2007h:11078)
  • 37. D.K. Knuth, Art of computer programming, volume 2: Seminumerical algorithms, third ed., Addison-Wesley Professional, November 1997. MR 633878 (83i:68003)
  • 38. L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Wiley-Interscience Series of Texts, Monographs and Tracts in Pure and Applied Mathematics, Wiley-Interscience, 1974. MR 0419394 (54:7415)
  • 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, Bulletin de la Société Mathématique de France 45 (1917), 132-144. MR 1504765
  • 41. E. Lehrer, The game of normal numbers, Mathematics of Operations Research 29 (2004), 259-265. MR 2065976 (2005a:91003)
  • 42. M.G. Madritsch, J.M. Thuswaldner, and R.F. Tichy, Normality of numbers generated by the values of entire functions, Journal of Number Theory 128 (2008), no. 5, 1127-1145. MR 2406483 (2009f:11092)
  • 43. W. 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), 125-132. MR 1504764
  • 44. R. G. Stoneham, A study of 60,000 digits of the transcendental ``e'', The American Mathematical Monthly 72 (1965), no. 5, 483-500. MR 0179871 (31:4108)
  • 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. E. Ugalde, An alternative construction of normal numbers, Journal de théorie des nombres de Bordeaux 12 (2000), no. 1, 165-177. MR 1827846 (2002b:11101)
  • 47. S. Wagon, Is Pi normal?, The Mathematical Intelligencer (1985), 65-67. MR 795541 (86j:11135)
  • 48. K. Weihrauch, Computable analysis: An introduction, Springer-Verlag, 1998. MR 1795407 (2002b:03129)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11-04, 11Y60, 65-04, 65-05

Retrieve articles in all journals with MSC (2010): 11-04, 11Y60, 65-04, 65-05


Additional Information

Johan Sejr Brinch Nielsen
Affiliation: FYS-NEXMAP, DTU Physics, Technical University of Denmark, Building 307, DK-2800 Kgs. Lyngby, Denmark
Email: jsbn@fysik.dtu.dk

Jakob Grue Simonsen
Affiliation: Department of Computer Science, University of Copenhagen (DIKU), Njalsgade 126–128, DK-2300 Copenhagen S Denmark
Email: simonsen@diku.dk

DOI: https://doi.org/10.1090/S0025-5718-2013-02675-0
Received by editor(s): May 4, 2011
Received by editor(s) in revised form: November 18, 2011
Published electronically: March 20, 2013

American Mathematical Society