Landau’s function for one million billions

Marc Deléglise[1]; Jean-Louis Nicolas[1]; Paul Zimmermann[2]

  • [1] Université de Lyon, Université de Lyon 1, CNRS, Institut Camille Jordan, Bât. Doyen Jean Braconnier, 21 Avenue Claude Bernard, F-69622 Villeurbanne cedex, France.
  • [2] Centre de Recherche INRIA Nancy Grand Est Projet CACAO -bâtiment A 615 rue du Jardin Botanique, F-54602 Villers-lès-Nancy cedex, France.

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

  • Volume: 20, Issue: 3, page 625-671
  • ISSN: 1246-7405

Abstract

top
Let 𝔖 n denote the symmetric group with n letters, and g ( n ) the maximal order of an element of 𝔖 n . If the standard factorization of M into primes is M = q 1 α 1 q 2 α 2 ... q k α k , we define ℓ ( M ) to be q 1 α 1 + q 2 α 2 + ... + q k α k ; one century ago, E. Landau proved that g ( n ) = max ℓ ( M ) ≤ n M and that, when n goes to infinity, log g ( n ) ∼ n log ( n ) .There exists a basic algorithm to compute g ( n ) for 1 ≤ n ≤ N ; its running time is 𝒪 N 3 / 2 / log N and the needed memory is 𝒪 ( N ) ; it allows computing g ( n ) up to, say, one million. We describe an algorithm to calculate g ( n ) for n up to 10 15 . The main idea is to use the so-called ℓ -superchampion numbers. Similar numbers, the superior highly composite numbers, were introduced by S. Ramanujan to study large values of the divisor function τ ( n ) = ∑ d | n 1 .

How to cite

top

Deléglise, Marc, Nicolas, Jean-Louis, and Zimmermann, Paul. "Landau’s function for one million billions." Journal de Théorie des Nombres de Bordeaux 20.3 (2008): 625-671. <http://eudml.org/doc/10854>.

