10 Lectures and 42 Open Problems — The Grothendieck Constant

10 Lectures and 42 Open Problems — The Grothendieck Constant

Definitions and mathematical statement

For a real $m\times n$ matrix $A=(a_{ij})$, put \[ B(A)=\max_{{\varepsilon}_i,\delta_j\in\{-1,1\}} \left|\sum_{i,j}a_{ij}{\varepsilon}_i\delta_j\right|. \] The real Grothendieck constant is the least $K$ such that, for every $m,n,A$ and all unit vectors $u_i,v_j$ in any real Hilbert space, \[ \left|\sum_{i,j}a_{ij}\langle u_i,v_j\rangle\right|\le K B(A). \] Determine this optimal universal constant $K_G^{{\mathbb{R}}}$ exactly. The dimensions and the matrix are arbitrary, and the comparison is with independent signs on rows and columns. Neither a fixed-dimensional variant nor the complex Grothendieck constant is the selected quantity. An improved upper or lower estimate alone is not an exact determination.

Formulation and concept references: [S1].

Short English statement

What is the exact largest advantage that real unit-vector inner products can have over signs in a bilinear form?

Research attempt

The universal optimization and its status.

The exact real constant is UNRESOLVED by this attempt. The primary source [S1] proves a strict improvement over Krivine's classical upper bound. Accordingly, the elementary derivation of that bound below is a valid certificate, not a proposed exact answer and not the best known upper estimate. The useful outputs are an exact small-matrix lower bound, a complete Gaussian rounding proof, and checks on two tempting but invalid amplification arguments.

Write $V(A)$ for the supremum of the absolute vector expression in the question. Simultaneously changing all row vectors to their negatives changes its sign, so absolute values can be replaced by maximization of the signed expression. The same applies to $B(A)$. If $A\ne0$, then $B(A)>0$: averaging the square of the signed sum over independent uniform signs gives $\sum_{ij}a_{ij}^2>0$. Consequently \[ K_G^{\mathbb R}=\sup_{m,n,A\ne0}\frac{V(A)}{B(A)}. \tag{310.1} \] This is a supremum over arbitrary finite sizes, not the optimization of one prescribed matrix.

Exact evaluation of the sign side.

For fixed column signs $\delta$, choose each row sign to agree with the sign of $\sum_j a_{ij}\delta_j$, choosing either sign when that sum is zero. This proves \[ B(A)=\max_{\delta\in\{-1,1\}^n} \sum_i\left|\sum_j a_{ij}\delta_j\right|. \tag{310.2} \] It gives an exact finite algorithm for rational matrices, albeit an exponential one. It also shows that imposing the same sign on row and column copies would change the problem: their choices are independent, even for a square symmetric matrix.

For fixed $m,n$, the vector side needs no Hilbert space of dimension larger than $m+n$. Only the span of the finitely many vectors matters. Equivalently introduce their Gram matrix $G$; the feasible set is \[ G\succeq0,\qquad G_{aa}=1\quad(1\leq a\leq m+n). \tag{310.3} \] The objective is the linear functional $\sum_{ij}a_{ij}G_{i,m+j}$. This set is closed and bounded because positive semidefiniteness gives $|G_{ab}|\leq1$, so the maximum is attained. Conversely every such matrix has a real Gram factorization. This finite-dimensional compactness does not bound the sizes needed in the outer supremum $310.1$.

A rigorous lower bound from a two-by-two matrix.

Take \[ H=\begin{pmatrix}1&1\\1&-1\end{pmatrix}. \] Equation $310.2$ gives $B(H)=2$: of $\delta_1+\delta_2$ and $\delta_1-\delta_2$, exactly one has absolute value two. For arbitrary unit $v_1,v_2$, optimizing the row vectors gives \[ V(H)=\max\left(\|v_1+v_2\|+\|v_1-v_2\|\right)=2\sqrt2. \tag{310.4} \] Indeed the sum of the squares of these two norms is four, so Cauchy--Schwarz bounds their sum by $2\sqrt2$. Equality holds for orthogonal $v_1,v_2$, with row vectors along their sum and difference. Thus $K_G^{\mathbb R}\geq\sqrt2$. This is an exact example in a two-dimensional real space, not an assertion that the universal constant equals its dimension-two variant.

Gaussian signs and the arcsine identity.

Let $x,y$ be unit vectors with $\langle x,y\rangle=t$, and let $Z$ be a standard Gaussian in their finite-dimensional span. Then \[ \mathbb E\left[\operatorname{sgn}\langle Z,x\rangle \operatorname{sgn}\langle Z,y\rangle\right] =\frac2\pi\arcsin t. \tag{310.5} \] For a proof, write $t=\cos\theta$ with $0\leq\theta\leq\pi$. The angular part of a rotationally invariant two-dimensional Gaussian is uniform. The two scalar products have opposite signs on sectors of total angular measure $2\theta$, hence with probability $\theta/\pi$. Their product expectation is $1-2\theta/\pi$, which is the right side. The collinear endpoints follow by direct inspection or continuity; zero scalar products have probability zero.

