Polynomgleichungen über $\mathbb {Z}$ mathend000#

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

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

so daß M = mathend000#

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

Beispiele:

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

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