Problème de Skolem

Une relation de récurrence linéaire définit les valeurs d'une suite de nombres comme combinaison linéaire de valeurs précédentes ; par exemple, les entiers de la suite de Fibonacci peuvent être définis par la relation de récurrence

${\displaystyle F(n)=F(n-1)+F(n-2).}$

avec les valeurs initiales ${\displaystyle F(0)=0}$ et ${\displaystyle F(1)=1}$.

Le problème de Skolem porte le nom de Thoralf Skolem qui, dans un article de 1933, démontre ce qu'on appelle le théorème de Skolem-Mahler-Lech sur les termes nuls d'une suite vérifiant une relation de récurrence linéaire à coefficients constants[2] - [3]. Le théorème dit que, si une telle suite possède des termes nuls, ceux-ci apparaissent, à un nombre fini d'exceptions près, à des positions qui se répètent régulièrement. Skolem démontre cette propriété pour des récurrences sur les nombres rationnels, et Mahler[4] - [5] - [6] puis Lech[7] l'étendent à d'autres corps de nombres. Les démonstrations du théorème ne donnent pas d'indication comment on pourrait tester si des zéros existent.

Il existe un algorithme qui permet de tester si une suite récurrente à coefficients constants possède une infinité de termes nuls, et s'il en est ainsi, de construire une décomposition des positions de ces termes en sous-suites périodiques ; la construction est basée sur les propriétés algébriques des racines du polynôme caractéristique de la suite[8]. La partie difficile du problème est de déterminer si l'ensemble des zéros qui ne se répètent pas est vide ou non[1].

Des résultats partiels sont connus concernant le cas particulier de récurrences de degré au plus 4, mais ces solutions ne s'appliquent pas en degré cinq ou plus[1] - [9] - [10]. Deux démonstrations annoncées[11] - [12] se sont avérées incomplètes[1]. Le problème est cité dans le livre de Terence Tao tiré de son blog[13].

Pour des suites récurrentes entières, le problème de Skolem est NP-difficile[14].

Chonev, Ouaknine et Worrell[15] ont donné une borne (non explicite) N qui est essentiellement polynomiale en les coefficients et les termes initiaux de la récurrence, tel que les termes d’indice plus grands que N sont tous non nuls, lorsque la récurrence est d'ordre 2, 3 ou 4. Une exposition détaillée en est donné dans la thèse de doctorat de Chonev[16].

Cette borne a été généralisée par Min Sha[17] au cas des suites récurrences simples[18] de nombres algébriques qui ont soit une racine caractéristique dominante, soit deux racines caractéristiques de module maximal. Il apparaît que ces conditions couvrent la plupart des cas pour des suites récurrentes à termes rationnels.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Skolem problem » (voir la liste des auteurs).

Notes

Bibliographie

• [1933] Thoralf Skolem, « Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen », Oslo Vid. akad. Skrifter, vol. I, n^o 6,‎ 1933
• [1935] Kurt Mahler, « Eine arithmetische Eigenschaft der Taylor-Koeffizienten rationaler Funktionen », Akad. Wetensch. Amsterdam, Proc., vol. 38,‎ 1935, p. 50-60.
• [1953] (en) C. Lech, « A Note on Recurring Series », Arkiv för Matematik, vol. 2,‎ 1953, p. 417-421 (DOI 10.1007/bf02590997).
• [1956] Kurt Mahler, « On the Taylor coefficients of rational functions », Proc. Cambridge Philos. Soc., vol. 52,‎ 1956, p. 39-48 (DOI 10.1017/s0305004100030966).
• [1957] Kurt Mahler, « Addendum to the paper "On the Taylor coefficients of rational functions" », Proc. Cambridge Philos. Soc., vol. 53,‎ 1957, p. 544 (DOI 10.1017/s0305004100032552)
• [1976] Jean Berstel et Maurice Mignotte, « Deux propriétés décidables des suites récurrentes linéaires », Bulletin de la Société Mathématique de France, vol. 104, n^o 2,‎ 1976, p. 175–184 (MR 0414475, lire en ligne).
• [1984] Maurice Mignotte, Tarlok Nath Shorey et Robert Tijdeman, « The distance between terms of an algebraic recurrence sequence », Journal für die Reine und Angewandte Mathematik, vol. 349,‎ 1984, p. 63–76 (MR 743965).
• [1984] (ru) N. K. Vereshchagin, « The problem of the appearance of a zero in a linear recursive sequence », Matematicheskie Zametki, vol. 38, n^o 2,‎ 1985, p. 177–189, 347 (MR 808885).
• [2002] Vincent D. Blondel et Natacha Portier, « The presence of a zero in an integer linear recurrent sequence is NP-hard to decide », Linear Algebra and its Applications, vol. 351/352,‎ 2002, p. 91–98 (DOI 10.1016/S0024-3795(01)00466-9, MR 1917474).
• [2007] Terence Tao, « Open question: effective Skolem–Mahler–Lech theorem », What's new, 25 mai 2007
• [2008] Terence Tao, Structure and Randomness: Pages From Year One of a Mathematical Blog, Amer. Math. Soc., 2008
• [2012] 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, Springer-Verlag, coll. « Lecture Notes in Computer Science vol. 7550 », 2012 (DOI 10.1007/978-3-642-33512-9_3, MR 3040104), p. 21–28.
• [2015] Ventsislav Chonev, Reachability Problems for Linear Dynamical Systems (Thèse de doctorat), University of Oxford, 2015 (lire en ligne).
• [2016] Ventsislav Chonev, Joël Ouaknine et James Worrell, « On the complexity of the orbit problem », Journal of the ACM, vol. 63,‎ 2016, article n^o 23 (arXiv 1303.2981).
• [2016] Min Sha, « Effective results on the Skolem Problem for linear recurrence sequences », Journal of Number Theory, vol. 197,‎ 2019, p. 228–249 (DOI 10.1016/j.jnt.2018.08.012).
• [2021] Paul C. Bell, Igor Potapov et Pavel Semukhin, « On the mortality problem: From multiplicative matrix equations to linear recurrence sequences and beyond », Information and Computation, vol. 281,‎ décembre 2021, article n^o 104736 (DOI 10.1016/j.ic.2021.104736, arXiv 1902.10188)