MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Let $f(n, q)$ be the reciprocal proportion of naturals less than $n$ which are not divisible by any prime less than $q$. Note that $\displaystyle \lim_{q \to \infty} f(n, q) = n$, while $\displaystyle \lim_{n \to \infty} f(n, q)$ is the sum of the reciprocals of those positive integers with prime factors all less than $q$. Thus, $\displaystyle \lim_{n \to \infty} \lim_{q \to \infty} f(n, q) = \infty$, while $\displaystyle \lim_{q \to \infty} \lim_{n \to \infty} f(n, q)$ is the harmonic series.

Given that we already know the harmonic series diverges, we may conclude that these limits commute, but is there any way to reason in the opposite order? That is, is there any good (independent) reason that these limits should commute, such that we can conclude via this reasoning that the harmonic series must diverge? As a particular question along these lines, do we in fact have the more general $\displaystyle \lim_{(n, q) \to (\infty, \infty)} f(n, q) = \infty$?

Edit: Thanks to "so-called friend Don", for answering this last question (about the general limit) in the affirmative, given (essentially) the fact that $\displaystyle \lim_{q \to \infty} \lim_{n \to \infty} f(n, q) = \infty$. My main question remains whether there is any "independent" reason the two iterated limits should be equal, so that we can noncircularly derive $\displaystyle \lim_{q \to \infty} \lim_{n \to \infty} f(n, q) = \infty$ from $\displaystyle \lim_{n \to \infty} \lim_{q \to \infty} f(n, q) = \infty$.

share|cite|improve this question

I think Greg might be answering a more difficult question. Let $z(n,q)=\min\{q,\log{n}\}$. By the sieve of Eratosthenes --- basically just inclusion-exclusion --- one can show that the proportion of natural numbers in $[1,n]$ not divisible by any prime up to $z(n,q)$ is (as $n\to\infty$) asymptotically $\prod_{p \leq z(n,q)} (1-1/p)$, uniformly in $q$. Note that this proportion is an upper bound on $f(n,q)^{-1}$.

Under your conditions, $z(n,q)\to \infty$, and so the product goes to zero since the sum of the reciprocals of the primes diverges. So yes, $f(n,q) \to\infty$ whenever $q,n\to\infty$.

share|cite|improve this answer
Oh, very nice, thank you. This does settle the question about the existence of the general limit, but, alas, this argument requires that we already know $\prod_{p}(1 - 1/p) = 0$, while my motivating hope remains that there is some way to noncircularly derive this fact from $\prod_{p}(1 - 1/p) = \lim_{q \to \infty} \lim_{n \to \infty} f(n, q)^{-1}$ and $\lim_{n \to \infty}\lim_{q \to \infty} f(n, q)^{-1} = 0$. – Sridhar Ramesh May 14 '14 at 3:27

I believe it's true that the number of integers up to $n$ that are not divisible by any prime less than $q$ is always at least $$ (1+o(1)) \frac{e^\gamma}2 n \prod_{p<q} \bigg( 1-\frac1p \bigg). $$ (This should follow from results about the Buchstab function, in particular that its minimum value is $\frac12$.) In particular, when $n$ and $q$ are large enough, the proportion of such integers is at least $\frac12 \prod_{p<q} ( 1-\frac1p )$, which tends to $0$ as $q\to\infty$. So I think this is an answer to your last question. (Of course it uses the fact that the reciprocal sum of the primes diverges, which seems weird in an attempt to prove that the harmonic series diverges - there's a more direct implication...!)

share|cite|improve this answer
If I'm reading you correctly, you are saying that for sufficiently large $n$ and $q$, we have that $f(n, q)^{-1}$ is at least a quantity which tends to zero. But surely we need to show $f(n, q)^{-1}$ to be at most a quantity which tends to zero, in order to answer the last question? – Sridhar Ramesh May 14 '14 at 0:09

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.