Geometric delights with Euler’s formula

The same formula appears on a Swiss postage stamp issued on March 6, 2007, to celebrate the 300th anniversary of Leonhard Euler’s birth, and on an East German stamp issued on September 6, 1983, to commemorate the 200th anniversary of his death.

Euler’s formula states that e ‒ k + f = 2 (more commonly written, in French notation, as s ‒ a + f = 2): in three-dimensional space, the number s of vertices minus the number a of edges plus the number f of faces of a convex polyhedron is invariably equal to 2.

Not everything is three-dimensional ---------------------------------

Can Euler’s formula be generalized? Consider dimensions below 3, using the notation *a_i for the number of elements of dimension i in an object of dimension n. For a point, a*₀ = 1: there is simply one point.

For a line segment, a₀ ‒ a₁ = 1: we have two points and one line segment (and 2 – 1 = 1).

For a polygon, a₀ ‒ a₁ + a₂ = 1: we have n points, n line segments and one surface (and n ‒ n + 1 = 1).

For a polyhedron, a₀ ‒ a₁ + a₂ ‒ a₃ = 1: this recovers Euler’s formula in three dimensions (with a₀ = s, a₁ = a, a₂ = f and a₃ = 1).

Euler’s formula for regular polyhedra -----------------------------------------------

Consider a regular polyhedron with m equilateral triangular faces. Let s denote the number of vertices.

Euler’s formula then gives:

s - \dfrac{3m}{2} + m-1=1.

Alternatively, we can use the angle-deficit theorem, which here gives the following relation (in degrees):

s \times \left( \cfrac{360^\circ}{60^\circ} -\cfrac{3m}{s} \right) \times 60^\circ = 720 ^\circ,

which yields the same result, namely 2s = m + 4. Furthermore, the number k of angles meeting at each vertex, namely

k= \dfrac{3m}{s},

is 3, 4 or 5 (since k > 2 and k × 60° < 360°).

There are therefore three regular polyhedra with triangular faces:

the tetrahedron (for which s = 4 and m = 4), the octahedron (with s = 6 and m = 8), and the icosahedron (with s = 12 and m = 20).

If the regular polyhedron has m square faces, we similarly obtain:

s - \dfrac{4m}{2} + m-1=1.

The angle-deficit theorem likewise gives:

s \times \left( \cfrac{360^\circ}{90^\circ} -\cfrac{4m}{s} \right) \times 90^\circ = 720 ^\circ,

that is, 2s = 2m + 4.

Furthermore, the number k of angles meeting at each vertex is

k= \dfrac{4m}{s},

and can only be 3. There is therefore only one regular polyhedron with square faces: the cube (for which s = 8 and m = 6). Finally, if the regular polyhedron has m pentagonal faces, we have

s-\frac{5m}{2}+m-1=1

. The angle-deficit theorem gives

s\times\left ( \frac{360^{\circ}}{108^{\circ}}-\frac{5m}{s} \right )\times 108^{\circ} = 720^{\circ}

, that is, 2s = 3m + 4. Furthermore, the number k of angles meeting at each vertex is

k=\frac{5m}{s}

and can only be 3. There is therefore only one regular polyhedron with pentagonal faces: the dodecahedron (for which s = 20 and *m = 12).

Ultimately, there are only five regular convex polyhedra: the tetrahedron, which is self-dual; the cube and its dual, the octahedron; and the icosahedron and its dual, the dodecahedron.

References

• Feature section “The saga of theorems: Euler’s formula.” Tangente 174, 2017.

• Leonhard Euler. Bibliothèque Tangente 29, 2007.

• Euler’s relation and polyhedra without “holes”. Geometry Unit of the Research Center of the Haute École de la Communauté française en Hainaut, 2023, available online.

The French mathematician Henri Poincaré (1854‒1912) proved that, for any convex polytope of dimension n, a₀ ‒ a₁ + a₂ ‒ a₃ +… + (‒1)*ⁿa_n = 1, which can be written more concisely as $\sum^n_{i=0} (-1)^ia_i =1,$ where a_n* = 1 (since the polytope is assumed to be convex, it is also connected).

Convexity—the property that every line segment joining two points of a polytope lies entirely within it—is sufficient, but not necessary, for Euler’s formula to apply to the polytope. It no longer applies, however, to more sophisticated shapes, such as those “with holes.”

The tesseract.

For a four-dimensional “volume” (or polychoron), how can we give concrete meaning to the expression a₀ ‒ a₁ + a₂ ‒ a₃ + a₄ = 1?

The four-dimensional hypercube, known as a tesseract, can be represented in a plane (in two dimensions) as a three-dimensional perspective view, as shown in the diagram. This representation—others are possible—makes it easier to count the three-dimensional cubes in the tesseract.

The origin O of the orthonormal coordinate system (O, x, y, z, w) in which the tesseract is represented lies at the center of the figure; the (Ow) axis cannot be shown. The w-coordinate is proportional to the side length of the cube in the figure; thus the “small” cube in the figure is closer to O than the “large” one.

