Landau’s function for one million billions
Journal de théorie des nombres de Bordeaux, Volume 20 (2008) no. 3, pp. 625-671.

Let ${𝔖}_{n}$ denote the symmetric group with $n$ letters, and $g\left(n\right)$ the maximal order of an element of ${𝔖}_{n}$. If the standard factorization of $M$ into primes is $M={q}_{1}^{{\alpha }_{1}}{q}_{2}^{{\alpha }_{2}}...{q}_{k}^{{\alpha }_{k}}$, we define $\ell \left(M\right)$ to be ${q}_{1}^{{\alpha }_{1}}+{q}_{2}^{{\alpha }_{2}}+...+{q}_{k}^{{\alpha }_{k}}$; one century ago, E. Landau proved that $g\left(n\right)={max}_{\ell \left(M\right)\le n}M$ and that, when $n$ goes to infinity, $logg\left(n\right)\sim \sqrt{nlog\left(n\right)}$.

There exists a basic algorithm to compute $g\left(n\right)$ for $1\le n\le N$; its running time is $𝒪\left({N}^{3/2}/\sqrt{logN}\right)$ and the needed memory is $𝒪\left(N\right)$; it allows computing $g\left(n\right)$ up to, say, one million. We describe an algorithm to calculate $g\left(n\right)$ 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 \left(n\right)={\sum }_{d\phantom{\rule{0.166667em}{0ex}}|\phantom{\rule{0.166667em}{0ex}}n}1$.

Soit ${𝔖}_{n}$ le groupe symétrique sur $n$ lettres et $g\left(n\right)$ l’ordre maximal d’un élément de ${𝔖}_{n}$. Si la factorisation en nombres premiers de $M$ est $M={q}_{1}^{{\alpha }_{1}}{q}_{2}^{{\alpha }_{2}}...{q}_{k}^{{\alpha }_{k}}$, nous définissons $\ell \left(M\right)$ comme étant ${q}_{1}^{{\alpha }_{1}}+{q}_{2}^{{\alpha }_{2}}+...+{q}_{k}^{{\alpha }_{k}}$ ; il y a un siècle, E. Landau a montré que $g\left(n\right)={max}_{\ell \left(M\right)\le n}M$ et que, quand $n$ tend vers l’infini, $logg\left(n\right)\sim \sqrt{nlog\left(n\right)}$.

Il existe un algorithme élémentaire pour calculer $g\left(n\right)$ pour $1\le n\le N$ ; son temps d’exécution est en $𝒪\left({N}^{3/2}/\sqrt{logN}\right)$ et la place mémoire nécessaire est en $𝒪\left(N\right)$ ; cela permet de calculer $g\left(n\right)$ jusqu’à, disons, un million. Nous donnons un algorithme pour calculer $g\left(n\right)$ pour $n$ jusqu’à ${10}^{15}$. L’idée principale est de considérer les nombres dits $\ell$-superchampions. Des nombres similaires, les nombres hautement composés supérieurs, ont été introduits par S. Ramanujan pour étudier les grandes valeurs de la fonction nombre de diviseurs $\tau \left(n\right)={\sum }_{d\phantom{\rule{0.166667em}{0ex}}|\phantom{\rule{0.166667em}{0ex}}n}1$.

