Problème de Skolem

De testwiki
Aller à la navigation Aller à la recherche

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

F(n)=F(n−1)+F(n−2).

avec les valeurs initiales F(0)=0 et 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]Modèle:,[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]Modèle:,[5]Modèle:,[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]Modèle:,[9]Modèle:,[10]. Deux démonstrations annoncées[11]Modèle:,[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

Modèle:Traduction/Référence

Notes

Modèle:Références

Bibliographie


Modèle:Portail

  1. ↑ 1,0 1,1 1,2 et 1,3 Modèle:Harvsp
  2. ↑ Modèle:Harvsp.
  3. ↑ Modèle:Harvsp citent un autre article de Skolem datant de 1934 pour ce résultat.
  4. ↑ Modèle:Harvsp.
  5. ↑ Modèle:Harvsp.
  6. ↑ Modèle:Harvsp.
  7. ↑ Modèle:Harvsp
  8. ↑ Modèle:Harvsp.
  9. ↑ Modèle:Harvsp.
  10. ↑ Modèle:Harvsp
  11. ↑ Modèle:Article.
  12. ↑ Modèle:Article.
  13. ↑ Modèle:Harvsp
  14. ↑ Modèle:Harvsp.
  15. ↑ Modèle:Harvsp
  16. ↑ Modèle:Harvsp.
  17. ↑ Modèle:Harvsp.
  18. ↑ Dans ce contexte, une suite récurrence est dite simple si toutes les racines de son polynôme caractéristique sont simples.
Récupérée de "https://fr.wiki.beta.math.wmflabs.org/w/index.php?title=Problème_de_Skolem&oldid=18026"