On the Diophantine problem related to power circuits

Titel: Zum diophantischen Problem im Zusammenhang mit Leistungsschaltungen (Power Circuits)

Autor: Alexander Rybalov
Institution: Sobolev-Institut für Mathematik, Omsk, Russland

---

1. Problemstellung und Hintergrund

Das Paper adressiert ein offenes Problem aus der theoretischen Informatik und mathematischen Logik, das von Myasnikov, Ushakov und Won in ihrer Arbeit zu Leistungsschaltungen (Power Circuits) aufgeworfen wurde.

• Hintergrund: Leistungsschaltungen sind Berechnungsstrukturen, die Addition und die Operation $(x, y) \mapsto x \cdot 2^y$ auf ganzen Zahlen unterstützen. Sie wurden genutzt, um einen polynomialen Algorithmus für das Wortproblem in der Baumslag-Gruppe $G(1,2)$ zu konstruieren, die eine nicht-elementare Dehn-Funktion besitzt.
• Die offene Frage: Myasnikov et al. stellten die Frage nach der Entscheidbarkeit des diophantischen Problems über der Struktur $\mathcal{N} = \langle \mathbb{N}_{>0}; +, x \cdot 2^y, \leq, 1 \rangle$.
• Kontext:
  • Das klassische diophantische Problem über $\langle \mathbb{N}; +, \cdot, 1 \rangle$ (Hilberts zehntes Problem) ist nach dem Satz von Matiyasevich unentscheidbar.
  • Im Gegensatz dazu ist die erste Ordnungstheorie von $\langle \mathbb{N}; +, x \mapsto 2^x, 1 \rangle$ (Addition und Exponentiation) nach Semenov entscheidbar.
  • Die Struktur $\mathcal{N}$ liegt zwischen diesen beiden Extremen, da sie Addition und eine "gemischte" Operation ($x \cdot 2^y$) enthält, aber keine allgemeine Multiplikation oder reine Exponentiation als Grundoperation hat.

Das Ziel des Papers ist der Beweis, dass das diophantische Problem über $\mathcal{N}$ unentscheidbar ist. Als direkte Konsequenz wird damit auch die Frage beantwortet, ob $\mathcal{N}$ eine automatische Struktur ist (die Antwort ist negativ).

---

2. Methodik und Beweisstrategie

Der Beweis folgt einer Reduktionskette, um die Unentscheidbarkeit von $\mathcal{N}$ zu zeigen. Die zentrale Idee besteht darin, die Multiplikation auf der Menge der natürlichen Zahlen größer als 1 ($\mathbb{N}_{>1}$) innerhalb der Struktur $\mathcal{N}$ diophantisch zu definieren.

Schritt 1: Reduktion auf $\mathbb{N}_{>k}$

Zunächst wird gezeigt, dass das diophantische Problem über $\mathbb{N}$ (das bekanntlich unentscheidbar ist) auf das Problem über $\mathbb{N}_{>k}$ (natürliche Zahlen größer als $k$) reduzierbar ist.

• Lemma 2.1: Für jedes $k \in \mathbb{N}$ gibt es eine Cook/Turing-Reduktion von $DP(\mathbb{N})$ zu $DP(\mathbb{N}_{>k})$.
• Methode: Durch Aufzählung aller Teilmengen von Variablen und Zuweisung von Werten aus $\{0, \dots, k\}$ wird ein System über $\mathbb{N}$ in ein endliches System von Systemen über $\mathbb{N}_{>k}$ umgewandelt.
• Folge (Korollar 2.2): $DP(\mathbb{N}_{>k})$ ist für jedes $k$ unentscheidbar.

Schritt 2: Diophantische Definierbarkeit in $\mathcal{N}$

Um $DP(\mathbb{N}_{>1})$ auf $DP(\mathcal{N})$ zu reduzieren, muss die Multiplikation $xy$für$x, y > 1$ in $\mathcal{N}$ definierbar sein. Der Autor definiert schrittweise notwendige Relationen und Funktionen:

1. Teilbarkeit ($x | y$):

   • Es wird bewiesen, dass $x | y \iff 2^x - 1 | 2^y - 1$.
   • Da die Struktur $\mathcal{N}$ die Operation $x \cdot 2^y$ erlaubt, kann $2^x - 1$ durch Umformung ($2^y + z = z \cdot 2^x + 1$) ausgedrückt werden. Somit ist die Teilbarkeitsrelation diophantisch definierbar.
   • Hinweis: Der Autor stellt fest, dass die Definierbarkeit der Teilbarkeit allein nicht ausreicht, da das diophantische Problem über $\langle \mathbb{N}; +, | \rangle$ bekanntermaßen entscheidbar ist (Lipshitz).

