The parity of the prime-counting function in time $x^{o(1)}$
Source: hexagonmath.org/abs/2611.00116v1
Computing the prime-counting function $\pi(x)$ exactly takes $x^{1/2+o(1)}$ steps by the analytic method of Lagarias and Odlyzko, and to our knowledge its parity is known faster only on short intervals: Tao, Croot and Helfgott decide whether an interval of length at most $x^{1/2+c}$ near $x$ contains an odd number of primes in time $x^{1/2-c+o(1)}$. However, their identity needs the Mobius function $\mu(d)$ for all $d\le\sqrt x$, and we know of no bound of the form $x^{o(1)}$ for the parity, even conditionally. We present deterministic algorithms that output $\pi(x) \bmod 2$ and the parity…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00116
curl -X POST /api/v1/records/hexagon/2611.00116/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00116/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'