42
$\begingroup$

The following simple-looking inequality for complex numbers in the unit disk generalizes Problem B5 on the Putnam contest 2020:

Theorem 1. Let $z_1, z_2, \ldots, z_n$ be $n$ complex numbers such that $\left|z_i\right| \leq 1$ for each $i \in \left\{1,2,\ldots,n\right\}$. Prove that \begin{align} \left| z_{1} + z_{2} + \cdots + z_n - n \right| \geq \left| z_{1} z_{2} \cdots z_n - 1 \right| , \end{align} and equality holds only if at least $n-1$ of the $n$ numbers $z_1, z_2, \ldots, z_n$ equal $1$.

In the particular case when $n = 4$, the theorem can be proved using stereographic projection onto a line, followed by a longish computation. This is how both proposed solutions go.

On the other hand, in the general case, the only elementary solution I know was given by @mela_20-15 on AoPS (spread over several posts). It has some beautiful parts (Cauchy induction), but also some messy ones (tweaking the points to lie on the unit circle in the induction step). There might also be a heavily analysis-based proof in Kiran Kedlaya's solutions (not sure if Theorem 1 is proved in full there).

Question. What is the "proof from the book" for Theorem 1?

Someone suggested to me to try to interpolate expressions of the form $\dbinom{n-1}{k-1}^{-1} \left|\sum\limits_{i_1 < i_2 < \cdots < i_k} z_{i_1} z_{i_2} \cdots z_{i_k} - \dbinom{n}{k}\right|$ between the left and the right hand sides in Theorem 1; but this does not work. For example, the inequality $\dfrac{1}{2} \left| z_1 z_2 + z_2 z_3 + z_1 z_3 - 3\right| \geq \left|z_1 z_2 z_3 - 1\right|$ fails quite often even on the unit circle.

A warning: Inequalities like Theorem 1 are rather hard to check numerically. Choosing the $z_i$ uniformly will rarely hit close to the equality case; usually the left hand side will be much larger than the right. Near the equality case, on the other hand, it is hard to tell whether the answer comes out right legitimately or whether accumulated errors have flipped the sign.

