FOM: A Natural(?) Nonrecursive Set of Integers (more)

[Harvey Friedman]

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

I should have mentioned that you can

i) replace 9 with any specific integer at least 9;
ii) replace 9 with a parameter.

Here is how the previous e-mail of 8:20AM 9/6/01 would like with 9 replace
with a parameter.

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 multivariate polynomial with integer coefficients whose number of
variables, degree, and coefficients are of
magnitude at most m.

Let A be the set of all integers n which is the maximum value of some
multivariate polynomial with integer coefficients whose number of
variables, degree, and coefficients are 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 multivariate polynomial with integer coefficients whose
number of variables, degree, and coefficients are of magnitude at most m.

Let B be the set of all integers n which is the number of positive values
of some multivariate polynomial with integer coefficients whose number of
variables, degree, and coefficients are 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.