Permutation binomials over finite fields

Ariane M. Masuda, Michael E. ZieveTransactions of the American Mathematical Society 2007

TL;DR

This paper investigates permutation binomials of the form $x^m + ax^n$ over finite fields. The authors establish a new lower bound for the GCD of the exponents' difference and the field size minus one, showing it must be greater than $\sqrt{p}-1$ for such polynomials to permute the prime field $\mathbb{F}_p$. They also provide conditions for the existence of these polynomials over general finite fields $\mathbb{F}_q$.

What Problem Does This Paper Address?

Permutation polynomials are functions over finite fields that rearrange the field's elements. While simple polynomials like $x^m$ are well-understood (they permute $\mathbb{F}_q$ if $m$ is coprime to $q-1$), the behavior of binomials like $x^m + ax^n$ is significantly more complex. Previous work established non-existence results for these binomials, often relying on bounds for rational points on curves. However, there was a lack of precise conditions for their existence and tighter bounds, particularly for prime fields. This paper aims to fill this gap by providing a stronger non-existence criterion and an existence result for permutation binomials.

Methods

The paper employs a combination of techniques. For the non-existence results, particularly for prime fields, the authors leverage Hermite's criterion, which provides necessary and sufficient conditions for a polynomial to be a permutation polynomial. This involves analyzing the degrees of terms in powers of the polynomial modulo $x^q - x$. For the existence results over general finite fields, the authors utilize a geometric approach involving function fields and Weil's bound on the number of rational points on curves. This allows them to estimate the number of coefficients $a$ that yield permutation binomials for a given pair of exponents $(m, n)$.

Datasets

Not discussed in the paper. The research focuses on theoretical properties of polynomials over finite fields, not empirical evaluation on datasets.

Key Insights and Ideas

  • A Stronger Non-Existence Criterion: The paper's most striking result is the proof that if $x^m + ax^n$ permutes $\mathbb{F}_p$, then $\gcd(m-n, p-1) > \sqrt{p}-1$. This is a significant improvement over previous bounds and provides a much tighter condition for non-existence.
  • Geometric Approach to Existence: The use of function fields and Weil's bound to prove the existence of permutation binomials is a powerful and elegant technique. This approach allows for quantitative estimates on the number of such polynomials.
  • Connecting Prime and General Fields: While some results are specific to prime fields, the paper also addresses existence over general finite fields $\mathbb{F}_q$, bridging theoretical insights across different field types.
  • Heuristic for Randomness: The paper presents a heuristic argument suggesting that "random" permutation binomials are rare when the GCD condition is not met, providing intuition for why such polynomials might be sparse.

Key Results

  • Theorem 1.3: If $x^m + ax^n$ permutes $\mathbb{F}_p$ (with $m>n>0, a \in \mathbb{F}_p^*$), then $\gcd(m-n, p-1) > \sqrt{p} - (3/4) - (1/2) > \sqrt{p}-1$.
  • Theorem 1.2: If $x^m + ax^n$ permutes $\mathbb{F}_p$ (with $m>n>0, a \in \mathbb{F}_p^*$), then $p-1 \le (m-1) \max(n, \gcd(m-n, p-1))$. This is presented as a "least common generalization" of previous results.
  • Theorem 3.1: For fixed $m, n$ with $\gcd(n, k, q-1)=1$ and $q \ge 4$, if $\gcd(k, q-1) > 2q(\log\log q)/\log q$, then there exist permutation binomials of the form $x^m + ax^n$ over $\mathbb{F}_q$. The paper also provides bounds on the number of such coefficients $a$.

Limitations and Future Work

  • Prime Field vs. General Fields: While Theorem 1.3 provides a strong non-existence result for prime fields, the paper notes that this specific bound does not hold for non-prime fields, citing counterexamples.
  • Improving Bounds: The authors suspect that Theorem 1.3 can be improved, with a computer-assisted conjecture suggesting $\gcd(m-n, p-1) > p/(2\log p)$ for prime fields. Proving this improved bound would likely require new methods.
  • Heuristic vs. Reality: The heuristic for random permutation binomials is suggestive but doesn't preclude the existence of non-random families of counterexamples, especially over non-prime fields where subfield structures can play a role.
  • Explicit Constructions: While the paper proves existence, finding explicit constructions for permutation binomials remains a challenging area. The paper mentions that for certain small cases (e.g., $r=2$), explicit parameterizations are possible, but this becomes difficult for larger parameters.

Summary updated

Abstract

We prove that if x^m + c*x^n permutes the prime field GF(p), where m>n>0 and c is in GF(p)^*, then gcd(m-n,p-1) > sqrt{p} - 1. Conversely, we prove that if q>=4 and m>n>0 are fixed and satisfy gcd(m-n,q-1) > 2q*(log log q)/(log q), then there exist permutation binomials over GF(q) of the form x^m + c*x^n if and only if gcd(m,n,q-1) = 1.
BibTeX
@article{masuda2007permutation,
  author = {Ariane M. Masuda and Michael E. Zieve},
  title = {{Permutation binomials over finite fields}},
  journal = {Transactions of the American Mathematical Society},
  year = {2007},
}
Figure