$\endgroup$
4
  • 2
    $\begingroup$ Is the one-variable-at-a-time maximum modulus principle argument really so bad? $\endgroup$
    – Will Sawin
    Sep 7 '21 at 17:18
  • $\begingroup$ Let $p(z)$ be the monic complex polynomial with roots $z_1, \ldots, z_n$. It seems to me natural to look at the polynomial $H(z) = (p(z) - (z-1)^n)/(n - e_1)$, where $e_1$ is the sum of the $z_i$ (the first elementary symmetric polynomial. Note that $H(z)$ is monic and that the first part of what you wish to prove is equivalent to $|H(0)| \leq 1$ (provided the $z_i$ are all in the closed unit disk). $\endgroup$
    – Malkoun
    Sep 7 '21 at 21:38
  • 2
    $\begingroup$ I have deleted my comment, thinking it was precisely what you had a counterexample for. I will retype it. The inequalities $|e_k - \binom{n}{k}|/{|e_1 - n|} \leq \binom{n-1}{k-1}$, for $2 \leq k \leq n$, seem to hold numerically, where $e_k$ is the $k$-th elementary symmetric polynomial in the $z_1, \ldots, z_n$. $\endgroup$
    – Malkoun
    Sep 7 '21 at 23:01
  • $\begingroup$ See the "Added" section in my post below for a proof of Malkoun's generalization for the $k$-th elementary symmetric polynomial ($1\leq k\leq n$). $\endgroup$
    – GH from MO
    Sep 9 '21 at 16:14
21
$\begingroup$

Here is a detailed and self-contained proof for general $n$, which also covers the "equality" case. It is based on Fedja's post, but it only uses (a variant of) the Gauss-Lucas theorem once.

Let $a_0,\dotsc,a_{n-1}\in\mathbb{C}$ be coefficients such that $$p(z):=(z-z_1)\dotsb(z-z_n)=(z-1)^n+\sum_{k=0}^{n-1}a_k z^k,$$ and assume that $(z-1)^{n-1}$ does not divide the left-hand side. Then, the $k$-sum on the right-hand side is a polynomial of degree $n-1$, because $$|a_{n-1}| = |n - (z_1 + \dotsb + z_n)|\geq n-(|z_1|+\dotsb+|z_n|)>0,$$ and we need to prove that $|a_{n-1}|>|a_0|$.

Introducing the differential operator $$Df(z):=(1-z)f'(z)+nf(z),$$ we claim that every root of the polynomial $Dp(z)$ lies in the closed unit disk. Indeed, assume for a contradiction that $Dp(z)=0$ and $|z|>1$. Then $p'(z)/p(z)=n/(z-1)$, that is, $$\frac{1}{n}\sum_{j=1}^n \frac{1}{z-z_j}=\frac{1}{z-1}.$$ Let $K$ be the image of the closed unit disk under the Möbius transformation $s\mapsto 1/(z-s)$. Using $|z|>1$, we see that $K$ is a closed disk containing $1/(z-1)$ on its boundary. By the previous display, this boundary point is a convex linear combination of the points $1/(z-z_j)$, which also lie in $K$. This forces that all the $z_j$'s are equal to $1$, contrary to our assumption. So the claim is proved.

Now observe that the polynomial $Dp(z)$ is the same as $$D\left(\sum_{k=0}^{n-1}a_k z^k\right)=a_{n-1}z^{n-1}+\sum_{k=0}^{n-2}((n-k)a_k+(k+1)a_{k+1})z^k.$$ We proved that this polynomial has all its roots in the closed unit disk, therefore $$|(n-k)a_k+(k+1)a_{k+1}|\leq\binom{n-1}{k}|a_{n-1}|,\qquad k\in\{0,\dotsc,n-2\}.$$ Applying the triangle inequality and re-arranging, we get that $$\frac{n-k}{k+1}|a_k|\leq|a_{k+1}|+\frac{1}{k+1}\binom{n-1}{k}|a_{n-1}|.\tag{$\ast$}$$ From here we derive by induction that $$\binom{n}{k}|a_0|\leq |a_k|+\binom{n-1}{k-1}|a_{n-1}|,\qquad k\in\{1,\dotsc,n-1\}.$$ In particular, the special case $k=n-1$ tells us that $n|a_0|\leq n|a_{n-1}|$.

To finish the proof, we only need to show that some of our inequalities are strict, so that the final inequality is strict as well. Let us assume that equality holds in each of our inequalities. Then the roots of $Dp(z)$ are equal to a single $w$ on the unit circle, so that $$(n-k)a_k+(k+1)a_{k+1}=\binom{n-1}{k}a_{n-1}(-w)^{n-1-k},\qquad k\in\{0,\dotsc,n-2\}.$$ In particular, the case $k=n-2$ yields $$\frac{2}{1-n}a_{n-2}=(1+w)a_{n-1}.$$ However, we have equality in $(\ast)$ for $k=n-2$, whence $|1+w|=2$, which forces $w=1$. But then the recursion yields that $$a_k=\binom{n-1}{k}(-1)^{n-1-k}a_{n-1},$$ i.e., $$p(z)=(z-1)^n+a_{n-1}(z-1)^{n-1}.$$ This contradicts our initial assumption, and we are done.

Added. As Malkoun pointed out in the comments, $(\ast)$ also implies the inequalities $$|a_k|\leq\binom{n-1}{k}|a_{n-1}|,\qquad k\in\{0,\dotsc,n-1\}.$$ Hence, renaming $k$ to $n-k$, we get the following generalization of the original inequality: $$\left|\sum_{1\leq j_1<\dotsb< j_k\leq n}z_{j_1}\dotsb z_{j_k}-\binom{n}{k}\right|\leq\binom{n-1}{k-1}|z_1+\dotsb+z_n-n|,\qquad k\in\{1,\dotsc,n\}.$$

$\endgroup$
10
  • 3
    $\begingroup$ Interestingly, the same method of proof proves "my" conjectured generalized inequalities in the comments of the original post, namely that $|e_k - \binom{n}{k}|/|e_1 - n| \leq \binom{n-1}{k-1}$, for $1 \leq k \leq n$, where $e_k$ is the $k$-th elementary symmetric polynomial in the $z_1, \ldots, z_n$ (of course, these are known, I am not claiming they are my inequalities, but I had conjectured them before, ran some numerical simulations which did not find counterexamples, and they turned out to be correct!). $\endgroup$
    – Malkoun
    Sep 9 '21 at 6:57
  • 2
    $\begingroup$ To prove them, you just have to apply the inductive step starting from some arbitrary $a_k$ rather than $a_0$. You then get that $|a_k| \leq \binom{n-1}{k}|a_{n-1}|$ which, when combined with $a_k = (-1)^{n-k}(e_{n-k} - \binom{n}{k})$, yield the desired generalized inequalities. $\endgroup$
    – Malkoun
    Sep 9 '21 at 7:02
  • 1
    $\begingroup$ @Malkoun: Yes, your intuition about the relevance of $p(z)-(z-1)^n$ was very much correct! $\endgroup$
    – GH from MO
    Sep 9 '21 at 11:04
  • 1
    $\begingroup$ @Malkoun: I added your pretty generalization in the "Added" section. $\endgroup$
    – GH from MO
    Sep 9 '21 at 16:11
  • 2
    $\begingroup$ Thank you! I've been able to follow the entire answer minus the equality case analysis (I am not quite sure how you get $w = 1$, but I assume this will fall out from enough fumbling around with the recursive equations). I am particularly happy to see a bunch of stronger inequalities fall out of the argument! $\endgroup$ Sep 9 '21 at 18:40
48
$\begingroup$

Darij, such stuff is usually Gauss-Lucas in disguise and this case is no exception, though one needs to use once the version for polar derivative $D_1f(z)=(1-z)f'(z)+nf(z)$ of a polynomial $f$ of degree $n$ with respect to $1$ (the corresponding theorem says that if a circle contains all roots of the polynomial $f$ but not the point $w$, then it contains all roots of $D_wf$). Just apply it once and then use the usual Gauss-Lucas, observing every time that if all roots are in the unit disk, then the free term cannot exceed the leading coefficient in absolute value.

For a polynomial of degree $n=5$, say, write it as $(z-1)^5+a_4z^4+\dots+a_0$. Then we need to show that if its roots are in the unit disk, then $|a_0|\le|a_4|$. Apply $D_1$ to kill $(z-1)^5$. You'll be left with the polynomial whose coefficients are $$ a_4, 2a_3+4a_4, 3a_2+3a_3, 4a_1+2a_2, 5a_0+a_1 $$ and whose roots are still in the unit disk.

Assume that $|a_4|<|a_0|=1$, say. Then $|a_1|>4$. Differentiate (normally). The coefficients will become $$ 4a_4, 3(2a_3+4a_4), 2(3a_2+3a_3), 4a_1+2a_2\,. $$ Since $|a_1|>4$, we must have $|a_2|>6$.

Differentiate again. You'll get $$ 12a_4, 6(2a_3+4a_4), 2(3a_2+3a_3)\,. $$ Since $|a_2|>6$, we must have $|a_3|>4$.

Finally, differentiate once more. You'll get $$ 24a_4, 6(2a_3+4a_4). $$ Since $|a_3|>4$, we must have $|a_4|>1$ contrary to what we have assume.

I leave it to you to write this properly for an arbitrary $n$ and to treat the equality case :-)

