# On the integrality gap of the maximum-cut semidefinite-programming
relaxation in fixed dimension

Fernando Mário de Oliveira Filho  F.M. de Oliveira Filho, Delft Institute of
Applied Mathematics, Delft University of Technology, Van Mourik Broekmanweg 6,
2628 XE Delft, The Netherlands<EMAIL_ADDRESS>and  Frank Vallentin  F.
Vallentin, Mathematisches Institut, Universität zu Köln, Weyertal 86–90, 50931
Köln, Germany<EMAIL_ADDRESS>
(Date: 9 March 2020)

###### Abstract.

We describe a factor-revealing convex optimization problem for the integrality
gap of the maximum-cut semidefinite-programming relaxation: for each $n\geq 2$
we present a convex optimization problem whose optimal value is the largest
possible ratio between the value of an optimal rank-$n$ solution to the
relaxation and the value of an optimal cut. This problem is then used to
compute lower bounds for the integrality gap.

###### 2010 Mathematics Subject Classification:

46N10, 68W25, 90C22

This project has received funding from the European Union’s Horizon 2020
research and innovation programme under the Marie Skłodowska-Curie agreement
No 764759. The second author is partially supported by the SFB/TRR 191
“Symplectic Structures in Geometry, Algebra and Dynamics” and by the project
“Spectral bounds in extremal discrete geometry” (project number 414898050),
both funded by the DFG

##  1\. Introduction

For $x$, $y\in\mathbb{R}^{n}$, write $x\cdot y=x_{1}y_{1}+\cdots+x_{n}y_{n}$
for the Euclidean inner product. Let $S^{n-1}=\\{\,x\in\mathbb{R}^{n}:x\cdot
x=1\,\\}$ be the $(n-1)$-dimensional unit sphere. Given a nonempty finite set
$V$, a nonnegative matrix $A\in\mathbb{R}^{V\times V}$, and an integer $n\geq
1$, write

$\operatorname{SDP}_{n}(A)=\max\biggl{\\{}\,\sum_{x,y\in V}A(x,y)(1-f(x)\cdot
f(y)):f\colon V\to S^{n-1}\,\biggr{\\}}.$ (1)

Replacing $S^{n-1}$ above by $S^{\infty}$, the set of all sequences $(a_{k})$
such that $\sum_{k=0}^{\infty}a_{k}^{2}=1$, we obtain the definition of
$\operatorname{SDP}_{\infty}(A)$.

Given a finite (loopless) graph $G=(V,E)$ and a nonnegative weight function
$w\colon E\to\mathbb{R}_{+}$ on the edges of $G$, the maximum-cut problem asks
for a set $S\subseteq V$ that maximizes the weight

$\sum_{e\in\delta(S)}w(e)=\sum_{\begin{subarray}{c}x\in S,y\in V\setminus S\\\
xy\in E\end{subarray}}w(xy)$

of the cut $\delta(S)=\\{\,e\in E:|e\cap S|=1\,\\}$. If $A\colon V\times
V\to\mathbb{R}$ is the matrix such that $A(x,y)=w(xy)$ when $xy\in E$ and
$A(x,y)=0$ otherwise, then the weight of a maximum cut is
$(1/4)\operatorname{SDP}_{1}(A)$.

$\operatorname{SDP}_{n}(A)$ is actually the optimal value of a semidefinite-
programming problem with a rank constraint, namely

${\begin{array}[]{r@{\ }l@{\quad}l}\text{max}&\sum_{x,y\in
V}A(x,y)(1-M(x,y))\\\ &M(x,x)=1\quad\text{for~{}$x\in V$},\\\
&\text{$M\in\mathbb{R}^{V\times V}$ is positive semidefinite and has rank at
most~{}$n$.}\end{array}}$ (2)

In $\operatorname{SDP}_{\infty}(A)$ the rank constraint is simply dropped. The
optimization problem $\operatorname{SDP}_{\infty}(A)$ is the semidefinite-
programming relaxation of the maximum-cut problem.

Obviously, $\operatorname{SDP}_{\infty}(A)\geq\operatorname{SDP}_{1}(A)$. In a
fundamental paper, Goemans and Williamson [8] showed that, if $A$ is a
nonnegative matrix, then

$\operatorname{SDP}_{1}(A)\geq\alpha_{\mathrm{GW}}\operatorname{SDP}_{\infty}(A),$

where

$\alpha_{\mathrm{GW}}=\min_{t\in[-1,1]}\frac{1-(2/\pi)\arcsin
t}{1-t}=0.87856\ldots.$

The $n$-dimensional integrality gap of the semidefinite-programming relaxation
is

$\gamma_{n}=\sup\Bigl{\\{}\,\frac{\operatorname{SDP}_{n}(A)}{\operatorname{SDP}_{1}(A)}:\text{$A$
is a nonnegative matrix}\,\Bigr{\\}},$

but it is often more natural to work with its reciprocal
$\alpha_{n}=\gamma_{n}^{-1}$. Goemans and Williamson thus showed that
$\alpha_{\infty}\geq\alpha_{\mathrm{GW}}$; Feige and Schechtman [7] later
showed that $\alpha_{\infty}=\alpha_{\mathrm{GW}}$ (see also §8.3 in Gärtner
and Matoušek [9]).

In dimension 2 it is known that

$\alpha_{2}=\frac{32}{25+5\sqrt{5}}=0.88445\ldots.$ (3)

The ‘$\leq$’ direction was shown by Delorme and Poljak [4, 5]; the ‘$\geq$’
direction was shown by Goemans in an unpublished note (cf. Avidor and Zwick
[2], who also provide another proof of this result). Avidor and Zwick [2]
showed that $\alpha_{3}\geq 0.8818$. Except for $n=2$ and 3, it is an open
problem whether $\alpha_{n}>\alpha_{\infty}=\alpha_{\mathrm{GW}}$.

###  1.1. A factor-revealing optimization problem

Theorem 1.1 below gives a factor-revealing optimization problem for
$\alpha_{n}$: an optimization problem defined for each $n\geq 2$ whose optimal
value is $\alpha_{n}$. Relaxations of it can be solved by computer to give
upper bounds for $\alpha_{n}$, as done in §4.

For a finite and nonempty set $U$, write

$\operatorname{CUT_{\square}}(U)=\operatorname{conv}\\{\,f\otimes
f^{*}:f\colon U\to\\{-1,1\\}\,\\},$

where $f\otimes f^{*}$ is the external product of the vector $f$, that is, the
matrix whose entry $(x,y)$ is $f(x)f(y)$. This set is known as the cut
polytope and was extensively investigated [6].

A kernel is a square-integrable (with respect to the Lebesgue measure) real-
valued function on $S^{n-1}\times S^{n-1}$; the set of continuous kernels is
denoted by $C(S^{n-1}\times S^{n-1})$. Write

$\operatorname{CUT_{\square}}(S^{n-1})=\\{\,K\in C(S^{n-1}\times
S^{n-1}):\bigl{(}K(x,y)\bigr{)}_{x,y\in
U}\in\operatorname{CUT_{\square}}(U)\\\ \text{for every finite and
nonempty~{}$U\subseteq S^{n-1}$}\,\\}.$

