Degree of Orthomorphism Polynomials over Finite Fields
An orthomorphism over a finite field Fq is a permutation
θ:Fq→Fq such that the map
x→θ(x)-x is also a permutation of Fq. The
degree of an orthomorphism of Fq, 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
not in {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.