On the largest sum-free subset of the lattice cube

1. Probleemstelling

Het artikel behandelt het probleem van het bepalen van de asymptotische dichtheid van de grootste somvrije deelverzameling binnen een $d$-dimensionale roosterkubus.

• Definities: Een deelverzameling $S$ van een abelse groep is somvrij als er geen $x, y, z \in S$ bestaan zodanig dat $x + y = z$. De auteurs bestuderen deelverzamelingen van de roosterkubus $[n+1]^d = \{0, 1, \dots, n\}^d$.
• Doel: Bepalen van de limiet $c_d = \lim_{n \to \infty} \frac{|S|}{n^d}$, waarbij $S$ de grootste somvrije deelverzameling is.
• Context:
  • Voor $d=1$ is het bekend dat $c_1 = 1/2$.
  • Voor $d=2$ bewezen Elsholtz en Rackham dat $c_2 = 3/5$.
  • Voor $d=3, 4$ hebben Lepsveridze en Sun de gevallen recent opgelost.
  • De Vermoeden: Er werd vermoed dat voor alle $d$ de optimale verzameling een "schijf" (slice) van de kubus is die wordt gedefinieerd door een hypervlak. Specifiek levert de verzameling $S^* = \{x \in [n+1]^d \mid u \le \sum x_i < 2u\}$, waarbij $u$ wordt gekozen om het volume van de schijf te maximaliseren, de maximale dichtheid op.
  • Laat $c^*_d$ het maximale volume van zo'n schijf zijn in de continue limiet $[0,1]^d$. Het vermoeden stelt dat $c_d = c^*_d$.

2. Methodologie

Het bewijs volgt de aanpak die is vastgesteld door Lepsveridze en Sun, waarbij een combinatie van dualiteit in lineaire programmering en probabilistische koppeling (joint mixability) wordt gebruikt.

A. Reductie tot Lineaire Programmering

Het probleem van het begrenzen van $|S|$ wordt geherformuleerd als een lineair programma (LP).

• Primaal Probleem: Maximaliseer $\sum |S(x)|$ (waarbij $S(x)$ vezels van de verzameling $S$ zijn) onder de beperking dat voor elke $x, y, z$ met $x+y=z$, geldt dat $|S(x)| + |S(y)| + |S(z)| \le 2(n+1)$.
• Duale Probleem: Om een bovengrens te vinden, moet men een haalbare oplossing (gewichten) construeren voor het duale LP. Het bestaan van dergelijke gewichten is afhankelijk van het vermogen om specifieke kansverdelingen te koppelen.

B. Joint Mixability

De kern van de technische innovatie is het bewijs van een Joint Mixability-resultaat.

