Avanço revela a estrutura oculta dos números primos

 (science.org)
1 pontos por GN⁺ 2024-08-02 | 1 comentários | Compartilhar no WhatsApp
  • Um preprint de 31 de maio de James Maynard e Larry Guth exclui certas exceções à hipótese de Riemann e representa o primeiro avanço em décadas em um problema de 165 anos: encontrar a estrutura oculta na distribuição dos números primos
  • O alvo central são os zeros não triviais da função zeta de Riemann, diretamente ligados à compreensão do erro entre a estimativa de Gauss para a quantidade de números primos e a distribuição real dos primos
  • Computadores já confirmaram que mais de 10 trilhões de zeros têm todos parte real igual a 1/2, mas o que os matemáticos querem não é uma verificação empírica, e sim uma prova de que outras posições são impossíveis
  • O resultado reduziu o limite superior para o número de zeros no ponto 3/4, que não era melhorado desde Albert Ingham em 1940, e quebrou uma barreira antiga ao combinar teoria analítica dos números e análise harmônica
  • A prova completa da hipótese de Riemann ainda está distante, mas o avanço pode levar a novas ferramentas para estimar a quantidade de primos em intervalos mais curtos e abordar outros problemas da teoria dos números

A hipótese de Riemann para decifrar a distribuição dos primos

  • Todo número natural pode ser decomposto em um produto de números primos, divisíveis apenas por eles mesmos e por 1, e matemáticos há muito tentam entender como esses primos se distribuem na reta numérica
  • À primeira vista, os primos parecem bastante aleatórios, mas acredita-se que haja uma estrutura oculta neles
  • Nos últimos 165 anos, a hipótese de Riemann esteve no centro da busca por essa estrutura
    • Se for provada, poderá funcionar como uma espécie de Pedra de Roseta para decifrar os primos
    • Há um prêmio de US$ 1 milhão oferecido pelo Clay Mathematics Institute

A estimativa de Gauss e os zeros da zeta

  • No fim dos anos 1700, aos 16 anos, Carl Friedrich Gauss observou que os primos se tornam mais raros à medida que crescem e estimou que a quantidade de primos menores ou iguais a X escala aproximadamente como X / ln X
  • Essa estimativa tem se ajustado muito bem à quantidade real de primos, que oscila levemente para cima e para baixo em torno da curva
  • Em 1859, Bernhard Riemann tentou tratar a diferença entre a curva de Gauss e a distribuição real dos primos usando a função zeta de Riemann
    • Essa função recebe como entrada números complexos, com componentes reais e imaginárias
    • Os zeros da zeta, pontos em que a função zeta de Riemann se torna 0, descrevem diretamente as flutuações do erro em torno da curva de Gauss

A restrição exigida pela hipótese de Riemann

  • A hipótese de Riemann prevê que, excetuando algumas soluções triviais que surgem para entradas negativas, todos os zeros da zeta devem ter parte real igual a 1/2 em sua entrada
  • Se a hipótese for verdadeira, as flutuações na quantidade de primos ficam limitadas, o que significa que não há grandes aglomerados nem grandes lacunas na distribuição dos primos ao longo da reta numérica
  • Até agora, computadores já examinaram mais de 10 trilhões de zeros não triviais da zeta, e todos estão exatamente sobre a parte real 1/2
  • Mas a verificação empírica, por si só, não basta
    • Maynard vê a prova não apenas como uma confirmação de que a hipótese é verdadeira, mas como uma forma de entender por que ela é verdadeira e obter novas técnicas poderosas para lidar com os primos
    • Ainda não há sequer uma rota de ataque plausível para provar a hipótese de Riemann

A fresta estreita visada por este resultado

  • Como os matemáticos não conseguem provar diretamente toda a hipótese de Riemann, eles vêm dividindo o problema ao reduzir as regiões onde os zeros da zeta não podem existir
  • Já se sabe que os zeros não triviais da zeta estão confinados entre 0 e 1
  • Além disso, há uma simetria espelhada em torno de 1/2, de modo que excluir zeros no ponto 3/4 também exclui zeros no ponto 1/4
  • As técnicas existentes funcionavam melhor entre 1/2 e 3/4, ou entre 3/4 e 1, mas permanecia a possibilidade de muitos zeros estarem escondidos em 3/4
  • O melhor limite superior para a quantidade de zeros que poderiam estar em 3/4 era um resultado de 1940 do matemático britânico Albert Ingham, e ninguém havia conseguido melhorá-lo desde então

