130 Boolean Analysis — Low Degree Obstruction

130.1 Overview

This file completes the counting half of the Razborov–Smolensky \(\mathrm{MOD}\, q\) lower bound over the root cube \(\{ 1,\omega \} ^n \subseteq K^n\). It introduces a concrete finite candidate family — squarefree polynomials whose supports all have size at most \(D\) — proves that it is complete for degree-\(\le D\) polynomials on the cube, counts the cube, the candidate family, and Hamming balls of functions, and combines these into an explicit obstruction to low-degree approximation of the product \(\prod _i x_i\).

130.2 Declarations

Definition 130.1 Low-degree squarefree supports

✓

For \(n, D \in \mathbb {N}\), the type of supports of squarefree monomials of degree at most \(D\): the subtype of finsets \(s \subseteq \mathrm{Fin}\, n\) with \(\left\lvert s\right\rvert \le D\). In the displays below this type is written \(\mathcal{S}_{n,D}\).

Definition 130.2 Low-degree squarefree polynomial from coefficients

✓

Given coefficients \(c\) indexed by \(\texttt{ACP.LowDegreeSupport}\ n\ D\), the multivariate polynomial

\[ \sum _{\substack {s \subseteq \mathrm{Fin}\, n \\ \left\lvert s\right\rvert \le D}} c(s)\, \prod _{i \in s} X_i , \]

i.e. the sum of the squarefree monomials \(\texttt{ACP.squarefreeMonomial}\ s\) weighted by \(c\), with the terms of support size \(\gt D\) set to \(0\).

Theorem 130.3 Squarefree representative on the root cube

✓

Every function \(f : \{ 1,\omega \} ^n \to K\) on the root cube is represented by a squarefree (multilinear) polynomial: there are coefficients \(c\) indexed by finsets of \(\mathrm{Fin}\, n\) such that \((\texttt{ACP.squarefreePolynomial}\ c)(x) = f(x)\) for all \(x\) in the root cube.

Theorem 130.4 Monomial-level degree-preserving multilinearization

✓

Assume \(\omega \ne 1\). If a monomial \(a\, X^m\) has total exponent sum \(\sum _i m_i \le D\), then it agrees on the root cube \(\{ 1,\omega \} ^n\) with a squarefree polynomial built only from supports of size at most \(D\): there exist coefficients \(c\) on \(\texttt{ACP.LowDegreeSupport}\ n\ D\) with \((\texttt{ACP.lowDegreeSquarefreePolynomial}\ c)(x) = (a\, X^m)(x)\) for every \(x\) in the cube.

Lemma 130.5 Additivity in the coefficient function

✓

The constructor \(\texttt{ACP.lowDegreeSquarefreePolynomial}\) is additive in its coefficient argument: the polynomial attached to \(c_1 + c_2\) is the sum of the polynomials attached to \(c_1\) and to \(c_2\).

Lemma 130.6 Zero coefficients give the zero polynomial

✓

The constructor \(\texttt{ACP.lowDegreeSquarefreePolynomial}\) sends the identically zero coefficient function to the zero polynomial.

Lemma 130.7 Finite-sum linearity in the coefficients

✓

For a finite index set \(S\) and coefficient functions \(c_i\), the polynomial attached to the pointwise sum \(\sum _{i \in S} c_i\) equals \(\sum _{i \in S}\) of the polynomials attached to the individual \(c_i\).

Theorem 130.8 Completeness of low-degree squarefree polynomials on the root cube

✓

Assume \(\omega \ne 1\). Every polynomial \(Q\) with \(\deg Q \le D\) agrees on the root cube \(\{ 1,\omega \} ^n\) with a low-degree squarefree polynomial: there are coefficients \(c\) on \(\texttt{ACP.LowDegreeSupport}\ n\ D\) such that \((\texttt{ACP.lowDegreeSquarefreePolynomial}\ c)(x) = Q(x)\) for all \(x\) in the cube.

Lemma 130.9 Degree bound for the constructed polynomial

✓

For any coefficient function \(c\) on \(\texttt{ACP.LowDegreeSupport}\ n\ D\), the polynomial \(\texttt{ACP.lowDegreeSquarefreePolynomial}\ c\) has total degree at most \(D\).

Definition 130.10 Support-to-sigma injection

✓

