Buchberger’s Algorithm – Why Doesn’t Buchberger’s Algorithm Solve Hilbert’s Tenth Problem?

diophantine equationsgroebner-basis

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?

Best 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.

Related Solutions

[Math] Solving a polynomial system using Groebner basis computations.

Usually, if you want to solve the system, you use something closer to the lexicographical ordering, which gives triangular Groebner bases:

i1 : T = ZZ[f,g,h, MonomialOrder => Lex]

o1 = T

o1 : PolynomialRing

After this, the rest is just the same as what you did:

i2 : Woot = gb ideal(f^2*g + g^2*h + 2*h^2, f + g + h, f^3*g^2*h) 

o2 = GroebnerBasis[status: done; S-pairs encountered up to degree 10]

o2 : GroebnerBasis

i3 : ideal gens Woot

              8      7      6      5      5     6     5     7       6       5     7     6     5    2 3       6       5     7  
o3 = ideal (4h  + 24h  + 48h  + 32h , 8g*h  + 4h  - 8h , g*h  + 4g*h  + 4g*h  - 2h  - 8h  - 8h , 8g h  - 3g*h  + 2g*h  - 4h  -
     -------------------------------------------------------------------------------------------------------------------------
        6      5   2 4     2 3      6       5     6     5   3     2       2     2
     10h  - 28h , g h  + 2g h  + g*h  + 4g*h  - 2h  - 8h , g  + 3g h + g*h  + 2h , f + g + h)

o3 : Ideal of T

Incidentally, the order in which you order the variables is quite important (but I think no one knows how to pick it, so you have to try a bit...) For example, if I change the order in this example, I get a considerably simpler triangular system:

i12 : T = ZZ[g,h,f, MonomialOrder => Lex]

o12 = T

o12 : PolynomialRing

i13 : ideal gens gb ideal(f^2*g + g^2*h + 2*h^2, f + g + h, f^3*g^2*h) 

               8      5     7     7       6    8    2 3      5    6   2 5      6       5     7   3     2      2    3
o13 = ideal (4f , 4h*f  + 4f , h*f  + 2h*f  + f , 2h f  - h*f  - f , h f  - h*f  + 2h*f  + 2f , h  + 2h f + 2h  - f , g + h +
      ------------------------------------------------------------------------------------------------------------------------
      f)

o13 : Ideal of T

One can solve it almost mentally now :)

Gröbner bases method to solve system of polynomial equations

Groebner bases are defined with respect to some ordering on the monomials of the ring. To compute a Groebner basis with respect to a fixed ordering (say, lexicographical), a computer algebra package such as Magma will first compute it with respect to an 'easier' basis, normally grevlex or weighted grevlex using some algorithm (e.g., Buchberger or Faugère) and then transform that into a Groebner basis with respect to your chosen basis (normally using something called a Groebner walk).

If you want to solve your polynomial equations then any Groebner basis will do. However, you might want to use several different ones. From practical experience using these things, the grevlex ordering might offer a short basis, but it will not be a basis for the radical of the ideal, just of the ideal itself. For solving the equations, you would like the radical of the ideal. This is possible, but hard. The poor man's version is to just remove all of the powers from the defining polynomials of the ideal. Now, switching to a different ordering yields a new set of defining polynomials, which might once again have powers. Remove these powers, then switch to another ordering, remove any powers you might find, and so on until your set of polynomials stabilizes with respect to all orderings you might want.

Since you aren't generating the genuine radical of the ideal, you might end up with possible solutions that aren't genuine, but this poor man's version of taking the radical is computationally a lot easier, in the sense that it's possible this year, and you might still get enough to work with.

Best Answer

Related Solutions

[Math] Solving a polynomial system using Groebner basis computations.

Gröbner bases method to solve system of polynomial equations

Related Question