PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension

Hiroki Fukui

arXiv:2610.21169v1math.NTcs.CRcs.ITmath.IT

TL;DR

The paper addresses whether quadratic APN permutations in odd dimensions can be represented with a zero-free reduced derivative, a condition relevant to lifting permutations to Galois rings. It proves that every such permutation in odd dimension n ≥5 has an optimal linear equivalent, using matrix counting for n ≥9 and classifications and certificates for n = 5, 7. These representatives yield ring permutation polynomials of optimal differential uniformity.

  • Problem

    The formal derivative of a reduced representative depends on the coordinates, although a zero-free derivative is required alongside a permuting reduction for the Galois-ring permutation criterion.

    Source: §I · p. 1

  • Method

    The proof combines a sufficient fixed-input criterion with linearization and projective cofactor-map counting for n ≥9, and classifications with finite certificates for n = 5, 7.

    Source: B. Method · p. 3, §III · p. 6

  • Results

    For every odd n ≥5, each quadratic APN permutation has a linear equivalent with zero-free reduced derivative and exactly two elements in each nonempty derivative fibre.

    Source: A. Main result · p. 2

  • Takeaways & Limitations

    Every such optimal representative yields permutation polynomials of optimal differential uniformity over every GR(2k, n), k ≥2.

    Source: A. Main result · p. 2

    The counting bound fails for n = 5, 7, which require classifications and finite certificates; the fixed-input criterion is sufficient, not necessary.

    Source: §X · p. 19

Abstract

from arXiv · show

The formal derivative of the reduced polynomial representative of a map on a binary finite field depends on the coordinates, although its differential uniformity does not. This matters for lifting permutations to Galois rings: a polynomial over a Galois ring of characteristic a power of two greater than two permutes the ring exactly when its reduction permutes the residue field and the derivative of the reduction has no zero there. We prove that for every odd $n\ge5$, every quadratic almost perfect nonlinear permutation $Q$ of $\mathbb{F}_{2^n}$ admits invertible binary-linear maps $L$ and $A$ such that the derivative of the reduced representative of $L\circ Q\circ A$ has no zero and each of its nonempty fibres has exactly two elements. The range is exact: this fails for $n=3$, as computed earlier, and for even $n$ there are no such permutations. For $n\ge9$, a linearization and a projectively injective cofactor map reduce the problem to counting binary matrices: more than 5% of the invertible inputs $A$ succeed, more than half for $n\ge15$, without any classification. For $n=5,7$ we use two independent classifications and finite certificates. Consequently every such permutation is linearly equivalent to a counterexample to the reduced critical-point conjecture of Bartoli and St\u{a}nic\u{a} that lifts to permutation polynomials of optimal differential uniformity over every Galois ring with this residue field. For odd $n\ge9$ the existence proof is checked in the Lean 4 proof assistant.

I. INTRODUCTION

The paper asks whether every quadratic APN permutation in odd dimension at least 5 can be linearly represented with a zero-free reduced derivative and smallest possible fibres. It proves this for all such permutations, reduces the large-dimension existence problem to matrix counting, and uses classifications and certificates in dimensions 5 and 7.

A. Main result

  • For every odd n ≥5, each quadratic APN permutation has a linear equivalent whose reduced derivative has no zero and whose nonempty fibres are pairs.The result gives the exact pairing x and x + r for some nonzero r.Source: A. Main result · p. 2
  • The dimension range is exact: n = 3 fails, while even dimensions have no quadratic APN permutations to which the result could apply.The theorem does not cover nonquadratic APN permutations or quadratic APN functions whose EA class contains no permutation.Source: A. Main result · p. 2
  • For odd n ≥5, the result supplies a linearly equivalent counterexample to the Reduced Critical-Point Conjecture [8].The conjecture asserts that every APN permutation's reduced representative has a zero of its formal derivative.Source: A. Main result · p. 2
  • Every such optimal representative lifts to permutation polynomials of optimal differential uniformity over each GR(2k, n), k ≥2.The lifting applies to every polynomial whose coefficientwise reduction is the optimal representative.Source: A. Main result · p. 2

