Problème de Skolem

En mathématiques, et plus particulièrement en théorie des nombres, le problème de Skolem est le problème de déterminer s'il existe, parmi les éléments d'une suite récurrente linéaire à coefficients constants, un terme qui est nul. Le problème peut être formulé pour divers types de nombres, y compris les entiers relatifs, les nombres rationnels, et les nombres algébriques. Il n'est pas connu s'il existe un algorithme qui permet de résoudre ce problème[1].

Relations de récurrence

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.

Résultats partiels

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].

Complexité

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.

Notes et références

• (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

1. Ouaknine et Worrell 2012
2. Skolem 1933.
3. Ouaknine et Worrell 2012 citent un autre article de Skolem datant de 1934 pour ce résultat.
4. Mahler 1935.
5. Mahler 1956.
6. Mahler 1959.
7. Lech 1953
8. Berstel et Mignotte 1976.
9. Mignotte, Shorey et Tijdeman 1984.
10. Vereshchagin 1985
11. V. Halava, T. Harju, M. Hirvensalo et J. Karhumäki, « Skolem's Problem – On the Border Between Decidability and Undecidability », Technical Report 683, Turku Centre for Computer Science,‎ 2005.
12. B. Litow, « A decision method for the rational sequence problem », Electronic Colloquium on Computational Complexity, vol. 4,‎ 1997.
13. Tao 2012, Section 1.9
14. Blondel et Portier 2002.
15. Chonev et Ouakine Worrell
16. Chonev 2015.
17. Sha 2019.
18. Dans ce contexte, une suite récurrence est dite simple si toutes les racines de son polynôme caractéristique sont simples.

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)
• [2022] Yuri Bilu, Florian Luca, Joris Nieuwveld et Joël Ouaknine, « Skolem Meets Schanuel », ArXiv,‎ 28 avril 2022 (DOI 10.48550/arXiv.2204.13417, arXiv 2204.13417)
• [2024] Yuri Bilu, Florian Luca, Joris Nieuwveld et Joël Ouaknine, « On the p-adic zeros of the Tribonacci sequence », Mathematics of Computation, vol. 93, n^o 347,‎ mai 2024, p. 1333–1353 (DOI 10.1090/mcom/3893, arXiv 2210.16959)