Data Exploration and Finding Low Hanging Fruit

One of Kaggle‘s intro competitions is to correctly characterize images of handwritten digits. In other words, given a picture of the digit ’1′ can you make a computer (quickly) determine that it is, in fact, the digit 1. One can instantly write an “algorithm” which will correctly guess the number approximately 10% of the time by guessing uniformly random digits. We’re going to try to do better than 10%. More importantly, we’re going to try to do it with as little effort and as little expertise as possible. The goal is to see how much low hanging fruit we can find just by poking around the data. The simpler the method the better! This is sort of a challenge to myself to see how good I can make a predictor without using any ML or statistical techniques.

First things first – look at some data. Here are a few of the images.

The Kaggle data set has about 4,000 of each digit so there’s bound to be some diversity, some of which can be seen in the differences between the versions of ’2′ displayed above. Our goal is to somehow encode what it means to be “3-like” or “7-like” and to encode the “3-ness” in an easily understood way. In fact, our approach is dead simple. We simply average all of the 3s and 4s etc in the data set to get a composite version. Here are the results as heatmaps:

Now, we’re not just interested in the averages as they are. Instead, we want to know what makes the image of an 8 different from all the other digits. In other words, we are interested in both how a given image looks like an 8 and how it does not look like a 3. To accomplish this, we subtract the average of all the images, shown here.

Subtracting this from all of the above images gives us the following ‘centered average digits.’

The change from blue to green backgrounds is a result of the fact that we now have negative values present (from subtracting the average picture). What we see here are both the hot spots for each digit (reds) and the spots each digit is unlikely to touch (blues) in any particular image. Note that for the analysis we are going to do, this step does not change the numerical outcome or the predictions made or the computational cost of the analysis. It is nonetheless interesting to see these characterizations of the different digits. I should also note that some normalization should probably occur here as a logical next step. You can see that the 8 has higher values because it has a depressed (bluer) background.

In any case, how do we tell a computer to compare these images and a given image of a handwritten digit? It’s pretty simple, we just take the dot product of the flattened images. For anyone not that familiar with linear algebra, this will return a large number when a given image and the comparison image have a lot of similar pixels, at least in this scenario.

We now declare that if we take some random image and do this process with all 10 average digits and 3 gets the highest score, then we label the given image a 3 and so forth. It turns out that this is good enough to be correct about 62% of the time. That’s a huge boost over random guessing without even doing any machine learning at all! What’s better is that this process is nice and fast and trying out this naive approach required understanding exactly 0 algorithms, just a little poking around.

The next thing to do is to figure out what’s happening with the other 38% of the cases. I built an array which has along the x-axis the correct label and along the y-axis the predicted label (not normalized). Let’s look at what we get.

To read this, each column represents all of the digits with a particular label and the rows represent the labels they are predicted to have by our method. Again, reds = lots. For example, very many 1s are predicted to be 8s. In fact, the predictor guesses 8 more for 1s than it guesses 1! What’s more, we can see that this method of prediction guesses 8 very frequently because the 8 row is rather well lit, as is the 0 row. As mentioned before, this may be a result of not normalizing the comparison set. In fact, this bias for 8s is so bad that there are 8251 incorrect guesses of 8 and only 3681 correct ones!

Perhaps some explanation can be found in the fact that drawn 8s tend to have the most ink on the page, so there’s a lot of places that 8s will overlap with other digits, contributing to a high score for a digit that is a little bit off-center or something. Here is an example of this in action – a 7 misclassified as an 8 because it  appears to slant at the wrong angle to hit the average 7.

This is not the most surprising part of this, though. The predictor, with 3795 different handwritten 5s to try, correctly classified an impressively bad ZERO of them. Almost all of the 5s are classified as 0s or 8s, and then a few 3s and a smattering of other bad guesses. Even more, it appears that nothing at all was labeled a 5, even in error! I had to double check this with the actual data.

