Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

November 23, 2019

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 na_n be the average length of the longest cycle in a permutation, averaged over all permutations of an nn-element set. Then a na_n is asymptotically equal to λn\lambda n where

λ0.6243299885 \lambda \approx 0.6243299885 \dots

is called the Golomb–Dickman constant. There’s a cool formula for this constant: λ= 0 1e Li(x)dxwhereLi(x)= 0 xdtlnt \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 nn-digit integer, the average number of digits of its largest prime factor is asymptotic to λn\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:

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 nn-element set to itself. Then the average length of its longest periodic orbit is asymptotic to

λπn2 \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

Neat! Is there a simple way to see that the average length of the longest periodic orbit grows like nn for a random permutation, but only like n\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

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

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

0L n1 0 \le L_n \le 1

As nn \to \infty, the cumulative probability

P(0L nα) P(0 \le L_n \le \alpha)

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

So, as nn \to \infty the probability that the longest cycle has length n/10\le n/10 becomes quite small, less than 10 1010^{-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(0L nα) 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

Fascinating, thanks!

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

Re: The Golomb–Dickman Constant

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 11 to nn. That’s enough to show that the longest cycle grows like nn.

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

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

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

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 >k\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

Post a New Comment