In principle, it is not clear that anything other than the constant 1 kernel
is in $\operatorname{CUT_{\square}}(S^{n-1})$. If $f\colon
S^{n-1}\to\\{-1,1\\}$ is any nonconstant measurable function, then one could
be tempted to say that $(x,y)\mapsto f(x)f(y)$ is in
$\operatorname{CUT_{\square}}(S^{n-1})$, but no such kernel is continuous, so
to see that $\operatorname{CUT_{\square}}(S^{n-1})$ is nontrivial requires a
more complicated argument. Fix $e\in S^{n-1}$ and let $f(x)$ be $1$ if $e\cdot
x\geq 0$ and $-1$ otherwise; let $K(x,y)=(2/\pi)\arcsin x\cdot y$ for every
$x$, $y\in S^{n-1}$. Grothendieck’s identity says that

$K(x,y)=\int_{\mathrm{O}(n)}f(Tx)f(Ty)\,d\mu(T),$

where $\mathrm{O}(n)$ is the group of $n\times n$ orthogonal matrices and
$\mu$ is the Haar measure on $\mathrm{O}(n)$ normalized so the total measure
is 1. Then it is easy to see that $K$ is continuous and that it belongs to
$\operatorname{CUT_{\square}}(S^{n-1})$. This kernel was first considered by
McMillan [12], who was perhaps the first to use such an infinite-dimensional
analogue of the cut polytope.

We say that a kernel $K$ is invariant if $K(Tx,Ty)=K(x,y)$ for all
$T\in\mathrm{O}(n)$ and $x$, $y\in S^{n-1}$. An invariant kernel is in fact a
univariate function, since the value of $K(x,y)$ depends only on the inner
product $x\cdot y$. Hence for $t\in[-1,1]$ we write $K(t)$ for the common
value taken by $K$ on pairs $(x,y)$ with inner product $t$.

######  Theorem 1.1.

If $n\geq 2$, then $\alpha_{n}$ is the optimal value of

${\begin{array}[]{r@{\ }l@{\quad}l}\sup&\alpha\\\
&1-K(t)\geq\alpha(1-t)\quad\text{for all~{}$t\in[-1,1]$},\\\
&\text{$K\in\operatorname{CUT_{\square}}(S^{n-1})$ is invariant}.\end{array}}$
(4)

This theorem is similar to the integral representation for the Grothendieck
constant [14, Theorem 3.4]. The easy direction is to show that the optimal
value of (4) is at most $\alpha_{n}$.

###### Proof of the easy direction of Theorem 1.1.

Let $(K,\alpha)$ be a feasible solution of (4) and let
$A\in\mathbb{R}^{V\times V}$ be any nonnegative matrix and $f\colon V\to
S^{n-1}$ be a function achieving the maximum in $\operatorname{SDP}_{n}(A)$.
Note $\bigl{(}K(f(x),f(y))\bigr{)}_{x,y\in
V}\in\operatorname{CUT_{\square}}(V)$. This implies that there are nonnegative
numbers $\lambda_{1}$, …, $\lambda_{r}$ that sum up to 1 and functions
$f_{1}$, …, $f_{r}\colon V\to\\{-1,1\\}$ such that

$K(f(x),f(y))=K(f(x)\cdot
f(y))=\lambda_{1}f_{1}(x)f_{1}(y)+\cdots+\lambda_{r}f_{r}(x)f_{r}(y)$

for all $x$, $y\in V$. But then

$\begin{split}\operatorname{SDP}_{1}(A)&\geq\sum_{k=1}^{r}\lambda_{k}\sum_{x,y\in
V}A(x,y)(1-f_{k}(x)f_{k}(y))\\\ &=\sum_{x,y\in V}A(x,y)(1-K(f(x)\cdot
f(y)))\\\ &\geq\alpha\sum_{x,y\in V}A(x,y)(1-f(x)\cdot f(x))\\\
&=\alpha\operatorname{SDP}_{n}(A),\end{split}$

so $\alpha\leq\alpha_{n}$. ∎

A proof that the optimal value of (4) is at least $\alpha_{n}$ is given in §2,
but it works only for $n\geq 3$. For $n=2$ a direct proof can be given by
showing a feasible solution of (4) with objective value $\alpha_{2}$; this was
done, in a different language, by Avidor and Zwick [2] and is outlined in §3,
where a short discussion on how lower bounds for $\alpha_{n}$ can be found is
also presented.

Notice that the optimization problem (4) is infinite: the kernel $K$ lies in
an infinite-dimensional space and must satisfy infinitely many constraints,
not to mention that the separation problem over
$\operatorname{CUT_{\square}}(U)$ is NP-hard since the maximum-cut problem is
NP-hard [10]. In §4 we will see how $K$ can be parameterized and how the
problem can be relaxed (by relaxing the constraint that $K$ must be in
$\operatorname{CUT_{\square}}(S^{n-1})$) and effectively discretized so it can
be solved by computer, providing us with upper bounds for $\alpha_{n}$. From
feasible solutions of this relaxation, instances with large integrality gap
can be constructed, as shown in §4.1.

##  2\. Proof of Theorem 1.1 for $n\geq 3$

The difficult part of the proof is to show that the optimal value of (4) is at
least $\alpha_{n}$. This is done here for $n\geq 3$, and for this we need a
few lemmas.

Let $\mu$ be the Haar measure on the orthogonal group $\mathrm{O}(n)$,
normalized so the total measure is 1. The Reynolds operator $R$ projects a
kernel $K$ onto the space of invariant kernels by averaging:

$R(K)(x,y)=\int_{\mathrm{O}(n)}K(Tx,Ty)\,d\mu(T)$

for all $x$, $y\in S^{n-1}$. If $K$ is a continuous kernel, then so is $R(K)$
[3, Lemma 5.4], and if $f\in L^{2}(S^{n-1})$, then $R(f\otimes f^{*})$ is
continuous [3, Lemma 5.5], where $f\otimes f^{*}$ is the kernel mapping
$(x,y)$ to $f(x)f(y)$.

A function $f\colon S^{n-1}\to\mathbb{R}$ respects a partition $\mathcal{P}$
of $S^{n-1}$ if $f$ is constant on each $X\in\mathcal{P}$; we write $f(X)$ for
the common value of $f$ in $X$.

######  Lemma 2.1.

If $n\geq 2$, then for every $\eta>0$ there is a partition $\mathcal{P}$ of
$S^{n-1}$ into finitely many measurable sets such that for every finite set
$I\subseteq[-1,1]$ and every nonnegative function $z\colon I\to\mathbb{R}$
there is a function $f\colon S^{n-1}\to\\{-1,1\\}$ that respects $\mathcal{P}$
and satisfies

$\sum_{t\in I}z(t)(1-R(f\otimes f^{*})(t))\geq\sum_{t\in
I}z(t)(\alpha_{n}(1-t)-\eta).$ (5)

