[FOM] Difficult?
Harvey Friedman
friedman at math.ohio-state.edu
Fri Apr 25 23:34:39 EDT 2003
Let n be a specific big integer of some interest. I want to know if
the number of primes less than n is even or odd.
DIGRESSION. Is the set of all positive integers n in base 2 such that
the number of primes less than n is even, #P-complete in the sense of
computational complexity theory? Same question with regard to the
function f(n) = the number of primes less than n.
So here is the main event.
CONJECTURE. "the number of primes less than 2^2^2^2^2^2^2^2 is even"
cannot be proved or refuted in ZFC even with large cardinal axioms,
without using at least 2^2^100 symbols, even if abbreviations are
allowed.
More information about the FOM
mailing list