A deranging puzzle

A few years ago, Taoyang Wu asked me for a problem on computational complexity. I suggested the following.

  • Input: A set S of permutations of {1,…,n}, with n>1.
  • Problem: Does the group G generated by S contain a fixed-point-free (f.p.f.) element?

I thought that the decision problem would be easy, but to my surprise, Taoyang showed that it was NP-complete.

Part of the reason I thought it would be easy was that, if the group G is transitive, the decision problem can be solved in constant time! Camille Jordan showed in 1873 that the answer is necessarily yes. Thereto hangs a tale.

In 1993, in a rush to produce something for Jack van Lint’s birthday, Arjeh Cohen and I proved a strengthening of Jordan’s theorem. Under the same conditions, at least a proportion 1/n of the elements of G are f.p.f. The proof is elementary; it is very odd that Frobenius or someone else didn’t find it almost a century earlier. And I have a claim to fame here. Jean-Pierre Serre gave a talk “On a theorem of Jordan” at Queen Mary and various other places (it was eventually published). He wouldn’t say beforehand which theorem of Jordan it was, but it turned out to be this one; he remarked on the fact that it had taken 120 years for it to be quantified, and went on to point to many consequences in number theory and topology. For example, the Chebotarev density theorem and our result imply that an irreducible polynomial of degree n>1 over the integers has no linear factor when reduced mod p for at least a proportion 1/n of all primes.

Incidentally, the proof of Jordan’s theorem is very easy. A simple argument (which we now know as the Orbit-Counting Lemma) shows that the average number of fixed points of elements of G is 1. But the identity fixes more than one point; so some element fixes fewer than 1.

To return to the complexity problem. Note that there is an efficient algorithm to check whether the group G is transitive (essentially, testing the connectedness of a graph). Now, given that G is transitive, we know that there is a f.p.f. element: so find one!

By my result with Arjeh Cohen, a random element has chance at least 1/n of being f.p.f. A short calculation shows that, if we choose n random elements independently, we have probability at least (1-1/e) of finding one; so, in mn choices, the probability that we don’t succeed is exponentially small (in terms of m). So there is an efficient randomized algorithm for this problem.

Derandomization is a big topic in computer science, about which I know nothing. But in this case, there is a deterministic polynomial-time algorithm to find a f.p.f. element, with a twist: it is a rather complicated group-theoretic algorithm, and the proof of its correctness uses the 10000 pages of the Classification of Finite Simple Groups.

In 1985, Fein, Kantor and Schacher showed that we can improve Jordan’s theorem another way: under the same hypotheses, there is a f.p.f. element of prime power order. (I mentioned this in my post on Isbell’s Conjecture. Emil Vaughan has checked that their arguments can be implemented in a polynomial time (though rather complex) algorithm.

The puzzle is:

Is there a more elementary algorithm to find a f.p.f. element in a transitive group?

Vaughan’s algorithm needs to know about the finite simple group, so that if it meets one of them in a known action, it can directly construct a f.p.f. element. Can this be avoided?

Next

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems. Bookmark the permalink.

2 Responses to A deranging puzzle

  1. Pingback: A birthday party « Peter Cameron's Blog

  2. Pingback: On a theorem of Jordan « Peter Cameron's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s