Renato Augusto Tavares
English

A Conjectura da Cobertura Fraca

Na monografia de 1998, Wirsching perguntou quão grande um certo conjunto de somas de potências de 2 e de 3 precisa ser para atingir todos os resíduos módulo 3ℓ3^\ell. Estendi o cálculo exato, provei que a resposta mais simples está errada e descrevi o que resiste.

A pergunta

Para inteiros j,k≥0j, k \ge 0, considere o conjunto de inteiros

Rj,k={∑i=0j2ai3i:j+k≥a0>a1>⋯>aj≥0}.R_{j,k} = \left\{ \sum_{i=0}^{j} 2^{a_i} 3^{i} \;:\; j + k \ge a_0 > a_1 > \cdots > a_j \ge 0 \right\}.

Cada elemento vem de uma sequência estritamente decrescente de j+1j+1 expoentes. Nenhum desses números é divisível por 3; são unidades 3-ádicas. A pergunta é de cobertura: fixada uma precisão ℓ\ell, quando é que Rj−1,jR_{j-1,j}, reduzido módulo 3ℓ3^\ell, atinge todas as 2·3ℓ−12 \cdot 3^{\ell-1} unidades?

Chame de j∗(ℓ)j^*(\ell) o menor jj para o qual isso acontece: o orçamento de cobertura. O conjunto Rj−1,jR_{j-1,j} tem (2jj)\binom{2j}{j} elementos, cerca de 4j4^j, e só por contagem seriam necessários j≈ℓlog4⁡3j \approx \ell \log_4 3 termos. A Conjectura da Cobertura Fraca (Conjectura V.3.9 da monografia) pede que o tamanho necessário exceda essa contagem por um fator apenas subexponencial. Em termos do excesso

e(ℓ)=j∗(ℓ)−ℓlog4⁡3,e(\ell) = j^*(\ell) - \ell \log_4 3 ,

se a conjectura vale, e(ℓ)e(\ell) cresce mais devagar do que qualquer função linear de ℓ\ell.

A tabela até ℓ = 23

Um manuscrito meu anterior, não publicado, tinha os valores exatos de j∗(ℓ)j^*(\ell) até ℓ=20\ell = 20. O preprint leva a tabela a ℓ=23\ell = 23. Cada nível triplica o número de resíduos, e o último exigiu cerca de 263 GiB de estado e 104 horas em um computador de mesa. A engenharia desse cálculo está descrita à parte.

Orçamento de cobertura j*(ℓ) para ℓ de 1 a 23Os 23 valores exatos de j*(ℓ) ficam entre a cota inferior demonstrada j*(ℓ) ≥ ℓ e a cota superior condicional nove oitavos de ℓ mais trinta e três meios, e acima da taxa ℓ log₄ 3 prevista pela contagem.0510152025303540451357911131517192123 ℓ (precisão 3-ádica: resíduos módulo 3^ℓ) ℓ = 1: j*(ℓ) = 1ℓ = 2: j*(ℓ) = 4ℓ = 3: j*(ℓ) = 6ℓ = 4: j*(ℓ) = 7ℓ = 5: j*(ℓ) = 9ℓ = 6: j*(ℓ) = 10ℓ = 7: j*(ℓ) = 11ℓ = 8: j*(ℓ) = 12ℓ = 9: j*(ℓ) = 13ℓ = 10: j*(ℓ) = 15ℓ = 11: j*(ℓ) = 16ℓ = 12: j*(ℓ) = 17ℓ = 13: j*(ℓ) = 18ℓ = 14: j*(ℓ) = 19ℓ = 15: j*(ℓ) = 20ℓ = 16: j*(ℓ) = 20ℓ = 17: j*(ℓ) = 21ℓ = 18: j*(ℓ) = 22ℓ = 19: j*(ℓ) = 23ℓ = 20: j*(ℓ) = 24ℓ = 21: j*(ℓ) = 25ℓ = 22: j*(ℓ) = 26ℓ = 23: j*(ℓ) = 27 ⁹⁄₈ ℓ + ³³⁄₂cota condicional j*(ℓ) calculado ℓcota inferior demonstrada ℓ log₄ 3taxa da contagem
Figura 4. Os 23 valores exatos de j∗(ℓ)j^*(\ell) (pontos), entre a cota inferior demonstrada j∗(ℓ)≥ℓj^*(\ell) \ge \ell e a cota superior condicional (tracejada), e acima da taxa ℓlog4⁡3\ell \log_4 3 que a contagem sozinha prevê (pontilhada). Os dois pontos vazados, ℓ=22\ell = 22 e 2323, não têm verificação cruzada por implementação independente. Dados: Tabela 1 do preprint. A compilação deste site recalcula j∗(ℓ)j^*(\ell) por força bruta para ℓ≤6\ell \le 6 e compara com a tabela.
Orçamento de cobertura j*(ℓ) e excesso e(ℓ) = j*(ℓ) − ℓ log₄ 3
ℓ123456789101112
j*(ℓ)1467910111213151617
e(ℓ)0,212,423,623,835,045,255,455,665,877,087,287,49
Continuação: ℓ de 13 a 23
ℓ1314151617181920212223
j*(ℓ)1819202021222324252627
e(ℓ)7,707,918,117,327,537,747,948,158,368,578,77

