I was reading the Polymath4 project and have trouble understanding one of the arguments. From page 6 of [1] (either the preprint or the final paper):

For any j ≥ 2, the interval $[a^{1/j}, b^{1/j}]$ has size $O(N^c)$ (by the mean value theorem), and so the $j$th summand on the RHS can be computed in time $O(N^{c+o(1)})$ by the AKS algorithm.

$c>0$ is an unspecified small constant and $N\le a\le b\le2N$ are arbitrary. $c$ is probably very tiny but implicitly $c<0.22.$ The summand referenced is $\left|p\in[a^{1/j},b^{1/j}]: p\text{ prime}\right|.$

I don't understand what's meant here. Taking, for concreteness, $j=2,a=N,b=2N$ this is:

The interval $[\sqrt N, \sqrt{2N}]$ has size $O(N^c)=o(N^{0.22})$ (by the mean value theorem), and so $\left|p\in[\sqrt N, \sqrt{2N}]: p\text{ prime}\right|$ can be computed in time $O(N^{c+o(1)}).$

If by size the authors meant the number of integers in the range it would be wrong: clearly that is $(\sqrt2-1)N^{0.5}+o(1)\neq o(N^{0.22}).$ But I can't think of another meaning that works here.

Further, it's not even clear to me if the result can be salvaged. Counting the number of primes in the interval should take time $O(N^{0.25+o(1)})$ with the Lagarias-Odlyzko algorithm, so I can't even count the set in that time. (On the other hand, this does not jeopardize the theorem, for which the time need only be $O(N^{0.5-c+o(1)}).$)

I must be misunderstanding something here; any help?

## References

[1] Terence Tao, Ernest Croot III and Harald Helfgott, Deterministic methods to find primes, Mathematics of Computation (in press). arXiv:1009.3956