Golomb-Dickman-Konstante

Die Golomb-Dickman-Konstante i​st eine mathematische Konstante a​us der Kombinatorik u​nd Zahlentheorie. Sie stellt einerseits d​en asymptotischen Erwartungswert d​er relativen Länge d​es längsten Zyklus e​iner zufälligen Permutation dar, andererseits g​ibt sie d​en asymptotischen Erwartungswert d​er relativen Anzahl d​er Ziffern d​es größten Primfaktors e​iner natürlichen Zahl an. Die Konstante i​st nach d​em US-amerikanischen Mathematiker Solomon W. Golomb u​nd dem schwedischen Aktuar Karl Dickman benannt, d​ie sie unabhängig voneinander entdeckten.

Definition

Die Golomb-Dickman-Konstante i​st definiert als

${\displaystyle \lambda =\int _{0}^{1}e^{\operatorname {li} (x)}~dx=\int _{0}^{\infty }e^{\operatorname {Ei} (-x)-x}~dx=0{,}6243299885\ldots }$   (Folge A084945 in OEIS),

wobei ${\displaystyle \operatorname {li} }$ der Integrallogarithmus und ${\displaystyle \operatorname {Ei} }$ die Integralexponentialfunktion sind.[1][2]

Vorkommen

Zyklen in Permutationen

Bezeichnet ${\displaystyle \alpha _{i}(\pi )}$ die Anzahl der disjunkten Zyklen der Länge ${\displaystyle i}$ einer Permutation ${\displaystyle \pi }$, dann ist

${\displaystyle M(\pi )=\max\{i\in \mathbb {N} \mid \alpha _{i}(\pi )>0\}}$

die Länge des längsten Zyklus von ${\displaystyle \pi }$. Für den Erwartungswert der relativen Länge des längsten Zyklus einer (gleichverteilt) zufälligen Permutation der Länge ${\displaystyle n}$ gilt asymptotisch[1]

${\displaystyle \lim _{n\to \infty }\operatorname {E} \left[{\frac {M(\pi )}{n}}\right]=1-\int _{1}^{\infty }{\frac {\rho (x)}{x^{2}}}~dx=\lambda }$.

Hierbei ist die Dickman-Funktion ${\displaystyle \rho }$ die eindeutige stetige Lösung der Delay-Differentialgleichung

${\displaystyle x\rho '(x)+\rho (x-1)=0~{\text{für}}~x>1}$

mit ${\displaystyle \rho (x)=1~{\text{für}}~x\leq 1}$.[3]

Primfaktoren

Bezeichnet ${\displaystyle f(n)}$ den größten Primfaktor einer zufälligen natürlichen Zahl ${\displaystyle n\leq N}$, dann gilt[1][4]

${\displaystyle \lim _{N\to \infty }\operatorname {P} (f(n)\leq n^{x})=\rho \left({\tfrac {1}{x}}\right)}$

für ${\displaystyle 0<x\leq 1}$ mit der Dickman-Funktion ${\displaystyle \rho }$. Hieraus folgt

${\displaystyle \lim _{N\to \infty }\operatorname {E} \left[{\frac {\ln(f(n))}{\ln(n)}}\right]=\int _{0}^{1}x~d\rho \left({\tfrac {1}{x}}\right)=\lambda }$.

Die Konstante ${\displaystyle \lambda }$ gibt demnach auch den asymptotischen Erwartungswert der relativen Anzahl der Ziffern des größten Primfaktors einer natürlichen Zahl an.[5] Allgemein entspricht sogar die gesamte Verteilung der Anzahl der Ziffern der Primfaktoren einer natürlichen Zahl asymptotisch der Verteilung der Längen der Zyklen einer zufälligen Permutation.[1]

Literatur

• Steven R. Finch: Mathematical Constants. Cambridge University Press, 2003, ISBN 978-0-521-81805-6.

Einzelnachweise

1. Steven R. Finch: Mathematical Constants. Cambridge University Press, 2003, S. 284–292.
2. Larry A. Shepp, Stuart P. Lloyd: Ordered cycle lengths in a random permutation. In: Trans. Amer. Math. Soc. Nr. 121, 1966, S. 350–557.
3. Solomon W. Golomb: Random permutations. In: Bull. Amer. Math. Soc. Nr. 70, 1964, S. 747.
4. Karl Dickman: On the frequency of numbers containing prime factors of a certain relative magnitude. In: Arkiv för Mat., Astron. och Fys. 22A, 1930, S. 1–14.
5. Donald E. Knuth, Luis Trabb Pardo: Analysis of a simple factorization algorithm. In: Theor. Comput. Sci. Nr. 3, 1976, S. 321–348.

Weblinks

• Eric W. Weisstein: Golomb-Dickman Constant. In: MathWorld (englisch).