## Monday, May 04, 2020

### Why is there no (d,n) grid for Hilbert's Tenth Problem?

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