# P2620: An APN permutation of the 256-element field

- ID: `P2620`
- Reference: `apn-permutation-f256`
- Page: https://theoremdb.org/statements/P2620
- Record maturity: Reviewed problem with recorded work

## 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?

### Remarks

- **Remark.** A function with this differential property is almost perfect nonlinear, or APN.
- **Remark.** Two solutions occur as a paired set {x,x+a}, so two is the smallest possible positive differential multiplicity.

### What 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.

## Status

No accepted construction or unrestricted nonexistence proof was found in the primary literature through 2026-07-25. [1](#reference-1) [3](#reference-3) [4](#reference-4)

## Work

### Evidence for the current status

**Proposition 1 (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.

The answer remains open. A witness must be a bijection \(F:\mathbb F_{2^8}\to\mathbb F_{2^8}\) satisfying
\[
\max_{a\ne0,\,b}\#\{x:F(x+a)+F(x)=b\}=2.
\]
The complete search space contains \(256!\) lookup tables, so every published computation uses structural restrictions or selected CCZ-equivalence classes.

Beierle, Brinkmann, and Leander searched APN permutations admitting a nontrivial linear self-equivalence. Their dimension-eight search exhausted all except a few self-equivalence classes and found no witness. Beierle, Langevin, Leander, Polujan, and Rasoolzadeh later generated 3,775,599 inequivalent quadratic APN functions in dimension eight. None of those functions is CCZ-equivalent to a permutation.

A June 2026 preprint by Kuznetsov found four further quadratic APN CCZ-classes absent from the 2025 database. Its displayed functions are nonpermutations, and the paper leaves open whether any of the four CCZ-classes contains a permutation. This latest result preserves the unrestricted open status.

### Background and intake notes

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: The inverse permutation x to x^254 has differential uniformity 4 over F_256.

### Other known results

- **Proposition 2** (supported): 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. [2](#reference-2) [5](#reference-5)

### Prior approaches

- **Route 1** (supported): Large restricted searches have produced strong exclusions, while each source records a boundary short of all 256-element-field permutations. [1](#reference-1) [3](#reference-3) [4](#reference-4)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python checks every derivative row and confirms that the 128 power permutations on F_256 have minimum differential uniformity four.

### 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `apn-permutation-f256`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://arxiv.org/abs/2606.11967
   - preprint; reference source; arXiv:2606.11967v2; checked 2026-07-25
   - Source 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 open
   - Source named by the research packet.
2. <a id="reference-2"></a>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 https://doi.org/10.1007/s00009-024-02660-x
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source 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
3. <a id="reference-3"></a>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 https://doi.org/10.1109/TIT.2021.3071533
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - restricted search over dimension-eight permutations with linear self-equivalences
4. <a id="reference-4"></a>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 https://arxiv.org/abs/2508.04644
   - preprint; reference source; arXiv:2508.04644v1; checked 2026-07-25
   - Source use: citation_only
   - 3,775,599 quadratic APN classes generated; none of the generated functions is CCZ-equivalent to a permutation
5. <a id="reference-5"></a>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 https://doi.org/10.1016/j.ffa.2017.02.001
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - partially bent and quadratic component exclusions