Sum of squares lower bounds for refuting any CSP

Introduction

In computational complexity, we have a comprehensive theory of worst-case hardness, assuming $\mathsf{P}\neq\mathsf{NP}$. The theory is particular rich in the context of constraint satisfaction problems (CSPs) — optimization tasks that are both simple to state and powerfully expressive. (See, e.g., [BJK05, Rag08].) But despite our many successes in the theory of $\mathsf{NP}$-completeness and $\mathsf{NP}$-hardness-of-approximation, we know relatively little about the nature of hard instances. For example, $3$-SAT is conjecturally hard to solve — or even approximate to factor $\frac{7}{8}+\epsilon$ — in $2^{o(n)}$ time. But what do hard(-seeming) instances look like? How can we generate one? These sorts of questions are a key part of understanding what makes various algorithmic problems truly hard. They are particularly important for CSPs, as these are nearly always the starting point for hardness reductions; the ability to find hard instances for CSPs yields the ability to find hard instances for many other algorithmic problems.

In some sense, a single instance can never be “hard” because its solution can always be hard-coded into an algorithm. Thus it is natural to turn to random instances, and the theory of average-case hardness. Uniformly random instances of CSPs are a particularly simple and natural source of hard(-seeming) instances. Furthermore, they arise as the fundamental object of study in many disparate areas of research, including cryptography [ABW10], proof complexity [BSB02], hardness of approximation [Fei02], learning theory [DLSS14], SAT-solving [SAT], statistical physics [CLP02], and combinatorics.

For random instances with subcritical constraint density, $\Delta<\alpha_{c}$, the natural algorithmic task is to try to efficiently find satisfying assignments. There have been quite a few theoretical and practical successes for this problem, for $\Delta$ quite large and even approaching $\alpha_{c}$ [Gab16, MPRT16]. On the other hand, for random instances with supercritical constraint density, $\Delta>\alpha_{c}$, the natural algorithmic task is to try to efficiently refute them; i.e., produce a certificate of unsatisfiability. For many CSPs, this task seems much harder, even heuristically. For example, random $3$-SAT instances are unsatisfiable (whp) once $\Delta>4.49$ [DKMPG08]; however, even for $\Delta$ as large as $n^{.49}$ there is no known algorithm that efficiently refutes random instances — even heuristically/experimentally. Thus the refutation task for random instances of CSPs with many constraints may be a source of simple-to-generate, yet hard-to-solve problems.

2 The importance and utility of hardness assumptions for random CSPs

For a wide variety of areas — cryptography, learning theory, and approximation algorithms — it is of significant utility to have concrete hardness assumptions concerning random CSPs. Because uniformly random CSPs are very simply and concretely defined, they form an excellent basis for constructing other potentially hard problems by reduction. An early concrete hypothesis comes from an influential paper of Feige [Fei02]:

For every small $\delta>0$ and for large enough constant $\Delta$, there is no polynomial-time algorithm that succeeds in $\delta$-refuting random instances of $3$-SAT.

Feige’s main motivation was hardness of approximation; e.g., he showed that the R3SAT Hypothesis implies stronger hardness of approximation results than were previously known for several problems (Balanced Bipartite Clique, Min-Bisection, Dense $k$-Subgraph, $2$-Catalog). By reducing from these problems, several more new hardness of approximation results based on Feige’s Hypothesis have been shown in a variety of domains [BKP04, DFHS06, Bri08, AGT12]. Feige [Fei02] also related hardness of refuting $3$-SAT to hardness of refuting $3$-XOR. The assumption that refuting $3$-XOR is hard has been used to prove new hardness results in subsequent work [OWWZ14]. Alekhnovich [Ale03] further showed that certain average-case hardness assumptions for XOR imply additional hardness results, as well as the existence of secure public key cryptosystems.

In even earlier cryptography work, Goldreich [Gol00] proposed using the average-case hardness of random CSPs as the basis for candidate one-way functions. Subsequent work (e.g., [MST03]) suggested using similar functions as candidate pseudorandom generators (PRGs). The advantage of this kind of construction is the extreme simplicity of computing the PRG: indeed, its output bits can be computed in $\mathsf{NC}^{0}$, constant parallel time. Further work investigated variations and extensions of Goldreich’s suggestion [ABW10, ABR12, AL16]; see Applebaum’s survey [App13] for many more details. Of course, the security of these candidate cryptographic constructions depends heavily on the hardness of refuting random CSPs. Applebaum, Ishai, and Kushilevitz [AIK06] took a slightly different approach to showing that PRGs exist in $\mathsf{NC}^{0}$, instead basing their result on one of Alekhnovich’s average case XOR hardness assumptions [Ale03].

3 Desiderata for hardness results

While Feige’s R3SAT Hypothesis has proven useful in hardness of approximation, there are several important strengthenings of it that would lead to even further utility. We discuss here four key desiderata for hardness results about random CSPs:

Predicates other than SAT. The hardness of random $3$-SAT and $3$-XOR has been most extensively studied, but for applications it is quite important to consider other predicates. For hardness of approximation, already Feige [Fei02] noted that he could prove stronger inapproximability for the $2$-Catalog problem assuming hardness of refuting random $k$-AND for large $k$. Subsequent work has used assumptions about the hardness of refuting CSPs with other predicates to prove additional worst-case hardness results [GL04, AAM+11, CMVZ12, BCMV12, RSW16]. Relatedly, Barak, Kindler, and Steurer [BKS13] have recently considered a generalization of Feige’s Hypothesis to all Boolean predicates, in which the assumption is that the “basic SDP” provides the best $\delta$-refutation algorithm when $\Delta=O(1)$. They also describe the relevance of predicates over larger alphabet sizes and with superconstant arity for problems such as the Sliding Scale Conjecture and Densest $k$-Subgraph. Bhaskara et al. [BCG+12] prove an SOS lower bound for Densest $k$-Subgraph via a reduction from Tulsiani’s SOS lower bound for random instances of CSP$(P)$ with $P$ a $q$-ary linear code [Tul09]. A computational hardness assumption for refutation of this CSP would therefore give a hardness result for Densest $k$-Subgraph.

These discussions lead us to the following goal:

The main theorem in this work, stated in Section 1.5, completely accomplishes this goal in the context of the Sum of Squares (SOS) method. Before stating our results, we review this method, as well as prior results in the direction of the above goal.

4 Prior results in proof complexity, and the SOS method

Much of the work in this area has focused on random instances of $k$-SAT. A seminal early work of Chvátal and Szemerédi [CS88] showed that Resolution refutations of random instances of $k$-SAT require exponential size when $\Delta$ is a sufficiently large constant. Ben-Sasson and Wigderson [BSW01, BS01] later strengthened this result to show that Resolution refutations require width $\Omega(\frac{n}{\Delta^{1/(k-2)+\epsilon}})$ for any $\epsilon>0$. Ben-Sasson and Impagliazzo and Alekhnovich and Razborov further extended these results to the Polynomial Calculus proof system [BSI99, AR01]; for example, the latter work showed that Polynomial Calculus refutations of random $k$-SAT instances with density $\Delta$ require degree $\Omega(\frac{n}{\Delta^{2/(k-2)}\log\Delta})$.

