What is the smallest unsolved Diophantine equation? 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:

*

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


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


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


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


*One knows the rational solutions of $P(x)=0$ to be undecidable.
 A: As in my previous answers, I will discuss only the solvability question: does a given equation have any integer solutions or not?
In my previous answers, I discussed the first item in the question: "One does not know the integral solutions of $P(x)=0$." All equations which belong to a well-known family of effectively solvable equations has been ignored. In that project, the current smallest open equation is $y(x^3-y)=z^3+3$ with $H=31$, see a separate Mathoverflow question Can you solve the listed smallest open Diophantine equations? for details.
In this answer, I will address the second item in the question: "There is a deterministic algorithm to find the integral solutions of $P(x)=0$, but the involved bounds are too big".
The current answers to this question are equations
$$
x^3+x^2y-y^3-y+3 = 0
$$
and
$$
y^3 = x^4+x+3
$$
with $H=29$.
The first equation has genus 1, and there is an effective upper bound for all potential integer solutions developed in [1]. The bound, however, is too large, despite some subsequent improvements. There is also an algorithm in [2], which is much faster but, to the best of my knowledge, was never implemented.
For the second equation, there is an effective upper bound for all potential integer solutions for any equation of the form $y^k=f(x)$, $k\geq 2$, under some minor conditions on polynomial $f(x)$, see [3], but the bound is too big. Much more promising is the effective Chabauty--Kim method, which is applicable for equations of genus $g\geq 2$ such that the rank $r$ of the Jacobian is less than the genus. For this equation, the genus $g=3$ and $r\leq 2$, hence the method should work in principle. For hyperelliptic equations, the method is actually implemented in Magma, but this equation is not hyperelliptic. Instead, it belongs to the family of Picard curves. For such equations, the case $r=0$ is resolved in the answer to this Mathoverflow question $y^3 = x^4 + x + 2$, and rational points on rank 0 Picard curves, while the case $r=1$ has been investigated in the recent work [4]. For our equation, however, the best known upper bound for the rank is $2$.
Of course, it is possible that these particular equations can be easily solvable by some elementary methods. If you solve any of them, please let me know in the comment, and I will update the answer with the next-smallest equations.
[1] Alan Baker and John Coates. Integer points on curves of genus 1. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 67, pages 595–602. Cambridge University Press, 1970.
[2] R. Stroeker, B.M.M de Weger, Solving Elliptic Diophantine Equations:
The General Cubic Case, Acta Arith. 87 (4) (1998).
[3] Alan Baker. Bounds for the solutions of the hyperelliptic equation. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 65, pages 439–444. Cambridge University Press, 1969.
[4] Hashimoto, Sachi, and Travis Morrison. "Chabauty-Coleman computations on rank 1 Picard curves." arXiv preprint arXiv:2002.03291 (2020).
A: This is another update of my answer, in which I also give a quick summary about solvability obstructions as suggested in Will Sawin's answer.
The smallest equation with easy-to-find solution is $0=0$ with $H=0$. The smallest equations with no solutions are $1=0$ and $-1=0$ with $H=1$. The smallest equations with at least one variable and no solutions are $x^2+1=0$ and $2x+1=0$ (and their variants) with $H=5$.
All equations with $H\leq 14$ either have small solutions or have trivial obstructions of at least one of the following types:
a) no real solutions (like $x^2+1=0$) or no real solution outside a region with finite number of integer points (like $x^2-2=0$),
b) no solutions modulo some integer (like $2x+1=0$), or
c) divisibility conditions imply at most finitely many possible solutions, and none of them works. An example is $(x^2+2)y=1$, where $y$ must be a divisor of $1$, but both divisors $y=1$ and $y=-1$ do not lead to a solution.
Equation $y^2=x^3-3$ with $H=15$ is the smallest equation with no solutions for which the trivial reasons above do not suffice and obstructions arising from divisibility properties of values of quadratic forms are needed. This equation belongs to the family of Mordell's equations and is well studied. The smallest equation with this type of obstruction which does not seem to be well-studied is $y(x^2-1)=z^2+1$ with $H=17$. This analysis covers all the equations up to $H\leq 21$.
Equation $xyz=x^2+y^2-z^2+2$ with $H=22$ is the smallest one with obstructions from Vieta jumping. This equation has been recently solved by Will Sawin and Fedor Petrov.
The listed obstructions suffice to solve all equations up to $H\leq 25$. There are several equations with $H=26$ which I currently do not see how to solve. An example is
$$
y(x^3-y)=z^2+2.
$$
Update July 2021: This equation is now solved. For the solution see https://math.stackexchange.com/questions/4159235/is-this-small-diophantine-equation-solvable?noredirect=1#comment8722722_4159235
For the next smallest open equations see my separate mathoverflow question Can you solve the listed smallest open Diophantine equations?
Update August 2021: For more details, see the arXiv preprint https://arxiv.org/abs/2108.08705
A: I will concentrate on the first question: ''One does not know the integral solutions of $P(x)=0$.'' To avoid discussion what exactly is meant by ''know the solutions'' if there are infinitely many of them, I consider the Hilbert 10th problem version of this question:
(*) For what ''smallest'' $P$ one does not know if there exist any integral solution of $P(x)=0$?
Next we need to clarify what is meant by ''unsolved'' in the title. If we insist on famous equation which people tried to solve and failed, that I know no open equation with $h<138$. Equation $x^3+y^3+z^3-33=0$ with $h=57$ suggested in the comments has been solved since that. For other equations listed in the comments the question (*) has a trivial ``Yes'' answer. The question is open for the equation $x^3+y^3+z^3-114=0$, but it has $h=138$.
However, there are many equations with smaller $h$ which are ''unsolved'' just because no-one tried to solve them. I have written a computer program which enumerates all equations with $h=1,2,3,\dots$. Most of them either have small solutions or does not have it for completely trivial reason, like non-existence of real solutions or divisibility obstruction with a small module. The first equation which is not completely trivial is $y^2=x^3-3$, but this is a special case of famous Mordell equation and is known to have no integer solutions.
The first equation which is not completely trivial and (to the best of my knowledge) was not discussed in the literature is
$$
x^2y = y^2 + z^2 + 1.
$$
It has $h=17$, seems to have no integer solutions, but not for a trivial reason like obstruction with a small module. So, it is currently ''unsolved'' (because noone tried to solve it), and therefore answers your question.
If someone will solve this equation, I will use my program to name the next one. This way we may ultimately find the smallest equation which mathoverflow users do not know how to solve.
A: It might be enlightening to divide equations into further types - first three decidable types, then four undecidable types.
(1) Equations which have a small or otherwise easy-to-find solution
(2) Equations which known techniques prove have no solutions
(3) Equations which (somehow) have an existence proof that a solution exists, but no known explicit solution.
(4) Equations which accepted heuristics suggest should have finitely many or no solutions, and have no small solutions, suggesting there are no solutions at all, but for which no proof that they are unsolvable exists.
(5) Equations which accepted heuristics predict should have infinitely many solutions, but very few of a given size, where we have not found any solutions yet.
(6) Equations which are mysterious in that accepted heuristics predict there should be many solutions, even of reasonable size, but none can be found.
(7) Equations where it is not clear after some thought which heuristics we should believe.

