← All papers
First page of Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension

Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension

Hiroki Fukui

math.NT Oct 15, 2026 · v1 cs.CR cs.IT
The Main Theorem for odd n≥9 is formalized in Lean 4 with Mathlib, using Mathlib's Schwartz–Zippel bound, and checked with lean4checker.
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ănică 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.

Lifting permutations of F_{2^n} to permutation polynomials over Galois rings requires that the formal derivative of the reduced representative have no zero. This derivative is not invariant under linear equivalence. The question is whether every quadratic APN permutation in odd dimension can be moved by linear input and output changes to an 'optimal' representative, whose derivative has no zero and has fibres of size exactly two.

For n≥9, a global linearization in a parameter ζ_A and a projectively injective cofactor map reduce the problem to a count. Invertible binary matrices are compared against matrices of rank ≤ n−2 together with a hypersurface of degree n(n−1), with the hypersurface bounded by Schwartz–Zippel. For n=5 and n=7, two independent published classifications and finite certificates are used. The n≥9 existence proof is formalized in Lean 4 with Mathlib and checked by the kernel and by lean4checker.

Every quadratic APN permutation of F_{2^n} with n≥5 odd has an optimal linearly equivalent representative. For n≥9, more than 5% of invertible inputs work, and more than half for n≥15. The statement fails for n=3. This yields counterexamples to the Bartoli–Stănică reduced critical-point conjecture that lift to permutation polynomials of optimal differential uniformity over every Galois ring with this residue field.