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.

Here’s one of the many cute facts about random permutations. 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 in Sections 3.10-3.12 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:

0 Comments & 0 Trackbacks

Post a New Comment