On the other hand, much of the positive work on refuting random $k$-SAT has used spectral techniques and semialgebraic proof systems. These latter proof systems are often automatizable using linear programming and semidefinite programming, and thereby have the advantage that they can naturally give stronger $\delta$-refutation algorithms. As examples, Goerdt and Krivelevich [GK01] showed that spectral techniques (which can be captured by SDP hierarchies) enable refutation of random $k$-SAT with $m=n^{\lceil k/2\rceil}$ constraints; Friedman and Goerdt [FG01] improved this to $m=n^{3/2+o(1)}$ in the case of random $3$-SAT. One of the first lower bounds for random CSPs using SDP hierarchies was given by Buresh-Oppenheim et al. [BOGH+03]; it showed that the Lovász–Schrijver+ (LS+) proof system cannot refute random instances of $k$-SAT with $k\geq 5$ and constant $\Delta$. Alekhnovich, Arora, and Tourlakis [AAT05] extended this result to random instances of $3$-SAT.

The strongest results along these lines involve the Sum of Squares (AKA Positivstellensatz or Lasserre) proof system. This system, parameterized by a tuneable “degree” parameter $d$, is known to be very powerful; e.g., it generalizes the degree-$d$ Sherali–Adams+ (SA+) and LS+ proof systems. In the context of CSP$(\mathcal{P})$ over domain $\{0,1\}$, it is also (approximately) automatizable in $n^{O(d)}$ time using semidefinite programming. As such, it has proven to be a very powerful positive tool in algorithm design, both for CSPs and for other tasks; in particular, it has been used to show that several conjectured hard instances for CSPs are actually easy [BBaH+12, OZ13, KOTZ14]. Finally, thanks to work of Lee, Raghavendra, and Steurer [LRS15], it is known that constant-degree SOS approximates the optimum value of CSPs at least as well as any polynomial-size family of SDP relaxations. See, e.g., [OZ13, BS14, Lau09] for surveys concerning SOS.

Early on, Grigoriev [Gri01] showed that SOS of degree $\Omega(n)$ could not refute $k$-XOR instances on sufficiently good expanders. Schoenebeck [Sch08] essentially rediscovered this proof and showed that it applied to random instances of $k$-SAT and $k$-XOR, specifically showing that SOS degree $\frac{n}{\Delta^{2/(k-2)-\epsilon}}$ is required to refute instances with density $\Delta$. Tulsiani [Tul09] extended this result to the alphabet-$q$ generalization of random $3$-XOR.

Beyond semialgebraic proof systems and hierarchies, even less is known about non-SAT, non-XOR predicates. Feldman, Perkins, and Vempala [FPV15] proved lower bounds for refutation of CSP$(P^{\pm})$ using statistical algorithms when $P$ supports a $(t-1)$-wise uniform distribution. Their results are incomparable to the above lower bounds for LP and SDP hierarchies: the class of statistical algorithms is quite general and includes any convex relaxation, but the [FPV15] lower bounds are not strong enough to rule out refutation by polynomial-size SDP and LP relaxations.

5 Our result

We essentially achieve the Goal described in Section 1.3 in the context of the powerful SOS hierarchy. Specifically, for every predicate family $\mathcal{P}$, we provide a full three-way tradeoff between constraint density, SOS degree, and strength of refutation. Our lower bound subsumes all of the hardness results for semialgebraic proof systems mentioned in the previous section. Furthermore, as we will describe, known algorithmic work implies that our full three-way hardness tradeoff is tight, up to lower-order terms.

To state our result, we need a definition. For a predicate $P:\Omega^{k}\to\{0,1\}$ and an integer $1<t\leq k$, we define $\delta_{P}(t)$ to be $P$’s distance from supporting a $t$-wise uniform distribution. Formally,

We can now (slightly informally) state our main theorem in the context of Boolean predicates:

Additionally, in the case that $\delta_{P}(t)=0$, our result does not need the additive $o(1)$ in refutation strength. That is:

We comment here on the (surprisingly mild) parameter-dependence hidden by the $\widetilde{\Omega}(\cdot)$ and $o(1)$ in these bounds. See Section 7 for full details.

In terms of $\Delta$, the $\widetilde{\Omega}(\cdot)$ is only hiding a factor of $\log\Delta$. Thus we get a full linear $\Omega(n)$-degree lower bound for $m=O(n)$ in both theorems above.

Indeed in this case of $t=\Theta(k)$, if we also have $\Delta=2^{\Theta(k)}$ then the degree lower bound for weak refutation in Theorem 1.2 is $\Omega(n)$ for $k$ as large as $\Omega(n)$; here, both $\Omega(\cdot)$’s hide only a universal constants. The regime of $\Delta=2^{\Theta(k)}$ is the algorithmically hardest one for $k$-SAT, and thus in this very natural case we have a linear-degree lower bound even for $k=\Omega(n)$.

The refutation strength $\delta_{P}(t)+o(1)$ in Theorem 1.1 is more precisely $\delta_{P}(t)+O(1/\sqrt{n})$ whenever $\Delta=n^{\Omega(1)}$.

Theorem 1.1 also holds for predicates $P$ with alphabet size $q>2$, with absolutely no additional parameter dependence on $q$.

The full three-way tradeoff in Theorem 1.1 between constraint density, SOS degree, and strength of refutation is tight up to a polylogarithmic factor in the degree and an additive $o(1)$ term in the strength of the refutation. The tightness follows from the below theorem, which is an immediate consequence of the general $\delta$-refutation framework of Allen et al. [AOW15] and the strong refutation algorithm for XOR due to Raghavendra, Rao, and Schramm [RRS16] (which fits in the SOS framework).

More generally, for a given predicate $P$ and a fixed number of random constraints $m=n^{1+c}$, we provably get a “time vs. quality” tradeoff with an intriguing discrete set of breakpoints: With constant degree, SOS can $\delta_{P}(2)$-refute, and then as the degree increases to $n^{1-2c}$, $n^{1-c}$, $n^{1-2c/3}$, etc., SOS can $\delta_{P}(3)$-refute, $\delta_{P}(4)$-refute, $\delta_{P}(5)$-refute, etc.

An alternative way to look at the tradeoff is by fixing the SOS degree to some $n^{\epsilon}$ and considering how refutation strength varies with the number of constraints. So for $m$ between $n$ and $n^{3/2-\epsilon/2}$ SOS can $\delta_{P}(2)$-refute; for $m$ between $n^{3/2-\epsilon/2}$ and $n^{2-\epsilon}$ SOS can $\delta_{P}(3)$-refute; for $m$ between $n^{2-\epsilon}$ and $n^{5/2-3\epsilon/2}$ SOS can $\delta_{P}(4)$-refute; etc.

The results in this corollary are tight up to the polylogs on $m$, by the SOS algorithms of [AOW15].

Technical framework

In Section 1, we described our results as being SOS lower bounds for random CSPs, with constraints chosen randomly from a fixed predicate family $\mathcal{P}$. However it is conceptually clearest to divorce our results from the “random CSP” model as quickly as possible.

Our lower bound applies whenever the underlying factor graph (bipartite constraint/variable graph) does not contain certain small forbidden subgraphs, which we call “implausible” subgraphs. Granted, the only examples we know of such graphs are random graphs (whp). Further, the condition of “does not contain any implausible subgraphs” is highly related to the condition of “has very good vertex expansion”. Still, we believe the right way to think about the requirement is in terms of forbidden subgraphs.

