Golomb-Dickman constant

The Golomb-Dickman constant is a mathematical constant from combinatorics and number theory . On the one hand it represents the asymptotic expected value of the relative length of the longest cycle of a random permutation , on the other hand it gives the asymptotic expected value of the relative number of digits of the largest prime factor of a natural number . The constant is named after the US mathematician Solomon W. Golomb and the Swedish actuary Karl Dickman , who discovered it independently of each other.

definition

The Golomb-Dickman constant is defined as

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

where are the logarithm of integral and the integral exponential function . ${\displaystyle \operatorname {li} }$ ${\displaystyle \operatorname {Ei} }$

Occurrence

Cycles in permutations

Denotes the number of disjoint cycles of the length of a permutation , then is ${\displaystyle \alpha _{i}(\pi )}$ ${\displaystyle i}$ ${\displaystyle \pi }$

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

the length of the longest cycle of . For the expected value of the relative length of the longest cycle of a ( uniformly distributed ) random permutation of the length, the following applies asymptotically ${\displaystyle \pi }$ ${\displaystyle n}$

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

Here the Dickman function is the unambiguous, continuous solution of the delay differential equation ${\displaystyle \rho }$

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

with . ${\displaystyle \rho (x)=1~{\text{für}}~x\leq 1}$

Prime factors

Denotes the largest prime factor of a random natural number , then applies ${\displaystyle f(n)}$ ${\displaystyle n\leq N}$

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

for with the Dickman function . It follows from this ${\displaystyle 0<x\leq 1}$ ${\displaystyle \rho }$

${\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 }$.

The constant therefore also indicates the asymptotic expected value of the relative number of digits of the largest prime factor of a natural number. In general, even the total distribution of the number of digits of the prime factors of a natural number corresponds asymptotically to the distribution of the lengths of the cycles of a random permutation. ${\displaystyle \lambda }$

literature

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

Individual evidence

1. ^ ^{A b c d} Steven R. Finch : Mathematical Constants . Cambridge University Press, 2003, pp. 284-292 .
2. ^ Larry A. Shepp , Stuart P. Lloyd : Ordered cycle lengths in a random permutation . In: Trans. Amer. Math. Soc. No. 121 , 1966, pp. 350-557 .
3. ^ Solomon W. Golomb : Random permutations . In: Bull. Amer. Math. Soc. No. 70 , 1964, pp. 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, p. 1-14 .
5. ^ Donald E. Knuth , Luis Trabb Pardo: Analysis of a simple factorization algorithm . In: Theor. Comput. Sci. No. 3 , 1976, p. 321-348 .

Web links

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