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.

Since there are infinitely many primes,

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

Screenshot 2015-06-26 03.46.54

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!

Leave a comment

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 Ralgebra, 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.

Leave a comment

Filed under Algebra