This is a continuation of Research Thread II of the “Finding primes” polymath project, which is now full. It seems that we are facing particular difficulty breaching the square root barrier, in particular the following problems remain open:
- Can we deterministically find a prime of size at least n in time (assuming hypotheses such as RH)? Assume one has access to a factoring oracle.
- Can we deterministically find a prime of size at least n in time unconditionally (in particular, without RH)? Assume one has access to a factoring oracle.
We are still in the process of weighing several competing strategies to solve these and related problems. Some of these have been effectively eliminated, but we have a number of still viable strategies, which I will attempt to list below. (The list may be incomplete, and of course totally new strategies may emerge also. Please feel free to elaborate or extend the above list in the comments.)
Strategy A: Find a short interval [x,x+y] such that , where is the number of primes less than x, by using information about the zeroes of the Riemann zeta function.
Comment: it may help to assume a Siegel zero (or, at the other extreme, to assume RH).
Strategy B: Assume that an interval [n,n+a] consists entirely of u-smooth numbers (i.e. no prime factors greater than u) and somehow arrive at a contradiction. (To break the square root barrier, we need , and to stop the factoring oracle from being ridiculously overpowered, n should be subexponential size in u.)
Comment: in this scenario, we will have n/p close to an integer for many primes between and u, and n/p far from an integer for all primes larger than u.
Strategy C: Solve the following toy problem: given n and u, what is the distance to the closest integer to n which contains a factor comparable to u (e.g. in [u,2u])? [Ideally, we want a prime factor here, but even the problem of getting an integer factor is not fully understood yet.] Beating here is analogous to breaking the square root barrier in the primes problem.
- The trivial bound is u/2 – just move to the nearest multiple of u to n. This bound can be attained for really large n, e.g. . But it seems we can do better for small n.
- For , one trivially does not have to move at all.
- For , one has an upper bound of , by noting that having a factor comparable to u is equivalent to having a factor comparable to n/u.
- For , one has an upper bound of , by taking to be the first square larger than n, to be the closest square to , and noting that has a factor comparable to u and is within of n. (This paper improves this bound to conditional on a strong exponential sum estimate.)
- For n=poly(u), it may be possible to take a dynamical systems approach, writing n base u and incrementing or decrementing u and hope for some equidistribution. Some sort of “smart” modification of u may also be effective.
- There is a large paper by Ford devoted to this sort of question.
Strategy D. Find special sequences of integers that are known to have special types of prime factors, or are known to have unusually high densities of primes.
Comment. There are only a handful of explicitly computable sparse sequences that are known unconditionally to capture infinitely many primes.
Strategy E. Find efficient deterministic algorithms for finding various types of “pseudoprimes” – numbers which obey some of the properties of being prime, e.g. . (For this discussion, we will consider primes as a special case of pseudoprimes.)
Comment. For the specific problem of solving there is an elementary observation that if n obeys this property, then does also, which solves this particular problem; but this does not indicate how to, for instance, have and obeyed simultaneously.