The Golomb-Dickman Constant

November 23, 2019

Posted by John Baez

$MathML-enabled post (click for more details).$

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.

$MathML-enabled post (click for more details).$

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}}$

Posted at November 23, 2019 12:11 AM UTC

TrackBack URL for this Entry: https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3159

7 Comments & 0 Trackbacks

Re: The Golomb–Dickman Constant

$MathML-enabled post (click for more details).$

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?

Posted by: Tobias Fritz on November 23, 2019 12:47 AM | Permalink | Reply to this

Re: The Golomb–Dickman Constant

$MathML-enabled post (click for more details).$

I think the answer to your second question is “no”.

Take the length of the longest cycle of the permutation $\sigma \in S_n$ and divide it by $n$ . This gives a function on $S_n$ , which we can think of as a random variable $L_n$ if we give each permutation the same probability of occurring. Clearly

$0 \le L_n \le 1$

As $n \to \infty$ , the cumulative probability

$P(0 \le L_n \le \alpha)$

approaches $\rho(1/\alpha)$ where $\rho$ is the Dickman function:

So, as $n \to \infty$ the probability that the longest cycle has length $\le n/10$ becomes quite small, less than $10^{-10}$ , but it approaches a constant value!

The Golomb-Dickman constant is thus given by some integral connected to the Dickman function.

I don’t understand this stuff deeply: I’m just reading it off Equation 3.10.3 in the paper by Lagarias. He says this fact was discovered by Knuth and Trabb-Pardo in 1976, though Goncharov got an equivalent formula for $P(0 \le L_n \le \alpha)$ in 1944.

By the way, this paper by Lagarias is packed with fun facts a.e..

Posted by: John Baez on November 23, 2019 1:30 AM | Permalink | Reply to this

Re: The Golomb–Dickman Constant

$MathML-enabled post (click for more details).$

Fascinating, thanks!

Posted by: Tobias Fritz on November 23, 2019 3:11 AM | Permalink | Reply to this

Re: The Golomb–Dickman Constant

$MathML-enabled post (click for more details).$

In regard to your first question:

For a random permutation, if you pick an element at random, the length of the cycle it belongs to is uniformly distributed from $1$ to $n$ . That’s enough to show that the longest cycle grows like $n$ .

For a random self-map, think “birthday paradox”. (Incidentally, this is the same idea that powers Pollard’s rho algorithm for factoring moderately large integers.)

Posted by: Austin on February 22, 2020 8:15 PM | Permalink | Reply to this

Re: The Golomb-Dickman Constant

$MathML-enabled post (click for more details).$

Extremely qualitative comment: I’d guess that a random permutation should be a hard-sphere “gas of cycles,” with a strong excluded-volume effect due to the cycles not intersecting.

Posted by: Blake Stacey on November 26, 2019 12:54 AM | Permalink | Reply to this

Re: The Golomb-Dickman Constant

$MathML-enabled post (click for more details).$

Yes.

But when I made that gas analogy I imagined that there would be lots of cycles of all sizes… sort of like molecules in a gas. Now I realize that a random permutation of a huge set is likely to contain a ‘giant cycle’ containing more than half the elements — not with probability approaching 1, but with probablity approaching about 69.3%. The rest of the set will probably contain its own giant cycle, and so on. So I’m vaguely thinking about some sort of scaling analysis, renormalization group stuff. Very vaguely, so far.

Posted by: John Baez on November 26, 2019 1:46 AM | Permalink | Reply to this

Re: The Golomb-Dickman Constant

$MathML-enabled post (click for more details).$

Yes, that kind of behavior would have me mumbling something about scaling and critical points. The other vague thought on my mind is that maybe a cycle of length $\gt k$ can somehow be regarded as a connected Feynman diagram, so that exponentiating the generating function can be an instance of the linked-cluster theorem.

Posted by: Blake Stacey on November 26, 2019 2:58 AM | Permalink | Reply to this

The n-Category Café

Skip to the Main Content

November 23, 2019