27
$\begingroup$

It is well known that two randomly chosen permutations of $n$ symbols commute with probability $p_n/n!$ where $p_n$ is the number of partitions of $n$. This is a special case of the fact that in a group, the probability that two elements chosen uniformly at random (with repetition allowed) is the number of conjugacy classes divided by the size of the group.

Question. What is the probability that two mappings of $n$ symbols chosen uniformly at random commute?

I suspect an exact answer would be difficult and would be happy to learn of reasonably tight asymptotic results.

Added. This probability should go to zero quickly because Misha Berlinkov recently showed that with probability going to 1 as $n$ goes to infinity, two random elements generate a subsemigroup containing a constant map and so if they commute they generate a unique constant map. This should happen almost never (and most likely has been proven).

Added based on Brendan McKay's answer. Computing the probability that an element of a monoid $M$ commutes with an element of its groups of units $G$ is no harder than the commuting probability in a group. Namely, $G$ acts on $M$ by conjugation; let's call the orbits conjugacy classes. Then the probability that an element of $G$ commutes with an element of $M$ is the number of conjugacy classes of $M$ divided by the number of elements of $M$. The proof is the same as for groups. If $Fix(g)=\{m\in M\mid gmg^{-1}=m\}$, then $$\frac{|\{(g,m)\in G\times M\mid gm=mg\}|}{|G||M|} = \frac{1}{|M|}\frac{1}{|G|}\sum_{g\in G}|Fix(g)| = \frac{\text{number of conjugacy classes}}{|M|}$$ by the Cauchy-Burnside-Frobenius orbit counting formula.

For $M=T_n$ the monoid of all mappings on $n$ symbols and $G=S_n$ the symmetric group, conjugacy classes correspond to isomorphism classes of functional digraphs on $n$ vertices. A functional digraph is a digraph (loops allowed) in which each vertex has outdegree $1$. Each mapping $f$ gives a functional digraph by drawing an edge from $i$ to $f(i)$. It is obvious that $f,g$ are conjugate iff their corresponding digraphs are isomorphic (it is the same proof that permutations are determined up to conjugacy by cycle type).

According to the book of Flajolet and Sedgewick, the number of unlabelled functional digraphs grows likes $O(\rho^{−n}n^{−1/2})$ where $\rho\approx .29224$. So the probability of a random mapping commuting with a random permutation is pretty small. Brendan raises the nice question of how different the probability of a random permutation commuting with a random mapping is from the probability of a random mapping commuting with a random mapping. My guess is the latter goes to $0$ qualitatively faster.

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ A (much) weaker necessary condition than commuting is that $fg$ and $gf$ have the same range. I expect that even that would be highly unlikely. In 100 trials for $n=10$ (which is far from infinity), it was not unusual for two random elements to generate all $10$ constant maps. Less common, but not that rare, was to generate only one or even no constant maps. However in none of the cases did $fg$ and $gf$ have the same range. $\endgroup$ – Aaron Meyerowitz Sep 24 '13 at 19:25
  • 1
    $\begingroup$ Have you tried computing the number of commuting maps for $n=1,2,3$, say, and then consulting the Online Encyclopedia of Integer Sequences? $\endgroup$ – Gerry Myerson Sep 24 '13 at 23:59
  • 2
    $\begingroup$ @GerryMeyerson, I didnt because I suspect there is little point to doing that in that the number of pairs of maps is $(n^n)^2$ and so one won't get very far. Also small n are atypical. I wouldn't trust any statement about $S_n$ obtained by just considering n=1,2,3,4. $\endgroup$ – Benjamin Steinberg Sep 25 '13 at 0:49
  • 5
    $\begingroup$ @Benjamin, you're missing the point (and the spelling). You calculate it for 1, 2, and 3. You look up the numbers you get in the OEIS. With luck, what you find out is that someone has studied the sequence before and there are links given to the literature where you find the answers to all your questions. The question of trusting a statement obtained by considering small $n$ doesn't arise. Have you no familiarity with the OEIS? $\endgroup$ – Gerry Myerson Sep 25 '13 at 6:26
  • 2
    $\begingroup$ @Gerry: Searching for "commuting functions" is also something worth trying, and it works! $\endgroup$ – Brendan McKay Sep 25 '13 at 11:42
11
$\begingroup$

The number of ordered pairs of commuting functions is A181162. I agree with those counts up to n=7. There is little in OEIS that helps to answer the asymptotics question.

Incidentally, the probability that $f(g(1))=g(f(1))$ is not $1/n$. I think it is $1/n + (n-1)/n^3~$ though I might have miscalculated. That formula works up to $n=7$.

