Hypercontractive inequalities via SOS, and the Frankl--Rödl graph

Introduction

The hypercontractive inequality is almost always used with either $p=2$ or $q=2$. The $(2,4)$-hypercontractivity inequality — i.e., the case $q=4$, $p=2$, $\rho=1/\sqrt{3}$ — is a particularly useful case, as is the following easy corollary:

Theorem 1.1 is known to have a proof which is noticeably simpler than that of the general hypercontractive inequality [MOO05]. Theorem 1.1 can be used to prove, e.g., the KKL Theorem [KKL88], the sharp small-set expansion statement for the $1/3$-noisy hypercube, and the Invariance Principle of [MOO10]. More generally, the hypercontractivity inequality has the following corollary:

This corollary is often used to control the behavior of low-degree polynomials of random bits.

Reverse hypercontractivity is perhaps most often used to show that if $A,B\subseteq\{-1,1\}^{n}$ are large sets and $({\boldsymbol{x}},\boldsymbol{y})$ is a $\rho$-correlated pair of random strings then there is a substantial chance that ${\boldsymbol{x}}\in A$ and $\boldsymbol{y}\in B$. This was first deduced in [MOR+06] by deriving the following consequence of reverse hypercontractivity:

The reverse hypercontractive inequality has been used, e.g., in problems related to approximability and hardness of approximation [FKO07, She09, BHM12], and problems in quantitative social choice [MOO10, Mos12a, MOS12b, Kel12, MR12].

The present work is concerned with proving hypercontractive inequalities via “sums of squares” (SOS); i.e., in the Positivstellensatz proof system introduced by Grigoriev and Vorobjov [GV01]. A recent work of Barak et al. [BBH+12] showed that the Khot–Vishnoi [KV05] SDP integrality gap instances for Unique-Games are actually well-solved by the “$4$-round Lasserre SDP hierarchy”; equivalently, the “degree-$8$ SOS hierarchy”. This is despite the fact that they are strong gap instances for superconstantly many rounds of other weaker SDP hierarchies such as Lovász–Schrijver+ and Sherali–Adams+ [RS09, KS09]. The key to analyzing the optimum value of the Khot–Vishnoi instances is the hypercontractive inequality, and perhaps the key technical component of the Barak et al. result is showing that Theorem 1.1 has a degree-$4$ “SOS proof”. That is, if we treat each $f(x)$ as a formal “indeterminate”, then $9^{k}\|f\|_{2}^{4}-\|\mathcal{P}^{\leq k}f\|_{4}^{4}$ is a degree-$4$ polynomial in the $2^{n}$ indeterminates, and Barak et al. showed that it is a sum of squared polynomials (hence always nonnegative).

The connection between SOS proofs and SDP relaxations for optimization problems was made independently by Lasserre [Las00] and Parrilo [Par00]. Roughly speaking, if a system of $n$-variate polynomial inequalities can be refuted within the degree-$d$ SOS proof system of Grigoriev and Vorobjov [GV01], then this refutation can also be found efficiently by solving a semidefinite program of size $n^{O(d)}$. The associated “degree-$d$ SOS hierarchy” for approximating optimization problems is known to be at least as strong as the Lovász–Schrijver+ and Sherali–Adams+ SDP hierarchies, and the [BBH+12] result shows that it can be noticeably stronger for the notorious Unique Games problem. (For more details, see e.g. [OZ13, BBH+12].)

Later, [OZ13] showed that the degree-$4$ SOS hierarchy correctly analyzes the value of the [DKSV06] instances of Balanced-Separator, which are known to be superconstant-factor integrality gap instances for superconstantly many rounds of the “LH SDP hierarchy” [RS09]. It was also shown in [OZ13] that the degree-$O(1)$ SOS hierarchy certifies the value of the [KV05] instances of Max-Cut to within factor $.952$, whereas superconstantly many rounds of the Sherali–Adams+ hierarchy are still off by a factor of $.878$ [RS09, KS09]. (The $.952$ here was very recently improved to any $1-\epsilon$. [DMN13]) The key to the former result was an SOS proof of the KKL Theorem (relying on [BBH+12]’s SOS proof of Theorem 1.1); the key to the latter was an SOS proof of an Invariance Principle variant, which in turn needed an SOS proof of higher-norm hypercontractivity, Theorem 1.2. The work [OZ13] was unable to actually obtain Theorem 1.2 with an SOS proof, but instead obtained a weaker version which sufficed for their purposes.

Still, the full power of the SOS hierarchy is far from well-understood. Analyzing what can and cannot be proved with low-degree SOS proofs is evidently very important; for example, it’s consistent with our current knowledge that the degree-$4$ SOS hierarchy refutes the Unique-Games Conjecture, gives a $1.01$-approximation for Uniform Sparsest-Cut, a $1.4$-approximation for Vertex-Cover, and certifies that any graph with chromatic number exceeding $5$ is not $3$-colorable.

In particular, hypercontractive inequalities have played a key role in many of the sophisticated SDP integrality gap instances. Thus it is natural to ask: Can a sharp version of the hypercontractive inequality be proved in the SOS proof system? Can any version of the reverse hypercontractive inequality be proved? As we will see, the latter question is particularly relevant for the known SDP integrality instances of the $3$-Coloring and Vertex-Cover problems.

2 Our results

The main result in this paper is an SOS proof of the reverse hypercontractivity Theorem 1.3 for all $q$ equal to the reciprocal of an even integer. As one application of this, we show that just the degree-$4$ algorithm from the SOS hierarchy can certify that the “Frankl–Rödl” SDP integrality gap instances for $3$-Coloring have chromatic number $\omega(1)$. Finally, we also give an SOS proof of the sharp $(2,q)$-hypercontractive inequality for all even integers $q$; in fact, a version with relaxed moment conditions. We find it interesting to see that the two powerful hypercontractive inequalities admit proofs as “elementary” as sum-of-squares proofs. On the other hand, to obtain these proofs we had to use somewhat elaborate methods, including computer algebra techniques.

As mentioned, Barak et al. [BBH+12] gave an SOS proof of Theorem 1.1, that $\|\mathcal{P}^{\leq k}f\|_{4}^{4}\leq 9^{k}\|f\|_{2}^{4}$. Although there is a very easy proof of this theorem “in ZFC” [MOO05], that proof uses the Cauchy–Schwarz inequality, whose square-roots do not obviously translate into SOS statements. The SOS proof in [BBH+12] gets around this by proving the generalized statement $\mathop{\bf E\/}[(\mathcal{P}^{\leq k}f)^{2}(\mathcal{P}^{\leq k^{\prime}}g)^{2}]\leq 3^{k+k^{\prime}}\mathop{\bf E\/}[f^{2}]\mathop{\bf E\/}[g^{2}]$, allowing them to replace Cauchy–Schwarz with $XY\leq\tfrac{1}{2}X^{2}+\tfrac{1}{2}Y^{2}$. In [OZ13] this SOS proof was very slightly generalized to cover the $(2,4)$-hypercontractive inequality, $\mathop{\bf E\/}[(T_{\rho}f)^{2}(T_{\rho}g)^{2}]\leq\mathop{\bf E\/}[f^{2}]\mathop{\bf E\/}[g^{2}]$ for $\rho=1/\sqrt{3}$. That work also gave an SOS proof of a weakened version of Theorem 1.2 for all even integers $q$, namely $\|\mathcal{P}^{\leq k}f\|_{q}^{q}\leq q^{O(qk/2)}\|f\|_{2}^{q}$. (Attention is restricted to even integers $q$ because the $(2,q)$-hypercontractive inequality cannot even be stated as a polynomial inequality otherwise.)

In Section 3 we prove the full $(2,q)$-hypercontractive inequality for all even integers $q$. Our strategy is as follows. First, we give a simple proof (“in ZFC”) of $(2,q)$-hypercontractivity for all even integers $q$; our proof works not just for random $\pm 1$ bits but for any random variables satisfying fairly liberal moment bounds. Indeed, we are not aware of any previous work showing that such moment bounds are sufficient for hypercontractivity. However this proof relies on the well-known fact that the hypercontractivity inequality tensorizes [KS88], which in turn uses the triangle inequality for the $(q/2)$-norm, an inequality that cannot even be stated in SOS. For our SOS extension of this result we move to a $(q/2)$-function version of the statement as in [BBH+12]; this requires some more work. Our final theorem is as follows:

As corollaries we have SOS proofs of $\|T_{\rho}f\|_{q}^{q}\leq\|f\|_{2}^{q}$ and $\|\mathcal{P}^{\leq k}f\|_{q}^{q}\leq(q-1)^{qk/2}\|f\|_{2}^{q}$.

We prove this result in Section 4. An induction on $n$ easily reduces the problem to the $n=1$ case; for each $k$, this is an inequality in four real indeterminates. Then by homogeneity we can further reduce to an inequality in just two indeterminates. Nevertheless, giving an SOS-proof of this “two-point inequality” for all $k$ seems to be surprisingly tricky. As an example of the problem we need to solve (the $k=3$ case), the reader is invited to try the following puzzle:

is a sum of squared polynomials in $a$ and $b$.”

Our solution is presented in Section 4.1. Our high level approach is to employ a change of variables which reduces the task to proving a sequence of one-variable real inequalities. This is helpful because every nonnegative univariate polynomial is SOS; hence we can use any mathematical technique to verify the one-variable inequalities. We establish the one-variable inequalities using techniques from computer algebra. Peculiarly, this approach only works for the specific choice $\rho=1-\frac{1}{2k}$; however the proof for general $0\leq\rho\leq 1-\frac{1}{2k}$ can be deduced since the two-point inequality is linear in $\rho$.

2.1 Application to integrality gap instances for 333-Coloring and Vertex-Cover

Along the lines of [BBH+12, OZ13], our SOS proof of the reverse hypercontractive inequality also has applications to integrality gap instances; specifically, for the $3$-Coloring and Vertex-Cover problems. These problems can be put in a common framework by considering the Maximum Independent-Set problem:

Given graph $G=(V,E)$ we define the (fractional) size of its maximum independent set:

There is a one-way connection with $k$-Coloring: any graph $G$ with chromatic number $\chi(G)\leq k$ has $\mathsf{Max}\text{-}\mathsf{IS}(G)\geq 1/k$. There is a two-way connection with the Vertex-Cover problem: a set $S\subseteq V$ is independent if and only if its complement $\overline{S}=V\setminus S$ is a vertex cover (i.e., every $e\in E$ meets $\overline{S}$). Thus $\mathsf{Min}\text{-}\mathsf{VC}(G)$, the minimum (fractional) size of a vertex cover in $G$, is equal to $1-\mathsf{Max}\text{-}\mathsf{IS}(G)$.

Finding the chromatic number or minimum vertex cover of a graph is an $\mathsf{NP}$-hard problem; thus it has been common to seek efficient approximation algorithms. For example, one may seek an efficient algorithm which can $100$-color any $3$-colorable graph, or find a vertex cover of size at most $1.5$ times the minimum. Neither of these problems is known to be polynomial-time solvable; nor is either known to be $\mathsf{NP}$-hard. In fact, the $3$-colorability question shows an enormous gap; we only know an efficient algorithm for $n^{.2111}$-coloring $3$-colorable graphs [ACC06], and $\mathsf{NP}$-hardness of $4$-coloring them [KLS00, GK04]. For Vertex-Cover, there is an easy linear-time $2$-approximation algorithm [GJ79, Gavril 1974], whereas achieving a $1.36$-approximation is known to be $\mathsf{NP}$-hard [DS05].

Based on the $40$-year lack of progress on the algorithms side, it is reasonable to suspect that there is no efficient $(2-\epsilon)$-approximation algorithm for Vertex-Cover. Similarly, one may suspect that there is no efficient algorithm for $O(1)$-coloring $3$-colorable graphs. Indeed, these statements are known to be true assuming the Unique-Games Conjecture in the first case [KR08], and a closely related variant of the Unique-Games Conjecture in the second [DMR09]. However there is reasonable doubt about the Unique-Games Conjecture [ABS10] and it’s important to seek alternative evidence of hardness. One very good form of evidence is showing that strong, generic polynomial-time optimization algorithms fail to give good approximations to the value of the optimal solution. Specifically, one can seek integrality gaps for the canonical hierarchies of linear programming and semidefinite relaxations of the problem. In this work we will often describe integrality gaps in more “proof-theoretic language”. For example, instead of saying that for Vertex-Cover, the complete graph $K_{n}$ is a factor-$\frac{n-1}{n/2}$ integrality gap instance for the linear program, we will say that linear programming “fails to certify $\mathsf{Min}\text{-}\mathsf{VC}(K_{n})>1/2$, even though $\mathsf{Min}\text{-}\mathsf{VC}(K_{n})=(n-1)/n$”.