@article{Deléglise2008,
abstract = {Let $\{\mathfrak\{S\}\}_n$ denote the symmetric group with $n$ letters, and $g(n)$ the maximal order of an element of $\{\mathfrak\{S\}\}_n$. If the standard factorization of $M$ into primes is $M=q_1^\{\alpha _1\}q_2^\{\alpha _2\}\ldots q_k^\{\alpha _k\}$, we define $\ell (M)$ to be $q_1^\{\alpha _1\}+q_2^\{\alpha _2\}+\ldots +q_k^\{\alpha _k\}$; one century ago, E. Landau proved that $g(n)=\max _\{\ell (M)\le n\} M$ and that, when $n$ goes to infinity, $\log g(n) \sim \sqrt\{n\log (n)\}$.There exists a basic algorithm to compute $g(n)$ for $1 \le n \le N$; its running time is $\mathcal\{O\}\left(N^\{3/2\}/\sqrt\{\log N\}\right)$ and the needed memory is $\mathcal\{O\}(N)$; it allows computing $g(n)$ up to, say, one million. We describe an algorithm to calculate $g(n)$ for $n$ up to $10^\{15\}$. The main idea is to use the so-called $\ell $-superchampion numbers. Similar numbers, the superior highly composite numbers, were introduced by S. Ramanujan to study large values of the divisor function $\tau (n)=\sum _\{d\,|\,n\} 1$.},
affiliation = {Université de Lyon, Université de Lyon 1, CNRS, Institut Camille Jordan, Bât. Doyen Jean Braconnier, 21 Avenue Claude Bernard, F-69622 Villeurbanne cedex, France.; Université de Lyon, Université de Lyon 1, CNRS, Institut Camille Jordan, Bât. Doyen Jean Braconnier, 21 Avenue Claude Bernard, F-69622 Villeurbanne cedex, France.; Centre de Recherche INRIA Nancy Grand Est Projet CACAO -bâtiment A 615 rue du Jardin Botanique, F-54602 Villers-lès-Nancy cedex, France.},
author = {Deléglise, Marc, Nicolas, Jean-Louis, Zimmermann, Paul},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {Arithmetical function; symmetric group; maximal order; highly composite number; arithmetical function; highly composite function; Landau's function},
language = {eng},
number = {3},
pages = {625-671},
publisher = {Université Bordeaux 1},
title = {Landau’s function for one million billions},
url = {http://eudml.org/doc/10854},
volume = {20},
year = {2008},
}

TY - JOUR
AU - Deléglise, Marc
AU - Nicolas, Jean-Louis
AU - Zimmermann, Paul
TI - Landau’s function for one million billions
JO - Journal de Théorie des Nombres de Bordeaux
PY - 2008
PB - Université Bordeaux 1
VL - 20
IS - 3
SP - 625
EP - 671
AB - Let ${\mathfrak{S}}_n$ denote the symmetric group with $n$ letters, and $g(n)$ the maximal order of an element of ${\mathfrak{S}}_n$. If the standard factorization of $M$ into primes is $M=q_1^{\alpha _1}q_2^{\alpha _2}\ldots q_k^{\alpha _k}$, we define $\ell (M)$ to be $q_1^{\alpha _1}+q_2^{\alpha _2}+\ldots +q_k^{\alpha _k}$; one century ago, E. Landau proved that $g(n)=\max _{\ell (M)\le n} M$ and that, when $n$ goes to infinity, $\log g(n) \sim \sqrt{n\log (n)}$.There exists a basic algorithm to compute $g(n)$ for $1 \le n \le N$; its running time is $\mathcal{O}\left(N^{3/2}/\sqrt{\log N}\right)$ and the needed memory is $\mathcal{O}(N)$; it allows computing $g(n)$ up to, say, one million. We describe an algorithm to calculate $g(n)$ for $n$ up to $10^{15}$. The main idea is to use the so-called $\ell $-superchampion numbers. Similar numbers, the superior highly composite numbers, were introduced by S. Ramanujan to study large values of the divisor function $\tau (n)=\sum _{d\,|\,n} 1$.
LA - eng
KW - Arithmetical function; symmetric group; maximal order; highly composite number; arithmetical function; highly composite function; Landau's function
UR - http://eudml.org/doc/10854
ER -

References

top
  1. E. Bach, Sums over Primes. Conference on Algorithmic Number Theory, Turku, May 8-11, 2007. 
  2. E. Bach and J. Sorenson, Computing prime harmonic sums. Submitted to Math. Comp. Zbl1204.11184
  3. M. Deléglise and J. Rivat, Computing π ( x ) : the Meissel, Lehmer, Lagarias, Miller, Odlyzko method. Math. Comp. 65 (1996), 235–245. Zbl0869.11068MR1322888
  4. H. Cramér, On the order of magnitude of the difference between consecutive prime numbers. Acta Arithmetica 2 (1936), 23–46. Zbl0015.19702
  5. P. Dusart, The k th prime is greater than k ( log k + log log k - 1 ) for k ≥ 2 . Math. Comp. 68 (1999), 411–415. Zbl0913.11039MR1620223
  6. P. Erdős and P. Turán, On some problems of a statistical group theory, IV. Acta Math. Acad. Sci. Hungar. 19 (1968), 413–435. Zbl0235.20004MR232833
  7. H. Gerlach, Über die Elemente einer Menge verallgemeinerter ganzer Zahlen, die klein sind bezüglich einer auf dieser Menge definierten reellwertigen Abbildung. Thesis of the University of Kaiserslautern, 1986. Zbl0606.10037
  8. J. Grantham, The largest prime dividing the maximal order of an element of S n . Math. Comp. 64 (1995), 407–410. Zbl0824.11059MR1270619
  9. E. Landau, Über die Maximalordnung der Permutationen gegebenen Grades. Archiv. der Math. und Phys., Sér 3, 5 (1903), 92–103. Handbuch der Lehre von der Verteilung der Primzahlen, I, 2nd ed, Chelsea, New-York, 1953, 222–229. Zbl34.0233.02
  10. G. Levitt and J.-L. Nicolas, On the Maximum Order of Torsion Elements in G L ( n , ℤ ) and Aut ( F n ) . Journal of Algebra 208 (1998), 630–642. Zbl0930.11070MR1655470
  11. J.-P. Massias, Majoration explicite de l’ordre maximum d’un élément du groupe symétrique. Ann. Fac. Sci. Toulouse Math. 6 (1984), 269–280. Zbl0574.10043MR799599
  12. J.-P. Massias, J.-L. Nicolas et G. Robin. Évaluation asymptotique de l’ordre maximum d’un élément du groupe symétrique. Acta Arithmetica 50 (1988), 221–242. Zbl0588.10049MR960551
  13. J.-P. Massias, J.-L. Nicolas and G. Robin, Effective Bounds for the Maximal Order of an Element in the Symmetric Group. Math. Comp. 53 (1989), 665–678. Zbl0675.10028MR979940
  14. W. Miller, The Maximal Order of an Element of a Finite Symmetric Group. Amer. Math. Monthly 94 (1987), 497–506. Zbl1191.11027MR935414
  15. F. Morain, Table de g ( n ) pour 1 ≤ n ≤ 32000 . Internal document, INRIA, 1988. 
  16. T. R. Nicely, http://www.trnicely.net/gaps/gaplist.html 
  17. J.-L. Nicolas, Sur l’ordre maximum d’un élément dans le groupe S n des permutations. Acta Arithmetica 14 (1968), 315–332. Zbl0179.34804MR230803
  18. J.-L. Nicolas, Ordre maximal d’un élément du groupe des permutations et highly composite numbers. Bull. Soc. Math. France 97 (1969), 129–191. Zbl0184.07202MR254130
  19. J.-L. Nicolas, Calcul de l’ordre maximum d’un élément du groupe symétrique S n . Rev. Française Informat. Recherche Opérationnelle, Sér. R-2 3 (1969), 43–50. Zbl0186.30202MR253514
  20. J.-L. Nicolas, On highly composite numbers.Ramanujan revisited, edited by G. E. Andrews, R. A. Askey, B. C. Berndt, K. G. Ramanathan, R. A. Rankin, Academic Press, 1988, 216–244. Zbl0651.10029MR938967
  21. J.-L. Nicolas, On Landau’s function g ( n ) . The Mathematics of Paul Erdős, vol. I, R. L. Graham and J. Nešetřil editors, Springer Verlag, Algorithms and Combinatorics no13 (1997), 228–240. Zbl0869.11077MR1425188
  22. J.-L. Nicolas, Comparaison des ordres maximaux dans les groupes S n et G L ( n , ℤ ) . Acta Arithmetica 96 (2000), 175–203. Zbl1016.11043MR1814452
  23. J.-L. Nicolas and N. Zakic, Champion numbers for the number of representations as a sum of six squares. In preparation. 
  24. S. Ramanujan, Highly composite numbers. Proc. London Math. Soc. Serie 2, 14 (1915), 347–409. Collected papers, Cambridge University Press, 1927, 78–128. Zbl45.1248.01MR2280858
  25. S. Ramanujan, Highly composite numbers, annotated by J.-L. Nicolas and G. Robin. The Ramanujan J. 1 (1997), 119–153. Zbl0917.11043MR1606180
  26. H. Riesel, Prime Numbers and Computer Methods for Factorization. Birkhäuser, 1985. Zbl0582.10001MR897531
  27. G. Robin, Méthodes d’optimisation pour un problème de théorie des nombres. R.A.I.R.O. Informatique Théorique 17 (1983), 239–247. Zbl0531.10012MR743888
  28. J. B. Rosser and L. Schoenfeld, Approximate Formulas for Some Functions of Prime Numbers. Illinois. J. Math 6 (1962), 64–94. Zbl0122.05001MR137689
  29. S. M. Shah, An inequality for the arithmetical function g ( x ) . J. Indian Math. Soc. 3 (1939), 316–318. Zbl0022.31004MR1236
  30. M. Szalay, On the maximal order in S n and S n * . Acta Arithmetica 37 (1980), 321–331. Zbl0443.10029MR598884
  31. P. M. B. Vitányi, On the size of DOL languages. Lecture Notes in Computer Science, vol. 15, Springer-Verlag, 1974, 78–92 and 327–338. Zbl0293.68062MR423893

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.