###### Proof.

Let $\mathcal{P}$ be any partition of $S^{n-1}$ into finitely many measurable
sets of small enough diameter such that for all $X$, $Y\in\mathcal{P}$, $x$,
$x^{\prime}\in X$, and $y$, $y^{\prime}\in Y$, we have $|x\cdot
y-x^{\prime}\cdot y^{\prime}|\leq\alpha_{n}^{-1}\eta$. Such a partition can be
obtained by considering e.g. the Voronoi cell of each point of an
$\epsilon$-net for $S^{n-1}$ for small enough $\epsilon$.

For $u\in S^{n-1}$ and $X\in\mathcal{P}$, write

$[u,X]=\\{\,T\in\mathrm{O}(n):Tu\in X\,\\}.$

Then $[u,X]$ is measurable [11, Theorem 3.7], so
$\\{\,[u,X]:X\in\mathcal{P}\,\\}$ is a partition of $\mathrm{O}(n)$ into
measurable sets, and hence for any $u$, $v\in S^{n-1}$ so is the common
refinement

$\\{\,[u,X]\cap[v,Y]:\text{$(X,Y)\in\mathcal{P}\times\mathcal{P}$ and
$[u,X]\cap[v,Y]\neq\emptyset$}\,\\}.$

Write $u=(1,0,\ldots,0)\in S^{n-1}$ and for $t\in[-1,1]$ let
$v_{t}=(t,(1-t^{2})^{1/2},0,\ldots,0)$, so $u\cdot v_{t}=t$. If $f\colon
S^{n-1}\to\mathbb{R}$ respects $\mathcal{P}$, then for every finite
$I\subseteq[-1,1]$ and every nonnegative $z\colon I\to\mathbb{R}$ we have

$\begin{split}\sum_{t\in I}z(t)(1-R(f\otimes f^{*})(t))&=\sum_{t\in
I}z(t)\int_{\mathrm{O}(n)}1-f(Tu)f(Tv_{t})\,d\mu(T)\\\ &=\sum_{t\in
I}z(t)\sum_{X,Y\in\mathcal{P}}\int_{[u,X]\cap[v_{t},Y]}1-f(Tu)f(Tv_{t})\,d\mu(T)\\\
&=\sum_{t\in
I}z(t)\sum_{X,Y\in\mathcal{P}}(1-f(X)f(Y))\mu([u,X]\cap[v_{t},Y])\\\
&=\sum_{X,Y\in\mathcal{P}}(1-f(X)f(Y))\sum_{t\in
I}z(t)\mu([u,X]\cap[v_{t},Y]).\end{split}$

By considering the matrix
$A_{z}\colon\mathcal{P}\times\mathcal{P}\to\mathbb{R}$ such that

$A_{z}(X,Y)=\sum_{t\in I}z(t)\mu([u,X]\cap[v_{t},Y]),$ (6)

we see that finding a function $f\colon S^{n-1}\to\\{-1,1\\}$ that respects
$\mathcal{P}$ and maximizes the left-hand side of (5) is the same as finding
an optimal solution of $\operatorname{SDP}_{1}(A_{z})$, so there is such a
function $f$ satisfying

$\sum_{t\in I}z(t)(1-R(f\otimes f^{*})(t))=\operatorname{SDP}_{1}(A_{z}).$ (7)

Now let $g\colon\mathcal{P}\to S^{n-1}$ be such that $g(X)=x$ for some $x\in
X$ chosen arbitrarily. Recall that the sets in $\mathcal{P}$ have small
diameter, so

$\begin{split}\operatorname{SDP}_{n}(A_{z})&\geq\sum_{X,Y\in\mathcal{P}}A_{z}(X,Y)(1-g(X)\cdot
g(Y))\\\ &=\sum_{t\in I}z(t)\sum_{X,Y\in\mathcal{P}}(1-g(X)\cdot
g(Y))\mu([u,X]\cap[v_{t},Y])\\\ &=\sum_{t\in
I}z(t)\sum_{X,Y\in\mathcal{P}}\int_{[u,X]\cap[v_{t},Y]}1-g(X)\cdot
g(Y)\,d\mu(T)\\\ &\geq\sum_{t\in
I}z(t)\sum_{X,Y\in\mathcal{P}}\int_{[u,X]\cap[v_{t},Y]}1-(Tu)\cdot(Tv_{t})-\alpha_{n}^{-1}\eta\,d\mu(T)\\\
&=\sum_{t\in I}z(t)\int_{\mathrm{O}(n)}1-t-\alpha_{n}^{-1}\eta\,d\mu(T)\\\
&=\sum_{t\in I}z(t)((1-t)-\alpha_{n}^{-1}\eta).\end{split}$

Now take any finite $I\subseteq[-1,1]$ and any nonnegative $z\colon
I\to\mathbb{R}$. If $f$ is a function that respects $\mathcal{P}$ and for
which (7) holds, then

$\sum_{t\in I}z(t)(1-R(f\otimes
f^{*})(t))=\operatorname{SDP}_{1}(A_{z})\geq\alpha_{n}\operatorname{SDP}_{n}(A_{z})\geq\sum_{t\in
I}z(t)(\alpha_{n}(1-t)-\eta),$

as we wanted. ∎

Lemma 2.1 is enough to show the following weaker version of the difficult
direction of Theorem 1.1:

######  Lemma 2.2.

If $n\geq 2$ and $1\geq\delta>0$, then the optimal value of the optimization
problem

${\begin{array}[]{r@{\ }l@{\quad}l}\sup&\alpha\\\
&1-K(t)\geq\alpha(1-t)\quad\text{for all~{}$t\in[-1,1-\delta]$},\\\
&\text{$K\in\operatorname{CUT_{\square}}(S^{n-1})$ is invariant}\end{array}}$
(8)

is at least $\alpha_{n}$.

###### Proof.

Fix $\eta>0$ and let $\mathcal{P}$ be a partition supplied by Lemma 2.1. Let
$\mathcal{F}$ be the set of all functions $f\colon S^{n-1}\to\\{-1,1\\}$ that
respect $\mathcal{P}$; note $\mathcal{F}$ is finite.

Let $I_{1}\subseteq I_{2}\subseteq\cdots$ be a sequence of finite nonempty
subsets of $[-1,1]$ whose union is the set of all rational numbers in
$[-1,1]$. Suppose there is no $m_{k}\colon\mathcal{F}\to\mathbb{R}$ satisfying

$\begin{split}&\sum_{f\in\mathcal{F}}(1-R(f\otimes
f^{*})(t))m_{k}(f)\geq\alpha_{n}(1-t)-\eta\qquad\text{for all~{}$t\in
I_{k}$},\\\ &\sum_{f\in\mathcal{F}}m_{k}(f)=1,\\\ &m_{k}\geq 0.\end{split}$

Farkas’s lemma [16, §7.3] says that, if this system has no solution, then
there is $z\colon I_{k}\to\mathbb{R}$, $z\geq 0$, and $\rho\in\mathbb{R}$ such
that

