Putnam 2020 inequality for complex numbers in the unit circle

Question

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.

Is the one-variable-at-a-time maximum modulus principle argument really so bad? — Will Sawin
– Will Sawin, Commented Sep 7, 2021 at 17:18
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). — Malkoun
– Malkoun, Commented Sep 7, 2021 at 21:38
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$. — Malkoun
– Malkoun, Commented Sep 7, 2021 at 23:01
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$). — GH from MO
– GH from MO, Commented Sep 9, 2021 at 16:14

GH from MO · Accepted Answer · 2022-06-27 21:54:33Z

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 $$\Re(a_{n-1}) = \Re\left(n-\sum_{j=1}^n z_j\right)=n-\sum_{j=1}^n\Re(z_j)>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\}.$$

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!). — Malkoun
– Malkoun, Commented Sep 9, 2021 at 6:57
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. — Malkoun
– Malkoun, Commented Sep 9, 2021 at 7:02
@Malkoun: Yes, your intuition about the relevance of $p(z)-(z-1)^n$ was very much correct! — GH from MO
– GH from MO, Commented Sep 9, 2021 at 11:04
@Malkoun: I added your pretty generalization in the "Added" section. — GH from MO
– GH from MO, Commented Sep 9, 2021 at 16:11
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! — darij grinberg
– darij grinberg, Commented Sep 9, 2021 at 18:40

fedja · Accepted Answer · 2021-09-07 22:45:26Z

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 :-)

Interesting! Where can I read about polar derivatives and the theorem you're using? — darij grinberg
– darij grinberg, Commented Sep 7, 2021 at 23:00
@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$. — fedja
– fedja, Commented Sep 7, 2021 at 23:34
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. — Terry Tao
– Terry Tao, Commented Sep 8, 2021 at 20:59
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. — darij grinberg
– darij grinberg, Commented Sep 9, 2021 at 18:31

6 revs · Accepted Answer · 2021-09-09 07:39:41Z

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)$.

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!). — fedja
– fedja, Commented Sep 8, 2021 at 15:45
Yes thanks i should combine the two in one inequality. Sorry — Toni Mhax
– Toni Mhax, Commented Sep 8, 2021 at 16:49
But if you combine, what will be the difference with the original version (except for the polar coordinate notation)? — fedja
– fedja, Commented Sep 8, 2021 at 16:51

Stack Exchange Network

Putnam 2020 inequality for complex numbers in the unit circle

3 Answers 3

You must log in to answer this question.

Putnam 2020 inequality for complex numbers in the unit circle

3 Answers 3

You must log in to answer this question.

Related