414/514 The theorems of Riemann and Sierpiński on rearrangement of series

I.

Perhaps the first significant observation in the theory of infinite series is that there are convergent series whose terms can be rearranged to form a new series that converges to a different value.

A well known example is provided by the alternating harmonic series,

\displaystyle 1-\frac12 +\frac13-\frac14+\frac15-\frac16+\frac17-\dots

and its rearrangement

\displaystyle 1-\frac12-\frac14+\frac13-\frac16-\frac18+\frac15-\dots

According to

Henry Parker Manning. Irrational numbers and their representation by sequences and series. John Wiley & Sons, 1906,

Laurent evaluated the latter by inserting parentheses (see pages 97, 98):

\displaystyle \left(1-\frac12\right)-\frac14+\left(\frac13-\frac16\right)-\frac18+\left(\frac15-\frac1{10}\right)-\dots \displaystyle=\frac12\left(1-\frac12+\frac13-\frac14+\dots\right)

A similar argument is possible with the rearrangement

\displaystyle 1+\frac13-\frac12+\frac15+\frac17-\frac14+\dots,

which can be rewritten as

\displaystyle 1+0+\frac13-\frac12+\frac15+0+\frac17+\dots \displaystyle =\left(1-\frac12+\frac13-\frac14+\frac15-\frac16+\frac17-\dots\right) \displaystyle +\left(0+\frac12+0-\frac14+0+\frac16+0-\dots\right) \displaystyle =\frac32\left(1-\frac12+\frac13-\frac14+\dots\right).

The first person to realize that rearranging the terms of a series may change its sum was Dirichlet in 1827, while working on the convergence of Fourier series. (The date is mentioned by Riemann in his Habilitationsschrift, see also page 94 of Ivor Grattan-Guinness. The Development of the Foundations of Mathematical Analysis from Euler to Riemann. MIT, 1970.)

Ten years later, he published

G. Lejeune Dirichlet. Beweis des Satzes, dass jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Factor sind, unendlich viele Primzahlen enthält. Abhandlungen der Königlich Preussischen Akademie der Wissenschaften von 1837, 45-81,

where he shows that this behavior is exclusive of conditionally convergent series:

Theorem (Dirichlet). If a series converges absolutely, all its rearrangements converge to the same value.

Proof. Let u_0,u_1,\dots be the original sequence and u_{\pi(0)},u_{\pi(1)},\dots a rearrangement. Denote by U_0,U_1,\dots and V_0,V_1,\dots their partial sums, respectively. Fix \epsilon>0. We have that for any n, if m is large enough, then for all i\le n there is some j\le m with \pi(j)=i. Also, there is a k such that for all j\le m there is a i\le k with \pi(j)=i, so

|U_m-V_m|\le\sum_{i=n+1}^m|u_i|+\sum_{i=n+1}^k|u_j|.

Choosing n large enough, and using that \sum_i|u_i| converges,  we can ensure that the two displayed series add up to less than \epsilon. This gives the result. \Box

II.

In 1853, Riemann proved his rearrangement theorem, although it was not published until 1866, as part of his Habilitationsschrift on representation of functions as trigonometric series, Ueber die Darstellbarkeit einer Function durch eine trigonometrische Reihe. See here for Riemann’s papers.

Theorem (Riemann). Given any \alpha\le\beta in the extended reals, a conditionally convergent series of reals can be rearranged so that the liminf of the partial sums of the rearranged series is \alpha, while the limsup is \beta. In particular, any real can be obtained as the sum of some rearrangement of the original series.

Proof. The idea is very simple, and based on the following observation:

Lemma. If u_0,u_1,\dots is a sequence of real numbers such that \sum_i u_i conditionally converges, then, letting a_0,a_1,\dots and -b_0,-b_1,\dots, respectively, denote the subsequence of positive and of non-positive terms, we have that both sequences are infinite, both converge to zero, and for any k, we have that \displaystyle \sum_{n=k}^\infty a_n=\sum_{n=k}^\infty b_n=+\infty.

Proof. The point is that, up to padding the subsequences with zeroes at appropriate places, \sum_i |u_i|=\sum_i a_i+\sum_i b_i, so at least one of the two series must diverge, since the original series is not absolutely convergent, by assumption. If one of the series converges, then the other, being a difference of two convergent series, would converge as well. It follows that both series diverge (to +\infty). Since both the a_i and the -b_i are subsequences of u_i, which converges to 0 (since \sum_i u_i converges), then they converge to zero as well. That, in fact, \sum_{n=k} a_n diverges no matter how large k is, is immediate. \Box

Using the lemma, we prove the rearrangement theorem in a straightforward fashion. To explain the idea, suppose first that \alpha=\beta=r is real. Consider the rearrangement that first adds positive terms until the sum is larger than r, then adds non-positive terms until the sum is smaller than r, then adds positive terms again, etc, so the partial sums oscillate being larger and smaller than r, but each time by smaller amounts, since the a_i and the b_i converge to 0.

The general case follows the same outline: If \alpha is real, define \alpha_n=\alpha for all n. If \alpha=+\infty, define \alpha_n=n, and if \alpha=-\infty, define \alpha_n=-n. Define the sequence \beta_n similarly.

We define the rearrangement v_0,v_1,\dots by stages, and use V_0,V_1,\dots to denote the partial sums of the rearranged sequence.  At the beginning of stage k, we have used an initial segment a_0,\dots,a_{t_{k-1}} of the subsequence of positive terms, and an initial segment -b_0,-b_1,\dots,-b_{s_{k-1}} of the subsequence of non-positive terms, and we have defined v_0,v_1,\dots,v_{m_{k-1}} (where m_{k-1}=t_{k-1}+s_{k-1}). At stage k=0, we begin with V_{-1}=0 and t_{-1}=s_{-1}=-1. We continue the definition by setting v_{m_{k-1}+1}=a_{t_{k-1}+1}, v_{m_{k-1}+2}=a_{t_{k-1}+2}, etc, until an index n is reached such that V_{m_{k-1}}+(a_{t_{k-1}+1}+\dots+a_n)>\beta_n. Note that n exists, since \sum_{i>t_{k-1}}a_i=+\infty. We stop at the least such n, and set t_k=n. Let l_k=m_{k-1}+(n-t_{k-1}).

We continue with v_{l_k+1}=-b_{s_{k-1}+1}, v_{l_k+2}=-b_{s_{k-1}+2}, etc, until an index n is reached such that V_{l_k}-(b_{s_{k-1}+1}+\dots+b_n)<\alpha_n. Again, n exists because \sum_{i>s_{k-1}}b_i=+\infty. The least such n we call s_k, and this concludes stage k.

It is now a routine matter to check that this rearrangement has the desired properties: The sequence of partial sums V_{l_0}, V_{l_1},\dots converges to \beta, because V_{l_k}-\beta_k\to 0, since a_i\to0. Similarly, the sequence V_{m_0},V_{m_1},\dots converges to \alpha. This shows that the limsup of the partial sums is at least \beta, and the liminf is at most \alpha. But the V_i with m_{k-1}\le i\le V_{l_k} are increasing, and the V_i with l_k\le i\le m_k are decreasing, so no larger limit than \beta or smaller than \alpha can be achieved. \Box

Corollary. There is an injection of \mathbb R into the set S_\infty of permutations of the natural numbers.

The idea here is that we can begin with our favorite conditionally convergent series, and assign to r\in\mathbb R the rearrangement with series converging to r given by the theorem. Of course there are other methods of establishing the corollary, but I find this argument cute.

Exercise. Modify the construction to show that a conditionally convergent series admits a rearrangement such that any extended real is the limit of a subsequence of the sequence of partial sums.  

III.

Prior to Riemann’s theorem, Ohm had obtained interesting related results, that were later extended by Schlömilch, and Pringsheim (see here and here for statements of some of their theorems, and further recent work). They are usually discussed in terms of rearrangements of the alternating harmonic series, although their results are more general. See also these slides by Marion Scheepers for additional work along these lines, and for details see

Marion Scheepers. On the Pringsheim rearrangement theorems. J. Math. Anal. Appl., 267 (2), (2002), 418–433. MR1888013 (2003j:40002).

(In the slides, Scheepers is using the notion of signwise monotonic series. This just means series \sum_i u_i where {}|u_0|,|u_1|,|u_2|,\dots is monotonically decreasing.)

Ohm’s theorem appear in

Martin Ohm. De nonnullis seriebus infinitis summandis Commentatio, Berlin, 1839.

 

It predicts the value of the series obtained if we fix positive integers p and q, and the terms of the alternating harmonic series are rearranged so that first we add the first p positive terms, then the first q negative terms, then the next p positive terms, then the next q negative ones, etc. For instance, if p=1 and q=2, the rearrangement is

1 - 1/2 - 1/4 + 1/3 - 1/6 - 1/8 + 1/5 - \dots

Theorem (Ohm). The rearrangement of the alternating harmonic series obtained by adding first the first p positive terms, then the first q negative terms, then the next p positive terms, then the next q negative terms, etc, converges to \ln(2) + (1/2) \ln(p/q).

In particular, for p=1, q=2, the limit is (1/2) \ln(2) and if p=2,q=1, the limit is (3/2)\ln(2), which coincides with the observations we began with.

(See also here.)

[My Master’s student Monica Agana is working on her thesis on the classical theory of rearrangements, covering in detail the results by Ohm, Schlömilch, and Pringsheim.]

IV. 

A rearrangement is sometimes called simple iff the subsequences of positive terms of the original series and of the rearranged series coincide, and similarly with the subsequence of non-positive terms. Note that the rearrangements in Riemann’s and Ohm’s theorems are simple.

In

Wacław Sierpiński. Sur une propriété des séries qui ne sont pas absolument convergentes, Bull. Intern. Acad. Sci.: Cracovie A (1911) 149–158,

Sierpiński considers a different kind of rearrangements, where the non-positive terms are all fixed, and only the positive terms are permuted. (The paper is available here.) His result is the following:

Theorem (Sierpiński).

  1. Let \sum_i u_i be a conditionally convergent series of real numbers that converges to U. For any V\le U there is a rearrangement v_0,v_1,\dots of the u_i such that \sum_i v_i=V, and the rearrangement leaves fixed all non-positive terms. 
  2. Similarly, for any W\ge U there is a rearrangement w_0,w_1,\dots of the u_i such that \sum_i w_i=W, and the rearrangement leaves fixed all positive terms.
  3. Moreover, for any extended real \alpha, there is a rearrangement s_0,s_1,\dots of the u_i such that \sum_i s_i=\alpha and, for every n, u_n>0 iff s_n>0.

Before we proceed with the proof, let me mention a related question. Given a conditionally convergent series \sum_i u_i with sum U, it follows from the theorem that if there is a rearrangement v_0,v_1,\dots fixing non-negative terms and such that \sum_i v_i=V, then any numbers in (-\infty,V] can be so obtained, regardless of whether V\le U or not, since a rearrangement of the v_i fixing its non-negative terms is also a rearrangement of the u_i with the same property. Let s be the supremum of the numbers V obtained via such rearrangements.

Question. Can s=+\infty? If s\in\mathbb R, is s one of these numbers V?

Proof. Note first that it suffices to prove (1), since (2) is an immediate consequence of it: Simply apply (1) to the series \sum_i -u_i, noting that -W\le -U to obtain (2). For (3), we can use (1) or (2) if \alpha is real. But it is an easy exercise to show (3) if \alpha=+\infty or \alpha=-\infty.

For completeness, I sketch a proof of (3) when \alpha=+\infty. The case \alpha=-\infty follows the same outline, just as (2) follows from (1). Let a_0,a_1,\dots and -b_0,-b_1,\dots denote, respectively, the subsequences of positive and of non-positive terms of the u_i, so \sum_i a_i=\sum_i b_i=+\infty. Split the sequence of b_i into two disjoint subsequences b_0',b_1',\dots and c_0,c_1,\dots such that \sum_i b_i'=+\infty but \sum_i c_i<+\infty, and c_i\ne 0 for all i.

We describe the rearrangement required in (3) by stages. Our rearrangement fixes all positive terms and only permutes the negative ones. At the beginning of stage n, the permuted sequence built so far consists precisely of initial segments of the c_i and of the b_i'. In fact, b_0',b_1',\dots,b_{n-1}' have been used, as have, say, c_0,\dots, c_{k-1}.

Continue by using c_k,c_{k+1},\dots whenever a non-positive term should be used in the rearrangement, until at least c_k has been used, and a partial sum is obtained that is strictly larger than

\displaystyle n+b_n'+\sum c_i.

(This is possible because \sum a_i=+\infty while \sum c_i<+\infty.) Once this happens, use -b_n' at the first opportunity. This concludes stage n.

By induction one easily checks that all partial sums in stage n+1 are larger than n, and therefore the rearranged series diverges to +\infty, as wanted. This completes the proof of (3) for \alpha=\pm\infty.

It remains to verify (1).

Just as Riemann’s theorem depended on a lemma about the series of positive and non-positive terms of the original sequence, Sierpiński’s result depends on a lemma about the series of positive terms. Unlike Riemann’s theorem, in this case, all the work goes into the proof of the lemma, and the theorem is more properly a corollary of it.

Lemma.Suppose a_0,a_1,\dots is a sequence of positive numbers such that \sum_i a_i=+\infty and \lim_i a_i=0 Let A_0,A_1,\dots denote the sequence of partial sums. For any L\ge0 there is a rearrangement c_0,c_1,\dots with sequence of partial sums C_0,C_1,\dots such that \lim_i (A_i-C_i)=L.

To see that the lemma implies the result, suppose that V\le U, and let L=U-V. As above, let a_0,a_1,\dots and -b_0,-b_1,\dots be, respectively, the subsequences of positive and of non-positive terms of the u_i. Let A_0,A_1,\dots and B_0,B_1,\dots denote, respectively, the sequences of partial sums of the a_i and of the b_i. For each i, let p_i be the number of positive terms among u_0,\dots,u_i, and let n_i be the number of non-positive terms, so that p_i+n_i=i+1, and if U_0,U_1,\dots denote the partial sums of the u_i, then U_i=A_{p_i}-B_{n_i} for all i, and p_i,n_i\to+\infty.

Apply the lemma to the a_i to obtain a rearrangement c_0,c_1,\dots with partial sums C_0,C_1,\dots such that A_i-C_i\to L. Consider the rearrangement v_0,v_1,\dots of the u_i that fixes the -b_i and permutes the a_i as indicated. If V_0,V_1,\dots are the partial sums of the V_i, note that, by design, V_i=C_{p_i}-B_{n_i}, so that U_i-V_i=A_{p_i}-C_{p_i}\to L, and V_i\to U-L=V, as wanted.

Note that the requirement that L\ge0 in the statement of the lemma, and therefore that V\le U in (1), cannot be improved in general to cover a larger range of possible values, since the a_i may be decreasing, in which case we have that A_i\ge C-i for all i.

All that remains is to prove the lemma.