There is a long line of work on integrality gaps for Chromatic-Number, Independent-Set, and Vertex-Cover. Specific works on integrality gaps for Vertex-Cover include [KG98, Cha02, ABL02, ABLT06, Tou06, FO06, STT07a, STT07b, GMT08, GM08, Sch08, CMM09, Tul09, GMPT10, GM10, BCGM11] (see Georgiou’s thesis [Geo10] for a recent survey), and papers on integrality gaps for $3$-Coloring include [KMS98, KG98, AK98, Cha02, FLS04, AG11]. Furthermore, almost any paper on the Lovász $\vartheta$-Function [Lov79] is implicitly concerned with integrality gaps for these problems.

Both for $3$-Coloring and Vertex-Cover, the integrality gap papers working with the strongest SDP relaxation employ the “Frankl–Rödl graphs” as their hard instances:

The following theorem is essentially due to Frankl and Rödl [FR87] (a few small details are only worked out in [GMPT10]):

whenever $\gamma\geq.1\sqrt{\frac{\log n}{n}}$ and $n$ is sufficiently large.

To obtain our result we need to show an SOS proof for the Frankl–Rödl Theorem. A key ingredient in Frankl and Rödl’s original proof is the vertex isoperimetric inequality on $\{-1,1\}^{n}$, due to Harper. The standard proof of this inequality involves a “shifting” argument which we do not see how to carry out with SOS. However, it is known that inequalities of this type can also be proved using the reverse hypercontractive inequality studied in this paper. In particular, Benabbas, Hatami, and Magen [BHM12] have very recently proven a “density” variation of the Frankl–Rödl Theorem using the reverse hypercontractive inequality. We obtain the SOS proof for the Frankl–Rödl Theorem by combining our SOS proof for the reverse hypercontractive inequality and an SOS version of the Benabbas–Hatami–Magen proof; see Section 5.

Preliminaries

We describe the SOS (Positivstellensatz) proof system of Grigoriev and Vorobjov [GV01] using the notation from the work [OZ13]; for more details, please see that paper.

Finally, when $A=\emptyset$ we will sometimes use the shorthand

which simply means that $p$ is SOS and $\deg(p)\leq k$.

We will use the following facts and lemmas in our SOS proofs. The first one, in particular, we use throughout without comment.

The following fact is a well-known consequence of the Fundamental Theorem of Algebra.

A univariate polynomial $p(x)$ is SOS if it is nonnegative. In other words, we have

It is also well known that for homogeneous polynomials, one can reduce the number of variables by $1$ by “dehomogenizing” the polynomial, getting an SOS representation (if there is one), and rehomogenizing it to get an SOS representation of the original polynomial. Applying this trick to Fact 2.3, we get:

A homogeneous bivariate polynomial $p(x,y)$ is SOS if it is nonnegative.

and each power $(X-c)^{i}$ is either a square or $(X-c)$ times a square. ∎

Since $\tfrac{X^{2k}+Y^{2k}}{2}-\left(\tfrac{X+Y}{2}\right)^{2k}$ is a degree-$2k$ homogeneous polynomial, the claim follows from Fact 2.4: the inequality is indeed true by convexity of $t\mapsto t^{k}$. ∎

The hypercontractive inequality in SOS

As a warmup, we give a simple proof (“in ZFC”) of the $(2,q)$-hypercontractive inequality $\|T_{\rho}f\|_{q}\leq\|f\|_{q}$ for all even integers $q$, which implies Theorem 1.2 for all even integers $q$. As mentioned, we do this under a significantly weakened moment condition:

For a real random variable ${\boldsymbol{x}}_{i}$, the condition is that $\mathop{\bf E\/}[{\boldsymbol{x}}_{i}^{2}]=1$ and

Our proof will show that these moment conditions are sharp; none of them can be relaxed.