B. Method

  • At a fixed input A, explicit output changes and, in one branch, an additional input shear yield an optimal representative under a sufficient condition on s(A) and η(A).The condition holds when s(A) = 0 or when s(A) = 1 and η(A) = 1; it is not claimed to be necessary.Source: B. Method · pp. 2–3
  • For n ≥9, linearization and projective injectivity of a cofactor map reduce existence to counting binary matrices by rank, without classification or character-sum estimates.The counting argument controls failing inputs through low-rank matrices and zeros of explicit polynomials.Source: B. Method · p. 3, C. Relation to previous work · p. 3

C. Relation to previous work

  • For odd n ≥9, at least 5.4% of invertible inputs work, rising above one half for n ≥15, and the theorem covers classes not yet found.For n = 5, 7 the counting bound fails, so the proof instead uses classifications, input witnesses, and 485 inconsistency certificates.Source: C. Relation to previous work · p. 3, B. Method · p. 3

D. Formal verification

  • The existence proof for odd n ≥9 is formalized in Lean 4, while the n = 5, 7 proof relies on classifications and finite certificates and is not formalized.The n ≥9 formal statement concerns quadratic APN bijections and their Lagrange representatives.Source: D. Formal verification · p. 3

E. Organization

The paper first fixes finite-field and Galois-ring terminology, then organizes the proof around interpolation data and invariants attached to an input map.

E. Organization

  • The proof proceeds from finite-field definitions and fixed-input analysis through linearization and cofactor methods, then treats dimensions 3, 5, and 7, corollaries, and formalization.Appendix A sharpens a degree bound, Appendix B gives an explicit Gold family, and supplementary material provides declarations, data, certificates, and archive identifiers.Source: E. Organization · p. 4

A. Maps of a finite field

  • A reduced representative is the unique polynomial of degree less than q representing a finite-field map, and its formal derivative is taken after this representation.Quadratic maps have exponents of binary weight at most two; optimality requires a zero-free derivative with every nonempty fibre of size two.Source: A. Maps of a finite field · pp. 4–5

B. Galois rings

  • For k ≥2, GR(2k, n) has residue field F, and ring differential uniformity uses subtraction rather than the field's characteristic-two sum.The identity map on GR(4, n) illustrates the distinction between the ring's difference and sum equations.Source: B. Galois rings · p. 5

C. Notation for the proof

  • The proof encodes output maps by vectors and records their constant-derivative outputs, common kernel, and whether the constant can be nonzero for each input A.Interpolation coefficients form N and p; additional notation encodes the polar tensor and related matrices.Source: C. Notation for the proof · p. 5

III. THE OUTPUT AT A FIXED INPUT

At a fixed input, the section characterizes output maps with constant derivatives and gives sufficient conditions for optimality. It also proves a maximal-rank result for left F-subspaces of binary-linear maps.

III. THE OUTPUT AT A FIXED INPUT

  • The section's fixed-input criterion is sufficient, not necessary: optimal outputs can be constructed when s(A)=0 or when s(A)=1 and η(A)=1.In the zero-derivative branch, one construction additionally shears the input.Source: §III · p. 6

A. The interpolation data

  • For quadratic g, the derivative of red(Lℓ◦g) is p·ℓ+Kℓ, with Kℓ determined by Nℓ and linear in ℓ over F.The constant and nonconstant derivative coefficients arise from the odd exponents of binary weight at most two.Source: A. The interpolation data · p. 6

B. Translation invariance

  • Translating the input preserves the nonconstant derivative part and leaves η unchanged on W=ker_F N.The change in the constant is a functional in row_F N, which vanishes on ker_F N.Source: B. Translation invariance · p. 6

C. Maximal rank in a left F-space

  • For any nonzero left F-subspace W, the largest binary rank of its maps is n−s, where s is the binary dimension of their common kernel.At least q^d−(2^(n−s)−1)q^(d−1) maps have kernel exactly the common kernel; consequently WA contains a bijection exactly when s(A)=0.Source: C. Maximal rank in a left F-space · pp. 6–7

