Iwaniec & Kowalski partial sums of multiplicative functions

Question

In their famous book Analytic Number Theory, Iwaniec and Kowalski include a section (1.6) on sums of multiplicative functions. The text seems to me unclear (or even wrong?) at some points. I would like some help to clarify the following points below.

For a multiplicative function $f$ and a prime $p$ they define $$\sigma_p(f)=\sum_{\nu=0}^\infty f(p^\nu)p^{-\nu}\text{.}$$ Moreover $\mathcal{M}_f(x)$ denotes the partial sum $\sum_{n\leq x}f(n)$.

1. After devising an upper bound (1.79) for $\mathcal{M}_f(x)$ in terms of the $\sigma_p$'s, they attempt to apply it to the function $f(m)=\tau_k(m)^\ell$, where $\tau_k(m)$ is the number of ways to write $m$ as the product of $k$ positive integers (so that $\tau_2$ is the usual divisor counting function.) In order to do this, they state the bound $$\sigma_f(p)\leq\left(1+\frac{1}{p}\right)^{k^\ell}\left(1+\frac{1}{p^2}\right)^c$$ where $c=c(k,\ell)$ is a positive constant. Where does this come from?
2. A bit later in the text, they devise a strategy to obtain an upper bound for $\mathcal{M}_f(x)$ when $f$ is non-negative and "completely sub-multiplicative", meaning that $f(mn)\leq f(m)f(n)$ for any $m,n\geq1$. They then apply the obtained bound to the case where $f$ is the characteristic function of the sums of two squares. However, this function is not completely sub-multiplicative! Indeed, $f(3)=0$, but $f(9)=1>f(3)^2$. Is this a clear mistake in the text or am I missing something?

Thanks in advance for any help.

Answer 1

