# Showing $d(ab)\leq d(a)d(b)$ for all integers $a$ and $b$.

In this question someone asked to prove that $$\sum_{n\leq x}d^2(n)=O(x\log^3 x)$$ where $d(n)$ is the divisor function: $d(n)=\sigma_0(n)=\sum_{a\mid n}1$ using $$\sum_{n\leq x}d(n)=x\log x+(2\gamma -1)x+O(\sqrt x).$$

I will post the chosen answer to the post by Sean Eberhard:

"Here is a different argument. Note that $d(ab)\leq d(a)d(b)$ for all integers $a$ and $b$. We thus have

$$\sum_{n\leq x} d(n)^2 = \sum_{ab\leq x} d(ab) \leq \sum_{ab\leq x} d(a)d(b) = \sum_{a\leq x} d(a) \sum_{b\leq x/a} d(b) \leq 2\sum_{a\leq x} d(a) {x\over a} \log x,$$ where in the final inequality I used your bound on $\sum_{n\leq x} d(n)$. Now note $$\sum_{a\leq x} {d(a)\over a} = \sum_{cd\leq x} {1\over cd} \leq \sum_{c\leq x}\sum_{d\leq x} {1\over cd} \leq (2\log x)^2."$$

My question pertains to his statement "Note that $d(ab)\leq d(a)d(b)$ for all integers $a$ and $b$." How can we prove this inequality? I feel that I am missing something about the proof which is not allowing me to conclude the result, I will post my attempt. Suppose $m$ and $n$ are coprime. Every divisor $d$ of $mn$ is uniquely of the form $d_1d_2$ with $d_1 | m$ and $d_2 | n$. So, the number of divisors of $mn$ is equal to the number of divisors of $m$ multiplied by the number of divisors of $n$, or equivalently $d (mn) = d (m) d (n)$. (I'm not sure how to deal with the case where $m$ and $n$ are not coprime to completely prove the statement for $\leq$).

• $d(ab)\leq d(a)d(b)$ holds for all $a,b$, not necessarily only for the ones where they are coprime. Indeed, when they are, equality holds. – vrugtehagel Mar 12 '18 at 22:09
• The critical observation is that every divisor of $ab$ can be written as a product of a divisor of $a$ and a divisor of $b$ (possibly in more than one way, but definitely in at least one way). – Erick Wong Mar 12 '18 at 23:02

This follows easily from the fact that every divisor of $ab$ can be expressed as a product of a divisor of $a$ and a divisor of $b$. The product does not have to be unique (and in fact is not unique in general unless $(a,b)=1$), but this establishes a surjection from the set of pairs of divisors of $a$ and $b$ onto the set of divisors of $ab$.

To see this fact, consider any $m \mid ab$ and take $x = (a,m), y = \frac{m}{x}$. Clearly $x,y$ are integers and $xy = m$, so it suffices to show that $x\mid a$ and $y \mid b$. The first of these is immediate from the definition of $x$. For the second, note that $m \mid ab$ implies $y \mid \frac{a}{x} b$, and that $\frac{a}{x}$ is an integer relatively prime to $y$ (again by definition of $x$). So we can eliminate the factor of $\frac{a}{x}$ on the right to obtain $y \mid b$.

$$\sum_{n\geq 1}\frac{d(n)^2}{n^s}=\prod_{p}\left(1+\sum_{k\geq 1}\frac{(k+1)^2}{p^{ks}}\right)=\prod_{p}\frac{(p^{2s}-1)p^{2s}}{(p^s-1)^4}=\frac{\zeta(s)^4}{\zeta(2s)}$$ holds for any $s$ such that $\text{Re}(s)>1$. The RHS has a pole of order four with residue $\frac{6}{\pi^2}$ at $s=1$, hence the statement can also be deduced from the Hardy-Littlewood tauberian theorem.

For $a\in \Bbb N$ let $d^+(a)$ be the number of positive divisors of $a.$

For $a,b\in \Bbb N$ there exists a finite non-empty set $M$ of primes such that $a=\prod_{p\in M}p^{A(p)}$ and $b=\prod_{p\in M}p^{B(p)}$ where each $A(p)$ and each $B(p)$ belongs to $\Bbb N\cup \{0\}.$

So $ab=\prod_{p\in M}p^{A(p)+B(p)}.$

We have $d^+(a)=\prod_{p\in M}(1+A(p))\;$ and $d^+(b)=\prod_{p\in M}(1+B(p)).$ So we have $$d^+(a)d^+(b)=\prod_{p\in M}(1+A(p))(1+B(p))=\prod_{p\in M}(1+A(p)+b(p)+A(p)B(p))$$ and we have $$d^+(ab)=\prod_{p\in M}(1+A(p)+B(p)).$$ Since $1+A(p)+B(p)+A(p)B(p)\geq 1+A(p)+B(p)>0$ for every $p\in M,$ we have $$d^+(a)d^+(b)\geq d^+(ab)$$ with equality iff $\gcd (a,b)=1.$

• The Q refers to integers $a,b$. For $0\ne a\in \Bbb Z$ the number of integer divisors of $a$ is $2d^+(|a|).$ – DanielWainfleet Mar 13 '18 at 2:52