The Grothendieck Constant is Strictly Larger than Davie-Reeds' Bound

1. Problem Statement

The Grothendieck constant ($K_G$) is a fundamental quantity in functional analysis, defined as the supremum of the ratio between the semidefinite programming (SDP) relaxation and the integer solution for a specific class of bilinear forms. Formally:
$$K_G := \sup_{n \in \mathbb{N}} \sup_{A \in \mathbb{R}^{n \times n}} \frac{\max_{\|x_i\|_2=1, \|y_j\|_2=1} \sum A_{ij} \langle x_i, y_j \rangle}{\max_{x_i, y_j \in \{\pm 1\}} \sum A_{ij} x_i y_j}$$
This constant has profound implications in:

• Quantum Information: It characterizes the maximal violation of Bell inequalities in 2-player XOR games (Tsirelson's bound).
• Theoretical Computer Science: It represents the integrality gap of specific SDPs, connecting to approximation algorithms, regularity lemmas, and the Unique Games Conjecture.

The Open Problem: Despite decades of research, the exact value of $K_G$ remains unknown.

• Upper Bound: Proven by Krivine (1977) as $K_G \le \frac{\pi}{2 \ln(1+\sqrt{2})} \approx 1.7823$.
• Lower Bound: Proven independently by Davie (1984) and Reeds (1991) as $K_G \ge K_{DR} \approx 1.6769$.
• Stagnation: The lower bound $K_{DR}$ had not improved since the 1980s. The authors aim to prove that this bound is not optimal.

2. Methodology

The authors employ a perturbative analysis of the operator that achieves the Davie–Reeds lower bound. Their approach involves the following steps:

A. Hermite Projection Games

The authors utilize the framework of "Hermite projection games," where the matrix $A$ is viewed as a linear operator on functions $f: \mathbb{R}^n \to \mathbb{R}$ under the Gaussian measure. These operators are linear combinations of projection operators $\Pi_k$ onto the space of degree-$k$ Hermite polynomials.

• The Davie–Reeds operator is $A_{DR} = \Pi_1 - \lambda^* I$, where $\lambda^* \approx 0.19748$.
• The SDP value of such an operator is simply the spectral norm (the maximum absolute coefficient $|c_k|$).

B. The Perturbation Strategy

The core insight is that near-optimal solutions (optimizers) for the Davie–Reeds game possess a non-negligible "weight" on their degree-3 Hermite coefficients.

1. Intuition: The authors interpret $K_G$ through nonlocal games. The Davie–Reeds game confuses players by "negating" the correct answer with probability $p$. They hypothesize that introducing more alternations (oscillations) in the game rules makes it harder for classical players, thereby increasing the integrality gap.
2. The Perturbed Operator: They define a new operator:
   $$A_\epsilon = \Pi_1 - \lambda^* I - \epsilon \Pi_3$$
   where $\epsilon > 0$ is a small constant. This adds a cubic term to the game.

C. Stability Analysis

To prove that $A_\epsilon$ yields a higher value, the authors must show that any function pair $(f, g)$ that nearly maximizes the value for $A_\epsilon$ must also be "close" to the optimizers of the original Davie–Reeds game.

• Lemma 4.2 (Stability): They prove that if a pair $(f, g)$ achieves a value close to the optimal $val(ADR)$, then $(f, g)$ is close in $L^2$ distance to a "Davie–Reeds strip function" (a specific structure defined by a threshold $C^*$).
• Degree-3 Weight: They prove (Lemma 3.3) that for any Davie–Reeds strip function, the correlation of their degree-3 Hermite projections is strictly positive:
  $$\mathbb{E}[(\Pi_3 f)(X)(\Pi_3 g)(X)] \ge 0.046$$
• The Trade-off: By introducing $-\epsilon \Pi_3$, the value of the game for classical strategies (which are constrained to $\{\pm 1\}$) decreases by approximately $\epsilon \times 0.046$. However, the SDP value (quantum strategy) remains largely unaffected because the spectral norm is dominated by the $\Pi_1$ term. This widens the gap.

3. Key Contributions

1. Breaking the 40-Year Stagnation: This is the first improvement to the lower bound of $K_G$ since the 1980s.
2. Proof of Non-Optimality: The authors rigorously prove that the Davie–Reeds operator is not the unique maximizer of the integrality gap; adding a small cubic perturbation strictly increases the gap.
3. Stability of Optimizers: They provide a quantitative stability lemma showing that near-optimal solutions for the Davie–Reeds game must have significant structure (specifically, non-zero degree-3 components), which allows for the perturbation argument.
4. Concurrent Work: The paper notes concurrent work by Heilman [Hei26] using a similar perturbation strategy but with a different analysis, achieving a slightly smaller bound improvement ($10^{-26}$ vs $10^{-12}$).

4. Main Results

The primary theorem establishes a new lower bound:

Theorem 1.1:
$$K_G \ge K_{DR} + 10^{-12}$$

Derivation Logic:

• Let $val(A)$ be the classical value and $sdp(A)$ be the SDP value.
• For the perturbed operator $A_\epsilon = \Pi_1 - \lambda^* I - \epsilon \Pi_3$:
  • $sdp(A_\epsilon) \approx 1 - \lambda^*$ (unchanged to first order).
  • $val(A_\epsilon) \le val(ADR) - \epsilon(0.046 - \text{error terms})$.
• By choosing $\epsilon = 4 \times 10^{-11}$, the error term $12(2\epsilon)^{1/4}$ becomes small enough that the subtraction term remains positive ($\approx 0.01$).
• The ratio $\frac{sdp(A_\epsilon)}{val(A_\epsilon)}$ thus increases by a constant factor relative to the original ratio, yielding the $10^{-12}$ improvement.

5. Significance

• Mathematical Insight: The result confirms the intuition that the "hardest" instances for the Grothendieck problem are not simple linear projections but involve higher-order oscillations (specifically degree-3 terms). It suggests that the true $K_G$ might be approached by operators with alternating signs in their Hermite coefficients ($\Pi_1 - c_3 \Pi_3 + c_5 \Pi_5 \dots$).
• Quantum vs. Classical: In the context of nonlocal games, this implies that the gap between quantum and classical correlations can be slightly larger than previously thought, even for 2-player XOR games.
• Methodological Impact: The use of stability analysis to characterize near-extremizers and then perturb them is a powerful technique that may be applicable to other open problems in functional analysis and approximation theory where exact constants are elusive.

In summary, Jones and Malavolta demonstrate that the long-standing lower bound for the Grothendieck constant is not tight, proving that $K_G$ is strictly larger than the Davie–Reeds bound by a small but positive constant, thereby opening a new avenue for refining the exact value of this fundamental mathematical constant.