(Both the published version and the arXiv version are available online.)

In 1953, Carlitz proved the surprising result that, for  q>2,  every permutation of  F_q  is the composition of permutations induced by either  x^q-2  or by linear polynomials  ax+b.  As a consequence, every permutation of  F_q  is induced by an exceptional polynomial.

Carlitz's proof is as follows: it suffices to prove the result in case the permutation is a 2-cycle of the form  (0c)  with  c  in  F_q^*,  since every permutation is a product of such 2-cycles. Then Carlitz observes that  (0c)  is the permutation of  F_q  induced by  f_c(x) := -c² (((x-c)^q-2 + c^-1)^q-2 - c)^q-2.  It is straightforward to verify that the polynomial   f_c  has this property, but it is not at all clear how one could have discovered the polynomial   f_c  in the first place. Without an explanation of how one could come up with   f_c,  this proof seems like a magical verification of the result, rather than a derivation of the result by pure thought.

We present a simple and natural procedure for producing another polynomial which has the same properties as   f_c.  Note that  μ(x) := 1-1/x  induces an order-3 permutation of  P¹(F_q),  and that one cycle of  μ  is  (∞10).  Then  h(x) := 1-x^q-2  agrees with  μ  on  F_q^*,  and  h  interchanges  0  and  1,  so  g(x) := h(h(h(x)))  induces the permutation  (01)  on  F_q.  Thus  c g(x/c)  induces the permutation  (0c).

We also discuss further issues related to this result, and deduce some consequences.

Michael Zieve:  home page   publication list