The n-Category Café

By the way, here’s a fun thing I covered in my class.

There’s a species $End$ where $End(X)$ is the set of endomorphisms of a finite set $X$. There’s a species $Perm$ where $Perm(X)$ is the set of permutations of $X$. And there’s a species $Tree$ where $Tree(X)$ is the set of rooted trees with $X$ as vertices.

We can compose species, and we have

$$End \cong Perm \circ Tree$$

This says an endomorphism of $X$ is a way of chopping $X$ into parts, putting a permutation on the set of parts, and putting a rooted tree structure on each part. This expresses how as we repeatedly apply the endomorphism to the elements of $X$, they flow down to the roots of trees, and from then on they get permuted.

Indeed there’s a species $Cyc$ where $Cyc(X)$ is the set of cyclic orderings of $X$ and a species $Exp$ where $Exp(X)$ is the one-element set, and we have

$$Perm \cong Exp \circ Cyc$$

Combining these facts we get

$$End \cong Exp \circ \Cyc \circ Tree$$

This expresses how an endofunction is a disjoint union of ‘connected components’, each of which consists of a cycle and trees rooted at each point of the cycle.

I would like to use this to solve your question.

I suspect your initial guess was right.

To recap: given an endofunction $f$ of a finite set $X$, put

$$\im^\infty(f) = \bigcap_{n \geq 0} f^n X.$$

(I called it $X_f$ before.) For $n \geq 1$, let $a_n$ denote the expected cardinality of $\im^\infty(f)$ for a random endofunction $f$ of an $n$-element set. You more or less conjectured that

$$\frac{a_n}{\sqrt{n}} \to \frac{1}{\lambda\sqrt{\pi/2}} = 1.27594\ldots$$

as $n \to \infty$, where $\lambda$ is the Golomb-Dickman constant. I believe that’s correct.

My argument is a combination of mathematical argument and computer experiment. Here goes.

For the mathematical part, I’ll want some terminology. Let $f$ be an endofunction of a finite set $X$. I mentioned before that $f$ restricts to a permutation of $\im^\infty(f)$. I’ll call this the permutation induced by $f$, and I’ll call $\im^\infty(f)$ the eventual image of $f$.

Given $1 \leq k \leq n$ and a permutation $\sigma$ of $\{1, \ldots, k\}$, how many endofunctions of $\{1, \ldots, n\}$ have $\sigma$ as their induced permutation? By what we know about the structure of endofunctions on a finite set, the answer is actually independent of $\sigma$. It’s the number $T_{n, k}$ of rooted forests with vertex-set $\{1, \ldots, n\}$ and with $\{1, \ldots, k\}$ as the set of roots.

Cayley’s formula easily implies that $T_{n, k} = k n^{n - k - 1}$. At least, so says Wikipedia, though I didn’t check.

So, given $1 \leq k \leq n$ and a prescribed permutation $\sigma$ of $\{1, \ldots, k\}$, the number of endofunctions of $\{1, \ldots, n\}$ whose induced permutation is $\sigma$ is $k n^{n - k - 1}$.

Since there are $k!$ permutations of $\{1, \ldots, k\}$, the number of endofunctions of $\{1, \ldots, n\}$ with eventual image $\{1, \ldots, k\}$ is $k! \cdot k n^{n - k - 1}$.

Of course, the same is true for any other $k$-element subset of $\{1, \ldots, n\}$. So, the number of endofunctions of $\{1, \ldots, n\}$ whose eventual image has cardinality $k$ is

$$\binom{n}{k} k! \cdot k n^{n - k - 1} = \frac{n! k n^{n - k - 1}}{(n - k)!}.$$

This is true for all $1 \leq k \leq n$.

There are $n^n$ endofunctions of $\{1, \ldots, n\}$. So, choosing one uniformly at random, the expected cardinality of its eventual image is

$$\frac{1}{n^n} \sum_{k = 1}^n \frac{n! k n^{n - k - 1}}{(n - k)!} \cdot k = \sum_{k = 1}^n \frac{k^2 (n - 1)!}{n^k (n - k)!}.$$

That expected cardinality is, by definition, $a_n$. So we’ve shown that