For your second question, I think you're correct in noting that they are incorrectly applying their result. I'm sure some sort of result for the sum of squares characteristic function holds, but it does not follow from their analysis in that section (see Ofir's answer for a reference on this problem).

To answer your first question, we can proceed by induction on $k$ when $\ell=1$, and then the result will follow for all $\ell \geq 1$ by a simple trick. For $k=1$, we have $$ \sum_{\nu=0}^\infty \frac{\tau_1(p^\nu)}{p^\nu} = \sum_{\nu=0}^\infty \frac{1}{p^\nu} = \left(1-\frac{1}{p}\right)^{-1} \leq \left(1+\frac{1}{p}\right)\left(1+\frac{1}{p^2}\right)^2. $$ The last inequality follows from $$ \begin{aligned} \left(1-\frac{1}{p}\right)^{-1} &= \left(1+\frac{1}{p}\right)\left(1-\frac{1}{p^2}\right)^{-1} \\ &= \left(1+\frac{1}{p}\right)\left(1+\frac{1}{p^2}\right) \left(1-\frac{1}{p^4}\right)^{-1} \\ &\leq \left(1+\frac{1}{p}\right)\left(1+\frac{1}{p^2}\right)^2, \end{aligned} $$ since $$ \left(1-\frac{1}{p^4}\right)^{-1} = 1 + \frac{1}{p^4-1} \leq 1 + \frac{1}{p^2} $$ because $p\geq 2$.

Suppose now that $$ \tag{1} \sum_{\nu=0}^\infty \frac{\tau_{k}(p^\nu)}{p^\nu} \leq \left(1+\frac{1}{p}\right)^{k} \left(1+\frac{1}{p^2}\right)^{2k} $$ For some $k\geq 1$. Then since $\tau_{k+1}(n) = \sum_{d\mid n} \tau_k(n)$, we have $$ \begin{aligned} \sum_{\nu=0}^\infty \frac{\tau_{k+1}(p^\nu)}{p^\nu} = \sum_{\nu=0}^\infty \sum_{r=0}^\nu \frac{\tau_k(p^r)}{p^r p^{v-r}} = \sum_{r=0}^{\infty} \frac{\tau_k(p^r)}{p^r} \sum_{\nu\geq r} \frac{1}{p^{\nu-r}} = \left(1-\frac{1}{p}\right)^{-1}\sum_{r=0}^{\infty} \frac{\tau_k(p^r)}{p^r}. \end{aligned} $$ By the induction hypothesis and our previous calculation, we thus have $$ \sum_{\nu=0}^\infty \frac{\tau_{k+1}(p^\nu)}{p^\nu} \leq \left(1+\frac{1}{p}\right)^{k+1} \left(1+\frac{1}{p^2}\right)^{2(k+1)}. $$ Thus (1) holds for all $k\geq 1$. The case $\ell > 1$ follows from the inequality $$ \tag{2} \tau_{k}(n)^\ell \leq \tau_{k^\ell}(n). $$ (If there is a proof of this inequality elsewhere, someone please leave a comment and I'll omit this part and link to a proof). By multiplicativity, it suffices to prove this for $n=p^\nu$. By a simple combinatorial argument, we have $$ \tau_{k}(p^\nu) = \binom{\nu+k-1}{k-1}, $$ so we need to show that $$ \tag{3} \binom{\nu+k-1}{k-1}^\ell \leq \binom{\nu+k^\ell-1}{k^\ell-1} $$ for all $\nu,k,\ell\geq 1$. After writing the binomial in terms of factorials, this is equivalent to showing $$ \prod_{r=0}^{\nu-1} \left(\frac{k+r}{r+1}\right)^\ell \leq \prod_{r=0}^{\nu-1} \frac{k^\ell+r}{r+1}, $$ which is equivalent to $$ \prod_{r=0}^{\nu-1} \frac{(k+r)^\ell}{k^\ell+r} \leq \prod_{r=0}^{\nu-1} (r+1)^{\ell-1}. $$ This follows from the fact that the quotients on the left decrease with $k$ for each $r$ and $\ell$, since $$ \frac{\partial}{\partial k} \left[ \frac{(k+r)^\ell}{k^\ell+r} \right] = -\frac{\ell r \left(k^\ell-k\right) (k+r)^{\ell-1}}{k \left(k^\ell+r\right)^2}, $$ which is negative if $k > 1$. Thus (2) holds for all $n$, and the desired result follows with $c(k,\ell) = 2k^\ell$.

Answer 2

Joshua gave nice argument, let me provide my perspective on 1, with several arguments. The bottom line is that the constant $k^{\ell}$ comes from $f(1)=k^{\ell}$, and that very little information on $f$ is needed in order to derive this bound.

Claim 1: Let $F(x) = \sum_{\nu} a_{\nu} x^{\nu} = 1+a_{1}x+\ldots$ be a power series with radius of convergence $r>1/2$. Then $$F(1/p) \le \left(1+\frac{1}{p}\right)^{a_1} \left(1+\frac{1}{p^2}\right)^{C}$$ for large enough $C$ depending on $F$.

Proof: Consider $$G(x) = \frac{F(x)(1+x)^{-a_1}-1}{x^2}.$$ It is analytic in $|x|<\min\{r,1\}$. Letting $C= \max\{1 , \max_{[0,1/2]}|G(x)|\}$ we find that $$F(x) = (1+x)^{a_1}(x^2 G(x)+1) \le (1+x)^{a_1}(1+Cx^2) \le (1+x)^{a_1}(1+x^2)^C$$ for $x \in [0,1/2]$. We now specialize to $x=1/p$. $\blacksquare$

Just apply the claim with $a_{\nu} = f(p^{\nu})$. In your case, however, there is much more structure. For instance, $\sigma_p(f)$ is a rational function of $1/p$, due to the following.

Claim 2: For a non-zero polynomial $P$ we have that $(\sum_n P(n) x^n )(1-x)^{\deg P +1}$ is a polynomial in $x$.

Proof: By linearity it suffices to consider $P_d(t)=\binom{t+d}{t}$ in which case $(\sum_n P_d(n) x^n) (1-x)^{d+1} \equiv 1$ by the binomial series.

This does not directly help us find an explicit value of $C$. Here is a strategy to get hold on such $C$, in the spirit of Joshua's argument.

Claim 3: $\binom{n+k-1}{n}^{\ell} \le \binom{n+k^{\ell}-1}{n}$. Proof I: Since $\binom{a+b}{a} = \prod_{i=1}^{a} \left(1+\frac{b}{i}\right)$, the inequality can be written as $\prod_{i=1}^{n} \left(1+\frac{k-1}{i}\right)^{\ell} \le \prod_{i=1}^{n} \left(1+\frac{k^{\ell}-1}{i}\right)$. It suffices to show $\left(1+\frac{k-1}{i}\right)^{\ell} \le 1+\frac{k^{\ell}-1}{i}$ for each $i$. This follows from Hölder: if $X$ is a random variable assuming the values $1$ with probability $1-1/i$ and $k$ with probability $1/i$, the inequality just says $(\mathbb{E}X)^{\ell} \le \mathbb{E}(X^{\ell})$. Proof II: We can deduce the claim from a repeated application of the inequality $\binom{n+k_1-1}{n}\binom{n+k_2-1}{n}\le \binom{n+k_1 k_2-1}{n}$. This has a combinatorial interpretation (see Max's comment to this answer).

Claim 4: For all $0\le x \le 1/2$ we have $(1-x)^{-A} \le (1+x)^{A} (1+x^2)^C$ for $C \ge \max\{-A,5A/3\}$. Proof: The inequality simplifies as $(1-x^2)^{A}(1+x^2)^C \ge 1$, or $f(t)=A\log(1-t)+C\log(1+t) \ge 0$ where $t \in I:=[0,1/4]$. Note $f(0)=0$ and that $f$ increases in $I$ if $C$ is large enough, namely $f'=-\frac{A}{1-t}+\frac{C}{1+t} = \frac{C-A-t(A+C)}{1-t^2} \ge 0$ for $t \le (C-A)/(C+A)$, which is $\ge 1/4$ for $C \ge \max\{-A,5A/3\}$.

By Claim 3 and the binomial series, $\sigma_p(f) = \sum_{n \ge 0}\binom{n+k-1}{n}^{\ell} p^{-n} \le \sum_{n \ge 0}\binom{n+k^{\ell}-1}{n} p^{-n} = \sum_{n \ge 0}\binom{n+k^{\ell}-1}{k^{\ell}-1} p^{-n} = (1-1/p)^{-k^{\ell}}$. This is small enough by Claim 4 with $x=1/p$, and we can take $c=\frac{5}{3}k^{\ell}$. $\blacksquare$

---

Regarding question 2: I do not know what the authors had in mind. I do suggest reading Selberg's elementary, and not sufficiently well known, for $\sum_{n \le x} \alpha(n) \sim Cx/\sqrt{\log x}$ where $\alpha$ is the indicator function of integers divisible only by primes of the form $4k+1$. This is essentially the claim you need. It is proved in 'Lectures on Sieves' in his collected papers, second volume, pages 183-185.