New Classes of Permutation Binomials and Permutation Trinomials over Finite Fields

• Permutation polynomials map a finite field onto itself bijectively and have applications in finite-field theory, coding theory, cryptography, combinatorial design, and communication theory.Source: §1 · p. 1
• Permutation binomials and trinomials have simple algebraic forms and have figured in results concerning the Welch conjecture and Ree-Tits symplectic spreads.A permutation trinomial over F_2^(2m+1) was a major ingredient in a proof of the Welch conjecture; Ball and Zieve's class provided a way to prove the construction of Ree-Tits symplectic spreads of PG(3, q).Source: §1 · p. 1
• The paper constructs new permutation binomials over finite fields with even extensions and new permutation trinomials over finite fields of even characteristic.It reviews known binomials over F_q^2 and trinomials over F_2^m; its stated approach to new binomials uses Hermite's criterion and solution counts for special equations.Source: §1 · p. 2

• Multiplicatively equivalent polynomials satisfy f(x) = g(x^d) for an exponent d coprime to q − 1; this preserves term count and permutation status.The property applies in particular to permutation binomials and trinomials.Source: §2 · p. 2
• The paper distinguishes multiplicative equivalence from the linear equivalence used in earlier references, which allows transformations of the form f(x) = c g(ax + b) + d.Source: §2 · p. 2
• Lemma 2.2 gives a sufficient transformation from x^r0(x^((q−1)/d) + a) to x^(r0+d)(x^((q−1)/d) + a) under its stated gcd condition.Source: §2 · p. 2
• Hermite's criterion tests permutation status by requiring exactly one root in F_q and specified reductions of powers of f modulo x^q − x.The stated power condition ranges over 1 ≤ t ≤ q − 2 with t not congruent to 0 modulo the characteristic.Source: §2 · p. 2
• For q = 2^k, x + x^2 + x^4 permutes F_q exactly when k is not divisible by 3.Source: §2 · p. 3

• A binomial x^m + ax^n can, after substituting x^t modulo x^q − x, be written in the form x^r(x^((q−1)/d) + a).Here 0 < n < m < q, a is nonzero, gcd(t, q − 1) = 1, and d divides q − 1.Source: §3 · p. 3
• The section focuses on permutation binomials over F_q^2, the finite fields with even extensions.Source: §3 · p. 3
• The reduction is stated as the reason the paper may restrict its study to binomials of the displayed standard form.Source: §3 · p. 3

• Theorem 3.1 gives a criterion for x^r(x^((q^2−1)/d) + a) to permute F_q^2, including the condition that −a is not in μ_d and a gcd bound.The supplied condition also requires η ∈ μ_((q^2−1)/d) for all η ∈ μ_2d; the bound is gcd(2d, 2r + (q^2−1)/d) ≤ 2.Source: A. Known permutation binomials over Fq2 · p. 3
• Theorem 3.2 states that x^(r+d(q−1)) + β^−1x^r permutes F_q^2 if and only if three listed gcd and non-equality conditions hold.The conditions include gcd(r, q − 1) = 1, gcd(r − d, q + 1) = 1, and (−β)^((q+1)/gcd(q+1,d)) ≠ 1.Source: A. Known permutation binomials over Fq2 · p. 3
• The reviewed known classes also include binomials of the forms ax + x^(5q−4) and ax + x^(3q−2), with parameter cases listed for particular q values.Source: A. Known permutation binomials over Fq2 · pp. 3–4

• For f(x) = x(x^(q+1) + a), permutation over Fq2 holds exactly when q is not 1 modulo 3 and a^(2(q−1)) − a^(q−1) + 1 = 0.Source: B. New classes of permutation binomials · p. 4
• For the first binomial, testing whether each equation f(x) = c has at most one solution reduces to checking whether a related cubic permutes Fq.The proof treats q ≡ 2 and q ≡ 0 modulo 3 separately.Source: B. New classes of permutation binomials · p. 5
• The first binomial is not multiplicatively equivalent to known ones, while the second is a linearized polynomial whose necessary-and-sufficient condition is presented as new.Source: B. New classes of permutation binomials · pp. 5, 7
• For f(x) = x^r(x^(q−1) + a), with 1 ≤ r ≤ q + 1, permutation over Fq2 holds exactly when r = 1 and a^(q+1) ≠ 1.Source: B. New classes of permutation binomials · p. 6

