Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension
Abstract
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≥5, every quadratic almost perfect nonlinear permutation Q of 𝔽2n admits invertible binary-linear maps L and A such that the derivative of the reduced representative of L∘ Q∘ 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≥9, 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≥15, 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≥9 the existence proof is checked in the Lean 4 proof assistant.
Related
- On some Non-Permutations of Quadratic Extension of Finite Field
- Quadratic-size Random Permutations are Universal
- An optimal constant for vector balancing with permutations
- Reduced APN permutations and a disproof of the Galois-ring lifting conjecture
- Coefficient choice in Galois-ring lifts of APN permutations: sharp unit-direction spectra and one-term optimal lifts
BibTeX
@misc{fukui2026optimal,
title = {{Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension}},
author = {Hiroki Fukui},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21169},
eprint = {2610.21169},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21169},
}
RIS
TY - UNPB
TI - Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension
AU - Hiroki Fukui
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.21169
UR - https://arxiv.org/abs/2610.21169
AB - 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≥5, every quadratic almost perfect nonlinear permutation Q of 𝔽_2^n admits invertible binary-linear maps L and A such that the derivative of the reduced representative of L∘ Q∘ 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≥9, 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≥15, 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≥9 the existence proof is checked in the Lean 4 proof assistant.
ER -