Our lower bound doesn’t really involve CSPs and constraints, per se. For each constraint-vertex $f$ in the underlying factor graph, rather than assuming it comes equipped with a constraint predicate $P$ applied to its vertex-variable neighbors, we assume it comes equipped with a probability distribution $\mu_{f}$ on assignments to its vertex-variable neighbors. We can have a different $\mu_{f}$ for every constraint-vertex $f$ if we want (indeed, the constraints need not even have the same arity).

Our SOS lower bounds now take the following form: Assume we are given a factor graph $G$ with no implausible subgraphs, and assume each constraint-vertex $f$ has an associated distribution $\mu_{f}$ that is $t$-wise uniform. Then the low-degree SOS proof system “thinks” that there is a global assignment to the variables such that, at every constraint-vertex $f$, the local assignment to the neighboring variable-vertices is in the support of $\mu_{f}$. (Indeed, it “thinks” that there is a probability distribution on global assignments such that for almost all $f$, the marginal distribution on $f$’s neighbors is equal to $\mu_{f}$.)

Let us make some of these notions more precise.

We fix an alphabet $\Omega$ of cardinality $q\geq 2$, and a maximum constraint arity $K\geq 3$.

The reader is strongly advised to focus on the case $q=2$, with $\Omega=\{\pm 1\}$, as the only real difficulty posed by larger alphabets is notational. Also, although we describe $K$ as a maximum arity, there will be no loss in thinking of every constraint as having arity $K$.

A probability distribution $\mu$ on $\Omega^{k}$ is said to be $t$-wise uniform if its marginal on every subset of $t$ coordinates is uniform.

Rather than our full Theorem 1.1 concerning $\delta$-refutation, the reader is advised to mainly keep in mind our Theorem 1.2, which is concerned with (weak) refutation of CSPs for which the predicates support a $(\tau-1)$-wise uniform distribution. Given our proof of Theorem 1.2, the more general Theorem 1.1 will fall out fairly easily.

We fix an integer $\tau$ satisfying $3\leq\tau\leq K$.

The reader is advised to focus on the simplest case of $\tau=3$ (corresponding to predicates supporting pairwise-uniform distributions), as the value of $\tau$ makes no real difference to our proofs.

The instance we work with consists of two parts: a factor graph and its constraint distributions. The factor graph, denoted $G$, is a bipartite graph with edges going between $n$ variable-vertices and $m$ constraint-vertices. For a constraint-vertex $f$ we write $N(f)$ for the neighborhood of $f$, which we take to be an ordered list of the variable-vertices adjacent to $f$. We assume that the degree (“arity”) of every constraint-vertex $f$ satisfies $\tau-1\leq|N(f)|\leq K$. Finally, each constraint-vertex $f$ also comes with a constraint distribution $\mu_{f}$ on $\Omega^{N(f)}$. It is assumed that each $\mu_{f}$ is $(\tau-1)$-wise uniform.

2 Plausible factor graphs

As mentioned earlier, our SOS lower bounds will hold whenever the factor graph $G$ has no “implausible” subgraphs. The meaning of this will be discussed in much greater detail in Section 4, but here we will give the briefest possible definition.

We introduce two parameters: $1\leq\scalebox{0.75}[1.0]{{SMALL}}\leq n/2$ and $0<\zeta<1$. (For the sake of intuition, the reader might think of, e.g., $\scalebox{0.75}[1.0]{{SMALL}}=n^{\Omega(1)}$ and $\zeta=\frac{1}{\log n}$.) The parameters are assumed to satisfy $K\leq\zeta\cdot\scalebox{0.75}[1.0]{{SMALL}}$.

Henceforth the factor graph $G$ is assumed to satisfy the following property: Let $H$ be an edge-induced subgraph in which every constraint-vertex has minimum degree $\tau$. Suppose $H$ has $c$ constraint-vertices, $v$ variable-vertices, and $e$ edges, with $c\leq 2\cdot\scalebox{0.75}[1.0]{{SMALL}}$. Then $(\tau-\zeta)c\geq 2(e-v)$.

We call the subgraphs $H$ for which the inequality holds plausible because they are indeed the ones that may plausibly show up when the factor graph $G$ is randomly chosen:

(Roughly stated; see Theorem 4.12 for a precise statement.) A random $G$ with constraint density $\Delta$ will satisfy the Plausibility Assumption whp provided $\displaystyle\scalebox{0.75}[1.0]{{SMALL}}\ll\frac{n}{\Delta^{2/(\tau-2-\zeta)}}$.

The Plausibility Assumption is highly similar to the assumption that $G$ has good vertex-expansion, and indeed our proof of Theorem 4.12 in Appendix A is a completely standard variant of the well-known proof that random bipartite graphs have good vertex-expansion.

3 The Sum of Squares algorithm, and pseudoexpectations

We give a brief overview of the Sum of Squares algorithm/proof system here. For more general background see, e.g., [BS]; for more details germane to this paper, see Section 5.3.

The Sum of Squares (SOS) algorithm is a hierarchy of semidefinite programming-based relaxations applicable to polynomial optimization problems; i.e., maximizing an $n$-variate polynomial subject to polynomial inequality and equality constraints. Each algorithm in the hierarchy is indexed by a parameter $d$ known as the degree of the relaxation. Central to the algorithm is the concept of pseudoexpectations that describe the feasible points of the SOS algorithm of degree $d$.

Given $n$ indeterminates, a degree-$d$ pseudoexpectation is a linear operator $\mathop{\bf\widetilde{E}\/}$ on the space of real polynomials of degree at most $d$ in those indeterminates, such that $\mathop{\bf\widetilde{E}\/}=1$. We also generally want it to satisfy the Positive Semidefiniteness condition: $\mathop{\bf\widetilde{E}\/}[p^{2}]\geq 0$ for every polynomial $p$ of degree at most $d/2$.

A degree-$d$ pseudoexpectation $\mathop{\bf\widetilde{E}\/}$ is said to satisfy a polynomial identity “$p=0$” if, for every polynomial $q$ with $\deg(p)+\deg(q)\leq d$, we have $\mathop{\bf\widetilde{E}\/}[pq]=0$.

Given a polynomial optimization problem — say, maximizing a polynomial $p_{1}$ subject to constraints $\{q_{i}=0:i\in[m]\}$ — the degree-$d$ SOS relaxation maximizes $\mathop{\bf\widetilde{E}\/}[p_{1}]$ over all degree-$d$ pseudoexpectations $\mathop{\bf\widetilde{E}\/}$ that satisfy the identities $\{q_{i}=0:i\in[m]\}$. A feasibility problem, in particular, would ask if there is a degree-$d$ pseudoexpectation satisfying certain polynomial equality constraints. These SOS relaxations can be expressed using a semidefinite program (SDP) of size $n^{O(d)}$. The Sum of Squares algorithm refers to (approximately) solving the SDP, which can generally be done in $n^{O(d)}$ time.

