Polynomial strategy

The polynomial strategy is a strategy to obtain a good algorithm for the finding primes project by means of computing certain polynomials in various rings that detect primes. The initial target is to obtain an elementary, deterministic [math]\displaystyle{ O(N^{1/2+o(1)}) }[/math] for obtaining a prime of size N, with the hope to beat the square root barrier later.

The basic ideas are as follows.

I. First, observe that to find a prime quickly, it would suffice to have an algorithm which, when given an interval [a,b] as input, determines whether that interval contains at least one prime. Indeed, once one has that algorithm, one can find a prime by starting with a large interval (e.g. [math]\displaystyle{ [10^k, 2 \times 10^k] }[/math]) that is already known to contain a prime (by Bertrand's postulate), and then reduce that interval to a single prime by a binary search using only O(k) steps.

II. Now fix [a,b], with a, b both of size O(N) (say), and consider the polynomial [math]\displaystyle{ f \in F_2[x] }[/math] defined by

[math]\displaystyle{ f(x) := \sum_{a \leq p \leq b} x^p \hbox{ mod } 2 }[/math]

where p ranges over primes. Clearly, this polynomial is non-zero iff [a,b] is a prime. So it will suffice to have an efficient algorithm (the benchmark time to beat here is [math]\displaystyle{ O(N^{1/2+o(1)}) }[/math]) which would detect whether f is non-zero quickly. (The reason for working modulo 2 will be made clearer in the next step.)

III. The reason we work modulo 2 is that f modulo 2 can be expressed in an appealingly "low-complexity" fashion (from the perspective of arithmetic circuit complexity). In particular, note that for a given number n, the number of divisors between 1 and n is odd if n is prime, and even if n is composite and non-square. So, we morally have

[math]\displaystyle{ f(x) = \sum_{a \leq n \leq b} \sum_{1 \leq d \lt \sqrt{n}: d | n} x^d \hbox{ mod } 2 }[/math] (1)

except for an error supported on square monomials [math]\displaystyle{ x^{m^2} }[/math] which hopefully can be compensated for later (and which can be computed in [math]\displaystyle{ O(N^{1/2+o(1)}) }[/math] time in any event).

The expression (1) can be rearranged as

[math]\displaystyle{ f(x) = \sum_{1 \leq d \lt \sqrt{b}} \sum_{a/d \leq m \leq b/d; m\gt d} x^{dm} \hbox{ mod } 2 }[/math].(2)

This expression has an arithmetic circuit complexity of [math]\displaystyle{ O(N^{1/2+o(1)}) }[/math], thanks to the Pascal's triangle modulo 2 identity

[math]\displaystyle{ (1+x)^{2^m-1} = 1 + x + \ldots + x^{2^m-1} }[/math]

and binary decomposition of the inner sum in (2). Unfortunately, this arithmetic circuit requires much more than [math]\displaystyle{ O(N^{1/2+o(1)}) }[/math] time to compute, due to the large amount of memory needed to store f (about O(N) bits), so arithmetic operations are very expensive.

IV. The next trick is to observe that in order to show that f mod 2 is nonzero, it suffices to show that [math]\displaystyle{ f(x) \hbox{ mod } (2, g(x)) }[/math] is nonzero for some low-degree g (e.g. degree [math]\displaystyle{ N^{o(1)}) }[/math]), or more generally that [math]\displaystyle{ f(x^t) \hbox{ mod } (2, g(x)) }[/math] is non-zero. The point is that because of the low arithmetic complexity of f, this criterion can be verified in just [math]\displaystyle{ O(N^{1/2+o(1)}) }[/math] time when g is low-degree.

For instance, if g(x)=x-1, then we are basically just evaluating f(1) mod 2, i.e. the parity of pi(x), which is known to be computable in time [math]\displaystyle{ o(N^{1/2}) }[/math], see prime counting function.

To finish the job, we need a result of the following form:

Goal 1 If [math]\displaystyle{ f(x^t) = 0 \hbox{ mod } (2,g(x)) }[/math] for many t, then f is zero.

Heuristics (see here) suggest that one needs to take t to be about [math]\displaystyle{ N^{1/2+o(1)} }[/math] in size. Using an FFT, it seems that one can compute all the [math]\displaystyle{ f(x^t) \hbox{ mod } 2, g(x) }[/math] simultaneously in time [math]\displaystyle{ N^{1/2+o(1)} }[/math] (how??), so the main job would be to establish Goal 1.

Here is a note suggesting that Strassen fast multiplication can be used to improve upon the FFT.