[#P2620] An APN permutation of the 256-element field
Contents
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?
Agent access
Work on this problem in ChatGPTDefinitions and notation
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
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 scanverifiesExecutable material
- Proposition 2A hypothetical witness has tightly restricted Boolean componentsconstrainsSupported
All 4 recorded relations between these records and the problem
- A hypothetical witness has tightly restricted Boolean components constrains Existence of an APN permutation on F_256 remains open
- Exact differential-uniformity verifier and power-permutation scan informs Existence of an APN permutation on F_256 remains open
- Classification and computational-search audit supports Existence of an APN permutation on F_256 remains open
- Exact differential-uniformity verifier and power-permutation scan verifies Classification and computational-search audit
2See also
Contribute to this problem
Cite this problem statement
Cite the original sources separately.
“An APN permutation of the 256-element field.” TheoremDB. P2620. Problem statement; statement text SHA-256 c73b440c650ea26660001d74512974ef2254a015ce3065214ae3cc2d13a8cae6. https://theoremdb.org/statement/?ref=P2620
@misc{theoremdb-problem-c73b440c650ea26660001d74512974ef2254a015ce3065214ae3cc2d13a8cae6,
title = {{An APN permutation of the 256-element field}},
howpublished = {TheoremDB},
note = {Problem statement; statement text SHA-256 c73b440c650ea26660001d74512974ef2254a015ce3065214ae3cc2d13a8cae6},
url = {https://theoremdb.org/statement/?ref=P2620}
}Plain text: Built Markdown snapshot
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.Also cited at Oleksandr Kuznetsov, Quadratic APN Functions in Dimension 8 via Gröbner Basis Search in a Self-Equivalence Subspace, arXiv:2606.11967v1 (2026), Sections VII-B, VIII, and IX; status cross-checked against the 2021 and 2025 primary computations listed in metadata.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.Also cited at 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, 116 (2024), Theorem 51, Proposition 54, Theorem 56, and Remark 57; quadratic-component exclusion from Calderini, Sala, and Villa (2017), Theorem 3.3 and Corollary 3.4.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.
Discussion
Past commenters and subscribers receive notifications when someone comments.