ANOTHER relevant fact: If $f$ is a permutation, then any function $g$ commuting with $f$ is determined by the image of one element of each cycle of $f$. So the number of such $g$ is at most $n^{C(f)}$ where $C(f)$ is the number of cycles of $f$. Random permutations have on average only $\ln n+O(1)$ cycles, so the probability of a random function commuting with a random permutation might be at most something like $n^{-n+\ln n+O(1)}$ (which is an abuse of expectations but might be something akin to the truth). Is a random function more or less likely to commute with another random function or with a random permutation? [NOTE: I added "at most" since some assignments don't work: the image of a point in a cycle of length $k$ must lie in a cycle whose length is a divisor of $k$.]

Improve this answer
$\endgroup$
3
  • $\begingroup$ the probability that a random permutation commutes with a random mapping can in principle be computed by the Burnside-Frobenius orbit counting lemma. It should be something like the number of orbits of S_n on mappings divided by the number of mappings. An orbit corresponds to a digraph on n vertices where all vertices have out-degree 1 (loops allowed). I believe something is known about this. My feeling is that permutations are more likely to commute with functions than general functions. This is at least true for small n. How big a difference to expect is not clear. $\endgroup$ – Benjamin Steinberg Sep 25 '13 at 13:45
  • $\begingroup$ Here I mean orbits under conjugation. $\endgroup$ – Benjamin Steinberg Sep 25 '13 at 13:47
  • 1
    $\begingroup$ I agree with your probability that $f(g(1)) = g(f(1))$. One simple-ish argument for it: work by cases on which of $f(1)$, $g(1)$, and 1 are equal. If $f(1) = g(1) = 1$, which happens with probability $\frac{1}{n^2}$, then $f(g(1)) = g(f(1))$ holds with probability 1. In all other cases, $f(g(1)) = g(f(1))$ holds with probability 1/n. The overall probability of $\frac{1}{n^2} + \frac{n^2-1}{n^2} \cdot \frac{1}{n} = \frac{1}{n} + \frac{n-1}{n^3}$ follows. $\endgroup$ – Peter LeFanu Lumsdaine Sep 25 '13 at 16:16
3
$\begingroup$

The expected value in Brendan McKay's answer on the probability of $f(g(1))=g(f(1))$ is correct. Just count the quintuples $(a,b,c,f,g)$ where $g(1)=a$, $f(1)=b$, $f(a)=c$, $g(b)=c$. For instance, there are $n(n-1)^2$ triples $(a,b,c)$ with $a\ne1$, $b\ne1$, and for each such tripel there are $n^{n-2}$ possibilities for $f$ and $g$ each, contributing $n(n-1)^2n^{2n-4}$ to the possibilities. In the cases $a\ne1$, $b=1$ we must have $c=a$, so the contribution is $(n-1)n^{2n-3}$. The same for $a=1$, $b\ne1$. Finally, if $a=b=1$, then $c=1$, and that case contributes $n^{2n-2}$.

Improve this answer
$\endgroup$
1
$\begingroup$

Let $f$ and $g$ be random mappings. If they commute, then $f(g(1))=g(f(1))$, and this happens with probability $n^{-1}$. Now $f(g(2))=g(f(2))$ also holds with probability $n^{-1}$, but these events need not be independent. To make them independent, suppose that the first equation holds. Fix $f(1), g(1), f(g(1)), g(f(1))$, without loss assume that 2 is not among them. With probability $\leq\frac{16}{n}$ we have that one of these elements equals one of $f(2), g(2), f(g(2)), g(f(2))$, in which case things get messy. If not, then $f(g(2))=g(f(2))$ holds with probability $\frac{1}{n-|\{f(1), g(1), f(g(1)), g(f(1))\}|}<\frac{2}{n}$. Hence the second equation holds true with probability $\leq\frac{18}{n}$.

Now continue. In the $k$-th step the conditional probability that the element you pick refutes commutativity subject to the condition that the mappings satisfy all equations already fixed is $\frac{1}{n-\#\{f(1), \ldots, g(x_k)\}}\leq \frac{1}{n-4k}$, if things are nice. The probability that things are messy is $\leq\frac{16 k}{n}$. Hence the probability that $f$ and $g$ commute is bounded above by $$ \prod_{16k<n}\left(\frac{1}{n-4k}+\frac{16 k}{n}\right)\leq e^{-n/18}. $$

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ Unfortunately it is not true that the probability that $f(g(1))=g(f(1))$ is $1/n$ (at least, not exactly). Both by hand and by computer I find 10 out of 16 pairs for $n=2$ have that property. See my answer. $\endgroup$ – Brendan McKay Sep 25 '13 at 11:39
  • $\begingroup$ Right. I was assuming that f at g(1) and g at f(1) are independent, which they are not. However, taking these probabilities to be $<2/n$ still suffices to give an exponential bound. $\endgroup$ – Jan-Christoph Schlage-Puchta Sep 26 '13 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.