A Famigerada Conjectura de Collatz

Texto por: Gabrielle Weber


Esteja avisade, queride leitore, mantenha distância da Conjectura de Collatz! 


A Conjectura de Collatz, proposta pelo matemático alemão Lothar Collatz em 1937, é um dos problemas em aberto mais perigosos da matemática. Trata-se, provavelmente, do problema mais simples que ainda não foi resolvido. E não foi por falta de tentativas. Jeffrey Lagarias, um especialista na conjectura de Collatz, catalogou pelo menos 331 trabalhos abordando a famigerada conjectura entre 1963 e 2009. Não obstante, matemáticos mais experientes comumente aconselham os neófitos a manterem distância da famigerada conjectura, sob o perigo de nunca mais produzirem matemática. Nas sábias palavras do grande matemático húngaro Paul Erdös: “A matemática simplesmente não está pronta para lidar com tais problemas.”


Mas do que diabos se trata tal problema que simultaneamente é tão sedutor e tão perigoso? Escolha um número positivo qualquer. Se ele for par, divida por 2. Se ele for ímpar, multiplique por 3 e adicione 1. A conjectura versa exatamente sobre o resultado da aplicação recursiva desse procedimento, que mais parece um truque de mágica barato que fazemos em festa em criança. Ingenuamente, somos levades a esperar que a sequência, dita de Collatz, gerada por esse algoritmo deva depender do número com que começamos. Algumas podendo convergir para um dado valor, já outras, divergir. Olhemos para alguns exemplos:


n=1: 1→4→2→1

n=2: 2→1

n=3: 3→10→5→16→8→4→2→1

n=4: 4→2→1

n=5: 5→16→8→4→2→1

n=6: 6→3→10→5→16→8→4→2→1


Vemos, por esses exemplos, que quando uma sequência de Collatz atinge o valor 1, ela fica presa no ciclo, 1→4→2. Com isso, podemos, enfim, enunciar a conjectura de Collatz:


“Toda sequência de Collatz converge para o número 1.”

Animação do gráfico da sequência de Collatz para n indo de 10 a 1000, ilustrando a sua convergência para 1. Animação feita no Mathematica.

Animação do gráfico da sequência de Collatz em escala logarítmica (azul) e sua aproximação linear (laranja) para n indo de 10 a 1000. Animação feita no Mathematica.

Mas como podemos testar essa conjectura?


Uma tentativa ingênua é empregar a força bruta, testando a conjectura para cada inteiro positivo. Em 2020, David Barina, verificou computacionalmente que ela é verdadeira para todos os valores menores do que 268 ≈ 2,95⨉1020. Consequentemente, é improvável que consigamos encontrar um contraexemplo por inspeção. Por outro lado, sabemos que para outras conjecturas, como a de Pólya, contraexemplos foram encontrados ao considerarmos números suficientemente grandes.


Uma outra forma de mostrarmos que conjectura é falsa, consiste em encontrar um outro ciclo fechado que não o 1→4→2. Contudo, resultados, como o de Barina, permitem que coloquemos restrições no tamanho de tais ciclos. Em 1993, Eliahou mostrou que tais ciclos devem ter pelo menos 17.087.915 passos. Logo, produzir ciclos não triviais para falsear a conjectura está longe de ser uma tarefa simples também.


Finalmente, podemos considerar o seguinte argumento heurístico que corrobora a veracidade da conjectura. A ideia é a seguinte. Se n for ímpar, ele será mapeado em 3n+1, que, por ser par, será dividido por 2: 


n → 3n+1 → (3n+1)/2


Heuristicamente, há uma chance de 50% que o resultado dessa divisão seja par, implicando mais uma divisão por 2. De fato, é possível demonstrar por argumentos probabilísticos que o número esperado de divisões por 2 antes de obtermos novamente um número ímpar é dois. Logo,


n → 3n+1 → (3n+1)/2 → (3n+1)/4


e, com isso, podemos afirmar que, se partirmos de um número ímpar n, o próximo número ímpar da sequência será aproximadamente 3n/4. Portanto, o módulo dos números ímpares na sequência diminuirá em direção a 1, sugerindo a validade da conjectura.


É possível tornar esse argumento rigoroso no contexto da estatística, ou seja, estudando o comportamento de quase todas as sequências de Collatz, em vez de todas, assim, excluindo os outliers (pontos muito fora). O primeiro resultado nessa direção foi obtido por Terras em 1976, ao mostrar que quase todos os inteiros positivos n eventualmente serão levados a valores menores do que n. Esse resultado foi refinado ao longo dos anos. Mais recentemente, em 2019, Terrence Tao mostrou que quase todo inteiro positivo n será levado a um valor menor que f(n), em que f é qualquer função que diverge para n suficientemente grande tão vagarosamente quanto se queira. Consequentemente, quase todas as sequências de Collatz (cerca de 99% delas) atingem valores nas proximidades de 1. Trata-se do resultado mais próximo de uma demonstração da conjectura que temos até hoje.

Referências