My understanding of what the comments and answers say, in this language, is as follows:
Equations of type (1) and (2) occur at the lowest heights, with (1) occurring at height 0 and (2) occurring at height 1.
We can further subdivide (2) according to the nature of the disproof. According to Bogdan's analysis, the lowest-height unsolvable equations all have mod $p$ obstructions, and next come equations with obstructions arising from divisibility properties of values of quadratic forms (I guess these are probably Brauer-Manin obstructions), and after that equations with obstructions from Vieta jumping. I would guess that at not-much-greater height we will need another obstruction from the toolbox of number theory.
I suspect equations of type (3) exist only for truly absurd heights - one can certainly cook them up using the solution to Hilbert's 10th problem, but I currently can't think of another way.
Somewhere between height 22 and height 45, we get equations of type (4), as I believe Chris Wuthrich's example $x^3-1 -z^2(y^3-1)$ has this form (If we imagine the probability that $z^2 (y^3-1) + 1$ is a perfect cube is proportional to $(z^2 y^3)^{-2/3}$ then summing over $z$, $y$ gives a finite quantity). (Also, Matt F. gave an example of an equation whose nontrivial solutions have this property, but which also has trivial solutions).
Somewhere between height 22 and height 138, we get equations of type (5). The example I'm thinking of is $x^3+y^3+z^3=114$, which is the smallest remaining unknown sum of three cubes. In this case the heuristic of Heath-Brown suggests there should be an (explicit) constant multiple of $\log \log n$ solutions with $x,y,z < n$, so the fact that no solutions are known is consistent with these heuristics.
Equations of type (6) and type (7) surely exist, but could potentially have enormous size.

One reason to study this question further is to understand which of the undecidable types appears first, and which are more common among equations of small height.
A: This answer is an update to the previous one. Equation $x^2y=y^2+z^2+1$ has been solved by Victor Ostrik in the comment to my previous answer. The program next returns equation $y(x^2+3)=z^2+1$, which reduces to question whether $\frac{z^2+1}{x^2+3}$ can be an integer, and the negative answer follows from the same observation about prime factors of $z^2+1$. Next it returns variations of these equations like $y(x^2+4)=z^2+2$ and $y(x^2-1-y)=z^2+4$ which I think can be solved by a similar argument. The first equation which looks different from above is
$$
xyz = x^2+y^2-z^2+2
$$
with $h=22$.
A: In all my answers so far, I have discussed only the solvability question: does a given equation have any integer solutions or not (in this case the current smallest open equation is still $y(x^3−y)=z^3+3$ of size $H=31$, see  Can you solve the listed smallest open Diophantine equations?).
But, of course, finding one solution does not mean to "solve" an equation. In this answer, I consider a much more general problem to decide whether the solution set is finite, and if so, list all the integer solutions. In this formulation, the smallest open equations are $y(z^2-y)=x^3-2$ and $xyz=x^3+y^2+2$ of size $H=22$. Note that for these equations the solvability question has trivial "Yes" answer, but it is open whether the solution sets are finite or infinite, see On the smallest open Diophantine equations: beyond Hilbert's 10 problem.
If the aim is to explicitly describe all solutions (in any form), then the smallest open equations are $y^2+z^2=x^3 \pm 1$ and $y(x^2-y)=z^2-1$ of size $H=17$, see How to describe all integer solutions to $x^2+y^2=z^3+1$? .
Finally, if we aim to describe all solutions in parametric form only, then the smallest open equations are $yz=x^3\pm 1$ and some other equations of size $H=13$, see Find all integer solutions to the following easy-looking Diophantine equations for more details and the full list of equations.
