Multipliers preserving series convergence

The Comparison Test shows that if {\sum a_n} is an absolutely convergent series, and {\{b_n\}} is a bounded sequence, then {\sum a_nb_n} converges absolutely. Indeed, {|a_nb_n|\le M|a_n|} where {M} is such that {|b_n|\le M} for all {n}.

With a bit more effort one can prove that this property of preserving absolute convergence is equivalent to being a bounded sequence. Indeed, if {\{b_n\}} is unbounded, then for every {k} there is {n_k} such that {|b_{n_k}|\ge 2^k}. We can ensure {n_k > n_{k-1}} since there are infinitely many candidates for {n_k}. Define {a_n=2^{-k}} if {n = n_k} for some {k}, and {a_n=0} otherwise. Then {\sum a_n} converges but {\sum a_nb_n} diverges because its terms do not approach zero.

What if we drop “absolutely”? Let’s say that a sequence {\{b_n\}} preserves convergence of series if for every convergent series {\sum a_n}, the series {\sum a_n b_n} also converges. Being bounded doesn’t imply this property: for example, {b_n=(-1)^n} does not preserve convergence of the series {\sum (-1)^n/n}.

Theorem. A sequence {\{b_n\}} preserves convergence of series if and only if it has bounded variation, meaning {\sum |b_n-b_{n+1}| } converges.

For brevity, let’s say that {\{b_n\}} is BV. Every bounded monotone sequence is BV because the sum {\sum |b_n-b_{n+1}| } telescopes. On the other hand, {(-1)^n} is not BV, and neither is {(-1)^n/n}. But {(-1)^n/n^p} is for {p>1}. The following lemma describes the structure of BV sequences.

Lemma 1. A sequence {\{b_n\}} is BV if and only if there are two increasing bounded sequences {\{c_n\}} and {\{d_n\}} such that {b_n=c_n-d_n} for all {n}.

Proof. If such {c_n,d_n} exist, then by the triangle inequality \displaystyle \sum_{n=1}^N |b_n-b_{n+1}| = \sum_{n=1}^N (|c_n-c_{n +1}| + |d_{n+1}-d_n|) = \sum_{n=1}^N (c_{n+1}-c_n) + \sum_{n=1}^N (d_{n+1}-d_n) and the latter sums telescope to {c_{N+1}-c_1 + d_{N+1}-d_1} which has a limit as {N\rightarrow\infty} since bounded monotone sequences converge.

Conversely, suppose {\{b_n\}} is BV. Let {c_n = \sum_{k=1}^{n-1}|b_k-b_{k+1}|}, understanding that {c_1=0}. By construction, the sequence {\{c_n\}} is increasing and bounded. Also let {d_n=c_n-b_n}; as a difference of bounded sequences, this is bounded too. Finally,

\displaystyle d_{n+1}-d_n = c_{n+1} -c_n + b_n - b_{n+1} = |b_n-b_{n+1}|+ b_n - b_{n+1} \ge 0

which shows that {\{d_n\}} is increasing.

To construct a suitable example where {\sum a_nb_n} diverges, we need another lemma.

Lemma 2. If a series of nonnegative terms {\sum A_n} diverges, then there is a sequence {c_n\rightarrow 0} such that the series {\sum c_n A_n} still diverges.

Proof. Let {s_n = A_1+\dots+A_n} (partial sums); then {A_n=s_n-s_{n-1}}. The sequence {\sqrt{s_n}} tends to infinity, but slower than {s_n} itself. Let {c_n=1/(\sqrt{s_n}+\sqrt{s_{n-1}})}, so that {c_nA_n = \sqrt{s_n}-\sqrt{s_{n-1}}}, and we are done: the partial sums of {\sum c_nA_n} telescope to {\sqrt{s_n}}.

Proof of the theorem, Sufficiency part. Suppose {\{b_n\}} is BV. Using Lemma 1, write {b_n=c_n-d_n}. Since {a_nb_n = a_nc_n - a_n d_n}, it suffices to prove that {\sum a_nc_n} and {\sum a_nd_n} converge. Consider the first one; the proof for the other is the same. Let {L=\lim c_n} and write {a_nc_n = La_n - a_n(L-c_n)}. Here {\sum La_n} converges as a constant multiple of {\sum a_n}. Also, {\sum a_n(L-c_n)} converges by the Dirichlet test: the partial sums of {\sum a_n} are bounded, and {L-c_n} decreases to zero.

Proof of the theorem, Necessity part. Suppose {\{b_n\}} is not BV. The goal is to find a convergent series {\sum a_n} such that {\sum a_nb_n} diverges. If {\{b_n\}} is not bounded, then we can proceed as in the case of absolute convergence, considered above. So let’s assume {\{b_n\}} is bounded.

Since {\sum_{n=1}^\infty |b_n-b_{n+1}|} diverges, by Lemma 2 there exists {\{c_n\} } such that {c_n\rightarrow 0} and {\sum_{n=1}^\infty c_n|b_n-b_{n+1}|} diverges. Let {d_n} be such that {d_n(b_n-b_{n+1}) = c_n|b_n-b_{n+1}|}; that is, {d_n} differs from {c_n} only by sign. In particular, {d_n\rightarrow 0}. Summation by parts yields

\displaystyle { \sum_{n=1}^N d_n(b_n-b_{n+1}) = \sum_{n=2}^N (d_{n}-d_{n-1})b_n + d_1b_1-d_Nb_{N+1} }

As {N\rightarrow\infty}, the left hand side of does not have a limit since {\sum d_n(b_n-b_{n+1})} diverges. On the other hand, {d_1b_1-d_Nb_{N+1}\rightarrow d_1b_1} since {d_N\rightarrow 0} while {b_{N+1}} stays bounded. Therefore, {\lim_{N\rightarrow\infty} \sum_{n=2}^N (d_{n}-d_{n-1})b_n} does not exist.

Let {a_n= d_n-d_{n-1}}. The series {\sum a_n} converges (by telescoping, since {\lim_{n\rightarrow\infty} d_n} exists) but {\sum a_nb_n} diverges, as shown above.

In terms of functional analysis the preservation of absolute convergence is essentially the statement that {(\ell_1)^* = \ell_\infty}. Notably, the {\ell_\infty} norm of {\{b_n\}}, i.e., {\sup |b_n|}, is the number that controls by how much {\sum |a_nb_n|} can exceed {\sum |a_n|}.

I don’t have a similar quantitative statement for the case of convergence. The BV space has a natural norm too, {\sum |b_n-b_{n-1}|} (interpreting {b_0} as {0}), but it’s not obvious how to relate this norm to the values of the sums {\sum a_n} and {\sum a_nb_n}.

Iterating the logistic map: limsup of nonperiodic orbits

Last time we found that when a sequence with {x_1\in (0,1)} and {x_{n+1} = 4x_n(1-x_n)} does not become periodic, its upper limit {\limsup x_n} must be at least {\approx 0.925}. This time we’ll see that {\limsup x_n} can be as low as {(2+\sqrt{3})/4\approx 0.933} and determine for which {x_1} it is equal to 1.

The quadratic polynomial {f(x)=4x(1-x)} maps the interval {[0,1]} onto itself. Since the linear function {g(x) = 1-2x} maps {[0,1]} onto {[-1,1]}, it follows that the composition {h=g\circ f\circ g^{-1}} maps {[-1,1]} onto {[-1,1]}. This composition is easy to compute: {h(x) = 2x^2-1 }.

We want to know whether the iteration of {f}, starting from {x_1}, produces numbers arbitrarily close to {1}. Since {f\circ f \circ \cdots \circ f = g^{-1}\circ h \circ h \circ \cdots \circ h\circ g} the goal is equivalent to finding whether the iteration of {h}, starting from {g(x_1)}, produces numbers arbitrarily close to {g(1) = -1}. To shorten formulas, let’s write {h_n} for the {n}th iterate of {h}, for example, {h_3 = h\circ h\circ h}.

So far we traded one quadratic polynomial {f} for another, {h}. But {h} satisfies a nice identity: {h(\cos t)=2\cos^2 t-1 = \cos(2t)}, hence {h_n(\cos t) = \cos (2^n t)} for all {n\in\mathbb N}. It’s convenient to introduce {\alpha = \frac{1}{\pi}\cos^{-1}(1-2x_1)}, so that { h_n(g(x_1)) = h_n(\cos 2\pi \alpha ) = \cos(2^n\cdot 2\pi \alpha) }.

The problem becomes to determine whether the numbers {2^n\cdot 2\pi \alpha} come arbitrarily close to {\pi}, modulo an integer multiple of {2\pi}. Dividing by {2\pi} rephrases this as: does the fractional part of {2^n \alpha} come arbitrarily close to {1/2}?

A number that is close to {1/2} has the binary expansion beginning either with {0.01111111\dots} or with {0.10000000\dots}. Since the binary expansion of {2^n\alpha} is just the binary expansion of {\alpha} shifted {n} digits to the left, the property {\limsup x_n=1} is equivalent to the following: for every {k\in\mathbb N} the binary expansion of {\alpha} has infinitely many groups of the form “1 followed by k zeros” or “0 followed by k ones”.

A periodic expansion cannot have the above property; this, {\alpha} must be irrational. The property described above can then be simplified to “irrational and has arbitrarily long runs of the same digit”, since a long run of {0}s will be preceded by a {1}, and vice versa.

For example, combining the pairs 01 and 10 in some non-periodic way, we get an irrational number {\alpha} such that the fractional part of {2^n\alpha} does not get any closer to 1/2 than {0.01\overline{10}_2 = 5/12} or {0.10\overline{01}_2 = 7/12}. Hence, {\cos 2^n 2\pi \alpha \ge -\sqrt{3}/2}, which leads to the upper bound {x_n\le (2+\sqrt{3})/4\approx 0.933} for the sequence with the starting value {x_1=(1-\cos\pi\alpha)/2}.

Let us summarize the above observations about {\limsup x_n}.

Theorem: {\limsup x_n=1} if and only if (A) the number {\alpha = \frac{1}{\pi}\cos^{-1}(1-2x_1)} is irrational, and (B) the binary expansion of {\alpha} has arbitrarily long runs of the same digit.

Intuitively, one expects that a number that satisfies (A) will also satisfy (B) unless it was constructed specifically to fail (B). But to verify that (B) holds for a given number is not an easy task.

As a bonus, let’s prove that for every rational number {y\in (-1,1)}, except 0, 1/2 and -1/2, the number {\alpha = \frac{1}{\pi}\cos^{-1}y} is irrational. This will imply, in particular, that {x_1=1/3} yields a non-periodic sequence. The proof follows a post by Robert Israel and requires a lemma (which could be replaced with an appeal to Chebyshev polynomials, but the lemma keeps things self-contained).

Lemma. For every {n\in \mathbb N} there exists a monic polynomial {P_n} with integer coefficients such that {P_n(2 \cos t) = 2\cos nt } for all {t}.

Proof. Induction, the base case {n=1} being {P_1(x)=x}. Assuming the result for integers {\le n}, we have {2 \cos (n+1)t = e^{i(n+1)t} + e^{-i(n+1)t} } {  = (e^{int} + e^{-int})(e^{it} + e^{-it}) - (e^{i(n-1)t} + e^{-i(n-1)t}) } { = P_n(2 \cos t) (2\cos t) - P_{n-1}(2\cos t) }
which is a monic polynomial of {2\cos t}. {\Box}

Suppose that there exists {n} such that {n\alpha \in\mathbb Z}. Then {2\cos(\pi n\alpha)=\pm 2}. By the lemma, this implies {P_n(2\cos(\pi \alpha)) =\pm 2}, that is {P_n(2y)=\pm 2}. Since {2y} is a rational root of a monic polynomial with integer coefficients, the Rational Root Theorem implies that it is an integer. {\Box}

A limsup exercise: iterating the logistic map

Define the sequence {\{x_n\}} as follows: {x_1=1/3} and {x_{n+1} = 4x_n(1-x_n)} for {n=1,2,\dots}. What can we say about its behavior as {n\rightarrow\infty}?

The logistic map {f(x)=4x(1-x)} leaves the interval [0,1] invariant (as a set), so {0\le x_n\le 1} for all {n}. There are two fixed points: 0 and 3/4.

Two fixed points of the logistic map: 0 and 3/4

Can {x_n} ever be 0? If {n} is the first index this happens, then {x_{n-1}} must be {1}. Working backwards, we find {x_{n-2}=1/2}, and {x_{n-3}\in \{1/2 \pm \sqrt{2}/4\}}. But this is impossible since all elements of the sequence are rational. Similarly, if {n} is the first index when {x_n = 3/4}, then {x_{n-1}=1/4} and {x_{n-2}\in \{1/2\pm \sqrt{3}/4\}}, a contradiction again. Thus, the sequence never stabilizes.

If {x_n} had a limit, it would have to be one of the two fixed points. But both are repelling: {f'(x) = 4 - 8x}, so {|f'(0)|=4>1 } and {|f'(3/4)| = 2 > 1}. This means that a small nonzero distance to a fixed point will increase under iteration. The only way to converge to a repelling fixed point is to hit it directly, but we already know this does not happen. So the sequence {\{x_n\}} does not converge.

But we can still consider its upper and lower limits. Let’s try to estimate {S = \limsup x_n} from below. Since {f(x)\ge x} for {x\in [0,3/4]}, the sequence {\{x_n\}} increases as long as {x_n\le 3/4}. Since we know it doesn’t have a limit, it must eventually break this pattern, and therefore exceed 3/4. Thus, {S\ge 3/4}.

This can be improved. The second iterate {f_2(x)=f(f(x))} satisfies {f_2(x)\ge x} for {x} between {3/4} and {a = (5+\sqrt{5})/8 \approx 0.9}. So, once {x_n>3/4} (which, by above, happens infinitely often), the subsequence {x_n, x_{n+2}, x_{n+4},\dots} increases until it reaches {a}. Hence {S\ge a}.

The bound {\limsup x_n\ge a} is best possible if the only information about {x_1} is that the sequence {x_n} does not converge. Indeed, {a} is a periodic point of {f}, with the corresponding iteration sequence {\{(5+ (-1)^n\sqrt{5})/8\}}.

Further improvement is possible if we recall that our sequence is rational and hence cannot hit {a} exactly. By doubling the number of iterations (so that the iterate also fixes {a} but also has positive derivative there) we arrive at the fourth iterate {f_4}. Then {f_4(x)\ge x} for {a\le x\le b}, where {b } is the next root of {f_4(x)-x} after {a}, approximately {0.925}. Hence {S\ge b}.

Stacking the iterates

This is a colorful illustration of the estimation process (made with Sage): we are covering the line {y=x} with the iterates of {f}, so that each subsequent one rises above the line the moment the previous one falls. This improves the lower bound on {S} from 0.75 to 0.9 to 0.92.

Although this process can be continued, the gains diminish so rapidly that it seems unlikely one can get to 1 in this way. In fact, one cannot because we are not using any properties of {x_1} other than “the sequence {x_n} is not periodic.” And it’s not true that {\limsup x_n = 1} for every non-periodic orbit of {f}. Let’s return to this later.

Sequences and nets

According to the (Banach-)Alaoglu theorem, for any Banach space X the closed unit ball of X^* is compact in the weak* topology (the weakest/coarsest topology that makes all evaluation functionals f\mapsto f(x) continuous).

For example, take X=\ell_{\infty}. The dual space \ell_{\infty}^* contains an isometric copy of \ell_1 because \ell_\infty^*=\ell_1^{**}. The sequence x_n=n^{-1}(e_1+\dots+e_n), where e_n are the standard basis vectors, is contained in the unit sphere of \ell_1. Should (x_n) have a weak*-convergent subsequence? Maybe it should, but it does not.

Indeed, take any subsequence (x_{n_k}). If necessary, choose a further subsequence so that n_{k+1}\ge 3n_k for all k. Define

\displaystyle y=\sum_{k}(-1)^k\sum_{n_{k-1}< j\le n_k} e_j

where we set n_0=0. Two things to notice here: (1) y\in \ell_{\infty}; and (2) at least 2/3 of the coefficients of e_j, 1\le j\le n_k, have the sign (-1)^k. Hence, \langle x_{n_k},y\rangle\le -1/3 when k is odd and \langle x_{n_k},y\rangle\ge 1/3 when k is even. This shows that (x_{n_k}) does not converge in the weak* topology.

The above does not contradict the Banach-Alaoglu theorem. Since \ell_\infty is not separable, the weak* topology on the unit ball of its dual is not metrizable. The compactness can be stated in terms of nets instead of sequences: every bounded net in X^* has a convergent subnet. In particular, the sequence (x_n) has a convergent subnet (which is not a sequence). I personally find subnets a recipe for erroneous arguments. So I prefer to say: the infinite set \{x_n\} has a cluster point x; namely, every neighborhood of x contains some x_n. You can use the reverse inclusion of neighborhoods to define a subnet, but I’d rather not to. Everything we want to know about x can be easily proved from the cluster point definition. For example,

  • \|x\|_{X^*}=1
  • \langle x, 1_{\infty}\rangle =1 where 1_{\infty} stands for the \ell_\infty vector with all coordinates 1.
  • \langle x, y\rangle = \langle x, Sy\rangle where S is the shift operator on \ell_\infty