PaperlayerView exact revision on arXiv

Source-linked AI summary

Low-degree polynomials lower bounds for clustering in small dimension

Alexandra Carpentier, Nicolas Verzelen

arXiv:2610.37272v1stat.MLcs.LG

TL;DR

For K ≫ d, tensor procedures require a large, non-explicit polynomial sample size, whereas existing low-degree bounds only establish n ≳log dK^2. The paper constructs a 2K-component Bernoulli mixture whose BCH-code centers match Rademacher moment tensors through order 2m + 1. With polylogarithmic separation, low-degree polynomials require n ≳log K^2d^(3/2) observations.

  • Problem

    For K ≫ d, tensor procedures require a large, non-explicit polynomial sample size, whereas existing low-degree bounds only establish n ≳log dK^2.

    Source: §1.2 · p. 3, §2 · p. 7

  • Method

    The paper constructs a 2K-component Bernoulli mixture whose BCH-code centers match Rademacher moment tensors through order 2m + 1.

    Source: §1.3 · p. 3, §2 · p. 6

  • Results

    With polylogarithmic separation, low-degree polynomials require n ≳log K^2d^(3/2) observations.

    Source: §2 · p. 7

  • Takeaways & Limitations

    The result gives a low-degree computational lower bound for clustering with many groups, and Gaussianization carries the hardness to isotropic Gaussian mixtures in the sense of reductions.

    Source: §2 · p. 7

    Whether the remaining factor-d gap to the sample size at which the empirical tensor becomes informative can be closed is left open; the conjectured procedure would rely on knowing the BCH structure.

    Source: §4 · p. 10

Abstract

from arXiv · show

We study the computational limits of clustering $n$ observations drawn from a mixture of $K$ isotropic distributions in $\mathbb R^d$, in the regime where the number $K$ of groups is much larger than the dimension $d$. In this regime, tensor-based procedures recover the partition with a polylogarithmic separation between the centers, but they require a sample size that is a large and non-explicit polynomial of $dK$, whereas the existing low-degree lower bounds only show that $n$ must be larger than $dK^2$. We introduce a mixture of $2K$ product Bernoulli distributions on $\{0,1\}^d$, with $K=(d+1)^m$, whose centers are built from a dual BCH code. This construction ensures that the moment tensors of the observations coincide with those of the uniform distribution on $\{-1,1\}^d$ up to the order $2m+1$. For any fixed $m$, we establish a low-degree polynomial lower bound showing that clustering is hard as long as the separation $\Delta$ satisfies $\Delta^2\ll(K^2d^{3/2}/n)^{1/(2m+2)}\wedge\sqrt d$, up to polylogarithmic factors. In particular, with a polylogarithmic separation, low-degree polynomials require $n\gtrsim K^2d^{3/2}$ observations, up to polylogarithmic factors. Through a Gaussianization argument, this hardness carries over, in the sense of reductions, to isotropic Gaussian mixtures. Our proof relies on a family of polynomials of the observations, indexed by bipartite graphs, which is almost orthonormal. The moments of these polynomials are governed by the number of solutions of polynomial systems over the finite field $\mathbb F\_{d+1}$ that are induced by the BCH code, and the crux of our analysis is to connect the combinatorial structure of the bipartite graphs with the structure of the solution sets of these systems.

1 Introduction

The paper studies computational limits of clustering when the number of groups greatly exceeds dimension, where available algorithms and low-degree lower bounds leave the sample-complexity picture unresolved. It constructs Bernoulli-mixture instances with BCH-code centers and proves a stronger low-degree lower bound in this regime.

1.2 Polynomial-time algorithms and low-degree lower bounds

  • For K much larger than d, existing tensor procedures achieve polylogarithmic separation but require a large, non-explicit polynomial sample size, while the prior low-degree bound only requires n ≳log dK^2.This motivates asking for the polynomial-time separation and sample-size thresholds in the many-groups regime.Source: §1.2 · p. 3

