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 . Estendi o cálculo exato, provei que a resposta mais simples está errada e descrevi o que resiste.
A pergunta
Para inteiros , considere o conjunto de inteiros
Cada elemento vem de uma sequência estritamente decrescente de expoentes. Nenhum desses números é divisível por 3; são unidades 3-ádicas. A pergunta é de cobertura: fixada uma precisão , quando é que , reduzido módulo , atinge todas as unidades?
Chame de o menor para o qual isso acontece: o orçamento de cobertura. O conjunto tem elementos, cerca de , e só por contagem seriam necessários 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
se a conjectura vale, cresce mais devagar do que qualquer função linear de .
A tabela até ℓ = 23
Um manuscrito meu anterior, não publicado, tinha os valores exatos de até . O preprint leva a tabela a . 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.
| ℓ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| j*(ℓ) | 1 | 4 | 6 | 7 | 9 | 10 | 11 | 12 | 13 | 15 | 16 | 17 |
| e(ℓ) | 0,21 | 2,42 | 3,62 | 3,83 | 5,04 | 5,25 | 5,45 | 5,66 | 5,87 | 7,08 | 7,28 | 7,49 |
| ℓ | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| j*(ℓ) | 18 | 19 | 20 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| e(ℓ) | 7,70 | 7,91 | 8,11 | 7,32 | 7,53 | 7,74 | 7,94 | 8,15 | 8,36 | 8,57 | 8,77 |
Resultados, por situação
Evidência computacional
Tabela exata de para . Os valores até reproduzem o manuscrito anterior e foram recalculados em Rust; foi conferido por uma implementação independente em Python.
Os níveis e vêm de uma única implementação. O preprint diz isso com todas as letras.
Seção 2 e Tabela 1
Demonstrado
para , e, sem condição alguma,
Um modelo em que o excesso é constante está, portanto, descartado.
Condicional
A melhor cota superior obtida:
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 , 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 o conjunto dos resíduos ainda não cobertos no orçamento . Para ,
Daí sai uma cota superior recursiva para , exata em uma faixa demonstrada e empiricamente exata além dela.
Seção 6
Demonstrado
Sempre que , todo último resíduo a ser coberto é ; 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 , 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 .
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.