There is an old puzzle which starts by asking: what is the next number in the sequence 1,2,4,? We are supposed to recognize the start of the sequence and answer that the next number is surely 8, because the first three numbers are consecutive powers of 2, and so the next number should be the cube of 2 which is 8. The puzzler then explains (contrary to expectations) that the successive terms in the sequence are actually the number of regions into which the plane is divided by a collection of lines in general position (so that any two lines intersect, and no three lines intersect in a single point). Thus:


So the “correct” answer to the puzzle is 7 (and the sequence continues 11, 26, \cdots (n^2+n+2)/2). This is somehow meant to illustrate some profound point; I don’t quite see it myself. Anyway, I would like to suggest that there is a natural sense in which the “real” answer should actually be 8 after all, and it’s the point of this short blog post to describe some connections between this puzzle, the theory of cube complexes (which is at the heart of Agol’s recent proof of the Virtual Haken Conjecture), and the location of the missing 8th region.

Actually, there is no great mystery about where the missing 8th region went. To ensure general position, I first needed to choose lines which were not parallel to each other, so let’s suppose that I have chosen a direction for the lines in advance. As I lay them in the plane one by one, I must also make sure that they don’t intersect an existing crossing. Since I have already chosen a direction for the line, I will either lie to the left or to the right of each existing crossing. After laying two lines, there is one crossing, so there are two choices for how I should lay the third line (given its direction); one choice gives the arrangement above; the other choice gives the following arrangement, which contains the missing 8th region:


Here I am thinking of the two different ways of arranging 3 lines in the plane as being related by a certain kind of “move” which translates the lines but does not turn them. The complementary regions are then specified by knowing on which side of each of the 3 lines they lie. We can think of this as a kind of (binary) code: if we orient each of the three lines, we denote a region to the left of it by L and a region to the right of it by R. Thus each region is coded by a three letter word in the alphabet L,R, so there are 8 possible regions which we can put in bijection with the numbers from 1 to 8 however we like.

The move on configurations of 3 lines is very closely related to a certain kind of move on knot diagrams called the “Reidemeister 3 move”. Think of the lines as shadows cast by strands of string, and think of moving one strand over a crossing of two other strands. The result (on shadows) is the Reidemeister 3 move:


What about 4 lines? We suppose that the 4 lines are ordered by increasing angle from horizontal, and give each complementary region a binary code depending on which side of the lines it’s on, so that there are 16 regions, which we give labels from 0 to 15. There are 8 configurations of 4 lines with given directions, indicated in the figure.


The unbounded regions — 0, 1, 3, 7, 15, 14, 12, 8 — are present in each configuration. As we “cycle” through these 8 configurations, in the order indicated in the figure, one bounded region appears and one disappears, in the cyclic order 10, 2, 6, 4, 5, 13, 9, 11.

For 5 lines there are many more combinatorial possibilities (even up to topological symmetries of the plane), but we can still get between any two configurations by a sequence of Reidemeister 3 moves, and all 32 regions appear in some configuration (actually, in many configurations). For more than 5 lines the story is similar.

There is a nice duality between arrangements of lines (or more generally, arrangements of hyperplanes) and zonohedra. If you recall from a previous post, a zonohedra is a polyhedron obtained as the Minkowski sum of a collection of intervals; that is, if I_1, I_2, I_3 \cdots I_n are intervals in some vector space, the zonohedron Z is the set of points of the form p_1 + p_2 + \cdots + p_n where each p_i \in I_i. Zonohedra are simply the (linear) projections to lower dimensional spaces of higher dimensional cubes. Given a zonohedron Z in a Euclidean space, there is a corresponding hyperplane arrangement in a projective space of one dimension lower, defined as follows: for each face F of the zonohedron, one considers the collection of supporting hyperplanes for Z that contain F. This is a polyhedron in projective space of dimension dim(Z) – dim(F) -1. So top dimensional faces give rise to points, codimension two faces give rise to segments, and so on. Each zone of the zonohedron (that is, each equivalence class of parallel edges, corresponding to one of the I_i) gives rise to the hyperplane in projective space corresponding to hyperplanes in the Euclidean space containing I_i. What is nice about this correspondence is that complementary regions to the hyperplane arrangement correspond to pairs of opposite vertices of the zonohedron. If we consider oriented hyperplanes then we get an arrangement of great spheres on a sphere; in the 2-dimensional case, an arrangement of great circles on the 2-sphere. So the 2^n possible regions that can occur (for all configurations) correspond to the 2^n vertices of the high dimensional cube, some subset of which project down to become the vertices of the zonohedron. (Note that I have swept under the rug the fact that we are now interested in configurations of great circles on the 2-sphere rather than straight lines in the plane. Three generic great circles on the 2-sphere decompose it into 8 regions, so this is another way of saying where the missing 8th region went: it was hiding round the back of the sphere).

