MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Yes. About r choose (r/2). (It might even be a good estimate.) Gerhard "Ask Me About System Design" Paseman, 2012.01.23 – Gerhard Paseman Jan 24 '12 at 2:04
I would be more interested in the sum over products of last primes. Jokes aside, very bad way of stating the question... – Wadim Zudilin Jan 24 '12 at 3:09
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 – Yemon Choi Jan 24 '12 at 3:37
@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. – Greg Martin Jan 24 '12 at 8:08
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 – Gerhard Paseman Jan 24 '12 at 8:49
up vote 0 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer
IIUIC Gerhard’s argument was to apply Sperner’s theorem ( – Emil Jeřábek Jan 24 '12 at 13:31
Yes, this is Sperner's theorem. I just love the proof so much I want to spell it out every time I use it :) – Johan Wästlund Jan 24 '12 at 14:30
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 – Gerhard Paseman Jan 24 '12 at 14:58
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$. – Farzad Aryan Jan 24 '12 at 18:32
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 – Gerhard Paseman Jan 24 '12 at 18:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.