Resultados, por situação

Evidência computacional

Tabela exata de j∗(ℓ)j^*(\ell) para ℓ=1,…,23\ell = 1, \dots, 23. Os valores até ℓ=20\ell = 20 reproduzem o manuscrito anterior e foram recalculados em Rust; ℓ=21\ell = 21 foi conferido por uma implementação independente em Python.

Os níveis ℓ=22\ell = 22 e 2323 vêm de uma única implementação. O preprint diz isso com todas as letras.

Seção 2 e Tabela 1

Demonstrado

j∗(ℓ)≥ℓj^*(\ell) \ge \ell para ℓ=2,…,23\ell = 2, \dots, 23, e, sem condição alguma,

e(ℓ)≥14log2⁡ℓ−O(1).e(\ell) \ge \tfrac{1}{4} \log_2 \ell - O(1).

Um modelo em que o excesso é constante está, portanto, descartado.

Condicional

A melhor cota superior obtida:

j∗(ℓ)≤98ℓ+332.j^*(\ell) \le \tfrac{9}{8}\,\ell + \tfrac{33}{2}.

Ela vem de reformular o orçamento como um jogo de payoff médio, e depende de uma correspondência entre o jogo e a cobertura que foi verificada por computador para ℓ=1,…,12\ell = 1, \dots, 12, mas não está provada em geral.

Seção 4; doze certificados armazenados e um verificador independente

Demonstrado

A rota natural por análise de Fourier está bloqueada no primeiro passo: o seu critério de positividade é inalcançável em qualquer orçamento. Mesmo admitindo-o, um cancelamento de raiz quadrada não melhoraria a cota do jogo.

Seção 5

Demonstrado

Inclusão por duplicação. Seja H(ℓ,j)H(\ell, j) o conjunto dos resíduos ainda não cobertos no orçamento jj. Para j≥ℓj \ge \ell,

H(ℓ,j+1)⊆2H(ℓ,j)∩4H(ℓ,j).H(\ell, j+1) \subseteq 2H(\ell, j) \cap 4H(\ell, j).

Daí sai uma cota superior recursiva para j∗(ℓ)j^*(\ell), exata em uma faixa demonstrada e empiricamente exata além dela.

Seção 6

Demonstrado

Sempre que j∗(ℓ)≥ℓ+1j^*(\ell) \ge \ell + 1, todo último resíduo a ser coberto é ≡1(mod⁡3)\equiv 1 \;(\bmod 3); e vale uma lei de contenção em duas classes módulo 9.

Evidência computacional

A comparação de quatro modelos de crescimento para e(ℓ)e(\ell), na cauda da tabela, desfavorece o constante e não distingue entre os crescentes (logarítmico, raiz quadrada, linear lento). São escores de ajuste penalizados, não evidência estatística calibrada.

Seção 3

Evidência computacional

Uma regra natural de “reparo de custo 1”, sugerida pelo teorema da duplicação, é falsa: em dois níveis consecutivos ela falha para 100 de 1458 e para 332 de 4374 casos. Isso não exclui que exista algum custo de reparo limitado.

Em aberto

A Conjectura da Cobertura Fraca e a taxa exata de crescimento de e(ℓ)e(\ell).

O que resiste

A parte mais longa do trabalho é uma tentativa de fechar a distância até a taxa conjecturada, e o registro honesto de por que ela não fecha. A versão ingênua da abordagem por somas exponenciais falha por uma razão que se pode verificar. O passo seguinte foi estudar diretamente os resíduos que demoram a ser cobertos, e é dali que vêm o teorema da duplicação, as restrições de congruência e a regra de reparo que acabou refutada.

Gosto desse tipo de resultado: um teorema sobre a estrutura do obstáculo é menos do que a conjectura, mas não desaparece se a conjectura for decidida por outro caminho.

O que fica em aberto

Além da conjectura em si, o preprint enuncia com precisão duas perguntas mais estreitas que ela, sugeridas pelos cálculos: excluir uma das duas classes módulo 9 e estabelecer uma propriedade de redundância em todas as larguras. Cada uma merece um ataque próprio.