Maximum-degree local permutation polynomials over the prime field
Henry Zweiman
September 8, 2026
Abstract
For every prime power and every positive integer , we prove the existence of a local permutation polynomial over with coefficients in and total degree . The proof uses a subfield patch that preserves the extremal coefficient, together with an analysis of a recursive family formed from inversion and a transposition. For every nonprime odd field, we compute the extremal coefficient of that family in every arity by a first-order recurrence over . In particular, over every with , the family fails to have maximum degree among arities precisely when is congruent to or modulo . This gives infinite families of counterexamples to the proposed maximum-degree conjecture for this recursion, while the ternary case supplies the missing construction for the uniform existence result.
1. Introduction and main results
A local permutation polynomial (LPP) over a finite field is a polynomial function that is a permutation in each variable when the other variables are fixed. We identify polynomial functions with their unique reduced representatives, whose degree in each variable is less than . For , an LPP has degree at most in each variable, and hence total degree at most . We call this total degree maximum degree.
Gutiérrez and Jiménez Urroz established unrestricted-coefficient existence and several prime-coefficient cases in [2,3]. Their remaining prime-coefficient existence question is answered by the following theorem.
Theorem 1.
For every prime power and every integer , there is an LPP in over of reduced total degree .
The characteristic-two case is already known [2, Theorem 4]. For , we extend prime-field examples by a patching construction that preserves the extremal coefficient. The case follows from the next result, which also describes the failure of a proposed general construction.
Let , put , and let
As functions, inverts nonzero elements and fixes zero, while interchanges zero and one and fixes all other elements. Define reduced polynomial functions
Every is an LPP defined over . The assertion that this recursion always has maximum degree in odd characteristic is Conjecture 1 of both [2, Section 6] and [3, Section 4].
For a reduced polynomial in variables, write
For an LPP, maximum degree is equivalent to .
Theorem 2.
Let with odd and . Set for the family (1). Define by
Then, for every ,
In particular, and have maximum degree if and only if . Explicitly,
where all quantities are interpreted in .
Corollary 3.
For the recursion (1) over , , the following hold.
If , then for every .
If , then fails to have maximum degree precisely when or , for .
If , then the failures in the paired arities occur precisely when in . Either there are no failures or the corresponding form one residue class modulo the multiplicative order of in .
In particular, and give a counterexample to the recursive conjecture with degree strictly smaller than . Theorem 2 classifies maximum-degree arities, rather than the precise degree when the extremal coefficient vanishes. Its hypothesis is essential to the coefficient-counting argument below; no classification over prime fields is asserted here. Also, is not of maximum degree for , so our statements about the recursion start at arity two.
2. Extremal coefficients and subfield patching
We first record the coefficient functional used throughout the paper. In two variables, replacing an embedded subsquare is a form of Latin trade; see [1, Section 1] for the trade viewpoint. The feature needed here is the exact preservation of a polynomial coefficient across different fields, together with Frobenius equivariance.
Lemma 4.
Let . For every reduced polynomial function ,
If is an LPP, then its degree in each variable is at most .
Proof.
For a reduced univariate polynomial , the sums of powers in give
Indeed, for , the sum of is nonzero only for , when it equals . Applying this identity one variable at a time proves (5).
On a coordinate line, an LPP takes each field value once. Its sum of values is therefore zero, as . For a reduced univariate polynomial this sum equals minus the coefficient of . Consequently the coefficient polynomial of in vanishes on every choice of the remaining coordinates. It is reduced in those coordinates and hence is the zero polynomial.
Lemma 5 (Subfield patch).
Let with , and let be an LPP of maximum degree. Define
Then is an LPP of maximum degree over , and
If is equivariant under the prime-field Frobenius automorphism, then so is , and its reduced polynomial has coefficients in the prime field.
Proof.
Fix all coordinates except . If a fixed coordinate lies outside , the coordinate map is translation by a constant of . Otherwise all fixed coordinates lie in . On the coordinate map is a permutation of , because is an LPP. On it is translation by a constant in , which permutes . These two parts have disjoint images, so the coordinate map permutes .
Put . Since and , both and vanish: the relevant total degree is greater than one. The function is supported on . Lemma 4 therefore gives
The degree bound in that lemma proves maximality.
Finally is stable under the prime-field Frobenius, and addition commutes with Frobenius. Thus (6) is equivariant whenever is. To see that equivariance is equivalent to prime-field coefficients, write the reduced representative as . Its coefficientwise Frobenius conjugate is . Equivariance and the bijectivity of Frobenius imply that and agree at every point of . Uniqueness of reduced interpolation yields for all .
The patch has a direct polynomial representative. If denotes its reduced polynomial over , then
Here means reduction modulo . Each bracket is the indicator function of . In particular, when , formula (8) visibly has coefficients in .
3. A transfer operator for the recursion
Let with . On the space of reduced univariate polynomial functions , define the linear operator
For put
Summing in the last coordinate of (1) shows that . Since , we obtain
Lemma 6.
Let , and put . The coefficients of satisfy
The integer in (12) is interpreted as an element of .
Proof.
Let be the reduced representative of . Since swaps zero and one, the difference between and is represented by
Indeed the sum on the right is at zero, at one, and zero elsewhere. In (9), substitute and write . Expansion of gives
For clarity, the coefficient of in that expansion is multiplied by . Among , this sum vanishes except at , where it is . The surviving coefficient is precisely .
Thus . Its constant coefficient is . For , the monomial reduces to . When this gives coefficient at ; the other cases give (12). No term of degree occurs.
4. The extremal coefficient over nonprime odd fields
We now prove Theorem 2. Assume with odd and , and put for . Lemma 6 shows that the coefficients of at indices and are zero. Its remaining positive-degree coefficients have the form
where and . For we may take ; the profile property then follows inductively from (12).
Write . In the complete index interval , each residue modulo occurs times. This multiplicity is zero in . Removing indices and using gives
By Lemma 6 we can therefore choose the profiles recursively as
Combining the two identities and substituting (16),
These evaluations remain valid when , where some of the named residues coincide: they are values of the same functions, not coordinates required to be distinct.
The residue of modulo is , so (10) becomes for . Consequently (17) gives
The initial values are and , obtained from and . Thus the even subsequence is the sequence in (2). The odd subsequence starts at and obeys , which proves by induction. Solving (2) proves (4). Lemma 4 then proves the maximum-degree criterion, completing Theorem 2. Corollary 3 follows immediately.
5. Uniform existence over the prime field
We complete the proof of Theorem 1 and give formulas for its constructions. For , the polynomial works in every field under consideration. It remains to treat .
Suppose . Theorem 5 of [2], applied over with , provides a maximum-degree LPP in every arity: the required conditions are and . For this is the desired polynomial. For any larger extension, apply Lemma 5 with . Formula (8) gives the resulting polynomial over and (7) proves its maximum degree.
For completeness, the prime-field seed can be chosen by a finite explicit procedure from that construction. Set . Form by taking disjoint copies of , adding them, and raising the sum to the th power. Choose with , and form
The seed construction proves that has nonzero coefficient at . Specialize the last variables to a tuple in for which the coefficient of remains nonzero. Such a tuple exists because that coefficient is a nonzero reduced polynomial in the last variables. Choosing the lexicographically first such tuple, with field elements represented by , makes this a deterministic procedure. Specialization preserves the local permutation property.
Finally, suppose . Since , its extension degree satisfies . Use the recursion (1). Corollary 3 shows that for every , and every operation in the recursion has coefficients in . This proves Theorem 1.
6. Scope and further questions
The subfield patch separates coefficient descent from the original construction of an LPP. Its extremal coefficient is preserved exactly, rather than merely shown to remain nonzero. The ternary recursion supplies the case where the prime subfield itself is too small for the patching lemma.
The transfer identity , where the derivative is taken after reducing , also applies when is prime. The simplification (14) does not: residue classes then occur only once. Determining the maximum-degree arities in that case is a separate problem. For nonprime odd fields, another question is to determine the exact reduced degree at the arities where Theorem 2 gives .
References
[1] N. J. Cavenagh and R. M. Falcón, Latin bitrades derived from quasigroup autoparatopisms, arXiv:2308.14987v1 (2023). https://arxiv.org/abs/2308.14987.
[2] J. Gutierrez and J. Jiménez Urroz, Permutation and local permutation polynomials of maximum degree, Afrika Matematika 36 (2025), article 45. doi:10.1007/s13370-025-01247-3.
[3] J. Gutierrez and J. Jiménez Urroz, Local permutation polynomials of maximum degree over prime finite fields, Bulletin of the Malaysian Mathematical Sciences Society 48 (2025), article 40. doi:10.1007/s40840-025-01825-5.