Search the site

Marc Deléglise; Jean-Louis Nicolas; Paul Zimmermann
Landau’s function for one million billions
Journal de théorie des nombres de Bordeaux, 20 no. 3 (2008), p. 625-671, doi: 10.5802/jtnb.644
Article PDF | Reviews MR 2523311 | Zbl pre05572695
Keywords: Arithmetical function, symmetric group, maximal order, highly composite number.

Résumé - 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$.

Bibliography

[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.
[3] M. Deléglise and J. Rivat, Computing $\pi (x)$: the Meissel, Lehmer, Lagarias, Miller, Odlyzko method. Math. Comp. 65 (1996), 235–245.  MR 1322888 |  Zbl 0869.11068
[4] H. Cramér, On the order of magnitude of the difference between consecutive prime numbers. Acta Arithmetica 2 (1936), 23–46. Article |  Zbl 0015.19702
[5] P. Dusart, The $k^{\text{th}}$ prime is greater than $k(\log k+\log \log k -1)$ for $k\ge 2$. Math. Comp. 68 (1999), 411–415.  MR 1620223 |  Zbl 0913.11039
[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.  MR 232833 |  Zbl 0235.20004
[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.  Zbl 0606.10037
[8] J. Grantham, The largest prime dividing the maximal order of an element of $S_n$. Math. Comp. 64 (1995), 407–410.  MR 1270619 |  Zbl 0824.11059
[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.  JFM 34.0233.02
[10] G. Levitt and J.-L. Nicolas, On the Maximum Order of Torsion Elements in $GL(n,\mathbb{Z})$ and $\text{Aut}(F_n)$. Journal of Algebra 208 (1998), 630–642.  MR 1655470 |  Zbl 0930.11070
[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. Cedram |  MR 799599 |  Zbl 0574.10043
[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. Article |  MR 960551 |  Zbl 0588.10049
[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.  MR 979940 |  Zbl 0675.10028
[14] W. Miller, The Maximal Order of an Element of a Finite Symmetric Group. Amer. Math. Monthly 94 (1987), 497–506.  MR 935414
[15] F. Morain, Table de $g(n)$ pour $1\le n\le 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.  MR 230803 |  Zbl 0179.34804
[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. Numdam |  MR 254130 |  Zbl 0184.07202
[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. Numdam |  MR 253514 |  Zbl 0186.30202
[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.  MR 938967 |  Zbl 0651.10029
[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 no 13 (1997), 228–240.  MR 1425188 |  Zbl 0869.11077
[22] J.-L. Nicolas, Comparaison des ordres maximaux dans les groupes $S_n$ et $GL(n,\mathbb{Z})$. Acta Arithmetica 96 (2000), 175–203.  MR 1814452 |  Zbl 1016.11043
[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.  MR 2280858 |  JFM 45.0286.02
[25] S. Ramanujan, Highly composite numbers, annotated by J.-L. Nicolas and G. Robin. The Ramanujan J. 1 (1997), 119–153.  MR 1606180 |  Zbl 0917.11043
[26] H. Riesel, Prime Numbers and Computer Methods for Factorization. Birkhäuser, 1985.  MR 897531 |  Zbl 0582.10001
[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.  MR 743888 |  Zbl 0531.10012
[28] J. B. Rosser and L. Schoenfeld, Approximate Formulas for Some Functions of Prime Numbers. Illinois. J. Math 6 (1962), 64–94. Article |  MR 137689 |  Zbl 0122.05001
[29] S. M. Shah, An inequality for the arithmetical function $g(x)$. J. Indian Math. Soc. 3 (1939), 316–318.  MR 1236 |  JFM 65.1153.01
[30] M. Szalay, On the maximal order in $S_n$ and $S_n^*$. Acta Arithmetica 37 (1980), 321–331. Article |  MR 598884 |  Zbl 0443.10029
[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.  MR 423893 |  Zbl 0293.68062