Small complete 3-term progression free sets in cyclic groups and vector spaces

Resumo Técnico: Conjuntos Pequenos de Progressões de 3 Termos Livres de Completude em Grupos Cíclicos e Espaços Vetoriais

Enunciado do Problema
O artigo aborda o problema de determinar o tamanho mínimo de um conjunto completo livre de progressões aritméticas de 3 termos (3-AP) em estruturas algébricas, especificamente grupos cíclicos ($\mathbb{Z}_m$) e espaços vetoriais finitos ($\mathbb{F}_p^n$). Enquanto o tamanho máximo de conjuntos livres de 3-AP é um tema central na combinatória aditiva (ex: teorema de Roth, Croot-Lev-Pach, Ellenberg-Gijswijt), o tamanho mínimo de um conjunto completo (um conjunto que não pode ser ampliado sem criar uma 3-AP) representa o análogo de limite inferior. Um argumento de contagem simples estabelece que a ordem de magnitude para este tamanho mínimo é de pelo menos a raiz quadrada da cardinalidade da estrutura. Os autores investigam se este limite inferior é apertado, abordando problemas abertos sobre a existência de tais conjuntos com tamanho $O(\sqrt{|G|})$ em grupos cíclicos e $p^{n/2}$ em espaços vetoriais.

Metodologia
Os autores empregam uma combinação de construções combinatórias explícitas, técnicas de redução modular e geometria algébrica sobre corpos finitos.

1. Grupos Cíclicos ($\mathbb{Z}_m$):

   • Propriedade Mais Forte: Os autores focam em conjuntos completos (2, -1)-evitadores. Um conjunto $A$ é (2, -1)-evitador se $A \cap (2A \dot{-} A) = \emptyset$ (onde $2A \dot{-} A = \{2a - b : a, b \in A, a \neq b\}$). Um conjunto é completo se $G = A \cup (2A \dot{-} A)$. Esta propriedade é mais forte do que ser livre de 3-AP completo, pois força cada ponto externo a ser uma extremidade de uma progressão com extremidades em $A$, em vez de permitir que o ponto externo seja um ponto médio.
   • Conjuntos R-Completos: A construção baseia-se em conjuntos "R-completos" — subconjuntos inteiros de $[0, R]$ que são internamente (2, -1)-evitadores e saturam o intervalo $[-R, 2R]$.
   • Construção de Dígito Binário: Usando uma construção de dígito binário generalizada (Lema 3.3), os autores geram conjuntos $P$ de tamanho $2^n$ que são $S_n$-completos. Ao escolher cuidadosamente a sequência de dígitos $d_i$, eles garantem que o conjunto resultante cubra uma ampla gama de módulos $m$.
   • Redução Modular: O Lema 3.2 demonstra que um conjunto $R$-completo em $\mathbb{Z}$ desce para um conjunto completo (2, -1)-evitador em $\mathbb{Z}_m$ sempre que $2R < m \leq 3R + 1$.
   • Verificação Finita: Para módulos pequenos ($m < 81$) onde a construção geral não se aplica ou onde conjuntos completos (2, -1)-evitadores podem não existir, os autores realizam uma enumeração exaustiva para determinar tamanhos mínimos exatos.

