Resolving a conjecture on quadratic APN functions and a new quadratic $(n,n)$-function associated to crooked functions

Claude Carlet; Darrion Thornburgh

Resolving a conjecture on quadratic APN functions and a new quadratic $(n,n)$-function associated to crooked functions

T0 review · 2 major / 4 minor · reviewed 2026-08-28 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The 2020 conjecture is true: every nonzero ortho-derivative component of a quadratic APN function has degree n-2.

desk verdict Gorodilova's conjecture is plausibly settled by a genuinely new parity-function framework, but the proof's keystone oddness result is imported from a self-cited prior paper and needs referee scrutiny. read the letter →

arxiv 2608.23888 v2 pith:VUC3VVUA submitted 2026-08-24 math.CO cs.ITmath.IT

Claude Carlet , Darrion Thornburgh This is my paper · ORCID

classification math.COcs.ITmath.IT MSC 11T7194A6005B99

keywords crookedfunctionsalmostperfectnonlinearortho-derivativealgebraicdegreeexcludeparityadjointbentsemi-bentWalshtransform

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves the 2020 conjecture restated as Conjecture 1.1: for $n \ge 4$, every nonzero component $v \cdot \pi_F$ of the ortho-derivative of a quadratic APN function $F$ on $\mathbb{F}_2^n$ has algebraic degree exactly $n-2$. The upper bound $\deg(\pi_F) \le n-2$ was already known; the contribution here is the matching lower bound, obtained for all quadratic APN functions and for the broader class of crooked functions. For a crooked function $F$ with $2^k$ quadratic components, at least $2^n - 2^{n-k}$ nonzero components of $\pi_F$ are shown to have degree $n-2$. The argument also constructs a new quadratic function $\varepsilon_F$, the exclude parity adjoint of $F$, and derives consequences for semi-bent components and for a 2009 conjecture on $m$-sequence cross-correlations.

What carries the argument

The machinery is built from three objects. First, the ortho-derivative $\pi_F$, defined by $\pi_F(0)=0$ and $\{0,\pi_F(a)\}^\perp$ equal to the underlying linear space of $\mathrm{Im}(D_aF)$ for nonzero $a$. Second, the exclude parity functions $f_v(u)$, which record the parity of the number of two-dimensional linear subspaces $E \subseteq \{0,u\}^\perp$ on which $F$ sums to $v$; these are shown to be quadratic. Third, the exclude parity adjoint $\varepsilon_F$, which repackages all $f_v$ into a single quadratic vectorial function. The load-bearing identity is Proposition 4.7, which equates $\deg(v \cdot \pi_F) = n-2$ with the conjunction of $m(v)$ odd and $\deg(f_v)=2$, and Theorem 4.8 supplies the force needed to make $f_v$ quadratic when a quadratic component of $F$ evaluates to 1 on $v$.

What would settle it

Compute the exclude multiplicities $m(v)=\mathrm{mult}_{G_F}(0,F(0)+v)$ for all nonzero $v$ for one quadratic APN function on $\mathbb{F}_2^4$ (for instance the Gold function $x \mapsto x^3$); an even value would invalidate Proposition 2.1 and collapse Corollary 4.9. Alternatively, check the algebraic normal form of every component $v\cdot\pi_F$ for a quadratic APN function in four or five variables: a single component of degree below $n-2$ would falsify the conjecture.

Watch

Extended reading notes

Core claim

The central discovery is that the algebraic degree of $v \cdot \pi_F$ is controlled by the parity of an exclude multiplicity: $m(v)=\mathrm{mult}_{G_F}(0,F(0)+v)$ counts triples in the graph of $F$ summing to that point, and Proposition 4.7 characterizes $\deg(v \cdot \pi_F)=n-2$ by $m(v)$ odd together with the exclude parity function $f_v$ having algebraic degree 2. The paper proves $m(v)$ is always odd for plateaued APN functions, and then uses the existence of a quadratic component $c \cdot F$ with $c \cdot v = 1$ to force $f_v$ to be genuinely quadratic. This yields the main theorem: for $n \ge 4$ and a crooked $F$ with $2^k$ quadratic components, at least $2^n - 2^{n-k}$ nonzero components of $\pi_F$ have degree $n-2$; in the quadratic APN case, $k=n$, so every nonzero component has degree exactly $n-2$, resolving Conjecture 1.1. Along the way the paper defines the exclude parity adjoint $\varepsilon_F$, a quadratic $(n,n)$-function satisfying $v \cdot \varepsilon_F(u) = f_v(u) \oplus 1$ for all nonzero $u,v$, and proves it exists for every crooked function when $n \ge 4$.

