Théorème de Skolem-Mahler-Lech

En théorie additive des nombres, le théorème de Skolem–Mahler–Lech déclare que si une suite de nombres est générée par une relation de récurrence linéaire, alors, avec des exceptions finies, les positions aux quelles la suite est nulle forment un motif qui se répète. Plus précisément, cet ensemble de positions peut être décomposé en un ensemble fini et en plusieurs suites arithmétiques complètes. Ici, une suite arithmétique infinie est complète s'il existe des nombres entiers a et b tels que la suite est constituée d'entiers naturels égaux à b modulo a.

Ce résultat est nommé d'après Thoralf Skolem (qui a prouvé le théorème pour des suites de nombres rationnels), Kurt Mahler (qui l'a prouvé pour des suites de nombres algébriques) et Christer Lech (qui l'a prouvé pour des suites dont les éléments appartiennent à n'importe quel champ de caractéristique 0). Ses preuves utilisent l'analyse p-adique.

Exemple

On considère la suite

0, 0, 1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 8, 0, ...

qui alternent entre des zéros et les nombres de Fibonacci. Cette séquence peut être générée par la relation de récurrence

$F(i)=F(i-2)+F(i-4)$

(Une forme modifiée de la suite de Fibonacci), à partir des cas de base F(1) = F(2) = F(4) = 0 et F(3) = 1. Pour cette suite, F(i) = 0 si et seulement si i vaut 1 ou est pair. Ainsi, les positions auxquelles la séquence est nulle peuvent être partitionnées en un ensemble fini (le singleton {1}) et une progression arithmétique complète (les nombres pairs positifs).

Dans cet exemple, une seule progression arithmétique était nécessaire, mais d'autres suites définies par récurrence peuvent avoir des zéros à des positions formant plusieurs progressions arithmétiques.

Résultats connexes

Le problème de Skolem consiste à déterminer si une suite définie par récurrence donnée possède un zéro. Il existe un algorithme pour tester s'il y a une infinité de zéros et, si la réponse est oui, trouver la décomposition de ces zéros dans des ensembles périodiques par le théorème de Skolem–Mahler–Lech. Cependant, on ignore s'il existe un algorithme pour déterminer si une suite par récurrence a des zéros non périodiques. (Ouaknine et Worrell 2012).

Références

• « {{{1}}} », cited in Lech 1953.
• « {{{1}}} », cited in Lech 1953.
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».