The Hofstadter consecutive-sum sequence omits infinitely many positive integers

Este artigo demonstra que a sequência de Hofstadter de somas consecutivas omite infinitos inteiros positivos, resolvendo uma conjectura do OEIS ao estabelecer limites assintóticos para o crescimento da sequência.

O essencial

Imagine que você tem uma fila de amigos, começando apenas com dois: o 1 e o 2. A regra do jogo é simples, mas viciante: para encontrar o próximo número da fila, você deve olhar para trás, pegar dois ou mais números que já estão na fila (que estejam um ao lado do outro) e somá-los.

O segredo é que você deve escolher o menor número possível que ainda não está na fila e que possa ser formado dessa maneira.

Vamos ver como a fila cresce:

• Começa: 1, 2.
• O próximo? 1+2 = 3. Fila: 1, 2, 3.
• O próximo? 2+3 = 5 (não pode ser 4, porque 4 não é soma de vizinhos). Fila: 1, 2, 3, 5.
• O próximo? 1+2+3 = 6. Fila: 1, 2, 3, 5, 6.
• E assim por diante: 1, 2, 3, 5, 6, 8, 10, 11...

Percebeu o que aconteceu? O número 4 não apareceu. Nem o 7, nem o 9. Eles ficaram de fora.

O Mistério de Hofstadter

Há décadas, o famoso matemático Douglas Hofstadter fez uma pergunta sobre essa sequência: "Será que, conforme a fila cresce infinitamente, ela acaba pegando quase todos os números inteiros, deixando apenas alguns poucos de fora? Ou será que ela deixa de fora uma quantidade infinita de números?"

A maioria das pessoas achava que a fila era "gorda" e pegava quase tudo, deixando apenas buracos pequenos e raros.

A Descoberta de Quanyu Tang

O matemático Quanyu Tang, neste novo artigo, chegou e disse: "Não, a fila é muito mais 'magra' do que pensávamos. Ela deixa de fora infinitos números!"

Ele provou que, quanto mais a sequência avança, mais ela se afasta da linha reta dos números naturais (1, 2, 3, 4, 5...). Em vez de seguir o ritmo "um número para cada passo", ela começa a dar "pulos" cada vez maiores.

A Analogia do Trem:
Imagine que os números inteiros são estações de trem (Estação 1, Estação 2, Estação 3...).

• A sequência de Hofstadter é um trem que para em algumas estações.
• No início, o trem para em quase todas as estações (1, 2, 3, 5, 6...).
• Mas Tang provou que, com o tempo, o trem começa a pular estações inteiras. Ele para na Estação 100, depois pula direto para a Estação 150, depois para a 220, e assim por diante.
• Isso significa que existem infinitas estações onde o trem nunca para. O "espaço vazio" entre as paradas cresce sem fim.

Como ele provou isso? (Sem matemática chata)

Tang usou duas ideias principais, como se fossem ferramentas de detetive:

1. O Detetive da "Soma de Vizinhos": Ele mostrou que, para um número ser escolhido pela sequência, ele precisa ser formado somando vizinhos. Ele descobriu que certos números (especialmente potências de 2, como 4, 8, 16, 32) são "difíceis de formar" dessa maneira. À medida que a sequência cresce, ela é forçada a pular esses números difíceis, criando buracos cada vez maiores.
2. A Regra do "Crescimento Explosivo": Ele usou uma ferramenta moderna da matemática (chamada de teoria aditiva combinatória) para mostrar que, se a sequência tentasse preencher todos os números, ela violaria uma lei fundamental sobre como conjuntos de números se organizam. Como essa lei não pode ser violada, a única saída é que a sequência precisa pular números.

O Resultado Quantitativo (O "Quão rápido?")

Além de provar que existem infinitos buracos, Tang também calculou quão rápido a sequência cresce.
Ele mostrou que o $n$-ésimo número da sequência é menor do que uma certa potência de $n$ (algo como $n$ elevado a 1,66).
Isso é importante porque, antes disso, ninguém sabia se a sequência crescia de forma linear (como uma linha reta) ou se explodia para o infinito de forma descontrolada. Agora sabemos que ela cresce de forma "polinomial" (controlada, mas acelerada).

Por que isso importa?

Este artigo resolve um quebra-cabeça antigo (o problema A005243 no banco de dados de sequências matemáticas).

• Antes: Achávamos que a sequência era "quase completa".
• Agora: Sabemos que ela é "cheia de buracos infinitos".

É como se tivéssemos pensado que uma rede de pesca capturava quase todos os peixes do oceano, e descobríssemos, na verdade, que a rede tem buracos tão grandes que a maioria dos peixes grandes escapa. A matemática é cheia de surpresas onde o que parece óbvio no começo (que a fila enche tudo) se revela falso quando olhamos para o horizonte distante.

Resumo em uma frase: A sequência de Hofstadter não é um tapete contínuo de números; é um tapete com furos infinitos, e o autor provou exatamente como esses furos se formam e crescem.

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "THE HOFSTADTER CONSECUTIVE-SUM SEQUENCE OMITS INFINITELY MANY POSITIVE INTEGERS", de Quanyu Tang, apresentado em português.

1. O Problema

O artigo aborda o comportamento assintótico da sequência de Hofstadter de soma consecutiva, definida como a sequência estritamente crescente $(a_n)_{n \ge 1}$ gerada de forma "gananciosa" (greedy).

