The number of divisors being less than or equal to twice the square root of a natural number

Question

Ok I have been working through my new book that arrived in the mail this week, "Problems in Analytic Number Theory" Second Edition, by M.Ram Murty.

Exercise 1.3.1 asks the reader to show that:

$$d(n) \leq 2 \sqrt{n}$$

and the solution simply states that because every divisor $\alpha$ of $n$ corresponds to a factorization $\alpha \beta=n$, and of course one of $\alpha$ or $\beta$ must be less than or equal to $\sqrt{n}$, the number of divisors must be less than or equal to $2 \sqrt{n}$.

In as much as yes I can see this to be the most simple and straight forward proof one can arrive at for this problem, there is still something that makes me feel uneasy, almost as if there is a intermediate lemma that is too obvious to the author to warrant inclusion, unfortunately, not so much is as obvious to me, so I was hoping someone could see what this is.

I just don't see how we get from knowing the elementary fact that one of the two factors of a particular factorization (ie, the product of a particular divisor and the rest ) being required to be less than or equal to $\sqrt{n}$,allows for us to make a similar conclusion concerning the total number of such factorizations.

Answer 1

For every divisor $d$, make the ordered pair $(d,\frac nd)$. The number of such ordered pairs is $d(n)$, clearly. Split them into three types, those with $d<\frac nd, d=\frac nd,d>\frac nd$. The middle group contains at most $1$ element, namely, $(\sqrt n,\sqrt n)$. The other two groups are in bijection with each other, by reversing the terms. Letting $A(n)$ be the number of elements in group $1$ we then see that:

$$d(n) = \begin{cases} 2A(n), & \text{if $n$ is not a perfect square} \\ 2A(n)+1 , & \text{if $n$ is a perfect square} \end{cases}$$

How big is $A(n)$?

Well, the smaller member of any ordered pair other than $(\sqrt n,\sqrt n)$ must be less than $\sqrt n$, clearly (otherwise both members would be $>\sqrt n$ hence the product would be greater than $n$). Thus $A(n)<\sqrt n$. It follows that

$$d(n) < \begin{cases} 2\sqrt n, & \text{if $n$ is not a perfect square} \\ 2\sqrt n+1 , & \text{if $n$ is a perfect square} \end{cases}$$

This is very close to what you wanted, but not exact. Of course, we can tighten our estimates. We distinguish two cases:

If $n$ is not a perfect square. In that case we already have $d(n)<2\sqrt n$ so we are done.

If $n$ is a perfect square then the fact that $2\sqrt n+1$ and $d(n)$ are both integers tells us that $$d(n)<2\sqrt n+1\implies d(n)≤2\sqrt n$$

Answer 2

List all the divisors of $n$:

$$d_1, d_2, \ldots, d_k.$$

Note that $k = \tau(n)$. These divisors come in pairs. For each $d_i$ that divides $n$, there is a $d_j$ such that $d_id_j = n.$ By your little fact, one of these hast to be less than or equal to $\sqrt{n}.$ That means half of the divisors are less than or equal to $\sqrt{n}$. There are only $\sqrt{n}$ possible values for $d_i$, then. And hence only $\sqrt{n}$ possible values for $d_j$. In total that's at most $2\sqrt{n}$ divisors.

When you see it, you'll go "Doh!"

Answer 3

You've already observed that there is a pairing between divisors greater than $\sqrt{n}$ and those less than $\sqrt{n}$. To get that this pairing, you need the fundamental theorem of arithmetic, i.e., there's no way to use the same factor twice.

Since every pair has a distinct factor less than or equal to $\sqrt{n}$ and there are $\sqrt{n}$ positive numbers less than or equal to $\sqrt{n}$, this gives the desired count.