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

November 16, 2014


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


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

Read the rest of this entry »

414/514 Homework 3 – Continuity and series

November 11, 2014

This set is due in three weeks, on Friday, December 5th, at the beginning of lecture.

1. Given a finite set A\subseteq\mathbb T=\{z\in\mathbb C\mid |z|=1\}, find (with proof) a power series f(x)=\sum_{n=0}^\infty a_n x^n with radius of convergence 1 and such that if z\in\mathbb T, then f(z) converges iff z\notin A.

Find (with proof) a countably infinite set  X\subseteq \mathbb T and a power series f(x)=\sum_{n=0}^\infty a_n x^n with radius of convergence 1 and such that if z\in\mathbb T, then f(z) converges iff z\notin X.

The first part is easy, the second one may be tricky. If after a few honest efforts you find yourself stuck, take a look at the literature. For instance, at either Stefan Mazurkiewicz, Sur les séries de puissances, Fundamenta Mathematicae, 3, (1922), 52–58, or Fritz Herzog, George Piranian, Sets of convergence of Taylor series. I. Duke Math. J., 16, (1949), 529–534. Both papers prove more general results, by explicit constructions. Present a detailed adaptation of their argument that solves the question. Do not simply reproduce the proof in the papers for the more general cases. Other relevant references on this topic are Fritz Herzog, George Piranian, Sets of convergence of Taylor series. II. Duke Math. J., 20, (1953), 41–54, and Thomas W. Körner, The behavior of power series on their circle of convergence. In Banach spaces, harmonic analysis, and probability theory (Storrs, Conn., 1980/1981), 56–94, Lecture Notes in Math., 995, Springer, Berlin-New York, 1983.

2. Present a detailed proof of Weierstrass theorem that for any compact interval [a,b], any continuous function f:[a,b]\to\mathbb R is the uniform limit of a sequence of polynomials. The proof should be different from the one presented in lecture (based on Bernstein polynomials). Again, although many books have a proof of this result, make sure your write up is your own.

287 – Coloring of graphs

November 9, 2014

I am posting here the nice slides on this topic made by Ian Cavey, Christian Sprague, and Mac Stannard. The slides are meant for a presentation of about 20 minutes.

Ramsey theory of very small countable ordinals

November 6, 2014

I was an undergraduate student at Los Andes, from 1992 to 1996. This year, their mathematics program is turning 50. There was a conference in September to celebrate the event, and I had the honor to give one of the talks (see here for the English version of the slides).

The Faculty of Science publishes a magazine, Hipótesis, and a special edition will be devoted to the conference. I have submitted an expository paper, based on my talk.

The topic is the partition calculus of very small countable ordinals (mainly ordinals below \omega^2, actually). The paper reviews Ramsey’s theorem and a few finite examples, before discussing the two main results.


One is an old theorem by Haddad and Sabbagh, unfortunately not well known. In 1969, they computed the Ramsey numbers r(\omega+n,m) for n,m finite.

Given nonzero ordinals \alpha,\beta, recall that r(\alpha,\beta) is the least \gamma such that any red-blue coloring of the edges of K_\gamma either admits a red copy of K_{\alpha} or a blue copy of K_\beta. Clearly r(\alpha,1)=1, r(\alpha,\beta)\ge r(\alpha,2)=\alpha if \beta\ge2, and r(\alpha,\beta)=r(\beta,\alpha), so we may as well assume that \alpha\ge\beta>2, and we adopt this convention in what follows.

Ramsey proved two theorems about this function in a famous 1928 paper that introduced the topic. In the notation we have just set up, his first result asserts that r(n,m) is finite whenever n,m are finite, and his second result states that r(\omega,\omega)=\omega. The computation of the numbers r(n,m) is an extremely difficult, most likely unfeasible, problem, though r is obviously a recursive function. We are concerned here with the values of the function when at least one of the arguments is infinite.

It turns out that r(\omega+1,\omega) is already \omega_1. Hence, if we are interested in studying the countable values of the function r(\alpha,\beta), then we must assume that either \omega=\alpha, in which case r(\alpha,\beta)=\omega and there is nothing more to say, or else (that is, if \alpha is countable and strictly larger than \omega) we must assume that \beta is finite.

The function has been intensively studied when \alpha is a limit ordinal, particularly a power of \omega. Here we look at the much humbler setting where \omega<\alpha<\omega2. Recalling that each ordinal equals the set of its predecessors, and using interval notation to describe sets of ordinals, the Haddad-Sabbagh result is as follows:

Lemma. For all positive integers n, m there exists a positive integer k\ge n, m such that for any red-blue coloring of the edges of K_{[0,k)}, and such that K_{[0,m)} is blue, there is a subset H of {}[0, k) with K_H monochromatic, and either K_H is blue and |H| = m + 1, or else K_H is red, |H|=n+1, and H\cap[0,m)\ne\emptyset.

Denote by r_{HS}(n+1,m+1) the smallest number k witnessing the lemma.

Theorem. If n,m are positive integers, then r(\omega +n,m)=\omega(m-1)+t, where r_{HS}(n+1,m)=(m-1)+t.

The theorem was announced in 1969, but the proof never appeared. I have written a survey on the topic, including what should be the first proof in print of this result.

