Euler's Formula, Proof 15: Binary Homology

Portions of the following proof are described by Lakatos (who credits it to Poincaré) however Lakatos omits any detailed justification for the properties of the map b defined below, instead treating them as axioms (so the theorem he ends up proving is that that Euler's formula is true of any polyhedron satisfying these axioms, but he doesn't prove that this is true of convex polyhedra).

Like the shelling proof, this proof interprets a polyhedron or polytope as a complex of polyhedral faces of varying dimensions, with f_i denoting the number of faces of dimension i. And like that proof, we add two "extra" cells, one for the whole polytope and one for the "empty face", so f_-1=f_d=1.

We interpret the subsets of faces of dimension i as a vector space over the two-element field GF(2), with vector addition being performed by symmetric difference of subsets (also known as exclusive or). In this way we get d+1 vector spaces V_i, with dimensions equal to f_i. The sets of faces of the polytope can be interpreted as forming bases for these vector spaces.

These spaces also come equipped with a linear mapping b taking each space V_i to the next lower dimensional space, defined on each face to be the set of its facets. When v is a sum of faces, b(v) is the sum of the corresponding sets of facets. (The empty face has no facets, and a vertex is defined to have the empty face as its only facet.) This mapping has two very important properties:

Boundaries have no boundaries. In other words, for any vector v, b(b(v))=0. If v is a basis vector, corresponding to a single face of the polytope, this is true because any ridge (face two dimensions lower than v) forms the boundary between two facets of v, and is therefore cancelled out in the calculation of b(b(v)). In the special case of the empty face, b(v)=0 already and for any linear map b(0)=0. In the special case of a vertex, b(v) is the empty face and again b(b(v))=0. The result follows as well for vectors other than the bases by linearity.
Any vector without a boundary is itself a boundary. In other words, for any vector v, if b(v)=0, then v=b(w) for some w. If v=0 then we can choose w=0 as well; for nonzero v we prove this by analyzing the vectors of each dimension separately. If v is in V_-1, it must be the empty face itself and is the boundary of some vertex. If v is in V₀, it must consist of an even number of vertices for b(v) to be zero. These vertices can be paired up and connected by paths; then w can be taken to be the vector sum of these paths. If v is in V₁, it forms a set of edges meeting an even number of times at each vertex; these edges can be grouped into Jordan curves and w can be taken to be the vector sum of regions bounded by these curves. If v is in V₂, it must be the whole set of facets of the polyhedron, since we can find a path on the polyhedron boundary from any facet to any other facet (avoiding vertices), and none of the edges crossed by this path can be in b(v). So we can take w to be the single cell corresponding to the whole polyhedron. Finally, if v is a nonzero vector in V₃, b(v) cannot be zero.

With these preliminaries out of the way we are ready to begin the proof that Sum(-1ⁱ f_i)=0.

Let B_i denote the subspace of V_i consisting of those vectors for which b(v)=0. Then the map b takes V_i to B_i-1. Whenever we have a linear map of vector spaces, we can use it to decompose the original space into its nullspace (the set of vectors mapped to zero, here B_i) and its orthogonal complement, which is mapped one-to-one onto the image of the map. This tells us that dim(V_i)=dim(B_i)+dim(B_i-1). Plugging this expansion into the sum we are trying to evaluate gives
Sum(-1ⁱ f_i) = Sum(-1ⁱ (dim(B_i) + dim(B_i-1)))
which equals zero, because each term B_i appears twice with opposite signs.

Cancelling the two extra parameters f_-1 and f₃ from the sum gives the usual Euler formula. I suspect there is a more direct, dimensionless way of proving that boundaryless vectors are themselves boundaries, but I don't see it and Lakatos doesn't describe it.

Homology theory, one of the foundation stones of algebraic topology, is devoted to defining similar vector spaces and understanding the extent to which the key equation dim(V_i)=dim(B_i)+dim(B_i-1) fails to be true in other topological spaces.

Proofs of Euler's Formula.
From the Geometry Junkyard, computational and recreational geometry pointers.
David Eppstein, Theory Group, ICS, UC Irvine.

Semi-automatically filtered from a common source file. Last update: Sunday, 27-Jan-2013 12:07:01 PST.