Proof. As in Riemann’s theorem, we proceed by stages. Starting with A_{-1}=C_{-1}=0, at stage n we examine A_{n-1}-C_{n-1} to decide the value of c_n. As in that theorem, we want to arrange that the values A_i-C_i increase if smaller than L, and decrease if larger, so that in the limit we obtain the desired value. Actually, we will need to modify slightly this strategy. To motivate the proof, consider first the case where the a_i are monotonic, that is, a_0\ge a_1\ge\dots In this case, the strategy works: At stage n, we consider two cases, according to whether A_{n-1}-C_{n-1}\le L or A_{n-1}-C_{n-1}>L:

  • If A_{n-1}-C_{n-1}\le L, then let r be such that a_r<a_n/2, and set c_n=a_r. This is possible, since a_r\to 0.

Note that, for as long as A_k-C_k\le L, we stay in this case. Thus, if from some point n on we are always in case 1, then for k large enough we have

\displaystyle A_k-C_k=(A_{n-1}-C_{n-1})+\sum_{i=n}^k (a_i-c_i)\ge(A_{n-1}-C_{n-1})+ \displaystyle \frac12\sum_{i=n}^k a_i\to\infty.

This is a contradiction, and indicates that repeated applications of this case always terminate, and lead to case 2. In particular, case 2 is considered infinitely often. Moreover, if k>n-1 is least such that A_k-C_k>L, then A_k-C_k=(A_{k-1}-C_{k-1})+(a_k-c_k)\le L+a_k.

  • If A_{n-1}-C_{n-1}>L, then in particular A_{n-1}\ne C_{n-1}, so at least one of the a_i, i<n-1, has not been considered yet as value of a c_j. Pick the least such index i, and define c_n=a_i.

Since this case applies infinitely often, the value of the least index i such that A_i is not one of the c_j increases unboundedly. By design, no index i is used more than once, and therefore this algorithm results in a rearrangement of the a_i. If we ever find an index k such that (again) A_k-C_k\le L, note that A_k-C_k=(A_{k-1}-C_{k-1})+(a_k-c_k)>(A_{k-1}-C_{k-1})-c_k {}>L-c_k.

Note that our assumption that the a_k are  decreasing ensures that, in case 2, (with notation as above) A_n-C_n=(A_{n-1}-C_{n-1})+(a_n-c_n)\le A_{n-1}-C_{n-1}, since a_i\ge a_n. Moreover, it cannot be that we have equality from some point on, since the a_k converge to 0. This means that the values A_k-C_k decrease.

Since a_i,c_i\to 0, it follows that, if case 1 is also applied infinitely often, then A_i-C_i\to L.  Therefore, to conclude, it suffices to argue that we cannot stay in case 2 forever. To see this, argue by contradiction, and assume that from n-1 on, we always stay in case 2. Let j_m be the number of indices i\le m such that a_i is not one of the c_k, k\le m. For any m\ge n, since A_{m-1}-C_{m-1}>L, then j_m\le j_{m-1}, with equality if and only if a_m is not one of the c_k, k<m. Since C_{n-1}\ne A_{n-1}, necessarily at least one of the c_i, i\le n-1, is a_r for some r\ge n. If r_0 is the least such index r, then j_{r_0}<j_{n-1}, because a_{r_0} is one of the c_i with i<r_0, in fact i<n. Since we cannot have an infinite decreasing sequence of positive integers, this means that (we have a contradiction and) eventually we should be in case 1 again. This completes the proof in the case the a_i are decreasing.

Let’s now consider the general case. If we try to implement the argument we just described, we see that if we are ever in case 1, A_k-C_k\le L, the sequence of A_i-C_i increases until we find an index j with A_j-C_j>L. Also, once we enter case 2, we cannot stay there indefinitely, as the number of terms a_i that are not some c_k, k\le j, decreases. The problem is that the sequence of A_i-C_i is not necessarily decreasing. In fact, if we are at a stage where we define c_n=a_i for some i<n, and it happens that a_n>a_i, then A_n-C_n>A_{n-1}-C_{n-1}. This means that, although we have ensured that \liminf (A_i-C_i)=L, and that there is a subsequence of the A_i-C_i converging to L, it may well be the case that \limsup (A_i-C_i)>L.

