On the Degree of Local Permutation Polynomials

Abstract

Every Latin square of prime or prime power order $s$ corresponds to a polynomial in 2 variables over the finite field on $s$ elements, called the local permutation polynomial. What characterizes this polynomial is that its restrictions to one variable are permutations. We discuss the general form of local permutation polynomials and prove that their total degree is at most $2s–4$, and that this bound is sharp. We also show that the degree of the local permutation polynomial for Latin squares having a particular form is at most $s–2$. This implies that circulant Latin squares of prime order $p$ correspond to local permutation polynomials having degree at most $p–2$. Finally, we discuss a special case of circulant Latin squares whose local permutation polynomial is linear in both variables.