1.3 Our contribution

  • For fixed m, the lower bound applies to instances with K = (d + 1)^m and separation satisfying the stated signal condition.It bounds degree-D polynomial prediction of whether two observations share a group by the trivial 1/K baseline when D is polylogarithmic in n.Source: §1.3 · p. 3
  • The BCH construction makes center and observation moment tensors match those of a Rademacher vector through order 2m + 1, leaving order 2m + 2 as the first informative tensor.The centers are almost orthogonal, with separation between Δ and 2Δ under the stated dimension condition.Source: §1.3 · p. 3
  • With polylogarithmic separation, low-degree polynomials require n ≳log K^2d^(3/2) observations, improving by a factor d over the prior bound [18].The result is novel for K ≥ d^2; the m = 1 regime is essentially covered by [10].Source: §1.3 · p. 4
  • The proof builds an almost-orthonormal family of observation polynomials indexed by bipartite graphs and analyzes finite-field solution counts for their moments.Graph structure is related to center moment tensors; remaining systems are bounded using Bézout-type bounds and Jacobian rank.Source: §1.3 · p. 4
  • Gaussianization transfers the Bernoulli-mixture hardness to isotropic Gaussian mixtures in the sense of reductions, with a separation-threshold change of order √log(n).The introduction also describes low-degree bounds as evidence of computational barriers, while noting the standard polynomial-time low-degree conjecture has been disproved.Source: §1.2 · p. 2, §1.3 · p. 4

2 Model and main results

The section constructs a 2K-component Bernoulli mixture from dual BCH codewords, matching Rademacher moments through order 2m+1 while keeping centers separated. It proves low-degree polynomials do not improve on random guessing under the stated signal conditions, and that polylogarithmic separation requires n ≳ K^2d^{3/2} samples up to polylogarithmic factors.

Mixture construction

  • The construction uses 2K Bernoulli components whose centers come from rescaled dual BCH codewords, with K=(d+1)^m.The codeword vectors are randomly signed and permuted in the construction.Source: §2 · p. 5

Moment matching

  • The center and observation moment tensors match those of a Rademacher vector through order 2m+1, making each observation indistinguishable from uniform {−1,1}^d by moments through that order.The moment-matching properties also hold unconditionally over the construction’s random choices.Source: §2 · p. 6

Center separation

  • When d≥(4m)^(m+1), the centers are pairwise at least ∆ apart, and the mixture separation is on the order of ∆.The separation guarantee follows from the near-orthogonality of the codeword vectors.Source: §2 · p. 6

Main result

  • As D grows, the low-degree correlation is (1 + o(1))/K, so degree-at-most-D polynomials do not predict group membership better than the constant random-guess rate 1/K.The stated rate conditions exclude the regime where distance-based procedures succeed.Source: §2 · p. 7
  • With polylogarithmic separation, low-degree polynomials require n ≳ K^2d^{3/2} samples up to polylogarithmic factors, improving the prior dK^2 bound by a factor d.This requirement remains a factor d below the sample size at which the empirical tensor of order 2m+2 becomes informative.Source: §2 · p. 7

3 Definition and Properties of the µk’s

The section defines center vectors from a dual BCH code and states their moment-matching properties. The centers match Rademacher moments through order 2m, with symmetric signed centers matching through order 2m+1.

3 Definition and Properties of the µk’s

  • The centers are renormalized codewords of the dual binary BCH code of length d and designed distance 2m+1.The construction gives a self-contained definition and proof of the properties used in the paper.Source: §3 · p. 7

3.1 Definition

  • Coordinates are identified with nonzero finite-field elements; ψ preserves addition into binary vectors, while powers are taken in the field.The binary-vector representation is used only through its additive structure.Source: §3.1 · pp. 7–8

3.2 Properties

  • Their order-l moments reduce to finite-field power-sum equations; the BCH choice matches Rademacher moments through order 2m.The equations use odd powers of the coordinate labels, and the construction makes the required power sums vanish.Source: §3.1 · p. 8, §3.2 · p. 9
  • The moments of the signed centers ±µ_k also match those of a Rademacher vector through order 2m+1, since symmetry makes odd-order tensors vanish.The unsigned center moments match through order 2m; the extra order follows from the signs.Source: §3.2 · p. 9

4 Discussion

