Proofs Without Words

$2\times 3 = 3\times 2$. Ecce!

Figure 1.

***** ******* *****

In this ‘proof,’ terms in the equation correspond to objects in the figure, and the identity is ‘proved’ by appealing to geometric symmetries of the figure. Symmetries mean a group $G$, acting on suitable objects in some space $\mathbb{X}$.

Many proofs without words take the following form: an identity $A=B$ is ‘proved’ by exhibiting an object $\alpha$ in $\mathbb{X}$ ‘representing’ $A$, which may be cut into pieces which can be rearranged (i.e., translated by elements of the group $G$) to form a new object $\beta$ ‘representing’ $B$. Such proofs often work best when $A$ and $B$ take values in an abelian group $\mathcal{P}$ (which need bear no direct relation to $G$), and the pieces into which $\alpha$ and $\beta$ are decomposed also represent elements in $\mathcal{P}$. The group $\mathcal{P}$ should be abelian because in a (planar) figure composed of several pieces there is no obvious order in which to ‘multiply’ the pieces. Pictorial identities in such groups $\mathcal{P}$ are called scissors congruences. An example is the Pythagorean identity $A^2+B^2=C^2$ for the sides of a right-angled triangle; see Figure 2.

Figure 2.

Pythagoras as a scissors congruence.

In this example $\mathcal{P}$ is $\mathbb{R}$ (where the areas $A^2$, $B^2$ and $C^2$ of the three squares take values) and $G$ is the group of isometries of the (Euclidean) plane.

Everyone knows the ‘proof without words’ for the commutative law for multiplication. There is another commutative law which is a bit trickier to see, one involving information. Let’s play twenty questions, and to save time let’s reduce the play to two questions. Let’s further assume that the questions allow only yes-no answers. You think of an object $X$ drawn from some class $\Omega$ of possible objects and I ask two yes-no questions $\alpha$ and $\beta$. Whatever we may mean by ‘information,’ it stands to reason that the amount of information I obtain from asking my questions does not depend on the order I ask them: if $H$ denotes the information I gain from asking a series of questions, and $\alpha \wedge \beta$ means I first ask $\alpha$ and then $\beta$, then I should have

$$H(\alpha \wedge \beta ) = H(\beta \wedge \alpha ).$$

On the other hand, I can compute $H(\alpha \wedge \beta )$ another way. Evidently $H(\alpha \wedge \beta )$ is equal to $H(\alpha )$ (the information I get by asking $\alpha$) plus the information I get from $\beta$ conditioned on having already obtained an answer to $\alpha$ (this is the chain rule for information). This second quantity is denoted $H(\beta | \alpha )$, and now my commutative law takes the form

$$H(\alpha ) + H(\beta | \alpha ) = H(\beta ) + H(\alpha |\beta ).$$

Our goal is to give a ‘proof without words’ for this equation.

To translate this into more traditional mathematics, $\Omega$ is a space with a probability measure on it and $X$ is a random variable. For concreteness let’s take $\Omega$ to be the unit interval $[0,1]$ and $X$ to be a random number drawn from this interval. A question about $X$ amounts to choosing some (measurable) subset of $\Omega$ and asking whether $X$ is in this subset or not. Again, for concreteness, let’s take $\alpha$ to be the question ‘is $X<p$?’ and $\beta$ to be the question ‘is $X<q$?’ for some fixed $0 < p < q < 1$.

Entropy is a numerical measure of information; it is given by a (rather opaque) formula

$$H(\alpha )\coloneq -p\log (p) - (1-p)\log (1-p)$$

which we write as a function $h(p)$ of $p$ since it depends only on $p$. One heuristic way to think about this formula is to observe that probabilities of independent events multiply, whereas we want to think of information as additive. Thus we define the entropy of an event as the log of its probability, and then the entropy of a question is the expectation of the entropy of an answer to that question. The conditional information $H(\beta |\alpha )$ is either zero if $X<p$ (because in that case we already know $X<q$) and otherwise is equal to $h(\frac{1-q}{1-p})$ because if we already know that $X>p$, the question ‘is $X<q$?’ has a ‘no’ answer with probability $(1-q)/(1-p)$. Thus our entropy equation becomes

$$h(p) + (1-p)h\left(\frac{1-q}{1-p}\right) = h(q) + qh\left(\frac{p}{q}\right)$$

and this is the form in which we shall give a proof without words.

OK. To present our proof without words we need three things: a class of geometric objects which will represent allowable terms in our equation, a group $G$ of symmetries so that geometric objects that differ by an element of $G$ will be considered to represent ‘the same’ term, and a list of allowable dissections of our objects that will represent addition of terms in the equation.

