🔢 mathematics

Several classes of permutation pentanomials

This paper introduces two large classes of permutation pentanomials over the finite field $\mathbb{F}_{q^2}$ for any prime $p$ and power $q=p^k$ , specifically constructed in the form $X^r B(X^{q-1})$ where $B(X)$ has coefficients primarily in the prime field.

Original authors: Zhiguo Ding

Published 2026-07-01

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhiguo Ding

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, magical lock with a specific number of slots. In the world of mathematics, this lock is a field called $\mathbb{F}_{q^2}$ , and the "slots" are all the possible numbers inside it.

A Permutation Polynomial is like a special master key. When you turn this key (plug a number into the formula), it shuffles every single slot in the lock exactly once. No two numbers end up in the same spot, and no spot is left empty. It's a perfect, chaotic dance where everyone gets a unique partner.

For a long time, mathematicians have been trying to find these "perfect shuffling keys" that are also simple. They want keys that don't have too many moving parts (terms) and use only simple numbers like $+1$ and $-1$ (like a coin flip: heads or tails).

The Big Discovery

The author, Zhiguo Ding, has found several new families of these perfect shuffling keys. Specifically, he found keys that are "pentanomials" (they have exactly five parts) or "quadrinomials" (four parts).

Think of these polynomials as recipes. Most recipes for these keys are messy, with dozens of ingredients. Ding's recipes are surprisingly clean:

They look like a main ingredient ( $X^r$ ) multiplied by a smaller, simpler recipe ( $B(X)$ ).
The smaller recipe usually has only five ingredients.
Almost all the ingredients are just $+1$ or $-1$. There is at most one "special" ingredient that might be different, but even that is usually just $0$, $1$, or $-1$.

How the Recipe Works

The paper presents a "Master Formula" (Theorem 1.1) that acts like a vending machine. You feed it three numbers ( $Q, R, S$ ) and a condition about the size of the lock ( $q$ ).

The Ingredients: The formula combines powers of $X$ (like $X^Q$ , $X^R$ , $X^S$ ) with $+1$ or $-1$.
The Secret Sauce: There is a special number, $b$ $b$ , which depends on a "root of unity." Think of a root of unity as a clock hand that spins around and lands exactly on the starting point after a certain number of steps.
- If the clock has 3, 4, or 6 hours (mathematically, $m \in \{3, 4, 6\}$ ), the secret sauce $b$ becomes a simple number ($0, 1,$ or $-1$).
- This is the "magic" that keeps the recipe simple. If the clock had 5 hours, the sauce would be a messy fraction, and the recipe would get complicated.
The Rules: The paper lists specific rules (like "the clock must spin 3 times" or "the numbers must add up to a specific remainder") that guarantee the key will work perfectly. If you follow these rules, the polynomial is guaranteed to be a perfect shuffler.

The "Shape-Shifting" Trick

The paper also reveals a fascinating secret about these keys (Theorem 1.14).

Imagine you have a complex, twisting maze (the polynomial). The author shows that if you look at it from a different angle (using a mathematical "lens" called linear equivalence), the maze isn't actually complex at all.

Under the right conditions, these fancy 5-part keys are actually just simple power functions in disguise.
It's like realizing that a complicated origami swan is just a flat piece of paper folded in a specific way. If you unfold it (change the perspective), it's just a simple line.
This means the author didn't just find new keys; he found a way to prove that these complex-looking keys are actually built on the simplest, most fundamental shuffling mechanism possible: just raising a number to a power.

Summary

In plain English, this paper is a cookbook for creating simple, efficient, and perfect shuffling keys for digital locks.

The Goal: Find formulas with very few terms (4 or 5) and simple coefficients ( $\pm 1$ ) that shuffle numbers perfectly.
The Method: Use a specific structure involving powers of $X$ and a "clock" (roots of unity) to ensure the math works out.
The Result: The author provides a list of rules that, if followed, guarantee you have a perfect key. He also proves that these complex-looking keys are secretly just simple power functions wearing a fancy costume.

This is pure mathematics: finding order, simplicity, and perfect patterns in the abstract world of numbers.

Technical Summary: Several Classes of Permutation Pentanomials

Problem Statement
The paper addresses the construction of permutation polynomials (PPs) over the finite field $\mathbb{F}_{q^2}$ , where $q = p^k$ for a prime $p$ and integer $k > 0$ . Specifically, the author focuses on polynomials of the form $f(X) = X^r B(X^{q-1})$ that possess at most five terms (pentanomials) or four terms (quadrinomials). A significant constraint in this work is that the coefficients of these polynomials are restricted to the set $\{1, -1\}$ , with the exception of at most one coefficient. The goal is to identify large classes of such polynomials that induce a permutation of $\mathbb{F}_{q^2}$ .

Methodology
The author employs a combination of algebraic number theory and the theory of rational functions over finite fields. The core methodology relies on the following steps:

Reduction to Roots of Unity: Utilizing Lemma 2.2 (based on prior work [2]), the problem of determining if $f(X) = X^r B(X^{q-1})$ permutes $\mathbb{F}_{q^2}$ is reduced to two conditions:
- $\gcd(r, q-1) = 1$ .
- The function $X^r B(X)^{q-1}$ permutes the set $\mu_{q+1}$ of $(q+1)$ -th roots of unity in $\mathbb{F}_{q^2}$ .
Rational Function Construction: The paper constructs specific rational functions $g(X) = \eta(X) \circ X^n \circ \rho(X)$ , where $\rho$ and $\eta$ are degree-1 rational functions involving a parameter $v$ . The parameter $v$ is chosen from $\mathbb{F}_q \cup \mu_{q+1}$ such that $v^2 \neq 1$ .
- When $v \in \mathbb{F}_q$ , the function $g(X)$ maps $\mu_{q+1}$ to itself.
- When $v \in \mu_{q+1}$ , the mapping properties depend on the specific structure of $v$ .
Coefficient Simplification via Roots of Unity: The author selects $v$ to be a primitive $m$ -th root of unity ( $m \ge 3$ ) in $\mathbb{F}_{q^2}$ . By choosing exponents $Q, R, S$ (which are powers of $p$ ) such that they satisfy specific congruences modulo $m$ , the resulting polynomial $B(X)$ derived from the rational function simplifies. Specifically, if $m \in \{3, 4, 6\}$ , the coefficients of the resulting polynomials collapse to values in $\{0, \pm 1\}$ .
Classification: The paper systematically analyzes cases where the exponents $(Q, R, S)$ satisfy congruences such as $\pm(1, 1, 1)$ or $\pm(1, 1, -1)$ modulo $m$ . This allows for the explicit construction of $B(X)$ with the desired sparse structure (at most five terms).

Key Contributions and Results

General Classification Theorems (Theorems 1.2 and 1.3): The paper establishes necessary and sufficient conditions for polynomials of the form $X^r B(X^{q-1})$ to be permutation polynomials over $\mathbb{F}_{q^2}$ .
- Theorem 1.2 covers cases where $B(X)$ is derived from $X^{Q+R+S}$ , resulting in polynomials with terms like $X^{Q+R+S} - X^Q - X^R - X^S + b$ .
- Theorem 1.3 covers cases where $B(X)$ is derived from $X^{Q+R-S}$ , resulting in different structural forms.
- Both theorems provide precise conditions on $q \pmod m$ and the greatest common divisors of the exponent sums with $q \pm 1$ .
Main Result (Theorem 1.1): This theorem synthesizes the previous findings to present two large classes of permutation polynomials with at most five terms. The coefficients are explicitly $\pm 1$ (except for at most one term), and the conditions for permutation are detailed based on the congruence of $q$ modulo $m$ and the specific values of $(Q, R, S) \pmod m$ .
Special Cases (Corollaries 1.5 – 1.10): The paper derives specific results for $m \in \{3, 6\}$ and $m=4$ .
- For $m \in \{3, 6\}$ , the constant $b$ becomes $\pm 1$ , yielding permutation pentanomials with coefficients strictly in $\{1, -1\}$ .
- For $m=4$ , the constant $b$ becomes $0$, yielding permutation quadrinomials with coefficients in $\{1, -1\}$ .
- These corollaries provide explicit lists of polynomial forms and the exact modular arithmetic conditions required for them to be PPs.
Structural Equivalence (Theorem 1.14): The paper demonstrates that in the special case where $r = Q + R + S$ , the constructed permutation polynomials are $\mathbb{F}_q$ -linearly equivalent to much simpler monomials (e.g., $X^{Q+R+S}$ ) or product maps (e.g., $(X^{Q+R+S}, Y^{Q+R+S})$ ). This equivalence provides an alternative proof for the special case and clarifies the algebraic structure of the constructed polynomials.

Significance and Claims
The paper claims to present "several classes" of permutation polynomials with a high degree of sparsity (at most five terms) and restricted coefficients ( $\pm 1$ ). The significance lies in the systematic derivation of these classes using roots of unity to force coefficient simplification.

The author notes that while the argument can be extended to sums of more than three powers of $p$ , the resulting polynomials would have more terms and appear "less elegant." Therefore, the paper focuses on the cases yielding pentanomials and quadrinomials. The results are presented as direct consequences of the classification theorems, offering a unified framework for generating these specific types of permutation polynomials over $\mathbb{F}_{q^2}$ . The work does not propose new applications or experimental implementations but rather contributes to the theoretical classification of sparse permutation polynomials with simple coefficients.

The Big Discovery

How the Recipe Works

The "Shape-Shifting" Trick

Summary

More like this