$$a_n = \sum_{k = 1}^n \frac{k^2 (n - 1)!}{n^k (n - k)!}.$$

I was feeling too tired/stupid to attempt to find a closed formula for $a_n$, or to try to figure out its asymptotics without the aid of a closed formula. So instead I just put some values of $n$ into sage.

What came out suggested that, as you predicted, $a_n$ grows like $\sqrt{n}$. And so I made a table showing $a_n$ and $a_n/\sqrt{n}$ for various values of $n$:

   n          a_n          a_n/sqrt(n)

    1    1.000000000000  1.00000000000000
    2    1.500000000000  1.06066017177982
    3    1.888888888889  1.09055050846929
    4    2.218750000000  1.10937500000000
    5    2.510400000000  1.12268501014309
   10    3.660215680000  1.15746182762620
  100   12.209960630216  1.22099606302160
 1000   39.303212926178  1.24287672209294
10000  124.999121868081  1.24999121868081
20000  176.912788799720  1.25096232638906

It looks as if $a_n/\sqrt{n}$ is converging. What to? Well, you mentioned the constant $\lambda\sqrt{\pi/2}$, whose reciprocal is $1.27594\ldots$. The numerical data above makes it plausible that this is the limit of $a_n/\sqrt{n}$. And if so, that’s the conjectured result.

Wow, Tom! You did what I wanted to do, but without explicitly talking about species — just sort of diving in there and thinking about all the ways you could flesh out a permutation of a subset of $\{1,\dots, n\}$ to an endofunction on all of $\{1,\dots, n\}$. Great!

Now the fun part is studying the asymptotic behavior of your sum

$$a_n = \sum_{k = 1}^n \frac{k^2 (n-1)!}{n^k (n-k)!}$$

as $n \to \infty$.

If you look at Theorem 3.12.1 in Lagarias’ paper, which is about random endofunctions, you’ll notice the proof contains the identity

$$\sum_{k = 1}^n \frac{k (n-1)!}{n^k (n-k)!} = 1$$

(after a trivial change of variables). This is not exactly your sum, since it contains a $k$ in the numerator instead of a $k^2$. And of course your sum is growing as $n$ increases. But they’re scarily similar!

By the way, this proof is even more concerned with showing that

$$\sum_{k = 1}^n \frac{ln(k)\,(n-1)!}{n^k (n-k)!} \; \sim \; \frac{1}{2} \ln n$$

as $n \to \infty$.

So, I suspect that these folks — Lagarias, and the people whose work he’s discussing — could also handle the asymptotics of

$$a_n = \sum_{k = 1}^n \frac{k^2 (n-1)!}{n^k (n-k)!}$$

as $n \to \infty$. Whether we can is another matter.

By the way, I strongly believe that

$$a_n = \sum_{k = 1}^n \frac{k^2 (n-1)!}{n^k (n-k)!} \sim c \sqrt{n}$$

but I’m not convinced yet that the constant $c$ is

$$\frac{1}{\lambda \sqrt{\pi/2}}$$

In his discussion of random endofunctions, Lagarias refers to this paper:

• Paul W. Purdom and J. H. Williams, Cycle length in a random function, Transactions of the American Mathematical Society 133 (1968), 547-551.

They compute the $m$th moment of this random variable: the length of the $i$th longest cycle of a randomly chosen endofunction on an $n$-element set, asymptotically as $n \to \infty$.

On page 549 they define a function

$$Q_n(k) = \sum_{j=1}^n \frac{(n-1)! j^k}{(n-j)! n^j}$$

I’m going to stick with their names for variables so I don’t get confused, but your $a_n$ is their $Q_n(2)$.

On page 550 they say

$$Q_n(2) = n Q_n(0)$$

They also give an exact formula for $Q_n(0)$ in terms of a special function called the incomplete gamma function, and also a simpler asymptotic formula good for $n \to \infty$:

$$Q_n(0) \sim \sqrt{\pi / 2n}$$

Their formula says more — it includes lower-order terms — but it implies this.

Putting all this together we get

$$a_n \sim c \sqrt{n}$$

where

$$c = \sqrt{\pi / 2} \approx 1.25331413732 \dots$$

