# Counting and understanging commuting functions.

Fix a positive integer $n$, and consider the functions from a set of size $n$ to itself. Let $cp(n)$ denote the number of ordered pairs $\langle f,g \rangle$ of these functions which commute, i.e., for which $f\circ g= g \circ f$. If we restrict $f$ and $g$ to be permutations, then the number of such pairs is well known: A053529 in the OEIS. But I cannot find any references to this more general case. Any pointers to existing work that I might be missing would be greatly appreciated. I've recently added the first 10 values of $cp(n)$ to the OEIS: A181162.

Obviously, $n^n\le cp(n)\le n^{2n}$. Also, $(cp(n)-n^n)/2$ is always an integer, since it counts the number of unordered pairs of distinct commuting functions. Nothing else seems to be as easy to prove as it should be. With some work, we can now show that $cp(n)$ is always divisible by $n$. I'm hoping that this is a new fact.

The investigation led me to the following strange fact about the symmetric group $S_n$. I'd like to know if this has been noticed before, or if it is also a new result. Fix a permutation $\sigma\in S_n$, and suppose that the size of the centralizer of $\sigma$ does not divide $(n-1)!$. (Note that it must divide $n!$, and the assumption is equivalent to saying that the size of $\sigma$'s conjugacy class is not a multiple of $n$). Represent $\sigma$ as a disjoint union of cycles. Then one of the following must hold:

1. There is a prime divisor $p$ of $n$ such that each of the cycles of $\sigma$ is either a fixed point or a cycle of size $p$.
2. $n$ is a multiple of 4 and each cycle of $\sigma$ has size 1, 2, or 4.

Case 1 includes the case of the identity function or $n/p$ cycles each of size $p$. There is just one $p$ for each $\sigma$, but each prime divisor of $n$ will occur is some case-1 permutation. Note that there can be at most three distinct cycle sizes in $\sigma$. If $n$ is prime, it is not hard to prove that the only possibilities for $\sigma$ are the identity and an $n$-cycle, but the general case seems to take a bit of work to establish.

-
1^1=cp(1)=1^{2\cdot 1}, so it should say \$n^n\leq cp(n)\leq n^{2n}. PS, for the community: Would it have been appropriate for me to edit the post myself to fix that? (just reached 2000 rep, don't know the relevant etiquette) – Ricky Demer Oct 13 '10 at 23:31
Some of the general algebra literature includes work on semigroups of functions on a set. My sometimes faulty memory suggests that work of Dietmar Schweigert or Klaus Denecke on hyperidentities included some basic results on iterated selfmaps of a finite set. They may not have addressed your issue, but their bibliographies might have. If other sources don't help you might look at the literature on finite semigroups (possibly monoids). Gerhard "Ask Me About System Design" Paseman, 2010.10.13 – Gerhard Paseman Oct 13 '10 at 23:33
Also, it should not be f comp g = f comp f . Also, in general algebra the notion of polarity has been studied, a restriction of which is your case. I hope Arturo Magidin or Joel Hamkins chimes in with a better suggestion than what I have offered. If you put in a universal-algebra tag, that might attract the desired kind of attention. Gerhard "Ask Me About System Design" Paseman, 2010.10.13 – Gerhard Paseman Oct 13 '10 at 23:40
Thanks for pointing out the typos, I've fixed them. I'm a topologist, and came to this question because commuting continuous maps are hard to classify. I started out by looking at semigroup theory, and nothing I could find seemed to help. But, since this about as far as you can get from my area of expertise, I might very well be missing something simple. – Jeff Norden Oct 14 '10 at 1:21
Jeff, I have never seen that fact about elements of S_n in classes of size not divisible by n; it's amusing. It was not clear from your post whether or not you actually have a proof. Do you? – Marty Isaacs May 29 '12 at 19:13