• Definitie: Verdelingen $\mu_1, \mu_2, \mu_3$ zijn jointly mixable (gezamenlijk mengbaar) als er een koppeling $(X_1, X_2, X_3)$ bestaat met deze marginaalverdelingen zodanig dat $X_1 + X_2 + X_3 = \mathbb{E}[X_1] + \mathbb{E}[X_2] + \mathbb{E}[X_3]$ bijna zeker geldt.
• Het Belangrijke Stelling (Stelling 1.5): De auteurs bewijzen dat voor elke niet-negatieve gehele getallen $r, s, t$ zodanig dat $r+s+t = dn$, de uniforme verdelingen op de discrete schijven $L_d(r), L_d(s), L_d(t)$ (waarbij $L_d(k) = \{x \in [n+1]^d : \sum x_i = k\}$) jointly mixable zijn.
• Bewijstechniek:
  • Inductie op $d$: Het basisgeval $d=2$ rust op bekende resultaten met betrekking tot intervallen en driehoeksongelijkheden.
  • Inductiestap ($d \ge 3$): De auteurs construeren een koppeling voor de eerste coördinaten met behulp van een vastpuntargument (Brouwer's Vastpuntstelling of Perron-Frobenius). Zij definiëren een afbeelding op de ruimte van kansverdelingen over de drager van de eerste coördinaten en tonen aan dat een vastpunt bestaat. Dit vastpunt zorgt ervoor dat de marginaalverdelingen overeenkomen met de vereiste uniforme verdelingen op de schijven, waardoor de inductiehypothese kan worden toegepast op de overige $d-1$ coördinaten.

C. Gewichtsconstructie en Schattingen van Schijven

Om de joint mixability toe te passen op het duale LP:

1. Partitie: Het domein $[n+1]^{d-1}$ wordt gepartitioneerd in vijf verzamelingen ($A, B, C, D, E$) op basis van de som van coördinaten ten opzichte van de optimale schijfparameter $u^*_d$.
2. Gewichtsfunctie: Met behulp van het resultaat van joint mixability construeren de auteurs een gewichtsfunctie $w(x,y,z)$ die wordt ondersteund door specifieke drietallen van deze verzamelingen.
3. Analytische Schattingen: Zij maken gebruik van log-concaviteit-eigenschappen van de kansdichtheidsfunctie van de som van uniforme stochastische variabelen (Irwin-Hall-verdeling). Zij leiden expliciete grenzen af voor de verhoudingen van schijfvolumes (Lemma 3.1) om te waarborgen dat de geconstrueerde gewichten voldoen aan de duale beperkingen.
   • Voor grote $d$ maken zij gebruik van schattingen voor grote afwijkingen (large deviation estimates).
   • Voor kleine $d$ ($5 \le d < 200$) verifiëren zij de ongelijkheden numeriek.

3. Belangrijkste Bijdragen

1. Oplossing van het Vermoeden voor Alle $d$: Het artikel bewijst dat $c_d = c^*_d$ voor alle dimensies $d \ge 1$. Dit bevestigt dat de optimale somvrije deelverzameling inderdaad de schijf is die wordt gedefinieerd door het hypervlak $\sum x_i \in [u^*_d n, 2u^*_d n)$.
2. Algemeen Joint Mixability-stelling: Het bewijs van Stelling 1.5 is een aanzienlijke bijdrage aan de waarschijnlijkheidstheorie en combinatoriek. Het stelt vast dat uniforme verdelingen op discrete schijven van een hyperkubus die optellen tot een constante, jointly mixable zijn, een resultaat dat eerdere bevindingen voor specifieke lage dimensies generaliseert.
3. Verfijning van de Lepsveridze-Sun-aanpak: De auteurs generaliseren de methode die werd gebruikt voor $d=3,4$ naar willekeurige dimensies, waarbij zij de complexiteit van het construeren van koppelingen in hogere dimensies overwinnen door een rigoureus inductief vastpuntargument.

4. Hoofdresultaten

• Stelling 1.1: Voor elke $d \ge 1$ en elke somvrije deelverzameling $S \subseteq [n+1]^d$ is de grootte begrensd door:
  $$|S| \le c^*_d n^d + O(n^{d-1})$$
  waarbij $c^*_d$ het maximale volume is van de schijf $S_d(u) = \{x \in [0,1]^d : u \le \sum x_i < 2u\}$.
• Corollarium: De limietdichtheid is exact het volume van de optimale schijf, waarmee het natuurlijke vermoeden van Cameron, Green en anderen wordt opgelost.

5. Betekenis en Uitbreidingen

• Combinatorische Getaltheorie: Dit resultaat beslecht een langdurig open probleem met betrekking tot de structuur van somvrije verzamelingen in hoog-dimensionale roosters. Het bevestigt dat de "schijf"-constructie universeel optimaal is, niet alleen voor lage dimensies.
• Probabilistische Methoden: Het artikel demonstreert de kracht van joint mixability en koppeltechnieken bij het oplossen van extremale combinatorische problemen. De inductieve constructie van koppelingen via vastpuntstellingen is een nieuwe en robuuste techniek.
• Algemene Convexe Verzamelingen: De auteurs bespreken kort of deze "schijf"-optimaliteit geldt voor algemene convexe verzamelingen. Zij geven een tegenvoorbeeld (Propositie 5.1) dat aantoont dat voor voldoende grote $d$ convexe verzamelingen bestaan waarbij de grootste somvrije deelverzameling geen enkele schijf is die wordt gedefinieerd door een lineaire functionaal. Dit benadrukt dat de symmetrie van de hyperkubus cruciaal is voor de optimaliteit van de schijf.
• Open Probleem: Het artikel laat de vraag open of de optimaliteit van de schijf geldt voor alle begrensde convexe verzamelingen in dimensie $d=2$.

Kortom, dit artikel biedt een complete oplossing voor de asymptotische dichtheid van de grootste somvrije deelverzameling in een roosterkubus, verenigt eerdere gedeeltelijke resultaten en introduceert krachtige probabilistische hulpmiddelen om willekeurige dimensies te behandelen.