REVIEW 5 major objections 4 minor 25 references
Affine equivalence for quadratic rotation symmetric Boolean functions
T0 review · 5 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Quadratic rotation-symmetric Boolean functions are balanced exactly when a gcd-based criterion says so; monomial ones split into τ(n)−1 affine equivalence classes.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (5)
- [§5.4, Theorem 5.36] 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.
- [§5.2, Proposition 5.21] 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.
- [§5, Theorem 5.2] 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.
- [§3, Theorem 3.4] 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.
- [§5, Theorem 5.3] 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.
minor comments (4)
- [§2, Theorem 2.1 proof] 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.
- [§5, equation (5-9)] 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.
- [§5.4, Example 5.37] 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.
- [§5, Theorem 5.3] 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.
Circularity Check
No circularity found: the main balancedness theorem is derived from field-theoretic arguments and independent gcd/linearized-polynomial results, not from fitted parameters or definitional equivalences.
full rationale
The paper's central claim, Theorem 5.3, is derived from a chain of field-theoretic reductions (trace representations, Frobenius actions, linearized polynomials) rather than from the weight-recursion algorithm or from data fitting. Theorem 2.1 proves that balancedness is preserved under the passage from an RS quadratic function to its trace form, using Walsh-transform identities and independent results from Carlet-Gao-Liu, Crama-Hammer, and Wu-Liu. Lemma 3.13, which supplies the v-value formula v(n) = deg gcd(x^n - 1, A(x)), is quoted from Anbar-Meidl-Topuzoglu [1] and has a published proof; it is an external, checkable computation and is not derived from the paper's own conclusions. Theorem 3.4 obtains the recursion polynomial for MRS quadratics by explicit matrix computation, not by fitting weights, and the cited recursion algorithm of [11,12] is used only illustratively in examples. Lemma 1.1 is a self-citation to Cusick [8], and it is load-bearing for the affine-equivalence counting in Section 4, but it is a standard classification with a published proof and its assumptions do not include the target balancedness characterization. The known proof gap in the odd-number-of-terms case (Proposition 5.21 is stated without a full proof, and Theorem 5.36 says the argument can be replicated 'virtually verbatim') is a completeness or correctness concern, not a circularity: the missing step is a logical implication within the proof, not an input that has been renamed as a prediction. No parameter is fitted to a subset of data and then used to predict a closely related quantity; no theorem is imported solely from the present authors to forbid alternatives; and no known result is merely renamed. Accordingly, no circular step can be exhibited, and the appropriate finding is no significant circularity.
Assumptions & free parameters
assumptions (5)
- domain assumption The rules matrix algorithm of [11,12] correctly computes the minimal polynomial whose non-x part defines the weight recursion for any rotation symmetric Boolean function.
- domain assumption Lemma 1.1: two quadratic Boolean functions are affine equivalent iff they have the same weight and nonlinearity (proof cited to [8, Lemma 2.3]).
- domain assumption The trace representation Q'(x)=Q(x,x^2,...,x^{2^{n-1}}) preserves nonlinearity for quadratics ([4, Theorem 5.1]) and balancedness (Theorem 2.1, proved here).
- domain assumption The plateau parameter of a quadratic RS function is v(n) = deg gcd(x^n - 1, A_n(x)) (Lemma 3.13, cited from [1, Section 2]).
- standard math Standard facts: finite field traces, Frobenius automorphism, linearized polynomials, Skolem-Mahler-Lech theorem, and Dickson's classification of quadratic forms.
Cite this review
Pith. "Pith review of Affine equivalence for quadratic rotation symmetric Boolean functions." pith.science (2026). https://pith.science/paper/BX4UVIPR
@misc{pith2026190808448,
author = {Pith},
title = {Pith review of: Affine equivalence for quadratic rotation symmetric Boolean functions},
year = {2026},
howpublished = {\url{https://pith.science/paper/BX4UVIPR}},
note = {Machine review of arXiv:1908.08448}
}
abstract
Let $f_n(x_0, x_1, \ldots, x_{n-1})$ denote the algebraic normal form (polynomial form) of a rotation symmetric (RS) Boolean function of degree $d$ in $n \geq d$ variables and let $wt(f_n)$ denote the Hamming weight of this function. Let $(0, a_1, \ldots, a_{d-1})_n$ denote the function $f_n$ of degree $d$ in $n$ variables generated by the monomial $x_0x_{a_1} \cdots x_{a_{d-1}}.$ Such a function $f_n$ is called monomial rotation symmetric (MRS). It was proved in a $2012$ paper that for any MRS $f_n$ with $d=3,$ the sequence of weights $\{w_k = wt(f_k):~k = 3, 4, \ldots\}$ satisfies a homogeneous linear recursion with integer coefficients. This result was gradually generalized in the following years, culminating around $2016$ with the proof that such recursions exist for any rotation symmetric function $f_n.$ Recursions for quadratic RS functions were not explicitly considered, since a $2009$ paper had already shown that the quadratic weights themselves could be given by an explicit formula. However, this formula is not easy to compute for a typical quadratic function. This paper shows that the weight recursions for the quadratic RS functions have an interesting special form which can be exploited to solve various problems about these functions, for example, deciding exactly which quadratic RS functions are balanced.
Reference graph
Works this paper leans on
- [1]
-
[2]
M. L. Bileschi, T. W. Cusick and D. Padgett, Weights of Boo lean cubic monomial rotation symmetric functions, Cryptogr. Commun. 4, pp. 105-130, 2012
work page 2012
-
[3]
A. Brown and T. W. Cusick, Recursive weights for some Bool ean functions, J. Math. Cryptol. 6, pp. 105-135, 2012
work page 2012
- [4]
-
[5]
J. W. S. Cassels, Local fields (Cambridge University Press, Cambridge, 1986)
work page 1986
-
[6]
A. Chirvasitu and T. W. Cusick, Dynamical systems proof o f existence of weight recursions for rotation symmetric functions, to appear
-
[7]
Y. Crama and P. Hammer, Boolean Models and Methods in Mathematics, Computer Science and Engineering (Cambridge: Cambridge University Press, 2010)
work page 2010
-
[8]
T. W. Cusick, Affine equivalence of cubic homogeneous rota tion symmetric functions, Inform. Sci. 181, pp. 5067-5083, 2011
work page 2011
Show all 25 references
-
[9]
T. W. Cusick, Finding Hamming weights without looking at truth tables, Cryptogr. Commun. 5, pp. 7-18, 2013
2013
-
[10]
T. W. Cusick, Permutation equivalence of cubic rotatio n symmetric functions, Int. J. Comput. Math. 92, pp. 1568-1573, 2015
2015
-
[11]
T. W. Cusick, Weight recursions for any rotation symmet ric Boolean functions, https://arxiv.org/abs/1701.06648, 18 pp., 2017
2017 arXiv
-
[12]
T. W. Cusick, Weight recursions for any rotation symmet ric Boolean functions, IEEE Trans. Inform. Theory 64, pp. 2962-2968, 2018
2018
-
[13]
T. W. Cusick and B. Johns, Recursion orders for weights o f Boolean cubic rotation symmetric functions, Discr. Appl. Math. 186, pp. 1-6, 2015
2015
-
[14]
T. W. Cusick, Y. Li and P. St˘ anic˘ a, On a conjecture for balanced symmetric Boolean functions, J. Math. Cryptol. 3, pp. 273-290, 2009
2009
-
[15]
T. W. Cusick and P. St˘ anic˘ a, Fast evaluation, weightsand nonlinearity of rotation symmetric functions, Discr. Math. 258, pp. 289-301, 2002
2002
-
[16]
T. W. Cusick and P. St˘ anic˘ a,Cryptographic Boolean Functions and Applications , second ed. (San Diego: Academic Press, 2017). First edition 2009
2017
-
[17]
Everest, A
G. Everest, A. van der Poorten, I. Shparlinski and T. War d: Recurrence Sequences. Math. Surveys Monographs 104 (Providence: American Mathematica l Society, 2003). 28
2003
-
[18]
G. Gao, X. Zhang, W. Liu and C. Carlet, Constructions of q uadratic and cubic rotation symmetric bent functions, IEEE Trans. Inform. Theory 58, pp. 4908-4913, 2012
2012
-
[19]
K. Khoo, G. Gong and D. Stinson, A new characterization o f semi-bent and bent functions on finite fields. Des. Codes Cryptogr. 38, pp. 279-295, 2006
2006
-
[20]
Kim, S.-M
H. Kim, S.-M. Park and S. G. Hahn, On the weight and nonlin earity of homogeneous rotation symmetric Boolean functions of degree 2, Discr. Appl. Math. 157, pp. 428-432, 2009
2009
-
[21]
MacWilliams and N.J.A
F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes (North-Holland, Amsterdam, 1978)
1978
-
[22]
Pieprzyk and C
J. Pieprzyk and C. X. Qu, Fast hashing and rotation-symm etric functions, J. Univers. Comput. Sci. 5 (1), pp. 20-31, 1999
1999
-
[23]
Su and X.Tang, On the systematic constructions of rot ation symmetric bent functions with any possible algebraic degrees
S. Su and X.Tang, On the systematic constructions of rot ation symmetric bent functions with any possible algebraic degrees. http://epr int.iacr.org/2015/451 or https://arxiv.org/abs/1505.02875, 20 pp., 2015
2015 arXiv
-
[24]
C. Tang, Y. Qi, Z. Zhou and C. Fan, Two infinite classes of r otation symmetric bent functions with simple representation. https://arxiv.org/abs/1508 .05674v2, 7 pp., 2015
2015
-
[25]
Wu and Z
B. Wu and Z. Liu, Linearized polynomials over finite field s revisited, Finite Fields Appl. 22, pp. 79–100, 2013. 29
2013
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.