On the largest sum-free subset of the lattice cube

1. Formulação do Problema

O artigo aborda o problema de determinar a densidade assintótica do maior subconjunto sem soma dentro de um cubo de rede $d$-dimensional.

• Definições: Um subconjunto $S$ de um grupo abeliano é sem soma se não existirem $x, y, z \in S$ tais que $x + y = z$. Os autores estudam subconjuntos do cubo de rede $[n+1]^d = \{0, 1, \dots, n\}^d$.
• Objetivo: Determinar o limite $c_d = \lim_{n \to \infty} \frac{|S|}{n^d}$, onde $S$ é o maior subconjunto sem soma.
• Contexto:
  • Para $d=1$, é bem conhecido que $c_1 = 1/2$.
  • Para $d=2$, Elsholtz e Rackham provaram que $c_2 = 3/5$.
  • Para $d=3, 4$, Lepsveridze e Sun resolveram recentemente os casos.
  • A Conjectura: Conjecturou-se que, para todo $d$, o conjunto ótimo é uma "fatia" do cubo definida por um hiperplano. Especificamente, o conjunto $S^* = \{x \in [n+1]^d \mid u \le \sum x_i < 2u\}$, onde $u$ é escolhido para maximizar o volume da fatia, produz a densidade máxima.
  • Seja $c^*_d$ o volume máximo de tal fatia no limite contínuo $[0,1]^d$. A conjectura afirma que $c_d = c^*_d$.

2. Metodologia

A prova segue a abordagem estabelecida por Lepsveridze e Sun, utilizando uma combinação de dualidade de programação linear e acoplamento probabilístico (misturabilidade conjunta).

A. Redução à Programação Linear

O problema de limitar $|S|$ é reformulado como um programa linear (PL).

• Problema Primal: Maximizar $\sum |S(x)|$ (onde $S(x)$ são as fibras do conjunto $S$) sujeito à restrição de que, para quaisquer $x, y, z$ com $x+y=z$, $|S(x)| + |S(y)| + |S(z)| \le 2(n+1)$.
• Problema Dual: Para encontrar um limite superior, deve-se construir uma solução viável (pesos) para o PL dual. A existência de tais pesos depende da capacidade de acoplar distribuições de probabilidade específicas.

B. Misturabilidade Conjunta

A inovação técnica central é a prova de um resultado de Misturabilidade Conjunta.

• Definição: Distribuições $\mu_1, \mu_2, \mu_3$ são misturáveis conjuntamente se existe um acoplamento $(X_1, X_2, X_3)$ com essas marginais tal que $X_1 + X_2 + X_3 = \mathbb{E}[X_1] + \mathbb{E}[X_2] + \mathbb{E}[X_3]$ quase certamente.
• O Teorema Chave (Teorema 1.5): Os autores provam que, para quaisquer inteiros não negativos $r, s, t$ tais que $r+s+t = dn$, as distribuições uniformes nas fatias discretas $L_d(r), L_d(s), L_d(t)$ (onde $L_d(k) = \{x \in [n+1]^d : \sum x_i = k\}$) são misturáveis conjuntamente.
• Técnica de Prova:
  • Indução em $d$: O caso base $d=2$ depende de resultados conhecidos sobre intervalos e desigualdades triangulares.
  • Passo Indutivo ($d \ge 3$): Os autores constroem um acoplamento para as primeiras coordenadas usando um argumento de ponto fixo (Teorema do Ponto Fixo de Brouwer ou Perron-Frobenius). Eles definem uma aplicação no espaço de distribuições de probabilidade sobre o suporte das primeiras coordenadas e mostram que um ponto fixo existe. Este ponto fixo garante que as marginais correspondam às distribuições uniformes requeridas nas fatias, permitindo que a hipótese indutiva seja aplicada às coordenadas restantes $d-1$.

C. Construção de Pesos e Estimativas de Fatias

