Counting Cycles of a Permutation in Parallel
How to count the number of cycles modulo in parallel
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 from a finite set to itself that is one-to-one. The set is usually taken to be for some , but we will allow any set .
The problem that I want to discuss is: does have an even or an odd number of cycles? Every permutation can be uniquely written, up to order, as a collection of cycles. The number of cycles of a permutation will be denoted by .
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 , and then trace out its cycle:
Then, move on to the next cycle, and eventually discover the cyclic structure of . This yields, of course, the exact number of cycles of the permutation.
There is another way to compute the number of cycles of a permutation modulo that is more indirect. This is the trick that I want to highlight:
Theorem: For any permutation ,
Here is the number of inversions of the permutation : an inversion is a pair of and in so that and yet . Here is an example: Consider the permutation that maps,
The number of cycles is , the cardinality of the set is , and there are inversions. The inversions are and . The theorem works, since .
If we think of the cardinality of as known, then the theorem really says:
The reason I am excited by the theorem is that computing seems, to me, to be a much less sequential task, than the usual method of determining the cyclic structure of a permutation:
The usual method is sequential. It follows a point to another point and eventually determines its cyclic structure. Of course this method determines more than just the number of cycles modulo : it gets the exact number of cycles. This method clearly is a sequential method, which does not seem to be parallelizable in any obvious manner.
The inversion method is easily made parallel. Have each “processor” take a pair of from , and then check whether they form an inversion: that is and . This all can be done in one parallel step. Then, the processors each report back to a central processor, who computes the total number of inversions modulo .
Can we generalize the inversion method to count cycles modulo something other than ? Put another way: is there a parallel method for computing the number of cycles of a permutation modulo say ? Note, simply computing the number of inversions modulo will not allow the determination of the number of cycles modulo of a permutation. That was one of the results of the earlier post.
Finally, can we use the inversion method to solve an open problem?