By converting to factorials and expanding, one verifies that

By the even moment conditions $\mathop{\bf E\/}[{\boldsymbol{x}}_{1}^{2j}]\leq(2s-1)^{j}{s\choose j}/{{2s}\choose{2j}}$, each summand in (1) is at most the corresponding term in (2) and the proof is complete. ∎

By considering $\epsilon\to 0$ in (1) and (2) it is easy to see for each $j=1,2,\dots,s$ in turn that the associated $s$-moment condition cannot be further relaxed.

Our SOS extension of this result requires the following lemma:

Let $v$ be an even positive integer and let $G_{1},\dots,G_{v},H_{1},\dots,H_{v}$ be indeterminates. Then

The non-SOS proof would be to just apply the AM-GM inequality. For the SOS proof we first trivially write

We then apply the fact that $\vdash_{{2}}XY\leq\tfrac{1}{2}X^{2}+\tfrac{1}{2}Y^{2}$ to each summand to deduce

We are now ready to state and prove the full version of Theorem 1.4.

Let ${\boldsymbol{x}}=({\boldsymbol{x}}_{1},\dots,{\boldsymbol{x}}_{n})$ be a sequence of independent real random variables satisfying the $s$-Moment Conditions. Then

We prove (3) by induction on $n$. The base case, $n=0$, is trivial. For general $n\geq 1$, we can decompose each $f_{i}(x)$ as

Formally, this means introducing the shorthand $h_{i}(x_{1},\dots,x_{n-1})=\sum_{S\not\ni n}\widehat{f_{i}}(S)\prod_{j\in S}x_{i}$, and similarly for $g_{i}$. We also introduce the notation $\boldsymbol{F}_{i}=f_{i}({\boldsymbol{x}})$, $\widetilde{\boldsymbol{F}}_{i}=T_{\rho}f_{i}({\boldsymbol{x}})$ for each $i$, and similarly $\boldsymbol{G}_{i},\widetilde{\boldsymbol{G}}_{i},\boldsymbol{H}_{i},\widetilde{\boldsymbol{H}}_{i}$. Note that these latter four do not depend on ${\boldsymbol{x}}_{n}$. By definition we have $\widetilde{\boldsymbol{F}}_{i}=\rho{\boldsymbol{x}}_{n}\widetilde{\boldsymbol{G}}_{i}+\widetilde{\boldsymbol{H}}_{i}$.

Using the fact that ${\boldsymbol{x}}_{n}$ is independent of all $\boldsymbol{G}_{i}$, $\boldsymbol{H}_{i}$ and has zero odd moments, the left-hand side of (3) can be written as follows:

We apply Lemma 3.3 to each $\mathop{{\textstyle\prod}}_{i\in V}\widetilde{\boldsymbol{G}}_{i}\widetilde{\boldsymbol{H}}_{i}$ (notice that each is multiplied against an SOS polynomial) to obtain

where the second inequality uses the $s$-Moments Condition and the bound on $\rho$, and the third inequality uses the induction hypothesis. (Again, note that each inequality is multiplied against an SOS polynomial.) It is easy to check that $\mathop{\bf E\/}[\boldsymbol{F}_{i}^{2}]=\mathop{\bf E\/}[\boldsymbol{G}_{i}^{2}]+\mathop{\bf E\/}[\boldsymbol{H}_{i}^{2}]$ and so the right-hand side of (3) is simply

Thus to complete the inductive proof, it suffices to show that for each $R\subseteq[s]$, the coefficient on $\prod_{i\in R}\mathop{\bf E\/}[\boldsymbol{G}_{i}^{2}]\prod_{i\in[s]\setminus R}\mathop{\bf E\/}[\boldsymbol{H}_{i}^{2}]$ in (5) is equal to $1$. By symmetry, and taking the sum over $v$ first in (5), it suffices to check that for each $r=|R|=|U\cup T|\in\{0,1,\dots,s\}$ we have

With a modest amount of work it is possible to prove this identity by “traditional” enumerative combinatorics methods; however it is much more efficient to simply use Zeilberger’s algorithm [Zei90, PWZ97]. This algorithm automatically generates the key rational function

