Counting Cycles of a Permutation in Parallel
How to count the number of cycles modulo 
Gian-Carlo Rota was one the world experts on combinatorics, and helped move the field from a corner of mathematics to become one of its central areas. Rota is famous for many other things, but his book Indiscrete Thoughts is a classic—it is a great read. Even more famous, is his list of Ten Lessons I Wish I Had Been Taught.
Today I plan to follow one of Rota’s lessons and highlight a result that I have already presented. I have not done this before, but I think the result is sufficiently interesting to warrant this. Somehow it got lost before, since the post on it contained several other ideas and results. This time it will be alone. I hope you agree that it is worth repeating; I think it is an interesting “trick” that you might be able to use.
Rota’s ten lessons created a bit of “push-back” as people say. The lesson that got the most push-back was titled:
Publish the Same Result Several Times,
which caused many to get quite upset—perhaps more than a bit. This is, of course, the lesson that I am following today.
Here is the exact quote from his paper:
After getting my degree I worked for a few years in functional analysis. I bought a copy of Frederick Riesz’s Collected Papers as soon as the big, thick, heavy, oversize volume was published. However, as I began to leaf through, I could not help but notice that the pages were extra thick, almost like cardboard. Strangely, each of Riesz’s publications had been reset in exceptionally large type. I was fond of Riesz’s papers, which were invariably beautifully written and gave the reader a feeling of definitiveness.
As I looked through his Collected Papers, however, another picture emerged. The editors had gone out of their way to publish every little scrap Riesz had ever published. It was clear that Riesz’s publications were few. What is more surprising is that the papers had been published several times. Riesz would publish the first rough version of an idea in some obscure Hungarian journal. A few years later he would send a series of notes to the French Academy’s Comptes Rendus in which the same material was further elaborated. A few more years would pass, and he would publish the definitive paper, either in French or in English.
Adam Koranyi, who took courses with Frederick Riesz, told me that Riesz would lecture on the same subject year after year while meditating on the definitive version to be written. No wonder the final version was perfect.
Riesz’s example is worth following. The mathematical community is split into small groups, each one with its own customs, notation, and terminology. It may soon be indispensable to present the same result in several versions, each one accessible to a specific group; the price one might have to pay otherwise is to have our work rediscovered by someone who uses a different language and notation and who will rightly claim it as his own.
Let’s now turn to the result that I want to highlight, which was originally presented here.
Number of Cycles of a Permutation
The result concerns permutations. Of course a permutation is nothing more than a mapping 
The problem that I want to discuss is: does 
Computing the number of cycles of a permutation seems to a sequential property. I am not exactly sure how to state this precisely, but the obvious algorithm requires that you pick a point 
Then, move on to the next cycle, and eventually discover the cyclic structure of
There is another way to compute the number of cycles of a permutation modulo 
Theorem: For any permutation
,
Here 
The number of cycles is 
If we think of the cardinality of
The reason I am excited by the theorem is that computing 
Open Problems
Can we generalize the inversion method to count cycles modulo something other than
Finally, can we use the inversion method to solve an open problem?
Trackbacks
- Counting Cycles of a Permutation in Parallel · ldfdc
- Math World | Counting Cycles of a Permutation in Parallel « Gödel's Lost Letter …
- Math World | Counting Cycles of a Permutation in Parallel « Gödel's Lost Letter …
- The Curious History of the Schwartz-Zippel Lemma « Gödel’s Lost Letter and P=NP
- Promise Problems And TWOPATHS « Gödel’s Lost Letter and P=NP
- generated discreteness | Peter's ruminations
My brain hurts. I’m just going to lie down for a while while I think about this one.
Was the post unclear? Am sorry if that happen.
Just to clarify, it seems like you are asking for something like a ‘nice formula’ for such modular counting, right? Because it looks clear that counting the number of cycles can be done in parallel. (or are you wondering more about the precise parallel complexity?)
(Each cycle is a strongly connected component, which can in parallel be identified with its minimal-index element; then we count the number of distinct elements via, say, parallel sorting.)
Nice post, and thanks for sharing the great Lessons from Rota.
Yes all can be done in parallel. The issue is can it be done with little work by each processor. So it is an efficiency issue.
Thanks for Rota comment. His list is quite neat. The book is a lot of fun to read too.
Pardon me if I don’t quite understand, but it seems like the original method is
and the parallel method 
. Isn’t that less efficient?
It is not the total number of operations that is key. It is the parallel time. Thus, the new method takes two steps, while the usual takes n steps. This is a huge difference in some complexity applications. This also means that we understand the structure of the problem more if we can see how to do the problem in few parallel steps. But, you are right about total cost.
The idea of the theorem to turn it around is vey interesting. But after this proof, which class can we put this problem into?
Guy Steele has posted slides of a SIGPLAN ICFP talk he gave last week about the difference between “thinking sequentially” and “thinking concurrently.” It certainly challenged some intuitions I had about computation. Link here:
http://research.sun.com/projects/plrg/Publications/ICFPAugust2009Steele.pdf
It seems that the “central processor” should be a tree-adder. It takes log(n^2) = O(log n) more steps. So, time complexity is O(n^2 / p + log n), as in the case, p = n^2, it is O(log n).
Suppose we define a directed graph on [n] where (i,j) is an edge iff (i,j) is an inversion. Then, this is a transitive acyclic graph, and so every cycle is actually a clique. So the number of edges (=inversions) in each clique is even since it is of the form k(k-1)/2. Therefore, the parity is determined by the number of cliques or equivalently the number of cycles. So the “reason” why parity seems to work (and mod3 does not) is because inversion is a binary relation.
Stupid mistake in my previous comment, but this seems to be fixable (one way or another :-)).
Create an _undirected_ graph G with an edge from u to v whenever pi(u) = v or pi(v) = u. The connected components of G are the cycles of pi. Connected components can be computed in O(log n) time using O(m / log n) processors (see Gazit, FOCS ’86, http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4568240). Counting the components created can be done fairly easily in time O(log n) time using O(n / log n) processors. So the problem of counting the number of cycles in a permutation can be solved in time O(log n) using O(n / log n) processors. With the number of cycles in hand, the number of cycles modulo any desired base can be computed in constant time on one processor. Of course there’s probably a much simpler direct algorithm, but this reduction is sufficient to show the asymptotic complexity.
RJLipton wrote:
Thus, the new method takes two steps.
What model of parallelism do you have in mind? In classic models such as the PRAM the step of counting how many processors say “I have an inversion” takes Theta(log n) time.
Update: I just read your post http://rjlipton.wordpress.com/2009/07/18/graphs-permutations-characters-and-logspace/ that you linked to. It seems that my O(log n) time solution does not answer your question since you are looking for an O(1) time solution using unbounded fan-in gates.