This is inverted from the plot (my bad) but you can see the 5th row down has 0s all the way across. I was definitely surprised by that.

One way to improve on this is to simply penalize 8 and 0, hoping to break a bunch of near-ties in favor of the correct value. After applying such a penalty, there is an immediate boost of about 11% on the training data to a correct labeling rate of 73%. Not too shabby for not doing much of anything! Here’s the matrix comparing the actual labels to the new predictions.

The strong rows of 0 and 8 are mostly gone, but now there’s some extra activity around 2, 6 and 9, and most fives are still classified as 3s. Of course, we could now try to penalize 2 and 6 and 9 and look again, but we won’t. Anyway, it’s not perfect, but we really didn’t do much or have to know much and this is a bit better than I expected. All we had to do was look around and think about the data.

Big Changes

On Wednesday I successfully defended my thesis!I could not possibly have done this without the assistance of my advisor Daniel Groves or the many other mathematicians who talked with me about relatively hyperbolic groups in the past couple years. I am making the thesis available next to my resume and CV for anyone to read. I put a lot of effort into making it accessible for people approaching this topic so I hope that somebody finds the work interesting and informative.

For now, I am going to shift my focus from my defense to my future. I am getting married and  moving to Washington, DC in July – we are really looking forward to having spring start before May, for one thing. So there’s lots to do there, as well as putting my full effort into learning as much statistics, programming and machine learning as possible in the next few months. Now I just need a job! Things are changing really fast for me but I’m really excited about whatever comes next.

The Reeb Graph and Topological Data Analysis

Before I transferred to UIC, I was a graduate student at the University of Florida. While I was there studying topology with Alexander Dranishnikov, UF hired a new director of the honors program who had a math background – Kevin Knudson. He had a lot of interest in algebraic topology, and specifically applied AT, that he shared with us. This is a really new field and has seen a lot of growth in the past decade, with researchers like Rob Ghrist at UPenn and Gunnar Carlsson at Stanford producing a lot of great ways to use algebraic topology to answer actual problems.

In fact, the Stanford Computation Topology group has just spun off a company, Ayasdi, that deals specifically with exploratory data analysis by using methods developed in pure math.  They’ve published a collection of videos that make the power of their approach obvious, and they’ve also made some white papers available on some of the under-the-hood details. The main paper is Topological Methods for the Analysis of High Dimensional Data Sets and 3D Object Recognition. As a bit of a programming exercise I thought I’d try to reproduce their Mapper tool, which looks to have developed into Ayasdi’s Iris.

They give a brief description of some of the possible applications of their approach and I decided to try to work out one of these on my own. The relevant structure that they apply is a coarse version of the Reeb graph, a construction from Morse theory. This graph encodes the connectivity structure of a Morse function.

The classical application: given a height function, the Reeb graph encodes the number of connected pieces at a particular height. Here and in all similar images in this post, the first arrow represents the function (eg height) and the squiggly arrow represents building the Reeb graph. For instance, in the image you can see that the shape has circular cross sections all in the middle, so those cross sections only have 1 connected piece. Around the hoops, the cross-sections are 2 circles, so there are 2 connected components and the Reeb graph at that height has 2 points.

So this might seem a little silly if you’re new to this. What’s the big deal? Well, there are a few things. First, the Reeb graph can be applied to shapes that exist in any dimension. For a shape that can be embedded in 3-space, the Reeb graph is really pretty obvious. The problem is that most data sets measure very many different things (hundreds of dimensions!) so you can’t just look at it and see what the connections are. The Reeb graph provides a natural way of simplifying this data in a combinatorial structure.

Next, the function does not have to be a height function. In fact, I generally think that a height function is sort of the most boring thing you can choose. Instead, you can choose a function which represents something that you expect to be interesting about the data set.  A natural candidate for this would be a density estimator. In other words, are there a lot of points near a particular part of this space (high density) or are the points all far away (low density). Here’s a sample data set (generated by x and y coordinates that are normally distributed) that illustrates the idea.

