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.

Skolem-Problem

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

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

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

Beispiele:

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

Formulierung des Problems

Das Skolem-Problem lautet:

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

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

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

Erläuterungen

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 $A$ , der für eine lineare Rekursionsfolge $u$ die Entscheidungsfunktion

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

berechnet, das heißt

A (u) = f (u)

.

Bekannte Resultate

Satz von Skolem-Mahler-Lech und seine Varianten

Der Satz von Skolem-Mahler-Lech sagt

Die Menge der Nullstellen ${n \in ℕ : 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 $λ_{i} / λ_{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]

Weitere Resultate

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

Einzelnachweise

1 2 3 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.
1 2 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.
↑ 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.
↑ 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.
↑ 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.

[Li-1] 1 2 3 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.

[LOW-2] 1 2 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.

[1]

[2]

[3]

[4]

[5]

Skolem-Problem

Formulierung des Problems

Erläuterungen

Bekannte Resultate

Satz von Skolem-Mahler-Lech und seine Varianten

Weitere Resultate

Verwandte Probleme

Einzelnachweise