🔢 mathematics

A Weil Sum Approach to Permutation Polynomials over Quadratic Extensions of Finite Fields

This paper characterizes specific classes of permutation polynomials over the quadratic extension field $\mathbb{F}_{q^2}$ by determining their exact number of zeros via Weil sums and explicitly provides their compositional inverses.

Original authors: Bidushi Sharma, Dhiren Kumar Basnet

Published 2026-06-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bidushi Sharma, Dhiren Kumar Basnet

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. Inside this facility, there is a special room called Finite Field Fq2. This room is filled with a specific number of unique items (let's call them "tokens").

The goal of this paper is to find a special set of instructions (a Permutation Polynomial) that can shuffle these tokens around. The rule for a "good" set of instructions is simple but strict: Every single token must move to a new spot, and no two tokens can ever land on the same spot. If even two tokens end up in the same spot, or if a token disappears, the instructions fail.

The authors, Bidshi Sharma and Dhiren Kumar Basnet, are like master locksmiths trying to figure out exactly which formulas work as these perfect shuffling instructions for this specific room.

The Tools: The "Weil Sum" Magic Wand

To test if a formula works, the authors use a mathematical tool called a Weil Sum. Think of this as a super-precise counter or a "magic wand."

Instead of trying to shuffle every single token one by one (which would take forever), the magic wand allows the authors to instantly count exactly how many tokens would end up in the same spot if they used a specific formula.

If the wand counts zero collisions for every possible scenario, the formula is a winner (a Permutation Polynomial).
If the wand counts one or more collisions, the formula is a loser.

The Two Formulas They Tested

The authors focused on two specific types of shuffling formulas:

Formula A: $x^q + bx^2 + cx + d$ $x^{q} + b x^{2} + c x + d$
- The Analogy: Imagine a machine that takes a token, squares it, adds a few other numbers, and spits it out.
Formula B: $x^{q+1} + bx^q + cx + d$ $x^{q + 1} + b x^{q} + c x + d$
- The Analogy: A slightly different machine that multiplies the token by itself one more time than the first machine, then adds other numbers.

They wanted to know: Under what specific conditions (what values for $b$ , $c$ , and $d$ ) do these machines shuffle the tokens perfectly without any collisions?

The Findings: What Worked and What Didn't

The paper splits its findings based on whether the "room" has an odd number of tokens or an even number of tokens.

1. When the room has an ODD number of tokens ( $q$ is odd)

Formula A ( $x^q + bx^2 + cx + d$ ):
- The Verdict: It only works if you turn off the "squaring" part ( $b=0$ ) and choose a very specific setting for the linear part ( $c$ ). If you try to include the squaring part ( $b \neq 0$ ), the machine always causes collisions. It's like trying to fit a square peg in a round hole; it just doesn't work.
Formula B ( $x^{q+1} + bx^q + cx + d$ ):
- The Verdict: The authors proved that if the room has an odd number of tokens, this formula never works as a perfect shuffler, no matter how you tweak the settings. It's a broken machine in this specific room. They even made a guess (a conjecture) that it probably never works even in other scenarios, but they couldn't prove it yet.

2. When the room has an EVEN number of tokens ( $q$ is even)

Formula A ( $x^q + bx^2 + cx + d$ ):
- The Verdict: Here, the machine can work! But it requires a very strict recipe. You either need to turn off the squaring part ( $b=0$ ) and pick a specific $c$ , OR you need to turn on the squaring part ( $b \neq 0$ ) but set $c$ to exactly 1. If you deviate from this recipe, the tokens crash into each other.
Formula B ( $x^{q+1} + bx^q + cx + d$ ):
- The Verdict: Just like in the odd-numbered room, this machine never works perfectly in an even-numbered room either. It always results in collisions.

The "Reverse Gear" (Compositional Inverses)

Once the authors found the formulas that did work (the perfect shufflers), they didn't stop there. They also figured out the Reverse Gear.

In a real-world analogy: If you have a machine that scrambles an egg perfectly, you also need a machine that can un-scramble it back into a raw egg. The authors provided the exact mathematical instructions to reverse their successful shuffling formulas. This is crucial because in many applications (like cryptography), you need to be able to undo the shuffle to read the original message.

Summary

In plain English, this paper is a rigorous test of two specific mathematical recipes. The authors used a powerful counting method (Weil sums) to determine exactly when these recipes successfully shuffle a set of numbers without any collisions.

They found that one recipe works only under very specific, narrow conditions (depending on whether the numbers are odd or even).
They found that the other recipe never works for the conditions they tested.
They also provided the "undo" button for the recipes that did work.

The paper is a "proof of concept" for these specific formulas, establishing clear rules for when they are safe to use as perfect shufflers and when they are destined to fail.

Technical Summary: A Weil Sum Approach to Permutation Polynomials Over Quadratic Extensions of Finite Fields

Problem Statement
The paper addresses the classification of permutation polynomials (PPs) over the quadratic extension of a finite field, $\mathbb{F}_{q^2}$ . Specifically, the authors investigate two distinct classes of polynomials:

$f(x) = x^q + bx^2 + cx + d$
$f(x) = x^q+1 + bx^q + cx + d$

The central problem is to determine the necessary and sufficient conditions on the coefficients $b, c, d \in \mathbb{F}_{q^2}$ such that these polynomials induce a bijection on $\mathbb{F}_{q^2}$ . The authors explicitly note that the polynomials under consideration do not fall into the Wan-Lidl type ( $x^s f(x^r)$ ) nor are they affine $q$ -polynomials, distinguishing them from many previously studied classes.

Methodology
The core methodology relies on characterizing a polynomial as a permutation if and only if the equation $f(x) = t$ has exactly one solution for every $t \in \mathbb{F}_{q^2}$ . Equivalently, the polynomial $f(x) + t$ must have exactly one zero in $\mathbb{F}_{q^2}$ .

To determine the exact number of zeros ( $M$ ) for these polynomials, the authors employ Weil sums (character sums) associated with the canonical additive character $\chi$ of $\mathbb{F}_{q^2}$ . The number of zeros is expressed via the identity:
$M = \frac{1}{q^2} \sum_{x \in \mathbb{F}_{q^2}} \sum_{y \in \mathbb{F}_{q^2}} \chi(y f(x))$
The analysis proceeds by separating cases based on the characteristic of the field ( $q$ odd vs. $q$ even) and the specific structure of the coefficients.

For $q$ odd: The authors utilize results on quadratic characters and specific evaluations of sums involving $x^q+1$ and quadratic terms. They derive explicit formulas for the number of zeros involving the quadratic character $\eta$ and trace maps.
For $q$ even: The approach involves analyzing the roots of auxiliary polynomials within the set of $(q+1)$ -th roots of unity ( $\mu_{q+1}$ ) and utilizing properties of self-conjugate reciprocal polynomials.
Inverse Construction: For the identified permutation polynomials, the authors derive their compositional inverses using Dickson matrices (for linearized components) and a general composition theorem for additive polynomials.

Key Contributions and Results

Characterization of $x^q + bx^2 + cx + d$ :
- Case $q$ is odd: Theorem 3.6 establishes that $x^q + bx^2 + cx + d$ is a permutation polynomial if and only if $b = 0$ and $c \notin \mu_{q+1}$ . The authors prove that if $b \neq 0$ , the polynomial never permutes $\mathbb{F}_{q^2}$ for odd $q$ .
- Case $q$ is even: Theorem 3.7 provides a complete characterization: the polynomial is a PP if and only if either ( $b=0$ and $c \in \mathbb{F}_q \setminus \{1\}$ ) or ( $b \in \mathbb{F}_q^*$ and $c = 1$ ).
Characterization of $x^{q+1} + bx^q + cx + d$ :
- Case $q$ is even: Proposition 3.8 proves that this polynomial is never a permutation polynomial over $\mathbb{F}_{q^2}$ , regardless of the coefficients. This result is derived independently of previous work (specifically [2]), offering a novel proof via Weil sums.
- Case $q$ is odd: Proposition 3.9 shows that if $b^q = c$ , the polynomial is never a PP. The authors also present Conjecture 3.10, suggesting that for odd $q$ , the polynomial is never a PP even when $b^q \neq c$ , though they note this remains unproven with current tools.
Compositional Inverses:
The paper explicitly constructs the compositional inverses for the valid permutation polynomials identified:
- For the odd $q$ case ( $b=0, c \notin \mu_{q+1}$ ), the inverse is given by $f^{-1}(x) = \frac{1}{c^{q+1}-1}(c^q x + x^q)$ .
- For the even $q$ cases, the inverses are derived using properties of $q$ -linearized polynomials and specific trace-based compositions.

Significance and Claims
The authors position their work as a direct application of Weil sums to a class of polynomials that are not affine $q$ -polynomials or of the Wan-Lidl type. The significance lies in:

Completeness: Providing a full characterization for the form $x^q + bx^2 + cx + d$ across both odd and even characteristics.
Novelty in Proof: Offering an independent proof for the non-existence of PPs of the form $x^{q+1} + bx^q + cx + d$ when $q$ is even, distinct from existing literature.
Methodological Utility: Demonstrating how character sums can be effectively used to count zeros and determine permutation properties for polynomials with mixed degrees ( $x^q$ and $x^2$ or $x^{q+1}$ ).

The paper concludes modestly, acknowledging that while the case $b^q \neq c$ for odd $q$ in the second polynomial class remains open, the established results provide a solid foundation for further investigation into the permutation behavior of these specific polynomial forms.