4
$\begingroup$

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.

1 Answers 1

5

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.

  • 0
    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.2012-11-20