As suggested by the name, pseudoexpectations generalize the notion of expectations with respect to a probability distribution on real indeterminate values satisfying the given polynomial identity constraints. In particular, if there is at least one real solution for the polynomial identity constraints, then any probability distribution on solutions yields a valid degree-$d$ pseudoexpectation, for any $d$. However, even when the polynomial constraints have no real solution, there may well be pseudoexpectations of limited degree that satisfy all the constraints. As one would expect, as the degree $d$ grows, the pseudoexpectations resemble actual expectations more and more. Indeed, if the constraints include that the $n$ indeterminates are Boolean (“$x_{i}^{2}=x_{i}$” or “$x_{i}^{2}=1$”) then every degree-$2n$ pseudoexpectation in fact corresponds to an actual distribution on real solutions.

In our context of CSPs, we can think of a constraint satisfaction problem $\mathcal{E}=\{(P_{i},S_{i})\}$ over $n$ Boolean variables $x_{1},\dots,x_{n}$ as a polynomial feasibility problem, with (the arithmetization of) the constraints $P_{i}(x_{S_{i}})=1$ as polynomial identities. As we know, randomly chosen CSPs with $\Delta\gg 1$ are unsatisfiable whp; to show a lower bound on the degree-$d$ SOS refutation algorithm amounts to showing that there exists a degree-$d$ pseudoexpectation that satisfies all the constraints. In more casual terminology, we say that degree-$d$ SOS “thinks” that the CSP is satisfiable.

4 Main result

We can now describe our main result with the terminology and set-up developed above.

In particular, if our instance comes from an actual random CSP with predicates, where for each $f$ the distribution $\mu_{f}$ is supported on satisfying assignments for the predicate at $f$, then the degree-$D$ SOS algorithm “thinks” that the CSP is completely satisfiable. This is of course despite the fact that, whp, the CSP is not satisfiable.

Sketch of our techniques

Throughout this section, we describe our techniques in the context of CSPs on $n$ Boolean variables and $k$-ary predicates that are $(\tau-1)$-wise uniform. As stated before, almost all of our ideas are present in this special case. Our goal is to build a degree-$d$ pseudoexpectation operator $\mathop{\bf\widetilde{E}\/}$ as described in Theorem 2.9.

As in all previous works on CSP lower bounds for hierarchies, we use a variant of the natural pseudoexpectation introduced by Benabbas et al. [BGMT12]. This pseudoexpectation is always defined in terms of a certain “closure” operator on instance graphs; previous works have used slightly different notions of “closure”. Our method introduces yet another definition of closure that we believe is the “right” one; at the very least, it seems to be precisely the right definition for facilitating our proofs.

We can describe a pseudoexpectation by prescribing its values on the basis of monomials of degree at most $d$. We work with the Fourier basis; i.e., $\pm 1$ notation.

In the context of CSPs, a natural way to come up with a pseudoexpectation is via the idea of local distributions. If $\mathop{\bf\widetilde{E}\/}$ is a degree-$d$ pseudoexpectation, then for every collection $S$ of at most $d/2$ variables, $\mathop{\bf\widetilde{E}\/}$ agrees with the expectation of an actual probability distribution. In particular, the pseudoexpectation of a monomial $x^{S}:=\prod_{i\in S}x_{i}$ for $S\subseteq[n]$ (or indeed any function on $S$) can then be described as the expectation of $x^{S}$ with respect to the local distribution $\eta_{S}$ that $\mathop{\bf\widetilde{E}\/}$ induces on the set $S$ of variables. For such a definition to make sense, the local distributions must satisfy consistency: the pseudoexpectation of $x^{T}$ should equal the expectation of $x^{T}$ with respect to the local distribution $\eta_{S}$ for any $S$ that includes $T$ and is of size at most $d$.

We would like to choose local distributions $\eta_{S}$ that are supported on satisfying assignments of all constraints completely included in $S$ (we call these the constraints covered by $S$). At first blush, we could choose the uniform distribution over the set of satisfying assignments for the constraints covered by $S$. However, this choice doesn’t satisfy the consistency constraints. The $t$-wise uniform distributions that are supported on satisfying assignments of the predicate $P$ now come to our rescue: if we obtain a local probability distribution that induces $\mu$ on the literals of any constraint in our CSP instance, we should intuitively expect be in good shape because $t$-wise uniformity roughly guarantees that any constraint that intersects $S$ in $t$ or less variables has a satisfying assignment that agrees with the assignment sampled for $S$. A natural choice is to define the probability of an assignment to $S$ to be the product of the probabilities (with respect to $\mu$) of the partial assignments corresponding to the constraints covered by $S$. This doesn’t work as-is, either: there could be constraints that intersect $S$ in many variables and yet are not completely contained inside $S$. A sample from $\eta_{S}$ thus might already force such a constraint to not be satisfied.

To correct for this, we want to collect all such “dependencies” before choosing the local distribution. Benabbas et al. [BGMT12] make this idea precise by defining a notion of closure for a set of variables $S$: intuitively, these are all the variables that one should care about when defining the local distribution on $S$. Concretely, their closure maps $S$ into a larger set $S^{\prime}$ such that for any $T\supseteq S^{\prime}$, the marginal of $\eta_{T}$ on $S$ is equal to the marginal of $\eta_{S^{\prime}}$ on $S$. We then choose $\eta_{S^{\prime}}$ to be the local distribution on $S^{\prime}$ and define $\eta_{S}$ to be the marginal of $\eta_{S^{\prime}}$ on $S$. For such an effort to be feasible, $S^{\prime}$ shouldn’t be much bigger than $S$: if in the extreme case the closure happened to be the whole set of variables $[n]$, we cannot define a distribution on satisfying assignments of all constraints covered by $S^{\prime}$.

The closure of Benabbas et al. [BGMT12] guarantees local consistency as we wanted. Local consistency is all that is required for showing a Sherali–Adams lower bound and is equivalent to the following local positivity condition, which is weaker than positive semidefiniteness: $\mathop{\bf\widetilde{E}\/}[p]\geq 0$ for $p$ for every truly nonnegative polynomial $p$ depending on at most $d$ variables. However, when trying to show that the more global $\mathop{\bf\widetilde{E}\/}[p^{2}]$ positive-semidefiniteness condition holds, the [BGMT12] construction seems hard to analyze.

To address this problem, Barak, Chan, and Kothari [BCK15] introduced a simpler variant of the [BGMT12] closure in order to show that the $\mathop{\bf\widetilde{E}\/}$ defined above satisfies the positive-semidefiniteness condition for certain pruned random instances of the CSP$(P^{\pm})$, when $P$ supports a pairwise-uniform distribution. However, their definition of closure degenerates into the set of all variables with high probability when the random CSP has $\Delta=\omega(1)$.

One of the main innovations in our work is the introduction of a new, simpler definition of closure that plays a key role in our proof of positive semidefiniteness and gives a definition of $\mathop{\bf\widetilde{E}\/}$ that works even when the number of constraints is superlinear in $n$. In addition, our definition of closure enables us to extend our results to $\delta$-refutation.

Our closure for a set of variables $S$ is a subgraph of the factor graph of the CSP instance, including both variables and constraints. We think of the closure of $S$ as being the set of variables and constraints that “matter” when defining the distribution $\eta_{S}$. Given that a predicate $P$ supports a $(\tau-1)$-wise uniform distribution, any constraint that affects $\eta_{S}$ must have at least $\tau-1$ variables in $S$. Otherwise, $(\tau-1)$-wise uniformity implies that we could ignore such a constraint without changing $\eta_{S}$. Any variable $v$ not in $S$ that occurs in only one constraint isn’t necessary for defining $\eta_{S}$, either. We could sum $\eta_{S}$ over the two assignments to $v$ to get a new distribution that no longer depends on $v$. This leads to a natural choice of the closure as the union of all small subgraphs of the factor graph such that each constraint contains at least $\tau-1$ variables and each variable outside of $S$ occurs in at least two constraints. For a formal definition, see Section 5.

