On the largest sum-free subset of the lattice cube

1. Enunciato del Problema

Il lavoro affronta il problema di determinare la densità asintotica del più grande sottoinsieme senza somme all'interno di un cubo reticolare $d$-dimensionale.

• Definizioni: Un sottoinsieme $S$ di un gruppo abeliano è senza somme se non esistono $x, y, z \in S$ tali che $x + y = z$. Gli autori studiano sottoinsiemi del cubo reticolare $[n+1]^d = \{0, 1, \dots, n\}^d$.
• Obiettivo: Determinare il limite $c_d = \lim_{n \to \infty} \frac{|S|}{n^d}$, dove $S$ è il più grande sottoinsieme senza somme.
• Contesto:
  • Per $d=1$, è ben noto che $c_1 = 1/2$.
  • Per $d=2$, Elsholtz e Rackham hanno dimostrato che $c_2 = 3/5$.
  • Per $d=3, 4$, Lepsveridze e Sun hanno recentemente risolto i casi.
  • La Congettura: Si è congetturato che per ogni $d$, l'insieme ottimale sia una "fetta" del cubo definita da un iperpiano. Nello specifico, l'insieme $S^* = \{x \in [n+1]^d \mid u \le \sum x_i < 2u\}$, dove $u$ è scelto per massimizzare il volume della fetta, produce la densità massima.
  • Sia $c^*_d$ il volume massimo di tale fetta nel limite continuo $[0,1]^d$. La congettura afferma che $c_d = c^*_d$.

2. Metodologia

La dimostrazione segue l'approccio stabilito da Lepsveridze e Sun, utilizzando una combinazione di dualità della programmazione lineare e accoppiamento probabilistico (miscelabilità congiunta).

A. Riduzione alla Programmazione Lineare

Il problema di limitare $|S|$ è riformulato come un programma lineare (PL).

