SUM OF THREE CUBES

[Harvey Friedman]

My thanks go to Timothy Chow for his very informative two postings on this
topic.

I still think that the set of all sums of three cubes of integers is the
"simplest" or "most attractive" candidate for a nonrecursive set of
integers.

Let's try to make some associated theory about this. Here are two ways.

1. The full definition of the set of integers using plus and times.
2. The full definition of a term using plus and times.

Obviously there are other more liberal categories to consider, such as
allowing constant integers. Here "integer" means Z, but one can also use N
or Z+.

But let's just stick to 1,2 for this posting. In particular, no constants.

For 1, we have the definition

The set of all n such that there exists a,b,c such that n = aaa + bbb + ccc.

We can use various complexity measures. For example, for this posting, let
us use *the number of occurrences of variables*.

So on this measure, (therexists a,b,c)(n = aaa + bbb + ccc) has measure 13.

CONJECTURE. All sets of integers satisfying a first order formula in one
free variable with at most 12 occurrences of variables is recursive.

For 2, again use the number of occurrences of variables. So we have aaa +
bbb + ccc. The number of such here is 9.

CONJECTURE. All sets of values of any expression in +,x with at most 8
occurrences of variables is recursive.

Harvey Friedman
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20201013/fd632b71/attachment.html>