Pith. sign in

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 →

arxiv 1908.08448 v2 pith:BX4UVIPR submitted 2019-08-22 cs.IT math.ITmath.RA

classification cs.ITmath.ITmath.RA MSC 94A6006E3011T71
keywords BooleanfunctionrotationsymmetricHamiltonweightbalancedaffineequivalencerecursionquadraticplateaued
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

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.

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.

Watch

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

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

5 major / 4 minor

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)
  1. [§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.
  2. [§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.
  3. [§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.
  4. [§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. [§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)
  1. [§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.
  2. [§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.
  3. [§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.
  4. [§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

0 steps flagged · score 0.0 of 10

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 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted to data; the constants c(Q) and d(Q) in Theorem 5.3 are existential and derived, not fitted. The axioms are standard finite-field theorems plus cited results from [1], [4], [8], [11], [12], and [25]. There are no invented entities.

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.
    Used in Section 3 to define R'(t) and in Section 5 to obtain u(n) sequences; no proof is repeated here.
  • 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]).
    Basis for counting affine equivalence classes in Theorem 4.3 and for the claim that weight plus nonlinearity determine the class.
  • 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).
    Connects Boolean RS functions to trace forms used throughout Section 5.
  • 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]).
    Load-bearing formula for all v-value computations and the proof of Theorem 5.3.
  • standard math Standard facts: finite field traces, Frobenius automorphism, linearized polynomials, Skolem-Mahler-Lech theorem, and Dickson's classification of quadratic forms.
    Invoked in Sections 2, 5.1, and 5.2 without proof.

how reviews work

0 comments
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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    Anbar, W

    N. Anbar, W. Meidl and A. Topuzoglu, Idempotent and p-pot ent quadratic functions: distri- bution of nonlinearity and co-dimension, Des. Codes Cryptogr. 82, pp. 265-291, 2017

  2. [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

  3. [3]

    Brown and T

    A. Brown and T. W. Cusick, Recursive weights for some Bool ean functions, J. Math. Cryptol. 6, pp. 105-135, 2012

  4. [4]

    Carlet, G

    C. Carlet, G. Gao and W. Liu, A secondary construction and a transformation on rotation symmetric functions, and their action on bent and semi-bent functions, J. Combin. Theory Ser. A 127, pp. 161–175, 2014

  5. [5]

    J. W. S. Cassels, Local fields (Cambridge University Press, Cambridge, 1986)

  6. [6]

    Chirvasitu and T

    A. Chirvasitu and T. W. Cusick, Dynamical systems proof o f existence of weight recursions for rotation symmetric functions, to appear

  7. [7]

    Crama and P

    Y. Crama and P. Hammer, Boolean Models and Methods in Mathematics, Computer Science and Engineering (Cambridge: Cambridge University Press, 2010)

  8. [8]

    T. W. Cusick, Affine equivalence of cubic homogeneous rota tion symmetric functions, Inform. Sci. 181, pp. 5067-5083, 2011

Show all 25 references
  1. [9]

    T. W. Cusick, Finding Hamming weights without looking at truth tables, Cryptogr. Commun. 5, pp. 7-18, 2013

  2. [10]

    T. W. Cusick, Permutation equivalence of cubic rotatio n symmetric functions, Int. J. Comput. Math. 92, pp. 1568-1573, 2015

  3. [11]

    T. W. Cusick, Weight recursions for any rotation symmet ric Boolean functions, https://arxiv.org/abs/1701.06648, 18 pp., 2017

  4. [12]

    T. W. Cusick, Weight recursions for any rotation symmet ric Boolean functions, IEEE Trans. Inform. Theory 64, pp. 2962-2968, 2018

  5. [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

  6. [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

  7. [15]

    T. W. Cusick and P. St˘ anic˘ a, Fast evaluation, weightsand nonlinearity of rotation symmetric functions, Discr. Math. 258, pp. 289-301, 2002

  8. [16]

    T. W. Cusick and P. St˘ anic˘ a,Cryptographic Boolean Functions and Applications , second ed. (San Diego: Academic Press, 2017). First edition 2009

  9. [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

  10. [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

  11. [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

  12. [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

  13. [21]

    MacWilliams and N.J.A

    F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes (North-Holland, Amsterdam, 1978)

  14. [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

  15. [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

  16. [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

  17. [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

Pith tools

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