4
$\begingroup$

In https://arxiv.org/abs/1009.3956 is it shown there is a $c>0$ such that $\pi(x)\bmod2$ can be computed in $o(x^{\frac12})$ time (more precisely number of primes $\bmod 2$ for an interval of length at most $O(x^{\frac12+c})$ in $[x,2x]$ can be computed in time $O(x^{\frac12-c})$)?

If so is there a good estimate known for $c$ and is $\frac12-c=o(1)$ believed achievable?

We know that Cramer's conjecture detects primes in $[x,2x]$ in $P$.

Assuming Cramer's or Riemann's conjecture is $\frac12-c=o(1)$ believed achievable for $\pi(x)\bmod2$?

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ I believe this is not actually established (the paper discusses possible strategies for achieving $c \ge 0$) and all that is proven is the bound $O(x^{\frac{1}{2}+o(1)})$. (And this isn't enough to deterministically find a prime in $O(x^{\frac{1}{2}+o(1)})$ time since we still have to guess a number with odd parity. To my knowledge these problems are still open.) $\endgroup$
    – Dan Brumleve
    Commented Dec 23, 2017 at 14:34
  • $\begingroup$ Theorem 1.2 says something close to this, but the length of the interval is restricted. $\endgroup$
    – Dan Brumleve
    Commented Dec 23, 2017 at 14:38
  • $\begingroup$ where do you read $c>0$ is not achieved for parity? $\endgroup$
    – Turbo
    Commented Dec 23, 2017 at 15:23
  • 2
    $\begingroup$ It says ' While this strategy has not been fully implemented, it can be used to establish partial results'and continues 'it can be used to establish partial results, such as being able to determine the \emph{parity} of the number of primes in a given interval in [N,2N] in time O(N1/2−c)'. $\endgroup$
    – Turbo
    Commented Dec 23, 2017 at 15:25
  • 4
    $\begingroup$ the parity of the number of divisors $d(n) = \sigma_0(n)$ is very easy to compute [cf. "locker problem"] and to sum over an interval :-) $\endgroup$
    – Noam D. Elkies
    Commented Dec 24, 2017 at 4:20

0

Reset to default

You must log in to answer this question.