(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 Zieve: home page publication list