# 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

## 1 Answer

The impossibility of deciding the solvability of Diophantine equations can be proven by exhibiting a single equation.

The Groebner basis of a principal ideal is any one of its generators.

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.

• That makes sense, but why do all those example show triangular systems, then? It that just something that happens sometimes? Also, is it true than that there are systems with solutions that Groebner bases won't help solve? Thanks for your help. – saulspatz Jul 30 '18 at 0:29
• @saulspatz Gauss elimination is Buchberger's for linear equations. Do you always get triangular systems by doing Gauss? A trapezoid is the most that you can hope for, for linear systems. – user580373 Jul 30 '18 at 0:31
• Okay, I understand. Thanks, again. – saulspatz Jul 30 '18 at 0:36
• @saulspatz See how confusing something, that although absolutely trivial, and even containing ideas that you are supposed to know, but that is slightly out of your horizon of understanding can be? Take that into account, when you see students asking trivial questions that they don't have any idea of how to even start. – user580373 Jul 30 '18 at 0:42