ON A THEOREM OF CARLITZ
Michael E. Zieve · 2009
Abstract. Carlitz proved that, for q> 2, the group of all permutations of Fq is generated by the permutations induced by linear polynomials and x q−2. His proof relies on a remarkable polynomial which appears to have been found by magic. We show here that no magic is required: there is a straightforward way to produce a simple polynomial which has the same remarkable properties as the complicated polynomial in Carlitz’s proof. We also identify the crucial subtlety which allows such simple polynomials to exist, and discuss some consequences. The theorem in the title is as follows: Theorem. If q> 2 then every permutation of Fq is the composition of permutations induced by x q−2 and by linear polynomials over Fq. Betti proved this for q = 5 (as the final assertion in [1]), and Dickson proved it for q = 7 [6, p. 119]. In response to a question posed by Straus, Carlitz [2] proved it in general, via the following argument. It suffices to prove the result in case the permutation is a 2-cycle of the form (0a) with a ∈ F ∗ q, since every permutation is a product of such 2-cycles. And Carlitz observed that (0a) is the permutation of Fq induced by) q−2) q−2 fa(x): = −a 2(( (x − a) q−2 + 1 − a. a Although it is straightforward to verify that fa has this property, it is not at all clear how one could have discovered the polynomial fa in the first place. Indeed, several authors have presented fa as a mysterious and complicated object: for instance, [11, p. 169] and [10, p. 358] assert that this representation of (0a) demonstrates that “simplicity as polynomials and simplicity as permutations are not equivalent.” My purpose here is to remove the mystery from Carlitz’s proof, by presenting a straightforward procedure for producing a simple polynomial which has the same crucial property as fa, namely that of inducing the permutation (0a). Note that µ(x): = 1 − 1/x induces an order-3 permutation of Fq ∪ {∞}, and one cycle of µ is (∞10). Then h(x): = 1 − xq−2 agrees with µ on F ∗ q, and h interchanges 0 and 1, so g(x): = h(h(h(x))) induces the permutation (01) on Fq. Thus ag(x/a) induces the permutation (0a). The surprising feature of this proof – and of Carlitz’s result, once we identify xq−2 with 1/x – is that we have expressed each element of the