O comportamento surpreendente das sequências recursivas | Revista Quanta

Na matemática, regras simples podem desbloquear universos de complexidade e beleza. Tomemos como exemplo a famosa sequência de Fibonacci, que é definida da seguinte forma: começa com 1 e 1, e cada número subsequente é a soma dos dois anteriores. Os primeiros números são:

1, 1, 2, 3, 5, 8, 13, 21, 34…

Simples, sim, mas esta receita despretensiosa dá origem a um padrão de significado de longo alcance, que parece estar entrelaçado na própria estrutura do mundo natural. É visto nas espirais das conchas dos náutilos, nos ossos dos nossos dedos e na disposição das folhas nos galhos das árvores. Seu alcance matemático se estende à geometria, álgebra e probabilidade, entre outras áreas. Oito séculos desde que a sequência foi introduzida no Ocidente – os matemáticos indianos estudaram-na muito antes de Fibonacci – os números continuam a atrair o interesse dos investigadores, uma prova de quanta profundidade matemática pode estar subjacente até mesmo à sequência numérica mais elementar.

Na sequência de Fibonacci, cada termo se baseia nos anteriores. Essas sequências recursivas podem exibir uma ampla gama de comportamentos, alguns deles maravilhosamente contra-intuitivos. Tomemos, por exemplo, uma curiosa família de sequências descrita pela primeira vez na década de 1980 pelo matemático americano Michael Somos.

Assim como a sequência de Fibonacci, uma sequência Somos começa com uma série de uns. A Somos-k sequência começa com k deles. Cada novo termo de um Somos-k a sequência é definida emparelhando os termos anteriores, multiplicando cada par, somando os pares e depois dividindo pelo termo k posições de volta na sequência.

As sequências não são muito interessantes se k é igual a 1, 2 ou 3 - são apenas uma série de repetições. Mas pelo k = 4, 5, 6 ou 7 as sequências têm uma propriedade estranha. Embora haja muita divisão envolvida, as frações não aparecem.

“Normalmente não temos esse tipo de fenômeno”, disse Somos. “É uma recorrência aparentemente simples, semelhante a Fibonacci. Mas há muito por trás dessa simplicidade.”

Outros matemáticos continuam a descobrir conexões surpreendentes entre as sequências de Somos e áreas aparentemente não relacionadas da matemática. Um jornal publicado em julho os utiliza para construir soluções a um sistema de equações diferenciais usado para modelar tudo, desde interações predador-presa até ondas viajando em plasmas de alta energia. Eles também são usados ​​para estudar a estrutura de objetos matemáticos chamados álgebras de cluster e estão conectados a curvas elípticas - que foram a chave para decifrar o Último Teorema de Fermat.

Janice Malouf, estudante de pós-graduação da Universidade de Illinois, publicou a primeira prova de que as sequências Somos-4 e Somos-5 são integrais (ou seja, todos os seus termos são números inteiros) em 1992. outras provas do mesmo resultado por diferentes matemáticos apareceram na mesma época, junto com provas de que as sequências Somos-6 e Somos-7 são integrais.

Esta estranha propriedade das sequências de Somos surpreendeu os matemáticos. “Somos sequências me intrigaram assim que tomei conhecimento delas”, disse James Propp, professor de matemática na Universidade de Massachusetts, Lowell. “O fato de Somos-4 até Somos-7 sempre fornecer números inteiros, não importa o quão longe você vá, parecia um milagre quando você via as coisas de uma perspectiva ingênua. Portanto, uma perspectiva diferente era necessária.”

Propp encontrou uma nova perspectiva no início dos anos 2000, quando ele e seus colegas descobriram que os números na sequência Somos-4 estão, na verdade, contando alguma coisa. Os termos da sequência correspondem a estruturas encontradas em determinados gráficos. Para alguns gráficos, é possível emparelhar vértices (pontos) com arestas (linhas) de modo que cada vértice esteja conectado exatamente a um outro vértice - não há vértices desemparelhados e nenhum vértice conectado a mais de uma aresta. Os termos da sequência Somos-4 contam o número de diferentes emparelhamentos perfeitos para uma determinada sequência de gráficos.

A descoberta não apenas ofereceu uma nova perspectiva sobre as sequências de Somos, mas também introduziu novas maneiras de pensar e analisar as transformações de grafos. Propp e seus alunos comemoraram fazendo com que o resultado fosse exibido em um T-shirt.