D. Maximal rank on a prescribed nonzero label

On a prescribed nonzero label, the maximal-rank set contains a witness whose kernel is the common kernel. For quadratic APN maps in odd dimension, the polar identity yields minimum rank three for nonzero elements of the constant-derivative space.

D. Maximal rank on a prescribed nonzero label

  • For every nonzero label δ, some L in the affine label fibre has ker L = U and rank n − s; the fibre contains at least q^(d−2)(q − q/2^s + 1) such maps.The result applies when the label functional is nonzero, and the zero-label case can differ.Source: D. Maximal rank on a prescribed… · p. 7

E. The polar identity and minimum rank three

F. A dimension constraint

The common-kernel dimension constrains the size and maximum rank of the constant-derivative space. Three output constructions then turn suitable fixed-input witnesses into optimal representatives.

F. A dimension constraint

  • The space W_g is nonzero, and its invariants satisfy s ≤ n − 3, d + s ≤ n − 2, s ≤ rank N − 2, and max rank L = n − s ≥ d + 2.The bound follows from the minimum rank-three result and an injective evaluation map on a complement of U.Source: F. A dimension constraint · p. 8

G. Three output constructions

  • For n ≥ 4, every γ ≠ 0 and β, ε in F_2 admit a nonzero z with Tr(z) = β and Tr(γ/z) = ε.The statement fails for n = 3 when γ = 1 and (β, ε) = (0, 0).Source: G. Three output constructions · p. 9
  • If a quadratic APN permutation h has nonzero constant reduced derivative, a suitable bijective output map makes its reduced derivative root-free with exactly two-element nonempty fibres.The construction uses L(y) = σy + Tr(θy) for a suitable nonzero σ.Source: G. Three output constructions · p. 9
  • If a quadratic APN permutation S has zero reduced derivative, an input shear At(x) = x + Tr(tx) makes it optimal for some nonzero t with Tr(t) = 0.The trace condition makes At bijective.Source: G. Three output constructions · p. 9
  • A witness w with nonzero label and rank at least n − 1 can be combined with a trace map to produce a bijective output map and an optimal representative.The construction selects a and f to meet two trace conditions, one governing bijectivity and one placing the derivative constant outside its linear part's image.Source: G. Three output constructions · pp. 9–10

H. The two-invariant criterion

Two invariants of a fixed input determine which construction applies: the common-kernel dimension s and the indicator η of whether a nonzero constant is available. When s = 0, or s = 1 and η = 1, an optimal linearly equivalent representative follows.

Criterion for a fixed input

  • A witness with nonzero constant label and rank at least n − 1 exists exactly when s ≤ 1 and η = 1.For any prescribed nonzero label, its kernel can be chosen to equal the common kernel U.Source: H. The two-invariant criterion · p. 10
  • The fixed-input criterion guarantees an optimal representative when s = 0 or when s = 1 and η = 1.The constructions use an output update for nonzero constant derivative, an input shear for zero derivative, or the kernel-line construction.Source: H. The two-invariant criterion · pp. 10–11
  • Each construction yields invertible binary-linear maps on input and output, so the resulting representative has the required linear-equivalence form.In the zero-derivative branch, the input map is composed with the bijective shear.Source: H. The two-invariant criterion · p. 11
  • The criterion is sufficient, not necessary, for an optimal output at the given input; inputs outside it are not needed once an input satisfying it is found.The paper does not assert that every input admits a successful construction.Source: H. The two-invariant criterion · p. 11

I. Output relabeling

Output relabeling preserves the fixed-input invariants, while the global linearization expresses the relevant matrix data through the input's projective parameter. This supports reducing the search over inputs to structured polynomial data.

I. Output relabeling

  • An invertible output relabeling preserves d, s, and η, while transporting the common kernel by the same relabeling.The constant label is unchanged under the induced correspondence between output maps.Source: §I · p. 11

A. Dickson matrices and the polar tensor

