Inequality with Complex Numbers

Consider the following problem:

Prove that for every set of complex numbers $\{z_i\}$, with $i$ ranging from one to $n$, there is a subset $J$ such that

$$\left|\sum_{j\in J} z_j\right|\ge \frac{1}{4\sqrt 2} \sum_{k=1}^n |z_k|.$$

Could someone give me an example of equality? I believe I proven have a stronger statement.

My proof. Consider all the $z_i$ with positive real part. Call the real part of the sum of these numbers $X^+$. In a similar way, form $X^-$, $Y^+$, and $Y^-$. Without loss of generality, let $X^+$ have the greatest magnitude of these.

Note that because $|\operatorname{Re}(z)|+|\operatorname{Im}(z)|\ge |z|$, we have

$$\left(\sum_{k=1}^n |\operatorname{Re}(z_k)|+|\operatorname{Im}(z_k)| \right) \ge \sum_{k=1}^n |z_k|.$$

But note that $\sum \limits_{k=1}^n |\operatorname{Re}(z_k)|+|\operatorname{Im}(z_k)| = X^+ + |X^-|+ Y^+ +|Y^-|$, so we have $$4X^+ \ge \sum_{k=1}^n |z_k|.$$ By choosing $J$ to be the set of complex number with positive real part, this proves a stronger statement, because the factor of $1/\sqrt 2$ isn't needed.

-
Do you know how to prove the inequality, or is that part of your question? – Srivatsan Dec 16 '11 at 5:27
I believe I have proved a stronger statement, so an example of equality would furnish a counterexample. – Potato Dec 16 '11 at 5:28
(Just a suggestion, feel free to ignore it. :-)) In that case, wouldn't it be better to post your proof and ask for verification, in addition to a counterexample? – Srivatsan Dec 16 '11 at 5:29
Re "Could someone give me an example of equality? I believe I proven have a stronger statement.": Equality is easy ($n=1,z_1=0$) and isn't the counterexample you seek, so you might wish to reword the first sentence of yours that I quoted. – msh210 Dec 16 '11 at 8:31

4 Answers

The constant $\frac{1}{4 \sqrt{2}}$ can be replaced by $\frac{1}{\pi}$, which is the best possible constant independent of $n$.

Let $R(z) = \max(0, \text{Re}(z))$. Choose $\theta \in [0,2\pi]$ to maximize $F(z_1,\ldots, z_n,\theta) = \sum_{j=1}^n R(e^{i\theta} z_j)$. Note that for any complex number $z$, $$\frac{1}{2\pi} \int_0^{2 \pi} R(e^{i \theta} z) \ d\theta = \frac{|z|}{2 \pi} \int_{0}^\pi \sin \theta \ d\theta = \frac{|z|}{\pi}$$ The maximal value of $F(z_1,\ldots,z_n,\theta)$ is at least the average value for $\theta \in [0,2\pi]$, namely $\frac{1}{\pi} \sum_{j=1}^n |z_j|$. Now note that if $J = \{j: R(e^{i\theta} z_j) > 0\}$, $\left|\sum_{j \in J} z_j\right| \ge \text{Re} \sum_{j \in J} e^{i \theta} z_j = F(z_1,\ldots,z_n,\theta)$.

To see that this estimate is best possible, consider cases where $n$ is large and the $z_n$ are the $n$'th roots of unity.

-
+1. This is a beautiful and surprising result. [I guessed wrongly that $\frac{1}{4}$ is correct and tight.] Is there a reference for this result? Also, is the following $d$-dimensional generalisation studied? Assume that $v_1, v_2, \ldots, v_n$ are in $\mathbb R^d$. Is it true that there exists $J \subseteq [n]$ such that $$\left \| \sum \limits_{j \in J} v_j \right\| \geqslant c_d \sum \limits_{i=1}^n \| v_i \|,$$ for some absolute constant $c_d > 0$ (independent of $n$)? And how small is $c_d$ for large $d$? – Srivatsan Dec 16 '11 at 7:59
Nice. I was only able to get the constant up to the maximum of $\dfrac{\theta}{2\pi}\cos(\theta/2)$ which is about $0.1786$ which is quite less than $1/\pi\doteq0.3183$ – robjohn Dec 16 '11 at 8:25
@Robert Israel Amazing! Did you knew that or proved by yourself? – Norbert Jan 25 '12 at 19:14
I proved it myself, although I've seen similar things before (certainly the techniques involved are well-known). – Robert Israel Jan 25 '12 at 22:40
Robert: I sought a higher dimensional generalisation of this problem in my previous comment. Here's an update you might find interesting. I posted it as a separate question; and @robjohn was able to extend your answer to that case as well. – Srivatsan Jan 26 '12 at 5:47

