A Famigerada Conjectura de Collatz

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.”

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

1. Lagarias, Jeffrey C. (2003). “The 3x+1 problem: An annotated bibliography (1963 -- 1999)”. https://arxiv.org/pdf/math/0309224.pdf 

2. Lagarias, Jeffrey C. (2006). “The 3x+1 problem: An annotated bibliography, II (2000 -- 2009)”. https://arxiv.org/pdf/math/0608208.pdf

3. Barina, David (2020). "Convergence verification of the Collatz problem". The Journal of Supercomputing. 77 (3): 2681–2688. doi:10.1007/s11227-020-03368-x. S2CID 220294340.

4. Eliahou, Shalom (1993). "The 3x + 1 problem: new lower bounds on nontrivial cycle lengths". Discrete Mathematics. 118 (1): 45–56. doi:10.1016/0012-365X(93)90052-U

5. Tao, Terrence (2019). “ALMOST ALL ORBITS OF THE COLLATZ MAP ATTAIN ALMOST BOUNDED VALUES”. https://arxiv.org/pdf/1909.03562.pdf 

6. Tao, Terrence (2020). “The Notorious Collatz conjecture”. https://terrytao.files.wordpress.com/2020/02/collatz.pdf