Explicit reduced APN permutations: ramification and optimal Galois-ring lifts
Hiroki Fukui
math.NT
Oct 15, 2026 · v1
cs.CR cs.IT
TL;DR
Key statements about the APN permutation family are formalised in Lean 4 with Mathlib, sorry-free, with sources and blueprint deposited on Zenodo.
Abstract
Let $m\ge5$ be odd and $q=2^m$. For every odd $r$ with $3\le r<m$ and $\gcd(r,m)=1$ we give the reduced polynomial $P_{m,r}=\mathrm{red}((T_r^3)^{2^{m-2}})$, $T_r=\sum_{i<r}X^{2^i}$, explicitly: it has coefficients in $\mathbb{F}_2$ and exactly $3r-2$ terms, it is an APN permutation of $\mathbb{F}_q$, and its formal derivative $1+X^{2^{r-2}}+X^{2^{m-2}}$ has no zero on $\mathbb{F}_q$ and is two-to-one. We determine the ramification of $P_{m,r}$ as a map of the projective line for all admissible $(m,r)$: there are $2^{m-r}$ finite ramification points, all wild, with index and different exponent $2^{r-2}$, all over the single finite branch value $1$. The $0/1$ lift of $P_{m,r}$ satisfies an identity in $\mathbb{Z}[X]$ that evaluates it over every Galois ring $\mathrm{GR}(2^k,m)$ with $m-1$ squarings, one general multiplication and $r+5$ additions or subtractions. For every quadratic optimal APN permutation $p$ of $\mathbb{F}_q$ (in particular $P_{m,r}$), every $k\ge2$ and every coefficient lift $F$ of $p$ to $\mathrm{GR}(2^k,m)$, we determine the differential rows of $F$ exactly in the unit directions whose residue lies outside the kernel $\{0,ρ\}$ of the linear part of $p'$ (they are the residue rows of $p$; $ρ=1$ for $P_{m,r}$) and in the directions in $2^{k-1}\mathrm{GR}(2^k,m)\setminus\{0\}$ (every nonzero entry equals $2q^{k-1}$). We also give a self-contained proof of the Li–Wang criterion for a Gold function plus a linearised polynomial, which explains why the inner map of $P_{m,r}$ is not a monomial, and record a two-word, two-layer transition that a simple linear layer forbids at the residue level.
Problem
Bartoli–Stănică conjectured that reduced APN permutations have rational critical points, and Rønjom–Sandrib conjectured that APN permutations of F_{2^m} have no lifts permuting Galois rings. The paper gives an explicit binary family that bears on both conjectures and studies how its lifts behave over Galois rings.
Approach
For odd m≥5 and admissible odd r, the reduced polynomial P_{m,r} = red((T_r^3)^{2^{m-2}}) is computed explicitly and shown to be an APN permutation. Its derivative is shown to have no zeros on F_q and to be two-to-one. Its ramification over the projective line is determined via Riemann–Hurwitz. The authors also give an integer product identity for the 0/1 lift and compute exact differential rows of coefficient lifts of quadratic optimal APN permutations in two classes of directions. Selected statements are formalised in Lean 4 with Mathlib.
Results
P_{m,r} has 3r-2 terms. It has 2^{m-r} wild finite ramification points, each with index and different exponent 2^{r-2}, all lying over the single finite branch value 1. Its 0/1 lift evaluates over GR(2^k,m) with one general multiplication. Every coefficient lift of P_{m,r} permutes GR(2^k,m), refuting the Rønjom–Sandrib conjecture for every odd m≥5 and k≥2. The Lean proofs use only the standard axioms and contain no sorry.
