Um cálculo exato com 263 GiB de estado
A tabela de da Conjectura da Cobertura Fraca parava em . Levá-la a multiplica o problema por 27. Este é o registro de como isso coube em um computador de 62 GiB, e do que foi preciso para confiar no resultado.
O problema
É preciso encontrar, para cada precisão , o menor tal que as somas , com expoentes estritamente decrescentes escolhidos entre e , atinjam todas as unidades módulo . Enumerar as somas é inviável: são delas, e para o orçamento é . A enumeração direta deixa de ser tratável depois de .
O algoritmo
O que importa não é a lista de somas, mas o conjunto de resíduos que elas atingem. Esse conjunto cabe em um vetor de bits com posições, e somar uma constante a todos os seus elementos é uma rotação cíclica do vetor.
O programa é uma programação dinâmica do tipo mochila 0/1 sobre os expoentes, percorridos em ordem decrescente. Para cada quantidade de termos já escolhidos há um vetor de bits com os resíduos alcançáveis; considerar um novo expoente é girar cada vetor pelo valor correspondente e fazer um OU com o vetor da camada seguinte. Em Rust, os vetores são Vec<u64>, e cada rotação com OU é repartida entre os núcleos com a biblioteca rayon.
A memória necessária é exata e previsível: bytes.
O custo
| Nível | Estado | Tempo de parede | Observação |
|---|---|---|---|
| ℓ = 1 a 16 | até 0,1 GiB | 6 s | |
| ℓ = 17 a 19 | até 2,7 GiB | 3,5 min | |
| ℓ = 20 | 9 GiB | 10 min | Limite da tabela anterior |
| ℓ = 21 | 27 GiB | 748 s | Cabe na memória física |
| ℓ = 22 | 84 GiB | 10 749 s | Exigiu 500 GiB de swap |
| ℓ = 23 | 263 GiB | 375 615 s | Cerca de 104 horas |
A partir de o estado não cabe na memória física, e o cálculo passa a depender de 500 GiB de memória virtual em disco. O último nível levou mais de quatro dias. Cada orçamento descartado é registrado em um arquivo de progresso, para que um reinício não refaça o que já foi excluído. Não há retomada do estado completo: interromper o processo perde a tentativa em curso.
A tabela para em porque esse é o último nível com resultado completo e verificado. O seguinte pediria cerca de 820 GiB.
Como confiar
Um número que custou 104 horas é exatamente o tipo de número em que não se deve confiar por cansaço. As defesas, em ordem crescente de alcance:
- Enumeração direta para , em um programa que não compartilha nenhum caminho de código com a programação dinâmica.
- Valores de referência para a e uma conferência pontual, em e , em que a imagem é módulo 9 e faltam . Essa validação é o primeiro comando das instruções, antes de qualquer execução longa.
- Uma implementação independente em Python, validada contra a tabela até , que confirma .
- Um lema, com prova, de que nenhum orçamento menor que cobre, o que fecha a busca por baixo sem depender do programa.
Para e não existe verificação cruzada por um segundo programa. O preprint diz isso, e os gráficos marcam esses dois pontos de forma diferente.
O que mais o repositório calcula
O mesmo repositório guarda o restante da parte computacional do artigo, com o custo de cada item declarado: o solucionador do jogo de payoff médio, com doze certificados armazenados (o maior tem 60 MB) e um verificador independente que os reconfere em menos de um minuto; o espectro de somas exponenciais em , que usa 22 GiB; e os conjuntos de resíduos não cobertos até , que sustentam os teoremas sobre a estrutura do que resiste.
Cada tabela e cada afirmação numérica do artigo aponta para uma pasta e um comando.