# If $a_n$ goes to zero, can we find signs $s_n$ such that $\sum s_n a_n$ converges?

Let $a_n$ be a sequence of complex numbers that converge to zero. Can we always find $s_n \in \{-1,1\}$ such that $\sum_{n=1}^{\infty} s_n a_n$ converges?

If the $a_n$ are real numbers, we can find such a sequence $s_n$. If the partial sum of the first $N$ terms is positive we make sure the following terms are negative until the sum becomes less than zero. Then we switch to making the terms positive until the partial sum becomes greater than zero, and so on. It is easy to see that the partial sums will either tend monotonically towards zero, or oscillate around zero with decreasing amplitude.

Edit: Actually there is no reason that the partials sums should go to zero in the monotone case. They will still converge however.

-
For the real sequence $a_n=1/3^n$, the partial sums neither tend monotonically towards zero, nor oscillate around zero with decreasing amplitude. They will converge, but to a non-zero number. –  Henry May 23 '12 at 9:32
Aha - I have a solution, and I'll write it this afternoon. –  mixedmath May 29 '12 at 11:00

Note: I had written this proof before the other answers were posted. I was about to discard it because the idea is actually the same as mixedmath's answer, but his answer has a small issue because it only proves the theorem for $k=n$, which can only prove that a subsequence of $b_n$ converges, not the whole sequence. So here is a hopefully correct proof.

First we prove the following theorem:

Theorem: For any finite sequence $a$ bounded by $M$, we can find signs $s$ so that $\left|\sum_{i=1}^k s_i a_i\right| \le 2M$ for all $k\le n$.

We say that $a$ and $b$ on the unit disk are compatible when either $a+b$ or $a-b$ lies on the unit disk.

Lemma: If $a,b,c$ lie on the unit disk, at least one of $(a,b)$, $(b,c)$ or $(a,c)$ is a compatible pair.

Proof. When $|a+b|>1$ with $a$ and $b$ in the unit disk, we also have $\left|\frac{a}{|a|}+\frac{b}{|b|}\right|>1$ and therefore the arguments of $a$ and $b$ differ by less than $2\pi/3$ (mod $2\pi$). Thus $a$ and $b$ are incompatible iff $\arg a - \arg b\in (-2\pi/3,-\pi/3)\cup(\pi/3,2\pi/3)$ (mod $2\pi$), which shows that $a,b,c$ cannot all be pairwise incompatible.

Lemma: For any finite sequence $a_1,\dots a_n$ with $a_i$ in the unit disk, we can find signs $s_1,\dots s_n$ and $t_1,\dots t_n$ so that for all $k\le n$, $\left|\sum_{i=1}^k s_i a_i\right|\le 2$, $\left|\sum_{i=1}^k s_i t_i a_i\right|\le 2$ and for each $\epsilon\in\{-1,1\}$, $u_\epsilon = \sum\limits_{\substack{i\le n\\t_i=\epsilon}} s_i a_i$ lies on the unit disk.

Proof. This is of course true for $n\le 2$. We continue by induction: assume we have built $s_1,\dots s_n$ so that the lemma applies. Then if $u_1$ and $u_{-1}$ are incompatible, $a_{n+1}$ is compatible with some $u_\epsilon$ so that we can find $s_{n+1}$ such that $u_\epsilon+s_{n+1}a_{n+1}$ lies on the unit disk, and letting $t_{n+1}=\epsilon$ finishes the proof. If $u_1$ and $u_{-1}$ are compatible so that $u_1+\epsilon~u_{-1}$ lies on the unit disk, we can pick any $s'_{n+1}$ and $t'_{n+1}$, and for $i\le n$ define $t'_i=-t'_{n+1}$ and $s'_i=s_i$ if $\epsilon=1$ and $s'_i=s_i t_i$ if $\epsilon=-1$.

We obtain the theorem as a corollary.

Now take an infinite sequence $a_n$ converging to 0. Let $n_i$ be an increasing sequence of integers such that $|a_n|<2^{-i}$ when $n\ge n_i$. We simply apply the theorem to each subpart $a_{n_i+1},\dots,a_{n_i}$ to define the sequence $s$. We can let $s_n=1$ for $n<n_1$.

Then we can prove that $b_n=\sum_{k=1}^n s_k a_k$ is a Cauchy sequence: for any $\varepsilon>0$, pick $i_0$ so that $4\cdot 2^{-i_0}\le \varepsilon$. Then for $n\ge N=n_{i_0}$, $|b_n-b_N|=|\sum_{k=N+1}^n s_k a_k|\le \sum_{i\ge i_0} 2\cdot 2^{-i}\le \varepsilon$.

