23 April 2015

Upper bound for Mahler's Measure

Statement: A polynomial $f(x) = x^n + a_{n-1}x^{n-1} + \dots + a_0 \in \mathbb{C}[x]$ that has roots $z_1, z_2, ... , z_n \in \mathbb{C},$ then:

$$\prod_{k = 1}^{n} \max (1,|z_k|) \leq \sqrt{1+|a_{n-1}|^2 + ... + |a_{0}|^2}$$

(The obvious approach is to use Jensen's Formula, but why I decided to share it is because of the surprisingly elementary proof which I was not aware of to begin with!)


Proof: The usual proof with Jensen's Formula:

Suppose the roots of polynomial $f(z)$ are $z_1,z_2,\cdots,z_n$,

where, $|z_1| \ge |z_2| \ge \cdots \ge |z_m| > 1 \ge |z_{m+1}| \ge \cdots \ge |z_n|$

Let, $g(z) = z^nf\left(\frac{1}{z}\right) = 1 + a_{n-1}z + \dots + a_0z^n$

Then, $\{1/z_k\}_{1\le k \le m}$ are the zeros of $g$ in the disk $|z| \le r = 1-\epsilon < 1$, where, $\epsilon$ is chosen such that $g(re^{i\theta}) \neq 0$ for $\theta \in [0,2\pi]$.

Then, using Jensen's Formula ([a proof on Math.Se]) we have: $\displaystyle \log|r^m z_1\cdots z_m| = \frac{1}{2\pi}\int_0^{2\pi} \log |g(re^{i\theta})|\,d\theta$

i.e.,$$|r^m z_1\cdots z_m| = \exp\left(\frac{1}{2\pi}\int_0^{2\pi} \log |g(re^{i\theta})|\,d\theta\right)$$

Applying Jensen Inequality, $\displaystyle \exp\left(\frac{1}{2\pi}\int_0^{2\pi} \log |g(re^{i\theta})|\,d\theta\right) \le \frac{1}{2\pi}\int_0^{2\pi} |g(re^{i\theta})|\,d\theta$

followed by Cauchy-Schwarz Inequality yields, 

$\displaystyle \frac{1}{2\pi}\int_0^{2\pi} |g(re^{i\theta})|\,d\theta \le \frac{1}{2\pi}\left(\int_0^{2\pi}\,d\theta\int_0^{2\pi} |g(re^{i\theta})|^2\,d\theta\right)^{1/2} = \sqrt{1+|a_{n-1}|^2 + ... + |a_{0}|^2}$

Therefore, $\displaystyle |r^m z_1\cdots z_m| \le \sqrt{1+|a_{n-1}|^2 + ... + |a_{0}|^2}$, and letting $\epsilon \to 0$, $r \to 1$ gives the desired result.


A Second Approach:

We can also use induction.

The 2-norm of a polynomial $f(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_0$ is defined as,

$\lVert f \rVert_2 := \sqrt{|a_n|^2+|a_{n-1}|^2 + ... + |a_{0}|^2}$

and, we have: 

Lemma: $\displaystyle \lVert (x-z)f(x) \rVert_2 = \lVert (\overline{z}x-1)f(x) \rVert_2$

$\displaystyle \begin{align}\lVert (x-z)f(x) \rVert_2^2 &= \sum\limits_{j=0}^{n+1} |a_{j-1} - za_j|^2 \textrm{ ,where, $a_{-1} = a_{n+1} = 0$ in notation} \\ &= \sum\limits_{j=0}^{n+1} (a_{j-1} - za_j)\overline{(a_{j-1} - za_j)} \\ &= (1+|z|^2)\lVert f(x) \rVert_2^2 - \sum\limits_{j=0}^{n+1} (a_{j-1}\overline{za_j} + za_j\overline{a_{j-1}}) \\ &= (1+|z|^2)\lVert f(x) \rVert_2^2 - \sum\limits_{j=0}^{n+1} (z\overline{a_{j-1}}a_{j} + \overline{z}a_{j-1}\overline{a_{j}}) \\ &= \sum\limits_{j=0}^{n+1}(\overline{z}a_{j-1} - a_j)(z\overline{a_{j-1}} - \overline{a_j}) \\ &= \sum\limits_{j=0}^{n+1}|\overline{z}a_{j-1} - a_j|^2 = \lVert (\overline{z}x-1)f(x) \rVert_2^2 \end{align}$

as before let us write the roots of the polynomial in the order, $|z_1| \ge |z_2| \ge \cdots \ge |z_m| > 1 \ge |z_{m+1}| \ge \cdots \ge |z_n|$ .

Consider the polynomial: $\displaystyle g(x) = \prod\limits_{j=1}^m (\overline{z_j}x-1)\prod\limits_{j=m+1}^n (x - z_j) = \sum\limits_{j=0}^{n}b_jx^j$,

where, $|b_n| = |z_1z_2\cdots z_m|$

Now, 

$\begin{align}|z_1z_2\cdots z_m| = |b_n| &\le \sqrt{|b_n|^2+\cdots+|b_0|^2} \\ & = \lVert g(x) \rVert_2 \\ &= \lVert \frac{g(x)}{\overline{z_1}x - 1}(x-z_1) \rVert_2 \\ &= \lVert \frac{g(x)}{\prod\limits_{j=1}^m (\overline{z_j}x-1)}\prod\limits_{j=1}^m(x-z_1) \rVert_2 [\textrm{ ,by repeated application of lemma}] \\ &= \lVert f \rVert_2 \end{align}$