2. Espaços Vetoriais ($\mathbb{F}_p^n$):

   • Gráficos Quadráticos: A construção central utiliza gráficos de aplicações quadráticas homogêneas $Q: U \to W$. Especificamente, eles constroem conjuntos da forma $A_Q = \{(u, Q(u)) : u \in U\}$.
   • Completude Extremidade-Ponto Médio: Os autores definem conjuntos "completos extremidade-ponto médio", onde todo ponto externo pode ser representado tanto como uma extremidade ($x = 2a - b$) quanto como um ponto médio ($2x = c + d$) de uma progressão formada por elementos em $A$. Esta propriedade é crucial para a construção de produto.
   • Construção de Subcampo: Eles constroem uma aplicação quadrática $Q(x, s) = x^2 - \delta s^2$ sobre um corpo de extensão $E = \mathbb{F}_{p^{kL}}$ e um subcampo $T = \mathbb{F}_{p^k}$, onde $\delta$ é um não-quadrado. Usando somas de caracteres e a cota de Weil, eles provam que esta aplicação é sobrejetora e possui um núcleo trivial, resultando em um conjunto completo (2, -1)-evitador em uma dimensão específica $n_0 = k(2L+1)$.
   • Lema de Produto: Para estender o resultado para todas as dimensões $n$, eles utilizam um lema de produto (Lema 4.2). Se $A$ é extremidade-ponto médio completo em um subespaço e $B$ é livre de 3-AP completo nas coordenadas restantes, o produto $A \times B$ é livre de -3-AP completo no espaço total. Isso permite o "preenchimento" (padding) das dimensões especiais com conjuntos menores para cobrir $n$ arbitrários.

Principais Contribuições e Resultados

1. Grupos Cíclicos:

   • Teorema 1.2: Para todo inteiro $m \geq 1$, existe um conjunto livre de 3-AP completo $A \subseteq \mathbb{Z}_m$ com tamanho $|A| < 2\sqrt{m}$.
   • Resultado Mais Forte para Grandes $m$: Para $m \geq 81$, o conjunto construído satisfaz a propriedade mais forte de ser (2, -1)-evitador completo.
   • Pequenos Módulos: O artigo fornece uma tabela de valores exatos para $a(3\text{-AP}, \mathbb{Z}_m)$ e $a(2, -1)(\mathbb{Z}_m)$ para $m \leq 80$, observando que conjuntos completos (2, -1)-evitadores não existem para certos módulos pequenos (ex: $m \in \{2, 5, 6, 8, 17, 18, 19, 20\}$).

2. Espaços Vetoriais:

   • Teorema 1.3: Para cada primo ímpar fixo $p$ e $\epsilon > 0$, existe uma constante $C_{p,\epsilon}$ tal que para todo $n \geq 1$:
     $$a(3\text{-AP}, \mathbb{F}_p^n) \leq C_{p,\epsilon} n^{1+\epsilon} p^{n/2} = p^{n/2 + o(n)}$$
   • Este resultado resolve a variante de espaço vetorial no sentido de que o expoente de $p$ é exatamente $n/2$, correspondendo ao limite inferior até um fator sub-exponencial.

Significância e Alegações
O artigo afirma resolver dois problemas abertos sobre a densidade do limite inferior da raiz quadrada para conjuntos livres de progressões completos:

• Grupos Cíclicos: Estabelece que o limite inferior é apertado até uma constante absoluta (especificamente 2) para todos os grupos cíclicos, e fornece construções explícitas para a propriedade mais forte de ser (2, -1)-evitador para $m \geq 81$.
• Espaços Vetoriais: Resolve a versão de expoente do problema para corpos de primos ímpares fixos, mostrando que o tamanho mínimo é $p^{n/2 + o(n)}$. Isso confirma que o limite trivial de contagem é essencialmente nítido em termos de taxa de crescimento exponencial.

Os autores observam que, embora a constante do resultado do grupo cíclico ($2$) esteja acima do alvo de $3/2$ sugerido em seu trabalho anterior, a construção é deliberadamente restrita à propriedade mais forte de ser (2, -1)-evitador. Eles sugerem que explorar a liberdade adicional da completude 3-AP padrão (permitindo que pontos externos sejam pontos médios) pode resultar em construções menores. Da mesma forma, para espaços vetoriais, a questão de uma constante absoluta uniforme independente de $n$ e a existência de tais limites para conjuntos completos (2, -1)-evitadores em cada dimensão permanecem abertas. O trabalho conecta esses problemas de combinatória aditiva à geometria finita, especificamente aos caps completos e conjuntos saturantes.