{"id":"22fc42c5-e152-4a16-bf9c-aff8cd6d4a7c","arxiv_id":"1908.08448","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For quadratic rotation-symmetric Boolean functions, balancedness is determined by the 2-adic valuation of the number of variables, and the monomial functions have explicit weight-recursion polynomials.","lead":"This paper derives explicit formulas for the Hamming-weight recursions of quadratic rotation-symmetric Boolean functions and uses them to characterize when such functions are balanced. It also counts the affine equivalence classes for the monomial subclass.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The odd half of Theorem 5.3 is supported only by a sketched 'virtually verbatim' argument (Theorem 5.36) plus unproved Proposition 5.21; this gap should be closed before acceptance.","rationale":"The reader's conditional verdict identifies Lemma 3.13 as the weakest assumption, but that lemma is imported from a published source ([1]) and is a standard gcd characterization of plateau parameters for idempotent quadratic functions. The more immediately load-bearing issue is internal: the proof of the odd half of the main theorem is explicitly sketched rather than written. Theorem 5.36 depends on Proposition 5.21, which is stated without proof, and on a nontrivial semi-equitability argument that is compressed into a single sentence. The paper's examples and the general shape of the argument make the theorem plausible, and I found no counterexample by hand, but the missing derivation is exactly the part that would rule out the 'initial segment with one missing element' possibility from Proposition 5.35. Because the central claim has two asymmetric halves, the unproven odd case is the part most likely to hide a parity error. The suggested exhaustive check for small J and n would either confirm the structural prediction or expose a concrete counterexample, and it would also test Proposition 5.21. Thus the appropriate verdict remains conditional on supplying the missing proof or verification.","tokens_in":24621,"tokens_out":30531,"duration_ms":295033,"concrete_test":"Enumerate all quadratic RS functions with exponent set {i : a_i = 1} for max exponent J ≤ 4 and all n ≤ 16. For each function, compute balancedness directly from the truth table of the trace form Q_n (or from the ANF for n ≥ 2J+1), and compare it with the prediction of Theorem 5.3, where c(Q) or the even-case modulus is computed from d_Q and the semi-equitability of the exponent multiset modulo powers of 2. In addition, for all such Q and ν ≤ 4, verify Proposition 5.21 directly: under the hypothesis 2^ν ≤ d_Q, Q_{2^ν} is unbalanced exactly when it is identically zero. Any mismatch, especially an initial segment with one missing element in the odd case, would refute Theorem 5.3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing weakness is internal to the proof of the odd-number-of-terms case of Theorem 5.3. Theorem 5.36 is not actually proven: its text says the argument is 'very similar to that in Theorem 5.32, and can in fact be replicated virtually verbatim,' but the only paragraph present contains the crucial step 'for ν < ν_Q the set of exponents of Q fails to be semi-equitable, making Q_{2^ν} balanced by Proposition 5.34.' This inference is not licensed by Proposition 5.34 alone, since that proposition only equates identical vanishing with semi-equitability. To conclude 'balanced' one must also use Proposition 5.21 ('If 2^ν ≤ d_Q then Q_n is unbalanced if and only if it is identically zero'), which is stated without proof. Proposition 5.21 is the bridge that rules out the 'initial segment with one missing element' alternative left open in Proposition 5.35; without it the odd half of Theorem 5.3 collapses. The parity/equitability case analysis for ν < ν_Q is omitted, including configurations with several odd-valuation groups above μ_0 and the edge case ν = 0. Since no code or exhaustive data accompany the paper, the missing 'virtually verbatim' proof cannot be checked by the reader. A secondary concern is Lemma 3.13, quoted from [1], but that result has a published proof; the decisive gap is internal.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies quadratic rotation symmetric (RS) Boolean functions, using the standard trace representation Q_n(x) = Tr_n(∑ a_i x^{2^i+1}) on GF(2^n). Its main result, Theorem 5.3, asserts that if Q has an odd number of nonzero coefficients a_i, then Q_n is balanced for all n except those with n ≡ 0 mod 2^{c(Q)} for some integer c(Q); if the number of nonzero coefficients is even, then Q_n is either never balanced or balanced exactly for n ≡ 2^{d(Q)-1} mod 2^{d(Q)} for some integer d(Q). The paper also gives the explicit weight recursion polynomial (x − 2)(x^{2t} − 2^t) for monomial quadratic RS functions (Theorem 3.4) and counts affine equivalence classes for monomial quadratics (Theorem 4.3). The proof of Theorem 5.3 is based on field-theoretic tools (trace, Frobenius, linearized polynomials) rather than on the earlier recursion algorithm.","tokens_in":24900,"tokens_out":38753,"duration_ms":322719,"significance":"If the balancedness characterization is correct, it is a complete and elegant solution for quadratic RS functions, and via Lemma 1.1 yields a practical route to affine equivalence classification. The paper includes explicit worked examples and uses published results appropriately. However, the proof has several gaps, notably in the odd-number-of-terms half of the main theorem (Theorem 5.36), an unproved key lemma (Proposition 5.21), an incomplete proof of the v-value period theorem (Theorem 5.2), and an unverified computation in Theorem 3.4. These gaps need to be closed before the claims are fully supported.","major_comments":[{"comment":"The proof of Theorem 5.36 is not self-contained: it says the argument is 'virtually verbatim' from Theorem 5.32 but does not provide the case analysis. The final step claims that for ν < ν_Q the set of exponents of Q fails to be semi-equitable, 'making Q_{2^ν} balanced by Proposition 5.34'. Proposition 5.34 only characterizes identical vanishing in terms of semi-equitability; the conclusion 'balanced' also requires Proposition 5.21. The edge case ν = 0 and configurations with several odd-valuation groups above μ_0 are not treated. Since Theorem 5.36 is half of the main theorem, a complete proof must be supplied.","section":"§5.4, Theorem 5.36"},{"comment":"Proposition 5.21 (if 2^ν ≤ d_Q then Q_{2^ν} is unbalanced if and only if it is identically zero) is stated without proof. It is used in the proofs of Proposition 5.31 and Theorem 5.36, and it is the bridge that turns non-vanishing into balancedness. The statement is true and can be proved by the same kernel-containment argument as Proposition 5.20, but the manuscript only says 'essentially the same argument proves' it. The proof must be written out.","section":"§5.2, Proposition 5.21"},{"comment":"The proof of Theorem 5.2 asserts without proof that the quantity K = 2^t(2^k − 1) satisfies (5-5): 'A(x) divides x^n − 1 if and only if x^K − 1 does, if and only if K divides n', and (5-6) that K is the smallest period of {v(n)}. As written, (5-5) appears to be false: the divisibility A(x) | x^n − 1 is governed by the least common multiple of the orders of the roots of A (together with a power of 2 for multiplicities), which need not be a Mersenne number of the form 2^k − 1. Since Theorem 5.2 underlies Corollary 5.17 and hence Proposition 5.35, the authors must either correct the definition of K or give a full proof.","section":"§5, Theorem 5.2"},{"comment":"The proof of Theorem 3.4 consists of 'Routine computation' for the identity R(t)^t = M(t) and the claim that R(t)^{2t} = 2^t I implies the minimal polynomial is x^{2t} − 2^t. The latter does not follow without proving that no smaller-degree polynomial annihilates R(t); the former needs a detailed derivation. Moreover, the minimal polynomial of the augmented rules matrix R'(t) is asserted to be (x − 2)(x^{2t} − 2^t) without proof. Since Theorem 3.4 is a main result of the paper (the special form of weight recursions), the missing arguments should be provided.","section":"§3, Theorem 3.4"},{"comment":"The theorem is stated with unspecified constants c(Q) and d(Q). The proof of Theorem 5.36 shows only that the set of 2-adic valuations for which Q is balanced is an 'initial interval' but does not state its endpoint or how to compute it; thus the theorem, as stated, does not provide the promised decision procedure. The even case is more explicit (d(Q) = ν_Q + 1 if balanced at ν_Q), but the odd case needs a statement such as: balanced for ν(n) ≤ ν_Q or ν_Q − 1 according as Q_{2^{ν_Q}} does or does not vanish identically.","section":"§5, Theorem 5.3"}],"minor_comments":[{"comment":"The inference |W_f(0)| = 2^n − 2N(f) for unbalanced f is attributed to Lemma 3.7 and (2-4), but it also depends on the Dickson-form facts from Lemma 3.5/3.8; the references should be expanded.","section":"§2, Theorem 2.1 proof"},{"comment":"The notation Tr_{GF(2^n)/GF(2^{2ν})} is confusing; use a clearer notation such as \\mathrm{Tr}_{2ν}^{n} or specify the trace as the intermediate trace in words.","section":"§5, equation (5-9)"},{"comment":"The initial segment of u(n) is given for n = 1 through 16, but the recursion is valid only for n ≥ 7; the text does explain this, but a less misleading presentation would separate recursion values from actual weights for n < 7.","section":"§5.4, Example 5.37"},{"comment":"The notation Q(a_1, ..., a_{[(n-1)/2]}) is misleading because Q is fixed while n varies; use J or a fixed bound for the number of terms.","section":"§5, Theorem 5.3"}],"recommendation":"major_revision","confidential_remarks":"The manuscript relies heavily on the authors' own previous results ([11,12] for recursions and [8] for Lemma 1.1). This is not a problem per se, but the companion reference [6] is 'to appear' and is used as a forward reference for the root conjecture; that is acceptable. The main concern is the incompleteness of the proofs of Theorems 5.36, 5.2, and 3.4, which should be addressed in revision. The central balancedness result appears defensible, so I do not recommend rejection, but the missing proofs are load-bearing and must be supplied."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, this paper is worth remembering. The headline result, Theorem 5.3, says that balancedness of any quadratic rotation-symmetric Boolean function is determined by n modulo a power of 2, with the modulus read off from a gcd formula. If true, that is the complete story for a class of functions that matter in cryptography, and it has a clean consequence: the affine equivalence classes of MRS quadratics are counted by tau(n) - 1. The v(n) = gcd(2t, n) formula and the explicit recursion polynomial (x - 2)(x^{2t} - 2^t) are genuinely new and well-motivated. The proof strategy is coherent: reduce to n a power of 2 via trace factorization, then analyze the kernel of a linearized polynomial.\n\nNow the soft spots. The stress-test note lands correctly on the odd case. Theorem 5.36 is not a proof; it says the argument is 'virtually verbatim' and then gives only the final step, which depends on Proposition 5.21. That proposition — if 2^nu <= d_Q then unbalanced iff identically zero — is stated without proof and is load-bearing. It is exactly the statement that excludes the 'initial segment with one missing element' option in Proposition 5.35. Without it, the odd half of the main theorem collapses. This is not a stylistic complaint; the missing lemma needs a proof or a pointer to one. Similarly, Theorem 3.4's matrix identity is dispatched as 'routine computation'; that is a smaller gap, but the reader cannot check it.\n\nWhere I part ways with the stress-test note: Lemma 3.13 is quoted from Anbar-Meidl-Topuzoglu with a published proof; that is fine. And the even-number-of-terms case is actually written out, with cases, in Theorem 5.32. The gap is concentrated in the odd case. I would not call the paper unserious — the field-theoretic infrastructure is solid and the examples match the stated results — but as it stands the main theorem is not fully proven. No code or exhaustive data is provided, so the sketched verification cannot be checked mechanically.\n\nWho is this for? People working on rotation-symmetric Boolean functions, weight recursions, and quadratic forms over GF(2). If the gap is filled, it will be a natural citation for the balancedness classification. I would send it to a competent referee rather than desk reject; the result is significant enough that the community needs a definitive version. The referee should insist on a written proof of Proposition 5.21 and a fleshed-out Theorem 5.36.","headline":"A plausible and useful classification of balanced quadratic RS functions, but the odd-number-of-terms half rests on an unproved proposition and a sketch, so it needs referee pressure before acceptance.","tokens_in":25460,"tokens_out":2058,"would_cite":true,"duration_ms":20562,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A60","06E30","11T71"],"pacs":[],"model":"deepseek-v4-flash","headline":"Quadratic rotation-symmetric Boolean functions are balanced exactly when a gcd-based criterion says so; monomial ones split into τ(n)−1 affine equivalence classes.","keywords":["Boolean function","rotation symmetric","Hamilton weight","balanced function","affine equivalence","weight recursion","quadratic Boolean function","plateaued function"],"falsifier":"Take Q_n = Tr_n($x^{3}$+$x^{5}$+$x^{7}$), the coefficients a_1=a_2=a_3=1 of Example 5.37. The theorem predicts balanced exactly for n not divisible by 4, so compute the truth-table weight or W_{Q_n}(0) directly for n=4,8,12 (should be unbalanced) and n=2,6,10 (should be balanced); any disagreement refutes the characterization. More generally, one can compute the plateau parameter from the Walsh spectrum of any small-n Q_n and compare it with v(n)=deg gcd(x^n−1,A(x)); the first mismatch settles the question.","tokens_in":24408,"feed_emoji":"⚖️","tokens_out":8854,"duration_ms":79157,"temperature":0.7,"pith_summary":"The paper gives a complete answer to when a quadratic rotation-symmetric (RS) Boolean function is balanced, i.e. has equally many 0s and 1s in its truth table. It proves that for any such function Q written as a sum of terms Tr_n($x^{{2i+1}}$), balancedness is governed by the degree of a single gcd, deg gcd(x^n−1, A(x)), and in the end by the residue of n modulo a power of two: an odd number of nonzero terms forces balance for every n except those divisible by $2^{{c(Q)}}$, and an even number forces either never-balanced or balance exactly for n ≡ $2^{{d(Q)−1}}$ mod $2^{{d(Q)}}$. This matters because for quadratic functions, weight and nonlinearity together determine affine equivalence, so the criterion classifies the affine equivalence classes; for monomial RS quadratics the count of classes in n variables is exactly τ(n)−1.","feed_headline":"A gcd tells when rotation-symmetric quadratics balance","feed_subtitle":"For these Boolean functions, balancing reduces to one residue class mod a power of two, which also classifies them.","key_machinery":"The engine of the paper is the gcd formula for the plateau parameter: for Q=Σ a_i(0,i)_n, set A(x)=Σ a_i(x^i+$x^{{−i}}$) in the Laurent polynomial ring GF(2)[$x^{{±1}}$]; then v(n)=deg gcd(x^n−1,A(x)). Every quadratic Boolean function is plateaued, so v(n) fixes the Walsh spectrum and hence the nonlinearity, and the linearized-polynomial criterion turns balancedness into a statement about this gcd. The other mechanism is the rules matrix R'(t) for monomial quadratics, whose minimal polynomial is (x−2)($x^{{2t}}$−2^t); it carries the weight recursion computation that Theorem 3.4 makes explicit.","core_discovery":"The central claim is a complete balancedness characterization for quadratic RS Boolean functions in the trace form Q_n(x)=Tr_n(Σ a_i $x^{{2i+1}}$). Theorem 5.3 states that with an odd number of nonzero a_i, Q_n is balanced for all n except n ≡ 0 mod $2^{{c(Q)}}$ for some integer c(Q); with an even number, Q_n is either never balanced or balanced precisely for n ≡ $2^{{d(Q)−1}}$ mod $2^{{d(Q)}}$. The proof runs through the equivalence between Q and its trace representation, the reduction of balancedness to vanishing on the kernel of the linearized polynomial Σ a_i($x^{{2^{n−i}}$}+$x^{{2^i}}$), and the gcd formula v(n)=deg gcd(x^n−1,A(x)) for the plateau parameter. In the monomial case the paper also proves the explicit weight recursion polynomial (x−2)($x^{{2t}}$−2^t), and, via weight-nonlinearity equivalence, counts the affine equivalence classes as τ(n)−1.","pith_inferences":["The theorem states the constants c(Q) and d(Q) exist but does not give formulas for them; a natural next step is to compute them directly from the multiplicity of x−1 in A(x), which would turn the classification into a closed formula.","Since v(n) = deg gcd(x^n−1,A(x)) is periodic with period equal to the order of A(x) modulo x^n−1, the set of non-balanced dimensions is probably a finite union of residue classes that can be listed algorithmically from A(x) alone.","The same linearized-polynomial route suggests a testable conjecture for cubic RS functions: balancedness may again depend only on n modulo a power of two, with the obstruction coming from a gcd formula yet to be found."],"forward_implications":["For any concrete quadratic RS function given by its coefficients a_i, one can compute v(n) by a single gcd and read off whether f_n is balanced for each n, without constructing truth tables.","For quadratics, equal weight and equal nonlinearity are necessary and sufficient for affine equivalence, so the balancedness criterion yields a complete affine-equivalence classification of quadratic RS functions.","The monomial functions (0,t)_n have exactly τ(n)−1 affine equivalence classes in n variables, one for each possible value of gcd(n,t).","The recursion polynomial x^{2t+1}−2x^{2t}−2^t x+2^{t+1}=(x−2)(x^{2t}−2^t) computes all weights of a monomial quadratic once the first 2t+1 values are known.","Because balancedness depends only on the 2-adic valuation of n, a balanced dimension n forces balance at every odd multiple of n."],"supporting_citations":[{"why":"Introduces the trace representation Q' of a quadratic RS function Q and proves that nonlinearity is preserved in the quadratic case, a step used in Theorem 2.1.","marker":"[4]"},{"why":"Supplies the linearized-polynomial machinery, including the intertwining relation and the GF(2)-structure result needed to equate balancedness of Q and Q'.","marker":"[25]"},{"why":"Provides Lemma 3.13, the gcd formula v(n)=deg gcd(x^n−1,A(x)) for the plateau parameter of general quadratic RS functions, on which Theorem 5.3 rests.","marker":"[1]"},{"why":"Gives the weight and nonlinearity formulas for monomial quadratic RS functions and the Dickson-rank lemmas used in Theorems 3.9 and 4.3.","marker":"[20]"},{"why":"Describes the algorithm and rules matrix for weight recursions of RS functions, which Theorems 3.1 and 3.4 make explicit for quadratics.","marker":"[12]"},{"why":"Provides the lemma that two quadratic functions are affinely equivalent exactly when their weights and nonlinearities agree, the bridge to affine-equivalence classification.","marker":"[8]"}],"fun_headline_variants":["Quadratic RS balance: one gcd test, one residue class","A single gcd classifies balanced quadratic RS functions","Balancedness of RS quadratics reduces to a gcd check","One gcd decides when quadratic RS functions balance"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's classification rests on a quoted identity it does not prove: the plateau parameter of any quadratic RS function equals deg gcd(x^n−1,A(x)); should that identity fail for a single function, the congruence description of balanced dimensions would no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["Quadratic RS balance: one gcd test, one residue class","A single gcd classifies balanced quadratic RS functions","Balancedness of RS quadratics reduces to a gcd check","One gcd decides when quadratic RS functions balance"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000329,"raw_usage":{"total_tokens":1895,"prompt_tokens":1064,"completion_tokens":831,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":680,"completion_tokens_details":{"reasoning_tokens":766}},"tokens_in":680,"tokens_out":831,"duration_ms":8372,"temperature":1.0,"reasoning_tokens":766,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:44:12.640475+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take Q_n = Tr_n($x^{3}$+$x^{5}$+$x^{7}$), the coefficients a_1=a_2=a_3=1 of Example 5.37. The theorem predicts balanced exactly for n not divisible by 4, so compute the truth-table weight or W_{Q_n}(0) directly for n=4,8,12 (should be unbalanced) and n=2,6,10 (should be balanced); any disagreement refutes the characterization. More generally, one can compute the plateau parameter from the Walsh spectrum of any small-n Q_n and compare it with v(n)=deg gcd(x^n−1,A(x)); the first mismatch settles the question.","supporting_citations":[{"cited_title":"Carlet, G","cited_arxiv_id":null,"evidence_quote":"Introduces the trace representation Q' of a quadratic RS function Q and proves that nonlinearity is preserved in the quadratic case, a step used in Theorem 2.1."},{"cited_title":"Wu and Z","cited_arxiv_id":null,"evidence_quote":"Supplies the linearized-polynomial machinery, including the intertwining relation and the GF(2)-structure result needed to equate balancedness of Q and Q'."},{"cited_title":"Anbar, W","cited_arxiv_id":null,"evidence_quote":"Provides Lemma 3.13, the gcd formula v(n)=deg gcd(x^n−1,A(x)) for the plateau parameter of general quadratic RS functions, on which Theorem 5.3 rests."},{"cited_title":"Kim, S.-M","cited_arxiv_id":null,"evidence_quote":"Gives the weight and nonlinearity formulas for monomial quadratic RS functions and the Dickson-rank lemmas used in Theorems 3.9 and 4.3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Describes the algorithm and rules matrix for weight recursions of RS functions, which Theorems 3.1 and 3.4 make explicit for quadratics."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the lemma that two quadratic functions are affinely equivalent exactly when their weights and nonlinearities agree, the bridge to affine-equivalence classification."}],"review_version":1}