• The reviewed list includes linearized trinomials and examples such as x + x^3 + x^5 for odd m and x + x^5 + x^7 when m is not divisible by 3.Source: A. The known permutation trinomials · p. 7
• Results attributed to include two trinomial forms for odd m and a form for positive even m.Source: A. The known permutation trinomials · p. 7
• Hou’s cited results include ax + bx^q + x^(2q−1) over Fq2 for even q.Source: A. The known permutation trinomials · p. 8

Theorem 4.7

• For q=2^(2k), f(x)=x+x^(2^k)+x^(2^(2k)-2^(k-1)+1) permutes Fq if and only if k is not divisible by 3.Source: B. New Classes of Permutation Trinomials · p. 8

Theorem 4.9

• For q=2^(2k), f(x)=x+ax^(2^(k+1)-1)+a^(2^k-1)x^(2^(2k)-2^(k+1)+1) permutes Fq when a has order 2^k+1.Source: B. New Classes of Permutation Trinomials · p. 10

Theorem 4.10

• For q=2^(2k+1), Theorem 4.10 gives a permutation trinomial for every a in Fq and generalizes the known permutation trinomial in Theorem 4.1(6).The source also notes that this class is equivalent to [21, Theorem 5.1], with a different and somewhat shorter proof.Source: B. New Classes of Permutation Trinomials · pp. 12–13

Theorem 4.11

• For q=2^(2k+1), f(x)=x+ax^3+a^(2^(2k+1)-2^(k+1))x^(2^(k+1)+2) permutes Fq for every a in Fq, generalizing the second trinomial in Theorem 4.2.The last class's proof omits a long, intricate trace claim and refers readers to for details.Source: B. New Classes of Permutation Trinomials · pp. 13–14

B. New Classes of Permutation Trinomials

• The proof derives (1 + d)^3 = (1 + c)^6, uses the gcd condition to obtain d = c^2, and concludes d ∈ {0,1}, contradicting d ≠ 0,1.Source: B. New Classes of Permutation Trinomials · p. 15

C. Multiplicative inequivalence of the new permutation trinomials with known ones

• The classes in Theorems 4.9, 4.10, and 4.11 are multiplicatively inequivalent to known permutations and pairwise inequivalent.The comparisons include differences in defining dimensions and a direct check for Theorem 4.9 against Theorems 4.5 and 4.6.Source: C. Multiplicative inequivalence of the… · p. 15
• The final three new classes have nontrivial coefficients; the authors contrast them with the few such classes they identify in F2^m.They distinguish these classes from Theorem 4.1 (5), (7), and (8), and from Theorems 4.5 and 4.6.Source: C. Multiplicative inequivalence of the… · p. 15
• Theorem 4.11 is multiplicatively inequivalent to the trinomial in Theorem 4.12, previously introduced in [21].The section states that the first class in [21] is equivalent to Theorem 4.10.Source: C. Multiplicative inequivalence of the… · pp. 15–16
• The two new classes with trivial coefficients are reported as new and multiplicatively inequivalent to each other, based on Magma checks in at least one F2^m for 4 ≤ m ≤ 10.The reported computation confirms the inequivalence conclusion for at least one small field in that range.Source: C. Multiplicative inequivalence of the… · p. 16

5. CONCLUSIONS

• The authors state that complete determination of all permutation binomials or trinomials over finite fields seems out of reach for now, and computer experiments suggest more classes remain to be found.They describe the constructed functions as a foundation for further research.Source: §5 · p. 16
• The constructed functions extend the known list and can be employed in linear and cyclic codes and used to construct bent and semi-bent functions.The applications are cited through,, and.Source: §5 · p. 16