Sum of divisors function inequality

292 Views Asked by At

Prove that if $n<m$ and $n$ divides $m$, then $\frac{\sigma(n)}{n} < \frac{\sigma (m)}{m}$, where $\sigma(x)$ denotes the sum of all the divisors of $x$.

I know that $\sigma (x)$ is multiplicative but not completely multiplicative. So, if $m=nk$ and $\gcd(n,k)=1$, then the inequality rewrites to $\frac{\sigma(n)}{n} < \frac{\sigma(n)\sigma(k)}{nk}$, which gives a lot of cancellation and can be easily proven. But how can it be solved if the gcd is not $1$?

2

There are 2 best solutions below

2
On BEST ANSWER

Working one prime at a time, it will suffice to show that the inequality $$ \frac{\sigma(np)}{np} > \frac{\sigma(n)}{n} $$ holds for all positive integers $n$ and all primes $p$.

Fix a positive integer $n$ and a prime $p$.

First suppose $p\not\mid n$.$\;$Then $$ \frac{\sigma(np)}{np} = \frac{\sigma(n)\sigma(p)}{np} = \frac{\sigma(n)}{n}\cdot \frac{\sigma(p)}{p} = \frac{\sigma(n)}{n}\cdot \frac{p+1}{p} > \frac{\sigma(n)}{n} $$ Next suppose $p\mid n$.

Then we can write $n=ap^k$, where $p\not\mid a$, so \begin{align*} \sigma(n) &= \sigma(ap^k) = \sigma(a)\sigma(p^k) = \sigma(a)\left(\frac{p^{k+1}-1}{p-1}\right)\\[4pt] \sigma(np) &= \sigma(ap^{k+1}) = \sigma(a)\sigma(p^{k+1}) = \sigma(a)\left(\frac{p^{k+2}-1}{p-1}\right)\\[4pt] \end{align*} so $$ \frac{\sigma(np)}{\sigma(n)} = \frac{p^{k+2}-1}{p^{k+1}-1} $$ hence $$ \frac {\left({\Large{\frac{\sigma(np)}{np}}}\right)} {\left({\Large{\frac{\sigma(n)}{n}}}\right)} = \frac{1}{p}\cdot \frac{p^{k+2}-1}{p^{k+1}-1} = \frac{p^{k+2}-1}{p^{k+2}-p} > 1 $$ and thus $$ \frac{\sigma(np)}{np} > \frac{\sigma(n)}{n} $$ Now suppose positive integers $n,m$ with $n < m$ are such that $n{\,\mid\,}m$.

Then we can write $$ m=n{\,\cdot\,}(p_1\cdots p_j) $$ where $p_1,...,p_j$ are primes, not necessarily distinct.

Let $x_0,...,x_j$ be defined recursively by $$ \left\lbrace \begin{align*} x_0&=n\\[4pt] x_i&=x_{i-1}p_i\;\text{for}\;\,1\le i\le j\\[4pt] \end{align*} \right. $$ Then for $1\le i\le j$ we get $$ \frac{\sigma(x_i)}{x_i} = \frac{\sigma(x_{i-1}p_i)}{x_{i-1}p_i} > \frac{\sigma(x_{i-1})}{x_{i-1}} $$ hence $$ \frac{\sigma(n)}{n} = \frac{\sigma(x_0)}{x_0} < \cdots < \frac{\sigma(x_j)}{x_j} = \frac{\sigma(m)}{m} $$

0
On

First, if $n$ is $1$, then $\frac{\sigma(n)}{n} = 1$, but with $m \gt 1$ you have $\sigma(m) \ge m + 1 \implies \frac{\sigma(m)}{m} \gt 1$, so your inequality holds then. Next, with $n \gt 1$, specify $n$ as a product of distinct primes, i.e.,

$$n = \prod_{i=1}^{j}p_i^{a_i}, \; j \ge 1 \tag{1}\label{eq1A}$$

Since $n \mid m$, all primes which divide $n$ also divide $m$, but with $m$ having at least one more prime factor, with possibly $0$ or more unique prime factors. You thus have for the same $j$ initial distinct prime factors as in \eqref{eq1A} that

$$m = \prod_{i=1}^{k}p_i^{b_i}, \; k \ge j, \; b_i \ge a_i \; \forall \; 1 \le i \le j \tag{2}\label{eq2A}$$

Since the divisor function is multiplicative, you have

$$\begin{equation}\begin{aligned} \frac{\sigma(n)}{n} & = \frac{\sigma(\prod_{i=1}^{j}p_i^{a_i})}{\prod_{i=1}^{j}p_i^{a_i}} \\ & = \frac{\prod_{i=1}^{j}\sigma(p_i^{a_i})}{\prod_{i=1}^{j}p_i^{a_i}} \\ & = \prod_{i=1}^{j}\left(\frac{\sigma(p_i^{a_i})}{p_i^{a_i}}\right) \\ & = \prod_{i=1}^{j}\left(\frac{p_i^{a+1} - 1}{(p_i - 1)(p_i^{a_i})}\right) \\ & = \prod_{i=1}^{j}\left(\frac{p_i^{a+1} - 1}{p_i^{a+1} - p_i^{a_i}}\right) \\ & = \prod_{i=1}^{j}\left(\frac{1 - \frac{1}{p^{a_i+1}}}{1 - \frac{1}{p_i}}\right) \\ \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

Similarly, you also have

$$\frac{\sigma(m)}{m} = \prod_{i=1}^{k}\left(\frac{1 - \frac{1}{p^{b_i+1}}}{1 - \frac{1}{p_i}}\right) \tag{4}\label{eq4A}$$

As Will Jagy's question comment suggests, consider separately each of the primes which divide $n$. For the $i$'th prime factor, \eqref{eq3A} has the factor of

$$\frac{1 - \frac{1}{p^{a_i+1}}}{1 - \frac{1}{p_i}} \tag{5}\label{eq5A}$$

and \eqref{eq4A} has the factor of

$$\frac{1 - \frac{1}{p^{b_i + 1}}}{1 - \frac{1}{p_i}} \tag{6}\label{eq6A}$$

Next, for $b_i \ge a_i$, you get

$$\begin{equation}\begin{aligned} p^{b_i + 1} & \ge p^{a_i + 1} \\ \frac{1}{p^{b_i + 1}} & \le \frac{1}{p^{a_i + 1}} \\ -\frac{1}{p^{b_i + 1}} & \ge -\frac{1}{p^{a_i + 1}} \\ \frac{1 - \frac{1}{p^{b_i + 1}}}{1 - \frac{1}{p_i}} & \ge \frac{1 - \frac{1}{p^{a_i + 1}}}{1 - \frac{1}{p_i}} \end{aligned}\end{equation}\tag{7}\label{eq7A}$$

Note if $b_i \gt a_i$, then \eqref{eq7A} becomes a strict inequality, i.e., it's $\gt$ instead of $\ge$.

In summary, for each factor in \eqref{eq3A} there's a corresponding factor in \eqref{eq4A} that is at least as large. There must also be either at least one corresponding factor in \eqref{eq4A} which is larger or at least one extra factor in \eqref{eq4A} (which would be $\gt 1$). Finally, any extra factors in \eqref{eq4A}, with $b_i \ge 1$, would all be $\gt 1$, so they would increase the overall product. This shows the product of all of the factors in \eqref{eq4A} is larger than that of \eqref{eq3A}, i.e., you have

$$\frac{\sigma(n)}{n} < \frac{\sigma (m)}{m} \tag{8}\label{eq8A}$$