The map sending a low-degree support \(s\) to the pair consisting of its exact cardinality \(\left\lvert s\right\rvert \in \mathrm{Fin}(D+1)\) together with \(s\) itself, viewed as an element of \(\{ t : \mathrm{Finset}(\mathrm{Fin}\, n) \mid \left\lvert t\right\rvert = \left\lvert s\right\rvert \} \). It is used as an injection for the binomial-sum bound rather than as a full equivalence.

Theorem 130.11 Binomial bound on the number of low-degree supports

✓

The number of low-degree squarefree supports satisfies

\[ \left\lvert \mathcal{S}_{n,D}\right\rvert \; \le \; \sum _{t=0}^{D} \binom {n}{t}. \]

Lemma 130.12 Size of the coefficient family

✓

For a finite type \(K_0\), the number of coefficient functions on low-degree supports is

\[ \left\lvert \mathcal{S}_{n,D} \to K_0\right\rvert \; =\; \left\lvert K_0\right\rvert ^{\, \left\lvert \mathcal{S}_{n,D}\right\rvert } . \]

Definition 130.13 Root cube as Boolean strings

✓

If \(\omega \ne 1\), the explicit equivalence \(\{ 1,\omega \} ^n \simeq (\mathrm{Fin}\, n \to \mathrm{Fin}\, 2)\) that records, for each coordinate, whether its value is \(1\) or \(\omega \).

Lemma 130.14 Cardinality of the root cube

✓

If \(\omega \ne 1\) and \(K\) is finite, then the root cube has exactly \(2^n\) points: \(\left\lvert \{ 1,\omega \} ^n\right\rvert = 2^n\).

Lemma 130.15 Number of functions on the root cube

✓

If \(\omega \ne 1\) and \(K\) is finite, the number of functions \(\{ 1,\omega \} ^n \to K\) is \(\left\lvert K\right\rvert ^{2^n}\).

Theorem 130.16 Hamming-ball bound for function spaces

✓

For finite types \(\alpha , \beta \), a center function \(\mathrm{center} : \alpha \to \beta \) and a radius \(e\), the number of functions \(f : \alpha \to \beta \) that differ from the center on at most \(e\) coordinates is bounded by

\[ \sum _{t=0}^{e} \binom {\left\lvert \alpha \right\rvert }{t}\, \left\lvert \beta \right\rvert ^{\, t}. \]

This is a slightly coarser form of the usual bound, which carries \((\left\lvert \beta \right\rvert -1)^t\) in place of \(\left\lvert \beta \right\rvert ^t\).

Theorem 130.17 Hamming-ball bound on the root cube

✓

For any center function on the root cube and any radius \(e\), the Hamming ball \(\texttt{ACP.rootCubeBall}\) of radius \(e\) around it satisfies

\[ \left\lvert B_e(\mathrm{center})\right\rvert \; \le \; \sum _{t=0}^{e} \binom {\left\lvert \{ 1,\omega \} ^n\right\rvert }{t}\, \left\lvert K\right\rvert ^{\, t}. \]

Theorem 130.18 Counting obstruction for low-degree squarefree candidates

✓

Let \(K\) be finite and \(\omega \ne 1\). Suppose the ball bound \(\sum _{t=0}^{e} \binom {2^n}{t}\, \left\lvert K\right\rvert ^{\, t} \le B\) holds and the counting is strict,

\[ \left\lvert K\right\rvert ^{2^n} \; \gt \; \left\lvert \mathcal{S}_{n,D} \to K\right\rvert \cdot B . \]

Then it is not the case that every function \(f : \{ 1,\omega \} ^n \to K\) admits a polynomial \(Q\) with \(\deg Q \le D\) and \(\texttt{ACP.rootCubeBadCount}\ f\ Q \le e\).

Theorem 130.19 Concrete root-product lower bound

✓

Let \(K\) be finite, \(\omega \ne 0\), \(\omega \ne 1\). Suppose \(\sum _{t=0}^{e} \binom {2^n}{t}\, \left\lvert K\right\rvert ^{\, t} \le B\) and

\[ \left\lvert K\right\rvert ^{2^n} \; \gt \; \left\lvert \mathcal{S}_{n,\lfloor n/2 \rfloor + d} \to K\right\rvert \cdot B . \]

Then no polynomial \(P\) with \(\deg P \le d\) approximates the product \(x \mapsto \prod _i x_i\) on the root cube with at most \(e\) errors, i.e. there is no such \(P\) with \(\texttt{ACP.rootCubeBadCount}\ (\prod _i x_i)\ P \le e\).