Michael E. Zieve:
On a theorem of Carlitz,
Journal of Group Theory 17 (2014), 667–669.

(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  Fq  is the composition of permutations induced by either  xq-2  or by linear polynomials  ax+b.  As a consequence, every permutation of  Fq  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  Fq*,  since every permutation is a product of such 2-cycles. Then Carlitz observes that  (0c)  is the permutation of  Fq  induced by  fc(x) := -c2 (((x-c)q-2 + c-1)q-2 - c)q-2.  It is straightforward to verify that the polynomial   fc  has this property, but it is not at all clear how one could have discovered the polynomial   fc  in the first place. Without an explanation of how one could come up with   fc,  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   fc.  Note that  μ(x) := 1-1/x  induces an order-3 permutation of  P1(Fq),  and that one cycle of  μ  is  (∞10).  Then  h(x) := 1-xq-2  agrees with  μ  on  Fq*,  and  h  interchanges  0  and  1,  so  g(x) := h(h(h(x)))  induces the permutation  (01)  on  Fq.  Thus  c g(x/c)  induces the permutation  (0c).

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


Michael Zievehome page   publication list