Degree of orthomorphism polynomials over finite fields

Abstract An orthomorphism over a finite field F q is a permutation θ : F q → F q such that the map x ↦ θ ( x ) − x is also a permutation of F q . The degree of an orthomorphism of F q , that is, the degree of the associated reduced permutation polynomial, is known to be at most q − 3 . We show that this upper bound is achieved for all prime powers q ∉ { 2 , 3 , 5 , 8 } . We do this by finding two orthomorphisms in each field that differ on only three elements of their domain. Such orthomorphisms can be used to construct 3-homogeneous Latin bitrades.