Oracle counterexample to finding pseudoprimes

One can consider the following soft generalisation to the finding primes conjecture:

Soft conjecture Suppose one has a set S of integers which is in P, and which is at least as dense at the primes (thus the set of k-digit elements of S has density [math]\displaystyle{ \gg 1/k }[/math]. Then there exists a deterministic algorithm which, when given an integer k, will produce an element of S of at least k digits in length in time poly(k).

This soft conjecture is for instance true if P=NP, by this argument. It certainly implies the finding primes conjecture, by taking S to be the set of primes. However, we show here that the soft conjecture fails in the presence of an oracle. Roughly speaking, this means that there is no "soft" way to prove the finding primes conjecture that uses nothing about the primes other than that they are in P and are dense.

Here's how it works. For each integer k, we recursively define the set [math]\displaystyle{ S_k }[/math] to be the set of k-digit numbers whose Kolmogorov complexity is at least [math]\displaystyle{ \sqrt{k} }[/math] relative to [math]\displaystyle{ S_1,\ldots,S_{k-1} }[/math]. What this means is that n lies in [math]\displaystyle{ S_k }[/math] if n has k digits and it is not possible to find a Turing machine of length less than [math]\displaystyle{ \sqrt{k} }[/math] that can compute n even given access to oracles for [math]\displaystyle{ S_1,\ldots,S_{k-1} }[/math]. An easy counting argument shows that all but at most [math]\displaystyle{ 2^{\sqrt{k}} }[/math] k-digit integers lie in [math]\displaystyle{ S_k }[/math]. Thus if we set S to be the union of the [math]\displaystyle{ S_k }[/math], then S is at least as dense as the primes (in fact it is much, much denser).

We now work relative to an oracle for S, i.e. the oracle takes any number n as input and returns whether it is in S in unit time. Clearly, S is now in P. Suppose for contradiction that there was an algorithm A (of length O(1)) which, when given k as input, returns an element of S at least k digits in length in time poly(k).

Let k be large. One can show inductively that every integer of k digits or more produced by the algorithm A with input k in time less than poly(k) has a Kolmogorov complexity of O( log(k) ) relative to [math]\displaystyle{ S_1,\ldots,S_{k-1} }[/math]; the point is that the oracles for [math]\displaystyle{ S_k, S_{k+1},\ldots, }[/math] can be shown by induction to be useless as the numbers produced by A will never lie in these sets. But O(log(k)) is less than [math]\displaystyle{ \sqrt{k} }[/math] for k large, so A cannot produce an element of S of k digits or more, a contradiction.

The same argument shows that there is no soft way to prove the weak conjecture either. However, it is not obvious whether one can adapt the argument to handle the situation in which there is a factoring oracle, since of course the fundamental theorem of arithmetic doesn't work if one replaces the primes by an arbitrary set S of "pseudoprimes".

It is also not known at present whether one can modify the above oracle to produce a situation in which P=BPP (or in which $latex P \neq BPP$).