$\begin{split}&\rho+\sum_{t\in I_{k}}z(t)(1-R(f\otimes f^{*})(t))\leq
0\qquad\text{for all~{}$f\in\mathcal{F}$},\\\ &\rho+\sum_{t\in
I_{k}}z(t)(\alpha_{n}(1-t)-\eta)>0.\end{split}$

Together, these inequalities imply that for every $f\in\mathcal{F}$ we have

$\sum_{t\in I_{k}}z(t)(1-R(f\otimes f^{*})(t))<\sum_{t\in
I_{k}}z(t)(\alpha_{n}(1-t)-\eta),$

a contradiction to the choice of $\mathcal{P}$.

Since all $m_{k}$ lie in $[0,1]^{\mathcal{F}}$, which is a compact set, the
sequence $(m_{k})$ has a converging subsequence; say this subsequence
converges to $m\colon\mathcal{F}\to\mathbb{R}$. Then $m\geq 0$ and
$\sum_{f\in\mathcal{F}}m(f)=1$. Moreover,

$\sum_{f\in\mathcal{F}}(1-R(f\otimes
f^{*})(t))m(f)\geq\alpha_{n}(1-t)-\eta\qquad\text{for all~{}$t\in[-1,1]$}.$
(9)

Indeed, the inequality holds for all $t\in[-1,1]\cap\mathbb{Q}$. But
$R(f\otimes f^{*})$ is continuous for every $f$, so the left-hand side above
is a continuous function of $t$, whence the inequality holds for every
$t\in[-1,1]$.

Fix $1\geq\delta>0$ and $\epsilon>0$ and set $\eta=\alpha_{n}\epsilon\delta$;
let $m$ be such that (9) holds. If $t\leq 1-\delta$, then $1-t\geq\delta$ and

$(1-\epsilon)(1-t)=(1-t)-\epsilon(1-t)\leq(1-t)-\epsilon\delta.$

So, for $t\in[-1,1-\delta]$, the left-hand side of (9) is at least

$\alpha_{n}(1-t)-\eta=\alpha_{n}((1-t)-\alpha_{n}^{-1}\eta)\geq\alpha_{n}(1-\epsilon)(1-t).$

Now $K_{\epsilon}=\sum_{f\in\mathcal{F}}R(f\otimes f^{*})m(f)$ is a continuous
kernel that moreover belongs to $\operatorname{CUT_{\square}}(S^{n-1})$. So
for every $\epsilon>0$ there is
$K_{\epsilon}\in\operatorname{CUT_{\square}}(S^{n-1})$ such that
$(K_{\epsilon},\alpha_{n}(1-\epsilon))$ is a feasible solution of (8), and by
letting $\epsilon$ approach 0 we are done. ∎

For $n\geq 3$, Theorem 1.1 can be obtained from Lemma 2.2 by using the
following lemma.

######  Lemma 2.3.

For every $n\geq 3$, there is $1\geq\delta>0$ such that if $(K,\alpha)$ is any
feasible solution of (8), then

$1-K(t)\geq\alpha(1-t)\qquad\text{for all~{}$t\in[1-\delta,1]$.}$

The proof of this lemma uses some properties of Jacobi polynomials, and goes
through only for $n\geq 3$. A proof of Theorem 1.1 for $n=2$ is given in §3.

The Jacobi polynomials111See for example the book by Szegö [17] for background
on orthogonal polynomials. with parameters $(\alpha,\beta)$, $\alpha$,
$\beta>-1$, are the orthogonal polynomials with respect to the weight function
$(1-t)^{\alpha}(1+t)^{\beta}$ on the interval $[-1,1]$. We denote the Jacobi
polynomial with parameters $(\alpha,\beta)$ and degree $k$ by
$P_{k}^{(\alpha,\beta)}$ and normalize it so $P_{k}^{(\alpha,\beta)}(1)=1$.

A continuous kernel $K\colon S^{n-1}\times S^{n-1}\to\mathbb{R}$ is positive
if $\bigl{(}K(x,y)\bigr{)}_{x,y\in U}$ is positive semidefinite for every
finite and nonempty set $U\subseteq S^{n-1}$. Schoenberg [15] characterizes
continuous, positive, and invariant kernels via their expansions in terms of
Jacobi polynomials:

######  Theorem 2.4 (Schoenberg’s theorem).

A kernel $K\colon S^{n-1}\times S^{n-1}\to\mathbb{R}$ is continuous, positive,
and invariant if and only if there are numbers $a_{k}\geq 0$ satisfying
$\sum_{k=0}^{\infty}a_{k}<\infty$ such that

$K(x,y)=\sum_{k=0}^{\infty}a_{k}P_{k}^{(\nu,\nu)}(x\cdot y)\qquad\text{for
all~{}$x$, $y\in S^{n-1}$}$

with absolute and uniform convergence, where $\nu=(n-3)/2$.

Schoenberg’s theorem is used in the proof of Lemma 2.3 and again in §§3 and 4.

###### Proof of Lemma 2.3.

Fix $n\geq 3$ and set $\nu=(n-3)/2$. Claim: there is $1\geq\delta>0$ such that
$t=P_{1}^{(\nu,\nu)}(t)\geq P_{k}^{(\nu,\nu)}(t)$ for all $k\geq 2$ and
$t\in[1-\delta,1]$.

The lemma quickly follows from this claim. Indeed, say $(K,\alpha)$ is
feasible for (8). Since every matrix in $\operatorname{CUT_{\square}}(U)$ for
finite $U$ is positive semidefinite, every kernel in
$\operatorname{CUT_{\square}}(S^{n-1})$ is positive. Hence using Schoenberg’s
theorem we write

$K(t)=\sum_{k=0}^{\infty}a_{k}P_{k}^{(\nu,\nu)}(t)\qquad\text{for
all~{}$t\in[-1,1]$}.$

Since $K\in\operatorname{CUT_{\square}}(S^{n-1})$, we have $K(1)=1$, so
$\sum_{k=0}^{\infty}a_{k}=1$.

As $(K,\alpha)$ is a feasible solution of (8), we know that

$1-K(-1)\geq\alpha(1-(-1))=2\alpha.$

Now $|P_{k}^{(\nu,\nu)}(t)|\leq 1$ for all $k$ and all $t\in[-1,1]$, so
$K(-1)\geq a_{0}-(1-a_{0})$, whence $a_{0}\leq 1-\alpha$. The claim implies
that, if $t\in[1-\delta,1]$, then

$K(t)\leq a_{0}+(1-a_{0})t,$

so for $t\in[1-\delta,1]$ we have

$1-K(t)\geq 1-a_{0}-(1-a_{0})t=1-t-a_{0}(1-t)\geq
1-t-(1-\alpha)(1-t)=\alpha(1-t),$

as we wanted.

To prove the claim, we use the following integral representation of Feldheim
and Vilenkin for the Jacobi polynomials: for $\nu\geq 0$,