The objects in our figure will be certain plane polygons assembled from pieces called $H$-trapezoids. A trapezoid is a quadrilateral with two parallel sides. A trapezoid is horizontal if the two parallel sides are horizontal. Unless it is a parallelogram, the other two sides, when extended, intersect at a point. An $H$-trapezoid is a horizontal trapezoid whose non-horizontal sides intersect at a point on the $x$-axis (for simplicity we’ll only consider $H$-trapezoids which lie on the positive side of the $x$-axis).

What about the group $G$? It is generated by three kinds of transformations which permute $H$-trapezoids:

(1)

horizontal translations $(a,b) \to (a+\lambda ,b)$ for $\lambda \in \mathbb{R}$;

(2)

horizontal shears $(a,b) \to (a+\lambda b,b)$ for $\lambda \in \mathbb{R}$;

(3)

dilations $(a,b) \to (\lambda a,\lambda b)$ for $\lambda \in \mathbb{R}^+$.

Translations and dilations together generate the affine group of the line $\mathbb{R}\rtimes \mathbb{R}^+$. Shears commute with both translations and dilations; thus $G \cong \mathbb{R}\oplus (\mathbb{R}\rtimes \mathbb{R}^+)$. Figure 3 shows four different $H$-trapezoids which are congruent under the $G$-action.

Figure 3.

$G$-equivalent $H$-trapezoids.

Finally we must say what sorts of ‘dissections’ are permitted; this is the geometric avatar of ‘addition’ in the abelian group where information will take its values. We shall define an abelian group $\mathcal{P}$ generated by $G$-equivalence classes of $H$-trapezoids modulo the relation $A+B = C$ whenever $C$ is an $H$-trapezoid decomposed into two $H$-trapezoids $A$ and $B$ by a straight line $\ell$ of one of the following two sorts:

(1)

(horizontal cut): $\ell$ is any horizontal line; or

(2)

(vertical cut): $\ell$ is any non-horizontal line concurrent with the non-horizontal edges of $C$.

These two decompositions are illustrated in Figure 4.

Figure 4.

Addition of $H$-trapezoids.

It turns out that as an abelian group, $\mathcal{P}$ is isomorphic to $\mathbb{R}\otimes _\mathbb{Z}\mathbb{R}^+$ where the first factor is $\mathbb{R}$ with its additive structure, and the second factor is $\mathbb{R}^+$ with its multiplicative structure. To see this observe first that every $H$-trapezoid may be scaled by a dilation so that its top edge has height $1$, and then it is determined up to the $G$-action by two numbers—the width $w$ of the top edge and the height $h$ of the bottom edge. Let’s denote this $G$-equivalence class of $H$-trapezoid by $T(w,h)$. A horizontal cut decomposes $T(w,h_1h_2)$ into $T(w,h_1)+T(w,h_2)$; a vertical cut decomposes $T(w_1+w_2,h)$ into $T(w_1,h)+T(w_2,h)$. Finally, $T(nw,h)= nT(w,h) = T(w,h^n)$ for any (positive) integer $n$, as can be seen by repeated shears, dilations, and the addition laws.

Identifying $\mathcal{P}$ with $\mathbb{R}\otimes _\mathbb{Z}\mathbb{R}^+$ shows how to make $\mathcal{P}$ into an $\mathbb{R}^+$-module: $\mathbb{R}^+$ acts by (scalar) multiplication on the left factor. In other words, for any $t\in \mathbb{R}^+$ and any $T(w,h)$ we define $t\cdot T(w,h) = T(tw,h)$. Geometrically this is achieved by stretching an $H$-trapezoid in the horizontal direction by a factor of $t$ (or, what is equivalent as classes in $\mathcal{P}$, stretching it in the vertical direction by a factor of $1/t$).

Where does entropy come in? To see this we must take an unexpected detour into hyperbolic geometry. Poincaré’s upper half-space model of the hyperbolic plane is the subset $\mathbb{H}\subset \mathbb{R}^2$ consisting of points $(x,y)$ where $y>0$, except that at points of height $y$ we scale the Euclidean metric infinitesimally by the factor $1/y$.

The action of $G$ on the upper half-space does not preserve the hyperbolic metric; however it does preserve the hyperbolic area form. It follows that hyperbolic area defines a (surjective) homomorphism from $\mathcal{P}$ to $\mathbb{R}$.