So $b_n$ converges. $\square$

## Can we improve the bound in the theorem?

Someone asked what the sharpest bound for the theorem was. If we restrict to the $k=n$ case, this is $\sqrt 2 M$. We have $\min(|a+b|^2,|a-b|^2) = |a|^2+|b|^2-2|a\cdot b|\le 2$ for $a,b$ in the unit disk ($\cdot$ is the scalar product). Since the lemma happens to prove that the sum can be indifferently written as $u_1+u_{-1}$ or $u_1-u_{-1}$ with $u_\epsilon$ in the unit disk, this proves the bound. The bound is sharp for $n\ge 2$: take $(a_1,\dots a_n)=(1,i,0,0,\dots)$.

However $\sqrt 2 M$ cannot be used to bound partial sums ($k<n$) when the set of signs is not allowed to vary: indeed for $a=1$, $b=\exp(i\pi/3+\varepsilon)$, $c=-\exp(i\pi/6)$, $|a+b+c|\le \sqrt 2$ is the only set of signs ensuring the bound, but $|a+b|=\sqrt 3-\varepsilon'>\sqrt 2$.

## Does the theorem work in higher dimensions?

Yes! Call the dimension $p$. When $a$ and $b$ are incompatible with $a,b$ in the unit $(p-1)$-sphere, the distance between $a$ and $b$ is bounded from below (by 1). This means there is an upper bound $N$ to the size of pairwise incompatible sets on the unit $(p-1)$-sphere, and therefore also on the unit ball because $a\mapsto a/\|a\|$ preserves incompatible pairs (a consequence of the fact that $\|ta-b\|$ is a convex function of $t$ with value at most 1 for $t=0$). Then the proof of the second lemma still holds, using a partition of $1,\dots n$ into $N$ subsets and requiring that for all assignments of a sign to each subset, the sum be bounded by $N$.

-
Great! That's exactly what I was going to write up. Great minds... –  mixedmath May 29 '12 at 14:49
so the lemma is essentially saying that we can split a finite sequence into two subsequences where each sum is contained in the unit disk for every $n$ ? In the second case of the proof, where you merge the two old subsequences into a new one and make $a_{n+1}$ into the other new one, I think you can't show that the new subsequence stays in the unit disk for all $n$. –  mercio May 29 '12 at 15:13
No, the unit disk property only applies to the full sequence ($k=n$). It's basically just an induction hypothesis to be able to apply the compatible pair lemma, so that's why we can erase all information about $t_i$ for $i\le n$. If for some reason you wanted to keep all the information, you could build a forest of at most two binary trees where the leaves are $s_1 a_1,\dots s_n a_n$ and where each subtree has a sum lying in the unit disk. The two cases in the proof then become very much alike: we have 3 trees and combine two of them, flipping the sign of a whole subtree if necessary. –  Generic Human May 29 '12 at 15:38
ah I see what I misread and I think I get it. It's very nice ! –  mercio May 29 '12 at 16:27

I like this problem very much. To be honest, I was first trying to show that it is not true by coming up with a clever counterexample, designed around fooling Henry's answer. But to cut that vein short, couldn't.

If I may boil down the entire proof into 2 statements:

1. Given a finite sequence $z_1, \dots, z_k$ of $k$ complex numbers with $|z_i| < M$ for all $i$, then there exists a constant $K(M) = K \in \mathbb{R}$ independent of the length of the sequence $k$ and a set of signs $s_i \in \{-1, 1\}$ s.t. $|s_1z_1 + \dots s_kz_k| < K$
2. Break a given sequence $\{z_i\}_{i \in \mathbb{N}}$ with $z_i \to 0$ into finite subsequences $\{z_{n_i}\}_{i \in I}$ with $|I|$ finite and with $|z_{n_j}| < 2^{-n}$ for each $j \in I$, and so that each $z_i$ is included in exactly one of the finite subsequences. Then applying the bound from above, we get the result.

So we now have a plan to follow.

Proof of [1.]: ($\spadesuit$)

Note that if $z_1, z_2$ are two complex units, then there are signs $s_i$ s.t. $|s_1z_1 + s_2z_2| \leq \sqrt 2 \leq 2$ (where $\sqrt 2$ is optimal, but where I only use $2$ because I can state it relying on trivial proof). Similarly, if $z_1, z_2$ have $|z_1|, |z_2| \leq M$, then there are signs $s_i$ s.t. $|s_1z_1 + s_2z_2| \leq 2M$.

Lemma: ($\diamondsuit$) If $z_1, z_2, z_3$ are three complex units, then we can always choose two of them (say $z_1, z_2$) s.t. $|z_1 + z_2|\leq 1$ or $|z_1 - z_2|\leq 1$