Zones in the zonohedron correspond to midcubes in the high dimensional cube that projects to it — that is, the codimension one cubes that slice symmetrically through the center, parallel to a pair of opposite top-dimensional faces. So we can see a direct correspondence between midcubes in a high dimensional cube, and lines in the plane, or great circles in the sphere for that matter. Since we are already considering straight lines in non-Euclidean geometries, let’s ask what happens if we consider generic configurations of (straight) lines in the hyperbolic plane. Now things get much more interesting. Two generic lines in the hyperbolic plane might intersect, or they might be disjoint. There is an abstract graph whose vertices correspond to the straight lines in the configuration, and whose edges correspond to the pairs of straight lines which intersect. A complete K_n in this graph — i.e. a configuration of n lines each of which intersects the other — gives rise in a canonical way to an n-dimensional cube, whose shadow is the 3-dimensional zonohedron that parameterizes the combinatorics of the configuration. If some K_i is contained as a subgraph of two distinct K_j, K_k we obtain a complex by gluing together the j-cube and k-cube along their corresponding sub i-cube. The resulting space is a cube complex — a combinatorial complex built from cubes by gluings which respect the cubical structure on faces. Unions of midplanes glue together to make combinatorial hyperplanes which correspond precisely to the lines in the configuration. If the arrangement of lines was invariant under some group of hyperbolic isometries, then this group acts naturally and combinatorially on the associated cube complex. For example, if we start with a closed hyperbolic surface S and a finite configuration of immersed closed geodesics on S, the universal cover is the hyperbolic plane with an interesting arrangement of lines which is invariant under the action of the fundamental group \pi_1(S).

In fact, it turns out that the key point is not that the arrangement is of lines, but that it is of codimension one objects. If G is a (finitely generated) group, and H is a subgroup, we say that H is codimension 1 if the quotient of the Cayley graph of G by H has at least two ends. If it does, we can divide the Cayley graph into two H-invariant subsets, so that the frontier has finitely many orbits under the H action; this frontier is a kind of combinatorial hyperplane in G. The G translates of this hyperplane might intersect each other in a complicated way in the Cayley graph. As before, we can build a cube complex, where (roughly speaking) the n-cubes are the collections of n translates of the hyperplane each of which intersects the other in an essential way. The details of this construction can be found in a paper of Sageev (who first thought it up) and the end result is that one obtains a natural action of G on a cube complex. In fact, this cube complex is very nice geometrically — it is simply connected, and non-positively curved, so that if we make it a metric space by declaring that every cube is Euclidean with side lengths of edge 1, the result is CAT(0). The construction works just as well with a finite collection of codimension 1 subgroups H_i instead of just one, and under suitable hypotheses, one shows that the group G is isomorphic to the (orbifold) fundamental group of a compact non-positively curved cube complex. This now becomes extremely relevant to Agol’s proof of the VHC — if G is the fundamental group of a hyperbolic 3-manifold, the surface subgroups constructed by Kahn-Markovic (see these blog posts) provide the raw material from which one builds a cube complex on which G acts, and this is the starting point for Agol’s work; see here for an introduction. I don’t know if Sageev was led from combinatorial hyperplane arrangements to cube complexes via zonohedra, but it’s plausible; and in any case thinking of it in these terms (at least for low dimensional examples) helps me to more easily see where the cubes “come from”.