Polynomgleichungen über $\mathbb {Z}$

Def: eine Menge M⊆$\mathbb {Z}$^k heißt diophantisch,

wenn ein Polynom P mit Koeffizienten in $\mathbb {Z}$ existiert,

so daß M =

{(x₁,…, x_i) | ∃x_i+1∈$\mathbb {Z}$,…, x_k∈$\mathbb {Z}$ : P(x₁,…, x_k) = 0}

Beispiele:

• Menge der Quadratzahlen (leicht)
• Menge der natürlichen Zahlen (schwer)
• Menge der Zweierpotenzen (sehr schwer)
• Menge der Primzahlen?

Abschluß-Eigenschaften? (Durchschnitt, Vereinigung, ...)