The discussion connects a moment-matching BCH construction to tensor-based recovery and conjectured polynomial-time clustering, while identifying unresolved limits on the construction and Gaussian lower bound. It also notes that the conjectured procedure depends on the centers’ algebraic structure.

4 Discussion

  • Thresholding the estimated order-2m+2 tensor recovers its support and signs with high probability once its entries fluctuate at scale n^-1/2.The discussion conjectures that this tensor could then support polynomial-time center recovery and clustering.Source: §4 · p. 9
  • For the BCH instances, polynomial-time clustering is conjectured when Δ² ≳_m log(d), with n ≳_log K²d²/Δ^4(m+1) observations.The conjecture uses assignment to the center maximizing each observation’s scalar product.Source: §4 · p. 9
  • Even if that procedure works, it relies heavily on knowing that the centers form a permuted and sign-flipped dual BCH code.It remains unclear whether sample complexity of order K²d² or K²d^3/2 is optimal over all mixtures with Δ-separated centers.Source: §4 · pp. 9–10
  • The uniform distribution on the proposed centers matches standard-normal moment tensors through order 2m+1, motivating a Gaussian-design construction.The text states this as the desired property of a tentative worst-case Gaussian-mixture instance.Source: §4 · p. 10
  • For general m, the minimum size of Gaussian designs matching the required moments remains largely unknown; known positive-weight constructions have O(d^{2m−1}) points.A lower bound of dm/m! points is of the same order as K = (d+1)^m.Source: §4 · p. 10
  • The reduction transfers the lower bound to entrywise-truncated Gaussian observations, at the cost of a log(n) factor in separation.A direct Gaussian proof is described as a possible extension using bipartite multigraphs and Hermite polynomials.Source: §4 · p. 10

5 Proof organization for Theorem 1

The proof reduces low-degree correlation to a graph-indexed invariant polynomial basis, then controls its moments to establish almost-orthonormality and bound the correlation. The argument applies under explicit dimension, degree, sample-size, and signal conditions.

5 Proof organization for Theorem 1

  • The proof uses permutation invariance to represent invariant polynomials with bipartite graphs, then restricts the low-degree correlation to even-degree graphs.Graphs with an odd-degree node give polynomials uncorrelated with the target functional.Source: §5 · p. 10, §5.1 · p. 11, §5.2 · p. 11

5.1 Bipartite graph formalism and invariant polynomial basis

  • The graph basis uses injective observation and coordinate labelings, with distinguished observation labels, and graph equivalence preserves those distinguished nodes.The resulting graph polynomials span the subspace invariant under coordinate permutations and permutations of observations 3 through n.Source: §5.1 · pp. 10–11

5.2 Correction and reduction to even-degree graphs

  • Centering graph polynomials by connected components reduces cross-moments; the proof then sums and normalizes these centered polynomials.The discussion attributes smaller cross-moments to this centering step.Source: §5.2 · pp. 11–12

5.3 Almost-orthonormality of the ˜ΨG’s.

  • Under Condition (Hsignal), 28D^4 ≤ d, D ≥ 2, and n ≥ d, Theorem 2 establishes almost-orthonormality of the normalized centered polynomials.The authors state that the signal condition likely cannot be weakened by a power of d, citing order-wise tight covariance bounds.Source: §5.3 · p. 12

5.4 Proof of Theorem 1

  • Combining that result with Lemma 8 bounds low-degree correlation; the proof separately controls correlation with each graph polynomial and sums over graphs.The stated argument assumes Hsignal, 28D^4 ≤ d, D ≥ 2, and n ≥ d.Source: §5.4 · p. 13

6 Moments of polynomials PG and ΨG

The moment analysis translates graph-indexed polynomial expectations into probabilities that BCH-induced polynomial systems are satisfied. It then uses graph structure and centering to control first and cross-moments.

6.1 First moment

  • The BCH design makes canonical polynomial expectations depend on whether an induced system of equations is satisfied, enabling first-moment bounds through solution-set probabilities.A graph with an even-degree structure has zero satisfaction probability when some vertex subset has a symmetric-difference neighborhood of size 1 through 2m+1.Source: §6.1 · p. 14
  • Condition (WG) excludes small nonempty symmetric-difference neighborhoods, and Lemma 11 bounds the system-satisfaction probability for graphs satisfying that condition.The exponent in the bound is optimal in general, as illustrated by the twin-node cycle construction.Source: §6.1 · pp. 14–15

