\begin{slide}{Polynomgleichungen über $\ZZ$}

Def: eine Menge $M\subseteq \ZZ^k$ heißt
\emph{diophantisch}, 

wenn ein Polynom $P$
mit Koeffizienten in $\ZZ$ existiert, 

so daß $M =$

\(
\{ (x_1,\ldots,x_i) \mid \exists x_{i+1}\in \ZZ,\ldots,x_k\in \ZZ : P( x_1,\ldots,x_k) = 0 \}
\)

Beispiele:
\begin{itemize}\itemsep 0pt
\item Menge der Quadratzahlen (leicht)
\item Menge der natürlichen Zahlen (schwer)
\item Menge der Zweierpotenzen (sehr schwer)
\item Menge der Primzahlen?
\end{itemize}

Abschluß-Eigenschaften? (Durchschnitt, Vereinigung, \dots)

\end{slide}

\begin{slide}{Diophantische Mengen}


Satz (Davis, Matiyasevich, Putnam, Robinson; $\approx$ 1970)

\begin{center}
 $M$ diophantisch $\iff$ $M$ ist rekursiv aufzählbar
\end{center}
\url{http://logic.pdmi.ras.ru/~yumat/H10Pbook/}

\bigskip

positive Werte dieses Polynoms $=$ Menge der Primzahlen

\begin{small}
$
(k+2)
(1 – (wz+h+j–q)^2 – ((gk+2g+k+1)(h+j)+h–z)^2 – (2n+p+q+z–e)^2 – 
(16(k+1)^3(k+2)(n+1)^2+1–f^2)^2 – (e^3(e+2)(a+1)^2+1–o^2)^2 – 
((a^2–1)y^2+1–x^2)^2 – (16r^2y^4(a^2–1)+1–u^2)^2 –
 (((a+u^2(u^2–a))^2 –1)(n+4dy)^2 + 1 – (x+cu)^2)^2 
– (n+l+v–y)^2 – ((a^2–1)l^2+1–m^2)^2 – (ai+k+1–l–i)^2 – 
(p+l(a–n–1)+b(2an+2a–n^2–2n–2)–m)^2 – (q+y(a–p–1)+s(2ap+2a–p^2–2p–2)–x)^2 
– (z+pl(a–p)+t(2ap–p^2–1)–pm)^2)
$
\end{small}

(challenge: \dots find some)
\url{http://primes.utm.edu/glossary/xpage/MatijasevicPoly.html}


\end{slide}
