FOM: Re: a "hard" problem?

[Harvey Friedman]

I just received the following e-mail from fellow subscriber Odlyzko and
also from Stephen Wolfram which essentially refutes the conjecture I made
in my posting of 1:55AM 7/12/00:

>PROBLEM: Is the number of primes less than 2^100 even? Is the number of
>primes less than 2^10,000 even?

>CONJECTURE?? The version with 2^10,000 cannot be proved or refuted in ZFC
>with abbreviations without using more than 2^100 bits.

It still may be that we are going to have trouble deciding the question for
2^10,000, or even for 2^100. Below, I consider replacing this conjecture by
the apparently far more mild conjecture:

CONJECTURE. Let n be an exponential stack of 2's of height 8. The question
"the number of primes less than n is even" cannot be proved or refuted in
ZFC with abbreviations with fewer than 2^1000 symbols.

The idea is to come up with as mathematically attractive as possible
candidate for a single completely finite problem for which one has some
feeling that it cannot be decided in ZFC in any feasible way. Obviously,
any completely finite problem can be decided in ZFC by running through all
of the cases.

Here is a copy of some very interesting and helpful correspondence.

>Harvey,
>
>  The number of primes below 2^100 is not hopeless.  There is an
>  algorithm (invented by Jeff Lagarias and myself) that computes
>  pi(x) in x^(1/2 + o(1)) steps.  This algorithm may not be practical
>  even for 2^100, but there is another algorithm, invented by Jeff
>  Lagarias, Victor Miller, and myself, which runs in time
>  x^(2/3 + o(1)), and is eminently practical.  The highest value
>  that has been computed with it so far is pi(10^20), so with
>  advances in hardware one could think of using it to compute
>  pi(2^100) in a couple of decades.
>
>  Neither algorithm offers any hope of getting the parity of pi(2^10,000).
>
>  Unfortunately I have no idea how to even try proving any lower
>  bounds for this problem.  It might be easy, for all we know.
>
>************************************************************************
>Andrew Odlyzko                                      amo at research.att.com
>AT&T Labs - Research                                voice:  973-360-8410
>http://www.research.att.com/~amo                    fax:    973-360-8178
>************************************************************************

>Date: Wed, 12 Jul 2000 23:45:50 -0500
>From: Stephen Wolfram <sw at wolfram.com>
>X-Accept-Language: en
>MIME-Version: 1.0
>To: Harvey Friedman <friedman at math.ohio-state.edu>
>Subject: Re: a "hard" problem?

>Harvey Friedman wrote:
>>
>> PROBLEM: Is the number of primes less than 2^100 even? Is the number of
>> primes less than 2^10,000 even?
>>
>> I am under the impression that such problems are completely hopeless, even
>> with the aid of a computer. Hopeless, even if we wish to prove or refute it
>> with a high degree of certainty. Hopeless even to justify making a
>> conjecture as to whether it is true or false.
>>
>> But should we conjecture some sort of formal undecidability of this
>> question? E.g.,
>>
>> CONJECTURE?? The version with 2^10,000 cannot be proved or refuted in ZFC
>> with abbreviations without using more than 2^100 bits.
>>
>> This leads us to the question of what the best example is of a problem like
>> this where such a conjecture can be verified?
>>
>> At the moment, the examples I can think of are hopelessly obnoxious.
>>
>> Any comments?

>I think the particular problem you describe may not be the best....
>
>From a generic Mathematica 4, on a generic PC:
>
>In[1]:=
>Timing[PrimePi[2^30]]
>
>Out[1]=
>{0.094 Second, 54400028}
>
>In[2]:=
>Timing[PrimePi[2^35]]
>
>Out[2]=
>{2.719 Second, 1480206279}
>
>In[3]:=
>Timing[PrimePi[2^40]]
>
>Out[3]=
>{28.515 Second, 41203088796}
>
>
>The way this works is by using the expansion of PrimePi[ ] in terms of
>PolyLog[ ], Zeta[ ] etc., and keeping enough terms to be able to decide
>which integer is the correct result.
>
>Surprisingly, ideas based the Riemann-Siegel formula allow one to
>compute Zeta[1/2+I t] for large t with fairly little computational
>effort. (There has been recent work on this by several people, and I
>think future versions of Mathematica will be even faster than the
>above.)
>
>
>Best wishes,
>
>-- Stephen

Shipman writes 3:53PM 7/12/00:

>Because it is conceivable that some analytic approximation to the pi(x)
>function may be found which is calculable in polynomial time in the input
>size, a better example would use 2^2^10000  rather than 2^10000.

Your guess turned out to be right. So rewriting my Conjecture??, it would read:

CONJECTURE?? The question "the number of primes less than 2^2^10,000 is
even" cannot be proved or refuted in ZFC with abbreviations with fewer than
2^100 symbols.

It doesn't look like this conjecture can be refuted with state of the art
theory like my original conjecture. But now let's say it differently.

Just how dangerous is the following conjecture?

CONJECTURE. Let n be an exponential stack of 2's of height 8. The question
"the number of primes less than n is even" cannot be proved or refuted in
ZFC with abbreviations with fewer than 2^1000 symbols.

>In fact, if P=PSPACE, an open question, then the number of primes less
>than 2^n, and hence the parity of this number, is going to be calculable
>in time polynomial in n.

>If you don't want to have infeasible numbers as part of the problem
>statement, a better bet for a "hard" problem would be the parity of some
>reasonable-sized Ramsey number like R(10,10), because good approximations
>for R(n,n) seem much harder than good approximations to pi(n), though I
>don't think we'd be able to prove that such a problem was hard for the
>same reason (solvable in PSPACE).

In my opinion, P = PSPACE is extremely far fetched, and a practical form of
P = PSPACE relevant to such problems is nearly absurd. I was interested in
pushing the envelope here. "R(10,10) is even" has far less appeal, and also
is tied up with PSPACE as Shipman points out, and also there is enough
symmetry in the Ramsey situation that it might actually be fairly easy to
show that it is even or to show that it is odd. With the prime question,
there is no such feeling of symmetry.

As you indicate, one way to look at such problems is in terms of
computational complexity. One can look at A = {n: the number of primes < n
is even} and B = {n: the number of primes < an exponential stack of 2's of
height n is even} and ask about their computational complexity. Apparently
A can be computed with a time bound that is a reasonable polynomial in n,
but which may or may not be feasible for values like n = 100, depending on
a combination of computer hardware and theory and programming and number
theory advances! But what about the computational complexity of B?

Another way of raising the issue is this. Do we have any reliable intuition
as to whether a single sentence is "hard" to decide?

We do seem to have reliable intuitions as to the recursive solvalibility
of, and the computational complexity of, various problems.

And in the context of set theory, we really do have pretty reliable
intuitions now as to whether single set theoretic sentences are "hard" in
the sense of being undecided within the ZFC framework.