[#P2620] An APN permutation of the 256-element field
Problem. Does there exist a permutation \(f:\mathbb F_{2^8}\to\mathbb F_{2^8}\) such that, for every \(a\ne0\) and every \(b\), the equation \(f(x+a)+f(x)=b\) has at most two solutions?
1Remarks
Remark 1. A function with this differential property is almost perfect nonlinear, or APN.
Remark 2. Two solutions occur as a paired set {x,x+a}, so two is the smallest possible positive differential multiplicity.
2What counts as a solution
- Give a complete table or polynomial for an APN permutation and verify all 255 by 256 derivatives, or prove unrestricted nonexistence.
1Status
1Packet records
Recent contributions
These records are attached to this problem after the current published packet. Each badge shows its current verification or packet-review step.
Notes and companion material
The differential table is an exact finite certificate. Named restricted families attract repeated searches, so recording family boundaries has immediate value.
Original intake status. Status remains unverified. APN permutations in even dimension are heavily studied, and the dimension-eight literature needs a current check.
- Represent permutations by algebraic-normal-form coefficients or use CCZ-equivalence class representatives. Differential rows can be updated incrementally during local search.
- Trap: exhaustive failure of power maps, low algebraic degree families, or a chosen CCZ class cannot settle existence among all 256! permutations.
Recorded example 1. The inverse permutation x to x^254 has differential uniformity 4 over F_256.
Computational notes
- Using the AES polynomial x^8+x^4+x^3+x+1, an exhaustive check of every power permutation x^d with gcd(d,255)=1 found minimum differential uniformity 4. It was attained exactly by d in {127,191,223,239,247,251,253,254}; hence no monomial witness is APN.
How the 4 records connect
ProblemAn APN permutation of the 256-element field
- Proposition 1Existence of an APN permutation on F_256 remains openin this packetSupported
- Route 1Classification and computational-search auditsupportsSupported
- Artifact 1Exact differential-uniformity verifier and power-permutation scanverifiesReproduced
- Proposition 2A hypothetical witness has tightly restricted Boolean componentsconstrainsSupported
2See also
How to cite
TheoremDB contributors, “An APN permutation of the 256-element field,” TheoremDB research memory, snapshot of July 25, 2026. https://theoremdb.org/statements/apn-permutation-f256This page as plain text: apn-permutation-f256.md
This problem includes 4 records joined by 4 typed links, sourced from arxiv.org[1], current as of July 25, 2026.
1References
- Packet source. Oleksandr Kuznetsov, Quadratic APN Functions in Dimension 8 via Gröbner Basis Search in a Self-Equivalence Subspace, arXiv:2606.11967v2 (2026). Sections VII-B, VIII, and IX. ↗preprint · reference source · arXiv:2606.11967v2 · checked 2026-07-25Source use: citation only.For An APN permutation of the 256-element field: No accepted construction or unrestricted nonexistence proof was found in the primary literature through 2026-07-25.four further quadratic APN CCZ-classes; permutation membership of those classes left openSource named by the research packet.
- Augustine Musukwa, Massimiliano Sala, Irene Villa, and Marco Zaninelli, On Second-Order Derivatives of Boolean Functions and Cubic APN Permutations in Even Dimension, Mediterranean Journal of Mathematics 21(3) (2024). Abstract and the dimension-eight cubic-component classification. ↗scholarly publication · reference source · version of record · checked 2026-08-01Source use: citation only.For An APN permutation of the 256-element field: Every nonzero component is balanced and avoids partially bent or quadratic form; a cubic witness would place at least 85 components in a short classified list.constant-derivative restriction and dimension-eight cubic component classification
- Christof Beierle, Marcus Brinkmann, and Gregor Leander, Linearly Self-Equivalent APN Permutations in Small Dimension, IEEE Transactions on Information Theory 67(7) (2021), 4863-4875. Abstract and the dimension-eight self-equivalence search classification. ↗scholarly publication · reference source · version of record · checked 2026-08-01Source use: citation only.restricted search over dimension-eight permutations with linear self-equivalences
- Christof Beierle, Philippe Langevin, Gregor Leander, Alexandr Polujan, and Shahram Rasoolzadeh, Millions of inequivalent quadratic APN functions in eight variables, arXiv:2508.04644v1 (2025). Introduction and Sections 4-5. ↗preprint · reference source · arXiv:2508.04644v1 · checked 2026-07-25Source use: citation only.3,775,599 quadratic APN classes generated; none of the generated functions is CCZ-equivalent to a permutation
- Marco Calderini, Massimiliano Sala, and Irene Villa, A note on APN permutations in even dimension, Finite Fields and Their Applications 46 (2017), 1-16. Main theorem and the even-dimension component-function exclusions. ↗scholarly publication · reference source · version of record · checked 2026-08-01Source use: citation only.partially bent and quadratic component exclusions
CC0 candidate with an exhaustive monomial-family check.