2. Strikte Ordnung ($x < y$):

   • Einfach definierbar durch $\exists z (x + z = y)$.

3. Ganzzahliger Binärischer Logarithmus ($\lfloor \log_2 x \rfloor$):

   • Definierbar durch die Bedingung $2^y \leq x < 2^{y+1}$.

4. Quadratfunktion ($x^2$):

   • Dies ist der technisch anspruchsvollste Teil. Der Autor konstruiert eine Menge $S(x) = \{kx(x+1) : k \in \mathbb{N}\}$, die durch Teilbarkeitsbedingungen definierbar ist.
   • Durch Kombination mit dem Logarithmus und spezifischen Kongruenzbedingungen ($x+2 | y+2x$ und $x+3 | y+3x$) wird sichergestellt, dass nur $x^2$ (und keine anderen Werte wie $2x^2+x$) die Kriterien erfüllt.

5. Multiplikation ($xy$):

   • Sobald $x^2$ definierbar ist, kann die Multiplikation über die algebraische Identität $2xy = (x+y)^2 - x^2 - y^2$ ausgedrückt werden.
   • Da Addition und Quadrieren in $\mathcal{N}$ definierbar sind, ist auch die Multiplikation definierbar.

Schritt 3: Der finale Reduktionsschritt

• Theorem 2.9: Da $DP(\mathbb{N}_{>1})$ unentscheidbar ist (nach Schritt 1) und die Multiplikation in $\mathcal{N}$ definierbar ist (nach Schritt 2), kann jedes diophantische System über $\mathbb{N}_{>1}$ in ein äquivalentes System über $\mathcal{N}$ übersetzt werden.
• Folge: Das diophantische Problem über $\mathcal{N}$ ist unentscheidbar.

---

3. Wichtige Beiträge und Ergebnisse

1. Unentscheidbarkeit bewiesen: Das Paper liefert den ersten Beweis, dass das diophantische Problem über der Struktur $\langle \mathbb{N}_{>0}; +, x \cdot 2^y, \leq, 1 \rangle$ unentscheidbar ist.
2. Lösung einer offenen Frage: Es beantwortet Problem 10.3 aus der Arbeit von Myasnikov, Ushakov und Won negativ.
3. Konstruktion der Multiplikation: Ein wesentlicher methodischer Beitrag ist der Nachweis, dass die Multiplikation auf $\mathbb{N}_{>1}$ allein durch Addition, die Operation $x \cdot 2^y$ und die Ordnung $\leq$ diophantisch definiert werden kann. Dies ist überraschend, da die Struktur keine direkte Multiplikation oder Exponentiation als Grundoperation enthält.
4. Automatische Strukturen: Als Korollar (2.10) wird gezeigt, dass $\mathcal{N}$ keine automatische Struktur ist. Da alle automatischen Strukturen eine entscheidbare erste Ordnungstheorie besitzen, folgt aus der Unentscheidbarkeit des diophantischen Problems (ein Teil der ersten Ordnungstheorie), dass $\mathcal{N}$ nicht automatisch sein kann.

---

4. Signifikanz und Implikationen

• Theoretische Informatik: Die Ergebnisse schärfen das Verständnis der Grenzen von Berechenbarkeit in Strukturen, die für die Analyse von Gruppen (wie der Baumslag-Gruppe) und deren Wortproblemen relevant sind. Sie zeigen, dass die Hinzunahme der Operation $x \cdot 2^y$ zu einer Struktur, die bereits Addition enthält, ausreicht, um die volle Komplexität der diophantischen Gleichungen (und damit die Unentscheidbarkeit) wiederherzustellen.
• Logik: Das Ergebnis grenzt die Klasse der Strukturen mit entscheidbaren diophantischen Problemen weiter ein. Es zeigt, dass selbst "schwächere" Operationen als die volle Multiplikation (wie $x \cdot 2^y$), wenn sie in Kombination mit Addition und Ordnung auftreten, zur Unentscheidbarkeit führen können.
• Automatische Strukturen: Die negative Antwort auf die Frage nach der Automatik von $\mathcal{N}$ ist wichtig für die Klassifizierung von Strukturen in der Modelltheorie und deren algorithmischen Eigenschaften.

Zusammenfassend demonstriert Rybalov, dass die kombinatorische Komplexität von Leistungsschaltungen tief genug ist, um die Unentscheidbarkeit des diophantischen Problems zu kodieren, was fundamentale Grenzen für algorithmische Lösungen in diesem Bereich aufzeigt.