On Permutation Trinomials and Complete Permutation Polynomials via Fiber Criteria over Finite Fields

This paper provides concise proofs for recent permutation polynomial results and establishes a general framework for constructing complete permutation polynomials over finite fields by combining Zieve's fiber criterion with the AGW criterion, specifically utilizing fiber decompositions over the cube roots of unity.

The Gist

Imagine you are a master locksmith trying to design a special key. In the world of mathematics, this "key" is a polynomial (a fancy equation), and the "lock" is a finite field (a small, closed universe of numbers).

Usually, a good key just needs to open the door once: it must take every number in the universe and shuffle them around so that no two numbers end up in the same spot. Mathematicians call this a Permutation Polynomial.

But this paper is about a much harder challenge: the Complete Permutation Polynomial. This is a "super-key." Not only must the key shuffle the numbers perfectly, but if you add the original number to the result (like adding a second layer of complexity), it still has to shuffle them perfectly without any collisions. It's like asking a magician to shuffle a deck of cards perfectly, and then, while the cards are still in the air, ask them to shuffle themselves again perfectly.

Here is how the authors, Chahrzade, Asmae, and Omar, cracked this difficult problem:

1. The Old Way vs. The New Shortcut

Previously, proving these "super-keys" worked was like checking every single lock in a massive castle one by one. It was slow, tedious, and prone to errors.

The authors found a shortcut. They realized that instead of checking the whole castle, you only need to check a tiny, specific group of three "guardians" (mathematicians call this a subgroup of cube roots of unity).

• The Analogy: Imagine you have a giant machine that sorts millions of marbles. Instead of watching the whole machine, you realize that if the machine sorts a specific group of three marbles correctly, the rest of the millions will fall into place automatically.
• The Tool: They used a "fiber criterion" (a fancy way of saying "checking the threads"). They looked at how the equation behaves on these three guardians. If the guardians are happy, the whole system works.

2. The "Three Guardians" Strategy

The authors focused on fields where the number of elements is one more than a multiple of 3 (like 7, 13, 19, etc.). In these worlds, there is a special trio of numbers that act like a clock face: 1, $\omega$, and $\omega^2$.

They proved that to make a "super-key" work, you just need to verify two things:

1. The Coprime Check: Make sure the exponent in the equation doesn't get stuck in a loop with the size of the field.
2. The Trio Check: Make sure the equation shuffles those three specific guardians perfectly.

If these two checks pass, the equation is a valid Permutation Polynomial. This turned years of complex calculations into a few lines of arithmetic.

3. The "Super-Key" Challenge (Complete Permutation)

The real magic happens in the second half of the paper. They wanted to find "super-keys" (Complete Permutation Polynomials).

To do this, they combined two powerful tools:

• Zieve's Criterion: The shortcut mentioned above.
• The AGW Criterion: A framework that breaks a big problem into smaller "fibers" (groups of numbers that behave similarly).

They discovered a General Rule for creating these super-keys. It's like a recipe:

• Step 1: Pick a number $r$ that plays nice with the field size.
• Step 2: Define a function $c$ that acts on our three guardians.
• Step 3: Check if the "fiber maps" (how the numbers move within their groups) are injective (no two numbers collide).
• Step 4: Check if the guardians themselves get shuffled correctly.

4. The "Magic Number" 9

The most exciting discovery is a specific condition for when this recipe works best. The authors found that if the size of your number universe ($q$) is one more than a multiple of 9 (e.g., 19, 37, 43), the math simplifies beautifully.

• The Analogy: It's like a dance. If the music is in a 9-beat rhythm, the dancers (the numbers) move in a perfect, predictable circle. You can easily predict where everyone will land.
• The "Scalar" Specialization: In this specific rhythm, the complex movement of the numbers simplifies to just "multiplying by a constant." It becomes as easy as checking if a number is zero or not. This allows them to generate infinite families of these "super-keys" very easily.

5. Why the Rule is Strict (The Counterexamples)

The authors didn't just show what works; they showed what fails. They proved that if you try to use their recipe in a universe where the size is only "one more than a multiple of 3" but not 9 (like 7 or 31), the dance breaks.

• The Analogy: Imagine trying to dance a waltz (3 steps) to a 9-beat rhythm. It works. But if you try to dance a waltz to a 7-beat rhythm, you trip over your own feet.
• They showed concrete examples where the "super-key" failed to open the lock because the rhythm (the math condition) wasn't right. This proves their rule isn't just a lucky guess; it's a necessary condition.

Summary

In simple terms, this paper is a user manual for building perfect mathematical shufflers.

1. Old way: Check everything manually (hard).
2. New way: Check just three special numbers (easy).
3. Super-way: If the universe size follows a specific "9-beat" rhythm, you can build these perfect shufflers using a simple, repeatable recipe.
4. Warning: If you ignore the rhythm, the recipe fails.

The authors have given mathematicians and cryptographers a powerful, easy-to-use toolkit to generate secure, complex number patterns for things like encryption and coding, all by focusing on a tiny group of three numbers.

Technical Summary

Here is a detailed technical summary of the paper "Permutation Trinomials and Complete Permutation Polynomials via Fiber Criteria over Finite Fields" by Bouyacoub, El-Baz, and Kihel.

1. Problem Statement

The paper addresses the construction and verification of Permutation Polynomials (PPs) and Complete Permutation Polynomials (CPPs) over finite fields $\mathbb{F}_q$.