• Definição: Começa com $a_1 = 1$ e $a_2 = 2$. Para $k \ge 3$, $a_k$ é o menor inteiro estritamente maior que $a_{k-1}$ que pode ser escrito como a soma de pelo menos dois termos consecutivos anteriores da sequência.
• Contexto: Esta sequência é identificada como A005243 na OEIS (On-Line Encyclopedia of Integer Sequences).
• A Conjectura: Embora a sequência pareça conter "a maioria" dos inteiros, observa-se que ela omite números como 4, 7, 9, 12, etc. A questão central, levantada por Hofstadter e registrada em várias fontes (incluindo o site de problemas de Erdős), é: A sequência omite infinitos inteiros positivos?
• Objetivo: Resolver a Conjectura 1.2 da OEIS, que afirma que a sequência omite infinitos inteiros, e fornecer limites superiores quantitativos para o crescimento de $a_n$.

2. Metodologia

O autor desenvolve uma prova que combina teoria dos números, análise combinatória aditiva e propriedades de sequências recursivas. A abordagem é dividida em duas partes principais:

A. Limites Qualitativos (Prova da Omissão Infinita)

O autor generaliza o problema para qualquer "semente" inicial finita de inteiros positivos. Define $b_n = a_n - n$, que mede o "excesso" do termo sobre seu índice.

1. Monotonicidade: Demonstra-se que a sequência $(b_n)$ é não decrescente para $n$ suficientemente grande.
2. Argumento por Contradição: Assume-se que $(b_n)$ é limitada. Isso implicaria que, para $n$ grande, $a_n$ se comportaria linearmente ($a_n = n + B$).
3. Análise de Potências de 2: Sob a hipótese de linearidade, o autor analisa como grandes potências de 2 (que não podem ser somas de inteiros consecutivos positivos, conforme o Lema 2.1) apareceriam na sequência.
4. Equação Diofantina: A representação de potências de 2 como somas de termos consecutivos leva a uma equação da forma $v^2 + v + E = 2^k$.
5. Teorema de Schinzel-Tijdeman: Utiliza-se um resultado profundo de Schinzel e Tijdeman (Corolário 2.3), que afirma que equações polinomiais do tipo $P(v) = y^k$ têm apenas um número finito de soluções inteiras para $k > 2$.
6. Conclusão: Como a equação teria infinitas soluções sob a hipótese de linearidade, e o teorema garante que só há finitas, a hipótese é falsa. Logo, $b_n \to \infty$, provando que $a_n$ cresce mais rápido que $n$ e, portanto, omite infinitos inteiros.

B. Limites Quantitativos (Limites Superiores Polinomiais)

Para a sequência clássica ($a_1=1, a_2=2$), o autor estabelece um limite superior polinomial para $a_n$.

1. Enumeração Gananciosa: Demonstra-se que a sequência $(a_n)$ é essencialmente a enumeração crescente de todos os inteiros que podem ser escritos como soma de termos consecutivos.
2. Conexão com Conjuntos Convexos: Define-se o conjunto de somas parciais $S_m = \{s_0, s_1, \dots, s_m\}$. O autor observa que este conjunto é convexo (as diferenças consecutivas são estritamente crescentes).
3. Diferenças de Conjuntos: A quantidade de inteiros representáveis até um certo ponto está relacionada ao tamanho do conjunto de diferenças $S_m - S_m$.
4. Teorema de Bloom: Aplica-se um limite inferior recente de Bloom para o tamanho do conjunto de diferenças de conjuntos convexos finitos: $|A - A| \gg |A|^{6681/4175 - \eta}$.
5. Recursão e Iteração: Combina-se o crescimento do número de inteiros representáveis com a definição gananciosa da sequência para obter uma relação de recorrência. A iteração dessa relação leva a um limite superior polinomial para $a_n$.

3. Principais Resultados

• Teorema 1.4 (Generalização): Para qualquer semente inicial finita de inteiros positivos, a sequência gerada omite infinitos inteiros. Mais especificamente, a sequência $(b_n = a_n - n)$ é não decrescente e ilimitada.
• Corolário 1.5: Consequentemente, $a_n = n + \omega(1)$, confirmando a Conjectura 1.2 da OEIS para a sequência clássica.
• Teorema 1.6 (Limite Superior): Para a sequência clássica, para todo $\epsilon > 0$, existe uma constante $C_\epsilon$ tal que:
  $$a_n \ll_\epsilon n^{4175/2506 + \epsilon}$$
  O expoente $4175/2506 \approx 1.666$. Este é o primeiro limite superior polinomial conhecido para este problema.

4. Significado e Contribuições

1. Resolução de um Problema Aberto: O artigo resolve definitivamente a questão de longa data sobre se a sequência de Hofstadter omite infinitos inteiros, confirmando a intuição numérica e a conjectura da OEIS.
2. Generalização: O resultado qualitativo não se limita à semente $(1, 2)$, mas aplica-se a qualquer semente finita de inteiros positivos, mostrando a robustez do fenômeno.
3. Avanço Quantitativo: Antes deste trabalho, não havia limites superiores polinomiais conhecidos para o crescimento de $a_n$. O autor fornece um limite explícito, embora reconheça que o expoente obtido ($\approx 1.666$) provavelmente não é ótimo.
4. Conexão Interdisciplinar: O trabalho conecta a teoria das sequências auto-geradas com resultados avançados de combinatória aditiva (limites de conjuntos de diferenças de conjuntos convexos) e teoria dos números (equações diofantinas de Schinzel-Tijdeman).
5. Observações Numéricas: O autor apresenta dados computacionais sugerindo que o crescimento real de $b_n$ (o número de omissões) pode ser da ordem de $n^\alpha$ com $1/5 < \alpha < 1/2$, possivelmente próximo a$1/3$, indicando que o limite superior polinomial atual é uma estimativa conservadora e que a sequência pode crescer quase linearmente.

Em suma, o artigo transforma um problema heurístico sobre uma sequência específica em um resultado rigoroso sobre a estrutura de sequências ganancianas, utilizando ferramentas profundas da matemática moderna para estabelecer tanto a existência de omissões infinitas quanto limites de crescimento.