“Para mim, grande parte do fascínio da matemática é quando você chega ao mesmo destino por caminhos diferentes e parece que algo milagroso ou profundo está acontecendo”, disse Propp. “O legal dessas sequências é que existem vários pontos de vista que explicam por que você obtém números inteiros. Existem profundezas escondidas lá.”

A história muda para sequências Somos de numeração mais alta. Os primeiros 18 termos de Somos-8 são inteiros, mas o 19º termo é uma fração. Cada sequência Somos depois disso também contém valores fracionários.

Outro tipo de sequência, desenvolvida pelo matemático alemão Fritz Göbel na década de 1970, é um contraponto interessante às sequências Somos. O nO quinto termo da sequência de Göbel é definido como a soma dos quadrados de todos os termos anteriores, mais 1, dividido por n. Tal como as sequências Somos, a sequência de Göbel envolve divisão, por isso podemos esperar que os termos não permaneçam inteiros. Mas por um tempo – à medida que a sequência fica enorme – eles parecem ser.

O décimo termo na sequência de Göbel é cerca de 10 milhão, o 1.5º, 11 bilhões. O 267º termo é demasiado grande para ser calculado – tem cerca de 43 mil milhões de dígitos. Mas em 178, o matemático holandês Hendrik Lenstra mostrou que, diferentemente dos primeiros 42 termos, este 43º termo não é um número inteiro.

As sequências de Göbel podem ser generalizadas substituindo os quadrados na soma por cubos, quartas potências ou até expoentes mais altos. (Sob esta convenção, sua sequência original é chamada de sequência 2-Göbel.) Essas sequências também exibem uma tendência surpreendente de começar com uma extensão estendida de termos inteiros. Em 1988, Henry Ibstedt mostrou que os primeiros 89 termos da sequência de 3-Göbel (que usa cubos em vez de quadrados) são inteiros, mas o 90º não é. Pesquisas subsequentes em outras sequências de Göbel encontraram trechos ainda mais longos. A sequência 31-Göbel, por exemplo, começa com impressionantes 1,077 termos inteiros.

Em julho os matemáticos da Universidade Kyushu Rinnosuke Matsuhira Toshiki Matsusaka e Koki Tsuchida compartilhou um papel mostrando que por um k-Sequência de Göbel, não importa a escolha de k, os primeiros 19 termos da sequência são sempre inteiros. Eles foram inspirados a investigar a questão por um mangá japonês chamado Seisū-tan, que se traduz como “O Conto dos Inteiros”. A quadro na história em quadrinhos pediu aos leitores que descobrissem o valor mínimo possível de N_k, o ponto em que um k-A sequência de Göbel deixa de produzir termos inteiros. Os três matemáticos decidiram responder à pergunta. “A persistência inesperada de números inteiros por um período tão prolongado contradiz a nossa intuição”, disse Matsusaka. “Quando os fenômenos ocorrem contrariamente à intuição, acredito que sempre há beleza presente.”

Eles encontraram um padrão de repetição de comportamento como k aumenta. Ao concentrarem-se num número finito de casos repetidos, eles tornaram o cálculo tratável e conseguiram completar a prova.

Uma olhada mais de perto na sequência N_k revela outra surpresa: N_k é primo com muito mais frequência do que você esperaria se fosse puramente aleatório. "Com o k-Sequência de Göbel, não é apenas notável que sejam números inteiros”, disse Ricardo Verde, um matemático da Universidade do Colorado. “O que é notável é que os números primos aparecem com tanta frequência. Isso faz parecer que algo mais profundo pode estar acontecendo.”

Embora o novo artigo apresente uma prova de que N_k é sempre pelo menos 19, não se sabe se é sempre finito ou se existe um k para o qual a sequência contém inteiros indefinidamente. “N_k se comporta misteriosamente. …Há um desejo fundamental de compreender o seu padrão subjacente”, disse Matsusaka. “Pode ser semelhante à alegria que senti quando criança ao resolver quebra-cabeças dados pelos professores. Mesmo agora, esses sentimentos daquela época permanecem dentro de mim.”

Quanta está realizando uma série de pesquisas para melhor atender nosso público. Pegue nosso pesquisa com leitores de matemática e você estará inscrito para ganhar de graça Quanta mercadoria.