Os matemáticos alcançaram um avanço no estudo do problema "perigoso"

Os matemáticos consideram a hipótese de Collatz um "pântano" e alertam um ao outro que vale a pena ficar longe dela. Agora, no entanto, Terence Tao fez mais progressos do que qualquer um em décadas.

Pegue qualquer número. Se for par, divida-o em dois. Se ímpar, multiplique por três, adicione um. Repita. Algum número chega a 1?

Matemáticos experientes aconselham os iniciantes a se afastarem da hipótese de Collatz . Eles chamam de música de sirene: caem sob sua influência e você nunca consegue um trabalho significativo.

A hipótese de Collatz, talvez o mais simples dos problemas não resolvidos da matemática, é precisamente o que a torna tão traiçoeira e atraente.

“Essa é uma tarefa muito perigosa. As pessoas ficam obcecadas com isso, mesmo que seja completamente impossível ”, disse Jeffrey Lagarias , matemático da Universidade de Michigan, especialista na hipótese de Collatz.

Mas em 2019, um dos melhores matemáticos do mundo se atreveu a abordá-lo e recebeu o mais significativo de todos os resultados alcançados em várias décadas.

Em 8 de setembro de 2019, Terence Tao publicou uma prova mostrando que a hipótese de Collatz é pelo menos "quase" verdadeira "quase" para todos os números. Embora o resultado do Tao não seja uma prova completa da hipótese, é um avanço muito sério para uma tarefa que não é tão fácil de revelar todos os seus segredos.

"Eu não esperava resolver o problema completamente", disse Tao, matemático da Universidade da Califórnia, em Los Angeles. "Mas consegui fazer mais do que esperava."

Collatz Puzzle

Lothar Collatz provavelmente apresentou uma hipótese com o mesmo nome na década de 1930. O desafio parece um truque de festa. Pegue qualquer número. Se for par, divida-o em dois. Se ímpar, multiplique por três, adicione um. Obtenha um novo número. Aplique as mesmas regras para ele. A hipótese diz o que acontecerá se você repetir persistentemente esse processo.

A intuição sugere que o número inicial afeta o resultado final. Talvez alguns números diminuam para 1. Talvez outros números aumentem indefinidamente.

No entanto, Collatz previu que não é assim. Ele sugeriu que, se você começar com um número inteiro positivo e repetir a sequência indicada por um longo período de tempo, então, a partir de qualquer número inicial, você chegará ao 1. E chegando à unidade, as regras da hipótese o capturam em um loop infinito: 1, 4, 2, 1, 4, 2, 1 e assim por diante, até o infinito.

Ao longo dos anos, muitos amantes de tarefas foram atraídos pela simplicidade atraente da hipótese de Collatz, ou "problema 3x + 1", como também é chamado. Os matemáticos já verificaram um quintilhão de exemplos (este é um número com 18 zeros), não encontrando uma única exceção à previsão de Collatz. Você mesmo pode tentar verificar alguns exemplos com qualquer uma das muitas “ calculadoras Collatz ” disponíveis na Internet. A Internet está cheia de evidências amadoras injustificadas de uma hipótese, cujos autores afirmam que foram capazes de provar ou refutá-la.



“Você só precisa multiplicar por 3 e dividir por 2, e já pode começar a brincar com ele. E é muito tentador ", disse Mark Chamberlain , matemático do Grinnel College, que gravou um vídeo popular no YouTube sobre esse problema chamado" O mais simples dos problemas impossíveis ".


Mas há pouca evidência verdadeira.

Na década de 1970, os matemáticos mostraram que quase todas as seqüências de Collatz - uma lista de números que você obtém quando repete o processo - acabam por chegar a um número menor que o inicial. Essa era uma evidência fraca de que quase todas as seqüências de Collatz levam a 1, mas mesmo assim foi. E de 1994 ao resultado do Tao em 2019, Ivan Korets manteve o recorde de demonstração do valor mínimo. Outros trabalhos tentaram similarmente atacar a tarefa, não se aproximando de seu objetivo principal.

