Reduced polynomial lifts of APN permutations over Galois rings and effective non-APN bounds
Daniele Bartoli, Pantelimon Stanica
math.NT
Aug 31, 2026 · v2
cs.IT
TL;DR
A third-party Lean 4 certificate, credited to Zhang and Haobo, formally verifies the counterexample: a degree-24 reduced APN permutation over F_32 with nowhere-zero derivative.
Abstract
We study coefficientwise permutation lifts of reduced polynomial representatives of almost perfect nonlinear (APN) permutations from finite fields to Galois rings. The standard permutation criterion shows that a permutation polynomial over $\mathbb F_{2^m}$ admits such a lift if and only if its formal derivative is nowhere zero on the field. In that case, every coefficientwise lift permutes $\operatorname{GR}(2^k,m)$ for every $k>1$. It is natural to conjecture that the reduced representative of an APN permutation admits no such lift. However, Zhang and Haobo supplied a counterexample to our earlier critical-point conjecture, which also refutes this lifting claim. Their degree-$24$ reduced APN permutation over $\mathbb F_{32}$ has a nowhere-zero formal derivative. We record this example and give an exact linear-image and trace-dual criterion for the absence of rational critical points in quadratic functions. We also obtain explicit non-APN bounds from Janwa-Wilson-Rodier surfaces. For every odd degree $d\ge5$ outside the Gold and Kasami-Welch exponent families, results of Hernando-McGuire and Aubry-McGuire-Rodier yield an absolutely irreducible component defined over the ground field. Applying the Cafure-Matera point estimate gives an explicit threshold above which no polynomial of degree $d$ over $\mathbb F_{2^m}$ is APN. This makes the known qualitative nonexistence result effective. An identity between difference tables extends the bound to polynomials $ax+g(x^2)+c$, where $a\ne0$ and $g$ has an odd degree in the stated range. Finally, every cubic permutation polynomial has a rational critical point and therefore admits no coefficientwise permutation lift.
Problem
The question is whether reduced polynomial representatives of APN permutations over F_{2^m} can lift coefficientwise to permutations of Galois rings GR(2^k,m). The paper also seeks effective degree bounds beyond which no polynomial is APN.
Approach
A standard criterion reduces the lifting question to whether the formal derivative has a rational zero. The authors record a counterexample due to Zhang and Haobo, which those authors formalized in Lean 4. They give a linear-image and trace-dual criterion for quadratic functions. Effective non-APN bounds come from Janwa–Wilson–Rodier surfaces, using absolutely irreducible components (Hernando–McGuire, Aubry–McGuire–Rodier) and the Cafure–Matera point estimate.
Results
A degree-24 reduced APN permutation over F_32 has a nowhere-zero derivative, so every coefficientwise lift of it permutes GR(2^k,5). This refutes the earlier critical-point conjecture. Explicit thresholds rule out APN polynomials of odd degree d≥5 outside the Gold and Kasami–Welch families, and the bound extends to polynomials ax+g(x^2)+c. Every cubic permutation polynomial has a rational critical point and so admits no such lift.