38
$\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$
13
  • 5
    $\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
  • 17
    $\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
  • 5
    $\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
  • 5
    $\begingroup$ Re the opening bid, $x^3 + y^3 + z^3 = 33$ is now (well, for some time, but this question just recently came back to the front page) known to be soluble. $\endgroup$
    – LSpice
    May 18 at 2:53
  • 4
    $\begingroup$ In contrast to what is claimed above, deciding whether a two-variable polynomial equation has an integer solution is still an open problem. Runge's method (used in the Hilliker-Straus paper mentioned above) and Baker's method are effective only for special equations. $\endgroup$ Jul 26 at 19:56
22
$\begingroup$

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.

$\endgroup$
3
  • 14
    $\begingroup$ Equation $x^2y=y^2+z^2+1$ has no integral solutions: rewrite it as $y(x^2-y)=z^2+1$. Thus we want to factorize $z^2+1$ into two factors sum of which is a square (in particular, both factors are positive). But all prime factors of $z^2+1$ are of the form $4k+1$ or 2 appearing with exponent at most 1, so all positive factors are congruent to 1 or 2 modulo 4. This is a contradiction. $\endgroup$ Aug 31 '20 at 17:07
  • 1
    $\begingroup$ @VictorOstrik Sorry, how are you getting that $y(x^2-y)$ must have a 3 mod 4 factor? $\endgroup$
    – JoshuaZ
    Aug 31 '20 at 17:59
  • 8
    $\begingroup$ @JoshuaZ Assume that $y=4k+1$ and $x^2-y=4l+1$. Then $x^2=4k+4l+2$ which is impossible. Similarly assuming $y=4k+1$ and $x^2-y=2(4l+1)$ or vice versa we get that $x^2$ is congruent to 3 modulo 4. $\endgroup$ Aug 31 '20 at 18:12
16
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ You predict that equations of type (6) may have enormous size. Well, assume for a moment that we do not know Vieta jumping obstruction. Then even for h=22 there is an equation with no solutions found for which heuristics predict there should be many solutions of reasonable size. So, it would be of type (6), and only the fact that we know Vieta jumping technique moves it to type (2). I assume that there might be equations with h in range from 26 to 40 which have no solutions for yet-to-be discovered obstructions and are therefore currently of type (6). $\endgroup$
    – Bogdan
    Jul 9 at 13:36
8
$\begingroup$

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

$\endgroup$
7
  • 5
    $\begingroup$ Your equation looks a bit like the Markoff surface $x^2+y^2+z^2=3xyz$. One can consider the phenomenon (Vieta jumping) If $(x,y,z)$ is a solution then $(yz-x, y,z), (x,xz-y,z),$ and $(x,y,-xy-z)$ are all solutions. Maybe one can show that, for all solutions, at least one of these must have smaller height? $\endgroup$
    – Will Sawin
    Aug 31 '20 at 21:54
  • 3
    $\begingroup$ Let me comment more generally that the heuristic of Heath-Brown on the sum of three cubes problem suggests, I believe, that broadly similar equations (i.e. cubics in three variables) that are sufficiently generic (don't have quadratic-recriprocity-based obstructions, Vieta jumping structure, or maybe a few other similar things), should have a constant times $\log n$ solutions of height up to $n$, so that if this constant is small, might have no solutions found by an easy computer search. So I think there is an unsolved problem somewhere among the three-variable cubics. $\endgroup$
    – Will Sawin
    Aug 31 '20 at 22:04
  • 3
    $\begingroup$ This equation is solvable mod p for any prime p. $z \equiv 1$ (mod p), $x \equiv y $ (mod p) has a solution when $p \equiv 1$ (mod 4). $z \equiv 0$ (mod p), and $x \equiv y y$ has a solution when -2 is a QR mod $p$. Similarly, $z \equiv -2$ (mod p) and $x \equiv y$ has a solution when $2$ is a QNR mod $p$. So that covers all of them. I haven't checked lifting for powers of $p$ but it should go through also. So if this one has no solutions it isn't just due to a simple modulus argument. $\endgroup$
    – JoshuaZ
    Sep 4 '20 at 11:44
  • 1
    $\begingroup$ That results in $x^2 + 1=0$, though, i.e., just again covers the $p\equiv1 \pmod{4}$ case. $\endgroup$ Nov 1 '20 at 18:15
  • 1
    $\begingroup$ @HarryAltman Oh, hmm, Not sure what I meant then. I'll have to think about this again. $\endgroup$
    – JoshuaZ
    Nov 1 '20 at 19:14
3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Do you have a link to where the H=22 equation is solved? $\endgroup$
    – JoshuaZ
    Jul 7 at 17:59
  • $\begingroup$ Yes, mathoverflow.net/questions/392993/… $\endgroup$
    – Bogdan
    Jul 7 at 18:33
  • 5
    $\begingroup$ Why don't you edit your original answer with these updates? It'd be nice to see the evolution of the study in a single answer. $\endgroup$
    – user347489
    Jul 7 at 19:07
  • 2
    $\begingroup$ If you have lost access to your account, you can request help from the moderators, I heard it is possible to merge accounts in such cases. $\endgroup$
    – Wojowu
    Jul 7 at 19:43
  • $\begingroup$ A small remark: the infamous "1988 IMO Q6" concerns the solutions to the Diophantine equation $x^2+y^2-xyz-z=0$, which has $H=18$. Of course it has solutions (which can be analyzed by Vieta jumping, see en.wikipedia.org/wiki/Vieta_jumping#Standard_Vieta_jumping), so it doesn't directly give an example for this question, but it may still be an equation worth noting. $\endgroup$
    – Terry Tao
    Aug 20 at 16:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.