Résumé - Sur la complexité du problème de Skolem à basse ordre

Sur la complexité du problème de Skolem à basse ordre

2025-07-15 12:04:28

{"Piotr Bacik","Joël Ouaknine","James Worrell"}

{cs.CC,cs.LO}

Le problème de Skolem demande si une séquence de récurrence linéaire donnée (LRS) possède une terme nul. Bien que le problème soit indécidable en général, l'article présente un algorithme aléatoire pour une version bornée du problème, déterminant s'il existe un terme nul dans une plage spécifiée. Cet algorithme s'exécute en temps polynomial pour les LRS de degré au plus d, et comme corollaire, montre que le problème de Skolem non borné pour les LRS de degré au plus 4 se situe dans coRP (RAM certifié avec temps polynomial). La clé de l'algorithme réside dans l'extension de l'LRS à une fonction analytique p-adique F, et l'utilisation de l'analyse p-adique pour trouver des zéros candidats dans une plage exponentiellement grande. L'algorithme effectue une recherche en profondeur de tous les résidus m dans la plage, et pour chaque zéro candidat, il construit un circuit arithmétique représentant le terme um et vérifie la nullité en temps polynomial aléatoire. Le temps d'exécution de l'algorithme est exponentiel par rapport au degré de l'LRS, ce qui est nécessaire en raison de la difficulté NP du problème borné. Cependant, même pour les LRS d'un degré fixe, le problème implique de détecter des zéros dans une plage exponentiellement grande, ce qui nécessite l'utilisation de l'analyse p-adique. L'algorithme est basé sur une approche p-adique introduite par Skolem dans sa preuve originale du Théorème de Skolem-Mahler-Lech. Cela implique l'extension de l'LRS à une fonction analytique p-adique F, et l'utilisation de l'analyse p-adique pour trouver les zéros de F. L'algorithme utilise la représentation de série Mahler des séries p-adiques, ce qui lui permet de travailler avec l'LRS sous-jacent sans calculer directement avec les nombres p-adiques. La correction de l'algorithme dépend d'une raffinement quantitatif de la preuve de Skolem, due à Van der Poorten et Schlickewei. Ce résultat fournit une borne supérieure sur le nombre de zéros de F dans le champ p-adique, ce qui se traduit par une borne polynomiale sur le nombre de zéros candidats examinés par l'algorithme. De plus, ce résultat est utilisé en combinaison avec le Théorème de préparation de Weierstrass pour déterminer en temps polynomial si la série F a un zéro dans le champ p-adique. En conclusion, l'article présente un algorithme aléatoire pour le problème de Skolem borné qui s'exécute en temps polynomial pour les LRS de degré au plus d, et montre que le problème de Skolem non borné pour les LRS de degré au plus 4 se situe dans coRP. La complexité de l'algorithme est exponentielle par rapport au degré de l'LRS, ce qui est nécessaire en raison de la difficulté NP du problème.