Bolzano-Weierstrass

A particularly useful result in real analysis is, remarkably, applicable to combinatorics problems where reals are not even mentioned. It is the fabled Bolzano-Weierstrass theorem. The statement of the theorem is that ‘every bounded sequence has a convergent subsequence’. It is not too difficult to prove this directly from the least upper-bound axiom of the real numbers.

Lion-hunting and interval bisection

Suppose we have a large desert, in which we are chasing a lion. What is the best way to catch it? Unlike in the trailer of the Travelling Salesman movie, you’re not allowed to melt the sand and imprison your feline friend in a sea of glass. The solution is to erect a fence, splitting the desert into two halves. Then choose the half containing the lion, and repeat the process, halving the area again in which the lion can roam. Eventually, you can confine the lion to an arbitrarily small area.

The proof of the Bolzano-Weierstrass theorem is similar, but with an infinite number of lions. Each time we erect a fence, we can choose a smaller interval still containing infinitely many lions (real numbers). We get an infinite sequence of intervals, each one half as large as the previous one. For instance, the result may resemble this:

{[0, 1], [0, 1/2], [1/4, 1/2], [1/4, 3/8], [1/4, 5/16], [9/32, 5/16], …}

The supremum (least upper bound) s of {0, 0, 1/4, 1/4, 1/4, 9/32, …} is equal to the infimum (greatest lower bound) of {1, 1/2, 1/2, 3/8, 5/16, 5/16, …}. If we choose an arbitrary real in each of these intervals to form a new sequence, the nth real must be within 2^-n of the limit s. So, by definition, this sequence of reals converges.

The Bolzano-Weierstrass theorem applies to spaces other than closed bounded intervals; the closed unit ball in R^n is another example (same proof). We describe such spaces as sequentially compact.

Infinitely many descendants

Now that we have the Bolzano-Weierstrass theorem, it’s time to use it to prove stuff. Ordinary people would apply it to problems in real analysis (where it does indeed work), but it’s more fun to prove theorems in combinatorics. The first problem is this:

  • Ezekiel (thanks to James Cranch for that name) has infinitely many descendents. Given that each person has only finitely many (possibly zero) children, prove that there is an infinite sequence {c_0, c_1, c_2, …}, such that c_(n+1) is the child of c_n.

This seems obviously true, but it is not trivial to prove. Let’s inject all people into the interval [0, 1]. Specifically, we append ‘1111…112’ (with n ones) to the end of the decimal expansion of person A to create the decimal expansion of the nth child of person A. So, the 5th child of the 3rd child of the 7th child of Ezekiel is represented by the real number 0.111111121112111112.

ancestry

We can now apply Bolzano-Weierstrass to get an infinite convergent sequence of reals with limit s. The decimal expansion of s cannot end in a recurring sequence of ones (lest we have a person with infinitely many children). So, the decimal expansion instead must contain infinitely many twos, and thus correspond to an infinite sequence of descendents.

Tiling the plane with polyominoes

  • We have a set of polyomino prototiles capable of tiling arbitrarily large squares (with some optional overhang), such that the resulting tiling is k-colourable. Prove that it’s possible to tile the entire plane with these polyominoes and k-colour that tiling.

The general problem of determining whether a set of polyominoes can tile the plane is difficult, as we cannot guarantee a periodic tiling. Indeed, it’s undecidable. Similarly, it’s difficult (NP-hard for the finite case) to 3-colour a particular map. Hence, our proof must somehow use the partial tilings (such as the one below) to construct a full tiling of the entire plane.

overhang

As shown above, there is a 3-colourable tiling of a 7 by 7 square (with overhang) by some polyominoes. We can convert it into a real number in the interval [0, 1] by reading the sequence of colours along a spiral as digits (red = 1, orange = 2, yellow = 3):

spiral

So, we get the real number 0.2112321233112333121131331222333222111222332222112. Repeating for squares of sizes 2n+1, for all positive integers n, we obtain an infinite sequence of bounded real numbers. By Bolzano-Weierstrass, there is a convergent subsequence. Its limit corresponds to a 3-coloured tiling of the whole plane.

Leo Moser’s harmonic rectangle problem

Consider the set of rectangles of dimensions {1×(1/2), (1/2)×(1/3), (1/3)×(1/4), …}. Their total area is equal to 1, so it may be possible for them to tile a unit square (this is an unsolved problem). It has been shown that they can be packed into a square of side length 1.002, so there are logically three possibilities:

  1. They can tile a unit square.
  2. They can be packed into squares of side length 1 + ε for all ε > 0, but cannot tile the unit square.
  3. There exists some k, where 1 < k < 1.002, such that they cannot be packed into a k × k square.

