Source-linked AI summary
New classes of trace-form permutation polynomials and their compositional inverses
Kirpa Garg
TL;DR
The paper addresses the restriction of trace-form permutation-polynomial constructions to coefficients in proper subfields. It constructs and characterizes two families over Fq2, computes their compositional inverses using Kloosterman sums and finite-field equations, and reports that the new families extend known classes while remaining QM inequivalent to them.
Problem
Existing constructions of this shape restrict h's coefficients to a proper subfield of Fq2, leaving broader coefficient families insufficiently characterized.
Method
The paper analyzes permutation conditions using Kloosterman sums and finite-field equations, then derives compositional inverses for the characterized families.
Results
The paper characterizes two families with coefficients in Fq2, including cases with c2 ∉ Fq or γ ∉ Fq, and determines their compositional inverses.
Takeaways & Limitations
The families form a more general class containing known and new permutation polynomials, and the new polynomials are QM inequivalent to known classes.
Takeaways & Limitations
For m even, the inverse analysis states that β ≠ 0 and treats four cases as exhaustive; another stated branch assumes m is odd and additional coefficient conditions.
Abstract
from arXiv · showhide
We construct permutation polynomials of the form x + γTr^{q^2}_q(h(x)) over the finite field F_{q^2}. More precisely, we present two families ofpermutation polynomials whose coefficients range over all elements of the field rather than being restricted to a proper subfield. We also compute the compositional inverses of both families. Our techniques involve the evaluation of certain Kloosterman sums together with the analysis of some equations over finite fields, and we believe these can be of independent interest.
1. Introduction
The introduction situates trace-form permutation polynomials within finite-field applications and prior constructions, then identifies subfield-restricted coefficients as a genuine limitation. The paper addresses this gap by characterizing two broader families over Fq2 and computing their compositional inverses.
- Permutation polynomials are bijective finite-field maps with applications in coding theory, cryptography, combinatorial designs, and engineering.
- Trace-based forms connect switching methods with Boolean functions and linear structures, motivating their study in permutation-polynomial constructions.
- Earlier constructions of the target shape confined h's coefficients to a proper subfield of Fq2, and this restriction affects which trace conditions are reachable.
- The paper gives necessary and sufficient permutation conditions for c1, c2, c3, γ ∈ Fq2 and computes the corresponding compositional inverses.
- The resulting families include cases with c2 ∈ Fq2\Fq and γ ∈ Fq2\Fq, while specializing coefficients recovers several known results within one framework.
- The paper further studies quasi-multiplicative equivalence to known classes to assess whether the new families are genuinely distinct.
2. Preliminaries
The preliminaries establish finite-field trace notation and introduce Kloosterman sums and cubic-factorization results used in later arguments. These tools support the analysis of permutation conditions over fields of characteristic two.
- The paper sets q = 2^m and defines the trace Tr_2^n from F_2^n to F_2^m when m divides n.
- A Kloosterman sum is introduced using a non-trivial additive character of F_q and elements a, b ∈ F_q.
- The preliminaries recall a characterization of factors of cubic polynomials over finite fields of even characteristic.
- For f(x) = x^3 + ax + b, the recalled lemma relates factorization to the roots and cube status of y^2 + by + a^3.
3. Two families of permutation polynomials
The paper characterizes two families of permutation polynomials over Fq2, including cases with coefficients outside Fq, by reducing permutation questions to finite-field equations and trace-map surjectivity. It also establishes the corresponding criteria through cubic analysis and collision arguments, with small cases checked computationally.
- First family: The first family is analyzed by reducing f1(x)=α to a cubic equation in u∈Fq, whose unique solvability characterizes permutation behavior.The substitution x=α+γu converts the permutation test into Equation (3.1), and cubic factorization results support the analysis.
- First family: When m is odd, z↦z3 permutes Fq, giving a unique solution of the reduced equation and proving that f1 permutes Fq2.The argument uses gcd(3,q−1)=1 to establish uniqueness for every α∈Fq2.
- First family: Theorem 3.3 gives necessary and sufficient coefficient conditions for the first family, including cases with γ∈Fq2\Fq and coefficients ranging over Fq2.Special cases include the condition γ∈Fq2\Fq, m odd, and a trace constraint involving c1.
- Second family: The auxiliary map H is surjective onto Fq\{1}, supporting the second-family analysis, while exceptional small fields are handled directly by computation.For q∈{4,8}, the relevant statement is verified with SageMath; another remaining case is q=8.
- Second family: The second family is characterized by Theorem 3.8 through alternative conditions ensuring permutation, while violations are shown to produce collisions.The proof combines trace-map surjectivity, admissible parameter choices, and explicit collision constructions; the theorem applies to arbitrary c1,c2,c3,γ∈Fq2.
- Second family: The necessity proofs rule out non-permutation cases by constructing collisions, using trace constraints, zero-set bounds, and finite-field character-sum estimates.For example, zero-set counting yields an impossibility for q≥8, while Weil-bound arguments restrict remaining cases to q≤11.
4. Compositional Inverse of the permutation polynomials
The paper determines explicit compositional inverses for both constructed families of trace-form permutation polynomials over Fq2. The formulas cover all coefficient choices satisfying the permutation conditions, with separate case analyses according to q and coefficient parameters.
- Inverse of f1: For q = 2^m with m odd, the inverse analysis uses a cubic equation over Fq whose unique solution determines the preimage x = y + γs.The uniqueness follows from the bijectivity of cubing and of β ↦ (β + 1)^3 on Fq.
- Inverse of f1: Theorems 4.1 and 4.2 determine the compositional inverse of f1 for every coefficient choice making it a permutation polynomial of Fq2.The inverse formulas are organized by the cases in the permutation characterization, including γ outside Fq when q = 2^m with m odd.
- Consequences: When γ, c1, and c2 lie in Fq with c3 = 1, the first family is an involution over Fq2, and the results extend earlier inverse and involution results.The paper also states that the involution property extends to all c1, c2 ∈ Fq with γ ∈ Fq* in the indicated specialization.
- Inverse of f1: For q = 2^m with m even, the inverse of f1 is obtained through the depressed cubic r^3 + βr + βT = 0 and its resolvent, with cube roots constructed in Fq2.The even-m case uses conjugate roots and a norm condition to produce r ∈ Fq.
- Inverse of f2: Theorem 4.7 gives the compositional inverse of the second family f2 for q = 2^m with m odd.Its proof reduces the inverse problem to a cubic and distinguishes the cases P = 0, P ≠ 0 with Q = 0, and P ≠ 0 with Q ≠ 0.
5. Quasi-multiplicative equivalence
The paper tests whether its two permutation-polynomial families are quasi-multiplicatively equivalent to each other or to known classes. Exponent-set and coefficient comparisons establish inequivalence for the genuinely new parameter regimes while recovering known classes under specialization.
- Definition and strategy: QM equivalence permits an invertible exponent multiplier d and nonzero scalars α, β satisfying f(X) = αg(βX^d).The analysis proceeds by first comparing exponent sets and then comparing coefficients when exponent sets can match.
- Between the new families: The two families f1 and f2 are not QM equivalent when all their relevant coefficients are nonzero, because their exponent sets have different cardinalities.The sets have cardinalities in {7, 8} for f1 and {9, 10} for f2.
- Comparison with known classes: Members of f1 with c2 ∈ Fq2\Fq are not QM equivalent to the corresponding known classes with coefficients in F2.Coefficient matching would force a transformed c2 coefficient to remain outside Fq, contradicting the known-class coefficient restriction.
- Comparison with known classes: Specializing the coefficients of the new families to {0, 1} recovers known classes, while parameters outside the subfield yield genuinely new QM-inequivalent polynomials.The same conclusion applies when c2 lies in Fq but c1 lies in Fq2\Fq.
- Comparison with known classes: For f2, the additional exponents 2q − 1 and q2 − q + 1 support the same coefficient-comparison argument, proving inequivalence when c2 ∈ Fq2\Fq.These exponents are interchanged by multiplication by q modulo q2 − 1.
- Monomial-count boundary: QM equivalence preserves monomial count, excluding equivalence between full-support members of the new families and known classes with fewer monomials.The paper notes that certain known classes are nevertheless specializations of the first family.
6. Conclusion
The paper characterizes two families of permutation polynomials over Fq2 and determines their compositional inverses. The families contain known results while also producing new polynomials that are QM inequivalent to known classes.
- Conclusion: The paper characterizes two families of permutation polynomials with coefficients in Fq2 and determines their compositional inverses.These are the principal results summarized in the conclusion.
- Conclusion: The families subsume several known results, forming a more general class containing both previously known and new permutation polynomials.Specializations connect the constructed families to earlier classes.
- Conclusion: The new polynomials are verified to be QM inequivalent to the known classes.This establishes their distinction under the equivalence relation studied in Section 5.