Skolem-Problem

Das Skolem-Problem ist eine Problemstellung der Mathematik und der theoretischen Informatik, die fragt, ob eine gegebene ganzzahlige lineare Rekursionsfolge eine Nullstelle besitzt. Das zugehörige Entscheidungsproblem, ob ein Algorithmus existiert, der diese Frage für alle linearen Rekursionsfolgen entscheiden kann, ist offen.

Das Problem ist nach Thoralf Skolem benannt, der 1934 erste Resultate über die Struktur der Nullstellen solcher Folgen erzielte. Der Satz von Skolem-Mahler-Lech macht eine Aussage dazu.

Eine Folge ${\displaystyle (u_{n})_{n\in \mathbb {N} _{0}}}$ mit ${\displaystyle u_{n}\in \mathbb {Z} }$ heißt lineare Rekursionsfolge (LRF), wenn sie für alle ${\displaystyle n\in \mathbb {N} _{0}}$ eine Rekursion der Form

${\displaystyle u_{n+k}=a_{1}u_{n+k-1}+a_{2}u_{n+k-2}+\dots +a_{k}u_{n}}$

mit festen Koeffizienten ${\displaystyle a_{1},\dots ,a_{k}\in \mathbb {Z} }$ erfüllt.^[1] Man nennt ${\displaystyle k}$ die Ordnung der Folge.

Beispiele:

• die Fibonacci-Folge erfüllt ${\displaystyle u_{n+2}=u_{n+1}+u_{n}}$ und hat Ordnung ${\displaystyle 2}$.

Das Skolem-Problem lautet:

Gegeben eine lineare Rekursionsfolge ${\displaystyle (u_{n})_{n\in \mathbb {N} _{0}}}$, gibt es ein ${\displaystyle n\geq 0}$, so dass ${\displaystyle u_{n}=0}$?

Das zugehörige Entscheidungsproblem ist offen:^[1]

Gibt es einen Algorithmus, der für jede beliebigen lineare Rekursionsfolge ${\displaystyle (u_{n})_{n\in \mathbb {N} _{0}}}$ das Skolem-Problem löst?

• Der Algorithmus, der schaut, ob irgendwann ein Folgenglied der unendlichen Rekursionsfolge gleich Null ist, ist kein Entscheidungsverfahren, da er im Fall, dass keine Nullstelle existiert, nie terminiert.
• Gesucht ist ein Algorithmus ${\displaystyle A}$, der für eine lineare Rekursionsfolge ${\displaystyle u}$ die Entscheidungsfunktion

${\displaystyle f(u)={\begin{cases}1,&\exists n\geq 0:\;u_{n}=0,\\0,&\forall n\geq 0:\;u_{n}\neq 0.\end{cases}}}$

berechnet, das heißt ${\displaystyle A(u)=f(u)}$.

Der Satz von Skolem-Mahler-Lech sagt

Die Menge der Nullstellen ${\displaystyle \{n\in \mathbb {N} :u_{n}=0\}}$ einer linearen Rekursionsfolge ist die Vereinigung einer endlichen Menge und einer endlichen Anzahl von arithmetischen Folgen.

Er liefert jedoch keinen Algorithmus zur Entscheidung, ob überhaupt Nullstellen existieren.^[1]

Eine stärkere Variante gilt für nicht-degenerierte Rekursionsfolgen. Eine lineare Rekursionsfolge heißt nicht-degeneriert, wenn der Quotient ${\displaystyle \lambda _{i}/\lambda _{j}}$ zweier verschiedener Nullstellen ihres charakteristischen Polynoms keine Einheitswurzel ist.

Eine nicht-degenerierte lineare Rekursionsfolge hat nur endlich viele Nullstellen.

Es ist jedoch offen, wie man die Nullstellenmenge allgemein berechnet.^[2]

Eine lineare Rekursionsfolge heißt einfach, wenn ihr charakteristisches Polynoms nur paarweise verschiedene Nullstellen besitzt. Für einfache LRF wurde 2022 ein Verfahren gefunden, welche das Skolem-Problem entscheidet, aber unter der Bedingung, dass zwei offene Vermutungen aus der analytische Zahlentheorie wahr sind (die p-adische Schanuel-Vermutung und das exponential local-global principle).^[2][3]

• 1984/1985 wurde gezeigt, dass das Problem für Rekursionen bis zur Ordnung ${\displaystyle 4}$ entscheidbar ist.^[4][5] Das ist der letzte Stand.
• Es ist bekannt, dass das Problem NP-schwer ist.

Das Positivitätsproblem fragt, ob alle Folgenglieder nichtnegativ sind:

Gegeben eine lineare Rekursionsfolge ${\displaystyle (u_{n})_{n\in \mathbb {N} _{0}}}$, gilt dann ${\displaystyle u_{n}\geq 0}$ für alle ${\displaystyle n\geq 0}$?

Das Entscheidungsproblem dazu ist auch offen:

Gibt es einen Algorithmus, der für jede lineare Rekursionsfolge ${\displaystyle (u_{n})_{n\in \mathbb {N} _{0}}}$ bestimmt, ob ${\displaystyle u_{n}\geq 0}$ für alle ${\displaystyle n\geq 0}$ gilt?

1. ↑ ^{a b c} Richard Lipton; Florian Luca; Joris Nieuwveld; Joël Ouaknine; David Purser; James Worrell: On the Skolem Problem and the Skolem Conjecture. In: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022). Association for Computing Machinery, New York, NY 2022, doi:10.1145/3531130.3533328. 
2. ↑ ^{a b} F. Luca; J. Ouaknine; J. Worrell: Universal Skolem Sets. In: Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021). 2021, S. 1–6, doi:10.1109/LICS52264.2021.9470513. 
3. ↑ Florian Luca, James Maynard, Armand Noubissie, Joël Ouaknine, James Worrell: Skolem Meets Bateman–Horn. In: Forum of Mathematics, Sigma. Band 12, e53, 2024, doi:10.1017/fms.2024.46. 
4. ↑ N. K. Vereshchagin: Occurrence of zero in a linear recursive sequence. In: Mathematical Notes of the Academy of Sciences of the USSR. Band 38, Nr. 2, 1985, S. 609–615, doi:10.1007/BF01156238. 
5. ↑ Tijdeman, R., Mignotte, M., and Shorey, T.N. "The distance between terms of an algebraic recurrence sequence.." Journal für die reine und angewandte Mathematik 349 (1984): 63-76.