To answer this question rigorously, one needs to give some open equations $P=0$ with $h(P)$ equal to some $N$ and solve all other equations with $h(P)\leq N$. Without this, we cannot guarantee that $N$ is indeed the smallest. Because the number of equations with $h(P)=N$ grows exponentially with $N$, one needs to write the whole book to solve them all.

This is exactly what I did! My newly published book

Bogdan Grechuk. Polynomial Diophantine Equations. A Systematic Approach. Springer Cham https://doi.org/10.1007/978-3-031-62949-5

solves all Diophantine equations $P=0$ in the order of $h(P)$, except that some are left as exercises. All the exercises are solved by my Ph.D. student Ashleigh Wilcox https://arxiv.org/abs/2404.08719 The book is 784 pages long, and the solutions to exercises took another 482 pages. After this work, we are now ready to answer the listed questions (except the undecidability part) in full.

What size would be the smallest $N$ for which:

• One does not know the integral solutions of $P(x)=0$

Answer: Some equations, like $y^2+z^2=x^3\pm 1$ of size $h=17$, may be considered open of solved depending on in which form we accept the answer. The smallest equations that are open without any doubts are the equations $$ 2x^2-xyz-y^2-1=0 $$ $$ 2x^2-xyz+y^2+1=0 $$ and $$ y^2+x^2y+z^2x+1=0 $$ of size $h=21$.

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

Answer: There are $8$ equations of size $h=27$ in this category. Examples are $y^3=2x^3+x+1$ and $y^3=x^4+x\pm 1$. We know there are algorithms for solving such equations, but currently do not know the actual solutions.

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

Answer: The smallest equations for which we do not know how to describe all rational solutions are the equations $$ y^2 - x^2y + z^2 + 1 = 0 $$ $$ y^2+z^2 = x^3+1 $$ and $$ y^2+z^2 = x^3-1 $$ of size $h=17$.

• One knows the integral solutions of P(x)=0 to be undecidable.
• One knows the rational solutions of P(x)=0 to be undecidable.

These questions do not make sense as stated, because only infinite families of equations may be "undecidable", not specific examples. For individual equations, one may instead ask what is the smallest (in $h$) equation for which the existence of integer solutions is independent from ZFC. This is open, and is the Open Question 8.23 in the book.

In addition, one may ask many similar question, e.g. what is the smallest open two-variable equation, the smallest equations for which we do not know whether any integer solutions exists, etc. The smallest open equations in each such category are summarized in the arxiv preprint

Bogdan Grechuk. A systematic approach to Diophantine equations: open problems https://arxiv.org/abs/2404.08518

I plan to keep this arxiv preprint up-to-date, so if you solve any equations from it, please let me know at [email protected]

I would like to conclude this answer with thank to Zidane for the question. It is not every day when a Mathoverflow question inspires a book to answer it!

To answer this question rigorously, one needs to give some open equations $P=0$ with $h(P)$ equal to some $N$ and solve all other equations with $h(P)\leq N$. Without this, we cannot guarantee that $N$ is indeed the smallest. Because the number of equations with $h(P)=N$ grows exponentially with $N$, one needs to write a whole book to solve them all.

This is exactly what I did! My newly published book

Bogdan Grechuk. Polynomial Diophantine Equations. A Systematic Approach. Springer Cham https://doi.org/10.1007/978-3-031-62949-5

solves all Diophantine equations $P=0$ in the order of $h(P)$, except that some are left as exercises. All the exercises are solved by my Ph.D. student Ashleigh Wilcox https://arxiv.org/abs/2404.08719 The book is 784 pages long, and the solutions to exercises took another 482 pages. After this work, we are now ready to answer the listed questions (except the undecidability part) in full.

What size would be the smallest $N$ for which:

• One does not know the integral solutions of $P(x)=0$

Answer: Some equations, like $y^2+z^2=x^3\pm 1$ of size $h=17$, may be considered open or solved depending on in which form we accept the answer. The smallest equations that are open without any doubts are the equations $$ 2x^2-xyz-y^2-1=0 $$ $$ 2x^2-xyz+y^2+1=0 $$ and $$ y^2+x^2y+z^2x+1=0 $$ of size $h=21$.

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

Answer: There are $8$ equations of size $h=27$ in this category. Examples are $y^3=2x^3+x+1$ and $y^3=x^4+x\pm 1$. We know there are algorithms for solving such equations, but currently do not know the actual solutions.

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

Answer: The smallest equations for which we do not know how to describe all rational solutions are the equations $$ y^2 - x^2y + z^2 + 1 = 0 $$ $$ y^2+z^2 = x^3+1 $$ and $$ y^2+z^2 = x^3-1 $$ of size $h=17$.

• One knows the integral solutions of P(x)=0 to be undecidable.
• One knows the rational solutions of P(x)=0 to be undecidable.

These questions do not make sense as stated, because only infinite families of equations may be "undecidable", not specific examples. For individual equations, one may instead ask what is the smallest (in $h$) equation for which the existence of integer solutions is independent from ZFC. This is open, and is the Open Question 8.23 in the book.

In addition, one may ask many similar questions, e.g. what is the smallest open two-variable equation, the smallest equations for which we do not know whether any integer solutions exist, etc. The smallest open equations in each such category are summarized in the arxiv preprint

Bogdan Grechuk. A systematic approach to Diophantine equations: open problems https://arxiv.org/abs/2404.08518

I plan to keep this arxiv preprint up-to-date, so if you solve any equations from it, please let me know at [email protected]

I would like to conclude this answer with thanks to Zidane for the question. It is not every day when a Mathoverflow question inspires a book to answer it!