Timeline for Estimate about primes
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 25, 2012 at 1:31 | comment | added | Gerhard Paseman | Then one can get $O(X^{1+\epsilon})$, although I won't begrudge you the aadditional $\sqrt{\log X}}$ savings from the other argument if you really want it. Gerhard "Ask Me About System Design" Paseman, 2012.01.24 | |
| Jan 24, 2012 at 23:59 | comment | added | Farzad Aryan | $B$ is a subset of $[X^2, 4X^{2}]$. The size of $B$ is very small, smaller than $X^{\epsilon}$. | |
| Jan 24, 2012 at 23:04 | comment | added | Gerhard Paseman | In fact, I think 2.8 X^2 is near optimal, and I will be happy to show that to you, although you might prefer to find it yourself. Of course, if B has special characteristics, one might do better still. Gerhard "Ask Me About System Design" Paseman, 2012.01.24 | |
| Jan 24, 2012 at 22:51 | comment | added | Gerhard Paseman | Indeed, I think the new sum has a trivial upperbound of 4X^2, abd that can probably be improved upon. Gerhard "Ask Me About System Design" Paseman, 2012.01.24 | |
| Jan 24, 2012 at 22:44 | comment | added | Gerhard Paseman | In which case I think you can get much better bounds than the worst case. I suspect an upper bound for this new sum is X^2. I will think about it. Gerhard "Ask Me About System Design" Paseman, 2012.01.24 | |
| Jan 24, 2012 at 22:13 | comment | added | Farzad Aryan | we were interested to have a bound on $$\sum_{n \in B} \sum_{ d|n \; X<d<2X} 1 $$ where B is a subset of $[x^2,4X^2]$. so the worst case in the sum is when $n$ has large number of prime factors. | |
| Jan 24, 2012 at 18:43 | comment | added | Gerhard Paseman | Arya, I would like to know the source and the motivation for this problem. If you provide that, I would be willing to produce some non-rigorous algebraic/analytic justification of the bounds. Gerhard "Ask Me About System Design" Paseman, 2012.01.24 | |
| Jan 24, 2012 at 18:32 | comment | added | Farzad Aryan | Guys thank yo very much for comments, I was not convinced by probabilistic method because its not always a proof. For example the probability of a number be co-prime to $p$ is (1-1/p) ans so the probability of a number be co-prime to set of primes is $\prod_{p \in P} (1-1/p)$. If we use this argument to count the prime numbers less than $X$, we have $\pi(X)= \prod_{p<\sqrt(X)} (1-1/p)X$ which is wrong by PNT and Mertens' theorems. Furthermore by the same argument the number less than $X$ which is co-prime to product of the all prime less than $X$ is $\prod_{p<X} (1-1/p)X$ real value is $0$. | |
| Jan 24, 2012 at 15:38 | history | edited | Johan Wästlund | CC BY-SA 3.0 |
added 291 characters in body
|
| Jan 24, 2012 at 14:58 | comment | added | Gerhard Paseman | I made my comments a bit cryptic so as to tease out of the original poster some motivation. I like your answer, but I and others would be enlightened by a parenthetical phrase such as "(imagine walking from bottom to top along this randomly chosen chain in the Boolean lattice, hoping to meet this divisor)" . It took me longer to understand your argument without the phrase than it did to come up with the initial estimate. I like the probabilistic refinement. The estimate feels right to me. Gerhard "Don't You Feel Mathematics Too?"I Paseman, 2012.01.24 | |
| Jan 24, 2012 at 14:30 | comment | added | Johan Wästlund | Yes, this is Sperner's theorem. I just love the proof so much I want to spell it out every time I use it :) | |
| Jan 24, 2012 at 13:31 | comment | added | Emil Jeřábek | IIUIC Gerhard’s argument was to apply Sperner’s theorem (en.wikipedia.org/wiki/Sperner%27s_theorem). | |
| Jan 24, 2012 at 12:55 | history | answered | Johan Wästlund | CC BY-SA 3.0 |