2 Proving positivity

Once we have the definition of the pseudoexpectation, we get to the main challenge in showing any SOS lower bound: arguing positive-semidefiniteness of the $\mathop{\bf\widetilde{E}\/}$ constructed. The high level idea in our analysis builds on the work of Barak, Chan and Kothari [BCK15]. Their idea of proving positive-semidefiniteness is simple. They begin by observing that it suffices to verify positive-semidefiniteness for a basis that satisfies orthogonality under $\mathop{\bf\widetilde{E}\/}[\cdot]$, meaning, the pseudoexpectation of the product of any distinct pair of basis polynomials is .

Suppose there exists a basis $f_{1},f_{2},\ldots$ for degree-$d$ polynomials such that the following two properties hold:

$\mathop{\bf\widetilde{E}\/}[f_{i}f_{j}]=0$ for all $i\neq j$.

$\mathop{\bf\widetilde{E}\/}[f_{i}^{2}]\geq 0$ for all $i$.

Then $\mathop{\bf\widetilde{E}\/}[g^{2}]\geq 0$ for all $g$ of degree at most $d$.

Write $g$ as $\sum_{i}a_{i}f_{i}$. Then $\displaystyle\mathop{\bf\widetilde{E}\/}[g^{2}]=\sum_{i,j}a_{i}a_{j}\mathop{\bf\widetilde{E}\/}[f_{i}f_{j}]=\sum_{i}a_{i}^{2}\mathop{\bf\widetilde{E}\/}[f_{i}^{2}]\geq 0.\qed$

Notice that the standard Fourier monomial basis guarantees us positivity (since $\mathop{\bf\widetilde{E}\/}$ satisfies the local Sherali–Adams positivity condition by construction). However, it is not orthogonal in general. How can we construct such a basis? One way to construct a basis that is orthogonal under $\mathop{\bf\widetilde{E}\/}[\cdot]$ is to perform the Gram–Schmidt process on, say, the monomial basis $1,x_{1},x_{2},\ldots,x_{1}x_{2},\ldots$ to get a new basis $f_{1},f_{2},\dots$. Now, Property 1 above holds for this new basis by construction. However, the Gram–Schmidt process is highly sequential and, in particular, the basis function towards the end could depend on all $n$ variables. Thus, we cannot appeal to local positivity of $\mathop{\bf\widetilde{E}\/}$ in order to argue positive-semidefiniteness of the newly generated basis. It appears that we have made no progress, ensuring orthogonality but potentially losing positivity.

The idea of Barak et al. to escape this pitfall is to show that local orthogonalization is enough. Before the start of the Gram–Schmidt process, we fix an order on basis vectors. In each step of the process, one orthogonalizes a basis function against all previous basis functions in this order by subtracting off its projection onto their span. Barak et al. analyze the variant of this process in which one orthogonalizes a basis function $x^{S}$ by subtracting off its projection onto the span of all basis functions the precede it in the order and are functions of variables that lie in a small “ball” around $S$ in the factor graph $G$ of the instance. This lets them ensure that the new basis satisfies positivity (since it now depends only on a small number of variables, one can appeal to the local positivity of $\mathop{\bf\widetilde{E}\/}$), and they show that this relaxed variant of the Gram–Schmidt process still ensures orthogonality.

Their proof, however, is highly combinatorial and requires various assumptions on the factor graph of the instance that intuitively shouldn’t matter. In particular, they need that the factor graph have no small cycles (girth should be logarithmic): while this can be ensured by pruning $o(n)$ fraction of the constraints in a random instance with $\Theta(n)$ constraints, this proof strategy breaks down for super-linear number of constraints .

Our main idea simplifies the analysis without requiring the assumptions of [BCK15] and yields tight results. It also naturally extends to the case of $t$-wise uniform predicates and further to $\delta$-approximate $t$-wise uniform predicates. We next describe our key technical ideas that makes this possible.

At a high level, our argument drops the local orthogonalization strategy of Barak et al. [BCK15] and instead runs the Gram–Schmidt procedure “as-is”. Thus orthogonality of the resulting basis functions is immediate, and we need only show positive-semidefiniteness. We show that for any sequential ordering of the basis monomials in the Gram–Schmidt procedure, so long as it is of increasing degree, whenever we orthogonalize a monomial $x^{S}$, the result basis function depends only on a small number of variables.

To see why such an assertion might be plausible, let us consider the task of orthogonalizing the singletons. The monomial basis may not orthogonal under $\mathop{\bf\widetilde{E}\/}[\cdot]$; e.g., consider the following $3$-XOR instance:

Observe that $x_{1}$ and $y_{1}$ each appear in exactly one constraint and all other variables each occur in exactly two constraints. Multiplying each block of constraints together, we see that if $\mathop{\bf\widetilde{E}\/}[\cdot]$ satisfies all constraints then $\mathop{\bf\widetilde{E}\/}[x_{1}]=1$ and $\mathop{\bf\widetilde{E}\/}[y_{1}]=-1$. So neither $x_{1}$ nor $y_{1}$ are orthogonal to $1$. Since the two sets of equations are disjoint, we also know that $\mathop{\bf\widetilde{E}\/}[x_{1}y_{1}]=-1$, so $x_{1}$ and $y_{1}$ are not orthogonal. We note that many such blocks may occur in a random instance with $m\gg n^{1.4}$ constraints. Let’s try to understand what happens when we run the Gram–Schmidt procedure on this basis. Consider an instance consisting of $n$ such disjoint blocks of $5$ constraints on $8n$ variables. Let $x_{i1}$ be the variables that is fixed in block $i$. Then every $x_{i1}$ is not orthogonal to $1$ and every pair $x_{i1},x_{j1}$ is not orthogonal. Intuitively, the variables $x_{i1},x_{j1}$ behave independently, but are biased. To fix this bias, consider the functions $\overline{x}_{i1}$ (where we use the notation $\overline{z}\coloneqq z-\mathop{\bf\widetilde{E}\/}[z]$). Now we have that $\overline{x}_{i1}$ is orthogonal to $1$ and, by independence of the blocks, $\mathop{\bf\widetilde{E}\/}[\overline{x}_{i1}\cdot\overline{x}_{j1}]=0$ for all $i,j$.

Ideally, we might hope this this new basis satisfies orthogonality when we move to degree $2$, as well. Unfortunately, in general the basis $\{1,\overline{x}_{1},\overline{x}_{2},\ldots,\overline{x}_{n},\overline{x_{1}x_{2}},\ldots\}$ again need not be orthogonal. Consider a $3$-XOR instance with $n$ constraints $x_{0}x_{i}y_{i}=b_{i}$ for $i\in[n]$; call this an $n$-star. Random instances contain stars of superconstant size with high probability. For all $\binom{n}{2}$ pairs $i,j$, it holds that $\overline{x_{i}y_{i}}$ and $\overline{x_{j}y_{j}}$ are not orthogonal under $\mathop{\bf\widetilde{E}\/}[\cdot]$:

