🔢 mathematics

A Complete Classification of a Reciprocal Degree-Five Quadrinomial Family over F_{q^2}

This paper provides a complete classification of a reciprocal degree-five quadrinomial family over $\mathbb{F}_{q^2}$ for all odd prime powers $q$ , revealing that the results depend sharply on $q \pmod 4$ : yielding infinite families governed by quadratic-character conditions when $q \equiv 1 \pmod 4$ , and restricting solutions to only the sporadic fields $q = 7, 19, 23$ when $q \equiv 3 \pmod 4$ due to character-sum obstructions.

Original authors: Brian M. Woody

Published 2026-07-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Brian M. Woody

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 a master locksmith trying to design a special kind of key. This key isn't for a physical door, but for a mathematical "universe" called a finite field (specifically, a quadratic extension denoted as $\mathbb{F}_{q^2}$ ).

In this universe, numbers don't go on forever; they wrap around like the hours on a clock. Your goal is to create a specific type of mathematical formula (a polynomial) that acts as a perfect shuffler. When you feed every number in this universe into your formula, it must spit out every number exactly once, with no duplicates and no missing numbers. In math terms, this is called a Permutation Polynomial.

This paper by Brian M. Woody is the ultimate guide to finding all the perfect shufflers in a very specific, tricky family of formulas. Here is the breakdown of his discovery using everyday analogies.

1. The Family of Formulas

The author is studying a specific "family" of four-term formulas (quadrinomials). Think of this family as a set of recipes that look almost the same, but have two adjustable knobs, labeled $a$ and $b$ .

The formula is: $F(x) = x^5 + a x^{q+4} + b x^{4q+1} + \frac{a}{b} x^{5q}$ .
The "knobs" $a$ and $b$ are numbers chosen from a smaller, simpler universe ( $\mathbb{F}_q$ ).
The author excludes "broken" recipes where the knobs are set to zero or specific values that make the formula collapse into a constant (like a broken key that just says "1" no matter what you turn).

2. The Two-Step Test

To see if a recipe works as a perfect shuffler, the author uses a two-step inspection process, which he calls the "Root-of-Unity Reduction."

Step 1: The Size Check. First, he checks if the "power" of the formula (the number 5) plays nicely with the size of the universe. If the universe size is a multiple of 5, the formula fails immediately.
Step 2: The Circle Test. If the size check passes, the problem shrinks down to a smaller, simpler stage: a "unit circle" of numbers. The author asks: Does this formula shuffle the numbers on this circle perfectly?

3. The Great Split: Two Different Worlds

The most exciting part of the paper is that the answer depends entirely on the size of the universe ( $q$ ). The author finds that the behavior splits into two completely different worlds, like a fork in the road.

World A: The "Infinite Highway" ( $q \equiv 1 \pmod 4$ )

In this world, the universe size leaves a remainder of 1 when divided by 4.

The Discovery: Here, you can find infinite perfect shufflers.
The Rule: To find them, you just need to tune the knob $b$ correctly. There are two specific "sweet spots" for $b$ (solutions to quadratic equations like $b^2 + 2b + 5 = 0$ ).
The Catch: Once you pick a $b$ from one of these sweet spots, you also need to check a "parity" condition (a mathematical property called the quadratic character). If the parity matches the sweet spot, any value for the other knob ( $a$ ) works!
Analogy: It's like finding a specific type of gear (the $b$ knob). Once you find the right gear, you can attach any handle (the $a$ knob) to it, and the machine will run perfectly. This creates an endless supply of working keys.

World B: The "Sporadic Islands" ( $q \equiv 3 \pmod 4$ )

In this world, the universe size leaves a remainder of 3 when divided by 4.

The Discovery: Here, the "infinite highway" disappears. The math becomes much stricter.
The Obstacle: The author proves that for almost all universe sizes in this world, the formula will inevitably create "collisions" (two different inputs giving the same output), making it a bad shuffler.
The Exception: There are only three tiny islands where perfect shufflers exist: universe sizes 7, 19, and 23.
The Analogy: Imagine looking for a needle in a haystack. In this world, the haystack is so big that you can prove there are no needles in 99% of it. You only find needles in three very specific, tiny piles. For any universe larger than 500 in this category, you can be 100% sure no perfect shufflers exist.

4. The "Collision" Detective Work

How did the author prove this? He looked for "collisions."

Imagine two people, Alice and Bob, entering the formula. If they come out with the same result, the formula has failed.
The author derived a complex equation (the "Collision Factorization") that predicts when Alice and Bob will collide.
The Magic Trick: He discovered that whether a collision happens depends only on the knob $b$ , not on $a$ . This was the key that allowed him to separate the problem into the two worlds described above.
In World A, he used a "character sum" argument (a way of counting patterns) to show that if you pick the wrong $b$ , collisions are guaranteed. If you pick the right $b$ , collisions vanish.
In World B, he used geometry (conics) to show that collisions are unavoidable unless the universe is tiny.

5. The Final Verdict

The paper provides a complete classification. It tells you exactly which knobs to turn to get a perfect shuffler for any odd-sized universe:

If the universe is "World A" type: Pick $b$ from the two specific equations and check the parity. If it matches, you have an infinite family of solutions.
If the universe is "World B" type: You are out of luck unless your universe is size 7, 19, or 23. If it is one of those, there are a few specific $b$ values that work.
For all other cases: No perfect shufflers exist in this family.

Summary

Brian Woody took a complex mathematical puzzle involving shuffling numbers in a finite universe and solved it completely. He found that the solution is either an infinite highway of possibilities (for certain universe sizes) or a tiny, scattered set of exceptions (for others). He proved that for large universes of the "wrong" type, it is mathematically impossible to find a solution, leaving only a few small, special cases where the magic works.