Proof: Assume not. Then $z_1$ must have an angle of between $60^\circ$ and $120^\circ$ with each of $z_2$ and $z_3$. But then it's easy to show that $z_2$ or $-z_2$ will have a relative angle less than $60^\circ$ with $z_3$. Thus $|z_3 + z_2| \leq 1$ or $|z_3 - z_2| \leq 1$. Contradiction. $\diamondsuit$

So given a finite sequence of complex numbers $z_1, \dots, z_k$, with $k \geq 3$ and $|z_i| \leq 1$, we may inductively choose signs to bound pairs $z_\alpha, z_\beta$ by a single element $z_\gamma$ satisfying $|z_\gamma| \leq 1$, until we are left with only 2 elements. But then we may apply the trivial bound first mentioned. So we have that there are signs so that $|s_1 z_1 + \dots + s_k z_k| \leq 2$. Scaling, we get the general result ($\leq 2M$ where $M$ is the bound on the $|z_i|$). $\spadesuit$

So given a finite sequence, we can choose signs to bound the sum irrespective of the (finite) length of the sequence. Now we use this on our infinite sequence.

Proof of the main result: ($\clubsuit$)

So we have a sequence $z_1, z_2 , \dots$ with $|z_i| \to 0$. I'm going to abuse a bit of notation here. Then for each $n \in \mathbb{N}$, there is a lowest index which I denote by $n_1$ so that $|z_i| > 2^{-n}$ for some $i < n_1$ and $|z_j| \leq 2^{-n}$ for all $j \geq n_1$. Then the elements sequentially between $z_{n_1}$ and $z_{(n+1)_1}$ can be relabelled as $z_{n_2}, z_{n_3}, \dots, z_{n_l}$, and there are finitely many numbers in each. For ease, denote the set of elements with index $1_j$ for some $j$ by $I_j$, so that $z_{1_1}, z_{1_2} \in I_1, z_{3_5} \in I_3$, etc.

So now, we are essentially done. Tossing aside the (finitely many) initial terms before $z_{1_1}$, we know that there are signs that can be given to $z_i \in I_j$ so that $|\sum_{I_j} z_i| < 2\cdot 2^{-j}$ for every $j$, and that the $I_j$ evenly cover the entire sequence $\{z_i\}$ in order. As $2\sum 2^{-j}$ converges, the triangle inequality gives us that our sequence converges as well. $\clubsuit$

EDIT

As Johan points out below, there is a detail missing. I was in the process of writing a completed solution when I noticed that my missing detail is included in Generic Human's post, and in the exact way I was going to do it. So I defer the missing detail.

-
Don't you need your lemma to hold when $|z_i| \le 1$ and are not necessarily units ? I think the proof of the lemma should stay correct in that case. –  mercio May 29 '12 at 13:11
@mercio: the exact same proof holds. Just scale everything. The last line of the proof of the lemma says exactly that. But you're right - we need the general result. –  mixedmath May 29 '12 at 13:12
My answer (posted minutes after yours) is very similar, but I feel my lemma is cleaner than yours. –  Ewan Delanoy May 29 '12 at 13:33
Nice. Just one question: you bound $|\sum_{I_j} z_i|$. Don't we need to bound sums over subsets of $I_j$ as well? –  Johan May 29 '12 at 13:37
@Ewan: That's okay. I like my lemma, and I like that it's self-contained. In fact, its geometric nature allows the result to be generalized (to higher dimensions), and I think I'm going to blog about it. If I remember, I'll post a link here when I do. –  mixedmath May 29 '12 at 13:39

The answer to your question is YES, we can always find a sequence of signs that makes the series convergent. The greedy construction in Henry's answer must be applied not once, but a countable number of times, on carefully chosen integer intervals.

We need the following lemma :

LEMMA. Let $b_1, \ldots ,b_r$ be complex numbers. Let $M={\sf max}(|b_1|,|b_2|, \ldots ,|b_r|)$. Then there is a sequence of signs $\epsilon_1,\epsilon_2, \ldots ,\epsilon_r$ with each $\varepsilon_k = \pm 1$ such that the $r$ numbers $c_1,,c_2, \ldots ,c_r$ defined by $c_k=\sum_{j=1}^k \varepsilon_k b_k$ all satisfy $|c_k| \leq M$.

This lemma is easily shown by an inductive step-by-step "greedy" construction, as in Henry's answer : the key property is that, if $|x|$ and $|y|$ are both $\leq M$, then at least one of $|x-y|$ or $|x+y|$ is $\leq M$ also. (otherwise we would deduce $2M < |x-y|+|x+y| \leq 2|x|$).