• Permutation Polynomial: A polynomial $f \in \mathbb{F}_q[X]$ that induces a bijection on $\mathbb{F}_q$.
• Complete Permutation Polynomial: A polynomial $f$ such that both $f$ and $f + X$ are permutation polynomials. CPPs are significantly harder to construct due to the rigid condition imposed by the additive term $X$.

The authors focus on specific families of trinomials of the form:
$$f(X) = X^r \left( X^{2s} + \delta X^s + \gamma \right)$$
where $s = (q-1)/3$ and $q \equiv 1 \pmod 3$. The goal is to provide new, simplified proofs for existing results regarding PPs and to establish a general framework for constructing CPPs of this form.

2. Methodology

The authors employ two primary theoretical tools to reduce the complexity of verifying permutation properties over the large field $\mathbb{F}_q$ to computations on a small subgroup:

1. Zieve's Theorem (Fiber Criterion):

   • Applicable to polynomials of the form $f(X) = X^r h(X^{(q-1)/d})$.
   • Reduces the permutation test over $\mathbb{F}_q$ to two conditions:
     1. $\gcd(r, (q-1)/d) = 1$.
     2. The map $u \mapsto u^r h(u)^{(q-1)/d}$ is a permutation of the multiplicative subgroup $\mu_d$ (roots of unity of order $d$).
   • In this paper, $d=3$, reducing the verification to the 3-element group $\mu_3 = \{1, \omega, \omega^2\}$.

2. The AGW Criterion (Akbary-Ghioca-Wang):

   • A fiber-wise framework that decomposes a bijection on a set $A$ into a permutation of fibers and a bijection on the base set.
   • Applied here with $A = \mathbb{F}_q^*$, $S = \bar{S} = \mu_3$, and the projection map $\pi(x) = x^s$.
   • This allows the authors to handle the additive term $X$ in CPPs ($F(X) = f(X) + X$), which breaks the multiplicative structure required for Zieve's theorem alone.

3. Key Contributions

A. Simplified Proofs for Existing PP Results

The authors provide short, transparent alternative proofs for recent results by Bousalmi, Bayad, and Derbal regarding permutation trinomials.

• Method: By applying Zieve's criterion with $d=3$, they reduce the verification of complex trinomial conditions to explicit arithmetic computations on the group $\mu_3$.
• Result: They confirm that specific families of trinomials $X^r(X^{2s} + \delta X^s + \beta)$ are PPs under specific arithmetic constraints on parameters $\delta, \gamma$, and $r$.

B. General Framework for Complete Permutation Polynomials (CPPs)

The paper's main contribution is a general criterion for determining when $f(X) = X^r c(X^s)$ is a CPP over $\mathbb{F}_q$ (where $q \equiv 1 \pmod 9$).

• Theorem 4.1: Establishes four necessary and sufficient conditions for $F(X) = f(X) + X$ to be a CPP:
  1. Coprimality: $\gcd(r, s) = 1$ and $\gcd(r, 3) = 1$.
  2. Fiber Injectivity: A specific map $\phi_u$ defined on the kernel of the projection must be injective.
  3. Well-definedness: A derived value $v(u)$ must be independent of the fiber representative.
  4. Base Permutation: The induced map $\bar{\psi}(u) = u \cdot v(u)$ must permute $\mu_3$.

C. Scalar Fiber Specialization

The authors identify a practical subclass where $r \equiv 1 \pmod s$ (specifically $r = 1 + ks$).

• Simplification: Under this condition, the fiber maps become scalar multiplications. The four complex conditions collapse into two simple checks:
  1. Non-vanishing of a scalar term $\tau(u) \neq 0$.
  2. The map $u \mapsto u \cdot \tau(u)^s$ is a permutation of $\mu_3$.
• Requirement: This specialization strictly requires $q \equiv 1 \pmod 9$ to ensure $\gcd(r, 3) = 1$.

4. Results and Examples

• Explicit Constructions: The authors generate explicit families of CPPs over finite fields $\mathbb{F}_{109}$, $\mathbb{F}_{163}$, and $\mathbb{F}_{199}$. In these examples, they define specific coefficients $\delta$ and exponents $r$ that satisfy the scalar fiber criterion, proving the polynomials are CPPs.
• Sharpness of Conditions (Counterexamples):
  • The paper demonstrates that the condition $q \equiv 1 \pmod 9$ is essential for their construction.
  • Counterexample 1 ($q=7$): $7 \equiv 1 \pmod 3$but$7 \not\equiv 1 \pmod 9$. The constructed polynomial fails to be a permutation (maps three distinct elements to 0).
  • Counterexample 2 ($q=31$): $31 \equiv 4 \pmod 9$. The constructed polynomial fails injectivity (maps distinct elements 5 and 8 to the same value).
  • These examples prove that the arithmetic conditions derived in the paper are not merely sufficient but necessary for the specific construction method used.

5. Significance

• Theoretical Unification: The paper unifies the treatment of permutation trinomials and complete permutation polynomials by leveraging fiber decomposition over the cube roots of unity.
• Efficiency: It replaces lengthy case-by-case analyses with systematic, short proofs based on group-theoretic properties of $\mu_3$.
• Practical Application: The "Scalar Fiber Specialization" provides a recipe for easily generating and verifying new CPPs, which are crucial for applications in coding theory, cryptography (e.g., S-box design), and pseudorandom sequence generation.
• Boundary Definition: By providing counterexamples, the paper clearly delineates the limits of the proposed method, showing that the $q \equiv 1 \pmod 9$ constraint is a fundamental arithmetic barrier for this specific class of constructions.