A simple calculation shows that these basis functions are orthogonal. Each basis function depends on at most $3$ variables, so the degree-$3$ Sherali-Adams positivity condition and Fact 3.1 imply that degree-$2$ positive semidefiniteness holds. We give a proof of orthogonality of $\widehat{x_{i}y_{i}}$ and $\widehat{x_{j}y_{j}}$ that illustrates the underlying intuition. Observe that $\widehat{x_{i}y_{i}}$ and $\widehat{x_{j}y_{j}}$ are independent conditioned on $x_{0}$ for all $i\neq j$, and we can write

where $1_{\{x_{0}=b\}}$ is the indicator function for $x_{0}=b$. Since we have orthogonalized $\widehat{x_{i}y_{i}}$ against all degree-$1$ basis functions and $1_{\{x_{0}=b\}}$ is a degree-$1$ polynomial, this expression is equal to . Therefore, $\mathop{\bf E\/}[\widehat{x_{i}y_{i}}|x_{0}]=0$ and $\widehat{x_{i}y_{i}}$ and $\widehat{x_{j}y_{j}}$ are orthogonal. In this case, $x_{i}y_{i}$ and $x_{j}y_{j}$ are correlated because they are connected by $x_{0}$. After subtracting off their correlation with $x_{0}$, the resulting functions are orthogonal and no longer correlated.

Let us now formalize this intuition and generalize it to higher degree. At a high level, our idea is to show that the Gram–Schmidt process produces a basis such that each new basis element depends only on a small number of variables. Let $y_{S}$ be the result of applying the Gram–Schmidt process to $x^{S}$. If $y_{T}$ appears in $y_{S}$ with a nonzero coefficient, then it must be the case that $\mathop{\bf\widetilde{E}\/}[x^{S}\cdot y_{T}]\neq 0$. That is, $x^{S}$ and $y_{T}$ are correlated under $\mathop{\bf\widetilde{E}\/}[\cdot]$. We show that this correlation is “witnessed” by some small, “dense” subgraph containing many constraints covered by few variables. If $y_{S}$ has many variables in its support, then there must be many such subgraphs. We show that the union of these subgraphs is dense enough to be “implausible”. This means that $y_{S}$ cannot have too many variables in its support.

Our witness can be seen as a generalization of the connected sets in the degree-$2$ case discussed above. Call two sets of vertices $c$-connected if removing any set of $c-1$ vertices cannot disconnect them. In the degree-$1$ case, nonzero correlation between $x^{S}$ and $y_{T}$ with $|S|=|T|=1$ is witnessed by a small, dense, connected ($1$-connected) subgraph. In the degree-$2$ case after orthogonalizing against degree-$1$ terms, we expect based on the star example that if $S$ and $T$ are only $1$-connected, then $x^{S}$ and $y_{T}$ will no longer be correlated. We show that nonzero correlation between $x^{S}$ and $y_{T}$ with $|S|=|T|=2$ is then witnessed by a small, dense, $2$-connected subgraph. In general, we show that nonzero correlation between $x^{S}$ and $y_{T}$ with $|S|=|T|=d$ is witnessed by a small, dense, $d$-connected subgraph. This stronger connectivity requirement enables us to show that these witness subgraphs and their unions are dense enough to be implausible if the support of a basis function grows too large. For details of this argument, see Section 6.

Forbidden subgraphs for the factor graph

Let us make a few definitions concerning factor graphs, after which we will elaborate on the “Plausibility Assumption”.

We call $H$ a subgraph of $G$ if it is an edge-induced subgraph; i.e., $H=G[A]$ for some subset $A$ of the edges of $G$. We explicitly allow $A=\emptyset$ and hence $H=\emptyset$. The subgraph $H$ need not be connected.

We will typically measure the “size” of a subgraph by the number of constraints in it:

Now regarding the Plausibility Assumption, for intuition’s sake let us suppose we are concerned with weak refutation and degree-$O(1)$ SOS, as in Corollary 1.5. Thus we have some $k$-ary predicate $P$ with $\mathcal{C}(P)=\tau$, and we are selecting a random CSP with slightly fewer than $n^{\tau/2}$ constraints; say $m=n^{(\tau-\zeta)/2}$. What does a random factor graph look like in this case? Which small subgraphs may appear? A quick-and-dirty method to analyze this is as follows. Consider the fixed small subgraph in Figure 1; call it $H$.

What is the expected number of copies of $H$ in a random factor graph $G$ with $n$ variable-vertices and $m=n^{(\tau-\zeta)/2}$ constraint-vertices? There are $\binom{m}{2}\approx m^{2}$ choices for $H$’s $2$ constraint-vertices and $\binom{n}{4}\approx n^{4}$ choices for $H$’s $4$ variable-vertices. Thinking of each constraint-vertex as choosing $k=O(1)$ random neighbors, the chance that the $6$ edges of $H$ show up is roughly $n^{-6}$. Thus, very roughly, we expect about $m^{2}n^{4}n^{-6}=n^{2\cdot(\tau-\zeta)/2+(4-6)}$ copies of $H$ in a random $G$. Thus copies of $H$ “plausibly” show up if and only $2\cdot(\tau-\zeta)/2+(4-6)\geq 0$; i.e., if and only if $\tau\geq 2+\zeta$. Since $\tau\geq 3$ always, this means we should certainly expect copies of $H$ in $G$.

This inequality is precisely the one occurring in the Plausibility Assumption from Section 2.2.

Despite the simple form of the inequality, we will find it helpful to view it in a different way. For reasons that will become clear in Section 5, we will be concerned almost exclusively with subgraphs of $G$ in which all constraint-vertices have degree at least $\tau$:

The empty subgraph $\emptyset$ is always trivially a $\tau$-subgraph. Also, if $H$ and $H^{\prime}$ are $\tau$-subgraphs then so is $H\cup H^{\prime}$.

Given a subgraph $H$, we classify the variable-vertices in $H$ as either leaf or interior depending on whether they have degree $1$ or at least $2$. (Since $H$ is an edge-induced subgraph, it does not have any isolated vertices.)

For $\tau$-subgraphs, there is a different way to view the “plausibility inequality” that will be more useful for us. We define it with some “accounting” terminology.

Let $H$ be a $\tau$-subgraph. For the purposes of this definition, consider each of its edges to be two directed edges.

For each variable-vertex, any out-edges in excess of $2$ are called excess, and we assign a debit for each. We’ll write $e_{v}$ for the total number of these.

For each constraint-vertex, any out-edges in excess of $\tau$ are called excess, and we assign a debit for each. We’ll write $e_{c}$ for the total number of these, and $e=e_{c}+e_{v}$ for the total debit (number of excess edges).

Let $H$ be a $\tau$-subgraph. We say that $H$ is plausible if $I(H)\geq 0$.

The next lemma implies that the inequality $I(H)\geq 0$ is the same as the inequality appearing in the Plausibility Assumption and in (1).

In light of this, we may restate the Plausibility Assumption:

