Golomb–Dickman constant

In mathematics, the Golomb–Dickman constant arises in the theory of random permutations and in number theory. Its value is

$\lambda =0.62432998854355087099293638310083724\dots$ (sequence A084945 in the OEIS)

It is not known whether this constant is rational or irrational.

Definitions

Let a_n be the average — taken over all permutations of a set of size n — of the length of the longest cycle in each permutation. Then the Golomb–Dickman constant is

$\lambda =\underset{n\to \mathrm{\infty }}{\lim }\frac{a_n}{n}.$

In the language of probability theory, $\lambda n$ is asymptotically the expected length of the longest cycle in a uniformly distributed random permutation of a set of size n.

In number theory, the Golomb–Dickman constant appears in connection with the average size of the largest prime factor of an integer. More precisely,

$\lambda =\underset{n\to \mathrm{\infty }}{\lim }\frac{1}{n}\sum _{k=2}^n\frac{\log (P_1(k))}{\log (k)},$

where $P_1(k)$ is the largest prime factor of k (sequence A006530 in the OEIS) . So if k is a d digit integer, then $\lambda d$ is the asymptotic average number of digits of the largest prime factor of k.

The Golomb–Dickman constant appears in number theory in a different way. What is the probability that second largest prime factor of n is smaller than the square root of the largest prime factor of n? Asymptotically, this probability is $\lambda$. More precisely,

$\lambda =\underset{n\to \mathrm{\infty }}{\lim }\text{Prob}\{P_2(n)\le \sqrt{P_1(n)}\}$

where $P_2(n)$ is the second largest prime factor n.

The Golomb-Dickman constant also arises when we consider the average length of the largest cycle of any function from a finite set to itself. If X is a finite set, if we repeatedly apply a function f: X → X to any element x of this set, it eventually enters a cycle, meaning that for some k we have $f^{n+k}(x)=f^n(x)$ for sufficiently large n; the smallest k with this property is the length of the cycle. Let b_n be the average, taken over all functions from a set of size n to itself, of the length of the largest cycle. Then Purdom and Williams proved that

$\underset{n\to \mathrm{\infty }}{\lim }\frac{b_n}{\sqrt{n}}=\sqrt{\frac{\pi }{2}}\lambda .$

Formulae

There are several expressions for $\lambda$. These include:

$\lambda =\underset{0}{\overset{1}{\int }}{e}^{\mathrm{L}\mathrm{i}(t)}dt$

where $\mathrm{L}\mathrm{i}(t)$ is the logarithmic integral,

$\lambda =\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-t-E_1(t)}dt$

where $E_1(t)$ is the exponential integral, and

$\lambda =\underset{0}{\overset{\mathrm{\infty }}{\int }}\frac{\rho (t)}{t+2}dt$

and

$\lambda =\underset{0}{\overset{\mathrm{\infty }}{\int }}\frac{\rho (t)}{(t+1{)}^2}dt$

where $\rho (t)$ is the Dickman function.

See also

• Random permutation
• Random permutation statistics

External links

• Weisstein, Eric W.. "Golomb-Dickman Constant". http://mathworld.wolfram.com/Golomb-DickmanConstant.html. 
• OEIS sequence A084945 (Decimal expansion of Golomb-Dickman constant)
• Finch, Steven R. (2003). Mathematical Constants. Cambridge University Press. pp. 284–286. ISBN 0-521-81805-2. https://archive.org/details/mathematicalcons0000finc.