Diophantine Sets

Diophantine sets are subsets defined by polynomial equations over integers.
More precisely \displaystyle S = \{ (x_1, x_2, \cdots , x_n) \in \mathbb{Z}| P(x_1, x_2, \cdots , x_n, y_1, y_2, \cdots, y_m)=0\}.
We obtain them basically by projecting integers solutions of some polynomial equations.

Observation 1: Using the statement P=0, Q=0 iff P^2+Q^2=0, we see that there is no difference between one polynomial equation and a system of polynomial equations.

Example: Even numbers are Diophantine: \displaystyle E= \{ x| x=2y\}.
Odd numbers: \displaystyle O =\{x| x=2y+1\}.

Non-negative integers are Diophantine. By Lagrange theorem we have \displaystyle \mathbb{Z}_{\ge 0}= \{n|n=x^2+y^2+z^2+t^2\}. As a result positive integers are given by \displaystyle \mathbb{N}= \{n|n=1+x^2+y^2+z^2+t^2\}. So we see that we can define Diophantine sets just by asking for solutions in positive integers: \displaystyle S = \{ (x_1, x_2, \cdots , x_n) \in \mathbb{Z}| P(x_1, x_2, \cdots , x_n, y_1, y_2, \cdots, y_m)=0, y_i \in \mathbb{N}\}.

Observation 2: Unions and intersections of Diophantine sets are Diophantine. If P(X,Y), Q(X,Z) are defining polynomials of two Diophantine sets, intersections are obtained by considering P(X, Y)^2+ Q(X, Z)^2=0 and unions are obtained by considering P(X,Y) Q(X, Z)=0.

Example: Composite numbers: \displaystyle \{x| x=yz, y,z>1 \}. We can write this as \displaystyle \{x| x=(1+a^2+b^2+c^2+d^2)(1+r^2+s^2+t^2+u^2)\} using the Diophantine description for positive integers.

In general, finding explicit Diophantine description of some subsets of integers and understand various constructions on Diophantine sets like unions, intersections etc helps us to find Diophantine description of many subsets.

Question: What kind of sets are Diophantine?

Problem: Can you describe powers of 2? What about prime numbers?

Non-trivial theorem: All recursively enumerable (that is all sets that can be enumerated by an “algorithm” ) are Diophantine.

Relations like a<b are Diophantine.

Crucial step in the proof of above theorem is to show that the exponential relation \displaystyle \{ (a,b,c)| a=b^c\} is also Diophantine.

Diophantine descriptions of primes!

{\bf{P}} such that

\displaystyle \begin{array}{rcl} &\left(wz + h + j - q \right)^2+ \left((gk + 2g + {\bf P}-1)(h + j) + h - z \right)^2+\\ & \left(16{\bf P}({\bf P}-1)^3(n + 1)^2 + 1 - f^2 \right)^2+ \left(2n + p + q + z - e \right)^2+\\ &\left(e^3(e + 2)(a + 1)^2 + 1 - o^2 \right)^2+ \left(a^2 - 1)y^2 + 1 - x^2 \right)^2+\\ &\left( 16r^2y^4(a^2 - 1) + 1 - u^2 \right)^2+ \left( n + \ell + v - y \right)^2+\\ &\left((a^2 - 1)\ell^2 + 1 - m^2 \right)^2+\left( ai + {\bf P}-1 - \ell - i \right)^2+\\ &\left(((a + u^2(u^2 - a))^2 - 1)(n + 4dy)^2 + 1 - (x + cu)^2 \right)^2+\\ &\left( p + \ell(a - n - 1) + b(2an + 2a - n^2 - 2n - 2) - m \right)^2+\\ &\left( q + y(a - p - 1) + s(2ap + 2a - p^2 - 2p - 2) - x \right)^2+ \\ &\left(z + p\ell(a - p) + t(2ap - p^2 - 1) - pm \right)^2=0 \end{array}

has positive integral solutions.

Resources:

    Leave a comment