Can anyone give an estimate (upper bound or lower bound) for the number of divisors $d\mid P_r$ such that $\frac{\sqrt{P_r}}{2}< d < \sqrt{P_r}$, where $P_r$ is the product of the $r$ smallest primes?
$\begingroup$
$\endgroup$
6
-
2$\begingroup$ Yes. About r choose (r/2). (It might even be a good estimate.) Gerhard "Ask Me About System Design" Paseman, 2012.01.23 $\endgroup$– Gerhard PasemanCommented Jan 24, 2012 at 2:04
-
$\begingroup$ I would be more interested in the sum over products of last primes. Jokes aside, very bad way of stating the question... $\endgroup$– Wadim ZudilinCommented Jan 24, 2012 at 3:09
-
1$\begingroup$ The question might be better received if it gave more context, more illustration of what the OP has already tried or learned, and followed suggestions in mathoverflow.net/howtoask $\endgroup$– Yemon ChoiCommented Jan 24, 2012 at 3:37
-
$\begingroup$ @Gerhard: I don't immediately see why $r$ choose $r/2$ is either an upper bound or a lower bound for the quantity in question. $\endgroup$– Greg MartinCommented Jan 24, 2012 at 8:08
-
2$\begingroup$ I could have messed up. I view the problem as specifying a certain antichain in a Boolean lattice of r atoms. I think r choose r/2 is an upper bound, and for large r the lower bound might be something like r choose r/3, but I don't have a proof. What is your take on it? Gerhard "Ask Me About System Design" Paseman, 2012.01.24 $\endgroup$– Gerhard PasemanCommented Jan 24, 2012 at 8:49
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
Let $x$ be such that $\pi(x) \sim \frac{x}{\log x} \sim r$, so that $P_r$ is about $e^x$. Let $\Psi(x,y)$ be the de Bruijn, function, the number of $y$-smooth numbers less than or equal to $x$. So a crude upper bound for the quantity in question is about
$$ \Psi(e^{x/2},x) - \Psi(e^{x/2}/2,x). $$
Out of these numbers (call the set of these numbers $X$) we want to get the squarefree ones. The proportion of squarefree numbers in all the integers is $1/\zeta(2)$ so it is tempting to use $|X|/\zeta(2)$ or $|X|\prod_{p\leq x}\left(1-1/p^2\right)$ as a crude first approximation, though I'm not sure how far off it is. The thing is that one is dealing here with only $x$-smooth numbers. Perhaps for each $p \leq z \ll x$ for suitable $z$ one can estimate the size of the subset of $X$ that is in $p^2\mathbb{Z}$, then use a simple inclusion-exclusion sieve to estimate the size of the subset of $X$ of numbers that, if they are divisible by prime squares $p^2$, must have $z \leq p\leq x$. Or, use more powerful sieve methods. (Guessing that sieving for squarefree numbers should be very similar to sieving for primes.)
Good references:
A. Granville, Smooth numbers: computational number theory and beyond, Algorithmic Number Theory, MSRI Publications, Volume 44, 2008.
T. Tao's blog, 254B, Notes 7: Sieving and expanders.
$\begingroup$
$\endgroup$
11
Gerhard did not mess up. $\binom{r}{r/2}$ (or more precisely, the central binomial coefficient, but say $r$ is even) is an upper bound. If we shuffle the primes and multiply them together in random order, then the probability that we hit a given product of $k$ primes is $1/\binom{r}{k}$ (since it requires the first $k$ primes to be a specified set), and therefore at least $$\frac1{\binom{r}{r/2}}.$$ It follows that the probability that some partial product is in the given interval is at least $N/\binom{r}{r/2}$, where $N$ is the number of divisors in the given interval (since we never stay in such a short interval).
Being a probability, this number is at most 1, which gives Gerhard's bound. My guess is that in reality that probability is more like $\log 2/\log r$, since if instead we add up the logarithms of the primes, we move in steps of size roughly $\log (r\log r) \sim \log r$, and we look for the probability of hitting an interval of length $\log 2$. This would suggest that $$N\approx \frac{\log 2}{\log r}\cdot \binom{r}{r/2}.$$ Edit: I'm fairly convinced that $N$ is of order $\binom{r}{r/2}/\log r$, but I'm not so sure about the constant $\log 2$, though it seems it gives asymptotically an upper bound.
answered Jan 24, 2012 at 12:55
-
$\begingroup$ IIUIC Gerhard’s argument was to apply Sperner’s theorem (en.wikipedia.org/wiki/Sperner%27s_theorem). $\endgroup$ Commented Jan 24, 2012 at 13:31
-
$\begingroup$ Yes, this is Sperner's theorem. I just love the proof so much I want to spell it out every time I use it :) $\endgroup$ Commented Jan 24, 2012 at 14:30
-
$\begingroup$ 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 $\endgroup$ Commented Jan 24, 2012 at 14:58
-
$\begingroup$ 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$. $\endgroup$ Commented Jan 24, 2012 at 18:32
-
$\begingroup$ 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 $\endgroup$ Commented Jan 24, 2012 at 18:43