Le comportement étonnant des séquences récursives | Magazine Quanta

En mathématiques, des règles simples peuvent ouvrir la voie à des univers de complexité et de beauté. Prenons la célèbre séquence de Fibonacci, définie comme suit : elle commence par 1 et 1, et chaque nombre suivant est la somme des deux précédents. Les premiers chiffres sont :

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

Simple, certes, mais cette recette sans prétention donne naissance à un modèle d’une portée considérable, qui semble être tissé dans le tissu même du monde naturel. On le voit dans les verticilles des coquilles de nautiles, les os de nos doigts et la disposition des feuilles sur les branches des arbres. Sa portée mathématique s'étend, entre autres domaines, à la géométrie, à l'algèbre et aux probabilités. Huit siècles après que la séquence a été introduite en Occident – ​​les mathématiciens indiens l’ont étudiée bien avant Fibonacci – les nombres continuent de susciter l’intérêt des chercheurs, ce qui témoigne de la profondeur mathématique qui peut sous-tendre même la séquence de nombres la plus élémentaire.

Dans la séquence de Fibonacci, chaque terme s’appuie sur ceux qui le précèdent. De telles séquences récursives peuvent présenter un large éventail de comportements, certains merveilleusement contre-intuitifs. Prenons par exemple une curieuse famille de séquences décrite pour la première fois dans les années 1980 par le mathématicien américain Michael Somos.

Comme la séquence de Fibonacci, une séquence de Somos commence par une série de un. Un Somos-k la séquence commence par k d'eux. Chaque nouveau mandat d'un Somos-k la séquence est définie en associant les termes précédents, en multipliant chaque paire ensemble, en additionnant les paires, puis en divisant par le terme k positions en arrière dans la séquence.

Les séquences ne sont pas très intéressantes si k est égal à 1, 2 ou 3 – ce ne sont que des séries de répétitions. Mais pour k = 4, 5, 6 ou 7 les séquences ont une propriété étrange. Même s’il y a beaucoup de divisions, les fractions n’apparaissent pas.

"Normalement, nous n'avons pas ce genre de phénomène", a déclaré Somos. « C'est une récidive d'une simplicité trompeuse, semblable à celle de Fibonacci. Mais il y a beaucoup de choses derrière cette simplicité.

D’autres mathématiciens continuent de découvrir des liens surprenants entre les séquences de Somos et des domaines mathématiques apparemment sans rapport. Un article publié en juillet les utilise pour construire des solutions à un système d'équations différentielles utilisé pour tout modéliser, des interactions prédateur-proie aux ondes se déplaçant dans des plasmas à haute énergie. Ils sont également utilisés pour étudier la structure d'objets mathématiques appelés algèbres amassées et sont connectés à courbes elliptiques – qui ont été la clé pour déchiffrer le dernier théorème de Fermat.

Janice Malouf, étudiant diplômé de l'Université de l'Illinois, a publié la première preuve que les séquences Somos-4 et Somos-5 font partie intégrante (ce qui signifie que tous leurs termes sont des entiers) en 1992. Autres preuves du même résultat par différents mathématiciens sont apparus à peu près à la même époque, accompagnés de preuves que les séquences Somos-6 et Somos-7 sont intégrales.

Cette étrange propriété des séquences de Somos a stupéfié les mathématiciens. "Les séquences de Somos m'ont intrigué dès que j'en ai entendu parler", a déclaré Jacques Propp, professeur de mathématiques à l'Université du Massachusetts, Lowell. « Le fait que Somos-4 à Somos-7 donnent toujours des nombres entiers, quelle que soit la distance parcourue, semblait être un miracle quand on regardait les choses d'un point de vue naïf. Il fallait donc une perspective différente.

Propp a découvert une nouvelle perspective au début des années 2000, lorsque lui et ses collègues ont découvert que les nombres de la séquence Somos-4 comptent en réalité quelque chose. Les termes de la séquence correspondent à des structures trouvées dans certains graphiques. Pour certains graphiques, il est possible d'associer des sommets (points) avec des arêtes (lignes) de sorte que chaque sommet soit connecté exactement à un autre sommet — il n'y a pas de sommets non appariés et aucun sommet connecté à plus d'une arête. Les termes de la séquence Somos-4 comptent le nombre de correspondances parfaites différentes pour une séquence particulière de graphiques.

La découverte a non seulement offert une nouvelle perspective sur les séquences de Somos, mais a également introduit de nouvelles façons de penser et d'analyser les transformations graphiques. Propp et ses étudiants ont célébré en affichant le résultat sur un T-shirt.

