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.

  • $\begingroup$ for 2, idk what page you're referring to, but maybe 0 is not a square for that purpose $\endgroup$ Oct 13 at 0:17
  • $\begingroup$ @mathworker21 That's not going to work, for example $3$ and $6$ can't be expressed as sums of two squares but $18 =3^2 + 3^2 $ can. $\endgroup$
    – Will Sawin
    Oct 13 at 0:33
  • 2
    $\begingroup$ Perhaps the right argument with the sums-of-squares function is to first apply this to the characteristic function of squarefree sums of two squares and then use the fact that, writing $n =m ^2 s$ with $s$ squarefree, $n$ is a sum of two squares if and only if $s$ is. $\endgroup$
    – Will Sawin
    Oct 13 at 23:46

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$.


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.

  • 1
    $\begingroup$ The probabilistic interpretation is very instructive and, in my opinion, a bit more elegant than my "brute force" approach. Very nice answer. $\endgroup$ Oct 14 at 15:53
  • $\begingroup$ Thanks Joshua, although morally this is the same argument as yours, up to details. By thw way, I am also completely confident in the existence of a combinatorial argument for $\binom{n+a-1}{n}\binom{n+b-1}{n} \le \binom{n+ab-1}{n}$, but can't find it. $\endgroup$ Oct 14 at 16:04
  • 1
    $\begingroup$ Let $f$ be a bijective mapping of $[a]\times [b]$ to $[ab]$. Then we can define an injective mapping of the pairs of $n$-combinations with repetitions chosen from $[a]$ and $[b]$ to those chosen from $[ab]$: simply sort the two $n$-combinations and apply $f$ to the corresponding pairs of elements in them. This proves the required inequality. $\endgroup$ Oct 14 at 17:02
  • $\begingroup$ @MaxAlekseyev Thanks, I refer to your argument in the answer now. $\endgroup$ Oct 14 at 17:07
  • $\begingroup$ @JoshuaStucky I just realized that if we don't want a concrete $C$ there is a really easy argument. $\endgroup$ Oct 14 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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