1
$\begingroup$

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

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

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}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ That's the condition I missed. Thanks! $\endgroup$
    – Charles
    Commented Nov 16, 2011 at 18:10
  • $\begingroup$ So basically Theorem 1.2 has no advantage over using Lifchitz's formula twice? $\endgroup$
    – Charles
    Commented Nov 16, 2011 at 19:37
  • $\begingroup$ @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.) $\endgroup$
    – user9072
    Commented Nov 16, 2011 at 21:55
  • 1
    $\begingroup$ 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.$ $\endgroup$
    – Charles
    Commented Nov 17, 2011 at 14:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .