🔢 mathematics

A new construction of permutation polynomials over $\mathbb{F}_{q^3}$

This paper introduces a novel systematic method to completely characterize and construct new families of permutation polynomials over $\mathbb{F}_{q^3}$ with simple coefficients for arbitrary prime powers $q$ , thereby resolving generalized conjectures in even characteristic through conceptually short proofs that avoid complex computations.

Original authors: Zhiguo Ding, Xu Song, Wei Xiong

Published 2026-05-18

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhiguo Ding, Xu Song, Wei Xiong

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 are running a massive, high-security sorting facility. Your job is to take a huge pile of unique items (let's call them "numbers") and rearrange them into a new order. The rule is strict: every single item must end up in a new spot, and no two items can ever land in the same spot. In the world of mathematics, this perfect rearrangement is called a permutation.

The paper you provided is about finding the perfect "sorting machines" (called polynomials) that can do this job for a very specific, complex type of warehouse: a field called $\mathbb{F}_{q^3}$ .

Here is a simple breakdown of what the authors, Zhiguo Ding, Xu Song, and Wei Xiong, achieved:

1. The Problem: The "Cube" Warehouse

Mathematicians have been studying these sorting machines for a long time. They are great at sorting "square" warehouses (fields like $\mathbb{F}_{q^2}$ ). There are thousands of known machines for squares.

But the "cube" warehouses ( $\mathbb{F}_{q^3}$ ) are much harder to crack. Until now, there were very few known machines that could sort these cubic fields without getting stuck or mixing up the items. The old methods were like trying to solve a 3D puzzle using only 2D tools—they just didn't fit well.

2. The New Method: A Two-Step Elevator System

The authors didn't just tweak the old tools; they built a completely new system. Instead of trying to sort the whole massive warehouse in one giant leap, they designed a two-step elevator system:

Step 1 (The Additive Floor): They first take the messy pile of numbers and move them to a simpler intermediate zone. Think of this as a "flat" floor where the items are arranged in neat, additive rows.
Step 2 (The Multiplicative Floor): From that flat floor, they move the items to an even simpler zone, a "circular" floor where the items are arranged in a ring.

By breaking the massive, confusing 3D problem into these two smaller, manageable steps, they could prove exactly when their sorting machine works. It's like saying, "To get to the top of the mountain, first climb the gentle slope, then take the steep path."

3. The Results: Simple Machines with Simple Parts

Using this new two-step method, the authors discovered several new families of sorting machines. What makes them special is their simplicity:

Few Parts: Most complex machines have hundreds of gears (terms). These new machines are like Swiss Army knives; they have very few parts (some have only 3, others 5 or 7).
Simple Materials: The "gears" they use are incredibly basic. They don't need complicated, weird coefficients. They mostly just use the number 1. It's like building a complex robot using only standard Lego bricks.

4. Solving Old Mysteries

The paper mentions that these new machines solve some long-standing riddles (conjectures) left by other mathematicians named Zhang, Zheng, Wang, Peng, and Li. Specifically, the authors figured out how to make these machines work perfectly when the "warehouse" has an even number of items (even characteristic), a scenario that had been tricky for others to solve.

5. The "Magic" Conditions

The authors didn't just say "these work." They gave a precise recipe for when the machine will work. It depends on the size of the warehouse ( $q$ ) and the settings of the machine ( $Q, R, S$ ).

They found that the machine works perfectly if the "settings" and the "warehouse size" don't share any common factors (a mathematical concept called being "coprime"). They translated this into a simple rule about how many times the number 2 divides into the settings. If the math checks out, the machine sorts the warehouse perfectly.

Summary

In short, this paper is a breakthrough in the world of mathematical sorting. The authors:

Invented a new two-step strategy to tackle a difficult 3D sorting problem.
Built simple, efficient machines (polynomials with few terms and simple numbers) that work for these 3D fields.
Solved old puzzles that other mathematicians had been stuck on for years.
Proved their results using short, clean logic rather than messy, complicated calculations.

They didn't just find one new machine; they found a whole new factory for building them.

Technical Summary: A New Construction of Permutation Polynomials over $\mathbb{F}_{q^3}$

Problem Statement
The paper addresses the construction and classification of permutation polynomials (PPs) over finite fields of cubic order, $\mathbb{F}_{q^3}$ . While systematic methods for constructing PPs over quadratic fields $\mathbb{F}_{q^2}$ are well-established (notably the method introduced in [8] which reduces the problem to rational functions on $\mathbb{P}^1(\mathbb{F}_q)$ ), the literature contains significantly fewer results for $\mathbb{F}_{q^3}$ . Existing constructions for cubic fields largely rely on variants of the quadratic method. The authors aim to develop a distinct, systematic approach to generate new families of PPs over $\mathbb{F}_{q^3}$ with simple coefficients and few terms, specifically resolving generalizations of conjectures by Zhang, Zheng, Wang, Peng, and Li in the case of even characteristic.

Methodology
The core innovation of this work is a "totally new systematic method" that employs a two-step reduction process, contrasting with the single-step reductions common in previous literature. The construction of a polynomial $f(X)$ over $\mathbb{F}_{q^3}$ is analyzed through the following decomposition:

Additive Reduction (Step 1): The permutation property of $f(X)$ on $\mathbb{F}_{q^3}$ is reduced to the permutation property of an associated function on the set of roots $\Gamma$ of the polynomial $X^{q^2} + X^q + X$ . This step utilizes an additive flavor, leveraging the structure of the kernel of the trace-like map $X \mapsto X^q - X$ .
Multiplicative Reduction (Step 2): The problem is further reduced from the set $\Gamma$ to the set of roots $\Lambda$ of the polynomial $X^{q+1} + X + 1$ . This step utilizes a multiplicative flavor, mapping the problem to the study of rational functions on $\Lambda$ .

The authors utilize specific lemmas (e.g., Lemma 3.1) to establish that a polynomial of the form $f(X) = L(X) + B(X) \circ (X^q - X) + (X^{q^2} + X^q + X) \circ C(X)$ permutes $\mathbb{F}_{q^3}$ if and only if:

$L(X) + (X^q - X) \circ B(X)$ permutes $\Gamma$ .
$L(X) + (X^{q^2} + X^q + X) \circ C(X)$ is injective on the cosets $u + \mathbb{F}_q$ .

The proofs rely on analyzing the permutation properties of rational functions on $\Lambda$ and $\Gamma$ , often reducing these to conditions involving greatest common divisors of exponents and the 2-adic valuation ( $\text{ord}_2$ ) of the field parameters.

Key Results
The paper presents several theorems and corollaries providing necessary and sufficient conditions for specific polynomial families to be permutation polynomials over $\mathbb{F}_{q^3}$ .

Theorem 1.1: Establishes conditions for polynomials of the form $f(X) = X^{Q+1} \circ (X^q - X) + (X^{q^2} + X^q + X) \circ cX^{R+S}$ to be PPs. The condition is $\gcd(q-1, (Q+1)(R+S)) = 1$ , which is equivalent to $p=2$ and $\text{ord}_2(k) \le \min(\text{ord}_2(\ell), \text{ord}_2(m-n))$ .
Corollary 1.2: Derives specific families of PPs with coefficients equal to 1:
- A trinomial $f_1(X) = X^{q^2Q+q} + X^{qQ+q^2} + X^{Q+1}$ .
- Three pentanomials ( $f_2, f_3, f_4$ ) with five terms.
- These results resolve two conjectures from [6] regarding pentanomials and provide a classification for the trinomial.
Theorem 1.4 & Corollary 1.5: Generalize the construction to include a coefficient $c \in \mathbb{F}_{q^3}$ , requiring $\gcd(q-1, Q+1)=1$ and $\text{Tr}_{\mathbb{F}_{q^3}/\mathbb{F}_q}(c) \neq 0$ . Setting $c=1$ yields a new family of PPs with coefficients 1.
Theorem 1.6 & 1.7: Prove that $(X^q - X) \circ X^{Q+1}$ (and specifically $(X^q - X) \circ X^3$ ) permutes the roots of $X^{q^2} + X^q + X$ under specific modular conditions ( $q \equiv 2 \pmod 3$ for the cubic case).
Theorem 1.8 & Corollary 1.9: Construct a family of PPs using the cubic term $X^3$ , valid for infinitely many characteristics where $q \equiv 2 \pmod 3$ . This includes a bivariate degree-3 polynomial that acts as a generalization of classical exceptional polynomials.

Significance and Claims
The authors claim that their proofs are "conceptually short and involve no complicated computations," contrasting with the lengthy algebraic manipulations often found in previous literature on PPs. The primary significance lies in:

Methodological Innovation: The introduction of a two-step reduction (additive followed by multiplicative) specifically tailored for $\mathbb{F}_{q^3}$ .
Resolution of Open Problems: The results resolve generalizations of conjectures by Zhang et al. in the even characteristic case.
Simplicity of Construction: The method yields PPs with very simple coefficients (often just 1) and a low number of terms (as few as three), which are of particular interest in applications requiring efficient implementation.
Infinite Families: The construction provides new families of PPs for infinitely many characteristics, rather than being restricted to specific small fields.

The paper does not propose new experimental applications or future engineering implementations but focuses strictly on the theoretical classification and construction of these polynomials.