B. The linearization theorem

  • For invertible A, the kernel of N_(g) equals the kernel of G(ζ_A), so W_A, d(A), U_A, and s(A) depend only on the projective class of ζ_A.The cofactor vector of N_(g) is given by ω(ζ_A).Source: B. The linearization theorem · p. 12
  • The linearization also gives a label formula p_h = λ(ζ) + κ(ζ)^(2^(n−1)) coordinatewise and defines a homogeneous polynomial Φ from λ, ω, and κ.For invertible A, Φ(ζ_A) is linked to the invariant condition d(A) = 1 and η(A) = 1 in the stated direction.Source: B. The linearization theorem · p. 12

V. THE COFACTOR DICTIONARY AND TWO NONZERO POLYNOMIALS

The cofactor dictionary relates properties of an input map A to the rank and kernel of matrices formed from its coefficient vector ζ_A. It identifies conditions under which the relevant space W_A is a line and gives a rank formula for s(A).

V. THE COFACTOR DICTIONARY AND TWO NONZERO POLYNOMIALS

  • The rank dictionary preserves binary rank under the adjoint map and scalar multiplication, so each nonzero projective class of ζ_A has exactly q − 1 representatives of the same rank.For F₂-linear A, L_{ζ_A} is the adjoint of A for the trace pairing.Source: §V · p. 13
  • For invertible A with ω(ζ_A) ≠ 0, W_A = Fω(ζ_A), while U_A = ker L_{ω(ζ_A)} and s(A) = n − rk ω(ζ_A).The cofactor vector also lies in ker G(ζ_A), whose rank is n − 1.Source: §V · p. 13
  • When A is invertible and Φ(ζ_A) ≠ 0, d(A) = 1, η(A) = 1, and s(A) = n − rk ω(ζ_A).The condition ensures ω(ζ_A) is nonzero, and W_A = Fω(ζ_A).Source: §V · p. 13

A. Moore points

Moore points establish nonzero polynomials and a projectively injective cofactor map. For odd n ≥ 9, these properties support a matrix-counting argument that guarantees invertible inputs producing optimal representatives.

A. Moore points

  • At Moore points m(x), the cofactor vector is a nonzero scalar multiple of m(a_x), where the kernel of G(m(x)) is Fm(a_x).The image of z ↦ B_Q(x,z) is the hyperplane {y : Tr(a_x y) = 0}.Source: A. Moore points · p. 13
  • Moore points show Φ is nonzero, while a nonzero homogeneous polynomial R of degree (n−1)(n−2) ensures [ζ] ↦ [ω(ζ)] is injective wherever R(ζ) ≠ 0.For x ≠ 0, Φ(m(x)) = t_x² ≠ 0.Source: A. Moore points · pp. 13–14

VI. UNIVERSAL INPUT EXISTENCE FOR n ≥9 AND PROOF OF THE MAIN THEOREM

  • The counting criterion bounds failures by the number of low-rank matrices and zeros of ΦR, using projective injectivity to control the low-rank contribution.The polynomial-zero contribution is bounded using deg(ΦR) ≤ n(n−1) and the Schwartz–Zippel bound.Source: §VI · p. 14
  • For odd n ≥ 9, some invertible A has s(A) = 0, or s(A) = 1 and η(A) = 1, yielding the input conditions used to construct an optimal representative.The lower bound for successful invertible inputs exceeds 5% for n ≥ 9 and exceeds one half for n ≥ 15.Source: §VI · pp. 14–15
  • The argument applies to every quadratic APN permutation without classification for n ≥ 9, relying on linear algebra, the almost-bent property, the Moore determinant, injectivity, and a polynomial zero bound.It is a pigeonhole argument comparing the low-rank matrix stratum with the invertible stratum.Source: §VI · pp. 14–15
  • For every quadratic APN permutation Q of F2^n with odd n ≥ 5, the Main Theorem gives an optimal P = L ◦ Q ◦ A′, with L and A′ invertible F2-linear.For n ≥ 9, Theorem VI.3 gives an invertible A with s(A) = 0, or s(A) = 1 and η(A) = 1; for n ∈ {5, 7}, Proposition VII.4 gives an invertible A with s(A) = 0, and the argument depends on classifications cited in Section VII.Source: §VI · p. 15

