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 engendrée par une relation de récurrence linéaire, alors, avec des exceptions finies, les positions auxquelles 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 infinie est dite arithmétique complète s'il existe des nombres entiers a et b tels que la suite est constituée de tous les entiers naturels congrus à 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 corps 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 alterne la suite nulle et la suite de Fibonacci. Cette suite est définie par la relation de récurrence
(une forme modifiée de celle de Fibonacci) et les quatre premières valeurs F(0) = F(1) = F(3) = 0 et F(2) = 1. Pour cette suite, F(i) = 0 si et seulement si i est nul ou impair. Ainsi, les positions auxquelles la suite est nulle peuvent être partitionnées en un ensemble fini (le singleton {0}) et une suite arithmétique complète (les entiers positifs impairs).
Dans cet exemple, une seule suite arithmétique était nécessaire, mais d'autres suites définies par récurrence peuvent avoir des zéros à des positions formant plusieurs suites 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
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Skolem–Mahler–Lech theorem » (voir la liste des auteurs).
- (de) Th. Skolem, « Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen », Oslo Vid. akad. Skrifter, vol. I, no 6, , cité dans Lech 1953.
- (de) K. Mahler, « Eine arithmetische Eigenschaft der Taylor-koeffizienten rationaler Funktionen », Akad. Wetensch. Amsterdam, Proc., vol. 38, , p. 50-60, cité dans Lech 1953.
- (en) C. Lech, « A Note on Recurring Series », Arkiv för Matematik, vol. 2, , p. 417-421 (DOI 10.1007/bf02590997).
- (en) K. Mahler, « On the Taylor coefficients of rational functions », Proc. Cambridge Philos. Soc., vol. 52, , p. 39-48 (DOI 10.1017/s0305004100030966).
- (en) K. Mahler, « Addendum to the paper "On the Taylor coefficients of rational functions" », Proc. Cambridge Philos. Soc., vol. 53, , p. 544 (DOI 10.1017/s0305004100032552).
- (en) Joël Ouaknine et James Worrell, « Decision problems for linear recurrence sequences », dans Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, France, September 17-19, 2012, Proceedings, Heidelberg, Springer-Verlag, coll. « Lecture Notes in Computer Science » (no 7550), , 21-28 p. (DOI 10.1007/978-3-642-33512-9_3, MR 3040104).