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

$\lambda =\underset{0}{\overset{1}{\int }}{e}^{\mathrm{li}(x)}dx=\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{\mathrm{Ei}(-x)-x}dx=0,6243299885\dots$   (Vorlage:OEIS),

wobei $\mathrm{li}$ der Integrallogarithmus und $\mathrm{Ei}$ die Integralexponentialfunktion sind.

Vorkommen

Zyklen in Permutationen

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

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

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

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

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

$x{\rho }^{\prime }(x)+\rho (x-1)=0\text{für}x>1$

mit $\rho (x)=1\text{für}x\le 1$.

Primfaktoren

Bezeichnet $f(n)$ den größten Primfaktor einer zufälligen natürlichen Zahl $n\le N$, dann gilt

$\underset{N\to \mathrm{\infty }}{\lim }\mathrm{P}(f(n)\le n^x)=\rho \left(\frac{1}{x}\right)$

für $0<x\le 1$ mit der Dickman-Funktion $\rho$. Hieraus folgt

$\underset{N\to \mathrm{\infty }}{\lim }\mathrm{E}\left[\frac{\ln (f(n))}{\ln (n)}\right]=\underset{0}{\overset{1}{\int }}xd\rho \left(\frac{1}{x}\right)=\lambda$.

Die Konstante $\lambda$ gibt demnach auch den asymptotischen Erwartungswert der relativen Anzahl der Ziffern des größten Primfaktors einer natürlichen Zahl an. 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.

Literatur

• Vorlage:Literatur

Weblinks

• Vorlage:MathWorld