For any complex $|w|=1$, $w\cdot z\le|z|$. Therefore, $$\sum_{k=1}^n z_k\cdot w\le\left|\sum_{k=1}^n z_k\right|\tag{1}$$ If we consider complex numbers that are contained in a wedge with angle $\theta$, then we have that by letting $w$ be the unit complex number in the middle of the wedge \begin{align} \left|\sum_{k=1}^n z_k\right| &\ge\sum_{k=1}^n z_k\cdot w\\ &\ge\sum_{k=1}^n |z_k|\cos(\theta/2)\tag{2} \end{align} because the angle between $z_k$ and $w$ is at most $\theta/2$.

Note that for a given angle $\theta$, we can find a wedge $W$ of angle $\theta$ that $$\sum_{z_k\in W} |z_k|\ge\frac{\theta}{2\pi}\sum_{k=1}^n |z_k|\tag{3}$$ that is, there must be a wedge that has at least the average of all wedges.

Putting together $(2)$ and $(3)$, we have \begin{align} \left|\sum_{z_k\in W} z_k\right| &\ge\cos(\theta/2)\sum_{z_k\in W} |z_k|\\ &\ge\frac{\theta}{2\pi}\cos(\theta/2)\sum_{k=1}^n |z_k|\tag{4} \end{align} The maximum of $\dfrac{\theta}{2\pi}\cos(\theta/2)$ is $0.1786$ when $\theta$ is $1.720667$. However, using $\theta=\pi/2$, we get $\dfrac{\theta}{2\pi}\cos(\theta/2)=\frac{1}{4\sqrt{2}}$. Plugging this into $(4)$, we get $$\left|\sum_{z_k\in W} z_k\right|\ge\frac{1}{4\sqrt{2}}\sum_{k=1}^n |z_k|\tag{5}$$

-

Let $z_k = r_k e^{i\varphi_k}$, $k\in[n] = \{1, 2, \dots, n \}$.

\begin{align*} \max_{I\subseteq [n]}\left|\sum_{k\in I}z_k \right| &\ge \frac{1}{2\pi}\int_0^{2\pi}\left|\sum_{k=1}^n z_k e^{ix}\right|\,dx \\&\ge \frac{1}{2\pi}\int_0^{2\pi} {\rm Im} \sum_{{\rm Im}(z_ke^{ix})\ge 0} z_k e^{ix} \,dx \\& = \sum_{k=1}^n \frac{1}{2\pi}\int_{0\le \varphi_k + x\le \pi} {\rm Im}(r_ke^{i(\varphi_k + x)})\,dx \\& = \sum_{k=1}^n \frac{r_k}{2\pi}\int_{0\le \varphi_k + x\le \pi} \sin(\varphi_k + x)\,dx \\& = \sum_{k=1}^n \frac{r_k}{2\pi} \cdot 2 \\& = \frac{1}{\pi}\sum_{k=1}^n |z_k| \end{align*}

-

Here is a geometric prove with the constant $\frac{3}{4\pi}$.

Denote $$z_0 = -\sum_{k=1}^n z_k$$

Hence we'll have that the sum of $z_k$'s is 0. It allows us to construct a convex polygon $P$ from the vectors $z_0, z_1, \dots, z_n$ ( it can be proved by simple induction on $n$ ). Denote the diameter of $P$ by $d = {\rm diam}(P)$. It is clear that the diameter is the length of the longest diameter of a polygon, therefore $$d = |AB| = \sum_{k\in I} z_k$$ for some $I\subseteq [n]$, where $A$ and $B$ are vertices of $P$ and

Let $\omega_1$ ($\omega_2)$ be tha circle at center $A$ ($B$) and of radium $d$, and let $L$ be the edge of the intersection of $\omega_1$ and $\omega_2$ as shown in the picture :)

Since $d$ is the diameter of $P$ then $P$ will be inside of $L$, and hence the perimater of $P$ is smaller that the perimater of $L$: $${\rm perimeter}(P) < {\rm perimeter}(L)$$

Simple calculation shows that $${\rm perimeter}(L) = \frac{4\pi}{3}d$$

Now $$\sum_{k=1}^n |z_k| \le \sum_{k=0}^n |z_k| = {\rm perimeter}(P) < {\rm perimeter}(P) = \frac{4\pi}{3}d = \frac{4\pi}{3}\sum_{k\in I} |z_k|$$

Hence $$\sum_{k\in I} |z_k| >\frac{3}{4\pi}\sum_{k=1}^n |z_k|$$ Notice that $$\frac{1}{4\sqrt{2}} < \frac{3}{4\pi} < \frac{1}{\pi}$$

-