Since $(a_n)$ converges to zero, there is an increasing function $\phi : {\mathbb N} \to {\mathbb N}$ such that

$$\forall t, \ \forall n \geq \phi(t), \ |a_n| \leq \frac{1}{2^t}$$

By lemma, for each $t$ there are signs $\epsilon_{\phi(t)+1},\epsilon_{\phi(t)+2}, \ldots ,\epsilon_{\phi(t+1)}$ such that, if we put $d_j=\epsilon_ja_j$ and $e_k=\sum_{j=\phi(t)+1}^k d_j$, then $|e_k| \leq \frac{1}{2^t}$ for each $k$ such that $\phi(t) \leq k \lt \phi(t+1)$.

Concatenating all those finite sequences of signs, we obtain an infinite sequence of sequence $(\epsilon_n)_{n\geq 0}$ with the following property : if we put $s_n=\sum_{k=1}^n \epsilon_k a_k$, then

$$\forall t, \forall n \ {\rm such \ that \ } \phi(t) \leq n \lt \phi(t+1), \ \ \big|s_n-s_{\phi(t)}\big| \leq \frac{1}{2^t}$$

Let $t$ be an integer, let $n \geq \phi(t)$ and let $u$ be the largest integer satisfying $\phi(u) \leq n$. Then we have

$$\big|s_n-s_{\phi(t)}\big| \leq \big|s_{\phi(u)}-s_{\phi(t)}\big|+\big|s_n-s_{\phi(u)}\big| \leq \bigg(\sum_{j=t+1}^{u} \big|s_{\phi(j)}-s_{\phi(j-1)}\big|\bigg)+\big|s_n-s_{\phi(u)}\big| \leq \sum_{k=t}^{\infty} \frac{1}{2^{k}} = \frac{1}{2^{t-1}}$$

So for any tow indices $n,m \geq \phi(t)$ we have $$|s_n-s_m| \leq |s_n-s_{\phi(t)}|+|s_n-s_{\phi(t)}| \leq \frac{1}{2^{t-2}}$$

So $(s_n)$ is a Cauchy sequence, and $(s_n)$ covnerges as wished.

-
I do not understand your claim that one of $|x+ y|$ and $|x-y|$ must be less than $M$. What if $x,y$ are orthogonal and both of length $M$? –  Johan May 29 '12 at 13:26
@Johan : You're right, I made a mistake there. Mixedmath's answer shows that this flaw can be settled. I wonder however what is the "optimal" K(M). –  Ewan Delanoy May 29 '12 at 13:57
@EwanDelanoy: For the greedy construction you get in the proof of your lemma the limit $M\cdot\sqrt{r}$ (if $b_{i+1}$ is perpendicular to the result you got for being greedy on $b_1, \dots, b_i$, and all $b_i$ having the same length). –  j.p. May 30 '12 at 12:33

Yes it is possible. [But perhaps not this way - see comments - keeping for the discussion and the reference from another reply]

Let $b_n =\sum_{i=1}^n s_i a_i = b_{n-1}+s_n a_n$ represent the partial sums.

Choose $s_{n+1} = 1$ when $|b_n + a_{n+1}| \le |b_n - a_{n+1}|$, and $s_{n+1} = -1$ when $|b_n + a_{n+1}| \gt |b_n - a_{n+1}|$.

Then the real sequence $c_n = |b_n|-|b_{n-1}|$ has $|c_n| \le |a_n|$, meeting your condition for reals converging to $0$ and has the signs you desire. So the partial sums of $c_n$ converge to a finite constant and, using the triangle inequality, so do the partial sums $b_n =\sum_{i=1}^n s_i a_i$.

-
I do not think your argument works. Pick $a_1=1$ and for every $n$ choose $a_{n+1}$ so that $\sum_{k=1}^n a_k+a_{n+1}$ lies on the unit circle, $a_{n+1}$ points in the clockwise direction from $\sum_{k=1}^n a_k$ and $|a_{n+1}| = n^{-1}$. If I am not mistaken we will then always get $s_{n+1}=1$ using your method, and the partial sums $b_n$ will go around the unit circle infinitely many times. –  Johan May 23 '12 at 11:10
@Johan: That is an interesting point and reminds me of the Lion and Christian problem. I suspect that you might be able to find a similar counter-example to any deterministic algorithm looking at earlier $a_i$, so perhaps a non-deterministic algorithm might work. –  Henry May 23 '12 at 22:03
You should edit your answer to point out that it is flawed. –  TonyK May 29 '12 at 9:46