(Non)Automaticity of number theoretic functions

Michael Coons[1]

  • [1] University of Waterloo Department of Pure Mathematics 200 University Avenue West Waterloo, Ontario N2L 3G1, Canada

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

  • Volume: 22, Issue: 2, page 339-352
  • ISSN: 1246-7405

Abstract

top
Denote by λ ( n ) Liouville’s function concerning the parity of the number of prime divisors of n . Using a theorem of Allouche, Mendès France, and Peyrière and many classical results from the theory of the distribution of prime numbers, we prove that λ ( n ) is not k –automatic for any k > 2 . This yields that ∑ n = 1 ∞ λ ( n ) X n ∈ 𝔽 p [ [ X ] ] is transcendental over 𝔽 p ( X ) for any prime p > 2 . Similar results are proven (or reproven) for many common number–theoretic functions, including ϕ , μ , Ω , ω , ρ , and others.

How to cite

top

Coons, Michael. "(Non)Automaticity of number theoretic functions." Journal de Théorie des Nombres de Bordeaux 22.2 (2010): 339-352. <http://eudml.org/doc/116406>.

@article{Coons2010,
abstract = {Denote by $\lambda (n)$ Liouville’s function concerning the parity of the number of prime divisors of $n$. Using a theorem of Allouche, Mendès France, and Peyrière and many classical results from the theory of the distribution of prime numbers, we prove that $\lambda (n)$ is not $k$–automatic for any $k&gt; 2$. This yields that $\sum _\{n=1\}^\infty \lambda (n) X^n\in \mathbb\{F\}_p[[X]]$ is transcendental over $\mathbb\{F\}_p(X)$ for any prime $p&gt;2$. Similar results are proven (or reproven) for many common number–theoretic functions, including $\varphi $, $\mu $, $\Omega $, $\omega $, $\rho $, and others.},
affiliation = {University of Waterloo Department of Pure Mathematics 200 University Avenue West Waterloo, Ontario N2L 3G1, Canada},
author = {Coons, Michael},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {arithmetic functions; automaticity},
language = {eng},
number = {2},
pages = {339-352},
publisher = {Université Bordeaux 1},
title = {(Non)Automaticity of number theoretic functions},
url = {http://eudml.org/doc/116406},
volume = {22},
year = {2010},
}

TY - JOUR
AU - Coons, Michael
TI - (Non)Automaticity of number theoretic functions
JO - Journal de Théorie des Nombres de Bordeaux
PY - 2010
PB - Université Bordeaux 1
VL - 22
IS - 2
SP - 339
EP - 352
AB - Denote by $\lambda (n)$ Liouville’s function concerning the parity of the number of prime divisors of $n$. Using a theorem of Allouche, Mendès France, and Peyrière and many classical results from the theory of the distribution of prime numbers, we prove that $\lambda (n)$ is not $k$–automatic for any $k&gt; 2$. This yields that $\sum _{n=1}^\infty \lambda (n) X^n\in \mathbb{F}_p[[X]]$ is transcendental over $\mathbb{F}_p(X)$ for any prime $p&gt;2$. Similar results are proven (or reproven) for many common number–theoretic functions, including $\varphi $, $\mu $, $\Omega $, $\omega $, $\rho $, and others.
LA - eng
KW - arithmetic functions; automaticity
UR - http://eudml.org/doc/116406
ER -

References

top
  1. B. Adamczewski and Y. Bugeaud, On the complexity of algebraic numbers. I. Expansions in integer bases. Ann. of Math. (2) 165 (2007), no. 2, 547–565. Zbl1195.11094MR2299740
  2. J.-P. Allouche, Note on the transcendence of a generating function. New trends in probability and statistics. Vol. 4 (Palanga, 1996), VSP, Utrecht, 1997, pp. 461–465. Zbl0932.11017MR1653629
  3. J.-P. Allouche, Transcendence of formal power series with rational coefficients. Theoret. Comput. Sci. 218 (1999), no. 1, 143–160, WORDS (Rouen, 1997). Zbl0916.68123MR1687784
  4. J.-P. Allouche and H. Cohen, Dirichlet series and curious infinite products. Bull. London Math. Soc. 17 (1985), no. 6, 531–538. Zbl0577.10036MR813734
  5. J.-P. Allouche, M. Mendès France, and J. Peyrière, Automatic Dirichlet series. J. Number Theory 81 (2000), no. 2, 359–373. Zbl0971.11006MR1752260
  6. J.-P. Allouche and J. Shallit, Automatic sequences. Cambridge University Press, Cambridge, 2003. Zbl1086.11015MR1997038
  7. W. D. Banks, F. Luca, and I. E. Shparlinski, Irrationality of power series for various number theoretic functions. Manuscripta Math. 117 (2005), no. 2, 183–197. Zbl1072.11002MR2150480
  8. P. Borwein and M. Coons, Transcendence of power series for some number theoretic functions. Proc. Amer. Math. Soc. 137 (2009), no. 4, 1303–1305. Zbl1236.11063MR2465652
  9. F. Carlson, Über Potenzreihen mit ganzzahligen Koeffizienten. Math. Zeitschr. (1921), no. 9, 1–13. Zbl48.1208.02MR1544447
  10. G. Christol, Ensembles presque périodiques k -reconnaissables. Theoret. Comput. Sci. 9 (1979), no. 1, 141–145. Zbl0402.68044MR535129
  11. A. Cobham, Uniform tag sequences. Math. Systems Theory 6 (1972), 164–192. Zbl0253.02029MR457011
  12. J. B. Conrey, More than two fifths of the zeros of the Riemann zeta function are on the critical line. J. Reine Angew. Math. 399 (1989), 1–26. Zbl0668.10044MR1004130
  13. Ch.-J. de la Vallée Poussin, Recherches analytiques de la théorie des nombres premiers. Ann. Soc. Scient. Bruxelles 20 (1896), 183–256. 
  14. P. Fatou, Séries trigonométriques et séries de Taylor. Acta Math. (1906), no. 30, 335–400. Zbl37.0283.01MR1555035
  15. J. Hadamard, Sur la distribution des zéros de la fonction ζ ( s ) et ses conséquences arithmétiques. Bull. Soc. Math. France 24 (1896), 199–220. Zbl27.0154.01MR1504264
  16. J. Hartmanis and H. Shank, On the recognition of primes by automata. J. Assoc. Comput. Mach. 15 (1968), 382–389. Zbl0164.05201MR235916
  17. E. Landau and A. Walfisz, Über die Nichtfortsetzbarkeit einiger durch Dirichletsche Reihen definierter Funktionen. Palermo Rend. (1920), no. 44, 82–86. Zbl47.0287.02
  18. K. Mahler, Arithmetische Eigenschaften der Lösungen einer Klasse von Funktionalgleichungen. Math. Ann. 101 (1929), no. 1, 342–366. Zbl55.0115.01MR1512537
  19. M. Minsky and S. Papert, Unrecognizable sets of numbers. J. Assoc. Comput. Mach. 13 (1966), 281–286. Zbl0166.00601MR207481
  20. K. Nishioka, Mahler functions and transcendence. Lecture Notes in Mathematics, vol. 1631, Springer-Verlag, Berlin, 1996. Zbl0876.11034MR1439966
  21. R. W. Ritchie, Finite automata and the set of squares. J. Assoc. Comput. Mach. 10 (1963), 528–531. Zbl0118.12601MR167374
  22. A. Selberg, On the zeros of Riemann’s zeta-function. Skr. Norske Vid. Akad. Oslo I. 1942 (1942), no. 10, 59 pp. Zbl0028.11101MR10712
  23. J. Shallit, Automaticity IV: Sequences, sets, and diversity. J. Théor. Nombres Bordeaux 8 (1996), no. 2, 347–367. Zbl0876.11010MR1438474
  24. E. C. Titchmarsh, The theory of the Riemann zeta-function. second ed., The Clarendon Press Oxford University Press, New York, 1986, Edited and with a preface by D. R. Heath-Brown. Zbl0601.10026MR882550
  25. H. von Mangoldt, Zu Riemanns Abhandlung über die Anzahle der Primzahlen unter einer gegebenen Grösse. J. Reine Angew. Math. 144 (1895), 255–305. 
  26. S. Yazdani, Multiplicative functions and k -automatic sequences. J. Théor. Nombres Bordeaux 13 (2001), no. 2, 651–658. Zbl1002.11025MR1879677

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.