Applying $310.5$ directly rounds correlations to arcsines, not to a fixed multiple of themselves. One cannot multiply a termwise inequality by arbitrary signed coefficients $a_{ij}$ and sum it. The next construction removes that obstruction exactly.

Tensor embeddings linearize the rounding.

Put \[ c=\operatorname{arsinh}(1)=\log(1+\sqrt2),\qquad b_r=\frac{c^{2r+1}}{(2r+1)!}\quad(r\geq0). \] For a real unit vector $u$, define vectors in the Hilbert direct sum of odd tensor powers by \[ U(u)=\bigoplus_{r\geq0}\sqrt{b_r}\,u^{\otimes(2r+1)}, \qquad W(v)=\bigoplus_{r\geq0}(-1)^r\sqrt{b_r}\, v^{\otimes(2r+1)}. \tag{310.6} \] The series converge because $\sum_rb_r=\sinh c=1$. Both vectors have norm one, and the tensor inner-product rule gives \[ \langle U(u),W(v)\rangle =\sum_{r\geq0}(-1)^rb_r\langle u,v\rangle^{2r+1} =\sin(c\langle u,v\rangle). \tag{310.7} \] Although the ambient sum is infinite-dimensional, the finitely many $U(u_i),W(v_j)$ span a finite-dimensional space. A standard Gaussian on that span therefore suffices; no Gaussian vector with identity covariance on an infinite-dimensional Hilbert space is assumed.

Use one Gaussian to round all these transformed vectors to signs. Since $c<\pi/2$ and $|\langle u,v\rangle|\leq1$, $\arcsin(\sin(ct))=ct$ on the entire required interval. Thus \[ \mathbb E\sum_{ij}a_{ij}\varepsilon_i\delta_j =\frac{2c}{\pi}\sum_{ij}a_{ij}\langle u_i,v_j\rangle. \] Every realized sign sum has absolute value at most $B(A)$. Taking absolute expectations proves the uniform inequality \[ V(A)\leq\frac{\pi}{2\log(1+\sqrt2)}B(A). \tag{310.8} \] All signs of the coefficients have been retained. Together with $310.4$, this proves a nontrivial finite interval for the universal constant by explicit constructions.

What optimizing this construction actually establishes.

For the same sine tensor prescription with another positive number $c'$, the two squared norms are $\sinh c'$. To keep them at most one before adding orthogonal padding, one needs $c'\leq c$. Hence $c$ is optimal for this particular coefficient prescription. This does not optimize every possible embedding or correlated rounding scheme. The source's strict improvement is precisely a warning against promoting an internally optimized method into the optimal universal constant.

Similarly, $310.4$ saturates two elementary inequalities for $H$. That says nothing about a matrix with many more rows and columns. There is no principle in $310.1$ that an extremizer must occur in the smallest nontrivial size. To prove an exact value one needs a universal upper bound and matching examples approaching it, with the same real scalar and independent-sign conventions.

Direct sums and tensor products fail to amplify naively.

For block diagonal matrices $A\oplus B$, independent row and column choices on the blocks give \[ B(A\oplus B)=B(A)+B(B),\qquad V(A\oplus B)=V(A)+V(B). \] The upper inequalities follow by bounding each block separately; the lower ones use optimal choices for each block, changing signs so their contributions are positive. Therefore the ratio for a direct sum is a weighted average of the two ratios, not their sum or product.

Tensor products permit signs indexed by pairs; these need not split into products of signs on individual factors. This invalidates the claim $B(A\otimes B)=B(A)B(B)$. A complete countercheck is $H\otimes H$, a four-by-four Hadamard matrix $Q$ with $QQ^{\mathsf T}=4I$. For every sign vector $\delta$, \[ \|Q\delta\|_1\leq2\|Q\delta\|_2=8. \] For $\delta=(1,1,1,-1)$, all four entries of $Q\delta$ have absolute value two, so $B(Q)=8$, whereas $B(H)^2=4$. In fact $V(Q)=8$ as well. For arbitrary unit column vectors, Cauchy--Schwarz and orthogonality of the columns of $Q$ give \[ \sum_{i=1}^4\Big\|\sum_{j=1}^4Q_{ij}v_j\Big\| \leq2\left(\sum_i\Big\|\sum_jQ_{ij}v_j\Big\|^2\right)^{1/2} =8. \] The sign example attains it. Tensoring this lower-bound witness therefore reduces its ratio to one, rather than squaring $\sqrt2$.

Verification and the remaining gap.

The saved finite checks enumerate signs exactly for $H$ and $H\otimes H$, verify their integer orthogonality identities, and numerically compare truncated tensor series and the arcsine formula with the stated elementary functions. No sampled Gaussian average is used in place of the exact angular proof of $310.5$.

The proof of $310.8$ is complete but its constant is known from [S1] to be nonoptimal. The first unresolved step is a sharp rounding or dual inequality together with matching unrestricted matrix examples. Finite semidefinite programs, direct sums and tensoring the displayed witness do not supply either half of that equality. The exact value in $310.1$ remains UNRESOLVED here.

Sources

• S1 1103.6161v3, The Grothendieck constant is strictly smaller than Krivine's bound. https://arxiv.org/abs/1103.6161. Formulation source.