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

1. Probleemstelling

De Grothendieck constante ($K_G$) is een fundamentele grootheid in de functionele analyse met diepgaande connecties naar kwantuminformatie, combinatorische optimalisatie en de meetkunde van Banachruimten. De constante wordt gedefinieerd als de supremum van de verhouding tussen de optimale waarde van een semidefiniete programmering (SDP) en de optimale waarde van een gerelateerd discrete probleem over matrices $A \in \mathbb{R}^{n \times n}$:

$$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}$$

Hoewel de constante decennia lang bestudeerd is, blijft de exacte waarde onbekend.

• Bovenste grens: Bewezen door Krivine (1977) als $K_G \leq \frac{\pi}{2 \ln(1+\sqrt{2})} \approx 1.7823$.
• Onderste grens: De beste bekende ondergrens, onafhankelijk bewezen door Davie (1984) en Reeds (1991), is $K_G \geq K_{DR} \approx 1.6769$.

Het doel van dit artikel is om aan te tonen dat de Davie-Reeds ondergrens niet optimaal is, en een kleine maar strikte verbetering te leveren op deze waarde.

2. Methodologie

De auteurs gebruiken een perturbatieve analyse van de operator die de Davie-Reeds ondergrens realiseert.

Hermite-projectiespellen

De analyse focust op een specifieke klasse van voorbeelden die "Hermite-projectiespellen" worden genoemd. In dit kader wordt de matrix $A$ geïnterpreteerd als een lineaire operator op de ruimte van functies $L^2(\gamma)$ (waarbij $\gamma$ de standaard Gaussische maat is). Deze operatoren worden uitgedrukt als lineaire combinaties van projectie-operatoren $\Pi_k$ die functies projecteren op de deelruimte van Hermite-polynomen van graad $k$.
De Davie-Reeds operator is gedefinieerd als:
$$A_{DR} = \Pi_1 - \lambda^* I$$
waarbij $\lambda^* \approx 0.19748$ een specifieke constante is die de integrality gap maximaliseert.

Perturbatie Strategie

De kern van de methode is het introduceren van een kleine kubische perturbatie aan de Davie-Reeds operator. De auteurs definiëren een nieuwe operator:
$$A_\varepsilon = \Pi_1 - \lambda^* I - \varepsilon \Pi_3$$
waarbij $\varepsilon > 0$ een kleine constante is en $\Pi_3$ projecteert op de graad-3 Hermite-componenten.

De intuïtie achter deze keuze is gebaseerd op het perspectief van niet-lokale spellen (XOR-spellen). De auteurs redeneren dat het toevoegen van een term met een wisselend teken (zoals $\Pi_3$) de "klassieke" strategieën (waarbij $x_i, y_i \in \{\pm 1\}$) meer verwart dan de "kwantum" strategieën (die gebruikmaken van Hilbertruimtes), waardoor de kloof (integrality gap) tussen beide toeneemt.

3. Belangrijkste Bijdragen en Bewijsvoering

Stabiliteitsanalyse van Optimizers

Een cruciale stap in het bewijs is het aantonen dat elke functiepaar $(f, g)$ dat bijna optimaal is voor de Davie-Reeds operator, structureel dicht bij de bekende "strip-functies" van Davie en Reeds ligt.

• Lemma 4.2 (Stabiliteit): Als een paar functies $(f, g)$ een waarde bereikt die binnen $\eta$ van de optimale Davie-Reeds waarde ligt, dan bestaan er Davie-Reeds "strip-functies" $(f_{DR}, g_{DR})$ zodanig dat de $L^2$-afstand tussen hen klein is ($O(\eta^{1/4})$).
• Dit betekent dat men de eigenschappen van de exacte optimizers kan gebruiken om de gedraging van bijna-optimizers te analyseren.

Gewicht op Graad-3 Coëfficiënten

De auteurs bewijzen dat voor elke Davie-Reeds optimizer (en dus ook voor bijna-optimizers), het gewicht op de graad-3 Hermite-coëfficiënten significant is.

• Lemma 3.3: Voor Davie-Reeds strip-functies geldt dat de correlatie van hun graad-3 projecties strikt positief is:
  $$\mathbb{E}[(\Pi_3 f)(X)(\Pi_3 g)(X)] \geq 0.046$$
• Dit is een fundamenteel resultaat: het toont aan dat de optimale strategieën voor de Davie-Reeds operator niet "zuiver" graad-1 zijn, maar een onvermijdelijke graad-3 component hebben.

Verbetering van de Gap

Door de operator te perturbëren met $-\varepsilon \Pi_3$, wordt de waarde van de operator voor de klassieke strategieën (de noemer in de definitie van $K_G$) verlaagd, omdat de graad-3 correlatie positief is en er een negatief teken voor staat. De SDP-waarde (de teller) blijft echter grotendeels ongewijzigd of daalt minder snel.

• Theorema 4.1: De auteurs bewijzen dat voor voldoende kleine $\varepsilon$:
  $$\text{val}(A_\varepsilon) \leq \text{val}(A_{DR}) - \varepsilon(0.046 - O(\varepsilon^{1/4}))$$
  Dit betekent dat de klassieke waarde daalt met een factor die lineair is in $\varepsilon$, terwijl de SDP-waarde (die gelijk is aan de spectrale norm $\sup |c_k|$) slechts marginaal verandert.

4. Resultaten

Het hoofdbewijs leidt tot de volgende stelling:

Theorema 1.1:
$$K_G \geq K_{DR} + 10^{-12}$$

Hoewel de numerieke verbetering ($10^{-12}$) extreem klein is, is het conceptueel revolutionair omdat het aantoont dat de Davie-Reeds ondergrens niet optimaal is. Het bewijst dat de ondergrens van $K_G$ sinds de jaren 80 voor het eerst is verhoogd.

5. Significantie

1. Doorbraak na decennia: Dit is de eerste verbetering van de onderste grens van de Grothendieck constante sinds de werken van Davie en Reeds in de jaren 1980.
2. Validatie van intuïtie: Het resultaat bevestigt de theoretische intuïtie dat het toevoegen van hogere-orde Hermite-projecties (zoals $\Pi_3$) met wisselende tekens leidt tot "hardere" instanties voor het Grothendieck-probleem.
3. Kwantum vs. Klassiek: In de context van kwantuminformatie betekent dit dat de maximale schending van Bell-ongelijkheden voor 2-speler XOR-spellen (die door $K_G$ wordt gekarakteriseerd) strikt groter is dan eerder werd aangenomen op basis van de Davie-Reeds constructie.
4. Methodologische impact: De gebruikte stabiliteitsanalyse van bijna-optimizers biedt een krachtig nieuw instrument voor het bestuderen van extremale problemen in de functionele analyse en de theorie van semidefiniete programmering.

Samenvattend tonen Jones en Malavolta aan dat de Davie-Reeds operator een suboptimale benadering is en dat een zorgvuldig gekozen perturbatie met een graad-3 term de kloof tussen kwantum- en klassieke strategieën verder vergroot, waardoor de ondergrens van de Grothendieck constante stijgt.