On the binary expansions of algebraic numbers

David H. Bailey; Jonathan M. Borwein; Richard E. Crandall; Carl Pomerance

doi:10.5802/jtnb.457

David H. Bailey ¹ ; Jonathan M. Borwein ² ; Richard E. Crandall ³ ; Carl Pomerance ⁴

¹ Lawrence Berkeley National Laboratory 1 Cyclotron Road Berkeley, CA 94720, USA
² Dalhousie University Department of Computer Science Halifax, NS B3H 4R2, Canada
³ Center for Advanced Computation Reed College Portland, OR 97202, USA
⁴ Dartmouth College Department of Mathematics 6188 Bradley Hall Hanover, NH 03755-3551, USA

Journal de théorie des nombres de Bordeaux, Tome 16 (2004) no. 3, pp. 487-518.

Résumé
Abstract

En combinant des concepts de théorie additive des nombres avec des résultats sur les développements binaires et les séries partielles, nous établissons de nouvelles bornes pour la densité de $1$ dans les développements binaires de nombres algébriques réels. Un résultat clef est que si un nombre réel $y$ est algébrique de degré $D > 1$ , alors le nombre $# (| y |, N)$ de $1$ dans le développement de $| y |$ parmi les $N$ premiers chiffres satisfait

# (| y |, N) > C N^{1 / D}

avec un nombre positif $C$ (qui dépend de $y$ ), la minoration étant vraie pour tout $N$ suffisamment grand. On en déduit la transcendance d’une classe de nombres réels $\sum_{n \geq 0} 1 / 2^{f (n)}$ quand la fonction $f$ , à valeurs entières, croît suffisamment vite, disons plus vite que toute puissance de $n$ . Grâce à ces méthodes on redémontre la transcendance du nombre de Kempner–Mahler $\sum_{n \geq 0} 1 / 2^{2^{n}}$ ; nous considérons également des nombres ayant une densité sensiblement plus grande de $1$ . Bien que le nombre $z = \sum_{n \geq 0} 1 / 2^{n^{2}}$ ait une densité de $1$ trop grande pour que nous puissions lui appliquer notre résultat central, nous parvenons à développer une analyse fine de théorie des nombres avec des calculs étendus pour révéler des propriétés de la structure binaire du nombre $z^{2}$ .

Employing concepts from additive number theory, together with results on binary evaluations and partial series, we establish bounds on the density of 1’s in the binary expansions of real algebraic numbers. A central result is that if a real $y$ has algebraic degree $D > 1$ , then the number $# (| y |, N)$ of 1-bits in the expansion of $| y |$ through bit position $N$ satisfies

# (| y |, N) > C N^{1 / D}

for a positive number $C$ (depending on $y$ ) and sufficiently large $N$ . This in itself establishes the transcendency of a class of reals $\sum_{n \geq 0} 1 / 2^{f (n)}$ where the integer-valued function $f$ grows sufficiently fast; say, faster than any fixed power of $n$ . By these methods we re-establish the transcendency of the Kempner–Mahler number $\sum_{n \geq 0} 1 / 2^{2^{n}}$ , yet we can also handle numbers with a substantially denser occurrence of 1’s. Though the number $z = \sum_{n \geq 0} 1 / 2^{n^{2}}$ has too high a 1’s density for application of our central result, we are able to invoke some rather intricate number-theoretical analysis and extended computations to reveal aspects of the binary structure of $z^{2}$ .

MR Zbl

DOI : 10.5802/jtnb.457

Affiliations des auteurs :

David H. Bailey ¹ ; Jonathan M. Borwein ² ; Richard E. Crandall ³ ; Carl Pomerance ⁴

¹ Lawrence Berkeley National Laboratory 1 Cyclotron Road Berkeley, CA 94720, USA
² Dalhousie University Department of Computer Science Halifax, NS B3H 4R2, Canada
³ Center for Advanced Computation Reed College Portland, OR 97202, USA
⁴ Dartmouth College Department of Mathematics 6188 Bradley Hall Hanover, NH 03755-3551, USA

@article{JTNB_2004__16_3_487_0,
     author = {David H. Bailey and Jonathan M. Borwein and Richard E. Crandall and Carl Pomerance},
     title = {On the binary expansions of algebraic numbers},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {487--518},
     publisher = {Universit\'e Bordeaux 1},
     volume = {16},
     number = {3},
     year = {2004},
     doi = {10.5802/jtnb.457},
     mrnumber = {2144954},
     zbl = {1076.11045},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.457/}
}

TY  - JOUR
AU  - David H. Bailey
AU  - Jonathan M. Borwein
AU  - Richard E. Crandall
AU  - Carl Pomerance
TI  - On the binary expansions of algebraic numbers
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2004
SP  - 487
EP  - 518
VL  - 16
IS  - 3
PB  - Université Bordeaux 1
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.457/
DO  - 10.5802/jtnb.457
LA  - en
ID  - JTNB_2004__16_3_487_0
ER  -

%0 Journal Article
%A David H. Bailey
%A Jonathan M. Borwein
%A Richard E. Crandall
%A Carl Pomerance
%T On the binary expansions of algebraic numbers
%J Journal de théorie des nombres de Bordeaux
%D 2004
%P 487-518
%V 16
%N 3
%I Université Bordeaux 1
%U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.457/
%R 10.5802/jtnb.457
%G en
%F JTNB_2004__16_3_487_0

David H. Bailey; Jonathan M. Borwein; Richard E. Crandall; Carl Pomerance. On the binary expansions of algebraic numbers. Journal de théorie des nombres de Bordeaux, Tome 16 (2004) no. 3, pp. 487-518. doi : 10.5802/jtnb.457. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.457/

Bibliographie
Cité par

