Un gros sous-groupe cyclique de $\mathfrak S_n$

Renart

Une question m'est venue en assistant à un oral de l'agrégation l'autre jour. Elle me semblait intéressante donc je vous la partage en espérant qu'elle vous intéresse aussi.

Notons $g(n)$ l'ordre maximal des éléments de $\mathfrak S_n$. Ma question est la suivante : quel est le comportement de $g(n)$ lorsque $n$ tend vers l'infini ? Je précise un petit peu : puisque $g$ va croitre extrêmement vite et qu'on ne peut pas vraiment espérer une formule "close" on cherchera simplement un équivalent de $\ln\big(g(n)\big)$ en $+\infty$.

Après recherches (merci à l'OEIS !) ce problème n'est pas nouveau, la fonction $g$ est appelée fonction de Landau qui a démontré en 1903 que

$\ln\big(g(n)\big) \sim \sqrt{n\ln(n)}$

J'arrive presque à redémontrer le résultat de Landau mais il y a un petit quelque chose qui manque, un argument heuristique que je ne sais pas trop transformer en preuve rigoureuse. Je posterai mes arguments d'ici quelques jours le temps de laisser chercher de leur côté ceux que ça intéresse.

Poirot

La fonction est bien connue en théorie analytique des nombres. Son estimation précise revient à statuer sur l'hypothèse de Riemann...

Ce n'est pas bien étonnant puisqu'on se retrouve rapidement à devoir estimer un certain PPCM.

Renart

Salut Poirot

Effectivement, j'ai lu sur Wikipédia en faisant mes recherches qu'une certaine majoration de $g(n)$ par une certaine fonction faisant intervenir $\mathrm{Li}(n)$ revenait à démontrer l'hypothèse de Riemann. Mais (heureusement !) l'équivalent trouvé par Landau se démontre sans recourir à cette hypothèse.
Ceci étant dit dans ma démonstration j'utilise un résultat plus faible : le théorème des nombres premiers. C'est sans doute quelque chose de connu quand on fait de la théorie des nombres mais n'étant pas familier du tout avec cette partie des mathématiques j'étais agréablement surpris de voir apparaitre le théorème des nombres premiers dans une question de sous-groupes cycliques de $\mathfrak S_n$

Math Coss

Un petit accès de tout-est-dans-toutisme ?
(Je plaisante mais je trouve cela remarquable aussi...)

Renart

Ça n'a pas l'air de passionner les foules 🙃

Bon je rédige quand même, comme promis, ce que j'avais trouvé.

Remarques préliminaires :
Soit $\sigma$ un élément de $S_n$, il se décompose en produit de cycles à supports disjoints et l'ordre de $\sigma$ est alors le ppmc des longueurs de ces cycles. Ainsi $g(n)$ est le maximum des ppmc des partitions de $n$, autrement dit on veut maximiser $\mathrm{ppmc}(n_1,\ldots,n_k)$ sous la contrainte $n_1+\ldots+n_k \leq n$. Première remarque, si $n_i$ et $n_j$ ont un facteur commun $q$ alors on ne change pas l'ordre de $\sigma$ en les remplaçant par $n_i/q$ et $n_j$, on peut donc se restreindre au cas où les $n_i$ sont premiers deux à deux. Deuxième remarque : si $n_i$ s'écrit $ab$ avec $a$ et $b$ des entiers premiers entre eux et supérieurs à $2$ alors on ne change pas le ppmc en remplaçant $n_i$ par $n_i' = a$ et $n_i'' = b$ et on a bien $n_i'+n_i'' \leq n_i$. Ainsi on peut supposer que les $n_i$ sont de la forme $p_i^{k_i}$ où les $p_i$ sont des nombres premiers tous distincts.

Minoration de $g(n)$ :
Pour minorer $g(n)$ il suffit de donner un élément $\sigma$ ayant un ordre assez grand. Vu ce qui précède on peut par exemple essayer avec un produit de cycles à supports disjoints d'ordre respectifs $2,3,5,7,\ldots, p_k$ où $p_k$ désigne le $k$-ième nombre premier et où l'on prendra $k$ le plus grand entier tel que $\sum_{i=1}^k p_i \leq n$. On aura alors
\[\ln(g(n)) \geq \ln(\mathrm{ppmc}(p_1,\ldots,p_k)) = \sum_{i=1}^k \ln(p_i).\]
D'après le théorème des nombres premiers on sait que $p_i = \varphi_i i \ln(i)$ avec  $\lim \varphi_i = 1$. On a donc

\[ \sum_{i=1}^k \ln(p_i) = \sum_{i=1}^k \ln(i) + \ln(\ln(i)) + \ln(\varphi_i) \]

et une comparaison somme-intégrale nous montre que ceci est équivalent à $k \ln(k)$, reste maintenant à déterminer jusqu'où sommer ou, autrement dit, un équivalent pour $k$ (qui dépend de $n$). Pour cela il faut estimer

\[   \sum_{i=1}^j p_i =  \sum_{i=1}^j \varphi_i i \ln(i) \]

et une nouvelle comparaison somme-intégrale nous donne $\frac{j^2}{2} \ln(j)$ comme équivalent ou encore $\frac J 2 \ln(\sqrt{J}) \sim \frac J 4 \ln(J)$ en posant $J= \sqrt{j}$. On cherche donc à résoudre l'équation $J\ln(J) = 4 n \Leftrightarrow Je^J = \exp(4n)$ d'inconnue $J$, ce qui nous donne $J= W(\exp(4n))$ où $W$ est la fonction de Lambert. D'après les propriétés de $W$ on a $W(\exp(4n)) = \frac{4n}{W(4n)} \sim \frac {4n}{\ln(n)}$ ou encore $j \sim \frac{2 \sqrt n}{\sqrt {\ln(n)}} $. On vérifie qu'on a bien le droit de composer les équivalents que l'on compose et on retrouve \[k \ln (k)  \sim \frac{2 \sqrt n}{\sqrt {\ln(n)}} \ln \left( \frac{2 \sqrt n}{\sqrt {\ln(n)}}\right)  \sim \sqrt {n \ln(n)}\]

ce qui est justement ce qu'on voulait.

Majoration de $g(n)$ :
C'est là que ça coince... On peut commencer par dire que $g(n)$ est une suite croissante et, toujours par des manipulations d'équivalents, on a $\sqrt{u_k \ln(u_k)} \sim \sqrt{u_{k+1} \ln(u_{k+1})} $ où $u_k = \sum_{i=1}^k p_i$. Si l'on arrivait à démontrer que $\ln(g(u_k)) = \sum_{i=1}^k \ln(p_i)$ cela terminerait alors la démonstration. Intuitivement c'est assez raisonnable : pour faire augmenter l'ordre de $\sigma$ sous la contrainte $n_1+\ldots + n_k\leq n$ il est plus avantageux de rajouter de nouveaux nombres premiers dans les $n_i$ que d'augmenter la puissance d'un nombre premier déjà présent. C'est en tout cas une propriété vérifiée pour les premières ($\leq 6$) valeurs de $k$. Malheureusement cela ne constitue pas une démonstration et, même d'un point de vue heuristique, ce n'est pas très convaincant.