The idea is that points in the center have a high density and points near the periphery have a low density. If we had this data, probably one thing we’d really like to know is where to find the densest concentration of points – ie where are they clustering? Here’s the same data with the points colored according to their density (darker = denser):

The next step is to embed this 2-d data into 3-d space by placing each point at a height that corresponds with its density – more dense = higher. (You may need to click on the image to animate it.)

Ok so how do we apply the Reeb construction to this? Well, let’s start with something that looks sort of like our randomly generated data set and apply the Reeb construction to that.

This is really nice because applying the Reeb graph to the density estimation has automatically pulled out the densest cluster as the top vertex! This is generally how this construction will work – you’ll see a peak vertex in the Reeb graph for every cluster in the data. Note that these top-level clusters don’t need to just be simple things like the data shown here, you can get clusters with interesting shapes.

As an aside, you might be thinking “couldn’t you just run some sort of clustering algorithm from the beginning here?” Of course the answer is yes, but with some major caveats. First, clustering is hard work for computers! If you have 100000000 data points, no chance of that working. Of course, what I’m doing here is also hard work for computers so that’s a rather weak point…. Second, this also lets you see how the clusters are related. Third, most clustering algorithms have an output which is just a list indicating which points belong to which clusters (or maybe a dendrogram or something depending on the algorithm) which I doubt would generate much insight. This outputs a nice graph that lets you see what’s happening! Lastly, this reduces the data in a very natural way that preserves a lot of the structure you might be worried about. Once the data has been simplified in this way, I’ve read somewhere that machine learning techniques will perform better. Seems plausible.

There remains the question of how we go from the given data set to our topological estimation of the data set. The answer is that we fudge it. Because our data is finite and sampled, and so not continuous or precise, we don’t need to use a continuous Reeb graph. Instead, we build a finite or approximate Reeb graph by considering only a small number of subintervals. Then we chop up the set and apply the Reed idea to that whole subinterval, not just to a single value as above.

Still, I haven’t done anything with the data so it doesn’t look like this has helped at all. However, consider the following: if you pick a random value for density, how many points have EXACTLY that density? The answer is (depending on your notion of random) going to be zero. On the other hand, if you pick a range of densities, then you have a good chance of capturing a bunch of points. That’s exactly what we use here.

To see this in action, I took the data set from above and sliced the densities into 12 possible ranges. On the image below, I’m including the 2nd least dense, 5th least dense, 9th least dense and most dense subsets. The least dense subset is hard to even notice since it’s only 2 points (IIRC) and they’re sort of close to the 5th least dense subset. Since I’ve excluded many of the density levels (eg 10 and 11) you get gaps between the data.

Ok so now is the time to apply some sort of clustering algorithm, even though I was dismissive of them before. However, we only apply the algorithm to each subset of points, which dramatically improves on the performance of the algorithm. If you just look at the picture above, you might guess that each interval has one circular component. That is approximately correct – the least dense points are not connected enough to get the whole circle, just subarcs (approximate). If we apply a clustering algorithm to all of these above level 3, we do indeed get a single component at each level, giving us something like the following Reeb graph (note that the orientation of the graph is determined randomly when its drawn and each vertex has a difficult to read label that indicated its density level).

Unfortunately, I didn’t save the exact data so I resampled and this one might be a tiny bit different. It’s a bit tattered near the bottom and there are some low-density floaters but that’s to be expected with a low-density data set – noise becomes more important! Nonetheless, you can immediately see at least one statistically important fact from this graph: the data is unimodal (ie like a bell curve – just one peak)! If you hadn’t seen the pictures that I showed you earlier, you wouldn’t know that. For example, if the data was 9 dimensional or something. Although I guess this is only half accurate since that cluster could have a significant amount of extra topological structure (it might be shaped weird) that you’re not seeing. That can be determined afterwards anyway. Here’s another data set and the accompanying graph:

You can see that the data has two peaks that are joined by a region of medium density. The graph has two ‘leaves’ that are joined  a few vertices away. Again, the bottom of the graph is pretty messy and there are some floaters around but the overall structure is intact.

One thing that I still haven’t mentioned is where the edges come from. To see this, we should take a look at another data set, this time a very simple 1D set. 

Let’s group these points according to their densities (here we just have 4 levels) and notice the key fact about our intervals in this example – many of them overlap:

And now apply the clustering algorithm to each density interval. For intervals that overlap, we include edges. Red boxes are clusters.

Now we just scrunch up all the clusters into single points to get the graph.

So now what do you do with this? Well, you can see how the data is shaped and how the clusters are related, qualitatively. You can run some sort of statistical test to understand what makes each cluster stand out, perhaps restricting your data set to just those high-density points (saving you mad flops). You can also take the data in each cluster and try to understand its shape, perhaps by running a similar process on it. You could also use some actual applied algebraic topology to do this by calculating the persistent homologies of each cluster.

There is one thing that I think really makes this approach powerful. After you stratify your data set according to this method, it’s simple to filter the data according to the observed structure. Then, you can apply either a battery of standard statistical tests to the simplified data (as noted above) or you can apply the Reeb construction a second (and third and fourth…) time using a different function for each iteration. What’s nice is that the major computational hurdles for this process are calculating the pairwise distances and building the graph but you only need to calculate the distances once, so every following iteration is cheaper than the first and since calculating the pairwise distances is , the savings are significant. Then, you can figure out reasonably quickly which things are the defining characteristics of each cluster and so forth.

I’ll finish with a few notes on this technique. First, the clustering algorithm I used is single-linkage. This suffers from a well-known flaw – two “obviously” distinct clusters can be identified as the same cluster if there’s a “bridge” between them. In other words, two large clusters can be turned into one cluster by connecting them with a narrow string of points because the algorithm only requires one nearby point to join things. I suspect that stratifying the data according to density goes a long way towards fixing this issue. Since SL is among the simplest clustering algorithms, overcoming this issue may make it the preferred choice in this context.

Second, here I constructed a Reeb graph, but the output need not be just a graph. In fact, the dimension of the output structure is effectively determined by the dimension of the range. For instance, if I had a domain specific function then I would get a “Reeb 2-complex.” Aside from the increased complexity of working with higher dimensional structures, the process is unchanged.

Third, the code I wrote still requires some serious hand holding. Specifically, there are two coefficients that I produced ad hoc – one in the density method and one in the clustering method. The density estimator functions by calculating and the value of needs to be determined beforehand. I haven’t worked this out completely but I suspect that should depend on the size of the data set and the dimension of the space and that it can probably be determined experimentally with relative ease.

In single linkage clustering, a maximum distance value, , must be provided by the user. I figured this out by trial and error for each case but my instinct is that is should depend only on density of the given cluster and dimension of the whole space. I haven’t spent any time trying to justify that claim. In any case, if that proves difficult to determine, one can always use DBSCAN or OPTICS instead and make a determination of the cluster structure from the output of those algorithms.

Stalling’s proof of the sphere theorem

Last spring I came across a paper of Peter Scott’s in which he provides new proofs (in 1980) for the Annulus and Torus theorems. In the paper, he describes his methods as partially modelled on a proof of Stallings of the sphere theorem of Papakyriakopolous. I looked this proof up in Stallings’ book and found that he uses a great blend of topology and group theory and thought that it ought to be shared. The statement of the theorem is as follows:

Sphere Theorem: Let be a compact 3-manifold such that . Then there exists a two-sided which is a 2-sphere or projective plane and which carries a non-trivial element of .

The main tools for the proof are the loop theorem (Papakyriakopolous’ generalization of Dehn’s lemma) and Stallings’ theorem on the ends of groups.

Loop Theorem: If there is a map with not null-homotopic in , then there is an embedding with the same property.

Stallings’ Theorem on Ends: Suppose that a finitely generated group has . Then either or , with finite and is an isomorphism between two subgroups of . ie the group is an amalgamated free product or an HNN-extension over a finite subgroup.

In fact, the whole theorem basically comes down to a sequence of isomorphisms from basic algebraic topology. Just remembering this one line is almost enough to completely reproduce the proof. After that, there’s just the matter of producing a CW complex which has the same fundamental group as the manifold.

Stallings’ Proof of the Sphere Theorem: We start by making a few modifications to our manifold, if necessary. Suppose that contains a 2-sphere or projective plane , then either we can choose (after moving it into the interior of ) to be our non-trivial element of or . In other words, it is easy to see that a contractible boundary component forces the manifold to be contractible. From now on, assume that this situation does not arise.

We now attempt to reduce the complexity of any boundary surfaces. To do so, let be such that . We can apply the Loop Theorem to an element of the kernel. This provides us with a disk embedded in which realizes the null-homotopy of that loop. A small neighborhood of this disk is a handle of .

We can see, by shrinking this handle and pulling it out, that has the homotopy type of for some submanifold which carries all of .

After performing this reduction as many times as possible (which is at most finitely many times by compactness), we are left with some submanifold such that , , contains no 2-spheres or projective planes and .

Now, is a collection of disjoint copies of the universal covers of the components of . Consequently, all of its homology groups are 0 (except in dimension 0). At this point, we apply some algebraic topology which gives us the aforementioned sequence of isomorphisms:

Here, is cohomology with compact support. Let’s justify these in order. The first is the Hurewicz theorem. The second follows from acyclic-ness (acyclicity? acyclinality? acycloidality? spell-check isn’t doing me any favors with this one). Lastly, we have relative Poincare duality.

Moreover, since and , the following theorem of Epstein (which I’m just quoting from memory here, to be checked later) implies that .

Theorem [Epstein]: If , .

By Stallings’ theorem on ends, we know that (the HNN case is similar so I’ll just do the amalgamated free product version).

By a well known construction for fundamental groups, we know that there is a map to a CW complex inducing an isomorphism of fundamental groups which “respects the amalgam structure.” Technically, . In other words, for any group we can let be a CW-complex such that . Here, we have three such complexes for , and we glue the two ends of to the other complexes according to the inclusions .

We can then find a separating subcomplex with finite fundamental group which carries nontrivial in both vertex complexes — this is (perhaps with homotopy). This carries the desired non-trivial element of since triviality of this element of implies that one of the two vertex groups would also be trivial. Lastly, because  is finite the choices of sub-manifold are restricted to the desired possibilities.

There are some details left to verify in many parts of what I’ve described, but I think I’ve presented most of the vital facts. Plus, I have pictures.

Group splittings: the trouble with circles (and planes)

As it turns out, a tremendous amount of the algebraic structure of a group (always with at least some finiteness condition) can be understood by observing the coarse geometry of the group. Some of the most general results are the celebrated theorems of Papasoglu and Stallings, which prove that splittings over two-ended groups and splittings over finite groups are easily identifiable from the Cayley graph. Numerous others have contributed, including (in no particular order) Bowditch, Rips and Sela, Kropholler, Fujiwara and Papasoglu, Dunwoody and Sageev, Scott and Swarup, Guirardel and Levitt, and myself.

Stallings theorem differs from the others, as they all fall under the category of splittings known as JSJ splittings. These particular splittings tend to focus on having cyclic edge groups, but the results of Guirardel and Levitt are more general, and my results are on splittings over two-ended and peripheral subgroups of relatively hyperbolic groups. The main characteristic of a JSJ splitting is that it captures a maximal amount of information about the possible splittings of a given group. As I’ll be discussing here, it may be difficult to know how many such splittings actually exist, even though we can “see” them in the coarse geometry. The problem is circles (or planes).

Consider a closed hyperbolic surface. This surface has a fundamental group which admits an infinite number of splittings, each corresponding to a different simple closed curve. From this curve, we can produce the splitting via van Kampen’s theorem. So far, so good. We’re happy with the topological picture presented and (with a bit of thought) we know that we can see all of the splittings in this way.

Except that there’s a big problem with this. Once I split the surface over a cyclic subgroup, I’ve necessarily made it impossible to realize an infinite number of other splittings in the same graph of groups. Every simple closed curve which has an essential intersection with our original curve is now living in two components. We can never realize these splittings as a graph of groups which refines them both.

A very nice fact is that this is the only context in which these “hyperbolic-hyperbolic” problems can happen. This is a central part of the various results on JSJ splittings. The solution to this problem is to abandon the goal of finding all of the cyclic splittings when this happens. Instead, we just allow ourselves to have some surface pieces in our graph of groups. In the end, we really understand all about the splittings from this anyway, so its a nice result. We can still get a very complete picture from the resulting graph of groups.

However, there is a further exception to this. Consider the following group: . This group is a hyperbolic semi-triangle group. It is generated by rotations around the vertices of a particular triangle which tessellates the hyperbolic plane.

Consequently, this group is quasi-isometric to and thus also to any closed hyperbolic surface group.This group admits no cyclic splittings whatsoever. Every simple closed curve is homotopic to the cone points of the quotient orbifold (or null-homotopic).

The main trouble is that, up to quasi-isometry, we just can’t tell these apart from surface groups. Thus, when studying JSJ splittings from a coarse geometry perspective, you have no idea if a plane gives you an infinite number of splittings or no splittings at all. The way circles arise is as the boundary of these planes embedded in the boundary of the larger group.

So that’s a rough idea of the difficulties that arise from these cases. Perhaps the most amazing thing is that, according to Bowditch, the only trouble that can come up is with groups that are virtually semi-triangle groups. In my next post I’ll deliver on the promise of my last post and talk about the cut pair tree. This is the context in which we see surfaces and interlocking cyclic subgroups arise in the context of splitting relatively hyperbolic groups.

Building R-trees from Continua I: the Cut Point R-Tree

This post is about a major component of my paper here: Papasoglu and Swenson’s method for constructing -trees from continua (compact, connected metrizable spaces), here. Since group actions on trees are so important (thanks to Bass and Serre) and a group action on a continuum is inherited by the tree we construct, this is really helpful for understanding these groups. It is especially useful for hyperbolic groups (by Bowditch), relatively hyperbolic groups (Bowditch again) and CAT(0) groups (Papasoglu and Swenson).

While I’m going to focus on the first stage of their construction in this post, the general process is to first construct a tree which encodes the structure of the cut points and then “blow up” some of the vertices of this tree in a way which encodes the cut pair structure. By a cut point, I mean some such that is not connected and by a cut pair I mean two points which are not cut points and such that is not connected. Bowditch talks about local cut points where I talk about cut pairs.

To understand the cut point tree, we establish an equivalence relation on the continuum . For any cut point , is equivalent only to itself, and for any other two points , if and only if there are no cut points which separate , ie these points are not in different components of the complement of any cut point. As it turns out, this relation satisfies a betweenness condition which turns into a “pre-tree.” It is the content of the first part of this paper that this can be turned in an -tree.

The betweenness property allows us to turn this into an -tree because it allows us to “connect the dots” between any two classes. First, we say that given two classes , the collection of classes which are between these is called an interval, . Betweenness also produces a unique (up to reversal) linear ordering on this interval. To built the associted -tree, we can just take all of the intervals, associate them with an actual arc and glue them together wherever they overlap. Obviously some care must be taken here, but that’s the general idea. Another version of this idea (starting with a 0-hyperbolic metric space and using the Gromov product instead) is outlined in Bestvina’s notes on R-trees.