DOI: 10.5802/jtnb.644
Keywords: Arithmetical function, symmetric group, maximal order, highly composite number.
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.
@article{JTNB_2008__20_3_625_0,
author = {Marc Del\'eglise and Jean-Louis Nicolas and Paul Zimmermann},
title = {Landau{\textquoteright}s function for one million billions},
journal = {Journal de th\'eorie des nombres de Bordeaux},
pages = {625--671},
publisher = {Universit\'e Bordeaux 1},
volume = {20},
number = {3},
year = {2008},
doi = {10.5802/jtnb.644},
mrnumber = {2523311},
language = {en},
url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.644/}
}
TY  - JOUR
AU  - Marc Deléglise
AU  - Jean-Louis Nicolas
AU  - Paul Zimmermann
TI  - Landau’s function for one million billions
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2008
SP  - 625
EP  - 671
VL  - 20
IS  - 3
PB  - Université Bordeaux 1
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.644/
UR  - https://www.ams.org/mathscinet-getitem?mr=2523311
UR  - https://doi.org/10.5802/jtnb.644
DO  - 10.5802/jtnb.644
LA  - en
ID  - JTNB_2008__20_3_625_0
ER  - 
%0 Journal Article
%A Marc Deléglise
%A Jean-Louis Nicolas
%A Paul Zimmermann
%T Landau’s function for one million billions
%J Journal de théorie des nombres de Bordeaux
%D 2008
%P 625-671
%V 20
%N 3
%I Université Bordeaux 1
%U https://doi.org/10.5802/jtnb.644
%R 10.5802/jtnb.644
%G en
%F JTNB_2008__20_3_625_0
Marc Deléglise; Jean-Louis Nicolas; Paul Zimmermann. Landau’s function for one million billions. Journal de théorie des nombres de Bordeaux, Volume 20 (2008) no. 3, pp. 625-671. doi : 10.5802/jtnb.644. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.644/

[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 \left(x\right)$: the Meissel, Lehmer, Lagarias, Miller, Odlyzko method. Math. Comp. 65 (1996), 235–245. | MR | Zbl

[4] H. Cramér, On the order of magnitude of the difference between consecutive prime numbers. Acta Arithmetica 2 (1936), 23–46. | Zbl

[5] P. Dusart, The ${k}^{\text{th}}$ prime is greater than $k\left(logk+loglogk-1\right)$ for $k\ge 2$. Math. Comp. 68 (1999), 411–415. | MR | Zbl

[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 | Zbl

[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

[8] J. Grantham, The largest prime dividing the maximal order of an element of ${S}_{n}$. Math. Comp. 64 (1995), 407–410. | MR | Zbl

[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.

[10] G. Levitt and J.-L. Nicolas, On the Maximum Order of Torsion Elements in $GL\left(n,ℤ\right)$ and $\text{Aut}\left({F}_{n}\right)$. Journal of Algebra 208 (1998), 630–642. | MR | Zbl

[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. | Numdam | MR | Zbl

[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. | MR | Zbl

[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 | Zbl

[14] W. Miller, The Maximal Order of an Element of a Finite Symmetric Group. Amer. Math. Monthly 94 (1987), 497–506. | MR

[15] F. Morain, Table de $g\left(n\right)$ 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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

[21] J.-L. Nicolas, On Landau’s function $g\left(n\right)$. 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 | Zbl

[22] J.-L. Nicolas, Comparaison des ordres maximaux dans les groupes ${S}_{n}$ et $GL\left(n,ℤ\right)$. Acta Arithmetica 96 (2000), 175–203. | MR | Zbl

[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

[25] S. Ramanujan, Highly composite numbers, annotated by J.-L. Nicolas and G. Robin. The Ramanujan J. 1 (1997), 119–153. | MR | Zbl

[26] H. Riesel, Prime Numbers and Computer Methods for Factorization. Birkhäuser, 1985. | MR | Zbl

[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. | Numdam | MR | Zbl

[28] J. B. Rosser and L. Schoenfeld, Approximate Formulas for Some Functions of Prime Numbers. Illinois. J. Math 6 (1962), 64–94. | MR | Zbl

[29] S. M. Shah, An inequality for the arithmetical function $g\left(x\right)$. J. Indian Math. Soc. 3 (1939), 316–318. | MR

[30] M. Szalay, On the maximal order in ${S}_{n}$ and ${S}_{n}^{*}$. Acta Arithmetica 37 (1980), 321–331. | MR | Zbl

[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 | Zbl

Cited by Sources: