Assuming $N$ is not a perfect square and that $D(k)$ is the set of positive divisors of $k$, then $|D(N)\cap [0, \sqrt{N}]| = |D(N)\cap [\sqrt{N},N]|$

Question

I never did this here, but this is not actually a question. I just found this fact by myself and I had to share it. It's such an elegant piece of observation, and yet so simple. I do want to know if this proof is right, though. So yeah, that might be a question.

So let's bring the statement again:

Assuming $N\in\mathbb{Z}^+$ is not a perfect square and that $D(k)$ is the set of positive divisors of $k\in\mathbb{Z}^+$, then $$|D(N)\cap [0, \sqrt{N}]| = |D(N)\cap [\sqrt{N},N]|$$ where $|A|$ denotes the number of elements of $A$.

A way I tried to prove this is by taking $n_1\in[0,\sqrt{N}]$ and $n_2\in[\sqrt{N},N]$ divisors of $N$, being $n_1, n_2\in\mathbb{Z}^+$, with $n_1\cdot n_2 = N$. Since $N$ is not a perfect square we know $\sqrt{N}$ is irrational, thus $n_1\neq n_2$ (otherwise $|D(N)|$ would be odd). Notice also that $D_1 = D(N)\cap [0, \sqrt{N}]$ and $D_2 = D(N)\cap [\sqrt{N},N]|$ are partitions of $D(N)$ (since $\sqrt{N}\not\in\mathbb{Z}$). This way $$|D_1| + |D_2| = |D(N)|.$$

We know that $n_1 < \sqrt{N}$. But we also know that $n_1 = \frac{N}{n_2}$. Thus:

\begin{align*} n_1 &< \sqrt{N}\\ \frac{N}{n_2} &< \sqrt{N}\\ n_2 &>\sqrt{N}. \end{align*}

This way, we have $n_2\in D_2$ and with that we've proved that for every positive integer $n_1 < \sqrt{N}$ divisor of $N$, there is an integer counterpart $n_2 > \sqrt{N}$ divisor of $N$. Since $D_1$ and $D_2$ are partitions of $D(N)$, we have that $|D_1| = |D_2|$.

Answer 1

There're a few issues with your argument, each of which have simple fixes, but as it stands I wouldn't personally be able to accept it. Specifically,

• You start by assuming $n_1 \in D_1$ and $n_2 \in D_2$, and then after a while, you prove $n_2 \in D_2$. At least ostensibly, this is assuming what you're trying to prove, so it would be fallacious. In your case, however, this is mostly just confusing, as it can be corrected just by re-writing how you introduce $n_2$.
• After that fix, what [again, you might argue "ostensibly"] you've shown is each $n_1 \in D_1$ gives you some $n_2 \in D_2$. This isn't enough to show the two sets have the same cardinality. You have all the pieces, but they aren't written down in the right order, so in some way you might say it's all there even though I don't know you well enough to know what you intended, except that...
• I don't know why you are forcing partitions into this argument. It's possible that there's some way in which they can be used to resolve these issues, but they definitely can't be used the way you tried to use them. Specifically, knowing that $D_1 \cup D_2 = D(N)$ and $D_1 \cap D_2 = \emptyset$ when $N$ isn't a perfect square doesn't imply $|D_1| = |D_2|$ in any apparent manner.

---

Here's how we might try to fix the argument:

A way I tried to prove this is by taking $n_1\in[0,\sqrt{N}]$ as a divisor of $N$ and $n_2 := N/n_1$, so that $n_1, n_2\in\mathbb{Z}^+$, with $n_1\cdot n_2 = N$. Since $N$ is not a perfect square we know $\sqrt{N}$ is irrational, thus $n_1\neq \sqrt{N}$. Define $D_1 = D(N)\cap [0, \sqrt{N}]$ and $D_2 = D(N)\cap [\sqrt{N},N]$.

We know that $n_1 < \sqrt{N}$. But we also know that $n_1 = \frac{N}{n_2}$. Thus:

\begin{align*} n_1 &< \sqrt{N}\\ \frac{N}{n_2} &< \sqrt{N}\\ n_2 &>\sqrt{N}. \end{align*}

