# Diophantine equations and Groebner bases

I'm trying to teach myself the basics of algebraic geometry and have run into something that I don't understand.

I know that the problem of deciding whether a Diophantine equation $P(\vec{x}) = 0$ has any solutions is undecidable (Hilbert's 10th problem). Since the integers form a ring, $\mathbb{Z}[\vec{x}]$ (the polynomials over $\mathbb{Z}$ with coefficients $\vec{x}$) is also a ring. So the question can be restated as asking whether the variety of $\langle P \rangle$ is empty or not. But $$\mathbf{V}(\langle P \rangle) = \mathbf{V}(G(\langle P \rangle))$$

where $\mathbf{V}(I)$ is the variety of the ideal $I$, and $G(I)$ is a Groebner basis for $I$. So we can check whether $\mathbf{V}(\langle P \rangle)$ is empty by checking whether $G(\langle P \rangle) = G(\langle 1 \rangle)$. But that would give us a decision procedure for solving Diophantine equations.

I'm assuming that I've gone wrong either:

• Assuming that I can compute a Groebner basis for $\langle P \rangle$ (since the integers don't form a field, I don't know whether this is legit)
• Assuming that Groebner bases have the same properties (like being canonical) if they're done over an arbitrary, non-field base ring
• Something else?

As I said, I'm just getting started looking at the whole field, so any pointers as to huge conceptual mistakes I'm making would be hugely appreciated.

Thanks.

Consider the equation $x^2+1=0$. We have the following:

(1) This equation does not have any solutions in $\mathbb{Q}$.

(2) It does have solutions in $\mathbb{C}$ namely $\pm i$.

(3) The ideal $\langle x^2+1 \rangle$ is not $\langle 1 \rangle$.

This shows the general pattern: Given an ideal $I \subseteq \mathbb{Q}[x_1, x_2, \ldots, x_n]$, with generators $\langle f_1, f_2, \ldots, f_r \rangle$, the ideal $I$ is equal to $\langle 1 \rangle$ if and only if there are no complex solutions to $f_1=f_2=\cdots=f_r=0$.

In the case where $I \neq \langle 1 \rangle$, there are complex solutions (and, in fact, these solutions will always live in some finite field extension of $\mathbb{Q}$). The problem which no one knows an algorithm for is to decide whether any of those solutions lie in $\mathbb{Q}$ itself.

• does this mean you can sometimes make use of this idea to solve a diophantine equation that would be difficult otherwise? (just not always) – sperners lemma Nov 19 '12 at 15:51
• Well, you can use Groebner bases to show that there are no complex solutions, and that certainly shows that there are no rational solutions. Less trivially, if there are only finitely many complex solutions, then you can use Groebner bases to find a polynomial $f(z) \in \mathbb{Q}[z]$ whose roots are defined over the same fields as the roots of the original equations, and then you can use the rational root theorem to determine whether $f$ has any rational roots. That's why the first nontrivial diophatine equations are curves. – David E Speyer Nov 19 '12 at 15:55
• Thanks very much. So just to double check I have this right, my basic misunderstanding was that if I have a ring $\mathbb{R}$ and some ideal $I \subseteq \mathbb{R}[\vec{x}] = \langle f_1, ... f_n \rangle$ then $I$ contains all polynomials that share solutions with the $f_i$ over an algebraic closure of $\mathbb{R}$ rather than $\mathbb{R}$ itself? – Matt Lewis Nov 19 '12 at 16:08
• Let's take $\mathbb{R}$ a field, not a ring, to avoid complications. Then yes. – David E Speyer Nov 19 '12 at 19:12
• I was afraid that'd be the answer :) The case I'm really interested in is arithmetic modulo $2^k$, which doesn't form a field. Looks like I have some more reading to do. Thanks again for the great answers. – Matt Lewis Nov 20 '12 at 14:33