VII. DIMENSIONS THREE, FIVE AND SEVEN

The argument treats n = 5 and 7 through classifications and finite certificates, while n = 3 is an explicit failure boundary. The small-dimension results provide the input witnesses needed for optimal representatives.

VII. DIMENSIONS THREE, FIVE AND SEVEN

  • For n = 5 and 7, every quadratic APN permutation has an invertible input A with s(Q ◦ A) = 0, yielding an optimal representative.For n = 7, exactly three of the 488 EA classes contain a permutation; the other 485 have XOR inconsistency certificates.Source: §VII · p. 16
  • The n = 5 proof uses the classifications of Brinkmann–Leander [12] and Yoshiara [14], then verifies input witnesses for the Gold representatives x³ and x⁵.The witnesses are transported to each quadratic APN permutation using the equivalence results and the input-transport lemma.Source: §VII · p. 16
  • For n = 7, two independently obtained classifications and computations support the result, with direct optimality checks for the three permutation classes.The witnesses are computed on the tabulated representatives, not inferred from identifying those classes as Gold classes.Source: §VII · pp. 16–17
  • For n = 3, no quadratic APN permutation of F₈ has a reduced representative whose derivative is free of zeros, so the Main Theorem fails there.The exhaustive conclusion was independently re-verified in two implementations.Source: §VII · p. 17

VIII. CONSEQUENCES

The optimal representative satisfies the derivative condition for lifting to Galois rings and attains the smallest possible ring differential uniformity. The paper distinguishes this result from earlier Dickson-polynomial examples whose residue maps are not APN.

VIII. CONSEQUENCES

  • For every odd n ≥ 5, each quadratic APN permutation is linearly equivalent to one contradicting Bartoli and Stănică’s reduced critical-point conjecture [8].The derivative-free condition is equivalent to every lift of the reduced representative permuting GR(2^k, n), for k ≥ 2.Source: §VIII · p. 17
  • Every polynomial lift of the optimal representative has ring differential uniformity 2 · 2^{n(k−1)}, the smallest possible value for a permutation polynomial over GR(2^k, n).The proof uses the APN property for unit directions and the derivative’s two-element nonempty fibres for non-unit directions.Source: §VIII · p. 17
  • Earlier Dickson-polynomial examples attain the same ring differential uniformity, but their residue maps are not APN, unlike the residue maps established here.The stated scope is permutation polynomials of the ring; table-defined ring permutations are not considered, and no cipher-security claim is made.Source: §VIII · p. 18

IX. FORMALIZATION

The Lean 4 development formalizes the Main Theorem for odd n ≥9, including the existence of an optimal representative. Its main theorem and supporting lemmas were built and independently checked, while several other results remain unformalized.

IX. FORMALIZATION

  • The Main Theorem for odd n ≥9 is formalized in Lean 4 and asserts the existence of an optimal representative after invertible binary-linear input and output maps.The theorem is named APNLift.LabelFormula.uopt_odd.Source: §IX · p. 18
  • The formal statement defines optimality through quadraticity, APN bijectivity, a zero-free reduced derivative, and exactly paired derivative fibres.For some nonzero r, equal derivative values occur exactly at x and x + r.Source: §IX · p. 18
  • The proof formalizes the output constructions, linearization, Moore-point arguments, and matrix count used to establish the theorem.The count uses degree En = n(n −1) and the inequality established for all odd n ≥9.Source: §IX · p. 18
  • A clean build completed without errors, no sorry occurs, and lean4checker replayed the final theorem's dependencies successfully.The audit checks the theorem's displayed type, but not changes to the meanings of definitions named by that type.Source: §IX · p. 18
  • The n = 5, 7 main theorem and several appendices, estimates, and auxiliary results are not formalized.The appendix on the Gold classes is separately formalized except for specified parts of Theorems B.2 and B.3.Source: §IX · p. 19