Para aplicar a misturabilidade conjunta ao PL dual:

1. Particionamento: O domínio $[n+1]^{d-1}$ é particionado em cinco conjuntos ($A, B, C, D, E$) com base na soma das coordenadas em relação ao parâmetro da fatia ótima $u^*_d$.
2. Função de Peso: Usando o resultado de misturabilidade conjunta, os autores constroem uma função de peso $w(x,y,z)$ suportada em triplas específicas desses conjuntos.
3. Estimativas Analíticas: Eles utilizam propriedades de log-cavidade da função densidade de probabilidade da soma de variáveis aleatórias uniformes (distribuição de Irwin-Hall). Eles derivam limites explícitos sobre as razões dos volumes das fatias (Lema 3.1) para garantir que os pesos construídos satisfaçam as restrições duais.
   • Para $d$ grande, eles utilizam estimativas de grandes desvios.
   • Para $d$ pequeno ($5 \le d < 200$), eles verificam as desigualdades numericamente.

3. Contribuições Principais

1. Resolução da Conjectura para Todo $d$: O artigo prova que $c_d = c^*_d$ para todas as dimensões $d \ge 1$. Isso confirma que o subconjunto sem soma ótimo é de fato a fatia definida pelo hiperplano $\sum x_i \in [u^*_d n, 2u^*_d n)$.
2. Teorema Geral de Misturabilidade Conjunta: A prova do Teorema 1.5 é uma contribuição significativa para a teoria da probabilidade e combinatória. Estabelece que distribuições uniformes em fatias discretas de um hipercubo que somam uma constante são misturáveis conjuntamente, um resultado que generaliza achados anteriores para dimensões baixas específicas.
3. Refinamento da Abordagem Lepsveridze-Sun: Os autores generalizam o método usado para $d=3,4$ para dimensões arbitrárias, superando a complexidade de construir acoplamentos em dimensões mais altas através de um rigoroso argumento indutivo de ponto fixo.

4. Resultados Principais

• Teorema 1.1: Para qualquer $d \ge 1$ e qualquer subconjunto sem soma $S \subseteq [n+1]^d$, o tamanho é limitado por:
  $$|S| \le c^*_d n^d + O(n^{d-1})$$
  onde $c^*_d$ é o volume máximo da fatia $S_d(u) = \{x \in [0,1]^d : u \le \sum x_i < 2u\}$.
• Corolário: A densidade limite é exatamente o volume da fatia ótima, resolvendo a conjectura natural proposta por Cameron, Green e outros.

5. Significado e Extensões

• Teoria dos Números Combinatória: Este resultado resolve um problema aberto de longa data sobre a estrutura de conjuntos sem soma em redes de alta dimensão. Confirma que a construção de "fatia" é universalmente ótima, não apenas para baixas dimensões.
• Métodos Probabilísticos: O artigo demonstra o poder da misturabilidade conjunta e de técnicas de acoplamento na resolução de problemas combinatórios extremos. A construção indutiva de acoplamentos via teoremas de ponto fixo é uma técnica nova e robusta.
• Conjuntos Convexos Gerais: Os autores discutem brevemente se essa optimalidade de "fatia" vale para conjuntos convexos gerais. Eles fornecem um contraexemplo (Proposição 5.1) mostrando que, para $d$ suficientemente grande, existem conjuntos convexos onde o maior subconjunto sem soma não é uma única fatia definida por um funcional linear. Isso destaca que a simetria do hipercubo é crucial para a optimalidade da fatia.
• Problema Aberto: O artigo deixa em aberto a questão de saber se a optimalidade da fatia vale para todos os conjuntos convexos limitados na dimensão $d=2$.

Em resumo, este artigo fornece uma solução completa para a densidade assintótica do maior subconjunto sem soma em um cubo de rede, unificando resultados parciais anteriores e introduzindo ferramentas probabilísticas poderosas para lidar com dimensões arbitrárias.