Consider the following problem.

Fix $n \in \mathbb N$. Prove that for every set of complex numbers $\{z_i\}_{1\le i \le n}$, there is a subset $J\subset \{1,\dots , n\}$ such that

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

I believe I proven have a stronger statement. Is this proof correct, and if so, what is the optimal constant?

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.

  • $\begingroup$ Do you know how to prove the inequality, or is that part of your question? $\endgroup$ – Srivatsan Dec 16 '11 at 5:27
  • $\begingroup$ I believe I have proved a stronger statement, so an example of equality would furnish a counterexample. $\endgroup$ – Potato Dec 16 '11 at 5:28
  • 5
    $\begingroup$ (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? $\endgroup$ – Srivatsan Dec 16 '11 at 5:29
  • $\begingroup$ 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. $\endgroup$ – msh210 Dec 16 '11 at 8:31

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.

  • 3
    $\begingroup$ +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$? $\endgroup$ – Srivatsan Dec 16 '11 at 7:59
  • $\begingroup$ 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$ $\endgroup$ – robjohn Dec 16 '11 at 8:25
  • $\begingroup$ @Robert Israel Amazing! Did you knew that or proved by yourself? $\endgroup$ – Norbert Jan 25 '12 at 19:14
  • $\begingroup$ I proved it myself, although I've seen similar things before (certainly the techniques involved are well-known). $\endgroup$ – Robert Israel Jan 25 '12 at 22:40
  • 1
    $\begingroup$ @Norbert - The proof of Lemma 6.3 in Walter Rudin, "Real and Complex Analysis", uses the same techniques, but is clumsier than the proof given by Robert Israel. $\endgroup$ – chizhek Sep 1 '14 at 10:05

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*}

  • $\begingroup$ I believe there's a typo in the first inequality: the sum shojld be only over the indices with positive $Im(z_k e^{ix})$ instead of over all indices. $\endgroup$ – Emolga Aug 8 '16 at 21:15

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 :) enter image description here

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}$$


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.