6.2 Second Moments

  • For second moments, component-centering makes cross-moments smaller; unmatched connected components contribute a factor of order d^-1/2 each.The gain follows because centering would make an unmatched component vanish absent the weak dependence induced by the random column permutation.Source: §6.2 · p. 16

AI Disclosure

  • The authors report using Gemini for bibliographical research and Claude for drafting, editing, and proof auditing, while taking responsibility for the manuscript.They state that AI-produced text was reviewed and rephrased by the authors.Source: AI Disclosure · p. 17

A Proof of Proposition 1

The proof of Proposition 1 uses symmetric differences, connected components, and partition-chain counting to control graph-based quantities. Component-count arguments establish the cases, while further bounds control the exponent term and final sum under the stated dimension condition.

A Proof of Proposition 1

  • Case (a) gives ω[R(1); R(2)] = 0 by Lemma 10, and the proof establishes Case (b) under Proposition 1’s assumptions.The proof identifies Case (b) as the most challenging case.Source: A Proof of Proposition 1 · pp. 18, 20
  • The Case (b) component-count bound follows by tracking node identifications and edge cancellations in the symmetric-difference graph.The proof bounds the component decrease from identifications and deleted components, then derives (2m + 1)δV + 2δW ≥ 2δcc.Source: A Proof of Proposition 1 · pp. 19–20
  • Case (c) uses E⊕ = ∅ to set u[R(1); R(2)] = 0 and proceeds as in Case (b); Case (d) follows a close variant of that argument.For Case (d), the proof modifies the symmetric-difference graph and invokes an analogous Lemma 12 argument.Source: A Proof of Proposition 1 · pp. 20–21
  • In proving Lemma 12, the authors use an auxiliary distribution that makes component events independent and bound the probability of collisions between sampled node sets.A union bound gives collision probability at most 2D^2/d, so the disjointness event has probability at least 1/2 under the stated conditions.Source: A Proof of Proposition 1 · p. 22
  • Under 28D^4 ≤ d, the geometric-type sum is at most 2, using q = 2^6D^4/d ≤ 1/4.The bound follows from q^ε/(1 − √q) ≤ 2, with ε determined by whether l is even or odd.Source: A Proof of Proposition 1 · p. 24
  • The proof bounds l ≤ D/2 because any nonempty connected component of a graph with even degrees contains at least four edges.When 28D^4 ≤ d, the geometric-type sum is at most 2.Source: A Proof of Proposition 1 · p. 24
  • The partition-chain counting bound is obtained by counting saturated chains to a partition and encoding arbitrary chains by intermediate ranks.The proof counts merges within each group, interleaves the resulting sequences, and bounds the number of possible rank subsets.Source: A Proof of Proposition 1 · pp. 24–25
  • For every admissible T and partition S, the argument establishes A_T ≥ (r(S) − l/2)_+/2 by first bounding A_[0:l] and then comparing A_T to it.The bound uses groups of S linking the graph components, organized as connected components of an auxiliary graph of atoms.Source: A Proof of Proposition 1 · pp. 25–26

B.1 Proof of Lemma 10

The proof uses the graph’s even-degree assumption to restrict neighborhood symmetric differences, then shows the resulting equation system has no solution for any injection σ.

B.1 Proof of Lemma 10

  • Even node degrees make symmetric differences of neighborhoods even-sized, excluding size 2m + 1 in the stated case.The proof assumes a subset V′ whose symmetric difference has size between 1 and 2m.Source: §B.1 · p. 26
  • If system (SG) is satisfied, every sum of the associated Equation (14) over a subset of V must equal 0 for each s ≤ m.Source: §B.1 · p. 26
  • The size bound and distinct σ(π2(w)) values imply, by Lemma 24, that the system has no solution for any injection σ.The proof then concludes.Source: §B.1 · p. 26

B.2 Proof of Lemma 11

