Skip to main content

Timeline for Parity of number of primes

Current License: CC BY-SA 3.0

29 events
when toggle format what by license comment
Dec 24, 2017 at 18:49 comment added Turbo Should be with parity count.
Dec 24, 2017 at 18:39 comment added Dan Brumleve Let us continue this discussion in chat.
Dec 24, 2017 at 18:38 comment added Turbo You are emphasizing my point with cc providing ability to find an interval of odd parity in poly time. $\frac{\log\log n}{\log n}$ is also $o(1)$ and so we cannot rule out poly time prime finding algorithm with parity of parity count (however if getter parity in poly time itself needs cc the point is mute).
Dec 24, 2017 at 18:24 comment added Dan Brumleve CC does help us find an interval containing an odd number of primes in polynomial time but I can't think of what else.
Dec 24, 2017 at 18:18 comment added Dan Brumleve CC would put prime finding in P, but all we get hope to get from parity is a better exponential algorithm (the "square root barrier"), or maybe a subexponential one if the exponent can be made $o(1)$.
Dec 24, 2017 at 16:41 comment added Turbo @danbrumleve I do not know more than what the paper talks about for parity. Both CC and parity should put prime finding in P and if CC is needed to get parity then the whole approach in the paper is mute and that is one of my motivations.
Dec 24, 2017 at 14:01 comment added Dan Brumleve I think your more precise statement is correct. Note the restriction on the interval length, we'd have to call the algorithm $\sqrt{x}$ times to get $\pi{(2 \cdot x)} - \pi{(x)} ~\text{mod}~ 2$. You are also welcome to correspond with me about finding primes over email, it is one of my favorite problems.
Dec 24, 2017 at 13:32 history edited Turbo CC BY-SA 3.0
added 223 characters in body
Dec 24, 2017 at 13:20 comment added Turbo @DanBrumleve you said $c>0$ is not achieved though. Am I interpreting incorrectly?
Dec 24, 2017 at 13:05 comment added Dan Brumleve mathworld.wolfram.com/MertensFunction.html has some algorithms with similar runtime but I don't know about parity.
Dec 24, 2017 at 4:20 comment added Noam D. Elkies 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 :-)
Dec 24, 2017 at 3:07 comment added Turbo are there other arithmetic functions parity is computable?
Dec 24, 2017 at 1:58 history edited YCor
edited tags
Dec 24, 2017 at 0:35 history edited Turbo CC BY-SA 3.0
deleted 96 characters in body
Dec 24, 2017 at 0:26 history edited Turbo CC BY-SA 3.0
edited body
Dec 24, 2017 at 0:20 history undeleted Turbo
Dec 23, 2017 at 15:41 history deleted Turbo via Vote
Dec 23, 2017 at 15:29 history edited Turbo CC BY-SA 3.0
added 51 characters in body
Dec 23, 2017 at 15:25 comment added Turbo 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)'.
Dec 23, 2017 at 15:23 comment added Turbo where do you read $c>0$ is not achieved for parity?
Dec 23, 2017 at 14:38 comment added Dan Brumleve Theorem 1.2 says something close to this, but the length of the interval is restricted.
Dec 23, 2017 at 14:34 comment added Dan Brumleve 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.)
Dec 23, 2017 at 14:15 history edited Turbo CC BY-SA 3.0
deleted 33 characters in body
Dec 23, 2017 at 14:12 history undeleted Turbo
Dec 23, 2017 at 14:08 history deleted Turbo via Vote
Dec 23, 2017 at 9:40 history undeleted Turbo
Dec 23, 2017 at 9:39 history deleted Turbo via Vote
Dec 23, 2017 at 7:58 history edited Turbo CC BY-SA 3.0
added 98 characters in body
Dec 23, 2017 at 5:54 history asked Turbo CC BY-SA 3.0