Nonexistence of Permutation Binomials of Certain Shapes

Ariane M. Masuda, Michael E. Zieve

TL;DR

This paper tackles the long-standing mystery of permutation binomials over finite fields. The authors prove that certain "simple" forms of permutation binomials, specifically $x^m + ax^n$, cannot exist when the difference in exponents $m-n$ shares common factors of 2 or 4 with the field size minus one ($p-1$). This result resolves conjectures for specific prime field structures.

What Problem Does This Paper Address?

Permutation polynomials are functions over finite fields that rearrange the elements of the field. They are fundamental in areas like coding theory and cryptography. While permutation monomials ($x^m$) are well-understood (they permute a field $\mathbb{F}_q$ if and only if $\gcd(m, q-1) = 1$), permutation binomials ($x^m + ax^n$) are far more elusive. Despite extensive study, their structure and conditions for existence remain largely mysterious. This paper focuses on a specific, seemingly simple class of permutation binomials: $f(x) = x^m + ax^n$ over a prime field $\mathbb{F}_p$ (where $p > 5$). The core problem is to determine when such binomials cannot be permutation polynomials, particularly when the difference in exponents, $m-n$, has specific relationships with $p-1$.

Methods

The authors employ a combination of theoretical tools and existing criteria. A key technique is the use of Hermite's criterion, which provides necessary and sufficient conditions for a polynomial to be a permutation polynomial. Hermite's criterion states that a polynomial $f(x)$ over $\mathbb{F}_q$ is a permutation polynomial if and only if:

  1. For every $i$ such that $0 < i < q-1$, the reduction of $f(x)^i$ modulo $x^q - x$ has a degree less than $q-1$.
  2. $f(x)$ has exactly one root in $\mathbb{F}_q$.

The paper also leverages Lemmas 2.1 and 2.2. Lemma 2.1 states that for a permutation polynomial, the greatest common divisor of the degrees of its terms must be coprime to $q-1$. Lemma 2.2 provides a reduction technique, showing that if certain forms of permutation binomials don't exist, then related forms also don't exist. The proofs often involve constructing specific powers of the binomial and analyzing the degrees of the resulting terms modulo $p-1$ to find contradictions with Hermite's criterion. The strategy is to reduce the problem to specific cases of $p$ and then show that no such binomial can exist.

Datasets

Not discussed in the paper. This is a theoretical number theory paper, not an empirical one.

Key Insights and Ideas

  • The "simple" shapes are restrictive: The paper demonstrates that even for binomials with a seemingly simple structure ($x^m + ax^n$), there are strong constraints on their existence as permutation polynomials.
  • Exponent differences matter: The core insight is that the value of $\gcd(m-n, p-1)$ is critical. Specifically, if this gcd is 2 or 4, the binomial cannot be a permutation polynomial. This is a non-trivial result because it's much harder to prove non-existence than existence.
  • Reduction to specific cases: The authors effectively reduce the general problem to analyzing specific prime field structures (e.g., $p \equiv 1 \pmod 4$, $p \equiv 1 \pmod 8$, $p \equiv 5 \pmod 8$) and specific exponent relationships.
  • Hermite's criterion as a powerful tool: The paper showcases the power of Hermite's criterion in proving non-existence by forcing contradictions related to the degrees of polynomial powers.

Key Results

The main quantitative result is:

  • If $p > 5$ is prime and $f(x) = x^m + ax^n$ is a permutation polynomial over $\mathbb{F}_p$ (with $m > n > 0$ and $a \in \mathbb{F}_p^*$), then $\gcd(m-n, p-1) \notin \{2, 4\}$.

This result resolves conjectures for cases where $(p-1)/2$ or $(p-1)/4$ are prime. The proofs systematically rule out the possibility of such binomials existing for these specific gcd values by analyzing the degrees of polynomial powers and showing they violate Hermite's criterion.

Limitations and Future Work

Limitations: * The paper focuses on a specific shape of binomial ($x^m + ax^n$) and prime fields $\mathbb{F}_p$. The results may not directly extend to other field sizes (e.g., $\mathbb{F}_{p^k}$) or more complex polynomial forms. * The proofs are highly technical and rely on specific properties of prime fields and exponent relationships.

Future Work: The paper implicitly suggests further investigation into:

  • The existence of permutation binomials for other values of $\gcd(m-n, p-1)$.
  • The structure and non-existence of permutation binomials over general finite fields $\mathbb{F}_q$.
  • The characterization of permutation binomials with more than two terms.

Summary updated

Abstract

Suppose $x^m+ax^n$ is a permutation polynomial over ${\Bbb F}_p$, where $p&gt;5$ is prime and $m&gt;n&gt;0$ and $a\in{\Bbb F}_p^*$. We prove that $\gcd(m-n,p-1)\notin\{2,4\}$. In the special case that either $(p-1)/2$ or $(p-1)/4$ is prime, this was conjectured in a recent paper by Masuda, Panario and Wang.
BibTeX
@article{masuda2007nonexistence,
  author = {Ariane M. Masuda and Michael E. Zieve},
  title = {{Nonexistence of Permutation Binomials of Certain Shapes}},
  journal = {The Electronic Journal of Combinatorics},
  year = {2007},
  doi = {10.37236/1013},
}
Figure