This matches your computer calculations quite nicely. The Golomb–Dickman constant $\lambda$ is a red herring here!

So, for those who haven’t been following carefully, we’ve proved this:

Theorem. Let $a_n$ be the expected number of periodic points for a randomly chosen endofunction of an $n$-element set. Then

$$a_n \sim \sqrt{\frac{\pi n}{2}}$$

as $n \to \infty$.

By the way, this gives an extremely impractical but pretty way to compute $\pi$, sort of like Buffon’s needle but using random endofunctions.

I figured this result on the size of the eventual image was unlikely to be new. Over on Twitter I’m starting to get some useful feedback from Louigi Addario-Berry:

You are veering into my territory! You can find some related results in Chapter 9 of Jim Pitman’s Combinatorial Stochastic Processes: https://www.stat.berkeley.edu/~aldous/206-Exch/Papers/pitman_CSP.pdf

Valentin Kolchin literally wrote the book on random mappings in 1986 (title: Random Mappings). His Lemma 3.1.4 gives the limiting distribution of $C_n/\sqrt{n}$, where $C_n$ is the # of cyclic points of a random function $f:[n] \to [n]$. He attributes this result to Bernard Harris (1960).

Harris’s paper: https://projecteuclid.org/euclid.aoms/1177705677

Harris efficiently crushes many simple questions about random endofunctions in Section 3 of this paper.

On Twitter Steven Galbraith writes:

I’ve seen this result (and other interesting results of similar type) in Random mapping statistics by P. Flajolet and A. M. Odlyzko (EUROCRYPT 1989). Crypto people are interested in this due to hash collisions and Pollard rho.

This is a very well-written article, which makes extensive use of generating functions (and thus implicitly species). It gives a much slicker proof than Tom’s and mine that if $f \colon X \to X$ is a random endofunction on an $n$-element set, the expected number of periodic points of $f$ is $\sim \sqrt{\pi n / 2}$. This proof uses generating functions!

This article also says that the expected cardinality of the image of $f^k$ is asymptotically

$$(1 - \tau_k) n$$

where

$$\tau_0 = 0, \quad \tau_{k+1} = e^{\tau_k - 1}$$

So, the expected size of the image of $f$ is

$$\sim (1- e^{-1})n \approx 0.63 n$$

as Mark Meckes pointed out, while the image of $f^2$ has expected size

$$\sim (1 - e^{e^{-1} - 1}) n \approx 0.47 n$$

and so on. Since each of these asymptotic formulae are only good in the $n \to \infty$ limit, and it typically takes more and more iterations of $f$ to reach the eventual image (the set of periodic points) as $n$ gets larger, we never notice from these formulae that the eventual image has average cardinality $O(\sqrt{n})$.

lambda wrote:

I’m not aware of any natural examples of nonisomorphic species with the same generating function that aren’t built from that one in some way

…where “that one” means total orders vs. permutations.

That’s a good challenge. Here’s what might be an example.

Any finite group has the same number of conjugacy classes as irreducible representations (over $\mathbb{C}$), but there’s no canonical bijection between the two things. So let’s define species $F$ and $H$ as follows: for a finite set $X$,

• $F(X)$ is the set of pairs $(\ast, C)$ where $\ast$ is a group structure on $X$ and $C$ is a conjugacy class of $(X, \ast)$

• $H(X)$ is the set of pairs $(\ast, \alpha)$ where $\ast$ is a group structure on $X$ and $\alpha$ is an isomorphism class of irreducible representations of $(X, \ast)$.

Then $F$ and $H$ have the same generating function, but I think they’re not isomorphic as species.

If one wanted to prove this, one would have to rule out the possibility that $F$ and $H$ are isomorphic as species in a way that changes the group structure. The point is that given a finite group $(X, \ast)$, conceivably there’s a different group structure $\star$ on $X$ such that the conjugacy classes of $(X, \ast)$ correspond naturally to the irreducible representations of $(X, \star)$.

I have a memory of someone telling me that for any finite group $(X, \ast)$, there is some associated group with the property just described, a kind of dual of $(X, \ast)$. (Is it the Langlands dual?) But it seems unlikely that this would have the same order as the original group, which it would have to in order to give an isomorphism between $F$ and $H$.