Load-bearing premise

The lower bound rests on Proposition 2.1, imported from the authors' prior work without its proof being reproduced: for every plateaued APN function in at least three variables, the exclude multiplicity of every point outside the graph is odd.

Editorial extensions

If this is right

The 2020 conjecture is settled, so the algebraic degree of every nonzero component of the ortho-derivative of a quadratic APN function is a known invariant, $n-2$, rather than merely an upper bound.
Every crooked function in even dimension $n \ge 4$ with at least one quadratic component has at least five semi-bent component functions; in particular this holds for all quadratic APN functions in even dimension.
Every crooked function $F$ in dimension $n \ge 4$ has an exclude parity adjoint $\varepsilon_F$; when $F$ is quadratic APN, $\varepsilon_F(u)=0$ only at $u=0$, and when $F$ is Gold, $\varepsilon_F=F$.
The exponential-sum congruence $G_n^{(i)} \equiv G_n^{(1)} \pmod{16}$ holds for all $i$ with $\gcd(i,n)=1$, giving partial support to the 2009 conjecture on $m$-sequence cross-correlations.
For a plateaued APN function in even dimension, the indicator of its bent components has algebraic degree exactly $n/2$; for a quadratic APN function restricted to a hyperplane, the indicator of near-bent components has degree $n-1$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: the equivalence that $\varepsilon_F$ is APN exactly when $\pi_F$ is $(n-2)$-th order sum-free turns the search for new APN functions into a checkable sum condition on $\pi_F$; the paper states the equivalence but does not advertise it as a search tool.
Editorial inference: the identity $\varepsilon_F=F$ for Gold functions suggests testing whether every known quadratic APN function is exclude parity self-adjoint, and whether any non-Gold example exists; since $\varepsilon$ is preserved up to linear equivalence under EA equivalence, this could sharpen the classification of quadratic APN functions.
Editorial inference: the degree-$n/2$ result for the bent-component indicator implies that the set of bent components of any plateaued APN function meets every $(n/2+1)$-dimensional linear subspace in an even number of points, a parity filter that could be applied in large amplitude-distribution searches.
Editorial inference: the modulo-16 congruence for $G_n^{(i)}$ is a natural first step toward the full 2009 conjecture; reaching full equality would require moving from Walsh-transform congruences for $\pi_F$ to exact exponential-sum identities.

Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

Claim #1: The central discovery is that the algebraic degree of $v \cdot \pi_F$ is controlled by the parity of an exclude multiplicity: $m(v)=\mathrm{mult}_{G_F}(0,F(0)+v)$ counts triples in the graph of $F$ summing to that point, and Proposition 4.7 characterizes $\deg(v \cdot \pi_F)=n-2$ by $m(v)$ odd together with the exclude parity function $f_v$ having algebraic degree 2. The paper proves $m(v)$ is alw

/-- @claim 1 The central discovery is that the algebraic degree of $v \cdot \pi_F$ is controlled by the parity of an exclude multiplicity: $m(v)=\mathrm{mult}_{G_F}(0,F(0)+v)$ counts triples in the graph of $F$ summing to that point, and Proposition 4.7 characterizes $\deg(v \cdot \pi_F)=n-2$ by $m(v)$ odd together with the exclude parity function $f_v$ having algebraic degree 2. The paper proves $m(v)$ is alw -/
def central_claim : Prop :=

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Chris,

