[FOM] Difficult?

[Rahul Santhanam]

>  > This still does not answer the original question about hardness. A
>  > hardness result would probably be quite difficult to show as it would
>  > effectively imply that there is no poly-time algorithm for computing
> f(n).
>
> Unless I'm misunderstanding you, then the question of poly-time
> algorithm for calculating pi(n) mod 2 is not relevant to Friedman's
> question about how many symbols this calculation would take in ZFC.
> There is, for example, a poly-time algorithm for determining whether
> Mersenne numbers are prime (either Agrawal et al's recent algorithm or
> the more classical Lucas-Lehmer test).  Yet we have no reason (to my
> knowledge) to suspect that if 2^(2^127-1)-1 is prime, then it would
> require fewer than 2^100 symbols to prove it in ZFC.  Even a linear time
> algorithm would require O(2^127) symbols to do it.
>
> (Aside:  The primality of this "double Mersenne prime" has been looked
> at, and to my knowledge no factor is known of it.  The reason it was
> looked at is as follows:
> 2 is prime
> 3=2^2-1 is prime
> 7=2^3-1 is prime
> 127=2^7-1 is prime
> 2^127-1 is prime
> 2^(2^127-1)-1 must be prime too, right?)
>

I was making the following 3 points -
(1) The language {n | pi(n) mod 2 = 0} is in a class generally believed to
be smaller than P^#P and is hence unlikely to be hard for P^#P.
(2) If one is less literal about the use of the word "hard" and only
requires the conclusion that the language is "intractable", then a
theorem by Toda shows that a hardness result for the smaller class would
imply reducibility of every language in the poly-time hierarchy to the
language and hence the language would be unlikely to be in P.
(3) Hardness results for either pi(n) or the language in (1) would
probably require significant advances in number theory. I am not sure
whether is any evidence that isn't an exact formula for pi(n).

My response did not take into account the context of Harvey's question.
A polynomial-time algorithm for primality certainly implies a polynomial
upper bound on the size of proofs of primality in any logical system where
Turing machine computations can be efficiently simulated (keeping in mind
that constants matter in the present context - I don't think there is any
upper bound known on the constant in the O() notation in
Agrawal-Kayal-Saxena's original proof of correctness of their algorithm).
Lower bounds are a different matter - I'm not sure how much hardness
results help here...

In your example of Mersenne primes, the natural (i.e., most compact)
representation of a candidate prime n is only log log log(n) bits long.
I think it is Harvey's point that "sparsifying" a language in this way is
not likely to make it much easier to solve. The n for which pi(n) is
calculated in his conjecture has an extremely compact representation; the
intuition is that this gives us no advantage. I have no idea how one would
go about proving this, though. Perhaps parametrizing the conjecture would
help.

Best,
Rahul.