"Nós realmente não entendemos a questão de Collatz o suficiente, então não houve trabalho significativo sobre esse assunto", disse Kannan Saundararajan , matemático da Universidade de Stanford que trabalhou nessa hipótese.

A futilidade dessas tentativas levou muitos matemáticos a concluir que essa hipótese simplesmente não está disponível no nível atual de conhecimento e que é melhor que eles dediquem seu tempo a outros estudos.

"O problema de Collatz é conhecido por sua complexidade - tanto que os matemáticos geralmente precedem cada discussão com um aviso para não perder tempo com isso", disse Joshua Cooper, da Universidade da Carolina do Sul.

Conselho inesperado

Pela primeira vez, Lagarias se interessou por essa hipótese como estudante há pelo menos 40 anos. Por décadas, ele foi um curador não oficial de tudo que estava relacionado a ela. Ele coletou toda uma biblioteca de obras relacionadas a ela e, em 2010, publicou algumas delas na forma de um livro intitulado: "O Desafio Decisivo: Problema 3x +1 ".

"Agora eu sei muito mais sobre esse problema e ainda posso dizer que é impossível resolvê-lo", disse Lagarias.

Tao geralmente não gasta seu tempo em tarefas impossíveis. Em 2006, ele recebeu o Fields Prize , o maior prêmio em matemática, e é considerado um dos melhores matemáticos de sua geração. Ele está acostumado a resolver problemas, não perseguindo castelos no ar.

"Esses são os riscos associados à profissão de matemática", disse ele. "Você pode ficar obcecado por uma das grandes tarefas conhecidas que estão além das capacidades de qualquer pessoa e perdem uma tonelada de tempo."

No entanto, o Tao nem sempre consegue resistir às tentações dessa área. Todo ano ele passa um ou dois dias no mais famoso dos problemas não resolvidos da matemática. Ao longo dos anos, ele adotou várias abordagens da hipótese de Collatz, mas sem sucesso.

Então, em agosto, um leitor anônimo deixou um comentário no blog de Tao. Ele sugeriu tentar resolver a hipótese de Collatz "para quase todos" os números, sem tentar provar completamente.

"Eu não respondi, mas isso me fez pensar nessa tarefa novamente", disse Tao.

E ele percebeu que a hipótese de Collatz era, de certa forma, semelhante a tipos especiais de equações - equações diferenciais parciais - que apareciam nos resultados mais significativos que ele obteve durante sua carreira.

Entradas e saídas

As equações diferenciais parciais (PDEs) podem ser usadas para modelar muitos dos processos físicos mais fundamentais do Universo, como a evolução de líquidos ou a passagem de ondas gravitacionais pelo espaço-tempo. Eles aparecem em situações em que a posição futura do sistema - por exemplo, o estado da lagoa cinco segundos depois de atirar uma pedra nele - depende da contribuição de dois ou mais fatores, como viscosidade e velocidade da água.

Parece que os PDEs complexos têm pouco a ver com uma questão aritmética tão simples quanto a hipótese de Collatz.

Mas Tao percebeu que eles tinham algo em comum. É possível substituir valores no PDE, obter outros valores, repetir o processo - e tudo isso para entender o estado futuro do sistema. Para cada LDPE, os matemáticos precisam saber se os valores iniciais na entrada levarão a valores infinitos na saída ou se as equações sempre produzirão valores finais, independentemente dos valores iniciais.


Terence Tao, inspirado no comentário em seu blog, fez o maior progresso em décadas ao estudar a hipótese de Collatz

Para Tao, esse objetivo era da mesma ordem em que você sempre obtém o mesmo valor (1) do processo Collatz, independentemente do valor inicial. Como resultado, ele percebeu que as técnicas de estudo de EDPs poderiam ser adequadas para o estudo da hipótese de Collatz.

Uma técnica particularmente útil usa um método estatístico para estudar o comportamento a longo prazo de um pequeno número de valores iniciais (algo como um pequeno número de configurações iniciais de água em uma lagoa) e extrapola o resultado para o comportamento a longo prazo de todas as possíveis configurações iniciais da lagoa.