The headline: this paper settles Gorodilova's 2020 conjecture on ortho-derivatives of quadratic APN functions: for n≥4, every nonzero component of π_F has algebraic degree n−2. That is a genuine open-problem resolution, and the proof machinery—exclude parity functions and the exclude parity adjoint—is new and worth knowing. The paper also gets a nice corollary that quadratic APN functions in even dimensions have at least five semi-bent components, and a mod 16 congruence on the 2009 Johansen–Helleseth–Kholosha exponential sum. I was skeptical going in, but the main derivation from Lemma 3.4 through Corollary 4.9 reads coherently; I do not see a circular step.

The strongest part is the framework. Defining the parity of exclude multiplicities with respect to the graph, showing those parities are quadratic, and then relating the degree of v·π_F to the degree of that parity function is a real conceptual advance. The Gold case ε_F=F is elegant, and the Kim APN computation (ε_κ differentially 4-uniform, image linearly equivalent to Im(κ)) is a nice data point.

Now the soft spot, and it is the one the stress-test flags: the proof of Corollary 4.9 rests on Proposition 2.1 from the authors' earlier paper [37], which says that for plateaued APN functions all exclude multiplicities are odd. That oddness is what turns Theorem 4.8 into the degree lower bound, and Proposition 4.2 uses the same proposition for the upper bound. The result is quoted without proof. It is a self-citation (shared author), and while that is not disqualifying, the current paper's main theorem stands directly on it. The reader's other complaints—plateaued-restriction facts from ePrint [22] and an uncited Gold ortho-derivative formula—are minor by comparison; they affect auxiliary results, not the main conjecture.

If [37]'s proposition is correct, and I have no reason to doubt it, the resolution stands. But a referee should be asked to verify that dependency, and the authors should be encouraged to reproduce the proof or at least provide a statement precise enough for the reader to check. As-is, the paper is acceptable for a strong venue after a careful round that addresses the self-citation transparency.

I would send it to peer review. It is a real result with a novel technique, and the fixable dependency should not sink it. A reader working on APN functions or crooked functions will want to see this. I would cite it.

Best.

Referee Report

2 major / 4 minor

Summary. The paper studies crooked functions F:F2^n→F2^n and their ortho-derivatives π_F. It introduces new Boolean 'exclude parity functions' f_v attached to the graph of F, proves a Walsh-transform description of the ortho-derivative in terms of these functions, and characterizes when deg(v·π_F)=n−2 in terms of deg(f_v)=2. Using Proposition 2.1 from the authors' related paper [37] — which asserts that plateaued APN functions have odd exclude multiplicities — the paper proves Corollary 4.9, thereby resolving Gorodilova's Conjecture 1.1 for quadratic APN functions in dimension n≥4. The paper also proves the upper bound deg(π_F)≤n−2 for all crooked functions, derives the existence of at least five semi-bent components in even dimension under a mild hypothesis, constructs an 'exclude parity adjoint' ε_F for every crooked function, proves that ε_F=F for Gold APN functions, obtains a congruence modulo 16 for the Johansen–Helleseth–Kholosha exponential sums, and determines exact algebraic degrees of indicators of bent and near-bent component sets.

Significance. If the proof is correct, the main result settles an open conjecture from 2020 in the affirmative and provides a new structural framework (exclude parity functions and the exclude parity adjoint) for studying APN and crooked functions. The paper contains explicit, checkable Walsh formulas and a number of nontrivial corollaries; the main derivation introduces no free parameters and is broadly stated. The proofs are detailed and appear internally coherent. However, the central lower bound is conditional on an externally cited, same-author result whose proof is not reproduced in the manuscript, so the significance is somewhat contingent on that result being accepted as a black box.

major comments (2)

