On the $p$-adic Skolem Problem

Résumé technique : Sur le problème de Skolem p-adique

1. Énoncé du problème
Le problème de Skolem demande si une suite récurrente linéaire (SRL) d'entiers donnée possède un terme nul. Bien que le théorème de Skolem-Mahler-Lech (démontré il y a plus de 90 ans) établisse que l'ensemble des zéros d'une SRL non dégénérée se compose d'un ensemble fini et d'un nombre fini de progressions arithmétiques, la preuve est inefficace ; elle ne fournit pas d'algorithme pour déterminer si un tel zéro existe. Par conséquent, la décidabilité du problème de Skolem demeure une question ouverte majeure en informatique théorique.

Cet article traite d'une relaxation du problème : le problème de Skolem p-adique. Au lieu de rechercher des zéros dans les nombres naturels ($\mathbb{N}$), les auteurs examinent si une SRL possède un zéro dans l'anneau des entiers p-adiques ($\mathbb{Z}_p$) pour un nombre premier $p$ donné. De plus, ils abordent le problème fonctionnel correspondant : le calcul de représentations exactes de tous ces zéros p-adiques. Bien que la résolution de la version p-adique ne résolve pas immédiatement le problème de Skolem original (car les zéros p-adiques peuvent ne pas correspondre à des zéros entiers), les auteurs démontrent que travailler p-adiquement offre une approche pratique pour trouver des zéros entiers et permet des résultats de décidabilité pour des problèmes connexes sous des hypothèses standards de théorie des nombres.

2. Méthodologie et cadre algorithmique
La méthodologie centrale consiste à étendre une SRL $u = \langle u_n \rangle$ en une fonction continue et analytique $f: \mathbb{Z}_p \to \mathbb{Z}_p$. Cela est réalisé par interpolation p-adique :

• Étant donnée une SRL avec des racines caractéristiques $\lambda_i$, la suite est décomposée en sous-suites $u_{Nn+\ell}$ (pour $0 \le \ell < N$) qui peuvent être représentées comme des fonctions analytiques $f_\ell(x)$ impliquant des exponentielles et des logarithmes p-adiques.
• Le problème de la recherche des zéros de la SRL se réduit à la recherche des zéros de ces fonctions analytiques $f_\ell$ dans $\mathbb{Z}_p$.

L'algorithme proposé combine deux stratégies de recherche distinctes pour garantir la terminaison et la correction :

1. Recherche par le lemme de Hensel : L'algorithme effectue une recherche exhaustive sur les classes résiduelles modulo $p^r$ (pour $r$ croissant). Si une classe résiduelle contient un zéro simple (où la valuation de la fonction est strictement supérieure au double de la valuation de sa dérivée), le lemme de Hensel garantit un zéro unique dans cette classe, qui peut être approché avec une précision arbitraire.
2. Énumération rationnelle : L'algorithme fait face à un défi avec les zéros multiples (multiplicité $\ge 2$), où la condition de Hensel peut ne jamais être satisfaite, entraînant potentiellement une boucle infinie. Pour résoudre cela, les auteurs s'appuient sur un lemme technique clé dérivé de la conjecture de Schanuel p-adique. Ce lemme prouve que pour les polynômes exponentiels irréductibles, tout zéro commun de multiplicité $\ge 2$ doit être rationnel. Par conséquent, l'algorithme exécute une recherche parallèle énumérant les nombres rationnels pour détecter ces zéros multiples.

L'algorithme produit une représentation finie de tous les zéros p-adiques (sous forme de disques dans $\mathbb{Z}_p$) et termine sous réserve de la conjecture de Schanuel p-adique.

3. Contributions clés et résultats théoriques
L'article présente les principaux résultats suivants :

• Décidabilité du problème de Skolem p-adique : En supposant la conjecture de Schanuel p-adique, le problème de décision $SP(\mathbb{Z}_p)$ (un zéro p-adique existe-t-il ?) est décidable, et le problème fonctionnel $FSP(\mathbb{Z}_p)$ (calculer tous les zéros p-adiques) est calculable.
• Lemme technique sur les zéros multiples : Les auteurs prouvent que si deux polynômes exponentiels premiers entre eux partagent un zéro p-adique, ce zéro doit être rationnel (sous l'hypothèse de la conjecture de Schanuel p-adique). Ce résultat est crucial pour garantir la terminaison de l'algorithme en limitant la recherche des zéros multiples à l'ensemble des nombres rationnels.
• Décidabilité du problème de Skolem simultané : En tant qu'application directe du lemme ci-dessus, l'article prouve que le problème de Skolem simultané (déterminer si deux SRL premières entre elles partagent un zéro entier commun) est décidable, là encore en supposant la conjecture de Schanuel p-adique. Cela est réalisé en construisant une nouvelle SRL $w_n = v_n^2 + p u_n^2$ et en analysant ses zéros p-adiques.
• Implémentation : Les auteurs ont implémenté l'algorithme dans l'outil « Skolem » (intégré à SageMath). L'outil gère les cas où le polynôme caractéristique se scinde dans $\mathbb{Z}_p$.

4. Résultats expérimentaux
Les auteurs rendent compte d'expériences utilisant des SRL générées aléatoirement d'ordres 2 à 7.

• Algorithme Hensel uniquement : Une version simplifiée de l'algorithme, supposant que tous les zéros sont simples (multiplicité 1), a résolu avec succès près de 100 % des instances jusqu'à l'ordre 4 et environ 50 % de l'ordre 5 dans un délai d'attente de 60 secondes.
• Algorithme complet : L'algorithme complet, qui inclut l'étape d'énumération rationnelle, a montré des taux de réussite similaires mais avec un temps d'exécution accru (1,3 à 1,5 fois plus lent que la version simplifiée pour les ordres 2–4).
• Observations : Dans l'ensemble de données testé, aucune SRL avec un zéro de multiplicité supérieure à 1 n'a été trouvée, suggérant que de tels cas sont rares en pratique. L'outil identifie efficacement les zéros entiers et rationnels en faisant correspondre les développements p-adiques à des approximations rationnelles.

5. Importance et limites
L'article affirme que, bien que les algorithmes proposés ne résolvent pas le problème général de Skolem (car ils ne peuvent pas toujours distinguer entre les zéros p-adiques rationnels et irrationnels, ni garantir qu'un zéro p-adique corresponde à un zéro entier), ils fournissent un outil pratique puissant.

• Utilité pratique : L'approche p-adique sert d'heuristique efficace pour trouver des zéros entiers de SRL.
• Avancement théorique : Ce travail établit une décidabilité conditionnelle pour le problème de Skolem simultané, une étape significative dans le paysage plus large de la décidabilité des SRL.
• Correction vs Terminaison : Les auteurs soulignent que la sortie de l'algorithme est correcte sans condition chaque fois qu'il termine. La conjecture de Schanuel p-adique est requise uniquement pour garantir la terminaison (en s'assurant que la recherche rationnelle capture tous les zéros multiples), et non pour la correction des zéros identifiés.

L'article conclut que la perspective p-adique offre une voie viable pour l'analyse des zéros des SRL, comblant le fossé entre les preuves théoriques inefficaces et les méthodes computationnelles efficaces sous des hypothèses standards de théorie des nombres.