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
HTML articles powered by AMS MathViewer

by Johan Sejr Brinch Nielsen and Jakob Grue Simonsen

Math. Comp. 82 (2013), 1837-1858

DOI: https://doi.org/10.1090/S0025-5718-2013-02675-0

Published electronically: March 20, 2013

PDF | Request permission

Supplement: Table supplement to this article.

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

Forman S. Acton, Numerical methods that work, Mathematical Association of America, Washington, DC, 1990. Corrected reprint of the 1970 edition. MR 1074173
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, DOI 10.1016/j.crma.2004.04.012
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, DOI 10.4007/annals.2007.165.547
B. Adamczewski and N. Rampersad, On patterns occurring in binary algebraic numbers, Proc. Amer. Math. Soc. 136 (2008), no. 9, 3105–3109. MR 2407073, DOI 10.1090/S0002-9939-08-09319-2
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, DOI 10.1006/jnth.1997.2207
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
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
David H. Bailey and Richard E. Crandall, Random generators and normal numbers, Experiment. Math. 11 (2002), no. 4, 527–546 (2003). MR 1969644
David H. Bailey and MichałMisiurewicz, A strong hot spot theorem, Proc. Amer. Math. Soc. 134 (2006), no. 9, 2495–2501. MR 2213726, DOI 10.1090/S0002-9939-06-08551-0
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
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, DOI 10.1006/jnth.1995.1024
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, DOI 10.1007/978-3-0348-8632-1
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, DOI 10.1090/S0025-5718-1970-0273773-8
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, DOI 10.1090/S0025-5718-1970-0272129-1
Patrick Billingsley, Asymptotic distributions of two goodness of fit criteria, Ann. Math. Statist. 27 (1956), 1123–1129. MR 82770, DOI 10.1214/aoms/1177728078
D. Bini and G Fiorentino, MPSolve benchmarks, http://www.dm.unipi.it/cluster-pages/mpsolve/bench.htm, Retrieved 2009-11-11, 5.55PM GMT.
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, DOI 10.1023/A:1019199917103
E. Borel, Les probabilités dénombrables et leurs applications arithmétiques, Rendiconti del Circolo Matematico di Palermo 27 (1909), 247–271.
Émile Borel, Sur les chiffres décimaux de $\sqrt {2}$ et divers problèmes de probabilités en chaîne, C. R. Acad. Sci. Paris 230 (1950), 591–593 (French). MR 34544
David W. Boyd, Small Salem numbers, Duke Math. J. 44 (1977), no. 2, 315–328. MR 453692
David W. Boyd, Pisot and Salem numbers in intervals of the real line, Math. Comp. 32 (1978), no. 144, 1244–1260. MR 491587, DOI 10.1090/S0025-5718-1978-0491587-8
D.G. Champernowne, The Construction of Decimals Normal in the Scale of Ten, J. London Math. Soc. s1-8 (1933), no. 4, 254–260.
Arthur H. Copeland and Paul Erdös, Note on normal numbers, Bull. Amer. Math. Soc. 52 (1946), 857–860. MR 17743, DOI 10.1090/S0002-9904-1946-08657-7
H. Davenport and P. Erdös, Note on normal decimals, Canad. J. Math. 4 (1952), 58–63. MR 47084, DOI 10.4153/cjm-1952-005-3
Y. Dodge, A natural random number generator, International Statistical Review / Revue Internationale de Statistique 64 (1996), no. 3, 329–344.
Artūras Dubickas, Sumsets of Pisot and Salem numbers, Expo. Math. 26 (2008), no. 1, 85–91. MR 2384277, DOI 10.1016/j.exmath.2007.06.002
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
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, DOI 10.1006/jsco.2002.0526
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, DOI 10.1090/S0273-0979-01-00902-8
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.
—, 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.
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.
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
Bruce R. Johnson and David J. Leeming, A study of the digits of $\pi ,\;e$ and certain other irrational numbers, Sankhyā Ser. B 52 (1990), no. 2, 183–189. MR 1178904
Tomi Kärki, Transcendence of numbers with an expansion in a subclass of complexity $2N+1$, Theor. Inform. Appl. 40 (2006), no. 3, 459–471. MR 2269204, DOI 10.1051/ita:2006034
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, MA, 1981. Seminumerical algorithms. MR 633878
L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 419394
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.
H. Lebesgue, Sur certaines démonstrations d’existence, Bull. Soc. Math. France 45 (1917), 132–144 (French). MR 1504765
Ehud Lehrer, The game of normal numbers, Math. Oper. Res. 29 (2004), no. 2, 259–265. MR 2065976, DOI 10.1287/moor.1030.0087
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, DOI 10.1016/j.jnt.2007.04.005
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
R. G. Stoneham, A study of $60,000$ digits of the transcendental “$e$”, Amer. Math. Monthly 72 (1965), 483–500. MR 179871, DOI 10.2307/2314118
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.
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
Stan Wagon, Is $\pi$ normal?, Math. Intelligencer 7 (1985), no. 3, 65–67. MR 795541, DOI 10.1007/BF03025811
Klaus Weihrauch, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction. MR 1795407, DOI 10.1007/978-3-642-56999-9