Sierpiński deals with this situation in a clever fashion. He ensures that if we are in case 2, so that c_n=a_i for some i<n, then also a_n=c_k for some k<n, which means that c_k was defined according to the prescription in case 1. He uses this to guarantee that A_n-C_n cannot stray too far from L. In detail, Sierpiński proceeds as follows, defining now three cases. Assume we are at the beginning of stage n:

  1. If A_{n-1}-C_{n-1}\le L, as before let c_n be some a_r where the index r has not yet been chosen, and a_r<a_n/2, and a_r<1/2^n.
  2. If A_{n-1}-C_{n-1}>L, now we consider two possibilities, according to whether or not the index n was picked previously: If it was not, then we let c_n=a_n. Note that A_n-C_n=A_{n-1}-C_{n-1} if this is the case, and that, since C_{n-1}\ne A_{n-1}, then necessarily some c_i with i<n must be a_r for some r>n. This means that at some later stage (at most by stage r), we are no longer to be in this case.
  3. If A_{n-1}-C_{n-1}>L, and the index n was chosen previously, then we let c_n be a_i, where i is the first index less than n not chosen yet.

As before, cases 1 and 3 happen infinitely often, so we have indeed defined a rearrangement. Moreover, if we are in case 3, then a_n=c_i for some i<n (this is why we included case 2). The point is that if stage i is by case 2, then c_i=a_i, and if it is by case 3, then c_i=a_j for some j<i. This means that the only way we can have c_i=a_n for n>i is if stage i was by case 1, which means that c_i<1/2^i.

Fix \epsilon>0. Since cases 1 and 3 happen infinitely often, if we choose n large enough, then we can ensure that all indices m mentioned below are so large that a_m,c_m<\epsilon, and if a_m=c_k for some k<m, then k>N where \sum_{i\ge N}1/2^i<\epsilon. We want to ensure that |(A_n-C_n)-L|<2\epsilon. This proves that A_n-C_n\to L.

If stage n is by case 1, and stage m<n was largest where A_m-C_m {}>L, then A_{m+1}-C_{m+1}=(A_m-C_m)+(a_{m+1}-c_{m+1})> L-c_{m+1}>L-\epsilon. Since the sequence A_i-C_i is increasing for m+1\le i\le n, we have L\ge A_n-C_n>L-\epsilon, as wanted.

Suppose then that stage n is by case 3, and that stage m<n was largest where we were in case 1. We then have that A_{m+1}-C_{m+1}=(A_m-C_m)+(a_m-c_m)\le L+a_m<L+\epsilon. Also,

A_n-C_n=A_{m+1}-C_{m+1}+\sum_{i=m+2}^n(a_i-c_i),

but for any such i, we have that stage i was either by case 2, and therefore a_i-c_i=0, or else it was by case 3, and therefore a_i=c_j<1/2^j for some j<i, but necessarily j>N, so

\displaystyle \sum_{i=m+2}^n(a_i-c_i)=\sum\{a_i-c_i\mid m+2\le i\le n, and stage i was by case 3\} \displaystyle \le\sum\{a_i\mid m+2\le i\le n, and stage i was by case 3\} \displaystyle \le\sum_{j>N}\frac1{2^j}<\epsilon.

This means that A_n-C_n<L+2\epsilon. But also

A_n-C_n=(A_{n-1}-C_{n-1})+(a_n-c_n)>L-c_n>L-\epsilon.

This completes the proof. \Box

This concludes the proof of Sierpiński’s theorem. \Box

Further work on rearrangements that fix pointwise prescribed subsets of \mathbb N has been pursued by Wilczyński and others, partly in the context of descriptive set theory. See for instance

Rafał Filipów, and Piotr Szuca. Rearrangement of conditionally convergent series on a small set. J. Math. Anal. Appl., 362 (1), (2010), 64–71. MR2557668 (2010i:40001).

Parts of this post have been used in this MO question.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: