3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $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. $\endgroup$ – vrugtehagel Mar 12 '18 at 22:09
  • $\begingroup$ 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). $\endgroup$ – Erick Wong Mar 12 '18 at 23:02
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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

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.