$P_{k}^{(\nu,\nu)}(\cos\theta)=\frac{2\Gamma(\nu+1)}{\Gamma(1/2)\Gamma(\nu+1/2)}\int_{0}^{\pi/2}\cos^{2\nu}\phi(1-\sin^{2}\theta\cos^{2}\phi)^{k/2}\\\
\cdot
P_{k}^{(-1/2,-1/2)}(\cos\theta(1-\sin^{2}\theta\cos^{2}\phi)^{-1/2})\,d\phi.$
(10)

This formula is adapted to our normalization of the Jacobi polynomials from
Corollary 6.7.3 in the book by Andrews, Askey, and Roy [1]; see also equation
(3.23) in the thesis by Oliveira [13].

For fixed $\theta$ and $\phi$, the function
$k\mapsto(1-\sin^{2}\theta\cos^{2}\phi)^{k/2}$ is monotonically decreasing.
Write $t=\cos\theta$ and recall that the Jacobi polynomials are bounded by 1
in $[-1,1]$; plug $k=2$ in the right-hand side of (10) to get

$P_{k}^{(\nu,\nu)}(t)\leq\frac{2\Gamma(\nu+1)}{\Gamma(1/2)\Gamma(\nu+1/2)}\int_{0}^{\pi/2}\cos^{2\nu}\phi(1-(1-t^{2})\cos^{2}\phi)\,d\phi$
(11)

for all $t\in[0,1]$ and $k\geq 2$. For $\nu=(n-3)/2$ with $n\geq 4$, we show
that there is $\delta>0$ such that the right-hand side above is at most $t$
for all $t\in[1-\delta,1]$; the case $n=3$ will be dealt with shortly.

Let $m\geq 2$ be an integer. Write $\cos^{m}\phi=\cos^{m-1}\phi\cos\phi$ and
use integration by parts to get

$m\int_{0}^{\pi/2}\cos^{m}\phi\,d\phi=(m-1)\int_{0}^{\pi/2}\cos^{m-2}\phi\,d\phi.$

It follows by induction on $m$ that, if $\nu=(n-3)/2$ with $n\geq 3$, then

$\int_{0}^{\pi/2}\cos^{2\nu}\phi\,d\phi=\frac{\Gamma(1/2)\Gamma(\nu+1/2)}{2\Gamma(\nu+1)}.$
(12)

The right-hand side of (11) is a degree-2 polynomial on $t$; let us denote it
by $p_{\nu}$. Use (12) to get

$p_{\nu}(t)=\frac{2\nu+1}{2(\nu+1)}t^{2}+\frac{1}{2(\nu+1)}.$

It is then a simple matter to check that, for $\nu=(n-3)/2$ with $n\geq 4$,
there is $\delta>0$ such that $p_{\nu}(t)\leq t$ for all $t\in[1-\delta,1]$.

For $n=3$ and hence $\nu=0$, we have $p_{\nu}(t)\geq t$ for all $t\in[0,1]$.
In this case, we may take $k=4$ in (10) and follow the same reasoning, proving
that the degree 4 polynomial obtained will have the desired property. It then
only remains to show that $P_{2}^{(0,0)}$ and $P_{3}^{(0,0)}$ are below
$P_{1}^{(0,0)}$ for $t$ close enough to 1, and this can be done directly. ∎

All that is left to do is to put it all together.

###### Proof of Theorem 1.1 for $n\geq 3$.

In §1.1 we have seen that the optimal value of (4) is at most $\alpha_{n}$.
The reverse inequality follows from Lemmas 2.2 and 2.3 put together. ∎

##  3\. Lower bounds for $\alpha_{n}$ and a proof of Theorem 1.1 for $n=2$

To get a lower bound for $\alpha_{n}$, one needs to show a feasible solution
of (4). One such feasible solution, that shows that
$\alpha_{n}\geq\alpha_{\mathrm{GW}}$, is
$(K_{\mathrm{GW}},\alpha_{\mathrm{GW}})$ with

$K_{\mathrm{GW}}(x\cdot y)=(2/\pi)\arcsin x\cdot y.$ (13)

We encountered this kernel in the introduction. Fix $e\in S^{n-1}$ and let
$f_{\mathrm{GW}}\colon S^{n-1}\to\\{-1,1\\}$ be such that
$f_{\mathrm{GW}}(x)=1$ if $e\cdot x\geq 0$ and $-1$ otherwise. Recall that
Grothendieck’s identity is

$K_{\mathrm{GW}}(x\cdot y)=R(f_{\mathrm{GW}}\otimes
f_{\mathrm{GW}}^{*})(x\cdot y),$

whence in particular
$K_{\mathrm{GW}}\in\operatorname{CUT_{\square}}(S^{n-1})$.

Let $t_{\mathrm{GW}}\in[-1,1]$ be such that
$\alpha_{\mathrm{GW}}=(1-K_{\mathrm{GW}}(t_{\mathrm{GW}}))/(1-t_{\mathrm{GW}})$;
then $t_{\mathrm{GW}}=-0.68918\ldots$. The easy direction of the following
result is implicit in the work of Avidor and Zwick [2].

######  Theorem 3.1.

If $n\geq 2$, then $\alpha_{n}>\alpha_{\mathrm{GW}}$ if and only if there is
an invariant kernel $K\in\operatorname{CUT_{\square}}(S^{n-1})$ such that

$1-K(t_{\mathrm{GW}})>1-K_{\mathrm{GW}}(t_{\mathrm{GW}}).$ (14)

If, moreover, $\alpha_{n}>\alpha_{\mathrm{GW}}$, then there is a measurable
function $f\colon S^{n-1}\to\\{-1,1\\}$ such that (14) holds for $K=R(f\otimes
f^{*})$.

###### Proof.

First the easy direction. Suppose there is such a kernel $K$. Then

$1-K(t_{\mathrm{GW}})>1-K_{\mathrm{GW}}(t_{\mathrm{GW}})=\alpha_{\mathrm{GW}}(1-t_{\mathrm{GW}}).$
(15)

Both functions

$t\mapsto 1-K(t)\qquad\text{and}\qquad t\mapsto 1-K_{\mathrm{GW}}(t)$

are continuous in $[-1,1]$. From (15), we see that there is $\epsilon>0$ such
that the first function above is at least
$(\alpha_{\mathrm{GW}}+\epsilon)(1-t)$ in some interval $I$ around
$t_{\mathrm{GW}}$. The second function above is at least
$\alpha_{\mathrm{GW}}(1-t)$ in $[-1,1]$ and, if $\epsilon$ is small enough,
then it is at least $(\alpha_{\mathrm{GW}}+\epsilon)(1-t)$ in $[-1,1]\setminus
I$ (recall from (13) that we know the second function explicitly). But then
for some $\lambda\in[0,1]$ and small enough $\epsilon^{\prime}>0$ we will have
that

$K^{\prime}=\lambda
K+(1-\lambda)K_{\mathrm{GW}}\in\operatorname{CUT_{\square}}(S^{n-1})$