Read the rest of this entry »

414/514 Examples of Baire class two functions

November 3, 2014

Previously, we listed some examples of Baire class one functions. Here we do the same for functions in the next class of Baire. Recall that if I is an interval, the function f:I\to\mathbb R is (in) Baire class two (\mathcal B_2) iff it is the pointwise limit of a sequence of Baire one functions.

This post comes from an answer I posted on Math.Stackexchange about a year ago.

Here are three examples:

    1. Let C be the Cantor set. For each interval (a,b) contiguous to C, define f on {}[a,b] by


      so f maps the interval to [-1,1]. Otherwise, let f(x)=0.

    2. Write each x\in(0,1) in binary: x=0.a_1a_2a_3\dots, not terminating in a string of 1s, and define

      \displaystyle f(x)=\limsup_{n\to\infty} \frac{a_1+\dots+a_n}n.

    3. Conway’s base 13 function.

The first two examples come from Bruckner’s book Differentiation of real functions. All three are examples of functions that are not derivatives but have the intermediate value property.

The first one is discontinuous precisely at the points of C, and it is “almost” Baire class 1, in that one can turn it into a Baire class 1 function by only modifying its values (carefully) at the endpoints of intervals contiguous to C. But if one does this, then the function no longer has the intermediate value property.

The second function has the property that the image of any subinterval of (0,1), no matter how small, is all of (0,1). The third function is in the same spirit, but it behaves even more dramatically: The image of every open interval is all of \mathbb R.

To verify that the functions are indeed in Baire class at most 2:

  1. For example 1, use that the limit of x^n on {}[0,1] is 0 for x<1, and 1 at x=1, to get for each open interval (a,b) contiguous to C a Baire class 1 function f_{[a,b]} that is zero everywhere except on {}[a,b], where it coincides with f. Now use that the sum of finitely many Baire class 1 functions is Baire class 1.
  2. For example 2, there are several ways to proceed. Here is one, which I do not think is optimal, but (I believe) is correct: Recall that a limsup is the infimum (over m) of a supremum (over all n>m), so it is enough to see that each f_m(x)= \sup_{n>m}g_n is Baire class 1, where

    \displaystyle g_n(x)=\frac{a_1+\dots+a_n}n.

    The point is that each g_n has finitely many discontinuities, all of which are jump discontinuities. Any such function is Baire class 1. This would appear to mean that f_m is Baire class 2, but we are saved by noting that f_m is the uniform limit of the g_n, n>m. (The point is that each Baire class is closed under uniform limits.)

  3. The argument for example 3 is similar. (Note that this function is unbounded.)

To see that the functions are not Baire class 1: The functions in examples 2 and 3 are discontinuous everywhere, but the set of points of continuity of a Baire class 1 function is dense. For example 1, use Baire’s extension of this result giving us that, in fact, if f is Baire class 1, then for any perfect set P, the set of points of continuity of f\upharpoonright P is comeager relative to P. In example 1 this fails (by design) when P=C. (All we need is that, for any closed set D, the restriction of a Baire one function to D has at least one continuity point on D. Baire also showed that this characterizes Baire one functions.)

Example 2 is also discussed in the van Rooij-Schikhof book (see their Exercise 9.M).

To close, let me include some examples that do not have the intermediate value property. Note first that if A\subseteq\mathbb R and \chi_A is its characteristic (or indicator) function, then \chi_A is continuous iff A=\emptyset or \mathbb R. More interestingly, \chi_A is Baire class 1 iff A is both an F_\sigma and a G_\delta set.

Recall that a set is F_\sigma iff it is the countable union of closed sets, and it is G_\delta iff it is the countable intersection of open sets. The notation F_\sigma is pronounced F-sigma. Here, the F is for fermé, “closed” in French, and the \sigma is for somme, French for “sum”, “union”. Similarly, the notation G_\delta stands for G-delta. Here, the G is for Gebiet, German for “area”, “region”— neighborhood—, and the \delta is for Durchschnitt, German for “intersection”.

Note that, in particular, open sets are both: They are clearly G_\delta, and any open interval (and therefore, any countable union of open intervals) is a countable union of closed intervals. It follows that closed sets are also both. In particular, the characteristic function of the Cantor set is Baire class 1. More generally, a function f is Baire class 1 iff the preimage f^{-1}(U) of any open set is F_\sigma.

For the more general case where A is F_\sigma or G_\delta, then \chi_A is Baire class 2. For any A which is either, but not both, \chi_A is an example of a properly Baire class 2 function. For instance, this is the case with A=\mathbb Q. In fact, \chi_A is Baire class 2 iff A is both an F_{\sigma\delta} and a G_{\delta\sigma} set (G_{\delta\sigma} sets are countable unions of G_\delta sets, that is, countable unions of countable intersections of open sets, and F_{\sigma\delta} sets are countable intersections of F_\sigma sets, that is, countable intersections of countable unions of closed sets).

More generally, f is Baire class 2 iff for any open U, the set f^{-1}(U) is G_{\delta\sigma}. For details, and a significant generalization due to Lebesgue, that characterizes each Baire class and relates it to the hierarchy of Borel sets, see section 24 in Kechris’s book Classical descriptive set theory.