$\endgroup$
7
  • 2
    $\begingroup$ Interesting! Where can I read about polar derivatives and the theorem you're using? $\endgroup$ Sep 7 '21 at 23:00
  • 3
    $\begingroup$ @darijgrinberg I learned it from Polya and Szego "Problems and Theorems in Analysis II" (see Problem 135 on page 58, though the page number may depend on the edition). But once you know the statement, it is not hard to prove: Let's, say, we have the standard unit disk. Just consider $f(z)/(w-z)^n$ as a polynomial $P$ of $\frac{z-a}{1-\bar az}$ with $a=1/\bar w$. Differentiate honestly, but then undo the Mobius transformation and apply the standard Gauss-Lucas to $P$. $\endgroup$
    – fedja
    Sep 7 '21 at 23:34
  • 9
    $\begingroup$ Perhaps it should be renamed the Polyar derivative. $\endgroup$ Sep 8 '21 at 2:41
  • 4
    $\begingroup$ Very nice! In retrospect one way to be guided to this solution is to see that the claimed equality condition ($n-1$ of the $z_1,\dots,z_n$ are equal to $1$) is equivalent to the polynomial $(z-z_1) \dots (z-z_n)$ being equal to $(z-1)^n$ plus a constant multiple of $(z-1)^{n-1}$; this linearisation of the condition suggests the use of a differential operator that kills the $(z-1)^n$ term. $\endgroup$
    – Terry Tao
    Sep 8 '21 at 20:59
  • 2
    $\begingroup$ Thanks, fedja! It was GH's answer that made the argument fully clear to me, but I'm fascinated at how you found just the right Moebius transformation to make Gauss-Lucas spit out the "right" result. $\endgroup$ Sep 9 '21 at 18:31
0
$\begingroup$

I am just putting an (incomplete) answer as i think this can be done in the following ''elementary'' way. And also since this would be giving some nice induction proofs... For a visualisation one may prove by induction the inequality when all variables are reals $r_i$ with $|r_i|\le 1$, $i=1,\ldots,n$. This reads as $$n-\sum_{i=1}^nr_i\ge 1-\prod_{i=1}^n r_i$$

For $z_i=r_i e^{\textrm{i}\theta_i}$ and $0\le r_i\le 1$, for all $i$, the given inequality is the following

$$(n-\sum_{i=1}^n r_i\cos(\theta_i))^2+\left(\sum_{i=1}^n r_i\sin(\theta_i)\right)^2\ge (1-\prod_{i=1}^nr_i\cos(\sum_{i=1}^n\theta_i))^2+\left(\prod_{i=1}^nr_i\sin(\sum_{i=1}^n\theta_i)\right)^2$$ I write the base case $n=2$, this becomes after simplifications $$r_1^2+r_2^2+4-4(r_1\cos(\theta_1)+r_2\cos(\theta_2)-r_1r_2\cos(\theta_1)\cos(\theta_2))\ge 1+r_1^2r_2^2$$ The left side is minimal for $(\theta_1,\theta_2)\in\{0,\pi\}$ (extremal values) which returns to the case of real variables. To see this note that the expression is affine in $ \cos(\theta_1)$ or $\cos(\theta_2)$.

$\endgroup$
3
  • 2
    $\begingroup$ The second inequality is certainly false: you can easily have the LHS zero and the RHS positive ($\theta$'s can be both positive and negative!). $\endgroup$
    – fedja
    Sep 8 '21 at 15:45
  • $\begingroup$ Yes thanks i should combine the two in one inequality. Sorry $\endgroup$
    – Toni Mhax
    Sep 8 '21 at 16:49
  • 2
    $\begingroup$ But if you combine, what will be the difference with the original version (except for the polar coordinate notation)? $\endgroup$
    – fedja
    Sep 8 '21 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.