On the binary expansions of algebraic numbers

David H. Bailey[1]; Jonathan M. Borwein[2]; Richard E. Crandall[3]; Carl Pomerance[4]

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

Journal de Théorie des Nombres de Bordeaux (2004)

  • Volume: 16, Issue: 3, page 487-518
  • ISSN: 1246-7405

Abstract

top
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 ∑ n ≥ 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 ∑ n ≥ 0 1 / 2 2 n , yet we can also handle numbers with a substantially denser occurrence of 1’s. Though the number z = ∑ n ≥ 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 .

How to cite

top

Bailey, David H., et al. "On the binary expansions of algebraic numbers." Journal de Théorie des Nombres de Bordeaux 16.3 (2004): 487-518. <http://eudml.org/doc/249270>.

@article{Bailey2004,
abstract = {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&gt; 1$, then the number $\#(|y|, N)$ of 1-bits in the expansion of $|y|$ through bit position $N$ satisfies\[ \#(|y|, N) &gt; CN^\{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 \ge 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 \ge 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 \ge 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$.},
affiliation = {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},
author = {Bailey, David H., Borwein, Jonathan M., Crandall, Richard E., Pomerance, Carl},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {binary-evaluation bounds; transcendency; algebraic numbers},
language = {eng},
number = {3},
pages = {487-518},
publisher = {Université Bordeaux 1},
title = {On the binary expansions of algebraic numbers},
url = {http://eudml.org/doc/249270},
volume = {16},
year = {2004},
}

TY - JOUR
AU - Bailey, David H.
AU - Borwein, Jonathan M.
AU - Crandall, Richard E.
AU - Pomerance, Carl
TI - On the binary expansions of algebraic numbers
JO - Journal de Théorie des Nombres de Bordeaux
PY - 2004
PB - Université Bordeaux 1
VL - 16
IS - 3
SP - 487
EP - 518
AB - 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&gt; 1$, then the number $\#(|y|, N)$ of 1-bits in the expansion of $|y|$ through bit position $N$ satisfies\[ \#(|y|, N) &gt; CN^{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 \ge 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 \ge 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 \ge 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$.
LA - eng
KW - binary-evaluation bounds; transcendency; algebraic numbers
UR - http://eudml.org/doc/249270
ER -

References

top
  1. J.-P. Allouche, J. Shallit, Automatic Sequences; Theory, Applications, Generalizations. Cambridge University Press, 2003. Zbl1086.11015MR1997038
  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. Zbl0879.11073MR1415794
  3. David H. Bailey, Richard E. Crandall, On the Random Character of Fundamental Constant Expansions. Experimental Mathematics 10 (2001), 175–190. Zbl1047.11073MR1837669
  4. David H. Bailey, Richard E. Crandall, Random generators and normal numbers. Experimental Mathematics, to appear. Zbl1165.11328MR1969644
  5. D. Bertrand, Theta functions and transcendence. Ramanujan Journal 1 (1997), 339–350. Zbl0916.11043MR1608721
  6. É. Borel, Sur les chiffres décimaux de 2 et divers problèmes de probabilités en chaine. C. R. Acad. Sci. Paris 230 (1950), 591–593. Zbl0035.08302MR34544
  7. É. Borel, Oeuvres d’É. Borel Vol. 2. Éditions du CNRS, Paris, 1972, 1203-1204. Zbl0256.01025
  8. Peter Borwein, On the Irrationality of Certain Series. Mathematical Proceedings of the Cambridge Philosophical Society, 112 (1992), 141–146. Zbl0779.11027MR1162938
  9. D. G. Champernowne, The Construction of Decimals Normal in the Scale of Ten. Journal of the London Mathematical Society 8 (1933), 254–260. Zbl0007.33701
  10. R. Crandall, C. Pomerance, Prime Numbers: A Computational Perspective. Springer-Verlag, New York, 2002. Zbl0995.11072MR2156291
  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. Zbl0938.11039MR1628840
  13. P. Erdős, On Arithmetical Properties of Lambert Series. Journal of the Indian Mathematical Society (N.S.) 12 (1948), 63–66. Zbl0032.01701MR29405
  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. Zbl0574.10045MR803155
  16. H. Halberstam, H.-E. Richert, Sieve Methods. Academic Press, London, 1974. Zbl0298.10026MR424730
  17. G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers. Oxford University Press, 1979. Zbl0020.29201MR568909
  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. Zbl0086.26202MR4860
  19. Aubrey J. Kempner, On Transcendental Numbers Transactions of the American Mathematical Society 17 (1916), 476–482. MR1501054
  20. M. J. Knight, An ‘Ocean of Zeroes’ Proof That a Certain Non-Liouville Number is Transcendental. American Mathematical Monthly 98 (1991), 947–949. Zbl0743.11034MR1137543
  21. L. Kuipers, H. Niederreiter, Uniform Distribution of Sequences. Wiley-Interscience, New York, 1974. Zbl0281.10001MR419394
  22. J. Lagarias, On the Normality of Fundamental Constants. Experimental Mathematics 10, no. 3 (2001), 353–366. MR1917424
  23. E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Bd. II, 2nd ed. New York: Chelsea, 1953, 641–669. Zbl0051.28007
  24. S. Lehr, Sums and rational multiples of q -automatic sequences are q -automatic. Theor. Comp. Sci. 108 (1993) 385–391. Zbl0768.11013MR1202029
  25. S. Lehr, J. Shallit, J. Tromp, On the vector space of the automatic reals. Theoretical Computer Science 163 (1996), 193–210. Zbl0874.11029MR1407021
  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. Zbl0519.10022MR732180
  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. Zbl0339.10028MR452125
  28. G. Martin, Absolutely Abnormal Numbers. American Mathematical Monthly 108 no. 8 (2001), 746–754. Zbl1036.11035MR1865662
  29. W. Miller, Transcendence measures by a method of Mahler. Journal of the Australian Mathematical Society (Series A) 32 (1982), 68–78. Zbl0482.10036MR643431
  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] Zbl0898.11031MR1422383
  31. I. Niven, Irrational Numbers. Carus Mathematical Monographs, no. 11, Wiley, New York, 1956. Zbl0070.27101MR80123
  32. P. Ribenboim, The New Book of Prime Number Records. Springer-Verlag, New York, 1996. Zbl0856.11001MR1377060
  33. K. Roth, Rational Approximations to Algebraic Numbers. Mathematika 2 (1955), 1–20. Corrigendum, pp. 168. Zbl0064.28501MR72182
  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. Zbl0797.11007MR1239914

NotesEmbed ?

top

You must be logged in to post comments.