This way, we have $n_2\in D_2$ and with that we've proved that for every positive integer $n_1 < \sqrt{N}$ divisor of $N$, there is an integer counterpart $n_2 > \sqrt{N}$ divisor of $N$.

This is where we need to look at what we've shown and actually state it. Partitions won't help us conclude. Instead, we note that we've defined a function $D_1 \to D_2$ given by $n \mapsto N/n$. By a similar argument, we could show another function $D_2 \to D_1$ given by $n \mapsto N/n$.

Further, if we compose either function with the other, then we have $N/(N/n)) = n$, which means they're inverses of each other and therefore each is a bijection. This directly shows $|D_1| = |D_2|$.

---

Once we are satisfied we have a valid proof, we should look at it again. Why, for instance, did we need to use $N$ is not a perfect square? It was only to show that $n_1 < \sqrt{N}$ (and $n_2 > \sqrt{N}$) which didn't really matter. In fact, if we use $n_1 \leq \sqrt{N}$ instead (resp. $n_2 \geq \sqrt{N}$), then it all still works using the same argument.

We also might clean up the proof by rearranging it for clarity, giving something like the following:

For convenience, define $D_1 = D(N)\cap [1, \sqrt{N}]$ and $D_2 = D(N)\cap [\sqrt{N},N]$.

Let $n_1 \in D_1$ and define $n_2 := N/n_1$. We know that $n_1 \leq \sqrt{N}$, but we also know that $n_1 = N/n_2$, so that $n_2 \in D(N)$ and $$N/n_2 = n_1 \leq \sqrt{N}$$ $$n_2 \geq \sqrt{N}.$$ This way, we have $n_2 \in D_2$. That is, $\phi_1(n) = N/n$ defines a function $\phi_1 : D_1 \to D_2$.

By a similar argument, $\phi_2(n) = N/n$ defines a function $\phi_2 : D_2 \to D_1$. Since $\phi_2(\phi_1(n)) = N/(N/n) = n$ and $\phi_1(\phi_2(n)) = N/(N/n) = n$, it follows that $\phi_2 = \phi_1^{-1}$, so in particular $\phi_1$ is one-to-one and onto (or "bijective").

From this, we conclude $|D_1| = |D_2|$.

---

As a final note, it may be useful to see how partitions fit in here. Even though I dropped it in the above argument, we can still use partitions to make further conclusions. Specifically, if $N$ is not a perfect square, then our conclusion applied to the partition gives $$|D_1| = |D_2| = |D(N)|/2$$ and a slightly modified argument gives the more general $$|D_1| = |D_2| = \lceil |D(N)|/2\rceil$$ as long as $N$ is a nonzero integer.

Answer 2

A variant of what Brian writes is the following:

Let $D(n)$ be the set of divisors of $n$. The map $\sigma\colon D(n)\to D(n)$ given by $\sigma(k) = n/k$ is an involution (since $\sigma(n/k) = n/(n/k) =k$) and hence gives an action of $S_2$ on $D(n)$. The orbits of this action all have size $1$ or $2$, and since an orbit of size $1$ must have $\sigma(k)=k=n/k$, there is at most one singleton orbit, and none unless $n$ is a perfect square. Let $\mathcal P$ denote the set of orbits of $\sigma$ on $D(n)$.

Now if we set $D_1(n) = \{k\in D(n): k\leq \sqrt{n}\}$ and $D_2(n)= \{k\in D(n): l \geq \sqrt{n}\}$ then $D(n) = D_1(n)\sqcup D_2(n)$ and if $\mathcal O$ is an orbit of $\sigma$ and $k \in O$, clearly $k \in D_1(n)$ or $k\in D_2(n)$. But if $k\leq\sqrt{n}$, then $n=k\sigma(k)\leq \sqrt{n}\sigma(k)$ hence $\sqrt{n}\leq \sigma(k)$. Similarly if $k\geq\sqrt{n}$ then $\sigma(k)\leq\sqrt{n}$. It follows that for any $O \in \mathcal P$ we have $|D_1(n)\cap O|=|D_2(n)\cap O|=1$. It follows that we must have $|D_1(n)| = |D_2(n)|= |\mathcal P|$.

Note that this argument as the (modest) advantage (as Brian's does also) of working uniformly for the cases where $n$ is a perfect square and $n$ is a nonsquare.