A standard two-dimensional square can be duplicated in a third dimension to form a cube, with the two squares joined by four additional edges and four additional faces. Similarly, a cube can be duplicated in the fourth dimension to form a tesseract, with the two cubes joined by eight edges, twelve faces and six additional cubes.

The eight cubes include the two produced by the duplication, both described in the coordinate system (O, x, y, z) and positioned at w₁ and w₂, respectively. They also include the six spaces between the faces of these two cubes: two are described in (O, w, x, y) at two coordinates z₁ and z₂; two others are similarly described in the coordinate system (O, w, x, z), and the final two in the coordinate system ( O , w , y , z ) .

A short journey into 4D ---------------------------

Let’s construct the tesseract in two stages. Starting with the cube (for which a₀ ‒ a₁ + a₂ ‒ a₃ = 8 – 12 + 6 – 1 = 1), add a point in the fourth dimension to form a four-dimensional pyramid (or a cone).

The expression then becomes:

(a₀ + 1) ‒ (a₁ + 8) + (a₂ + 12) ‒ (a₃ + 6) + 1 = (8 + 1) – (12 + 8) + (6 + 12) – (1 + 6) + 1 = 1.

Starting with this (a₀ ‒ a₁ + a₂ ‒ a₃ + a₄ = 9 – 20 + 18 – 7 + 1 = 1), if the point is expanded into a cube “parallel” to the first cube (a four-dimensional prism), we obtain:

(a₀ – 1 + 8) ‒ (a₁ + 12) + (a₂ + 6) ‒ (a₃ + 1) + a₄= (9 – 1 + 8) – (20 + 12) + (18 + 6) – (7 + 1) + 1 = 1.

Let us proceed in the same way from a tetrahedron (for which a₀ ‒ a₁ + a₂ ‒ a₃ = 4 – 6 + 4 – 1 = 1), adding a point in the fourth dimension to form a hypercone (called a pentachoron). This gives:

(a₀ + 1) ‒ (a₁ + 4) + (a₂ + 6) ‒ (a₃ + 4) + 1 = (4 + 1) – (6 + 4) + (4 + 6) – (1 + 4) + 1 = 1.

####

The pentachoron.

From there (a₀ ‒ a₁ + a₂ ‒ a₃ + a₄ = 5 – 10 + 10 – 5 + 1 = 1), if the point becomes a tetrahedron “parallel” to the first tetrahedron (a hypercylinder), we find that:

(a₀ – 1 + 4) ‒ (a₁ + 6) + (a₂ + 4) ‒ (a₃ + 1) + a₄= (5 – 1 + 4) – (10 + 6) + (10 + 4) – (5 + 1) + 1 = 1.

In four dimensions, a simplex is a four-dimensional polytope whose vertices lie on the coordinate axes of the orthonormal coordinate system (O, x, y, z, w), together with the origin O. More generally, in a space of dimension n, a simplex is a polytope whose vertices lie on the coordinate axes of the orthonormal coordinate system (O, x₁, x₂, x₃… *x_n), together with the origin O. A simplex therefore has n* + 1 vertices.

In dimension 1, the simplex is a line segment; we have: 2 – 1 = 1.

In dimension 2, the simplex is a triangle; we have: 3 – 3 + 1 = 1.

In dimension 3, the simplex is a tetrahedron, and 4 – 6 + 4 – 1 = 1.

In dimension 4, the simplex is a 5-cell, and 5 – 10 + 10 – 5 + 1 = 1.

In higher dimensions, it is easy to see that

a_i= \text{C}^{i+1}_{n+1}.

Here the notation denotes a binomial coefficient, namely the number of combinations of p objects chosen from n.

There are n + 1 vertices, and each i-dimensional face of the simplex is determined by choosing i + 1 vertices from among them.

This yields the following fundamental identity:

\sum^n_{i=0} (-1)^i \,\text{C}^{i+1}_{n+1} =1.

We have

(1-1)^{n+1}= 0 =1 - \sum^n_{i=0} (-1)^i \,\text{C}^{i+1}_{n+1}.

It all starts with a simplex ---------------------------------

Euler's formula therefore holds for every simplex. To extend it to every convex polytope of dimension n, we make a series of modifications to this n-dimensional simplex, such as adding or "flattening" a vertex or an edge. Without attempting to catalogue every possibility, we describe seven such modifications below (the diagrams show three-dimensional polytopes to make the geometry easier to follow).

A vertex from which a edges emanate is duplicated: a₀ increases by 1, a₁ increases by 1 + 2, and a₂ increases by 2 (how the a edges are distributed between the two vertices makes no difference).

Net change: 1 – 3 + 2 = 0, so the identity remains unchanged by this operation.

A vertex is raised from a face with s vertices: a₀ increases by 1, a₁ increases by s, and a₂ increases by s ‒ 1 (the original face disappears).

Net change: 1 – s + (s – 1) = 0, so the identity remains unchanged.

*A vertex is raised from an edge between two faces with s₁ and s₂ vertices, while remaining in the plane of one of those faces. The integer a*₀ increases by 1, a₁ by s₂ – 1 (one edge disappears in the operation), and a₂ by (s₂ – 1) – 1 (the enlarged face already existed, while the other original face disappears).

Net change: 1 – (s₂ – 1) + (s₂ – 2) = 0.

*A vertex is raised from an edge between two faces with s₁ and s₂ vertices: a*₀ increases by 1, a₁ by s₁ + s₂ – 2 – 1 (the two faces share two vertices, and one edge disappears), and a₂ by s₁ + s₂ – 2 – 2 (the two faces share two vertices, and the two original faces disappear).

Net change: 1 – (s₁ + s₂ – 3) + (s₁ + s₂ – 4) = 0.

An edge is introduced: its endpoints are created on two edges belonging to the same face. Thus a₀ increases by 2, a₁ increases by 1 + 2 (the original edges are split), and a₂ increases by 2 – 1 (one face disappears).

Net change: 2 – (1 + 2) + (2 – 1) = 0.

A vertex (from which a edges emanate) is flattened: a₀ increases by a – 1 (one vertex disappears), a₁ increases by a, and a₂ increases by 1.

Net change: a – 1 – a + 1 = 0.

*An edge whose endpoints are vertices from which a₁ and a₂ edges emanate is flattened: a*₀ increases by a₁ + a₂ – 2 – 2 (two vertices disappear), a₁ by a₁ + a₂ – 2 – 1 (two edges are shared, and one edge disappears), and a₂ by 1.

Net change: (a₁ + a₂ – 4) – (a₁ + a₂ – 3) + 1 = 0.

Here, a₁ = a₂ = 3.

Every polytope has a dual ----------------------------

The numbers of vertices and faces can be interchanged (the figure shows the cube as an example). The centers of the cube's faces—the cube being the primal polyhedron—are the vertices of the dual polyhedron. At each such vertex, the number of faces that meet equals the number of vertices on the corresponding face of the original cube. The dual of a cube is an octahedron, and conversely. The cube has eight vertices, twelve edges and six faces, whereas the octahedron has six vertices, twelve edges and eight faces.

Primal and dual polyhedra

illustrated by the cube–octahedron pair.

The dual of a tetrahedron—which has four vertices, six edges and four faces—is another tetrahedron. The dual of an icosahedron (twelve vertices, thirty edges and twenty faces) is a dodecahedron (twenty vertices, thirty edges and twelve faces), and conversely.

From dimension 4 onward, passing to the dual polytope reverses the order of the first n – 1 coefficients *a_i. Thus, the n-tuple (a*₀, a₁… *a_k … a_n*_‒2, *a_n*_‒1) becomes (*a_n*_‒1, *a_n*_‒2… *a_n*_‒*_k*_‒1 … a₁, a₀). The dual polytope of the tesseract (which has sixteen vertices, thirty-two edges, twenty-four faces and eight cells) is the hexadecachoron, or 16-cell (a polytope consisting of eight vertices, twenty-four edges, thirty-two faces and sixteen cells). Euler's formula remains valid for both geometric objects.

A representation of a hexadecachoron.

The icositetrachoron (with its twenty-four vertices, ninety-six edges, ninety-six faces and twenty-four cells) is self-dual. The hecatonicosachoron (600, 1,200, 720, 120) and the hexacosichoron (120, 720, 1,200, 600) are dual to each other.

Duality in linear programming --------------------------------------------

The concept of duality also arises in the problem-solving technique known as linear programming. The simplex algorithm was introduced in 1947 by the American mathematician George Bernard Dantzig (1914–2005). The problem is formulated as a system of inequalities expressing constraints (upper or lower bounds), each linear in the problem's variables (the word "simplex" comes into its own when slack variables are added to turn the inequalities into equalities, thereby moving from canonical form to standard form). The constraints define hyperplanes bounding a polytope whose vertices correspond to the problem's variables. An objective function, a linear combination of the variables, must be maximized (or minimized); it corresponds to a hyperplane independent of the polytope. The optimum is attained at a vertex of the polytope (where the objective function is at its best!). The algorithm then moves along the polytope's edges in a carefully chosen order to reach an optimal solution as quickly as possible. This is the primal problem.

The problem obtained by converting the variables of the primal problem into constraints and vice versa—and hence vertices into hyperplanes and vice versa—is called the dual problem, and its cost function gives the same optimal value! A solver (an algorithm that solves this type of optimization problem) can switch from the primal problem to the dual problem, and back again, as needed.

Once the inequalities have been replaced by equalities (standard form), the primal and dual problems do indeed have the same number of variables. This number—the dimension of the simplex—is equal to the number of constraints once the bounds on the variables, such as nonnegativity, have been taken into account. In practice, the number of variables in problems of this kind is highly… variable, ranging from a few dozen to a few thousand, or even far more in some applications.