Renato Augusto Tavares
English

Um cálculo exato com 263 GiB de estado

A tabela de j∗(ℓ)j^*(\ell) da Conjectura da Cobertura Fraca parava em ℓ=20\ell = 20. Levá-la a ℓ=23\ell = 23 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 ℓ\ell, o menor jj tal que as somas ∑i2ai3i\sum_{i} 2^{a_i} 3^{i}, com jj expoentes estritamente decrescentes escolhidos entre 00 e 2j−12j-1, atinjam todas as unidades módulo 3ℓ3^\ell. Enumerar as somas é inviável: são (2jj)\binom{2j}{j} delas, e para ℓ=23\ell = 23 o orçamento é j=27j = 27. A enumeração direta deixa de ser tratável depois de ℓ=4\ell = 4.

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 3ℓ3^\ell 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: (ℓ+1)·3ℓ/8(\ell + 1) \cdot 3^{\ell} / 8 bytes.

O custo

Custo do cálculo por nível, na máquina de referência
NívelEstadoTempo de paredeObservação
ℓ = 1 a 16até 0,1 GiB6 s
ℓ = 17 a 19até 2,7 GiB3,5 min
ℓ = 209 GiB10 minLimite da tabela anterior
ℓ = 2127 GiB748 sCabe na memória física
ℓ = 2284 GiB10 749 sExigiu 500 GiB de swap
ℓ = 23263 GiB375 615 sCerca de 104 horas

A partir de ℓ=22\ell = 22 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 ℓ=23\ell = 23 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 ℓ≤4\ell \le 4, em um programa que não compartilha nenhum caminho de código com a programação dinâmica.
  • Valores de referência para ℓ=1\ell = 1 a 77 e uma conferência pontual, em ℓ=2\ell = 2 e j=2j = 2, em que a imagem é {1,2,5,7}\{1, 2, 5, 7\} módulo 9 e faltam {4,8}\{4, 8\}. 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é ℓ=17\ell = 17, que confirma j∗(21)=25j^*(21) = 25.
  • Um lema, com prova, de que nenhum orçamento menor que ℓ\ell cobre, o que fecha a busca por baixo sem depender do programa.

Para ℓ=22\ell = 22 e 2323 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 ℓ=18\ell = 18, que usa 22 GiB; e os conjuntos de resíduos não cobertos até ℓ=21\ell = 21, 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.