I am self-learning An Introduction to Sieve Methods and their Applications by Alina Carmen Cojocaru & M. Ram Murty.

The authors left the proof of Proposition 9.1.1 as an exercise and I try to prove it. Here is the proposition:

$$\mathcal D=\left\{D\,:\,\mathbb N\longrightarrow\mathbb C\ \left|\ \sum_{n\leq x}|D(n)|^2=O(x(\log x)^\alpha)\ \text{for some}\ \alpha>0\right\}\right..$$

  1. If $D\in\mathcal D$ and $\theta>0$, then

$$\sum_{n\leq x}\frac{|D(n)|}{n^\theta}\ll x^{1-\theta}(\log x)^\alpha\ \ \ \ \text{for some}\ \alpha>0.$$

  1. If $D_1,D_2\in\mathcal D$, then

$$\sum_{ef\leq x}|D_1(e)D_2(f)|d(ef)\ll x(\log x)^\beta\ \ \ \ \text{for some}\ \beta>0,$$


$$\sum_{ef\leq x}|D_1(e)D_2(f)|^2d(ef)\ll x(\log x)^\gamma\ \ \ \ \text{for some}\ \gamma>0,$$

where $d(n)$ is the number of positive divisors function.

I have proved part 1 but stuck in part 2. Here is my proof for part 1:

By Cauchy-Schwarz inequality,

$$\sum_{n\leq x}|D(n)|\leq\sqrt{\left(\sum_{n\leq x}|D(n)|^2\right)\cdot\lfloor x\rfloor}\ll x(\log x)^{\alpha/2}.$$

Therefore, by partial summation,

$$\begin{aligned} \sum_{n\leq x}\frac{|D(n)|}{n^\theta}&=\frac{1}{x^\theta}\sum_{n\leq x}|D(n)|+\theta\int_1^x\left(\sum_{n\leq t}|D(n)|\right)\frac{dt}{t^{\theta+1}}\\ &\ll x^{1-\theta}(\log x)^{\alpha/2}+\theta\int_1^x\frac{(\log t)^{\alpha/2}}{t^\theta}dt\\ &\ll x^{1-\theta}(\log x)^{\alpha/2}. \end{aligned} $$

For part 2, the best bound I got is $x^{1+\epsilon}(\log x)^\beta,\ \forall\epsilon>0$, using Dirichlet's hyperbola method. I don't have any idea dealing with the function $d(n)$.

Any comment and answer is appreciated.

  • $\begingroup$ What's the precise meaning of $\ll$, here? $\endgroup$
    – FShrike
    May 25 at 20:21
  • 1
    $\begingroup$ @FShrike it’s another way to write big O notation. $$f(x) << g(x) \ <=>\ f(x) = O(g(x)).$$ $\endgroup$ May 25 at 21:32
  • 1
    $\begingroup$ @LucaArmstrong (it's \ll btw to render $\ll$) I've seen it mean different things in different contexts $\endgroup$
    – FShrike
    May 25 at 21:54

1 Answer 1


Notation) We put $\mathcal{L}=\log(x+1)$ and write $\mathcal{L}^M$ for any fixed power of $\mathcal{L}$. There may be multiple appearances of $M$ but they do not mean the same constants everytime. Let $\epsilon$ be a fixed positive number smaller than $\log 2$.

For the first estimate of $2.$, we use the following for all $D\in\mathcal{D}$: $$ \sum_{n\leq x} |D(n)|d(n) \ll x \mathcal{L}^M. $$ This follows by Cauchy-Schwarz, the left hand side of the above is $$ \ll \sqrt{ \sum_{n\leq x}|D(n)|^2 \cdot \sum_{n\leq x} d(n)^2 } $$ Then the result follows.

Now, the proof of the first estimate: By partial summation for the sum over $f$, $$ \begin{align} \sum_{ef\leq x} |D_1(e)D_2(f)|d(ef)&\leq \sum_{ef\leq x} \frac{|D_1(e)D_2(f)|d(e)d(f)x}{ef}\\ &=\sum_{e\leq x} |D_1(e)|d(e) \sum_{f\leq x/e} \frac{|D_2(f)|d(f)x}{fe}\\ &\ll \sum_{e\leq x} \frac{|D_1(e)|d(e)x}e \mathcal{L}^M. \end{align} $$ By partial summation, we have $$ \sum_{e\leq x}\frac{|D_1(e)|d(e)}e \ll \mathcal{L}^M. $$ Then by combining these estimates, we have $$ \sum_{ef\leq x} |D_1(e)D_2(f)|d(ef)\ll x\mathcal{L}^{2M} $$ as desired.

We will show that the second estimate of $2.$, does not hold, by showing a counterexample.

We say that a number is a primorial if it is of the form $\prod_{p\leq y} p$. Let $D_1=D_2=D$ be the arithmetic function defined as follows: $$ D(n)=\begin{cases}1 &\mbox{ if }n=1,\\ 0 &\mbox{ if }n \text{ is not a primorial and not }1,\\ \sqrt n &\mbox{ if }n=\prod_{p\leq y} p \text{ is a primorial and }y \text{ is a prime number}.\end{cases} $$ Then $D\in\mathcal{D}$ by $\sum_{n\leq x} D(n)^2\ll x$.

However, if $x$ is a primorial, then by the case $e=x$ and $f=1$, we have $$ \sum_{ef\leq x}|D_1(e)D_2(f)|^2d(ef) \geq D_1(x)^2D_2(1)^2d(x) $$ When $x$ is a primorial, we have $D_1(x)^2=x$ and $$ d(x)\geq x^{\frac{\log 2 -\epsilon}{\log\log x}}. $$ Thus, together with $D_2(1)=1$, the above lower bound for the sum is $$ x^{1+\frac{\log 2 -\epsilon}{\log\log x}}. $$ This lower bound is not $\ll x(\log x)^{\gamma}$ for any fixed $\gamma>0$.

  • $\begingroup$ Ah, the key here is that the second part of the second case is false! I sat down and tried to work through this problem and failed, but I didn't think to see if it was true. $\endgroup$
    – davidlowryduda
    May 26 at 11:56
  • $\begingroup$ From the first part of 2, we see that $$\sum_{e\leq x} |D_i(e)|^4\ll x(\log x)^{\alpha}$$ for some $\alpha>0$ implies the result of the second part. Then we also see this does not follow from $$\sum_{e\leq x} |D_i(e)|^2\ll x(\log x)^{\alpha}$$ This was the starting point where I started to think that the second part is false and looked for a counterexample. $\endgroup$ May 26 at 14:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .