Renato Augusto Tavares
English

O expoente de contagem do mapa 5x+1

Dois modelos probabilísticos preveem expoentes diferentes para o número de predecessores na árvore do mapa 5x+15x+1: cerca de 0,650919 e cerca de 0,678. A diferença é menor que o erro de uma medição ingênua. Este trabalho mede com um instrumento calibrado.

Duas previsões

Troque o 3 por um 5 no problema de Collatz e o comportamento muda: acredita-se que quase todas as órbitas do mapa 5x+15x+1 escapam para o infinito. A árvore reversa de um inteiro, formada pelos seus predecessores, ainda existe e cresce, mas devagar: o número de predecessores abaixo de xx deve se comportar como xηx^{\eta} para algum expoente η\eta menor que 1.

Há duas previsões para esse expoente. Kontorovich e Lagarias chegam a η≈0,650919\eta \approx 0,650919 por um modelo de passeio aleatório ramificado; a própria existência do expoente é a Conjectura 7.2 deles. Volkov, por outro modelo estocástico, chega a cerca de 0,6780,678. A distância entre as duas é de 0,027, e Kontorovich e Lagarias observam que os dados de Volkov não pareciam suficientes para discriminar entre os valores.

O problema do instrumento

A árvore pode ser enumerada exatamente. Um estimador de janela fixa aplicado a essa enumeração lê 0,639, com intervalo de 95% entre 0,633 e 0,645, o que não exclui nenhum dos dois valores. E há algo pior: aplicado a uma construção sintética cujo expoente é conhecido, o mesmo estimador lê 0,038 abaixo do alvo. O viés do instrumento é maior que a diferença que se quer medir. Uma leitura crua, por mais dígitos que tenha, não decide a questão.

A calibração

A saída foi construir seis árvores sintéticas que preservam a estrutura de irmãos da árvore aritmética, de forma exata ou relaxada, e que são ajustadas para ter um expoente escolhido: quatro para 0,650919 e duas para 0,678. O estimador é então lido na árvore verdadeira e nas seis construções, década por década, e a pergunta passa a ser em qual das duas faixas a leitura verdadeira cai.

Leitura do expoente de contagem da árvore 5x+1 por década, contra construções calibradasEm cada uma das cinco décadas, a leitura da árvore aritmética é comparada com a faixa das construções ajustadas ao valor de Kontorovich e Lagarias e com a faixa das ajustadas ao valor de Volkov. Na década mais profunda a leitura, 0,64926, cai dentro da primeira faixa e abaixo da segunda.0,600,620,640,660,68 Construções ajustadas a 0,650919 em 10⁵→10⁶: de 0,59064 a 0,61366Construções ajustadas a 0,678 em 10⁵→10⁶: de 0,59408 a 0,64477Árvore aritmética em 10⁵→10⁶: 0,6340110⁵→10⁶Construções ajustadas a 0,650919 em 10⁶→10⁷: de 0,61363 a 0,63749Construções ajustadas a 0,678 em 10⁶→10⁷: de 0,63432 a 0,66268Árvore aritmética em 10⁶→10⁷: 0,6269710⁶→10⁷Construções ajustadas a 0,650919 em 10⁷→10⁸: de 0,63152 a 0,64758Construções ajustadas a 0,678 em 10⁷→10⁸: de 0,66394 a 0,67200Árvore aritmética em 10⁷→10⁸: 0,6462210⁷→10⁸Construções ajustadas a 0,650919 em 10⁸→10⁹: de 0,64219 a 0,64990Construções ajustadas a 0,678 em 10⁸→10⁹: de 0,67157 a 0,67745Árvore aritmética em 10⁸→10⁹: 0,6488010⁸→10⁹Construções ajustadas a 0,650919 em 10⁹→10¹⁰: de 0,64738 a 0,65122Construções ajustadas a 0,678 em 10⁹→10¹⁰: de 0,67358 a 0,67748Árvore aritmética em 10⁹→10¹⁰: 0,6492610⁹→10¹⁰ 0,678previsão de Volkov 0,650919Kontorovich–Lagarias década de contagem (faixa de inteiros enumerados)
Figura 5. Leitura do estimador na árvore aritmética (ponto e traço) em cada década de contagem, contra a faixa das construções ajustadas a 0,650919 (barra cheia) e a faixa das ajustadas a 0,678 (barra hachurada). As linhas pontilhadas são os alvos nominais; as barras ficam abaixo deles porque o estimador tem viés. Na década mais profunda, a leitura 0,64926 cai dentro da primeira faixa e 0,02432 abaixo da segunda. Dados: tabela por década do preprint.

Resultados, por situação

Demonstrado

Congruência entre irmãos. Na árvore reversa do mapa qx+1qx+1 acelerado, filhos consecutivos de um mesmo nó satisfazem exatamente

w′=2dw+2d−1q,d=ordq⁡(2).w' = 2^{d} w + \frac{2^{d} - 1}{q}, \qquad d = \operatorname{ord}_q(2).

Para q=5q = 5, isso é w′=16w+3w' = 16w + 3. É o único enunciado demonstrado do trabalho, e é o que as construções sintéticas precisam preservar.

Evidência computacional

Na década 109→101010^{9} \to 10^{10}, a árvore aritmética lê 0,64926, com intervalo de 95% entre 0,64818 e 0,65027. As quatro construções ajustadas a 0,650919 leem entre 0,64738 e 0,65122; as duas ajustadas a 0,678, entre 0,67358 e 0,67748.

A leitura fica 0,02432 abaixo da menor das duas construções de Volkov, com intervalo de bootstrap de 95% entre 0,0208 e 0,0273.

300 raízes abaixo de 10⁴; enumeração em C com OpenMP

Evidência computacional

A regra de parada do experimento original de Volkov, reimplementada, reproduz as três primeiras estimativas dele e dá 0,681 contra o 0,680 publicado.

Hipóteses da leitura

A comparação supõe que o expoente realizado por cada construção é igual ao seu alvo e que o viés calibrado se transfere para a árvore determinística. Nenhuma das duas coisas é provada. Outras três entradas do argumento são problemas em aberto, entre elas a existência do expoente.

Em aberto

Se o limite é 0,650919 ou algum valor abaixo dele. O trabalho não diz, e não poderia dizer.

Em uma frase: sob as hipóteses declaradas, os dados são compatíveis com a previsão de Kontorovich e Lagarias e ficam separados da de Volkov. Isso é evidência computacional, não uma refutação.

Controles negativos

Uma verificação que nunca foi vista falhar não é evidência de nada. Três conferências do repositório vêm acompanhadas de controles negativos executados: uma sonda para cada elo da cadeia de cálculo da pressão, uma réplica do gerador de números aleatórios comparada com o código em C, e três mutações que o filtro de comparação de saídas tem de detectar.

Todo arquivo de saída versionado se reproduz byte a byte a partir do código e dos dados, com duas exceções documentadas, que carregam um tempo de relógio embutido. O repositório também registra um erro que aconteceu durante a revisão, quando duas amostras de 300 raízes, que compartilham apenas 31, foram confundidas; a conferência que hoje distingue as duas existe por causa disso.