Degree of Orthomorphism Polynomials over Finite Fields

Abstract

An orthomorphism over a finite field ${\mathbb{F}}_q$ is a permutation $\theta :{\mathbb{F}}_q\mapsto {\mathbb{F}}_q$ such that the map $x\mapsto \theta (x)-x$ is also a permutation of ${\mathbb{F}}_q$. The degree of an orthomorphism of ${\mathbb{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\notin \{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.