is such that
$1-K^{\prime}(t)\geq(\alpha_{\mathrm{GW}}+\epsilon^{\prime})(1-t)$ for all
$t\in[-1,1]$, so the optimal value of (4) is greater than
$\alpha_{\mathrm{GW}}$ and therefore $\alpha_{n}>\alpha_{\mathrm{GW}}$ from
the easy direction of Theorem 1.1 (proved in §1.1).

Now suppose $\alpha_{n}>\alpha_{\mathrm{GW}}$. For every $\eta>0$, Lemma 2.1
gives a measurable function $f\colon S^{n-1}\to\\{-1,1\\}$ such that

$1-R(f\otimes f^{*})(t_{\mathrm{GW}})\geq\alpha_{n}(1-t_{\mathrm{GW}})-\eta$

(take $I=\\{t_{\mathrm{GW}}\\}$ and $z=1$ in the lemma); set $K=R(f\otimes
f^{*})$. Then

$1-K(t_{\mathrm{GW}})\geq\alpha_{n}(\alpha_{\mathrm{GW}}^{-1}(1-K_{\mathrm{GW}}(t_{\mathrm{GW}})))-\eta.$

Since $\alpha_{n}/\alpha_{\mathrm{GW}}>1$, we finish by taking $\eta$ close
enough to 0. ∎

Theorem 3.1 shows that, to find a lower bound for $\alpha_{n}$, we need to
find a better partition of the sphere $S^{n-1}$, and this can be done by
finding a maximum cut in a graph defined on a discretization of the sphere
(cf. the proof of Lemma 2.1). This can be tricky in general: Avidor and Zwick
[2] present such a better partition for $n=3$, but their construction is ad
hoc. For $n=2$, however, one may use the hyperplane rounding procedure to
obtain such a better partition, in a curious application of the Goemans-
Williamson algorithm to improve on itself.

We want to find an invariant kernel
$K\in\operatorname{CUT_{\square}}(S^{n-1})$ satisfying (15), that is, we want
to find a good solution of the following optimization problem:

${\begin{array}[]{r@{\ }l@{\quad}l}\sup&1-K(t_{\mathrm{GW}})\\\
&\text{$K\in\operatorname{CUT_{\square}}(S^{n-1})$ is invariant.}\end{array}}$

This seems to be a difficult problem, but we can relax the constraint that
$K\in\operatorname{CUT_{\square}}(S^{n-1})$ by requiring only that $K$ be
positive. Then, using Schoenberg’s theorem to parameterize $K$ as in §2, we
get the following relaxation of our problem:

${\begin{array}[]{r@{\
}l@{\quad}l}\sup&1-\sum_{k=0}^{\infty}a_{k}P_{k}^{(\nu,\nu)}(t_{\mathrm{GW}})\\\\[3.0pt]
&\sum_{k=0}^{\infty}a_{k}=1,\\\ &a_{k}\geq 0\quad\text{for all~{}$k\geq
0$.}\end{array}}$ (16)

For $n=2$ and hence $\nu=-1/2$, the optimal solution of (16) is $a_{k}=0$ for
all $k\neq 4$ and $a_{4}=1$, as may be proved, for instance, by showing a
solution to the dual of (16) having the same objective value as the solution
$a$ (see §4 for a description of the dual problem of a problem related to
(16)).

Using formula (5.1.1) from Andrews, Askey, and Roy [1], this means that the
optimal kernel is

$K(\cos\theta)=P_{4}^{(-1/2,-1/2)}(\cos\theta)=\cos 4\theta.$

If we identify the circle $S^{1}$ with the interval $[0,2\pi]$, then the inner
product between points $\theta$, $\phi\in[0,2\pi]$ is $\arccos(\theta-\phi)$,
so

$K(\theta,\phi)=\cos 4(\theta-\phi)=\cos 4\theta\cos 4\phi+\sin 4\theta\sin
4\phi.$

Taking $g\colon S^{1}\to S^{1}$ such that $g(\theta)=(\cos 4\theta,\sin
4\theta)$, we have $K(\theta,\phi)=g(\theta)\cdot g(\phi)$.

Now, let us round the rank-2 solution $g$. Let $e=(1,0)$ and set $f(\theta)=1$
if $e\cdot g(\theta)\geq 0$ and $f(\theta)=-1$ otherwise. The resulting
partition is exactly the windmill partition that, combined with the partition
$f_{\mathrm{GW}}$ of the sphere into two equal halves, shows that

$\alpha_{2}=\frac{32}{25+5\sqrt{5}}$

(cf. Avidor and Zwick [2]); see also Figure 1.

Figure 1. On the left we have the unit circle $S^{1}$ and, supported on a
point $\theta$, the vector $f(\theta)=(\cos 4\theta,\sin 4\theta)$ — in blue
if $\cos 4\theta\geq 0$ and in red otherwise. On the right, we have in gray
the segments of the circle where $\cos 4\theta\geq 0$; this is the windmill
partition.

###### Proof of Theorem 1.1 for $n=2$.

In §1.1 we have seen that the optimal value of (4) is at most $\alpha_{2}$.
The reverse inequality is proved by Avidor and Zwick [2]: they show how to
pick $\lambda\in[0,1]$ such that, if $f\colon S^{1}\to\\{-1,1\\}$ is the
windmill partition of Figure 1 and $f_{\mathrm{GW}}\colon S^{1}\to\\{-1,1\\}$
is the partition into two equal halves, then $(K,\alpha)$ with

$K=\lambda R(f\otimes f^{*})+(1-\lambda)R(f_{\mathrm{GW}}\otimes
f_{\mathrm{GW}}^{*})$

and

$\alpha=\frac{32}{25+5\sqrt{5}}$

is a feasible solution of (4). Since $\alpha_{2}=\alpha$, we are then done. ∎

For $n\geq 3$, the approach outlined above does not work. The optimal solution
of the relaxation (16) is always $a_{k}=0$ for all $k\neq 1$ and $a_{1}=1$.
The hyperplane rounding then gives the partition $f_{\mathrm{GW}}$ into two
equal halves, therefore not providing a lower bound for $\alpha_{n}$ better
than $\alpha_{\mathrm{GW}}$.

##  4\. Upper bounds for $\alpha_{n}$ and bad instances

Let us see how to solve a relaxation of (4) in order to get upper bounds for
$\alpha_{n}$. The first order of business is to use Schoenberg’s theorem
(Theorem 2.4) to parameterize $K$ as

$K(t)=\sum_{k=0}^{\infty}a_{k}P_{k}^{(\nu,\nu)}(t)\qquad\text{for
all~{}$t\in[-1,1]$},$ (17)

where $\nu=(n-3)/2$, $a_{k}\geq 0$ for all $k$, and
$\sum_{k=0}^{\infty}a_{k}<\infty$.

Say now that $U\subseteq S^{n-1}$ is a nonempty finite set and $Z\colon
U\times U\to\mathbb{R}$ and $\beta\in\mathbb{R}$ are such that

$\sum_{x,y\in U}Z(x,y)A(x,y)\geq\beta$

