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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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