Understanding Lemma 2.1 in P. Erdos and I. Z. Ruzsa's "On the Small Sieve. I, Sifting by Primes.

Question

I am reading a paper of P. Erdos and I. Z. Ruzsa and I had a question on Lemma 2.1.

Let $A$ be a set of natural numbers.

Let $B$ denote the set of natural numbers divisible by no element of $A$.

Here is Lemma 2.1:

For all $y$ we have:

$$\sum_{b \le y \text{ and } b \in B}1/b \ge \prod_{a \in A}(1 - 1/a)\log(y+1)$$

I am lost at how this relates to the argument which consists of the following points:

• Every number has (one or more) decompositions of the form: $$a_l^{a_l}\dots a_k^{a_k}b,\,\,\,\,b\in B,\,\,\,\,a_i\in A$$

• Hence: $$\sum_{n \le y}1/n \le \sum_{b \le y \text{ and } b \in B}1/b\prod_{a\in A}(1 + a^{-1} + a^{-2}+\dots)$$

• which immediately yields Lemma 2.1

• Note: As a by-product, this gives us a proof for the Heilbron-Rohrbach Inequality:

$$\Delta(A) = \lim_{x \to \infty}\frac{F(x,A)}{x} \ge \prod_{a \in A}(1 - 1/a)$$

where $F(x,A)$ denotes the number of natural numbers $n \le x$ divisible by no element of $A$.

I am not clear how the argument leads to the proof of the lemma. I am unclear how the argument leads to the Heilbronn-Rohrbach Inequality.

Any explanation or hint would be highly appreciated.

Answer 1

The inequality $$ \sum_{n \le y}1/n \le \sum_{b \le y \text{ and } b \in B}1/b\prod_{a\in A}(1 + a^{-1} + a^{-2}+\dots) $$ follows from admitting the expression for $n$ as $a_l^{a_l}\dots a_k^{e_k}b,\,\,\,\,b\in B,\,\,\,\,a_i\in A$ for any possible $a_i \in A$, $e_i$'s and $b\in B$. Thus, possibly over-counting happens, but the inequality is true. One way to understand the right side is to convert the sum over those expression into a product.

A few things that you need to know are $$ \log(y+1)\leq \sum_{n\leq y} \frac1n $$ This can be shown by comparing the graphs of $f(x) = \frac1{x+1}$ and $g(x) = \frac1{\lfloor x+1 \rfloor}$. Since we have $f(x)\leq g(x)$ for $0\leq x \leq y$, we obtain the result by integration: $$ \log(y+1)=\int_0^y \frac1{x+1}dx \leq \int_0^y \frac1{\lfloor x+1 \rfloor} dx = \sum_{n\leq y} \frac1n $$ with the last equality is true for any positive integer $y$.

Secondly, by the geometric series $$ \frac1{1-r}=1+r+r^2+\cdots , \ \ \ |r|<1, $$ we have $$ \prod_{a\in A} (1+a^{-1}+a^{-2}+\cdots) = \prod_{a\in A} \frac1{1-\frac1a}=\left(\prod_{a\in A}\left(1-\frac1a\right)\right)^{-1}. $$

Then we have

$$ \log(y+1)\leq \sum_{b\leq y \ \mathrm{and} \ b\in B} 1/b \prod_{a\in A} \left(1-\frac1a\right)^{-1}. $$ This yields the lemma: $$ \sum_{b\leq y \ \mathrm{and} \ b\in B} 1/b \geq \prod_{a\in A}\left(1-\frac1a\right) \log(y+1).$$

For Heilbron-Rohrbach, assume the existence of $\Delta(A)$. Then for any $a\in A$, $e\geq 1$, we have $$ \lim_{x\rightarrow\infty}\frac{F(x/a^e, A)}{x/a^e} = \Delta(A), $$ since $x/a^e\rightarrow\infty$ as $x\rightarrow\infty$. Then we set up the counting as below: with $a_i\in A$, $e_i\geq 1$, $b\in B$. For any $\epsilon>0$ and sufficiently large $x$, we have $$ \sum_{n\leq x} 1 \leq \sum_{\prod a_i^{e_i} b \leq x} 1=\sum_{a_i, e_i} F\left(\frac x{\prod a_i^{e_i}},A\right)\leq (\Delta(A)+\epsilon)\sum_{a_i,e_i} \frac x{\prod a_i^{e_i}} $$ The last sum is $x\prod_{a\in A}(1+a^{-1}+a^{-2}+\cdots)$. As before, this is $x\prod_{a\in A} (1-1/a)^{-1}$. Then the result follows by taking $\epsilon\rightarrow 0+$.

Answer 2

For proving this you really need :

• $1+a^{-1}+a^{-2}+\ldots = \frac{1}{1-1/a} $.

• $$\prod_{a \in A} (1+a^{-1}+a^{-2}+\ldots) = \sum_{c \in E^A} c^{-1}$$ where $E^A$ is the set whose elements are of the form $a_l^{e_l}\dots a_k^{e_k}$. If $A$ contains $2,4,8$ then $4$ has $4$ different factorization, in that case repeat it $4$ times in $E^A$.

• $\sum_{n=1}^N n^{-1} \ge \int_1^N \frac{dx}{x} = \log(N)$