As mentioned earlier, for an appropriate choice of SMALL , the Plausibility Assumption holds for a random instance. More precisely, in Appendix A we prove the below theorem. The reader is advised that in this theorem, the first claim is the main one; it is used to show our Theorem 1.2 concerning weak refutation. The second claim (“Moreover…”) is a technical variant needed to extend our results to give Theorem 1.1 concerning $\delta$-refutation.

Let $\lambda=\tau-2\geq 1$. Fix $0<\zeta\leq.99\lambda$, $0<\beta<\frac{1}{2}$. Then except with probability at most $\beta$, when $\boldsymbol{G}$ is a random instance with $m=\Delta n$ constraints, the Plausibility Assumption holds provided

where $\gamma=\frac{1}{K}\left(\frac{\beta^{1/\lambda}}{2^{K/\lambda}}\right)^{O(1)}$. Moreover, assuming $\zeta<1$, except with probability at most $\beta$ we have

Defining the pseudoexpectation

In this section we define the “closure” of a set of variables. Roughly speaking, this can be thought of as the smallest $\tau$-subgraph of $G$ that fully determines the distribution on $S$ under a natural “planted distribution”.

Let $S$ be a set of variables. We say that a subgraph $H$ is $S$-closed if it is a $\tau$-subgraph and all its leaf vertices are in $S$.

For every constraint in $G$, if $H$ is taken to be the full neighborhood of that constraint, and $S$ is the set of variables in that constraint, then $H$ is $S$-closed.

Note that a union of $S$-closed $\tau$-subgraphs is $S$-closed. This leads us to the following definition:

If $H$ is $\emptyset$-closed then its revenue is at most . Hence if it is plausible, its cost is . ∎

We will now give an important generalization of this fact for $S$-closures, $|S|>0$

Suppose that $H$ is a $\tau$-subgraph formed as a union, $H=H_{1}\cup\cdots\cup H_{t}$, where each $H_{j}$ is small and where we have $R(H_{1}\cup\cdots\cup H_{j})\leq\zeta\cdot\scalebox{0.75}[1.0]{{SMALL}}$ for all $1\leq j\leq t$. Then $H$ is small.

showing that $H^{\prime}\cup H_{t}$ is small, completing the induction. ∎

2 The planted distribution

We’ll write $\eta_{H}$ for the probability distribution on $\Omega^{n}$ associated to this planted distribution on $H$, and we’ll write $\mathop{\bf E\/}_{H}[\cdot]$ for the associated expectation.

Although the notation in the below proof looks cumbersome, the calculations are actually fairly straightforward. We strongly encourage the reader to work through the proof in the case of $q=2$, $\Omega=\{\pm 1\}$, with “$\overline{1_{c}}(x_{i})$” replaced by $cx_{i}\in\{\pm 1\}$.

since $\mathop{\bf E\/}_{\boldsymbol{c}\sim\Omega}[\overline{1_{\boldsymbol{c}}}(x_{i})]=0$ for any fixed value $x\in\Omega$. Thus in (3) it is equivalent to sum over $\tau$-subgraphs $H^{\prime}$, and so returning to (2) we get

Suppose now that $T\subseteq[n]$ is a set of variables. We’ll decompose an $x\in\Omega^{n}$ into its projection $x_{T}$ onto the coordinates in $T$ and $x_{\overline{T}}$ onto the coordinates not in $T$. Then

where we used (4). Now suppose the $\tau$-subgraph $H^{\prime}$ has a leaf vertex $j$ that is in $\overline{T}$; i.e., it’s not in $T$. Then ${\boldsymbol{x}}_{j}$ appears exactly once in the above, within the expression

As ${\boldsymbol{x}}_{j}$ is chosen uniformly and independently of all random variables, the above contains a factor of the form $\mathop{\bf E\/}_{{\boldsymbol{x}}_{j}\sim\Omega}[\overline{1_{\boldsymbol{w}_{f,j}}}({\boldsymbol{x}}_{j})]$. But for any fixed outcome of $\boldsymbol{w}_{f,j}$, this expectation is , meaning (6) will vanish. Thus any summand $H^{\prime}$ in (5) will vanish if $H^{\prime}$ has a leaf variable outside $T$. Thus we may equivalently sum only over $T$-closed $H^{\prime}$. That is,

Suppose we took $T=\emptyset$ above. Since $H$ is small, every subgraph $H^{\prime}$ is plausible and hence Fact 5.6 implies that the above has only one summand, corresponding to $H^{\prime}=\emptyset$. The summand is trivially $1$, and hence

Observe that this does not depend at all on the $\mu_{f}$’s; in particular, it is easily seen to the be the probability of consistent suggestions under completely uniform $\mu_{f}$’s. In any case, since (8) is positive, as promised, we may condition on the associated event; thus from (7) we obtain

3 Pseudoexpectations

In this section, we formally define the pseudoexpectation with which we will work.

Given a polynomial expression $p(x)$ in the indeterminates $1_{c}(x_{i})$, we write

Recall that a pseudoexpectation on polynomials of degree at most $D$ is a linear map $\mathop{\bf\widetilde{E}\/}[\cdot]$ satisfying $\mathop{\bf\widetilde{E}\/}=1$. We can uniquely define it by specifying its values on all monomials of degree at most $D$. Further, recall that if $p(x)$ is a polynomial, we say that $\mathop{\bf\widetilde{E}\/}[\cdot]$ satisfies the identity $p(x)=0$ if $\mathop{\bf\widetilde{E}\/}[p(x)\cdot q(x)]=0$ for all polynomials $q(x)$ with $\deg(p\cdot q)\leq D$.

Let $p(x)$ be a polynomial expression of multilinear-degree at most $\zeta\cdot\scalebox{0.75}[1.0]{{SMALL}}$. Let $H$ be any small subgraph containing

This is immediate from Theorem 5.12 and Remark 5.5. ∎

Let $q(x)$ be a nonzero polynomial with $\deg(p\cdot q)\leq\zeta\cdot\scalebox{0.75}[1.0]{{SMALL}}$. Writing $q(x)=\sum_{j}M_{j}(x)$ where each $M_{j}(x)$ is a monomial, we have

We have the following immediate corollaries:

Our pseudoexpectation $\mathop{\bf\widetilde{E}\/}[\cdot]$ satisfies the following identities:

$\sum_{c\in\Omega}1_{c}(x_{i})=1$ for all $i\in[n]$ (i.e., the identity $\sum_{c\in\Omega}1_{c}(x_{i})-1=0$).

$1_{c}(x_{i})^{2}=1_{c}(x_{i})$ for all $c\in\Omega,i\in[n]$.

Another corollary is the following (cf. the rough statement of our main technical result, Theorem 2.9):

Our pseudoexpectation $\mathop{\bf\widetilde{E}\/}[\cdot]$ satisfies the identity

The proof of positive semidefiniteness

Throughout this section, fix a degree $D$ satisfying $1\leq D\leq\frac{1}{3}\zeta\cdot\scalebox{0.75}[1.0]{{SMALL}}$. Our goal will be to establish:

If $p(x)$ is a polynomial expression of degree at most $D$, then $\mathop{\bf\widetilde{E}\/}[p(x)^{2}]\geq 0$.

A monomial index will be a set $S$ of pairs $(i,c)\in[n]\times\Omega$, with no variable $i\in[n]$ occurring more than once. We write $x^{S}$ for the monomial $\prod_{(i,c)\in S}1_{c}(x_{i})$, with the usual convention that $x^{\emptyset}=1$. Finally, we write $\mathcal{M}^{\leq D}$ for the collection of monomial indices $S$ with $|S|\leq D$.

