The greedy 3-sumfree sequence $S_{1,g,g+1}$

Resumo Técnico: A Sequência Gulosa 3-Sumfree $S_{1,g,g+1}$

Enunciado do Problema
O artigo aborda a caracterização da sequência gulosa 3-sumfree $S_{x,y,z}$, definida como a sequência crescente de inteiros positivos que começa com $x, y, z$, onde cada termo subsequente é o menor inteiro maior que o termo precedente que não pode ser expresso como a soma de três termos distintos anteriores. Especificamente, os autores investigam a sequência $S_{1,g,g+1}$ para cada inteiro $g \ge 2$. Embora Bosma et al. [1] tivessem estabelecido descrições explícitas para casos pequenos específicos ($g=2, 3, 4$) usando o provador de teoremas automático Walnut e conjecturado uma fórmula uniforme para todos os $g \ge 2$, uma prova geral permanecia em aberto.

Metodologia
Os autores empregam um argumento direto de soma de intervalos em vez de depender de prova automática de teoremas. A metodologia procede da seguinte forma:

1. Definição do Conjunto Candidato ($A_g$): O artigo define um conjunto específico $A_g$ baseado em aritmética modular. Seja $m = 10g + 3$, $e = 2g + 1$ e $f = 6g + 1$. O conjunto $A_g$ consiste nos termos iniciais $\{1, e, f\}$ e uma união de intervalos periódicos $I_k$ e $J_k$ para $k \ge 0$, definidos como:

   • $I_k = km + [g, 2g]$
   • $J_k = km + [6g + 2, 7g + 1]$
     O conjunto $A_g$ é construído para ser a união desses componentes disjuntos.

2. Redução a Duas Proposições: A prova de que $S_{1,g,g+1} = A_g$ é reduzida à verificação de duas propriedades relativas à natureza "forçada" de inteiros (um inteiro é forçado se for a soma de três elementos distintos do conjunto):

   • Proposição 2: Todo inteiro $n > g + 1$ que não está em $A_g$ é forçado (ou seja, pode ser escrito como uma soma de três elementos distintos de $A_g$).
   • Proposição 3: Nenhum elemento dentro de $A_g$ é forçado (ou seja, nenhum elemento de $A_g$ pode ser escrito como uma soma de três elementos distintos de $A_g$).

3. Aritmética de Intervalos: O núcleo da prova envolve o cálculo das somas de conjuntos dos intervalos definidos. Usando identidades elementares para as somas de conjuntos de intervalos (por exemplo, $b_3[u, v] = [3u+3, 3v-3]$), os autores demonstram que as lacunas em $A_g$ são exatamente cobertas por somas de três elementos distintos de $A_g$, enquanto as somas de três elementos de $A_g$ sempre caem no complemento de $A_g$ (especificamente, um padrão de complemento periódico $C$).

4. Verificação Indutiva: Os autores usam indução sobre $n$ para mostrar que a regra gulosa admite exatamente os elementos de $A_g$. Se $n \notin A_g$, ele é forçado por elementos menores que $n$ (que estão na sequência pelo processo indutivo), portanto é excluído. Se $n \in A_g$, ele não é forçado por elementos menores que $n$, portanto é admitido.

Principais Resultados
O artigo estabelece o Teorema 1, que fornece uma caracterização exata da sequência $S_{1,g,g+1}$ para todos os $g \ge 2$:
Um inteiro $z$ pertence a $S_{1,g,g+1}$ se, e somente se:
$$z \in \{1, 2g + 1, 6g + 1\} \quad \text{ou} \quad z \pmod{10g + 3} \in [g, 2g] \cup [6g + 2, 7g + 1].$$

O artigo detalha ainda a estrutura da sequência:

• Termos Iniciais: A sequência começa com $1, g, g+1, \dots, 2g, 2g+1, 6g+1$.
• Periodicidade Eventual: Após os primeiros $g+4$ termos, a sequência torna-se periódica módulo $m = 10g + 3$.
• Estrutura do Período: O bloco repetitivo tem um comprimento de $2g + 1$ e consiste nos resíduos:
  $$6g + 2, 6g + 3, \dots, 7g + 1, g, g + 1, \dots, 2g.$$

Significância e Alegações
O artigo afirma fornecer uma prova direta da conjectura formulada por Bosma, Bruin, Fokkink, Grube, Reuijl e Tromp [1]. Embora a conjectura tenha sido verificada mecanicamente para $2 \le g \le 10$, este trabalho estende o resultado para todos os inteiros $g \ge 2$ através de meios analíticos. Os autores declaram explicitamente que sua abordagem produz uma "prova direta" usando argumentos de soma de intervalos, contrastando com os métodos computacionais usados no trabalho anterior. O artigo também fornece uma descrição explícita completa da periodicidade eventual, incluindo tanto o pré-período quanto o bloco repetitivo, resolvendo inteiramente a estrutura da sequência.