Tag Archives: inequalities

A New AM-GM Inequality

I recently found the following inequalities useful:

$\displaystyle \left(x+\frac{a_1+\cdots+a_n}{n}\right)^n\ge (x+a_1)\cdots(x+a_n)\ge \left(x+\sqrt[n]{a_1\cdots a_n}\right)^n$,

for any $x,a_1,\dots,a_n\ge 0$.

To prove the left half simply apply AM-GM to the product

$\displaystyle (x+a_1)\cdots (x+a_n)\le \left(\frac{(x+a_1)+\cdots+(x+a_n)}{n}\right)^n$.

The right half follows directly from Hölder’s inequality.

More generally, one has

$\displaystyle\left(\frac{a_1+\cdots+a_n}{n}+\frac{b_1+\cdots+b_n}{n}\right)^n\ge (a_1+b_1)\cdots(a_n+b_n)\\\ge \left(\sqrt[n]{a_1\cdots a_n}+\sqrt[n]{b_1\cdots b_n}\right)^n$

for $a_1,\dots,a_n,b_1,\dots,b_n\ge 0$. The proof goes similarly.

One obtains similar inequalities for any number of vectors $a,b,c,\dots$.

As an example, for $a_i=i$ we get the inequalities

$\displaystyle \left(x+\frac{n+1}{2}\right)^n\ge (x+1)\cdots (x+n)>\left(x+\frac ne\right)^n$

using the fact that $\sqrt[n]{n!}/n\to 1/e$ from above.

Filed under Algebra

Another Inequality Involving Sigma and Tau

Let $n$ be a positive integer. By the weighted AM-GM inequality, one has

$\displaystyle\frac{\sum d\cdot n/d}{\sum n/d}\ge\left(\prod d^{n/d}\right)^\frac{1}{\sum n/d}$,

where all sums and products are taken over the positive divisors $d$ of $n$. This means

$\displaystyle\boxed{\frac{n\tau(n)}{\sigma(n)}\ge\left(\prod_{d\mid n}d^{1/d}\right)^{n/\sigma(n)}}$.

Considering the analytic behaviour of the function $f(x)=x^{1/x}$ one deduces

$\displaystyle\prod_{d\mid n}d^{1/d}\ge\prod_{1\neq d\mid n}n^{1/n}=n^{(\tau(n)-1)/n}$

for any $n$, with equality iff $n$ is prime or $1$ or $4$. (By convention we take an empty product to be $1$.) Combining this with the first inequality in this post we obtain

$\displaystyle n^{1/2}\ge\frac{n\tau(n)}{\sigma(n)}\ge n^\frac{\tau(n)-1}{\sigma(n)}$,

i.e.,

$\boxed{\displaystyle n^{1/2}\le\frac{\sigma(n)}{\tau(n)}\le n^{1-\frac{\tau(n)-1}{\sigma(n)}}}$.

This strengthens the first boxed inequality from this post.

Filed under Number Theory

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