The proof of Lemma 11 counts injective solutions of a finite-field equation system by bounding the dimension and degree of an associated algebraic set. Graph enumeration properties support the dimension bound, and a Bézout bound yields the final estimate.

B.2 Proof of Lemma 11

  • The proof bounds |U|, the number of injective tuples satisfying system (32), by first bounding the variety’s dimension and then applying Bézout’s inequality.U consists of tuples with distinct, nonzero coordinates in the d nonzero elements of F_{d+1}.Source: §B.2 · p. 27
  • The proof applies Bézout using cumulative degree, bounded by the product of the defining-equation degrees, to limit the number of rational points.The stated graph degree conditions also give |E| ≥ (2m + 2)|V| and hence m|V| ≤ |E|/2.Source: §B.2 · p. 28
  • The final estimates convert the bound from d + 1 to d and establish (18).The proof uses |W| and the number of nontrivial connected components in the conversion estimates.Source: §B.2 · p. 28
  • Graph lemmas construct a large subset W with the G-enumeration property under the stated graph conditions, including the absence of isolated nodes.This subset is the key technical step used in the proof.Source: §B.2 · p. 29
  • The G-enumeration property supports a Jacobian rank bound: the system’s rows reproduce (SG), and distinct coordinates yield an invertible Vandermonde matrix.The proof uses this to establish linear independence of the indexed columns and constrain the dimension.Source: §B.2 · pp. 27, 29, 30

B.3 Proof of technical lemmas

The technical lemmas establish bounds for graph-enumeration and tuple sets using pruning, induction, edge counting, and counting and spectral arguments. They also use finite-field syndromes to constrain equal-syndrome subsets in the exponent-optimality argument and show that the Jacobian rank bound in Lemma 11 is attained.

B.3 Proof of technical lemmas

  • Lemma 17’s enumeration set is built by pruning and peeling vertices, applying induction to the remaining components, and counting edges to establish the lower bound.The proof first reduces to a pruned connected bipartite graph, then uses a cycle to find a degree-(m + 1) vertex as the start of the peeling process.Source: §B.3 · pp. 30–31

B.4 Optimality of the exponent in Lemma 11

  • For the exponent-optimality argument, nonempty subsets of size at most 2m have nonzero syndrome, forcing equal-syndrome m-subsets to coincide and distinct equal-syndrome (m + 1)-subsets to be disjoint.The lower bound uses direct counting rather than Lang–Weil type estimates; syndromes add under symmetric difference over the characteristic-2 field.Source: §B.4 · p. 34
  • For each pair of nonadjacent nodes in W◦, tuples assigning them the same value number at most (m!)^(2r)d^(2r(m+1)−1).Summing this bound over at most |W◦|^2 pairs controls tuples excluded from U by such collisions.Source: §B.4 · p. 34
  • A trace bound for the symmetric matrix M converts the count of zero-syndrome subsets into Tr(M^(2r)) ≥ (1 − o(1))d^(2r(m+1)), and hence a lower bound on |U|.The argument relates injective tuples with zero syndrome to subsets of size 2m + 2, then uses syndrome counts and Cauchy–Schwarz.Source: §B.4 · pp. 34–35
  • |U| ≥ (1 − o(1))d^(2r(m+1)), yielding Pσ[A_G◦] ≥ (1 − o(1))d^(-2rm).The probability bound follows by dividing |U| by d^(2r(2m+1)).Source: §B.4 · p. 35
  • For every x ∈ U, rank(J_x) = ⌈b(G◦)⌉ = 2rm, so the lower bound on rank used in Lemma 11 is attained for G◦.The Jacobian rows indexed by (i, v_t) and (i, v′_t) coincide, giving rank at most 2rm; Lemma 15 gives the matching lower bound.Source: §B.4 · p. 35

C Proof of Theorem 2

The proof reduces Theorem 2 to a bound on the Gram matrix’s operator norm, using the largest row l1 norm. It introduces graph matchings and edit distance to organize the moment sums used for that bound.

C Proof of Theorem 2

  • Under the stated signal and dimension conditions, Proposition 2 is used as a corollary to establish Theorem 2.The proof bounds a symmetric matrix’s operator norm by its largest row l1 norm.Source: C Proof of Theorem 2 · p. 35

