TheoremDB
All problems

[#P2620] An APN permutation of the 256-element field

Checking solution status

Loading the current review decision.

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 accessWork on this problem in ChatGPT

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

What counts as a solution

Current status (Existence of an APN permutation on F_256 remains open). No accepted construction or unrestricted nonexistence proof was found in the primary literature through 2026-07-25.[1][3][4]

1Packet records

4 records

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
The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemAn APN permutation of the 256-element field

All 4 recorded relations between these records and the problem

2See also

Contribute to this problem
Cite this problem statement

Cite the original sources separately.

Plain text
“An APN permutation of the 256-element field.” TheoremDB. P2620. Problem statement; statement text SHA-256 c73b440c650ea26660001d74512974ef2254a015ce3065214ae3cc2d13a8cae6. https://theoremdb.org/statement/?ref=P2620
BibTeX
@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}
}

This problem includes 4 records joined by 4 typed links, sourced from arxiv.org[1], current as of July 25, 2026.

1References

  1. 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.
  2. 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
  3. 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
  4. 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
  5. 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

Loading discussion.

Add a comment

Report comment

Flag this problem

Sign in to follow

Sign in in another tab, then return here.

Open sign-in in another tab

Report a problem

Report location:

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.