SUM OF THREE CUBES

[Timothy Y. Chow]

Harvey Friedman wrote:
> QUESTION: Is the set of all sums of three cubes of integers recursive?
> It is obviously recursively enumerable.
>
> This seems to be the most attractive set of integers for which it is
> not known whether it is recursive. Any competitors?

This question came up about 20 years ago here on FOM.

https://cs.nyu.edu/pipermail/fom/1999-November/003472.html

Assuming you're looking for Diophantine examples, one competitor might be 
the "rational cuboid"; it is unknown whether there exists a 3-dimensional 
rectangular box whose edge lengths, face diagonals, and body diagonal are 
all integers.  (You might object that a set which is not known to be 
nonempty is not very elegant.  But the sum of three cubes has this flavor, 
too; most number theorists expect that every integer not congruent to 4 or 
5 mod 9 is a sum of three cubes.)  There's also the "congruent number 
problem"; a congruent number is a positive integer that is the area of a 
right triangle with three rational number sides.

A number theorist would say that the rational cuboid problem is hard 
because we don't know much about arithmetic surfaces of general type, and 
the reason that there is no known algorithm for deciding whether an 
integer is a congruent number is that we don't know an algorithm for 
determining whether the elliptic curve y^2 = x^3 - n^2 x has positive 
rank.

If you are willing to cast your net a little wider, both MathOverflow and 
cstheory.SE have lists of attractive decision problems whose decidability 
is not known.

https://mathoverflow.net/q/345388 
https://mathoverflow.net/a/15306
https://cstheory.stackexchange.com/q/18846

The top answer on the CS site is, given a finite list of 2x2 integer 
matrices, do they multiplicatively generate the zero matrix?  Note that 
the 3x3 case is known to be undecidable.

> QUESTION: Is there an integer such that the question of whether it is
> the sum of three cubes is independent of ZFC?

As mentioned above, the majority opinion seems to be that every integer 
not congruent to 4 or 5 mod 9 is the sum of three cubes.  If the majority 
opinion is correct, then the answer to this question is no.

> I got interested in the question of giving natural sets of integers
> KNOWN to be nonrecursive. See
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.170.8659&rep=rep1&type=pdf
> https://www.ams.org/journals/tran/2005-357-03/S0002-9947-04-03632-3/S0002-9947-04-03632-3.pdf

There's also a MathOverflow list of decision problems known to be 
undecidable.

https://mathoverflow.net/q/11540/

But I don't think any of these have the flavor that you're looking for, 
except perhaps FRACTRAN, and the related "generalized Collatz problem," 
which was shown by Kurtz and Simon to be undecidable.

http://people.cs.uchicago.edu/~simon/RES/collatz.pdf

Tim