Hilbert's 10th problem, in modern language is:
Find an algorithm that will, given a poly over Z in many variables, determine if it has a solution in Z.
This problem was proven undecidable through the work of Davis, Putnam, Robinson and then
Matiyasevich supplied the last crucial part of the proof.
Let H10(d,n) be the problem with degree d and n variables.
I had assumed that somewhere on the web would be a grid where the dth row, nth col has
U if H10(d,n) is undecidable
D if H10(d,n) is decidable
? if the status of H10(d,n) was unknown.
I found no grid. I then collected up all the results I could find here
This lead to the (non-math) question: Why is there no grid out there? Here are my speculations.
1) Logicians worked on proving particular (d,n) are undecidable. They sought solutions in N. By contrast number theorists worked on proving particular (d,n) decidable. They sought solutions in Z.. Hence a grid would need to reconcile these two related problems.
2) Logicians and number theorists didn't talk to each other. Websites and books on Hilbert's Tenth problem do not mention any solvable cases of it.
3) There is a real dearth of positive results, so a grid would not be that interesting. Note that we do not even know if the following is decidable: given k in Z does there exists x,y,z in Z such that
x^3 +y^3+ z^3 = k. I blogged about that here
4) For an undecidable result for (d,n) if you make n small then all of the results make d very large.
For example
n=9, d= 1.6 x 10^{45} is undecidable. The status of n=9, d=1.6 x 10^{45} -1 is unknown.
Hence the grid would be hard to draw.
Frankly I don't really want a grid. I really want a sense of what open problems might be solved. I think progress has gone in other directions- H10 over other domains. Oh well, I want to know about
n=9 and d=1.6 x 10^{45}-1. (parenthesis ambiguous but either way would be an advance.)
If a question is undecidable it just mean the QUESTION is wrong, question the question.
ReplyDeleteHere's a nice overview of related questions http://www-math.mit.edu/~poonen/papers/h10_notices.pdf
ReplyDeleteI wonder if you are talking about the right notion of "degree" of a multivariate polynomial (see wikipedia). In your write-up Def 1.4 you say that the degree of (z_1w + z_2)^(2^k) is 2^k but in fact it is 2^(k+1) as the highest term is z_1^(2^k)w^(2^k) which has degree 2^k + 2^k. It would be easy to reduce the maximum degree of a single variable by introducing additional variables and equations, say replace x^8 by x' and x' = a^2, a = b^2, b = x^2. Several equations (e_i = f_i)_(i<n) can be put into one equation (sum_(i<n) (e_i-f_i)^2)=0. All of this is of course well-known.
ReplyDeleteBill, in connection with your writeup, Lagarias works out explicitly that H10(2,2) is solvable with a relatively simple exponential time algorithm. See https://arxiv.org/abs/math/0611209
ReplyDeleteHere https://mathoverflow.net/questions/207482/algorithmic-un-solvability-of-diophantine-equations-of-given-degree-with-given it is claimed that the case of cubic equations in 2 variables is decidable
ReplyDelete