[1] J.-P. Allouche, J. Shallit, Automatic Sequences; Theory, Applications, Generalizations. Cambridge University Press, 2003. | MR | Zbl

[2] David H. Bailey, Peter B. Borwein, Simon Plouffe, On The Rapid Computation of Various Polylogarithmic Constants. Mathematics of Computation 66 no. 218 (1997), 903–913. | MR | Zbl

[3] David H. Bailey, Richard E. Crandall, On the Random Character of Fundamental Constant Expansions. Experimental Mathematics 10 (2001), 175–190. | MR | Zbl

[4] David H. Bailey, Richard E. Crandall, Random generators and normal numbers. Experimental Mathematics, to appear. | MR | Zbl

[5] D. Bertrand, Theta functions and transcendence. Ramanujan Journal 1 (1997), 339–350. | MR | Zbl

[6] É. Borel, Sur les chiffres décimaux de $\sqrt{2}$ et divers problèmes de probabilités en chaine. C. R. Acad. Sci. Paris 230 (1950), 591–593. | MR | Zbl

[7] É. Borel, Oeuvres d’É. Borel Vol. 2. Éditions du CNRS, Paris, 1972, 1203-1204. | Zbl

[8] Peter Borwein, On the Irrationality of Certain Series. Mathematical Proceedings of the Cambridge Philosophical Society, 112 (1992), 141–146. | MR | Zbl

[9] D. G. Champernowne, The Construction of Decimals Normal in the Scale of Ten. Journal of the London Mathematical Society 8 (1933), 254–260. | Zbl

[10] R. Crandall, C. Pomerance, Prime Numbers: A Computational Perspective. Springer-Verlag, New York, 2002. | MR | Zbl

[11] R. Crandall, S. Wagon, Sums of squares: computational aspects. Manuscript, 2002.

[12] D. Duverney, Keiji. Nishioka, Kumiko Nishioka, I. Shiokawa, Transcendence of Jacobi’s theta series and related results. Number Theory. Diophantine, Computational and Algebraic Aspects, Kálmän Yöry (ed.) et al. , Walter de Gruyter, Berlin (1998), 157–168. | MR | Zbl

[13] P. Erdős, On Arithmetical Properties of Lambert Series. Journal of the Indian Mathematical Society (N.S.) 12 (1948), 63–66. | MR | Zbl

[14] P. Flajolet, I. Vardi, Zeta Function Expansions of Classical Constants. Manuscript (1996), available at http://pauillac.inria.fr/algo/flajolet/Publications/Landau.ps

[15] E. Grosswald, Representations of Integers as Sums of Squares. Springer-Verlag, New York, 1985. | MR | Zbl

[16] H. Halberstam, H.-E. Richert, Sieve Methods. Academic Press, London, 1974. | MR | Zbl

[17] G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers. Oxford University Press, 1979. | MR | Zbl

[18] G. H. Hardy, Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, 1999, 9–10, 55, and 60–64. | MR | Zbl

[19] Aubrey J. Kempner, On Transcendental Numbers Transactions of the American Mathematical Society 17 (1916), 476–482. | MR

[20] M. J. Knight, An ‘Ocean of Zeroes’ Proof That a Certain Non-Liouville Number is Transcendental. American Mathematical Monthly 98 (1991), 947–949. | MR | Zbl

[21] L. Kuipers, H. Niederreiter, Uniform Distribution of Sequences. Wiley-Interscience, New York, 1974. | MR | Zbl

[22] J. Lagarias, On the Normality of Fundamental Constants. Experimental Mathematics 10, no. 3 (2001), 353–366. | MR

[23] E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Bd. II, 2nd ed. New York: Chelsea, 1953, 641–669. | Zbl

[24] S. Lehr, Sums and rational multiples of $q$ -automatic sequences are $q$ -automatic. Theor. Comp. Sci. 108 (1993) 385–391. | MR | Zbl

[25] S. Lehr, J. Shallit, J. Tromp, On the vector space of the automatic reals. Theoretical Computer Science 163 (1996), 193–210. | MR | Zbl

[26] J. H. Loxton, A method of Mahler in transcendence theory and some of its applications. Bulletin of the Australian Mathematical Society 29 (1984), 127–136. | MR | Zbl

[27] J. H. Loxton, A. J. van der Poorten, Arithmetic properties of certain functions in several variables III. Bull. Austral. Math. Soc. 16 (1977), 15–47. | MR | Zbl

[28] G. Martin, Absolutely Abnormal Numbers. American Mathematical Monthly 108 no. 8 (2001), 746–754. | MR | Zbl

[29] W. Miller, Transcendence measures by a method of Mahler. Journal of the Australian Mathematical Society (Series A) 32 (1982), 68–78. | MR | Zbl

[30] Yu. V. Nesterenko, Modular functions and transcendence questions. Mat. Sb. 187 (1996), 65–96; translation in Sb. Math. 187 (1996), 1319–1348 [MR 97m:11102] | MR | Zbl

[31] I. Niven, Irrational Numbers. Carus Mathematical Monographs, no. 11, Wiley, New York, 1956. | MR | Zbl

[32] P. Ribenboim, The New Book of Prime Number Records. Springer-Verlag, New York, 1996. | MR | Zbl

[33] K. Roth, Rational Approximations to Algebraic Numbers. Mathematika 2 (1955), 1–20. Corrigendum, pp. 168. | MR | Zbl

[34] J. Samborski, Problem E2667. American Mathematical Monthly 84 (1977), pp. 567.

[35] J. Shallit, private communication.

[36] J. Shallit, A. van der Poorten, A specialised continued fraction. Canadian Journal of Mathematics 45 (1993), 1067–1079. | MR | Zbl

Cité par Sources :