A classification of permutation binomials of the form $x^i+ax$ over $\mathbb{F}_{2^n}$ for dimensions up to 8

Yi Li, Xiutao Feng, Qiang Wang

TL;DR

Researchers have finally cracked the classification of permutation binomials of the form $x^i + ax$ over finite fields of characteristic 2 for dimensions up to $n=8$. By combining exhaustive computer searches with rigorous mathematical proofs, they identified three entirely new general classes of these polynomials, including a rare family with a surprisingly large "index."

What Problem Does This Paper Address?

In the world of finite fields—mathematical structures with a finite number of elements—a permutation polynomial (PP) is a function that rearranges the elements of the field perfectly, like shuffling a deck of cards. These polynomials are vital for cryptography (designing secure ciphers), coding theory (error correction), and combinatorial designs.

While simple monomials ($x^i$) are well-understood, binomials (polynomials with two terms, like $x^i + ax$) are much trickier. Despite decades of study, mathematicians haven't been able to fully characterize which binomials act as permutations. This paper tackles a specific subset: binomials over fields of size $2^n$ for $n \leq 8$. The goal is to move beyond just finding examples and instead prove general "classes" or families that explain why these specific binomials work.

Methods

The authors employed a "search-and-prove" strategy:

  1. Exhaustive Search: They used computers to find every single permutation binomial of the form $x^i + ax$ for dimensions $n \leq 12$.
  2. The Index Approach: They classified these results using the "index" of a polynomial—a value that typically relates to the complexity of the polynomial's behavior. Most known PPs have small indices; finding ones with large indices is a significant discovery.
  3. Mathematical Proofs: To turn their search results into general theorems, they used two heavy-duty tools:
  4. Hermite’s Criterion: A classical method that uses the degrees of a polynomial's powers to check for the permutation property.
  5. The AGW Criterion: A modern, sophisticated method that uses commutative diagrams to translate a complex permutation problem on a large field into a simpler one on a smaller subset (like roots of unity).

Datasets

The "data" in this paper consists of the results of exhaustive searches over finite fields $\mathbb{F}_{2^n}$ for $n = 1, \dots, 12$. The authors present these findings in detailed tables (Tables 1-5), listing the exponent $i$, the index, and references to known literature. For $n \leq 8$, they successfully mapped every computer-generated example to either a known result or one of their three new theorems.

Key Insights and Ideas

  • Extension Fields vs. Prime Fields: The authors observed that in prime fields (where the size is just a prime number), the index of a permutation binomial is always small ($< \sqrt{q} + 1$). However, in extension fields (like $\mathbb{F}_{2^{12}}$), they found indices as large as 91. This highlights a fundamental difference in how these fields behave.
  • Large Index Discovery: One of the new classes discovered (over $\mathbb{F}_{q^3}$) has an index of $\frac{q^2+q+1}{3}$. This is considered "relatively large" and provides an answer to an open problem regarding the existence of such high-index PPs.
  • Mersenne Prime Connection: The paper notes that for $n=5$ and $n=7$, no non-linearized permutation binomials exist. This is explained by the fact that $2^5-1$ and $2^7-1$ are Mersenne primes, which severely restricts the possible algebraic structures.

Key Results

The authors proved three new general classes of permutation binomials:

  1. Theorem 7 (over $\mathbb{F}_{q^2}$): $f_1(x) = x^{6q-5} + ax$ is a PP under specific conditions on $a$ and $n$.
  2. Theorem 8 & Corollary 9 (over $\mathbb{F}_{q^3}$): Characterized $x^{(q^2+q)/2} + ax$ and $x^{q^2+q-1} + ax$. These explain several "mysterious" examples found in their search.
  3. Theorem 10 (over $\mathbb{F}_{q^4}$): A new class involving a complex exponent that generalizes the behavior seen in $\mathbb{F}_{2^8}$.

By the end of the paper, every permutation binomial of the form $x^i + ax$ over $\mathbb{F}_{2^n}$ for $n \leq 8$ is fully explained by either existing theory or these new theorems.

Limitations and Future Work

  • Dimension Limit: While the classification is complete for $n \leq 8$, the tables for $n=9, 10, 12$ still contain examples that are only "implicitly characterized." A full explicit classification for these higher dimensions remains open.
  • Characteristic $p$: This study focused on fields of characteristic 2 (binary-based). The authors suggest that extending this classification to fields of odd characteristic (where the base is an odd prime $p$) is a natural and necessary next step.
  • Trinomials: The paper focuses on binomials; moving to trinomials (three terms) would exponentially increase the complexity of the search and the proofs.

Summary updated

Abstract

Permutation polynomials with few terms (especially permutation binomials) attract many people due to their simple algebraic structure. Despite the great interests in the study of permutation binomials, a complete characterization of permutation binomials is still unknown. In this paper, we give a classification of permutation binomials of the form $x^i+ax$ over $\mathbb{F}_{2^n}$, where $n\leq 8$ by characterizing three new classes of permutation binomials. In particular one of them has relatively large index $\frac{q^2+q+1}{3}$ over $\mathbb{F}_{q^3}$.
BibTeX
@misc{li2023classification,
  author = {Yi Li and Xiutao Feng and Qiang Wang},
  title = {{A classification of permutation binomials of the form $x^i+ax$ over $\textbackslash\{\}mathbb\{F\}\_\{2^n\}$ for dimensions up to 8}},
  year = {2023},
  eprint = {2312.16908},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.16908},
}

Loading related content...

Figure