Constante de Golomb–Dickman

Soit a_n l'espérance — prise sur l'ensemble des permutations d'un ensemble de taille n — de la longueur du plus grand cycle de chaque permutation. La constante de Golomb-Dickman est définie par

${\displaystyle \lambda =\lim _{n\to \infty }{\frac {a_{n}}{n}}.}$

En termes probabilistes, ${\displaystyle n\lambda }$ est asymptotiquement l'espérance de la longueur du plus grand cycle d'une permutation de ${\displaystyle {\mathcal {S}}_{n}}$ uniformément distribuée.

En théorie des nombres, la constante de Golomb–Dickman apparaît dans la taille moyenne des plus grands diviseurs premiers d'un entier. Plus précisément,

${\displaystyle \lambda =\lim _{n\to \infty }{\frac {1}{n}}\sum _{k=2}^{n}{\frac {\ln(P_{1}(k))}{\ln(k)}},}$

où ${\displaystyle P_{1}(k)}$ est le plus grand facteur premier de k, ce qui signifie que le nombre de chiffres en base n de ${\displaystyle P_{1}(n)}$ converge en moyenne de Cesàro vers ${\displaystyle \lambda }$. Donc si n est un entier à d chiffres dans une base donnée, alors ${\displaystyle \lambda d}$ est en moyenne le nombre de chiffres dans cette base du plus grand facteur premier de n.

La constante de Golomb–Dickman apparaît aussi dans le problème arithmétique suivant : quelle est la probabilité que le deuxième facteur premier de n soit plus petit que la racine du premier ? Asymptotiquement, cette probabilité vaut ${\displaystyle \lambda }$ :

${\displaystyle \lambda =\lim _{n\to \infty }{\text{Prob}}\left\{P_{2}(n)\leqslant {\sqrt {P_{1}(n)}}\right\}}$

où ${\displaystyle P_{2}(n)}$ est le deuxième plus grand facteur premier de n.

Enfin, la constante apparaît lorsque l'on s'intéresse à la longueur moyenne du plus grand cycle de toute fonction d'un ensemble fini dans lui-même. Si X est un ensemble fini, on applique successivement la fonction f : X → X à n'importe quel élément x de cet ensemble, cela forme un cycle, montrant que pour un certain k ${\displaystyle f^{n+k}(x)=f^{n}(x)}$ pour n assez grand; le plus petit k respectant cette propriété est la longueur du cycle. Soit b_n la moyenne prise sur l'ensemble des fonctions d'un ensemble de taille n dans lui-même, de la taille du plus grand cycle. Purdom et Williams[2] ont montré que

${\displaystyle \lim _{n\to \infty }{\frac {b_{n}}{\sqrt {n}}}={\sqrt {\frac {\pi }{2}}}\lambda .}$

Il existe plusieurs expression de ${\displaystyle \lambda }$. En particulier :

${\displaystyle \lambda =\int _{0}^{1}e^{\mathrm {Li} (t)}\,dt}$

où ${\displaystyle \mathrm {Li} (t)}$ est la fonction logarithme intégral,

${\displaystyle \lambda =\int _{0}^{\infty }e^{-t-E_{1}(t)}\,dt}$

où ${\displaystyle E_{1}(t)}$ est la fonction exponentielle intégrale, et

${\displaystyle \lambda =\int _{0}^{\infty }{\frac {\rho (t)}{t+2}}\,dt}$

et

${\displaystyle \lambda =\int _{0}^{\infty }{\frac {\rho (t)}{(t+1)^{2}}}\,dt}$

où ${\displaystyle \rho (t)}$ est la fonction de Dickman.

• Permutations aléatoires
• Combinatoire analytique

• (en) Eric W. Weisstein, « Golomb-Dickman Constant », sur MathWorld
• suite A084945 de l'OEIS, décimale de la constante de Golomb-Dickman
• Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, 284–286 (ISBN 0-521-81805-2, lire en ligne)

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Golomb–Dickman constant » (voir la liste des auteurs).