"Pour moi, une grande partie de l'attrait des mathématiques réside dans le fait que vous arrivez à la même destination par des chemins différents et qu'il semble que quelque chose de miraculeux ou de profond se passe", a déclaré Propp. « Ce qui est intéressant avec ces séquences, c'est qu'il existe différents points de vue qui expliquent pourquoi vous obtenez des nombres entiers. Il y a là des profondeurs cachées.

L'histoire change pour les séquences Somos de numérotation plus élevée. Les 18 premiers termes de Somos-8 sont des entiers, mais le 19ème terme est une fraction. Chaque séquence Somos suivante contient également des valeurs fractionnaires.

Un autre type de séquence, développé par le mathématicien allemand Fritz Göbel dans les années 1970, constitue un contrepoint intéressant aux séquences de Somos. Le nLe terme de la suite de Göbel est défini comme la somme des carrés de tous les termes précédents, plus 1, divisée par n. Comme les séquences de Somos, la séquence de Göbel implique une division, on peut donc s'attendre à ce que les termes ne restent pas des entiers. Mais pendant un moment – ​​alors que la séquence devient énorme – ils semblent l’être.

Le 10e terme de la séquence de Göbel est d'environ 1.5 million, le 11e environ 267 milliards. Le 43ème terme est beaucoup trop grand pour être calculé : il comporte quelque 178 milliards de chiffres. Mais en 1975, le mathématicien néerlandais Hendrik Lenstra a montré que contrairement aux 42 premiers termes, ce 43ème terme n'est pas un nombre entier.

Les séquences de Göbel peuvent être généralisées en remplaçant les carrés de la somme par des cubes, des puissances quatrièmes ou même des exposants supérieurs. (Selon cette convention, sa séquence originale est appelée séquence à 2-Göbel.) Ces séquences affichent également une tendance surprenante à commencer par une étendue étendue de termes entiers. En 1988, Henry Ibstedt montré que les 89 premiers termes de la séquence de 3-Göbel (qui utilise des cubes au lieu de carrés) sont des entiers, mais pas le 90ème. Des recherches ultérieures sur d'autres séquences de Göbel ont révélé des étendues encore plus longues. La séquence de 31 Göbel, par exemple, démarre avec 1,077 XNUMX termes entiers.

En juillet, les mathématiciens de l'Université de Kyushu, Rinnosuke Matsuhira, Toshiki Matsusaka et Koki Tsuchida partagé un papier montrant que pour un k-Séquence de Göbel, quel que soit le choix de k, les 19 premiers termes de la suite sont toujours des entiers. Ils ont été inspirés pour se pencher sur la question par un manga japonais intitulé Seisū-tan, qui se traduit par « Le conte des nombres entiers ». UN cadre dans la bande dessinée a demandé aux lecteurs de déterminer la valeur minimale possible de N_k, le point auquel un k-La séquence de Göbel cesse de produire des termes entiers. Les trois mathématiciens ont décidé de répondre à la question. "La persistance inattendue des nombres entiers pendant une durée aussi longue contredit notre intuition", a déclaré Matsusaka. "Lorsque des phénomènes se produisent contrairement à l'intuition, je crois qu'il y a toujours de la beauté présente."

Ils ont trouvé un modèle de comportement répétitif comme k augmente. En se concentrant sur un nombre fini de cas répétitifs, ils ont rendu le calcul réalisable et ont pu compléter la preuve.

Un regard plus attentif sur la séquence N_k révèle une autre surprise : N_k est premier bien plus souvent que ce à quoi on pourrait s'attendre s'il était purement aléatoire. "Avec le k"Séquence de Göbel, ce n'est pas seulement remarquable qu'ils soient des entiers", a déclaré Richard Green, mathématicien à l'Université du Colorado. « Ce qui est remarquable, c'est que les nombres premiers apparaissent si souvent. Cela donne l’impression que quelque chose de plus profond pourrait se produire.

Bien que le nouvel article présente une preuve que N_k est toujours au moins 19, on ne sait pas si est toujours fini, ou s'il existe un k pour lequel la séquence contient indéfiniment des entiers. "N_k se comporte mystérieusement. … Il existe un désir fondamental de comprendre son schéma sous-jacent », a déclaré Matsusaka. « Cela ressemble peut-être à la joie que j’éprouvais quand j’étais enfant en résolvant les énigmes proposées par les enseignants. Même maintenant, ces sentiments de cette époque persistent en moi.

Quanta mène une série d’enquêtes pour mieux servir notre public. Prenez notre enquête auprès des lecteurs de mathématiques et vous serez inscrit pour gagner gratuitement Quanta marchandise.