15
$\begingroup$

If $P=\sum_{\bf i} a_{\bf i}x^{\bf i}\in {\mathbb Z}[x_1,\dots,x_d]$, let $|P|=\sum_{\bf i}|a_{\bf i}|x^{\bf i}$ and $h(P)=|P|(2,\dots,2)$, so that there is only a finite number of $P$ with $h(P)\leq N$ when $d$ varies. What size would be the smallest $N$ for which:

$\bullet$ One does not know the integral solutions of $P(x)=0$.

$\bullet$ There is a deterministic algorithm to find the integral solutions of $P(x)=0$, but the involved bounds are too big.

$\bullet$ One knows the integral solutions of $P(x)=0$ but not its rational solutions.

$\bullet$ One knows the integral solutions of $P(x)=0$ to be undecidable.

$\bullet$ One knows the rational solutions of $P(x)=0$ to be undecidable.

$\endgroup$
  • $\begingroup$ Not a duplicate, but closely related: mathoverflow.net/questions/54857/… $\endgroup$ – Wojowu Dec 2 '18 at 17:00
  • 2
    $\begingroup$ Regarding fourth and fifth point: if you mean algorithmically undecidable, there is none - the solution set is trivially decidable for any integer polynomial. If you mean undecidable in the sense of it being unprovable what the solutions are, the answer depends on background theory (Peano arithmetic, ZFC, etc.) There isn't a single polynomial which could work for all theories. $\endgroup$ – Wojowu Dec 2 '18 at 17:04
  • 12
    $\begingroup$ To start the bidding: according to Poonen at www-math.mit.edu/~poonen/papers/h10_notices.pdf , it is not known whether there are integer solutions to $x^3+y^3+z^3-33 = 0$ (so $h(P) = 57$ in this case). $\endgroup$ – Terry Tao Dec 2 '18 at 17:51
  • 4
    $\begingroup$ I believe this paper of Hilliker and Strauss jstor.org/stable/1999638?seq=1#metadata_info_tab_contents implies that the first question is decidable in two variables, so one needs at least three variables. I believe all quadratic Diophantine equations are known to be decidable also, so this makes Poonen's example likely to be almost the best possible. $\endgroup$ – Terry Tao Dec 2 '18 at 18:44
  • 1
    $\begingroup$ Given the logic tag, I’d like to advertise $a^5+b^5=c^5+d^5$, a simple equation that would have lower height than the $33$ equation if we used $3/2$ instead of $2$. If writing a number as a sum of fifth powers is unique, then we can use $x^5+y^5$ for a pairing function on the rationals, which would be an advance on Hilbert’s 10th problem over $\mathbf{Q}$. $\endgroup$ – Matt F. Dec 4 '18 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.