{"id":"e4eceeb0-85b0-4a84-b1b2-ec4f8f6ec87a","arxiv_id":"2608.23888","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The ortho-derivative components of any quadratic APN function in n variables all have algebraic degree n-2, resolving Gorodilova's conjecture.","lead":"This paper proves Gorodilova's conjecture that every nonzero component of the ortho-derivative of a quadratic APN function has algebraic degree n minus 2, and builds a new quadratic function from any crooked function. The proof introduces 'exclude parity' functions and settles a 2020 conjecture central to the study of APN functions in cryptography and finite fields.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Corollary 4.9 (Gorodilova's conjecture) rests entirely on the unproved external Proposition 2.1: odd exclude multiplicity for plateaued APN functions.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing concern: Proposition 2.1 from [37] is external, self-cited, and not re-proved, and Corollary 4.9 depends on it twice (for the upper bound in Proposition 4.2 and for the lower bound in Theorem 4.8). My reading of the proof confirms that without oddness of m(v), the main theorem cannot go through. The internal arguments in Section 4 are otherwise coherent: Theorem 4.8's use of the bilinear form beta_{c·F} and the parity argument with q_{L,U,v} is valid, and Proposition 4.7's equivalence of algebraic degree with parity of exclude multiplicities is sound. The additional gaps flagged by the reader, such as the Gold ortho-derivative formula in Section 5.1, do not affect the proof of Gorodilova's conjecture. Therefore the appropriate verdict remains CONDITIONAL: the central claim is probably true, but the paper must either supply a proof of Proposition 2.1 or give a fully verifiable reference. No change to the reader's verdict is needed.","tokens_in":39139,"tokens_out":7598,"duration_ms":72483,"concrete_test":"Re-derive Proposition 2.1 within the framework of the present paper: using only Theorem 3.7, Lemma 3.4, and the definitions in Section 4, prove that m(v)=mult_GF(0,F(0)+v) is odd for every nonzero v when F is a quadratic APN function. As a computational cross-check, directly compute the parity of mult_GF(0,F(0)+v) for all v!=0 and for all known quadratic APN functions in dimensions n<=10 (e.g., Gold functions in n=6,8,10 and the Kim APN function in n=6); any even value would refute Proposition 2.1 and collapse Corollary 4.9.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of the paper, Corollary 4.9, derives the lower bound deg(v·pi_F)=n-2 from Theorem 4.8, whose hypothesis m_L(v) odd is supplied solely by Proposition 2.1 from the authors' previous paper [37]. Proposition 2.1 states that for every plateaued APN function F and every (a,b) outside the graph of F, the exclude multiplicity mult_GF(a,b) is odd; applied to quadratic APN functions, this gives m(v)=mult_GF(0,F(0)+v) odd for every nonzero v. The same proposition is also used in Proposition 4.2 to obtain the upper bound deg(pi_F)<=n-2 for crooked functions. If Proposition 2.1 were false for even one quadratic APN function and one v with m(v) even, Proposition 4.2 would force deg(v·pi_F)=n, directly contradicting Conjecture 1.1. The paper cites [37] but does not reproduce or even sketch the proof, and [37] is a co-authored self-citation; the reader cannot check the keystone from the present text. Other external dependencies, such as the plateaued-restriction facts from [22] and the Gold ortho-derivative formula, are not needed for the main conjecture, so this single unproved oddness result is the load-bearing concern.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":39377,"tokens_out":19812,"duration_ms":162785,"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":[{"comment":"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.","section":"§4, Corollary 4.9; §2, Proposition 2.1"},{"comment":"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.","section":"§5, Theorem 5.5 and Lemma 5.3"}],"minor_comments":[{"comment":"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.","section":"§4, Proposition 4.2 and §3, Proposition 3.9"},{"comment":"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.","section":"§2, Definition 4.3 and §5, Lemma 5.2"},{"comment":"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.","section":"§5.1, Proposition 5.12"},{"comment":"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.","section":"Abstract and §4"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is mathematically substantial and the main proof chain is credible, but the headline result is conditional on Proposition 2.1 of [37], a same-author publication whose proof is not reproduced. I would not recommend accepting the paper until that result is made verifiable from the present text, either by reproducing the proof or by giving a precise pointer and proof sketch. The additional dependencies on [22], an ePrint preprint, should also be clarified for the second main result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Chris,\n\nThe 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.\n\nThe 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.\n\nNow 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.\n\nIf [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.\n\nI 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.\n\nBest.","headline":"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.","tokens_in":39925,"tokens_out":2796,"would_cite":true,"duration_ms":27024,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"pith_extraction":{"msc":["11T71","94A60","05B99"],"pacs":[],"model":"deepseek-v4-flash","headline":"The 2020 conjecture is true: every nonzero ortho-derivative component of a quadratic APN function has degree n-2.","keywords":["crooked functions","almost perfect nonlinear functions","ortho-derivative","algebraic degree","exclude parity adjoint","bent functions","semi-bent functions","Walsh transform"],"falsifier":"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.","tokens_in":38914,"feed_emoji":"🧮","tokens_out":10328,"duration_ms":81603,"temperature":0.7,"pith_summary":"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.","feed_headline":"APN ortho-derivative components all have algebraic degree n-2","feed_subtitle":"Every nonzero component of the ortho-derivative has algebraic degree exactly n-2.","key_machinery":"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$.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Supplies Proposition 2.1, the oddness of exclude multiplicities for plateaued APN functions on which the lower-bound argument depends.","marker":"[37]"},{"why":"Establishes the earlier upper bound $\\deg(\\pi_F) \\le n-2$ for quadratic APN functions; the paper generalizes it and needs the exact equality statement.","marker":"[26]"},{"why":"Defines crooked functions and the ortho-derivative and supplies the subspace structure of preimages $\\pi_F^{-1}(b)$, used for vector space partitions and the semi-bent count.","marker":"[33]"},{"why":"Introduces the conjecture that every nonzero component of $\\pi_F$ has degree $n-2$, with computational evidence through dimension 11 for then-known quadratic APN functions.","marker":"[28]"},{"why":"Provides the characterization of functions whose restrictions to affine spaces are plateaued, used throughout for amplitudes and hyperplane restrictions.","marker":"[22]"},{"why":"Supplies the vector space partition theorem used to lift the existence of one semi-bent component to at least five.","marker":"[30]"},{"why":"Introduces the $m$-sequence exponential-sum problem and the conjecture that the paper partially resolves modulo 16.","marker":"[31]"}],"fun_headline_variants":["Quadratic APN ortho-derivative degree n-2: conjecture resolved","For quadratic APN, ortho-derivative components all have degree n-2","Ortho-derivative degree n-2 proven for all quadratic APN","APN ortho-derivative: every component reaches degree n-2","Crooked function ortho-derivative degree n-2 in quadratic case"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quadratic APN ortho-derivative degree n-2: conjecture resolved","For quadratic APN, ortho-derivative components all have degree n-2","Ortho-derivative degree n-2 proven for all quadratic APN","APN ortho-derivative: every component reaches degree n-2","Crooked function ortho-derivative degree n-2 in quadratic case"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000808,"raw_usage":{"total_tokens":3722,"prompt_tokens":1299,"completion_tokens":2423,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":915,"completion_tokens_details":{"reasoning_tokens":2324}},"tokens_in":915,"tokens_out":2423,"duration_ms":17405,"temperature":1.0,"reasoning_tokens":2324,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-28T00:04:40.186276+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"On lower bounds for the distances between APN functions","cited_arxiv_id":null,"evidence_quote":"Supplies Proposition 2.1, the oddness of exclude multiplicities for plateaued APN functions on which the lower-bound argument depends."},{"cited_title":"On the properties of the ortho-derivatives of quadratic functions","cited_arxiv_id":null,"evidence_quote":"Establishes the earlier upper bound $\\deg(\\pi_F) \\le n-2$ for quadratic APN functions; the paper generalizes it and needs the exact equality statement."},{"cited_title":"Kyureghyan","cited_arxiv_id":null,"evidence_quote":"Defines crooked functions and the ortho-derivative and supplies the subspace structure of preimages $\\pi_F^{-1}(b)$, used for vector space partitions and the semi-bent count."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the conjecture that every nonzero component of $\\pi_F$ has degree $n-2$, with computational evidence through dimension 11 for then-known quadratic APN functions."},{"cited_title":"Determining those Boolean functions whose restric- tions to affine spaces are plateaued","cited_arxiv_id":null,"evidence_quote":"Provides the characterization of functions whose restrictions to affine spaces are plateaued, used throughout for amplitudes and hyperplane restrictions."},{"cited_title":"On the length of the tail of a vector space partition","cited_arxiv_id":null,"evidence_quote":"Supplies the vector space partition theorem used to lift the existence of one semi-bent component to at least five."},{"cited_title":"Further results on m-sequences with five-valued cross correlation","cited_arxiv_id":null,"evidence_quote":"Introduces the $m$-sequence exponential-sum problem and the conjecture that the paper partially resolves modulo 16."}],"review_version":1}