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 |