for all $A\in\operatorname{CUT_{\square}}(U)$, so $Z$ and $\beta$ give a valid
constraint for $\operatorname{CUT_{\square}}(U)$. If
$K\in\operatorname{CUT_{\square}}(S^{n-1})$, then

$\sum_{x,y\in U}Z(x,y)K(x,y)\geq\beta.$

Rewriting this inequality using the parametrization of $K$ we see that the
variables $a_{k}$ satisfy the constraint

$\sum_{k=0}^{\infty}a_{k}r_{k}\geq\beta,$

where $r=(r_{k})$ is the sequence such that

$r_{k}=\sum_{x,y\in U}Z(x,y)P_{k}^{(\nu,\nu)}(x\cdot y).$

Let $\mathcal{R}$ be a finite collection of pairs $(r,\beta)$, each one
associated with a valid constraint of $\operatorname{CUT_{\square}}(U)$ for
some finite set $U\subseteq S^{n-1}$, as described above. Recall that, if
$K\in\operatorname{CUT_{\square}}(S^{n-1})$, then $K(1)=1$, and that
$P_{k}^{(\nu,\nu)}(1)=1$ in our normalization. Choose a finite nonempty set
$I\subseteq[-1,1]$. Then the following linear-programming problem with
infinitely many variables but finitely many constraints is a relaxation of
(4); its optimal value thus provides an upper bound for $\alpha_{n}$:

${\begin{array}[]{r@{\ }l@{\quad}l}\sup&\alpha\\\
&\sum_{k=0}^{\infty}a_{k}=1,\\\
&\alpha(1-t)+\sum_{k=0}^{\infty}a_{k}P_{k}^{(\nu,\nu)}(t)\leq 1&\text{for
all~{}$t\in I$},\\\ &\sum_{k=0}^{\infty}a_{k}r_{k}\geq\beta&\text{for
all~{}$(r,\beta)\in\mathcal{R}$},\\\ &a_{k}\geq 0&\text{for all~{}$k\geq
0$}.\end{array}}$ (18)

A dual problem for (18) is

${\begin{array}[]{r@{\ }l@{\quad}l}\inf&\lambda+\sum_{t\in
I}z(t)-\sum_{(r,\beta)\in\mathcal{R}}y(r,\beta)\beta\\\\[3.0pt] &\sum_{t\in
I}z(t)(1-t)=1,\\\\[3.0pt] &\lambda+\sum_{t\in
I}z(t)P_{k}^{(\nu,\nu)}(t)-\sum_{(r,\beta)\in\mathcal{R}}y(r,\beta)r_{k}\geq
0\quad\text{for all~{}$k\geq 0$},\\\\[3.0pt] &z,y\geq 0.\end{array}}$ (19)

It is routine to show that weak duality holds between the two problems: if
$(a,\alpha)$ is a feasible solution of (18) and $(\lambda,z,y)$ is a feasible
solution of (19), then

$\alpha\leq\lambda+\sum_{t\in
I}z(t)-\sum_{(r,\beta)\in\mathcal{R}}y(r,\beta)\beta.$

So to find an upper bound for $\alpha_{n}$ it suffices to find a feasible
solution of (19).

To find such a feasible dual solution we follow the same approach presented by
DeCorte, Oliveira, and Vallentin [3, §8] for a very similar problem. We start
by choosing a large enough value $d$ (say $d=2000$) and truncating the series
in (17) at degree $d$, setting $a_{k}=0$ for all $k>d$. Then, for finite sets
$I$ and $\mathcal{R}$, problem (18) becomes a finite linear-programming
problem. We solve it and from its dual we obtain a candidate solution
$(\lambda,z,y)$ for the original, infinite-dimensional dual. All that is left
to do is check that this is indeed a feasible solution, or else that it can be
turned into a feasible solution by slightly increasing $\lambda$. This
verification procedure is also detailed by DeCorte, Oliveira, and Vallentin
(ibid., §8.3).

Finding a good set $I\subseteq[-1,1]$ is easy: one simply takes a finely
spaced sample of points. Finding a good set $\mathcal{R}$ of constraints is
another issue. The approach is, again, detailed by DeCorte, Oliveira, and
Vallentin (ibid., §8.3); here is an outline. We start by setting
$\mathcal{R}=\emptyset$. Then, having a solution of (18), and having access to
a list of facets of $\operatorname{CUT_{\square}}(U)$ for a set $U$ of 7
elements, numerical methods for unconstrained optimization are used to find
points on the sphere for which a given inequality is violated. These violated
inequalities are then added to (18) and the process is repeated.

Table 1 shows a list of upper bounds for $\alpha_{n}$ found with the procedure
described above. These bounds have been rigorously verified using the approach
of DeCorte, Oliveira, and Vallentin.

$n$ | Upper bound | $n$ | Upper bound
---|---|---|---
4 | 0.881693 | 12 | 0.878923
5 | 0.880247 | 13 | 0.878893
6 | 0.879526 | 14 | 0.878864
7 | 0.879184 | 15 | 0.878835
8 | 0.879079 | 16 | 0.878798
9 | 0.879016 | 17 | 0.878772
10 | 0.878981 | 18 | 0.878772
11 | 0.878953 | 19 | 0.878744
Table 1. Upper bounds for $\alpha_{n}$ from a relaxation of problem (4). For
$n=3$, the relaxation gives an upper bound of $0.8854$, not better than
$\alpha_{2}$. These bounds have all been computed considering a same set
$\mathcal{R}$ with 28 constraints from the cut polytope found heuristically
for the case $n=4$; improvements could possibly be obtained by trying to find
better constraints for each dimension. The bound using $\mathcal{R}$ decreases
more and more slowly after $n=19$; for $n=10000$ one obtains the upper bound
$0.878695$.

###  4.1. Constructing bad instances

A feasible solution of (19) gives an upper bound for $\alpha_{n}$, but this
upper bound is not constructive, that is, we do not get an instance of the
maximum-cut problem with large integrality gap. Let us see now how to extract
bad instances for the maximum-cut problem from a solution of (19).

Let $I\subseteq[-1,1)$ be a finite nonempty set of inner products and
$\mathcal{R}$ be a finite set of constraints from the cut polytope. Say
$(\lambda,z,y)$ is a feasible solution of (19) and let

$\alpha=\lambda+\sum_{t\in
I}z(t)-\sum_{(r,\beta)\in\mathcal{R}}y(r,\beta)\beta$

be its objective value.

The intuition behind the construction is simple. We consider a graph on the
sphere $S^{n-1}$, where $x$, $y\in S^{n-1}$ are adjacent if $x\cdot y\in I$
and the weight of an edge between $x$ and $y$ is $z(x\cdot y)$. Bad instances
will arise from discretizations of this infinite graph.

Given a partition $\mathcal{P}$ of $S^{n-1}$ into finitely many sets, denote
by $\delta(\mathcal{P})$ the maximum diameter of any set in $\mathcal{P}$. Let
$(\mathcal{P}_{m})$ be a sequence of partitions of $S^{n-1}$ into finitely
many measurable sets such that $\mathcal{P}_{m+1}$ is a refinement of
$\mathcal{P}_{m}$ and