[§4, Corollary 4.9; §2, Proposition 2.1] The proof of Gorodilova's conjecture rests on Proposition 2.1 from [37], which states that mult_{G_F}(a,b) is odd for every plateaued APN function F and every (a,b) outside the graph. This is the sole source of the oddness of m(v) needed in Theorem 4.8 to conclude deg(v·π_F)=n−2. If Proposition 2.1 failed for one quadratic APN function and one nonzero v, the lower-bound argument for that component would collapse; moreover, Proposition 4.2 would force deg(v·π_F)=n, contradicting the conjecture. Since [37] is a same-author publication and the present paper does not reproduce or sketch the proof, the keystone of the main result cannot be verified from the present text alone. Please include a proof of Proposition 2.1 (or a precise theorem/page reference in [37] together with a proof sketch in an appendix) so that the central claim is self-contained on this load-bearing point.
[§5, Theorem 5.5 and Lemma 5.3] The second main result, the existence of the exclude parity adjoint for every crooked function, also depends on external results that are not proved here: the plateaued restriction facts from [22] are used to assert that restrictions to hyperplanes are plateaued, and Lemma 5.3 relies on [5, Proposition 3.1]. These dependencies are less central than Proposition 2.1, but Theorem 5.5 is advertised as a second main result. I ask the authors to state these external facts precisely and, for the ePrint reference [22], to indicate whether it has appeared in a peer-reviewed venue or to provide the needed arguments.

minor comments (4)

[§4, Proposition 4.2 and §3, Proposition 3.9] In the statements/proofs concerning the identically zero case, the value of the exclude multiplicity is written as 2^{k−1}/3; it should be (2^k−1)/3, since the relevant formula is mult=(|A|−1−wt)/3 with |A|=2^k. As written, 2^{k−1}/3 is not an integer for even k.
[§2, Definition 4.3 and §5, Lemma 5.2] The exclude parity function f_{L,U,v} is defined only for nonzero v, but Lemma 5.2 uses the convention that f_0 is identically one. Please state this convention explicitly at the definition and check that it is consistent with the later use of f_v for v=0.
[§5.1, Proposition 5.12] In the proof that m_u(v)=m_{u^2}(v^2), the fact that squaring induces a bijection on the set of 2-dimensional linear subspaces of F_{2^n} is used implicitly. Adding a sentence to this effect would improve readability.
[Abstract and §4] The abstract uses k for the number of quadratic components (2^k), while Section 4 uses k for the dimension of the subspace L. This dual use of k can confuse the reader; consider denoting the dimension of Q(F) by κ or d.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Gorodilova's conjecture is derived from newly introduced parity functions, with the only external keystone being an independent prior result on exclude multiplicities.

full rationale

The central derivation is not circular. Corollary 4.9 obtains the lower bound deg(v·π_F)=n-2 by combining Theorem 4.8 with the oddness of m(v), where Theorem 4.8 is proved internally through the newly defined exclude parity functions f_v and Proposition 4.7's equivalence between deg(π^v_{F|L})=k-2 and the conjunction of oddness of m_L(v) with deg(f_{L,U,v})=2. The only external keystone is Proposition 2.1 from the authors' prior work [37], quoted in the paper as: 'Assume n≥3. Let F be a plateaued APN function. Then mult_{G_F}(a,b) is odd for all (a,b)∈(F_2^n)^2\G_F.' This proposition is then invoked in Corollary 4.9: 'By Proposition 2.1, we know that mult_{G_F}(a,b) is odd for all (a,b)∉G_F, and so m(v) is odd for all nonzero v.' Although [37] is a same-author citation and the proof is not reproduced, Proposition 2.1 is a parameter-free statement about exclude multiplicities of plateaued APN functions; it does not assert or assume Gorodilova's conjecture, and it is not derived from any fitted data in the present paper. The algebraic-degree conclusion therefore does not reduce to its input by construction, and the dependence on [37] is a normal external dependency rather than a circular step. The remainder of the chain—Proposition 4.5, Proposition 4.7, Theorem 4.8, and Corollary 4.9—is self-contained within the manuscript, and no fitted parameter is relabeled as a prediction. Consequently, the paper receives a circularity score of 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper's central claim rests on standard finite-field facts plus a small set of external theorems, two from the authors' own prior work. No free parameters are fitted. No new ungrounded entities are introduced: the adjoint epsilon_F is constructed and proven to exist, with computational checks for Gold and Kim functions.

assumptions (6)

