Golomb-Dickman Constant

N.B. A detailed on-line essay by S. Finch was the starting point for this entry.

Let $\Pi$ be a Permutation of $n$ elements, and let $\alpha_i$ be the number of Cycles of length $i$ in this Permutation. Picking $\Pi$ at Random gives

$$\left\langle{\,\sum_{j=1}^\infty \alpha_j}\right\rangle{} = ... ... {1\over i} = \ln n+\gamma+{\mathcal O}\left({1\over n}\right)$$ (1)

$$\mathop{\rm var}\nolimits \left({\,\sum_{j=1}^\infty \alpha_... ...\textstyle{1\over 6}}\pi^2+{\mathcal O}\left({1\over n}\right)$$ (2)

$$\lim_{n\to\infty} P(\alpha_1=0)={1\over e}$$ (3)

(Shepp and Lloyd 1966, Wilf 1990). Goncharov (1942) showed that

$$\lim_{n\to\infty} P(\alpha_j=k)={1\over k!}e^{-1/j}j^{-k},$$ (4)

which is a Poisson Distribution, and

$$\lim_{n\to\infty} P\left[{\left({\,\sum_{j=1}^\infty \alpha_j-\ln n}\right)(\ln n)^{-1/2}\leq x}\right]=\Phi(x),$$ (5)

which is a Normal Distribution, $\gamma$ is the Euler-Mascheroni Constant, and $\Phi$ is the Normal Distribution Function. Let

$$M(\alpha) \equiv \max_{1\leq j<\infty} \alpha_j$$ (6)

$$m(\alpha) \equiv \min_{1\leq j<\infty} \alpha_j.$$ (7)

Golomb (1959) derived

$$\lambda\equiv\lim_{n\to\infty} {\left\langle{M(\alpha)}\right\rangle{}\over n}=0.6243299885\ldots,$$ (8)

which is known as the Golomb Constant or Golomb-Dickman constant. Knuth (1981) asked for the constants $b$ and $c$ such that

$$\lim_{n\to\infty} n^b[\left\langle{M(\alpha)}\right\rangle{}-\lambda n-{\textstyle{1\over 2}}\lambda]=c,$$ (9)

and Gourdon (1996) showed that

$$\left\langle{M(\alpha)}\right\rangle{}=\lambda(n+{\textstyle... ...e{1\over 6}} j^{1+2n}+{\textstyle{1\over 6}}j^{2+n}\over n^3},$$ (10)

where

$$j\equiv e^{2\pi i/3}.$$ (11)

$\lambda$ can be expressed in terms of the function $f(x)$ defined by $f(x)=1$ for $1\leq x\leq 2$ and

$${df\over dx}=-{f(x-1)\over x-1}$$ (12)

for $x>2$, by

$$\lambda=\int_1^\infty {f(x)\over x^2}\,dx.$$ (13)

Shepp and Lloyd (1966) derived

$$\lambda = \int_0^\infty \mathop{\rm exp}\nolimits \left({-x-\int_x^\infty {e^{-y}\over y}\, dy}\right)$$

$$= \int_0^1 \mathop{\rm exp}\nolimits \left({\,\int_0^x {dy\over \ln y}}\right)\,dx.$$ (14)

Mitchell (1968) computed $\lambda$ to 53 decimal places.

Surprisingly enough, there is a connection between $\lambda$ and Prime Factorization (Knuth and Pardo 1976, Knuth 1981, pp. 367-368, 395, and 611). Dickman (1930) investigated the probability $P(x,n)$ that the largest Prime Factor $p$ of a random Integer between 1 and $n$ satisfies $p<n^x$ for $x\in(0,1)$. He found that

$$F(x)\equiv \lim_{n\to\infty} P(x,n) =\cases{ 1 & if $x\geq ... ...^x F\left({t\over 1-t}\right){dt\over t} & if $0\leq x<1$.\cr}$$ (15)

Dickman then found the average value of $x$ such that $p=n^x$, obtaining

$$\mu \equiv \lim_{n\to\infty} \left\langle{x}\right\rangle{}=\lim_{n\to\infty} \left\langle{\ln p\over\ln n}\right\rangle{}=\int_0^1 x{dF\over dx}\,dx$$

$$= \int_0^1 F\left({1\over 1-t}\right)\,dt=0.62432999,$$ (16)

which is $\lambda$.

References

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/golomb/golomb.html

Gourdon, X. 1996. http://www.mathsoft.com/asolve/constant/golomb/gourdon.html.

Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1973.

Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1981.

Knuth, D. E. and Pardo, L. T. ``Analysis of a Simple Factorization Algorithm.'' Theor. Comput. Sci. 3, 321-348, 1976.

Mitchell, W. C. ``An Evaluation of Golomb's Constant.'' Math. Comput. 22, 411-415, 1968.

Purdom, P. W. and Williams, J. H. ``Cycle Length in a Random Function.'' Trans. Amer. Math. Soc. 133, 547-551, 1968.

Shepp, L. A. and Lloyd, S. P. ``Ordered Cycle Lengths in Random Permutation.'' Trans. Amer. Math. Soc. 121, 350-557, 1966.

Wilf, H. S. Generatingfunctionology, 2nd ed. New York: Academic Press, 1993.