C.1 Additional graph notation

  • A node matching records which nodes of two graphs receive equal labels, and compatible labelings share exactly those matched nodes.The graph sides are matched separately, and the resulting matching indexes quantities used in the moment sums.Source: §C.1 · pp. 35–36
  • Semi-matched node pairs retain at least one unmatched incident edge, whereas perfect matches have all incident edges matched.The symmetric difference graph’s node count is related to the semi-matched and perfectly matched pairs.Source: §C.1 · p. 36
  • The edit distance is zero exactly for equivalent graphs, and within G≤D this is equivalent to equality.This distance provides a measure for comparing the graphs in the later bounds.Source: §C.1 · p. 36

C.2 Entry-wise control of Γ

This section controls graph contributions by counting graphs at a given edit distance and bounding the resulting terms. The counting argument separates edges removed from the first graph from new edges added in the symmetric difference.

C.2 Entry-wise control of Γ

  • 4 · 36^ζD^(3ζ+1) bounds the number of graphs at edit distance ζ from a fixed graph in G≤D.The count enumerates dropped edges and then possible attachments for the new edges.Source: §C.2 · p. 37
  • The counting argument needs only consider ζ ≤ 2D, since the fully unmatched matching gives edit distance at most 2D.For a fixed matching, the second graph is determined by which first-graph edges are dropped and how the remaining new edges are attached.Source: §C.2 · p. 37
  • For distinct graphs in G≤D, the edit distance is a nonzero even integer at least 4.Their matched symmetric difference is a nonempty simple bipartite graph with even degrees and no isolated nodes.Source: §C.2 · p. 37

C.3 Proof of Proposition 3

The proof controls cross moments by summing over node matchings and grouping them into shadows. Matchings that leave a low-degree node unmatched contribute zero, while the remaining bounds use the structure of the symmetric difference graph.

C.3 Proof of Proposition 3

  • Matchings that leave a node of degree at most 2m+1 unmatched contribute zero to the cross-moment sum.The unmatched node cannot share a label with a node in the other graph, so Proposition 1(a) makes the corresponding expectation vanish.Source: §C.3 · p. 38
  • For matchings in M⋆, each unmatched V-side node has degree at least 2m+2 in the symmetric difference graph.This yields an edge-count lower bound used in the proof; exceptional unmatched components, when present, contribute at least four edges.Source: §C.3 · p. 39
  • The proof groups matchings by their shadow, which records unmatched nodes and semi-matched node pairs; membership in M⋆ depends only on that shadow.Perfect matchings correspond to the empty shadow, and M⋆ excludes matchings outside the specified low-degree matching condition.Source: §C.3 · pp. 38, 40
  • The empty-graph case is handled by the same argument, with non-isolated nodes of the first graph serving as unmatched V-side nodes.If a non-isolated node has degree below 2m+2, its expectation term vanishes by Proposition 1(a).Source: §C.3 · p. 41

D Proof of Lemma 9

The proof bounds graph-indexed polynomial terms by splitting graphs according to whether the two distinguished vertices are isolated, connected, or in separate components. Low-degree vertices force vanishing, while graph decompositions and prior bounds yield the final estimate.

D Proof of Lemma 9

  • If a vertex other than v1 and v2 has degree below 2m+2, the relevant expectation vanishes in each of the three graph cases.The cases distinguish an isolated distinguished vertex, distinguished vertices in the same component, and distinguished vertices in separate components.Source: D Proof of Lemma 9 · pp. 41–42
  • When v1 and v2 are isolated, the proof separates the graph into disjoint pieces and uses Proposition 1, with non-isolated vertices controlling the component bound.Only v1 and v2 may be isolated in a graph of G≤D, giving |V⊕| ≥ |V| − 2.Source: D Proof of Lemma 9 · p. 41
  • When v1 and v2 share a component, identifying them and removing duplicated edges produces a connected graph used to bound the remaining term.The other components form G0, whose component count is at most |V| − 2.Source: D Proof of Lemma 9 · p. 42
  • When v1 and v2 lie in distinct components, the proof merges their components by identifying the two vertices and bounds the resulting terms using Proposition 1 or Lemma 11.The remaining connected components are grouped into G0.Source: D Proof of Lemma 9 · pp. 42–43
  • i ≤ 16 Kd^1/4 ρ^|E|.The proof obtains this bound after applying Proposition 1 or Lemma 11 to the decomposed graph terms.Source: D Proof of Lemma 9 · p. 43