• Problema Primal: Massimizzare $\sum |S(x)|$ (dove $S(x)$ sono le fibre dell'insieme $S$) soggetto al vincolo che per qualsiasi $x, y, z$ con $x+y=z$, $|S(x)| + |S(y)| + |S(z)| \le 2(n+1)$.
• Problema Duale: Per trovare un limite superiore, è necessario costruire una soluzione ammissibile (pesi) per il PL duale. L'esistenza di tali pesi dipende dalla capacità di accoppiare specifiche distribuzioni di probabilità.

B. Miscelabilità Congiunta

L'innovazione tecnica centrale è la dimostrazione di un risultato di Miscelabilità Congiunta.

• Definizione: Le distribuzioni $\mu_1, \mu_2, \mu_3$ sono miscelabili congiuntamente se esiste un accoppiamento $(X_1, X_2, X_3)$ con queste marginali tale che $X_1 + X_2 + X_3 = \mathbb{E}[X_1] + \mathbb{E}[X_2] + \mathbb{E}[X_3]$ quasi certamente.
• Il Teorema Chiave (Teorema 1.5): Gli autori dimostrano che per qualsiasi interi non negativi $r, s, t$ tali che $r+s+t = dn$, le distribuzioni uniformi sulle fette discrete $L_d(r), L_d(s), L_d(t)$ (dove $L_d(k) = \{x \in [n+1]^d : \sum x_i = k\}$) sono miscelabili congiuntamente.
• Tecnica di Dimostrazione:
  • Induzione su $d$: Il caso base $d=2$ si basa su risultati noti riguardanti intervalli e disuguaglianze triangolari.
  • Passo Induttivo ($d \ge 3$): Gli autori costruiscono un accoppiamento per le prime coordinate utilizzando un argomento di punto fisso (Teorema del Punto Fisso di Brouwer o Perron-Frobenius). Definiscono una mappa sullo spazio delle distribuzioni di probabilità sul supporto delle prime coordinate e dimostrano l'esistenza di un punto fisso. Questo punto fisso garantisce che le marginali corrispondano alle distribuzioni uniformi richieste sulle fette, permettendo di applicare l'ipotesi induttiva alle restanti $d-1$ coordinate.

C. Costruzione dei Pesi e Stime delle Fette

Per applicare la miscelabilità congiunta al PL duale:

1. Partizionamento: Il dominio $[n+1]^{d-1}$ è partizionato in cinque insiemi ($A, B, C, D, E$) in base alla somma delle coordinate rispetto al parametro ottimale della fetta $u^*_d$.
2. Funzione di Peso: Utilizzando il risultato di miscelabilità congiunta, gli autori costruiscono una funzione di peso $w(x,y,z)$ supportata su triple specifiche di questi insiemi.
3. Stime Analitiche: Sfruttano le proprietà di log-concavità della funzione di densità di probabilità della somma di variabili casuali uniformi (distribuzione di Irwin-Hall). Derivano limiti espliciti sui rapporti dei volumi delle fette (Lemma 3.1) per garantire che i pesi costruiti soddisfino i vincoli duali.
   • Per $d$ grandi, utilizzano stime sulle grandi deviazioni.
   • Per $d$ piccoli ($5 \le d < 200$), verificano le disuguaglianze numericamente.

3. Contributi Chiave

1. Risoluzione della Congettura per Ogni $d$: Il lavoro dimostra che $c_d = c^*_d$ per ogni dimensione $d \ge 1$. Ciò conferma che il sottoinsieme senza somme ottimale è effettivamente la fetta definita dall'iperpiano $\sum x_i \in [u^*_d n, 2u^*_d n)$.
2. Teorema Generale di Miscelabilità Congiunta: La dimostrazione del Teorema 1.5 è un contributo significativo alla teoria della probabilità e alla combinatoria. Stabilisce che le distribuzioni uniformi sulle fette discrete di un ipercubo che sommano a una costante sono miscelabili congiuntamente, un risultato che generalizza le scoperte precedenti per specifiche basse dimensioni.
3. Raffinamento dell'Approccio Lepsveridze-Sun: Gli autori generalizzano il metodo utilizzato per $d=3,4$ a dimensioni arbitrarie, superando la complessità della costruzione di accoppiamenti in dimensioni superiori attraverso un rigoroso argomento induttivo di punto fisso.

4. Risultati Principali

• Teorema 1.1: Per ogni $d \ge 1$ e per ogni sottoinsieme senza somme $S \subseteq [n+1]^d$, la dimensione è limitata da:
  $$|S| \le c^*_d n^d + O(n^{d-1})$$
  dove $c^*_d$ è il volume massimo della fetta $S_d(u) = \{x \in [0,1]^d : u \le \sum x_i < 2u\}$.
• Corollario: La densità limite è esattamente il volume della fetta ottimale, risolvendo la congettura naturale posta da Cameron, Green e altri.

5. Significato ed Estensioni

• Teoria dei Numeri Combinatoria: Questo risultato risolve un problema aperto di lunga data riguardante la struttura degli insiemi senza somme in reticoli di alta dimensione. Conferma che la costruzione "a fetta" è universalmente ottimale, non solo per basse dimensioni.
• Metodi Probabilistici: Il lavoro dimostra la potenza della miscelabilità congiunta e delle tecniche di accoppiamento nella risoluzione di problemi combinatori estremali. La costruzione induttiva di accoppiamenti tramite teoremi di punto fisso è una tecnica nuova e robusta.
• Insiemi Convessi Generali: Gli autori discutono brevemente se questa ottimalità "a fetta" valga per insiemi convessi generali. Forniscono un controesempio (Proposizione 5.1) che mostra che per $d$ sufficientemente grande, esistono insiemi convessi in cui il più grande sottoinsieme senza somme non è una singola fetta definita da un funzionale lineare. Ciò evidenzia che la simmetria dell'ipercubo è cruciale per l'ottimalità della fetta.
• Problema Aperto: Il lavoro lascia aperta la questione se l'ottimalità della fetta valga per tutti gli insiemi convessi limitati in dimensione $d=2$.

In sintesi, questo lavoro fornisce una soluzione completa alla densità asintotica del più grande sottoinsieme senza somme in un cubo reticolare, unificando risultati parziali precedenti e introducendo potenti strumenti probabilistici per gestire dimensioni arbitrarie.