MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


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

share|cite|improve this question
up vote 4 down vote accepted

The statement to be proved in the passage mentioned by the OP is Theorem 1.2. In the formulation of this result it says that $[a,b]$ is an interval of size at most $N^{1/2 + c}$ contained in $[N,2N]$. Thus, I strongly assume that this condition is also imposed at the point and OPs example for concreteness does not fulfil it. Indeed imposing this assumption on $a,b$ and using the mean value theorem for j-th root function one gets the claimed bound for $b^{1/j} - a^{1/j}$.

share|cite|improve this answer
That's the condition I missed. Thanks! – Charles Nov 16 '11 at 18:10
So basically Theorem 1.2 has no advantage over using Lifchitz's formula twice? – Charles Nov 16 '11 at 19:37
@Charles: You are welcome. I am sorry I cannot answer the follow-up; what formula do you mean? (I tried to search but first all I found was physics-things, then also prime things but not really sure what is meant.) – user9072 Nov 16 '11 at 21:55
Nevermind, I see the advantage -- Theorem 1.2 is slightly faster though works under more restrictive conditions. The formula I meant was $\pi(x)\equiv \sum_{m\le\sqrt x}\mu(m)\sum_{n\le\sqrt{x/m^2}} \left\lfloor\frac{x}{nm^2}\right\rfloor\pmod2.$ – Charles Nov 17 '11 at 14:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.