Then, writing $t(r,v^{\prime})$ for the expression in the sum on the left-hand side of (6), we have

as can be verified by a trivial calculation. Summing the above equation for $v^{\prime}=0,\dots,r$ shows that $T(r+1)-T(r)=0$, where $T(r)=\sum_{v^{\prime}=0}^{r}t(r,v^{\prime})$. Together with the initial value $T(0)=1$, it follows by induction that $T(r)=1$ for all $r$, as required. ∎

The reverse hypercontractive inequality in SOS

This section is devoted to providing a proof Theorem 1.5, the reverse hypercontractivity in the SOS proof system. More precisely:

For each fixed $k$, we prove Theorem 4.1 by induction on $n$. The $n=1$ base case of the induction is the following $4$-variable inequality:

Proving this base case will be the key challenge; for now, we give the induction which proves Theorem 4.1.

Let $n>1$. Given indeterminates $f(x)$, $g(x)$ for $x\in\{-1,1\}^{n}$, let $f_{0}(x)$ be shorthand for $f(x_{1},\dots,x_{n-1},1)$, let $f_{1}(x)$ be shorthand for $f(x_{1},\dots,x_{n-1},-1)$, and similarly define shorthands $g_{0}$, $g_{1}$. Now

By four applications of induction, we deduce

Now applying the $n=1$ base case of the induction (Theorem 4.2) to the right-hand side of the above we conclude that

Our remaining task is to prove the $4$-variable base case, Theorem 4.2. Let us make a few simplifications. First, we claim it suffices to prove it in the case $\rho=\rho^{*}=1-\frac{1}{2k}$. To see this, note that

is linear in $\rho$. Thus if we can show it is SOS for both $\rho=0$ and $\rho=\rho^{*}$, it follows easily that it is SOS for all $0<\rho<\rho^{*}$. And for $\rho=0$ the task is easy:

by Lemma 2.6. Next, for clarity we make a change of variables; our task becomes showing that for real indeterminates $\mu,\nu,\alpha,\beta$,

Finally, by homogeneity we can reduce the above to proving the following “two-point inequality”:

Suppose we show that $P_{k}(a,b)$ is equal to a sum of squares, say $\sum_{i=1}^{m}R_{i}(a,b)^{2}$ where each $R_{i}(a,b)$ is a bivariate polynomial. Viewing this as an SOS identity in $a$ only, we deduce that $\deg_{a}(R_{i})\leq k$ for each $i$ since $\deg_{a}(P_{k})\leq 2k$ (here $\deg_{a}(R_{i})$ denotes the degree of $R_{i}$ viewed as a univariate polynomial in $a$, and likewise $\deg_{a}(P_{k})$); similarly, $\deg_{b}(R_{i})\leq k$ for each $i$. Then

and in the summation each expression $\mu^{k}\nu^{k}R_{i}(\tfrac{\alpha}{\mu},\tfrac{\beta}{\nu})$ is a polynomial in $\mu,\nu,\alpha,\beta$. ∎

It remains to establish the Two-Point Inequality via an SOS proof.

We remind the reader that there is of course a “ZFC” proof of the Two-Point Inequality, since it follows as a special case of the reverse hypercontractive inequality.

This section is devoted to proving the Two-Point Inequality; i.e., showing $P_{k}(a,b)$ is SOS. After significant trial and error, we were led to the crucial idea of rewriting it under the following substitutions:

Next we use $r^{2}=s^{2}-4t$ to eliminate $r$, obtaining

Now we expand $(s^{2}-4t)^{j}$ in the latter sum so that we can write it as an even polynomial in $s$. We get

In fact that is precisely what we show below, using some computer algebra assistance. We remark, though, that is not a priori clear that this strategy should work; i.e., that $Q_{k,0}(t),\dots,Q_{k,k}(t)$ should be nonnegative. It does not follow from the truth of the Two-Point Inequality. To see this, observe that whereas the Two-Point Inequality is known to hold for any $0\leq\rho\leq\rho^{*}$, it is not true that $Q_{k,0}(t)\geq 0$ for all $0\leq\rho\leq\rho^{*}$. In fact, for $k=1$ we have

which is nonnegative for all $t$ only for the specific choice $\rho^{*}=1-\frac{1}{2k}=\frac{1}{2}$.

