54
$\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:

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

$\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, 2018 at 17:04
  • 21
    $\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, 2018 at 17:51
  • 6
    $\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, 2018 at 18:44
  • 10
    $\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, 2021 at 2:53
  • 9
    $\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, 2021 at 19:56

6 Answers 6

28
$\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$
4
  • 21
    $\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, 2020 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, 2020 at 17:59
  • 11
    $\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, 2020 at 18:12
  • $\begingroup$ For the equation x^2 y = y^2 + z^2 + 1, x^2 = z^2 + 2 and y=z^2 + 1. I doubt that there are integer solutions to this problem. $\endgroup$
    – A. J.
    Feb 20, 2022 at 4:01
21
$\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
  • 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, 2021 at 13:36
14
$\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, 2020 at 21:54
  • 5
    $\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, 2020 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, 2020 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, 2020 at 18:15
  • 2
    $\begingroup$ @HarryAltman Oh, hmm, Not sure what I meant then. I'll have to think about this again. $\endgroup$
    – JoshuaZ
    Nov 1, 2020 at 19:14
8
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Excuse my late curiosity, but I have a small question: In your answers, you mentioned an algorithm that computes you all diophantine equations of a certain height. While I have found a few naïve ways to do just that, I can not for the life of me figure out how to make this computationally feasible for larger $h$. Do you mind sharing how you have done this? $\endgroup$
    – TheOutZ
    Dec 12, 2023 at 23:37
  • $\begingroup$ There is no magic here, just a step-by-step work. We start with a naïve way, probably one of a few you discovered. Then we eliminate easy equations. For example, all equations of the form ax_i = P where P is a polynomial in variables other than x_i are easy. And so on. With no restrictions on the equations and the problem, the smallest open ones have size H=17. For restricted problems we need to go deeper but can do search more efficiently. For example, if we only need to determine whether solutions exist, we can eliminate all equations with small solutions, which greatly reduces the search. $\endgroup$ Dec 13, 2023 at 12:58
  • $\begingroup$ Grechuck After pondering it a bit more and coding it up, I admit my defeat. While I can see how eliminating "easy equations" might reduce the search space a tiny bit, I fail to see how we get all (or quickly assure of trivialness of most) of these equations in the first place - after all, the space of possibilities grows (even with a modest bound on the coefficients) enormously fast. Let's phrase it this way: How did you, for example, manage to find all equations up to $h=17$ in the original question (ignoring verifying solutions for a moment)? Am I just too blind to see it? $\endgroup$
    – TheOutZ
    Dec 19, 2023 at 0:55
  • $\begingroup$ Quartic equations up to $17$ are easy to list, so consider at most cubic. Assume we have $n=4$ variables, say $x,y,z,t$. List all possible monomials of degree $d\leq 3$ without coefficients, that is, $1,x,y,z,t,x^2,y^2,xy,...$. Consider all combinations of such monomials with total $h$ up to $17$. For some combinations, for example $1,x^3,yz,t$, all equations are easy no matter what are coefficients. We can exclude such combinations. For each of the remaining combinations, consider all possible coefficients. Then do the same for $n=2,3,5,...$ variables. On my computer, this works quite fast. $\endgroup$ Dec 19, 2023 at 10:07
6
$\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, 2021 at 17:59
  • $\begingroup$ Yes, mathoverflow.net/questions/392993/… $\endgroup$
    – Bogdan
    Jul 7, 2021 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, 2021 at 19:07
  • 3
    $\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, 2021 at 19:43
  • 3
    $\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, 2021 at 16:56
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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