8866128975287528³+(-8778405442862239)³+(-2736111468807040)³

Update: The result was achieved by Andrew Booker from Bristol. Here is the preprint Cracking the problem with 33.

It is a notoriously difficult open problem which integers can be written as the sum of three integer cubes.  Such integers cannot be 4 or 5 modulo 9, since integer cubes are 0, \pm 1 modulo 9. Euler’s proved that 0 has no such representation. It can be conjectured that for every other integer such a representation does exist. For more on the problem see this 1996 posting by Noam Elkies.

33 was the smallest integer for which this was not known and Andrew Booker in Bristol just proved that

I heard it from Alon Amit on Quora and FB who saw it in Tim Browning’s homepageAlon’s Quora post contains more information on the problem, and a link to Bjorn Poonen’s paper on undecidability in number theory, which opens with the problem. The earlier record (30) was achieved in 1999 by  Michael Beck, Eric Pine, Wayne Tarrant, and Kim Yarbrough Jensen, following an approach suggested by N. Elkies. (Here is the paper.)

Update: the opening  sentences from Booker’s paper.

_______

Let k be a positive integer with k ≠ ±4 (mod 9). Then Heath-Brown [HB92] has conjectured that there are infinitely many triples (x,y,z)\mathbb Z^3 such that

 \displaystyle (1)~~~k = x^3 + y^3 + z^3.

Various numerical investigations of (1) have been carried out, beginning as early as 1954 [MW55]; see [BPTYJ07] for a thorough account of the history of these investigations up to 2000. The computations performed since that time have been dominated by an algorithm due to Elkies [Elk00]. The latest that we are aware of is the paper of Huisman [Hui16], which determined all solutions to (1) with k ≤ 1000 and max{|x|,|y|,|z|}≤ 10^{15}. In particular, Huisman reports that solutions are known for all but 13 values of k ≤ 1000:

(2) 33, 42, 114, 165, 390, 579, 627, 633, 732, 795, 906, 921, 975.

Elkies’ algorithm works by finding rational points near the Fermat curve X^3 +Y^3 = 1 using lattice basis reduction; it is well suited to finding solutions for many values of k simultaneously. In this paper we describe a different approach that is more efficient when k is fixed. It has the advantage of provably finding all solutions with a bound on the smallest coordinate, rather than the largest as in Elkies’ algorithm. This always yields a nontrivial expansion of the search range since, apart from finitely many exceptions that can be accounted for separately, one has

max{|x|,|y|,|z|} > 3 √2min{|x|,|y|,|z|}.

_______

Additional links

And here is A 2015 Tim Browning in Numberphile video about the problem; Reddit discussion; 2013 MO question; The Aperiodical.

And I met Tim Browning last fall at IST, Austria!  Tim told me about his works with Will Sawin and others applying the circle method (and other methods from Analytic number theory) to algebraic geometry. See the paper by Browning and Sawin A geometric version of the circle method and subsequent papers.

 

Update (Sept 6, 2019):
42 = (−80538738812075974)³+80435758145817515³+12602123297335631³

This entry was posted in Number theory and tagged . Bookmark the permalink.