No contexto da hipótese de Collatz, imagine que começamos com uma grande amostra de números. Nosso objetivo é estudar como esses números se comportam quando aplicamos o processo Collatz a eles. Se quase 100% dos números da amostra chegarem a 1 ou forem muito próximos de 1, podemos concluir que quase todos os números se comportarão da mesma maneira.

Mas, para que essa conclusão seja justificada, é necessário selecionar cuidadosamente a amostra. Essa tarefa é semelhante à compilação de uma amostra de eleitores nas eleições presidenciais dos EUA. Para uma amostragem cuidadosa de toda a população, proporções ponderadas devem ser usadas para republicanos e democratas, homens e mulheres, e assim por diante.

Os números têm seus próprios parâmetros "demográficos". Números pares e ímpares, números divisíveis por 3 e números que diferem entre si de maneiras ainda mais complicadas. Ao criar uma seleção de números, você pode garantir que certos tipos de números entrem nele e outros não, de acordo com um princípio equilibrado - e quanto melhor você escolher pesos, mais precisas serão suas conclusões sobre todos os números em geral.

Escolha ponderada

A tarefa de Tao era muito mais complicada do que apenas entender como criar uma seleção inicial de números com os pesos certos. Em cada etapa do processo Collatz, os números com os quais você trabalha são alterados. Uma mudança óbvia é que quase todos os números da amostra estão diminuindo.

Outra mudança, talvez menos óbvia, é que os números podem começar a se acumular em grupos. Por exemplo, você pode começar com uma bela distribuição uniforme de números de um a um milhão. Porém, após cinco iterações, é provável que os números se concentrem em vários pequenos intervalos da linha numérica. Em outras palavras, você pode começar com uma boa amostra, que em cinco etapas será distorcida irremediavelmente.

"Geralmente, você pode esperar que a distribuição após a iteração seja completamente diferente da inicial", disse Tao. No entanto, sua idéia principal era como criar uma amostra de números que, na maioria das vezes, retinham seus pesos originais no processo Collatz.

Por exemplo, a amostra inicial do Tao é ponderada para que não tenha números divisíveis por três, uma vez que o processo de Collatz ainda elimina rapidamente esses números. Alguns outros pesos escolhidos pelo Tao são mais difíceis. Ele prefere números cujo restante da divisão por 3 é 1 e parte de números cujo restante da divisão por 3 é 2.

Como resultado, a amostra com a qual o Tao começa mantém seu caráter mesmo após o início do processo Collatz.

"Ele encontrou uma maneira de continuar esse processo para que, depois de algumas etapas, ainda esteja claro o que está acontecendo", disse Saundararajan. "Quando vi esse trabalho pela primeira vez, fiquei muito feliz e decidi que era incrível."

Tao usou sua técnica de atribuição de peso para provar que quase todos os valores iniciais - pelo menos 99% - chegaram a um valor muito próximo de 1. Isso permitiu concluir que 99% dos valores iniciais são maiores que um quatrilhão , como resultado, chegar a valores menores que 200.

Este é sem dúvida o resultado mais forte da longa história dessa hipótese.

"Este é um grande avanço em nosso conhecimento do que está acontecendo com esta tarefa", disse Lagarias. "Este é definitivamente o melhor resultado em muito tempo."

O método Tao é quase certamente incapaz de obter a prova completa da hipótese de Collatz. O motivo é que sua seleção inicial ainda está um pouco distorcida após cada etapa. A distorção será mínima, enquanto a amostra ainda contém muitos valores diferentes, longe de 1. Mas no processo de Collatz, todos os números na amostra começam a tender para um e uma pequena distorção se torna maior - assim como um pequeno erro no cálculo do resultado da votação não tem. um valor grande no caso de uma amostra grande, mas afeta fortemente o resultado quando a amostra é pequena.

Qualquer evidência de uma hipótese completa provavelmente será baseada em uma abordagem diferente. Como resultado, o trabalho de Tao é ao mesmo tempo um triunfo e um aviso para todos os interessados: assim que lhe parecer que você encurralou a tarefa, ela escapa.

"Você pode se aproximar arbitrariamente da hipótese de Collatz, mas ainda permanece inatingível", disse Tao.