FOM: A Natural(?) Nonrecursive Set of Integers

[Harvey Friedman]

Natural(?) Nonrecursive Sets of Integers
by
Harvey M. Friedman
September 6, 2001

Here is a natural(?) nonrecursive set of integers.

For integers n,m, define R(n,m) if and only if n is the maximum value of
some polynomial P:Z^9 into Z with degree and coefficients of magnitude at
most m.

Let A be the set of all integers n which is the maximum value of some
polynomial P:Z^9 into Z with degree and coefficients of magnitude at most
log log log n.

For integers n,m, define S(n,m) if and only if n is the number of positive
values of some polynomial P:Z^9 into Z with degree and coefficients of
magnitude at most m.

Let B be the set of all integers n which is the number of positive values
of some polynomial P:Z^9 into Z with degree and coefficients of magnitude
at most log log log n.

THEOREM. A,B,R,S are of Turing degree <= 0'. A,B,R,S are are not Pi-0-1.
A,B meet every infinite r.e. set.

The expression log log log n is used as a particularly simple expression
that does the job. However, an interesting question is to figure out just
what expressions will make A and/or B nonrecursive.