### The Golomb-Dickman Constant

#### Posted by John Baez

I’m falling in love with random permutations. There’s something both simple and fairly deep about them. I like to visualize a random permutation as a “gas of cycles”, governed by the laws of statistical mechanics. I haven’t gotten very with this analogy yet. But I’m learning a lot of fun stuff.

Here’s one of the many cute facts about random permutations — not the simplest, but not the most complicated.

Let $a_n$ be the average length of the longest cycle in a permutation, averaged over all permutations of an $n$-element set. Then $a_n$ is asymptotically equal to $\lambda n$ where

$\lambda \approx 0.6243299885 \dots$

is called the Golomb–Dickman constant. There’s a cool formula for this constant: $\lambda = \int_0^1 e^{\mathrm{Li}(x)} dx \; \; where \; \; Li(x) = \int_0^x \frac{dt}{\ln t}$ But nobody has been able to prove that it’s irrational!

The Golomb–Dickman constant also shows up in number theory… in a very similar way! If you randomly choose a huge $n$-digit integer, the average number of digits of its largest prime factor is asymptotic to $\lambda n$.

So, there’s a connection between prime factorizations and random permutations! And this fact is both simpler and more interesting to me than the Golomb–Dickman constant. You can read more about this here:

- Jeffrey Lagarias, Euler’s constant: Euler’s work and modern developments, Sections 3.10-3.12

The Golomb–Dickman constant is a kind of relative of Euler’s constant, though there’s no known formula expressing one in terms of the other.

Here’s another appearance of this constant. Say you randomly choose a function from a huge $n$-element set to itself. Then the average length of its longest periodic orbit is asymptotic to

$\lambda \; \sqrt{\frac{\pi n}{2}}$

## Re: The Golomb–Dickman Constant

Neat! Is there a simple way to see that the average length of the longest periodic orbit grows like $n$ for a random permutation, but only like $\sqrt{n}$ for a random self-map?

And is there concentration of measure, in the sense that “average length” actually means almost surely close to that length in both cases?