most recent 30 from http://mathoverflow.net 2013-05-24T01:31:58Z http://mathoverflow.net/feeds/question/98288 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/98288/bounding-a-signed-sum-of-complex-numbers Someone 2012-05-29T15:17:11Z 2012-05-29T18:50:33Z

<p>Let $z_i \in \mathbb{C}\:$ for $i=1,\dots, n\;$ be complex numbers, all with absolute value $|z_i|\le 1\;$.</p> <p>Prove (or disprove) that there exists a choice of signs $s_i \in \{\pm 1\}$ such that $$\left|\sum_{i=1}^n s_i\cdot z_i\right| \le \sqrt{2}.$$</p> <p>[My interest in this problem is purely for fun. I couldn't solve it a long time ago, forgot about it, but shortly ago it came back into my mind again.]</p>

http://mathoverflow.net/questions/98288/bounding-a-signed-sum-of-complex-numbers/98297#98297 js 2012-05-29T18:44:12Z 2012-05-29T18:50:33Z

<p>What follows is not an answer, but is too long for a comment.</p> <p>This problem and its natural higher-dimensional generalization is connected with the recent MO questions <a href="http://mathoverflow.net/questions/98007/covering-a-unit-ball-with-balls-half-the-radius" rel="nofollow">Covering a unit ball with balls half the radius</a> and <a href="http://mathoverflow.net/questions/97939/" rel="nofollow">covering disks with smaller disks</a> : let $K_d$ be the smallest constant such that for any sequence $(z_i)_{i \geq 1}$ of vectors of $\mathbb{R}^d$ of (euclidean) norm at most one, there's some choice of signs $s_i = \pm 1$ such that the partial sums $\sum_{1 \leq i \leq n} s_i z_i$ are all bounded by $K_d$.</p> <p>Now let $N_d$ be the minimal number of balls of radius $\frac{1}{2}$ needed to cover a ball of radius $1$ (in $\mathbb{R^d}$). I claim that $K_d \leq N_d$.</p> <p>Proof : Let $K_{d,n}$ be the same constant as $K_d$, but for which we require only the first $n$ partial sums to be bounded by $K_{d,n}$. Then a straightforward averaging argument yields $K_{d,n} \leq \sqrt{n} \leq n$. Now let $n > N_d$. Fixing a covering of the unit ball with $N_d$ balls of radius $\frac{1}{2}$, then there must be two distinct $ i &lt; j \leq N_d +1$ such that $z_i$ and $z_j$ lie in the same ball of radius $\frac{1}{2}$, and hence must satisfy $|| z_i - z_j || \leq 1$. If we replace $z_j$ by $z_j - z_i$, suppress $z_i$, and then use $K_{d,n-1}$, we get a sequence of signs which achieve $K_{d,n} \leq \max ( N_d, K_{d,n-1} ) $. But Kônig's lemma (for infinite binary trees) gives $K_d \leq \sup_{n} K_{d,n} $, hence the desired result.</p>