We abuse notation as follows: If a monomial index $S$ occurs in a place where a subset of variables is expected, we intend the subset of variables \{i:(i,c)\in S\text{ for somec}\}.

2 Gram–Schmidt overview

Our goal in this section is to show that the modified Gram–Schmidt process from linear algebra can be successfully applied to the monomials $({x}^{S}:S\in\mathcal{M}^{\leq D})$, in the ordering $\preceq$, using $\mathop{\bf\widetilde{E}\/}[\cdot]$ as the “inner product”: $\langle p(x),q(x)\rangle\coloneqq\mathop{\bf\widetilde{E}\/}[p(x)\cdot q(x)]$. Of course, we don’t know that this is a genuine inner product (indeed, that’s essentially what we’re trying to prove). We will discuss this issue shortly, but we first remind the reader that the modified Gram–Schmidt process would typically produce a collection of polynomials $y_{S}=y_{S}(x)$, for $S\in\mathcal{M}^{\leq D}$, that are orthogonal under $\mathop{\bf\widetilde{E}\/}[\cdot]$ (meaning $\mathop{\bf\widetilde{E}\/}[y_{S}\cdot y_{S^{\prime}}]=0$ if $S\neq S^{\prime}$) and that have the same span as $({x}^{S}:S\in\mathcal{M}^{\leq D})$. As well, it would produce “normalized” versions of these polynomials $z_{S}=y_{S}/\sqrt{\mathop{\bf\widetilde{E}\/}[y_{S}^{2}]}$, satisfying $\mathop{\bf\widetilde{E}\/}[z_{S}^{2}]=1$.

We now address the obviously difficulty that $\mathop{\bf\widetilde{E}\/}[\cdot]$ is not (known to be) an inner product, because we don’t know it’s positive definite on the monomials of $\mathcal{M}^{\leq D}$. Our goal will be to show that as we follow the Gram–Schmidt process, it never encounters any “positive definiteness problems”, and therefore “succeeds”. The main “positive definiteness problem” Gram–Schmidt might encounter would be if it creates a polynomial $y_{S}$ with $\mathop{\bf\widetilde{E}\/}[y_{S}^{2}]<0$. In this case, when it tries to produce the normalized polynomial $z_{S}$, it would certainly fail.

There is one additional potential problem, occurring if Gram–Schmidt produces a $y_{S}$ with $\mathop{\bf\widetilde{E}\/}[y_{S}^{2}]=0$. In the usual process from linear algebra this may indeed occur, and the Gram–Schmidt algorithm copes by treating $z_{S}$ as (effectively, throwing it out of the span). This is a valid strategy because genuine inner products are strictly positive definite. However we only expect our “inner product” $\mathop{\bf\widetilde{E}\/}[\cdot]$ to be positive semidefinite. We therefore need a different coping mechanism. For us, when $\mathop{\bf\widetilde{E}\/}[y_{S}^{2}]=0$ occurs, we will simply define its “normalized” version $z_{S}$ to be $y_{S}$. The challenge of this is that Gram–Schmidt’s guarantee of producing an orthogonal collection $(y_{S}:S\in\mathcal{M}^{\leq D})$ relies syntactically on all the $z_{S}$ polynomials satisfying $\mathop{\bf\widetilde{E}\/}[z_{S}^{2}]=1$. Thus we will have an additional burden: we will have to “manually” show that $\mathop{\bf\widetilde{E}\/}[y_{S}^{2}]=0$ implies that $y_{S}$ is orthogonal under $\mathop{\bf\widetilde{E}\/}[\cdot]$ to all other polynomials. It will count as a “positive definiteness problem” if we are unable to show this; we will call this the “pseudovariance zero problem”. We remark that the main positive definiteness problem is fundamentally more important than this “pseudovariance zero problem”, and the reader may wish to ignore the pseudovariance zero issue on first reading.

We now describe the modified Gram–Schmidt process in detail. The process works in stages, named after the elements of $\mathcal{M}^{\leq D}$ and in order of $\preceq$. At the end of stage $S$ it creates a certain polynomial $z_{S}$. Stage $\emptyset$ always “succeeds” and simply consists of defining $z_{\emptyset}=1$. In some cases it may happen that $\mathop{\bf\widetilde{E}\/}[z_{S}^{2}]=0$. In this case we say that $z_{S}$ has pseudovariance zero, and the Gram–Schmidt algorithm will add $S$ to a growing collection called PvZ .

Each stage $S$ is further divided into substages, associated to monomial indices $T\prec S$ in order of $\preceq$. Let us introduce some notation:

Let $\mathcal{M}^{\leq D}_{2}$ denote the collection of all pairs $(S,T)\in\mathcal{M}^{\leq D}\times\mathcal{M}^{\leq D}$ with $T\prec S$. We define a total ordering $\preceq_{2}$ on $\mathcal{M}^{\leq D}_{2}$ via

Thus the overall progression of substages in Gram–Schmidt is through the elements of $\mathcal{M}^{\leq D}_{2}$ in order of $\preceq_{2}$. Substage $(S,T)$ creates a polynomial $y_{S,T}$ as follows:

Of course, if $\mathop{\bf\widetilde{E}\/}[y_{S}^{2}]<0$ then we have encountered a positive definiteness problem. Indeed, to be conservative we will treat it as a problem if $\mathop{\bf\widetilde{E}\/}[y_{S,T}^{2}]<0$ for any $(S,T)\in\mathcal{M}^{\leq D}_{2}$.

We may now summarize the discussion so far:

Suppose the modified Gram–Schmidt process succeeds through substage $(S,T)$. Then we have:

$y_{S,T}={x}^{S}-p(x)$ for some polynomial $p(x)$ supported on monomials ${x}^{T^{\prime}}$ with $T^{\prime}\preceq T$;

$\mathop{\bf\widetilde{E}\/}[y_{S,T}\cdot z_{T^{\prime}}]=0$ for all $T^{\prime}\preceq T$, and hence $\mathop{\bf\widetilde{E}\/}[y_{S,T}\cdot q(x)]=0$ for all polynomials $q(x)$ supported on monomials $x^{T^{\prime}}$ with $T^{\prime}\preceq T$;

$\mathop{\bf\widetilde{E}\/}[y_{S,T}^{2}]\geq 0$.

In particular, if the process succeeds through stage $S$, we have:

$z_{S}=c\cdot{x}^{S}-p(x)$ for some positive constant $c>0$ and some polynomial $p(x)$ supported on monomials ${x}^{T}$ with $T\prec S$;

$\mathop{\bf\widetilde{E}\/}[z_{S}\cdot z_{T}]=0$ for all $T\prec S$, and hence $\mathop{\bf\widetilde{E}\/}[z_{S}\cdot q(x)]=0$ for all polynomials $q(x)$ supported on monomials ${x}^{T^{\prime}}$ with $T^{\prime}\prec S$;

$\mathop{\bf\widetilde{E}\/}[z_{S}^{2}]=0$ if $S$ is put in PvZ , else $\mathop{\bf\widetilde{E}\/}[z_{S}^{2}]=1$.