X. CONCLUDING REMARKS

Every quadratic APN permutation in odd dimension n ≥5 has a linearly equivalent optimal representative, with different existence arguments for n ≥9 and n = 5, 7. The conclusion also identifies scope limits and open questions.

X. CONCLUDING REMARKS

  • Every quadratic APN permutation in odd dimension n ≥ 5 has an optimal representative L ◦ Q ◦ A, with invertible F2-linear L and A; this range is exact, failing at n = 3 and empty for even n.For n ≥ 9, at least a fixed fraction of invertible inputs works; for n ≥ 15, more than half work.Source: §X · p. 19
  • For n ≥9, a matrix-counting argument gives successful inputs, while n = 5, 7 rely on classifications and explicit witnesses.The small-dimension witnesses were rechecked against a second classification; the n ≥9 case is checked in Lean.Source: §X · p. 19
  • The result's range is exact: it fails for n = 3, and there are no quadratic APN permutations for even n.The n = 3 exception is also cited as Proposition VII.6 and.Source: §X · p. 19
  • The argument uses quadraticity through linearization, and the authors make no claim for APN permutations of higher algebraic degree.Experiments on relabelled power maps, including degree-three Welch functions, suggest zero-free reduced derivatives may also be common there.Source: §X · p. 19
  • Whether every quadratic APN permutation in odd dimension n ≥5 is linearly equivalent to one with zero reduced derivative remains open.The property holds for Gold classes and further families; such a form would yield an optimal map directly.Source: §X · p. 19
  • A uniform argument avoiding classifications for n = 5, 7 remains open because the counting bound fails in those dimensions.Such an argument would also make these cases amenable to formalization.Source: §X · p. 19
  • The inputs admitting an optimal output are not characterized, and some n = 9, 11 inputs have no optimal output for any linear output map.For the stated Dembowski–Ostrom examples, the reduced derivative of L ◦P vanishes at 0 for every output L.Source: §X · p. 19

APPENDIX A A SHARPER DEGREE: THE PFAFFIAN ROUTE

The Pfaffian route supplies a lower-degree cofactor for the counting argument, while the Gold-class appendix gives explicit optimal representatives through an input shear. The square-shear results characterize when the derivative is zero-free and construct a closed-form family.

APPENDIX A A SHARPER DEGREE: THE PFAFFIAN ROUTE

  • The Pfaffian route lowers the exceptional hypersurface degree from En = n(n −1) to Dn, but does not extend the counting result to n = 5, 7.This variant is not formalized.Source: Appendix A · p. 19
  • The Pfaffian vector of an odd-dimensional alternating matrix lies in its kernel and is nonzero exactly at rank n −1.Its coordinates are homogeneous of degree (n −1)/2 in the matrix entries.Source: Appendix A · p. 19
  • The Pfaffian construction yields a cofactor c whose nonvanishing identifies inputs where the associated matrix has rank n −1 and kernel Fζ.The projective map [ζ] ↦ [ω(ζ)] is injective on the locus where c(ζ) ≠ 0.Source: Appendix A · p. 20

APPENDIX B AN EXPLICIT FAMILY FOR THE GOLD CLASSES

  • The appendix gives closed-form optimal representatives in every Gold class without an estimate or search.The result is obtained by an input shear.Source: Appendix B · p. 20

A. The square-shear criterion

  • For odd n ≥5, the square-shear criterion gives an APN permutation whose reduced derivative has fibres {x, x + 1} and is zero-free exactly under a trace condition.The condition is Tr(π^2h^2/t) = 0 for nonzero t with Tr(t) = 0.Source: A. The square-shear criterion · p. 21
  • For each Gold exponent and odd n ≥5, Theorem B.3 constructs q/2 −1 distinct optimal APN permutations linearly equivalent to the Gold power map.Their reduced derivatives are t(X^(2e+1) + X^2 + 1).Source: A. The square-shear criterion · p. 21

Related papers

Loading 2610.21169v1…