Technical Summary: A Complete Classification of a Reciprocal Degree-Five Quadrinomial Family over $\mathbb{F}_{q^2}$

Problem Statement
The paper addresses the classification of permutation polynomials (PPs) over the quadratic extension field $\mathbb{F}_{q^2}$ , where $q$ is an odd prime power. Specifically, it investigates a reciprocal degree-five quadrinomial family defined by:
$F_{a,b}(x) = x^5 + ax^{q+4} + bx^{4q+1} + \frac{a}{b}x^{5q}$
where $a, b \in \mathbb{F}_q$ . The study focuses on nondegenerate cases where $b \neq 0, \pm 1$ and $a \neq \pm b$ . The goal is to determine the necessary and sufficient conditions on $q$ , $a$ , and $b$ such that $F_{a,b}(x)$ induces a bijection on $\mathbb{F}_{q^2}$ .

Methodology
The author employs the standard root-of-unity reduction (Akbary–Ghioca–Wang criterion), which reduces the permutation problem on $\mathbb{F}_{q^2}$ to two conditions:

Coprimality: $\gcd(5, q-1) = 1$ (equivalently $q \not\equiv 1 \pmod 5$ ).
Unit Circle Permutation: The induced rational function $R(z) = \frac{h^*(z)}{h(z)}$ must permute the unit circle $\mu_{q+1} = \{z \in \mathbb{F}_{q^2} : z^{q+1} = 1\}$ , where $h(z) = 1 + az + bz^4 + \frac{a}{b}z^5$ .

The core technical innovation lies in the collision factorization. By analyzing the equation $R(x) = R(y)$ for distinct $x, y \in \mu_{q+1}$ , the author demonstrates that the condition for a collision depends solely on the parameter $b$ and is independent of $a$ . This factorization leads to a polynomial $K_b(x, y)$ whose vanishing determines injectivity.

The analysis proceeds by reducing the collision condition to a trace equation involving $V = v + v^{-1}$ and $U = u^2 + u^{-2}$ (where $u=xy, v=x/y$). This reduction transforms the problem into studying the existence of solutions to specific quadratic equations and character sums on conics. The methodology splits into two distinct branches based on the residue of $q$ modulo 4:

Branch $q \equiv 1 \pmod 4$ : The author utilizes a "sign-switch lifting" argument and character-sum estimates (Weil bounds) to show that for large $q$ , collisions exist unless specific quadratic conditions on $b$ are met.
Branch $q \equiv 3 \pmod 4$ : The problem is converted into a character-sum problem on a nonsingular conic $C_b$ . The author proves that for sufficiently large $q$ , the number of points on this conic satisfying specific square-class constraints is strictly positive, implying the existence of collisions.

Key Contributions and Results
The paper provides a complete classification of the nondegenerate members of this family for all odd prime powers $q$ . The Main Theorem (1.1) establishes that $F_{a,b}$ is a permutation polynomial if and only if one of the following holds:

Infinite Branch ( $q \equiv 1 \pmod 4$ ):
- $q \not\equiv 1 \pmod 5$ .
- $b$ $b$ satisfies one of two quadratic equations with specific quadratic character constraints:
  - $b^2 + 2b + 5 = 0$ and $\chi(b) = 1$ , OR
  - $b^2 - 2b + 5 = 0$ and $\chi(b) = -1$ .
- Here, $\chi$ denotes the quadratic character of $\mathbb{F}_q$ .
- For any such valid $b$ , any nondegenerate value of $a$ with $a \neq \pm b$ works.
Sporadic Branch ( $q \equiv 3 \pmod 4$ ):
- The only solutions occur for specific small fields and parameters:
  - $(q, b) \in \{(7, 2), (7, 3), (7, 4), (7, 5), (19, 2), (19, 4), (19, 5), (19, 7), (23, 7), (23, 16)\}$ .
- For any such valid $(q, b)$ , any nondegenerate value of $a$ with $a \neq \pm b$ works.

Technical Details of the Proof:

Large Field Elimination: For $q > 289$ in the $q \equiv 1 \pmod 4$ branch and $q > 500$ in the $q \equiv 3 \pmod 4$ branch, the author uses Weil bounds on character sums to prove that "generic" parameters $b$ always yield collisions, thereby eliminating them.
Finite Verification: The remaining small fields are verified exhaustively using a computational script. The verification confirms that no other sporadic cases exist and validates the theoretical bounds.
Counting: The paper calculates the number of genuine quadrinomials (excluding cases where terms cancel or coefficients vanish) for both infinite and sporadic branches.

Significance
The paper claims significance in providing a complete classification for a specific reciprocal degree-five quadrinomial family, a problem that had not been fully resolved. The work highlights a sharp dichotomy in the behavior of these polynomials:

For $q \equiv 1 \pmod 4$ , the classification yields infinite families governed by quadratic character conditions.
For $q \equiv 3 \pmod 4$ , the classification yields only sporadic examples, with a "square-class obstruction" preventing solutions in large fields.

The author positions this work as complementary to existing sparse permutation polynomial constructions (such as those by Ding, Zieve, Özbudak, and others). Unlike previous works that often rely on characteristic-power support patterns or lower-degree rational functions, this family features a coefficient-linked structure where the induced rational map has true degree five. The independence of the collision condition from the parameter $a$ is identified as a key structural feature that simplifies the classification. The results extend the known landscape of permutation polynomials over finite fields, offering new examples for applications in finite geometry, coding theory, and cryptography.