Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
5  
(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 4

up vote 16 down vote accepted
+50

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.

share|improve this answer
3  
+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? –  no identity 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} $$

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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