17 Responses to 8866128975287528³+(-8778405442862239)³+(-2736111468807040)³

  1. Vincent says:

    Nice, I never realized this was so wide open! Can you say a bit more about Euler’s result. In particular what is wrong with my example $1^3 + 0^3 + (-1)^3 = 0$?

  2. vegafrank says:

    New version update(March 10. 2019)

    P versus NP is considered as one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This problem was first mentioned in a letter written by John Nash to the National Security Agency in 1955. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this huge problem have failed. Another major complexity class is coNP. Whether NP = coNP is another fundamental question that it is as important as it is unresolved. We prove there is a problem in coNP that is not in P. In this way, we show that P is not equal to coNP. Since P = NP implies P = coNP, then we also demonstrate that P is not equal to NP.

    https://zenodo.org/record/2589001

    • Xezlec says:

      Just for fun, I actually tried reading this thing. The language and notation are so confused and wrong that it took at least an hour for me to even figure out what you were trying to say. I think you were trying to describe the problem of determining whether a given integer x is the smallest integer accepted by a given circuit C. I think you were arguing that this problem is not in P, and since it’s obviously in co-NP, that proves that P != NP. The reason you think it’s not in P seems to be that (1) you assume that in order to solve that problem, it is necessary to first find a set S of all possible integers that satisfy C, and (2) the only way to find this set is a brute force search. It seems very unlikely that either of these assumptions is true.

      • vegafrank says:

        Thanks for reading my proof. I will take the problem that you had to understand it as a mistake that I need to improve in the following versions. Look at the point (1) and (2) in the following reduction: Suppose we want to know whether a Boolean circuit C is in CIRCUIT-UNSAT (that is, whether C does not accept any input value). We can construct another circuit C’ such that C’ only accepts the input value 0. Then, we can mix C and C’ into a new circuit C” with an OR gate joining the output gates and coinciding the input gates. The new circuit C” accepts some input x if and only if x is accepted by C or C’. Therefore, the instance (0, C”) such that 0 is the smallest integer that C” accepts would mean that C belongs to CIRCUIT-UNSAT. Since, we can construct C” in polynomial time, then it results that the points (1) and (2) (that you mentioned) are applied to CIRCUIT-UNSAT in a respective way. Consequently, it is very reasonable that these assumptions is indeed true.

      • vegafrank says:

        I do not mean 0 but (2^b – 1) where b is the number of input gates in C. The instance will be (2^b – 1, C”) and the circuit C’ only accepts 2^b – 1 instead of 0. The Mistake is fixed.

      • vegafrank says:

        New version update(March 14. 2019)

        P versus NP is considered as one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This problem was first mentioned in a letter written by John Nash to the National Security Agency in 1955. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this huge problem have failed. Another major complexity class is coNP. Whether NP = coNP is another fundamental question that it is as important as it is unresolved. We prove there is a problem in coNP that is not in P. In this way, we show that P is not equal to coNP. Since P = NP implies P = coNP, then we also demonstrate that P is not equal to NP.

        https://zenodo.org/record/2593729

  3. eppstein says:

    Another (new) link for this problem: https://en.wikipedia.org/wiki/Sums_of_three_cubes

    • Gil Kalai says:

      Thanks David! I wonder if there is a result (or even a hope for a result) of the form: If d is such that there are integers x,y,z with x^3 + y^3+z^3=d, then there is such a triple with |x|,|y|,|z|\le f(d), for some specific f(d). Or perhaps some result of the form there are infinitely many d such that there are integers x,y,z with x^3 + y^3+z^3=d and |x|,|y|,|z|\ge g(d) for some specific g(d).

      • eppstein says:

        I don’t know enough of this sort of number theory to guess which way these things should go. But according to Booker’s manuscript the conjecture is that each d has infinitely many triples that represent it, so the answer to your second question would be yes. Or maybe you meant that |x|, |y|, |z| are all large in every representation rather than just that there exists a large representation.

        As for the first question, that would go a long way towards answering the implicit question at the start of Poonen’s survey, of whether these problems are decidable. (It would answer the question if f is computable). I infer that we probably don’t already know of such a result.

      • Gil Kalai says:

        Ohh, sorry I did not formulate my second question the way I meant it: It should be “Or perhaps some result of the form there are infinitely many d such that there are integers x,y,z with x^3 + y^3+z^3=d and such that there are no solutions to x^3 + y^3+z^3=d with |x|,|y|,|z| \le g(d) for some specific g(d). ”

        In words, the first question asks: assuming there are solutions (or even infinitely many solutions) can we give (prove of give heuristically) upper bounds on how large they are?

        The second question asks: Can we find (provably or heuristically) infinitely many values of d, so that there are solutions (known or conjectured) but there are no small (as a function of d) solutions?

  4. Gil Kalai says:

    Tim Browning told me that the result was achieved by Andrew Booker from Bristol.

  5. Gil Kalai says:

    What I find striking in this result is how easy it is to check the validity of the result, and thus also how large is the gap between the discovery and the verification. As for the discovery, Booker’s paper describes the algorithm and its implementation and concludes with “The total computation used approximately 15 core-years over three weeks of real time.”

  6. Pingback: 33을 3개의 3제곱수의 합으로 – udaqueness

  7. Gil Kalai says:

    Over Facebook Adin Pal asked: What are the integers that can be presented as the sum of two cubes? David Galvin gave the link to a 2003 paper by Kevin A. Broughan: https://cs.uwaterloo.ca/journals/JIS/VOL6/Broughan/broughan25.pdf

  8. Gil Kalai says:

    Updatק Sept 6 2019: 2019: (−80538738812075974)³+80435758145817515³+12602123297335631³=42, https://people.maths.bris.ac.uk/~maarb/. This completes all the numbers less than 100.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s