domain assumption Proposition 2.1 of [37]: for n>=3 and a plateaued APN function F, mult_GF(a,b) is odd for all (a,b) not in the graph of F.
Invoked in Corollary 4.9 and Lemma 5.2 as the source of oddness of m(v), a necessary hypothesis for Theorem 4.8. The result comes from a paper co-authored by Thornburgh and is not proved in this paper.
domain assumption Restrictions of crooked or partially-bent functions to affine hyperplanes are plateaued with controlled amplitude ([22], [14]).
Used in Theorem 5.5 (odd n) and Proposition 4.10. The paper cites the authors' ePrint [22] for this, though the fact is also stated in the published reference [14].
domain assumption For the Gold function F(x)=x^(2^i+1), the ortho-derivative is pi_F(x)=x^(-(2^i+1)).
Invoked after Proposition 5.12 to derive the Walsh-transform expression and the mod 16 congruence, but stated as 'recalled' without a proof or a correct citation.
standard math Heden's theorem on vector space partitions (Theorem 4.11 of [30]).
Used in Proposition 4.12 to force at least 5 semi-bent components. Standard external theorem, stated in the paper.
standard math McEliece's weight congruence for Reed-Muller codes ([35]).
Used in Lemma 6.1 to obtain the lower bound deg(1_B(F)) >= n/2.
standard math Known characterization: for odd n, an APN function that is also AB satisfies mult_GF(t,F(t)+v) = (2^(n-1)-1)/3 for all nonzero v ([42]).
Used in Corollary 3.5 to prove that pi_F is invertible in odd dimensions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Resolving a conjecture on quadratic APN functions and a new quadratic $(n,n)$-function associated to crooked functions." pith.science (2026). https://pith.science/paper/VUC3VVUA

@misc{pith2026260823888,
  author       = {Pith},
  title        = {Pith review of: Resolving a conjecture on quadratic APN functions and a new quadratic $(n,n)$-function associated to crooked functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VUC3VVUA}},
  note         = {Machine review of arXiv:2608.23888}
}

abstract

We say an $(n,n)$-function $F \colon \mathbb{F}_2^n \to \mathbb{F}_2^n$ is a crooked function if for any nonzero $a \in \mathbb{F}_2^n$, the image of $D_aF(x)=F(x)+F(x+a)$ is an affine hyperplane. The only known examples of crooked functions are all quadratic almost perfect nonlinear (APN), or equivalently, for every known crooked function, $D_aF$ is affine for all $a \in \mathbb{F}_2^n$. The ortho-derivative $\pi_F \colon\mathbb{F}_2^n \to \mathbb{F}_2^n$ of a crooked function $F$ is the function such that $\pi_F(0)=0$, and for any nonzero $a$, the set $\{0,\pi_F(a)\}^\perp$ is the underlying vector space of $\mathrm{Im}(D_aF)$. We prove that for $n \geq 4$ and a crooked function $F$, if $k$ is a non-negative integer such that $F$ has $2^k-1$ quadratic component functions, $\pi_F$ has at least $2^n-2^{n-k}$ component functions of algebraic degree $n-2$. In particular, we resolve Gorodilova's conjecture that every component function of $\pi_F$ has algebraic degree $n-2$ when $F$ is quadratic APN. As a second main result, for $n \geq 4$, we associate to a crooked function $F$ a quadratic function $\varepsilon_F \colon \mathbb{F}_2^n \to \mathbb{F}_2^n$ that satisfies a strong geometric-combinatorial condition regarding the sums of $F$ over $2$-dimensional linear subspaces. As a corollary to both of our main results, we prove that for any even $n \geq 4$, any quadratic APN $(n,n)$-function has at least $n$ semi-bent components. Furthermore, we obtain a congruence result on a problem on $m$-sequences introduced by Johansen, Helleseth, and Kholosha, and we determine the exact algebraic degrees of some Boolean functions associated to the bent and near-bent components of particular classes of plateaued vectorial functions.

Discussion (0). Continue with ORCID to comment.

Pith tools

Reviewed August 28, 2026 · model on record in the stance chip above.