The connection to entropy becomes clearer once we compute that the hyperbolic area of $T(a,a)$ is $-a\log (a)$. To see this, observe that $T(a,a)$ has a representative of its $G$-equivalence class with vertices at $(0,1),(a,1),(0,a),(a^2,a)$. Then we may compute

$$\mathrm{area}(T(a,a))=\int _{y=a}^{y=1} \int _{x=0}^{x=ay} \frac{1}{y^2} dx dy = -a\log {a}.$$

In particular, $h(p)$ is the area of the expression $[p]\coloneq T(p,p)+T(1-p,1-p)\in \mathcal{P}$, and the entropy equation will follow from an analogous identity in $\mathcal{P}$:

$$[p] + (1-p)\left[ \frac{1-q}{1-p}\right] = [q] + q\left[\frac{p}{q}\right].$$

Figure 5.

The entropy equation as a scissors congruence in $\mathcal{P}$.

At long last we may give the proof of this identity without words; this is Figure 5. On the left $[p]$ is in blue and $(1-p)[\frac{1-q}{1-p}]$ is in yellow while on the right $[q]$ is in blue and $q[\frac{p}{q}]$ is in yellow. These are evidently equidecomposable in $\mathcal{P}$.

One may think of this picture in several ways. The map $\phi :(x,y) \to (\frac{x}{y},\log {y})$ is a diffeomorphism from the upper half space to $\mathbb{R}^2$; if we think of $\mathbb{R}^2$ as $T^*\mathbb{R}$ with its tautological symplectic form $\omega$, then $\phi ^*\omega$ is the hyperbolic area form and the group $G$ acts by symplectomorphisms.

In fact, one may reinterpret Figure 5 as a scissors congruence in a somewhat different group. In place of the group $G$ one can consider the group $G'$ generated by horizontal translations, dilations, and reflection in the $y$-axis $(a,b) \to (-a,b)$; and then we may define $\mathcal{P}'$ to be the abelian group generated by $G'$-equivalence classes of $H$-trapezoids modulo horizontal or vertical cuts. Now $G'$ really is a group of hyperbolic isometries (it is the ‘parabolic’ subgroup of hyperbolic isometries fixing a point at infinity) and $\mathcal{P}'$ is a rather interesting refinement of $\mathcal{P}$. The decomposition in Figure 5 proves a valid identity in $\mathcal{P}'$ which is now harder to interpret because of the more complicated structure of $\mathcal{P}'$ as an abelian group.

The $\mathbb{R}$-vector space spanned by formal symbols $[x]$ for $0<x<1$ modulo the entropy equation is denoted $\beta _2$, and is a kind of ‘additive linearization’ of the Bloch group, which arises in the geometry of 3-dimensional hyperbolic polyhedra. There is a short exact sequence called the Cathelineau complex

$$0 \to \beta _2 \to \mathbb{R}\otimes _\mathbb{Z}\mathbb{R}^+ \to \Omega ^1_{\mathbb{R}/\mathbb{Q}}\to 0$$

where $\Omega ^1_{\mathbb{R}/\mathbb{Q}}$ is the (additive) group of Kähler differentials of $\mathbb{R}$ over $\mathbb{Q}$. After our identification of $\mathcal{P}$ with $\mathbb{R}\otimes _\mathbb{Z}\mathbb{R}^+$, the first map is $[a] \to T(a,a)+T(1-a,1-a)$ and the second map is $T(a,b) \to (a/b) db$.

This sequence is closely related to the famous ‘Dehn–Sydler–Jessen’ sequence which encodes (among other things) the fact that volume and the Dehn invariant together are a complete invariant of scissors congruence for 3-dimensional Euclidean polyhedra. What is the deeper connection between 3-dimensional polyhedra, hyperbolic and symplectic geometry, Kähler differentials, $H$-trapezoids, and the chain rule for conditional entropy? I am at a loss for words.

Author’s Note

Cathelineau’s paper (which contains much more than is discussed here) is “Remarques sur les différentielles des polylogarithmes uniformes” and appeared in Ann. Inst. Fourier (Grenoble) 46 (1996), no. 5, 1327–1347. I learned about this paper, and its connection to the Dehn–Sydler–Jessen theorem, from Daniil Rudenko. I’d like to thank Rich Schwarz, Amie Wilkinson and the anonymous referee for comments on earlier versions of this note.

Danny Calegari is a professor of mathematics at the University of Chicago. His email address is dannyc@math.uchicago.edu.

Article DOI: 10.1090/noti2557

Credits

Figure 1, Figures 3–5, and author photo are courtesy of Danny Calegari.

Figure 2 is courtesy of Scott Sheffield.