E Proof of reduction lemmas

The reduction lemmas restrict the low-degree correlation optimization to invariant polynomials and then to a basis formed by even-degree graph polynomials. Odd-degree graph terms contribute neither to the correlation with x nor to cross terms with the even-degree part.

E Proof of reduction lemmas

  • Symmetrizing any admissible polynomial over row and coordinate permutations preserves its correlation with x and does not increase its squared norm.The joint law of (x, Y) is invariant under these permutations, and Jensen’s inequality bounds the symmetrized norm.Source: E Proof of reduction lemmas · p. 43
  • A graph with an odd-degree vertex has zero correlation with x under either of the two labelings considered.The odd multiplicity leaves an independent Rademacher factor of mean zero.Source: E Proof of reduction lemmas · p. 44
  • The symmetric difference of two labeled graphs is used to analyze products of graph polynomials and show that odd-degree terms are orthogonal to the retained part.The decomposition into P1 and P2 gives E[P1P2] = 0 and E[xP2] = 0.Source: E Proof of reduction lemmas · pp. 44–45
  • The invariant polynomials of degree at most D have a basis consisting of 1 and the graph polynomials PG for even graphs G.The proof reduces any admissible invariant polynomial to this span without changing its correlation with x.Source: E Proof of reduction lemmas · pp. 43, 45
  • The graph-polynomial family and the Ψ-polynomial family span the same space, since each can be expanded using the other and graph subgraphs.The converse expansion removes connected components from graphs, up to graph equivalence.Source: E Proof of reduction lemmas · p. 45

F Proofs of the properties of the BCH construction

The BCH construction makes short finite-field power-sum constraints equivalent to pairing repeated coordinate labels, yielding the desired moment identities. The proof transfers this pairing criterion to the centers and observations, and establishes separation of distinct signed centers.

F Proofs of the properties of the BCH construction

  • The BCH power-sum lemma is proved self-contained, without relying on coding theory.The section proves the construction’s moment and center-separation properties alongside the graph-system lemmas.Source: F Proofs of the properties of the BCH… · p. 45
  • For l ≤ 2m, the finite-field power-sum constraints hold exactly when the listed nonzero elements can be grouped into pairs of equal values.The proof first shows all power sums through 2m vanish, then rules out any value with odd multiplicity.Source: F Proofs of the properties of the BCH… · pp. 46–47
  • The BCH construction’s coordinate moment indicator equals the indicator that the coordinate list is paired, and hence equals the uniform Rademacher moment U(l).The field elements corresponding to coordinates satisfy the power-sum system precisely under the pairing condition.Source: F Proofs of the properties of the BCH… · p. 47
  • The proof transfers the BCH moment property to the centers ±Xk and then to observations Yi by conditioning on the latent component and sign.For each product order up to 2m+1, repeated indices reduce to an odd-multiplicity coordinate set of size at most that order.Source: F Proofs of the properties of the BCH… · pp. 47–48
  • For every l ≤ 2m+1, the observation-coordinate product expectation equals the uniform Rademacher moment, namely 1 when indices pair and 0 otherwise.The equality follows by reducing repeated coordinates to the set of indices occurring an odd number of times and applying the center moment identity.Source: F Proofs of the properties of the BCH… · pp. 47–48
  • The nontrivial BCH coordinate sums Sk are bounded by converting a power-moment bound into a uniform bound through dilation invariance and large orbits.Each nonzero orbit contains at least d/(2m−1) indices, allowing the moment bound to control the maximum sum.Source: F Proofs of the properties of the BCH… · pp. 48–49
  • Distinct signed centers are separated by at least Δ in Euclidean norm.For different component indices, the squared sign-adjusted codeword distance is at least d; opposite signs with the same index give squared distance 4d.Source: F Proofs of the properties of the BCH… · p. 49
Loading 2610.37272v1…