Nevertheless, we now complete the proof of the Two-Point Inequality by showing that $Q_{k,0}(t),\dots,Q_{k,k}(t)$ are all nonnegative.

For $k=1$ we have $Q_{1,0}(t)=t^{2}$ (as noted in (9)); henceforth we may assume $k\geq 2$. For $t<0$ we substitute $a=\sqrt{-t}$, $b=-\sqrt{-t}$ into (8); since $s=a+b=0$ we get $P_{k}(\sqrt{-t},-\sqrt{-t})=Q_{k,0}(t)$. By Remark 4.3 we have $P_{k}(\sqrt{-t},-\sqrt{-t})\geq 0$ and hence $Q_{k,0}(t)\geq 0$ for all $t<0$.

Denoting the sum in this expression by $S_{k}(t)$, Zeilberger’s algorithm [Zei90, PWZ97] finds the recurrence equation

valid for all $k\geq 0$. The recurrence can be obtained for example by simply typing the command

SumTools[Hypergeometric][ZeilbergerRecurrence](

binomial(2*k,2*j)*(1-t)^(2*k-2*j)/(1+t)^(2*k)*(-4*t)^j,

into the computer algebra software Maple.

Since the coefficients in this recurrence do not depend on $k$ but only on $t$, the recurrence can be solved in closed form. Together with the initial values $S_{0}(t)=1$ and $S_{1}(t)=\tfrac{t^{2}-6t+1}{(t+1)^{2}}$, it follows that $S_{k}(t)=\cos(4k\arctan(\sqrt{t}))$. (Not every computer algebra system may deliver the solution in this form; however, for the correctness of the proof it is sufficient to check that $\cos(4k\arctan(\sqrt{t}))$ is indeed a solution of the recurrence. This is easy to verify.) Hence,

using the fact that the parenthesized expression is clearly nonnegative. We now split into two cases.

$t\geq\frac{1}{2k(2k-1)}$. In this case we simply use that $\cos(4k\arctan(\sqrt{t}))\geq-1$ to obtain

which is indeed nonnegative when $t\geq\frac{1}{2k(2k-1)}$.

$0\leq t\leq\frac{1}{2k(2k-1)}$. In this case we use the following estimates:

Note that $4k\arctan(\sqrt{t})\leq 4k\sqrt{t}\leq 4k\sqrt{\frac{1}{2k(2k-1)}}$, and the latter quantity is at most $\sqrt{2}$ for all $k\geq 2$. Since $\cos(x)$ is decreasing for $x\in[0,\sqrt{2}]$ we have

It remains to show that $q(t)\geq 0$ for $0\leq t\leq\frac{1}{2k(2k-1)}$. Since $q(t)$ is a quadratic polynomial with negative leading coefficient, we only need to check that $q(0),~{}q(\frac{1}{2k(2k-1)})\geq 0$. We have $q(0)=\left(\tfrac{8}{3}k-4\right)k^{2}$, which is clearly nonnegative for $k\geq 2$. Finally, one may check that

which is evidently nonnegative for $k\geq 2$. ∎

In fact, we will prove the stronger claim that each $Q_{k,i}(t)$ is nonnegative even when $\rho^{*}$ is set to . I.e., we will show that

is nonnegative. To see that this is indeed stronger, simply note that $Q_{k,i}(t)$ and $\widetilde{Q}_{k,i}(t)$ are convex combinations of the same two main quantities, but $\widetilde{Q}_{k,i}(t)$ has less of its “weight” on the first quantity $\tbinom{2k}{2i}(1+t)^{2k-2i}$, which is clearly nonnegative. We will furthermore show that even $\widetilde{Q}_{k,0}(t)\geq 0$.

This is not particularly easy to prove by hand, but using computer assistance yields a compact proof. Using automated guessing [Kau09] one can discover that the following recurrence seems to hold for all integers $0\leq i\leq k$:

The correctness of this recurrence was shown by computing an ideal of annihilating operators for $\widetilde{Q}_{k,i}(t)$ from the sum definition using creative telescoping and holonomic closure properties, and then showing by a Gröbner basis computation that the guessed recurrence belongs to this ideal. A detailed description of this calculation would lead a bit to far, the interested reader is referred to [Kou13, Kau13, Kau14] for recent introductions to the relevant computational techniques and the algebraic theory behind them.

The Frankl-Rödl Theorem in SOS

We prove Theorem 5.1 by “SOS-izing” the Benabbas–Hatami–Magen Fourier-theoretic proof [BHM12] of the following “density” version of the Frankl–Rödl Theorem:

Here the $o_{n}(1)$ goes to rather slowly in $n$, which means that the Benabbas–Hatami–Magen proof only recovers the Frankl–Rödl Theorem for $\gamma>\omega(\frac{1}{\log n})$. This is due to comparison between the $T_{d}$ and $S_{d}$ operators described below; it seems possible that some additional technical work would allow for smaller values of $\gamma$.

Benabbas, Hatami, and Magen [BHM12] introduce the following operator:

The key technical contribution of [BHM12] is showing how to pass between the $S_{d}$ operators (which are relevant for Frankl–Rödl analysis) and the $T_{\rho}$ operators (for which we have reverse hypercontractivity). Intuitively, the operators $S_{d}$ and $T_{1-2d/n}$ should be similar (at least if $d/n$ is bounded away from and $1$). However there is one caveat: “parity” issues with $S_{d}$. For example, if $f:\{-1,1\}^{n}\to\{0,1\}$ is the indicator of the strings of even Hamming weight, then

Benabbas, Hatami, and Magen evade this parity issue by considering the operator $\tfrac{1}{2}S_{d}+\tfrac{1}{2}S_{d+1}$.

For integer $0\leq d<n$, we define the operator $S_{d}^{\prime}=\tfrac{1}{2}S_{d}+\tfrac{1}{2}S_{d+1}$.

The crucial theorem in [BHM12]’s work is the following:

where each real number $\delta(U)$ satisfies

Given Theorem 5.5, Benabbas, Hatami, and Magen are able to deduce their main Theorem 5.2 from the reverse hypercontractivity result Theorem 1.3 without too much trouble. We now show that this deduction can also be carried out in the SOS proof system. Specifically, we give here the proof of our Theorem 5.1, relying on the SOS proof of hypercontractivity (Theorem 4.1) from Section 4.

Write $d=(1-\gamma)n$ (where $\frac{1}{\log n}\leq\gamma\leq\frac{1}{4}$) and write $\rho^{\prime}=1-2d/n=-(1-2\gamma)$. For $i=0,1$ let us denote

because if $x$’s Hamming weight has the same parity as $y$’s then their distance can only be $d$ (an even integer) not $d+1$ (an odd one). Using Theorem 5.5 it follows that

(with the second bound using $\gamma\geq\frac{1}{\log n}$.) We now write $g_{i}(x)$ to denote $f_{i}(-x)$ and also $\rho=-\rho^{\prime}=1-2\gamma$; then

We have $f(x)^{2}=f(x)\vdash_{{2k}}f(x)^{2k}=f(x)$, from which we may easily deduce

Since $\rho=1-2\gamma\leq 1-\frac{1}{2k}$ we may apply our reverse hypercontractivity result Theorem 4.1 (in Section 4) to deduce

We’re now almost done. First, $\mathop{\bf E\/}[f_{i}]=\mathop{\bf E\/}[g_{i}]$ formally for each $i=0,1$. Second, for simplicity we use the bound

where the second inequality is Lemma 2.6. Finally, from Lemma 2.5 we may deduce

for $C$ sufficiently large, using our upper bound on $\delta$. Combining the previous two statements we can get

Conclusions

We describe here a few questions left open by our work. Regarding reverse hypercontractivity, it seems we may not have given the Book proof of the SOS Two-Point Inequality. We would be happy to see a more elegant “human proof”, but even more interesting would be a computer algebra technique that could automatically prove SOS-ness, symbolically for all $k$.

The authors would like to thank Siavosh Benabbas and Hamed Hatami for the advance copy of [BHM12]. Proposition 4.5 was independently proven by Fedor Nazarov; we are very grateful to him for sharing his proof with us. Thanks also to Rajsekar Manokaran, Toni Pitassi, and Doron Zeilberger for helpful discussions.

References

Appendix A Solution to the puzzle