# Why doesn't Buchberger's algorithm solve Hilbert's tenth problem?

I've been reading a bit about Buchberger's algorithm and Groebner bases. I'm not really trying to understand the math behind it at this point, just trying to get an idea of how the method could be used to solve systems of polynomial equations. From what I've seen on the Web, it looks to me like the method could be used to find all integer solutions of a system of Diophantine equations. There's clearly something I don't understand, since I know Hilbert's tenth problem is unsolvable.

Here's what I'm thinking. Given a system of polynomials with integer coefficients, the method produces a "triangular" system of polynomials with integer coefficients with the same zero set, and in which each polynomial has one fewer unknown than the preceding one, as in Gaussian elimination.

Say the last polynomial is $p(z) =a_nz^n+a_{n-1}z^{n-1}+\dots+a_0$ By comparing $|a_nz^n|$ to $\sum_{k=0}^{n-1}|a_kz^k|$ we can find $N$ such that $p(z)=0\implies |z|<N.$ Then we can can systematically test every integer in the range $[-N, N]$ and substitute each $0$ of $p$ into the next equation, arriving at a univariate polynomial, and percolate up until we have found all solutions.

The only way out that I can think of is that the system has a solution but no Groebner basis exists, but nothing I've read so far indicates that this is a possibility. On the other hand, perhaps there's some part of the description of Groebner bases that I have understood. Or, perhaps I'm just being stupid.

Which is it?

• I don't know much about Buchberger's algorithm but I don't think it actually produces a "triangular" system as you describe. For instance, if you started with just a single polynomial, wouldn't the algorithm do nothing? – Eric Wofsey Jul 29 '18 at 23:24
• @EricWofsey I guess that's the part of the explanation that I didn't understand. I'll have to go over those Web pages again and look for that. – saulspatz Jul 30 '18 at 0:21

The analysis you did to decide a polynomial of a single variable, wouldn't apply to one in several variables. For example, $y-x=0$ has arbitrarily large integer solutions.