I am studying signed and complex measure and at a point in a proof the following lemma is being used:

Lemma. If $z_1,...,z_n$ are complex numbers, then there exists a subset $S\subset\{1,2,...,n\}$ such that $$\left|\sum_{k\in S}z_k \right| \geq \frac{1}{\pi}\sum_{k=1}^n|z_k|.$$

Does this equality have some name, or do similar kind of inequalities exist? Can the constant appearing ($1/\pi$) be sharpened?


WLOG, normalize so that $\sum|z_k|=1$. Take the subset $S_\theta$ of those $z_k$ which lie in the half-plane $\{ z:\Re (ze^{-i\theta})>0\}$. We will prove that for some $\theta$, $$\Sigma_\theta:=\left|\sum_{k\in S_\theta}z_k\right|\geq\Re\left( e^{-i\theta}\sum_{k\in S_k}z_k\right)=:\sigma(\theta)>1/\pi.$$ We have $$\sigma(\theta)=\sum_{k}|z_k|\cos^+(\phi_k-\theta),$$ where $\cos^+x=\max\{0,\cos x\}$, and $\phi_k=\arg z_k$, and summation is over all $k$. Now notice that $$\frac{1}{2\pi}\int_0^{2\pi}\sigma(\theta)d\theta=\frac{1}{2\pi}\sum_k|z_k|\int_0^{2\pi}\cos^+(t)dt=\frac{1}{\pi}.$$ This implies that $\sigma(\theta)\geq 1/\pi$ at some point. Equality is only possible when $\sigma$ is constant, but evidently it is not constant. Therefore, we have a strict inequality. It is clear from this proof that the estimate $1/\pi$ is also best possible, if $n$ is not restricted.

For fixed $n$ you can do better.

I do not know whether this has a name but this is a nice calculus problem, and it also demonstrates a simple and useful principle. (I learned of this problem in 1976 as an olimpiad problem).

  • $\begingroup$ is there an easy geometric interpretation for your proof. $\endgroup$ – abel Mar 29 '15 at 18:10
  • $\begingroup$ Of course. Trying to find a subset with largest sum, it is evident that the best thing you can do is to take those vectors which lie in some half-plane. $\endgroup$ – Alexandre Eremenko Mar 29 '15 at 18:45

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.