1
$\begingroup$

Edit: Apologies, as mentioned in the comments I failed to notice the analytic algorithms that take $O(n^{1/2+\epsilon})$ time, so this question doesn’t make much sense. It’s possible there is a sensible question restricting to sieve-like algorithms, but I don’t know how to make that precise.

The fastest algorithms for computing $\pi(n)$ (counting primes up to $n$) appear to require $\tilde{O}(n^{2/3})$ time (ignoring logarithmic factors). For example, Deleglise and Rivat give an algorithm with complexity $O(n^{2/3}/\log^2 n)$, which is itself an improvement to several other algorithms with similar complexity. The two-thirds power lower bound seems to be because one needs to sieve up through $n^{2/3}$ and explicitly handle primes in that range to deal with inclusion/exclusion interactions of smaller factors.

Question: Is it possible to get a rigorous $\Omega(n^{2/3-\epsilon})$ lower bound for some natural black box generalization of $\pi(n)$?

For example, can we replace $\mathbb{N}$ by some larger class of black box arithmetic semigroups (monoids with a norm and a set of primes) such that similar algorithms work for counting primes and there is a matching rigorous lower bound?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Some google-fu (with the name of Andrew Odlyzko which I happened to remember) lead to this MO post mathoverflow.net/questions/53278/… , which had the following link mail-archive.com/[email protected]/msg44646.html , from which it apears that already in the late 80's there were $O(n^{1/2 + \varepsilon})$ algorithms for the prime counting function. And indeed, it is literally mentioned on the first page of the Deleglise--Rivat paper, how did you miss it? $\endgroup$
    – Aleksei Kulikov
    Commented Mar 22 at 18:51
  • $\begingroup$ Apologies, I swapped in that link after reading in more detail about some of the prior algorithms, and incorrectly though it was $O(n^{2/3})$ still based on Wikipedia not mentioning the faster algorithms in the algorithm section of en.m.wikipedia.org/wiki/Prime-counting_function. $\endgroup$
    – Geoffrey Irving
    Commented Mar 22 at 19:12
  • $\begingroup$ Indeed, the paper I read in detail was the 1985 paper which predated by two years the analytic paper you mention by the same authors. :/ $\endgroup$
    – Geoffrey Irving
    Commented Mar 22 at 19:15
  • $\begingroup$ And one would expect the analytic methods to extend similarly to other arithmetic semigroups, so likely it’s $O(n^{1/2+\epsilon})$ for those as well. So apologies for the noise. $\endgroup$
    – Geoffrey Irving
    Commented Mar 22 at 19:17

1 Answer 1

Reset to default
2
$\begingroup$

A recent preprint Computing $\pi(N)$: An elementary approach in $\tilde O(\sqrt N)$ time indeed gave a sieve-like algorithm that takes $\tilde O(\sqrt N)$ time. Their method also generalizes to a broader class of number-theoretical functions.

Improve this answer
$\endgroup$

You must log in to answer this question.

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