A abordagem de Maynard e Guth

  • Maynard é especialista em teoria analítica dos números e recebeu a Fields Medal em 2022; durante os últimos 10 anos, ele voltou repetidamente a esse problema nas tardes de sexta-feira, mas sem obter resultados
  • Em uma reunião da American Mathematical Society em 2020, Maynard pediu ajuda a Larry Guth, do MIT, especialista em análise harmônica
    • A análise harmônica usa ideias tomadas da física e está relacionada a técnicas de decompor sons em suas notas componentes
    • Guth também ficou anos preso ao problema e, pouco antes de desistir, encontrou um avanço junto com Maynard
  • Os dois tomaram estratégias emprestadas de suas respectivas linguagens matemáticas e trocaram ideias por e-mail tarde da noite, quebrando o limite superior de Ingham de uma forma pouco ortodoxa

Possíveis impactos em toda a teoria dos números

  • Maksym Radziwill avalia este trabalho como a primeira ideia nova em 50 anos na busca pelos zeros da zeta e acredita que uma área há muito negligenciada pode voltar a se movimentar
  • O limite superior melhorado ajuda pouco na prova completa da hipótese de Riemann, mas pode influenciar a teoria dos números de forma ampla
    • Matemáticos poderão estimar melhor a quantidade de primos em intervalos mais curtos
    • Radziwill acredita que a nova estratégia pode ajudar a simplificar seu trabalho anterior relacionado a sistemas dinâmicos
    • Ela também pode ajudar no problema de Kakeya
    • Guth tem interesse em usar essa ideia para explorar relações profundas entre a física das ondas e a distribuição de conjuntos de números

Leituras relacionadas

1 comentários

 
GN⁺ 2024-08-02
Opiniões do Hacker News

  • Isso saiu em maio, e já havia um artigo melhor na Quanta, que também foi discutido aqui
    https://www.quantamagazine.org/sensational-proof-delivers-ne...

  • Fico imaginando essa descoberta levando a um avanço maior sobre números primos, tornando fácil a fatoração em primos de inteiros grandes e inutilizando da noite para o dia criptografia de chave pública como RSA
    Se qualquer pessoa conseguisse quebrar chaves de tamanho usado em serviços reais até com uma CPU de consumidor, será que a indústria teria planos de recuperação de desastre para esse cenário? Grandes empresas conseguiriam migrar rapidamente para outros sistemas criptográficos ainda não quebrados? Para desenvolvedores de jailbreak, modders de consoles e o pessoal da “liberdade dos dispositivos”, seria um dia dos sonhos, mas o impacto geral pareceria catastrófico e difícil de dimensionar
    Fico com a impressão de que a indústria não considera uma descoberta súbita em teoria dos números como um evento possível

    • No caso do RSA, isso já aconteceu várias vezes
      Houve uma época em que o governo dos EUA restringia a exportação de chaves RSA longas, e em certo momento boa parte do mundo usava chaves RSA de 128 bits, até que o método de Dixon fez todo mundo correr para chaves de 512 bits. Depois, por causa do special number field sieve, subiram às pressas para 1024 bits; e, por causa do general number field sieve, de novo para 2048 bits — e isso nem faz tanto tempo assim
      Se você olhar hardware de criptografia RSA dos anos 80, há equipamentos que se orgulham de processar 512 bits. Hoje são inúteis
      https://people.csail.mit.edu/rivest/pubs/pubs/Riv84.pdf
      As fórmulas de complexidade do special/general number field sieve diferem por apenas algumas constantes; olhando essas constantes, fico em dúvida se elas parecem mesmo limites fundamentais. É difícil acreditar que não exista algum modo de reduzi-las ainda mais e tornar inúteis até chaves de 2048 bits
      Não é preciso perguntar “o que acontece se o RSA for quebrado”. Como já passamos por isso várias vezes, dá para dizer de imediato que todo mundo vai se atropelar para aumentar o tamanho das chaves e auditar todos os dados que possam ter sido expostos
    • Se for descoberto um método para fatorar facilmente inteiros grandes em hardware de consumidor, será muito doloroso, já que o RSA é um dos principais algoritmos de chave pública
      Ainda assim, antes de se preocupar, é bom lembrar que o RSA resistiu a 47 anos de criptoanálise ativa. Nesse período, muitos algoritmos alternativos foram propostos como superiores, mas vários foram quebrados pouco tempo depois
      O movimento de migração para algoritmos de curva elíptica também ocorre principalmente porque eles são mais fáceis para os computadores executarem na criptografia/descriptografia
      Pessoalmente, se eu tivesse que apostar dinheiro em um algoritmo de chave pública que ainda existirá daqui a 10 anos, apostaria no RSA
    • Acho que é aqui que entra a migração para curvas elípticas, e parece que ela já está bem avançada tanto em assinaturas quanto em handshakes (Diffie-Hellman)
      A recuperação de desastre não seria uma tarefa de 1 minuto, mas, se RSA/DH se tornassem inseguros da noite para o dia, não acho que tudo simplesmente ficaria aberto. Minhas chaves SSH também já são uma mistura de vários métodos
    • A indústria não estava preparada nem para uma atualização ruim da CrowdStrike, mas, mesmo assim, em alguns dias conseguiu contornar a situação
      Parece que a capacidade de se preparar para cenários catastróficos é superestimada, enquanto a capacidade de sobreviver é subestimada
    • Há uma visão de que a descoberta de fatoração rápida é extremamente rara. Muita gente inteligente já olhou para isso, então, por enquanto, provavelmente é impossível — mas essa própria narrativa pode ser um ponto fraco
      Esse risco é tão real quanto o de uma grande tempestade solar derrubar a rede elétrica e, por atrasos na fabricação de transformadores e falta de estoques, levar a um período de recuperação de vários anos, quase como voltar à Idade da Pedra. Mas, nessa perspectiva, parece pequeno e teórico demais para justificar muito tempo de atenção
      Quanto a planos, não sei se simplesmente mudar para ECC é tão fácil assim. A criptografia assimétrica real em ECC depende de um segredo compartilhado; se assumirmos que o RSA foi quebrado e que o canal de troca não é seguro, ela pode ficar mais vulnerável a ataques man-in-the-middle do que o RSA. Não parece uma substituição simples
      Separadamente, também é possível que o RSA já tenha sido quebrado e que a solução esteja sendo mantida em segredo por agências de criptoanálise. Para elas, esconder uma descoberta seria extremamente atraente, e talvez tentassem encontrar formas de suprimir uma “descoberta súbita em teoria dos números”

  • As pessoas sempre acham que a estrutura dos números primos é complexa, mas, na verdade, vejo isso apenas como uma estrutura recursiva dos tamanhos de intervalo que os múltiplos dos intervalos anteriores não conseguem alcançar.
    Isso não torna fácil “prever” sem acompanhar todos os intervalos anteriores, mas, essencialmente, não é uma estrutura complexa. É interessante que uma estrutura tão simples seja tão difícil de capturar. É parecido com a forma como a sequência 3n+1 gera complexidade, ou como o mapa logístico fica complexo ao ultrapassar um valor crítico.

    • Um gerador que produz “todos os primos” é bastante simples e determinístico.
      Mas, dado apenas um primo n, para obter o próximo primo é preciso recalcular restos não triviais; portanto, a representação binária do número n por si só não contém informação suficiente para responder rapidamente qual é o próximo primo. Primeiro é preciso pré-calcular alguns pontos de referência. No fim, ainda há mais complexidade, mas continua sendo simples e bastante óbvio; nem é um problema que entraria em NP.
    • Ah, claro. Nada mais simples do que fornecer a teoria de base da teoria dos números, uma das áreas mais rigorosas e intelectualmente intimidantes da matemática /s
    • Fico curioso por que isso não é considerado um problema resolvido.
      https://en.wikipedia.org/wiki/Information_theory
      https://en.wikipedia.org/wiki/Computational_irreducibility
      https://en.wikipedia.org/wiki/Aperiodic_tiling

  • O trecho “em sua sessão dedicada de reflexão nas tardes de sexta-feira, ele voltou a esse problema repetidamente ao longo da última década, mas sem resultados” é inspirador.

    • Lembro que Richard Hamming também costumava reservar as tardes de sexta-feira para pensamentos profundos e grandiosos. Um jeito excelente de fazer isso.

  • Quando você desenha a curva de Gauss e a curva de Riemann em determinado espaço, algo ainda mais mágico aparece.
    Para ver do que se trata em relação aos zeros triviais e não triviais, veja esta animação da Wikipédia: [https://en.wikipedia.org/wiki/File:Riemann3d_Re_0.1_to_0.9_I...](https://en.wikipedia.org/wiki/File:Riemann3d_Re_0.1_to_0.9_Im_1_to_51.ogg)
    Basicamente, acho que isso sugere que existe alguma outra relação entre os números reais e imaginários que ainda não descobrimos.
    E, como a matemática de Riemann participa da mecânica quântica, isso também tem implicações para a busca de uma teoria da gravidade.
    Parece uma ciência estranha pensar que os números primos estejam, ou possam estar, envolvidos em uma teoria da gravidade.

  • Fiquei curioso com a expressão “eles finalmente fizeram algumas jogadas pouco ortodoxas para romper a barreira de Ingham”.
    Por que trazer métodos de outra área seria pouco ortodoxo? Para quem vem da engenharia, isso é até comum. A análise harmônica é uma ferramenta básica em várias áreas, como áudio, ondas, análise elétrica e estatística, e seus algoritmos também são, internamente, matemática pura.
    Se você quer encontrar estruturas repetitivas em algum sistema de base, não é normal experimentar várias técnicas de representação e escolher a que melhor se ajusta ao problema?

    • A citação não me parece dizer que a parte pouco ortodoxa da abordagem tenha sido simplesmente usar ideias de análise harmônica. Usar análise harmônica em teoria dos números não é nenhuma novidade.
      Na primeira aula de teoria analítica dos números, a ideia central — e também a ideia central do famoso artigo de Riemann de 1859 — pode ser descrita como “análise harmônica”. Não é coincidência, já que Riemann foi um pioneiro da área: https://old.reddit.com/r/math/comments/16bh3mi/what_is_the_b...
      A grande corrente mais quente da teoria dos números hoje também é, essencialmente, análise harmônica de “dimensão superior” sobre corpos numéricos: https://en.wikipedia.org/wiki/Automorphic_form, https://en.wikipedia.org/wiki/Langlands_program. O caso unidimensional que o programa de Langlands busca generalizar é https://en.wikipedia.org/wiki/Tate%27s_thesis, também chamado de “análise de Fourier sobre corpos numéricos”, uma das ideias mais importantes da teoria dos números do século 20.
      Entre as referências do artigo de Guth-Maynard também está o livro de 1994 H. Montgomery, Ten Lectures On The Interface Between Analytic Number Theory And Harmonic Analysis, No. 84. American Mathematical Soc., 1994. Já em 1994 havia dez palestras inteiras sobre a interface entre os temas e, pelo número de citações do livro, havia muito mais pontos de contato. Eu mesmo citei esse livro em mais da metade dos meus artigos.
      O surpreendente não é o fato de terem usado análise harmônica em si, mas onde e como ela foi aplicada. Essa é a parte realmente impossível de transmitir ao público geral, então não culpo o autor da matéria.
      Isso soa como dizer “por que criar uma conexão é surpreendente?”, mas avanços muitas vezes vêm de novas conexões, e o fato de esses avanços acontecerem de vez em quando não significa que novas conexões deixem de ser surpreendentes.
    • “Pouco ortodoxo” talvez seja uma expressão um pouco forte, mas o que provavelmente se quer dizer é que aplicaram uma técnica existente de outra área de uma nova maneira.
      Na matemática, grandes avanços surgem com bastante frequência quando alguém percebe um paralelismo entre duas áreas que, à primeira vista, parecem não relacionadas, e usa uma ideia de uma área como insight para a outra.
      A parte difícil é que essas conexões entre áreas normalmente não são óbvias. Ver a semelhança pode exigir um salto considerável de compreensão.
    • É uma expressão meio engraçada. É só o jornalista escrevendo como jornalista.
      Também dá para dizer que toda descoberta matemática envolve, em algum grau, uma jogada “pouco ortodoxa”. Afinal, o ortodoxo é tudo o que já se sabia até agora.

  • Na frase “À primeira vista, parece bastante aleatório. Mas acredita-se que, na verdade, exista esse tipo de estrutura oculta dentro dos primos”, fico curioso sobre como seria um padrão de primos hipotético
    A expectativa é algo como uma fórmula fechada? Se a hipótese de Riemann for provada, qual seria o próximo passo para entender a distribuição? Ou espera-se que a própria prova contenha essa resposta?

  • Toda vez que ouço falar de James Maynard, fica mais forte a impressão de que ele é um gênio do tipo que surge uma vez por geração
    Ele já contribuiu tanto para a teoria dos números primos que começo a sentir que talvez eu veja a prova da hipótese de Riemann ainda em vida

  • É a primeira vez que vejo essa imagem, e ela é envolvente, então fiquei curioso. Os padrões que aparecem quando se desenham os primos em um gráfico de coordenadas polares são uma descoberta recente, ou já são conhecidos há muito tempo e foram usados apenas como ilustração? Queria saber o nome e a história

  • Saindo um pouco pela tangente, esta frase me faz pensar em um aspecto dos provadores automáticos com o qual talvez ainda nem tenhamos começado a lidar
    “O matemático Alex Kontorovich, da Rutgers University, diz: ‘É um avanço sensacional. Esta prova contém um monte de ideias novas que as pessoas vão explorar nos próximos anos’”
    Muitas vezes, a prova de algo é mais interessante não como um meio de conferir rigor, mas como uma nova perspectiva sobre o objeto. Fico curioso se já houve trabalho nesse sentido em matemática automatizada