$\lim_{m\to\infty}\delta(\mathcal{P}_{m})=0.$

For $m\geq 0$, let
$A_{z}^{m}\colon\mathcal{P}_{m}\times\mathcal{P}_{m}\to\mathbb{R}$ be the
matrix defined in (6) for the partition $\mathcal{P}=\mathcal{P}_{m}$ and the
function $z$. Since $\mathcal{P}_{m+1}$ is a refinement of $\mathcal{P}_{m}$,
both limits

$\lim_{m\to\infty}\operatorname{SDP}_{1}(A^{m}_{z})\qquad\text{and}\qquad\lim_{m\to\infty}\operatorname{SDP}_{n}(A^{m}_{z})$

exist, as the sequences of optimal values are monotonically increasing and
bounded. As $z\neq 0$, both limits are positive, hence

$\lim_{m\to\infty}\frac{\operatorname{SDP}_{1}(A^{m}_{z})}{\operatorname{SDP}_{n}(A^{m}_{z})}$
(20)

exists. Claim: the limit above is at most $\alpha$.

Once the claim is established, we are done: for every $\epsilon>0$, by taking
$m$ large enough (that is, by taking a fine enough partition) we have

$\frac{\operatorname{SDP}_{1}(A^{m}_{z})}{\operatorname{SDP}_{n}(A^{m}_{z})}\leq\alpha+\epsilon,$

that is, we get a sequence of bad instances for the maximum-cut problem.

To prove the claim, suppose (20) is at least $\alpha+\epsilon$ for some fixed
$\epsilon>0$. Then for all large enough $m$ we have

$\operatorname{SDP}_{1}(A^{m}_{z})\geq(\alpha+\epsilon)\operatorname{SDP}_{n}(A^{m}_{z}).$

Following the proof of Lemma 2.1, this means that for every large enough $m$
there is a function $f_{m}\colon S^{n-1}\to\\{-1,1\\}$ that respects
$\mathcal{P}_{m}$ and satisfies

$\sum_{t\in I}z(t)(1-R(f_{m}\otimes f_{m}^{*})(t))\geq\sum_{t\in
I}z(t)((\alpha+\epsilon)(1-t)-\eta_{m}),$

where $\eta_{m}\geq 0$ and $\eta_{m}\to 0$ as $m\to\infty$.

Use the feasibility of $(\lambda,z,y)$ for (19) together with the definition
of $\alpha$ to get from the above inequality that

$\lambda+\sum_{t\in I}z(t)R(f_{m}\otimes
f_{m}^{*})(t)-\sum_{(r,\beta)\in\mathcal{R}}y(r,\beta)\beta\leq-\epsilon+\eta_{m}\sum_{t\in
I}z(t).$ (21)

Next, note that $R(f_{m}\otimes
f_{m}^{*})\in\operatorname{CUT_{\square}}(S^{n-1})$. Using Schoenberg’s
theorem (Theorem 2.4), write

$R(f_{m}\otimes f_{m}^{*})(t)=\sum_{k=0}^{\infty}a_{k}P_{k}^{(\nu,\nu)}(t),$

where $\nu=(n-3)/2$, $a_{k}\geq 0$, and $\sum_{k=0}^{\infty}a_{k}=1$. Use
again the feasibility of $(\lambda,z,y)$ for (19) together with (21) to get

$\begin{split}0&\leq\sum_{k=0}^{\infty}a_{k}\biggl{(}\lambda+\sum_{t\in
I}z(t)P_{k}^{(\nu,\nu)}(t)-\sum_{(r,\beta)\in\mathcal{R}}y(r,\beta)r_{k}\biggr{)}\\\
&\leq\lambda+\sum_{t\in I}z(t)R(f_{m}\otimes
f_{m}^{*})(t)-\sum_{(r,\beta)\in\mathcal{R}}y(r,\beta)\beta\\\
&\leq-\epsilon+\eta_{m}\sum_{t\in I}z(t).\end{split}$

Since $\epsilon>0$ and $\eta_{m}\to 0$ as $m\to\infty$, by taking $m$ large
enough we get a contradiction, proving the claim.

## References

  * [1] G.E. Andrews, R. Askey, and R. Roy, Special Functions, Encyclopedia of Mathematics and its Applications 71, Cambridge University Press, Cambridge, 1999.
  * [2] A. Avidor and U. Zwick, Rounding two and three dimensional solutions of the SDP relaxation of MAX CUT, in: Approximation, randomization and combinatorial optimization, Lecture Notes in Computer Science 3624, Springer, Berlin, 2005, pp. 14–25.
  * [3] E. DeCorte, F.M. de Oliveira Filho, and F. Vallentin, Complete positivity and distance-avoiding sets, to appear in Mathematical Programming, Series A, 2020, 57pp., arXiv:1804:09099.
  * [4] C. Delorme and S. Poljak, Combinatorial properties and the complexity of a max-cut approximation, European Journal of Combinatorics 14 (1993) 313–333.
  * [5] C. Delorme and S. Poljak, Laplacian eigenvalues and the maximum cut problem, Mathematical Programming 62 (1993) 557–574.
  * [6] M.M. Deza and M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15, Springer-Verlag, Berlin, 1997.
  * [7] U. Feige and G. Schechtman, On the integrality ratio of semidefinite relaxations of MAX CUT, in: Proceedings of the 33th Annual ACM Symposium on Theory of Computing, Crete, Greece, 2001, pp. 433–442.
  * [8] M.X. Goemans and D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the Association for Computing Machinery 42 (1995) 1115–1145.
  * [9] B. Gärtner and J. Matoušek, Approximation Algorithms and Semidefinite Programming, Springer, Heidelberg, 2012.
  * [10] R.M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations (Proceedings of a symposium on the Complexity of Computer Computations, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, 1972; R.E. Miller and J.W. Thatcher, eds.), Plenum Press, New York, 1972, pp. 85–103.
  * [11] P. Mattila, Geometry of Sets and Measures in Euclidean Space: Fractals and Rectifiability, Cambridge Studies in Advanced Mathematics 44, Cambridge University Press, Cambridge, 1995.
  * [12] B. McMillan, History of a problem, Journal of the Society for Industrial and Applied Mathematics 3 (1955) 119–128.
  * [13] F.M. de Oliveira Filho, New bounds for Geometric Packing and Coloring via Harmonic Analysis and Optimization, Ph.D. Thesis, University of Amsterdam, 2009.
  * [14] G. Pisier, Grothendieck’s theorem, past and present, American Mathematical Society. Bulletin. New Series 49 (2012) 237–323.
  * [15] I.J. Schoenberg, Positive definite functions on spheres, Duke Mathematical Journal 9 (1942) 96–108.
  * [16] A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, Chicester, 1986.
  * [17] G. Szegö, Orthogonal Polynomials (Fourth Edition), American Mathematical Society Colloquium Publications Volume XXIII, American Mathematical Society, Providence, 1975.