Golomb-Dickman-Konstante

Die Golomb-Dickman-Konstante ist eine mathematische Konstante aus der Kombinatorik und Zahlentheorie. Sie stellt einerseits den asymptotischen Erwartungswert der relativen Länge des längsten Zyklus einer zufälligen Permutation dar, andererseits gibt sie den asymptotischen Erwartungswert der relativen Anzahl der Ziffern des größten Primfaktors einer natürlichen Zahl an. Die Konstante ist nach dem US-amerikanischen Mathematiker Solomon W. Golomb und dem schwedischen Aktuar Karl Dickman benannt, die sie unabhängig voneinander entdeckten.

Definition

Die Golomb-Dickman-Konstante ist definiert als

λ = ∫ 0 1 e li ⁡ ( x )   d x = ∫ 0 ∞ e Ei ⁡ ( − x ) − x   d x = 0,624 3299885 … {\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 li {\displaystyle \operatorname {li} } der Integrallogarithmus und Ei {\displaystyle \operatorname {Ei} } die Integralexponentialfunktion sind.[1][2]

Vorkommen

Zyklen in Permutationen

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

M ( π ) = max { i ∈ N ∣ α i ( π ) > 0 } {\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 n {\displaystyle n} gilt asymptotisch[1]

lim n → ∞ E ⁡ [ M ( π ) n ] = 1 − ∫ 1 ∞ ρ ( x ) x 2   d x = λ {\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

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

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

Primfaktoren

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

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

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

lim N → ∞ E ⁡ [ ln ⁡ ( f ( n ) ) ln ⁡ ( n ) ] = ∫ 0 1 x   d ρ ( 1 x ) = λ {\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. ↑ a b c d 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