# Monthly Archives: June 2015

## An inequality involving sigma and tau

Let $\tau(n)$ and $\sigma(n)$ respectively be the number and the sum of the positive divisors of the positive integer $n$. We will prove the following inequality:

$\sigma(n)\ge \sqrt n\tau(n)$.

First proof. By the Cauchy-Schwarz inequality,

$\displaystyle\sigma(n)^2=\left(\sum_{d\mid n}d\right)\left(\sum_{d\mid n}\frac nd\right)\ge (\sqrt n\tau(n))^2=n\tau(n)^2$.

Second proof. By Chebyshev’s inequality,

$\displaystyle\sigma(n)^2=\left(\sum_{d\mid n}d\right)\left(\sum_{d\mid n}\frac nd\right)\ge \tau(n)\cdot n\tau(n)$.

Third proof. By the AM-GM inequality,

$\displaystyle 2\sigma(n)=\sum_{d\mid n}\left(d+\frac nd\right)\ge 2\sqrt n\tau(n)$.

Fourth proof. Again by the AM-GM inequality,

$\displaystyle n^{\tau(n)}=\prod_{d\mid n}d\prod_{d\mid n}n/d=\left(\prod_{d\mid n}d\right)^2\Rightarrow n^{\tau(n)/2}=\prod_{d\mid n}d\le\left(\frac{\sigma(n)}{\tau(n)}\right)^{\tau(n)}$.

Fifth proof. If $n=p_1^{a_1}\cdots p_k^{a_k}$ factored into primes, then AM-GM gives

$\displaystyle\sigma(n)=\prod_{j=1}^k(p_j^{a_j}+\cdots+p_j+1)\ge\prod_{j=1}^k(a_j+1)p_j^{a_j/2}=\sqrt{n}\tau(n)$.

We also trivially have $\sigma(n)\le n\tau(n)$. Hence for all $n$,

$\displaystyle \boxed{\sqrt n\le\frac{\sigma(n)}{\tau(n)}\le n}$.

In general, if $f:\mathbb N\to\mathbb N$ is completely multiplicative, and

$F(n):=\displaystyle\sum_{d\mid n}f(d)$,

then the first four proofs can be generalised to deduce that

$(*)\qquad\qquad\qquad\qquad\quad\ F(n)\ge \tau(n)\sqrt{f(n)}$.

For example, if $\sigma_k(n)$ is the sum of the $k$-th powers of the positive divisors of $n$, then this shows that

$\displaystyle \boxed{n^{k/2}\le\frac{\sigma_k(n)}{\tau(n)}\le n^k}$

for each $k\ge 0$. This, combined with the result from the previous post, gives

$\displaystyle\lim_{n\to\infty}\frac{\sigma_k(n)}{n^{k+1}}=0$,

i.e., $\sigma_k(n)=o(n^{k+1})$ as $n\to\infty$, for each $k\ge 0$.

1 Comment

Filed under Number theory

## An asymptotic property of the divisor counting function

Let $\tau(n)$ be the number of positive divisors of the positive integer $n$ and let $\phi(n)$ be Euler’s function. Then it is easily seen that

$\phi(n)+\tau(n)\le n+1$

for each $n$. So

$\displaystyle\frac{\phi(n)}{n}+\frac{\tau(n)}{n}\le 1+\frac 1n$

holds for all $n$.

$\displaystyle\limsup_{n\to\infty}\frac{\phi(n)}{n}=\lim_{n\to\infty}\frac{n-1}{n}=1$.

So it follows that

$\displaystyle\limsup_{n\to\infty}\frac{\tau(n)}{n}=0$.

Therefore, by the sandwich theorem,

$\displaystyle\lim_{n\to\infty}\frac{\tau(n)}{n}=0$,

i.e., $\tau(n)=o(n)$ as $n\to\infty$. In layman’s terms, this is saying that the number of divisors of $n$ is small compared to $n$ when $n$ is large. The following plot of $\tau(n)/n$ against $n$ for $1\le n\le 500$ captures this nicely.

So this means, for example, that there are only finitely many positive integers $n$ with more than $n/2015$ divisors, which I think is pretty neat!

Filed under Number theory

## Symmetric polynomials in two variables

Let $R$ be a commutative ring. The fundamental theorem of symmetric polynomials says that any symmetric polynomial in $R[X,Y]$ can be expressed uniquely as a polynomial in $X+Y$ and $XY$.

Recently I was thinking about this along the following lines. Let $R[X,Y]^{S_2}$ denote the set of all symmetric polynomials in $R[X,Y]$. Then the theorem above is saying that $R[X,Y]^{S_2}$ is generated by $\{X+Y,XY\}$ as an $R$algebra, i.e., $R[X,Y]^{S_2}=R[X+Y,XY]$. Being unsuccessful at utilising this I ended up with the following. (I can’t see the best way of showing that a set generates an algebra.)

Let $f(X,Y)=\sum_{i,j}a_{i,j}X^iY^j\in R[X,Y]^{S_2}$. Since $f(X,Y)=f(Y,X)$, we have $a_{i,j}=a_{j,i}$ for all $i,j$. Hence $f(X,Y)=\sum_{i\le j}a_{i,j} (XY)^i(X^{j-i}+Y^{j-i})$. So it suffices to show that $X^n+Y^n$ can be expressed as a polynomial in $X+Y$ and $XY$ for each $n\ge 0$. But this follows easily by induction and the following identity

$X^n+Y^n=(X+Y)(X^{n-1}+Y^{n-1})-XY(X^{n-2}+Y^{n-2})$.

However, this argument doesn’t generalise immediately to more variables, and I don’t particularly like any of the proofs that I’ve found so far.