Let’s take a look at an example (this diagram is intentionally very similar to one in the original paper):

 

Here, the black circles represent the cut points. We need to be careful how we interpret the sawtooth topologists sine curve (TSC), however. Every point of this subcontinua is a cut point, so every point represents its own class in the tree. The exception to this is the green class, which contains all of the points in the closure of the curve. The green class represents an end for the tree of the TSC. This is actually a major problem – vertices of the -trees we construct can correspond to ends of subtrees. We will deal with this later, when we talk about making the tree simplicial in some contexts.

In order to see why this construction is useful, we consider the case of relatively hyperbolic groups. By a construction of Groves-Manning (Bowditch has a similar construction), every relatively hyperbolic group can be associated to a -hyperbolic metric space called the cusped space. This space has the property that in the boundary, every peripheral subgroup stabilizes a unique point. Thus, if the group splits over a subgroup of a peripheral subgroup, that means that it has a cut point in the boundary. We can recognize this splitting by the group’s action on the tree built from its boundary using Bass-Serre theory. We need to be a bit careful because this tree may not be simplicial. Much of Bowditch’s work on these splittings went towards showing that this tree is simplicial under very mild hypotheses.

Let’s look at an actual group where this happens and see how the boundary looks. Let where is a complete hyperbolic 3-manifold with finite volume (but not compact!), e.g. a hyperbolic knot complement. This group is hyperbolic relative to the stabilizer of its cusps. Let’s just assume that there is a unique cusp and the cusp stabilizer is . Then and where is the cusped space. Now, consider the group . Its cusped space has the following boundary and cut point tree:

Obviously, I have not included all of the data from the boundary in the tree, since doing so is tedious. In any case, this construction results in a group action on a tree so that the black vertices are all stabilized by and the white vertices are all stabilized by one of the copies of . From this, we can obtain the quotient graph of groups which is, unsurprisingly, an interval with as both vertex groups and as the edge group.

Next post will be about the cut pair tree (also called the JSJ tree) where many more interesting things can happen.

 

Banach-Tarski I: Outline (and first post!)

This is my first post and I’m going to use it to begin a nice proof of the Banach-Tarski ‘paradox’ (BTP). I gave a talk on this topic at the Binghamton University Graduate Conference in Algebra and Topology (BUGCAT) in November of 2010. Knowing a proof of the BTP is nice since the proof uses some nice ideas from geometric group theory, it’s easier than most graduate students realize, and almost everyone knows the statement of it, including many non-mathematicians!

The outline of the proof is quite illuminating and many students might find that they can fill in several of the gaps with just that information. First, one begins by understanding what a so-called paradoxical decomposition of the free group on two generators (while here, let’s fix some notation for this: ). This type of decomposition essentially means covering by two much smaller subsets of . In order to apply this knowledge, one has to construct – or at least justify the existence of – a subgroup . Applying the decomposition to this free subgroup lets one construct a similar decomposition of the sphere   as desired. Now, there may be a few loose ends to gather up. In particular, there might be some topological nastiness that has to be cleaned up. To do this, we use the notion of equidecomposability. This allows us to get another partition which steers clear of any of the problems arising from the application of the paradoxical decomposition of the free group.

The BTP is one of the main examples of proofs requiring the Axiom of Choice and how strange things can get when one accepts it. The point in the proof at which the AoC is applied is when the paradoxical decomposition of is used to construct a similar decomposition of ; one must select a representative of each orbit.

In my opinion, the AoC and the BTP don’t really present much of an issue. I think that the original interpretation (look at the crazy things we can do with this axiom – it must be wrong!) makes much less sense than the notion that the topology of might be finer and more interesting than the level of topology which is witnessed by the physical sciences or our intuition. Existence on or above the level of elementary particles is already too coarse to find sets with a fine enough structure to be non-measurable.