With help from the Bolzano-Weierstrass theorem, we can actually eliminate the second of these possibilities. Specifically, for a given packing, we represent the nth rectangle by a triple (x, y, θ) of bounded reals giving the coordinates of the rectangle and its orientation. Concatenating all of these triples together gives a sequence {a_(1,1), a_(1,2), a_(1,3), …}. Repeat for another packing of a square with a smaller side length, {a_(2,1), a_(2,2), a_(2,3), …}. Repeat this infinitely many times for a decreasing sequence of side lengths converging to 1 (which we can do, assuming the second possibility). This gives a sequence of sequences.

By Bolzano-Weierstrass, we can take a subsequence where all of the a_(i,1)s converge. Then, within this subsequence, take a subseqence where all of the a_(i,2)s converge. Repeat ad infinitum. The limit gives a tiling of the unit square by these rectangles (Proof: assume otherwise, then there must be some pair of rectangles which overlap or overspill by some real value h > 0, whence we obtain a contradiction).

There is a related problem proposed by Coxeter, asking for the diameter d of the smallest circle into which discs of radii {1, 1/2, 1/3, …} can be packed. It transpires that the trivial lower bound of d = 3 can actually be attained. This is not a tiling, by the way, as the discs have a total area of π^3/6 whereas the large circle has an area of 9π/4 (convince yourself that the latter is substantially larger than the former).

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

5 Responses to Bolzano-Weierstrass

  1. Andymc says:

    If you use the “infinitely many pigeons into finitely many pigeonholes, ad infinitum” approach on the second problem, it feels very similar to using the retarded approach (:-D) with a first-principles definition of ‘limit’…

    (Each extra ‘shell’ that you put on with pigeonhole is like a new epsilon being put into the limit definition… I think…)

    • apgoucher says:

      Yes, the lion-hunting approach halves the area each time, so eventually it drops below any prescribed value (epsilon). All of these examples essentially rely on the same ideas and are classified as ‘proofs by compactness’. You can apply the lion-hunting argument directly to the situation without needing the Bolzano-Weierstrass theorem, but once you’ve proved Bolzano-Weierstrass you can repeatedly reuse it as a lemma (as I did in those examples).

  2. I think there is a gap in the proof of your last example (Leo Moser’s harmonic rectangle problem):

    “By Bolzano-Weierstrass, we can take a subsequence where all of the a_(i,1)s converge. Then, within this subsequence, take a subseqence where all of the a_(i,2)s converge. Repeat ad infinitum. The limit gives a tiling of the unit square by these rectangles”

    It seems that this argument could be used to prove the Bolzano-Weierstrass theorem for infinite dimensional real vectorspaces (such as the space of real sequences), where it doesn’t hold in general. So this looks at least fishy to me.

    More concretely: Repeating this construction at infinitum just gives you converging subsequences for each n. How do you construct a limit sequence from that? For example, simply intersecting all those converging subsequences might lead to an empty set.

    • apgoucher says:

      Yes, I suppose I wasn’t particularly clear.

      The converging subsequences are nested within each other, so the first subsequence (where a_(i,1) is convergent) contains the second subsequence (where both a_(i,1) and a_(i,2) are convergent, and the limit of a_(i,1) is the same as in the first subsequence), which in turn contains a third subsequence, and so on.

      This gives us a well-defined sequence of limits {omega_1, omega_2, omega_3, …}, where omega_n is the limit of a_(i,n) in the mth subsequence (for all m >= n).

      I’m not asserting that the space of all bounded real sequences is sequentially compact (as this is false; consider {{1,0,0,0,…},{0,1,0,0,…},{0,0,1,0,…},{0,0,0,1,…},…} for example. If we apply my construction to this, we obtain {0,0,0,0,…}, which is at a distance of 1 from those sequences (in the Euclidean norm).

      Fortunately, I did not rely on this in the proof by contradiction. For the limit packing to be invalid, there must be two rectangles (let’s say, the nth and mth rectangles) which overlap by some distance h. This implies that those rectangles overlap by h in the limit of the max(3n,3m)th subsequence, so they must overlap in at least one [actually, infinitely many] of the terms of that subsequence. Contradiction.

  3. Pingback: TREE(3) and impartial games | Complex Projective 4-Space

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