Euler's Formula, Proof 17: Valuations

This proof comes from Klain and Rota, who develop it as part of a more general theory of invariant measures on Euclidean spaces. Thanks also to Robin Chapman for helping explain it to me.

Let $U^d$ be the vector space of functions from ${\mathbb{R}}^d$ to $\mathbb{R}$, and $V^d$ be the subspace of $U^d$ generated by characteristic functions of compact convex sets in ${\mathbb{R}}^d$. We define a function ${\chi }_d$ that maps $V^d$ to real numbers, as follows:

• If $d=1$, for any function $f$ in $V^d$, let $$\mathrm{D}f(x)=f(x)-\underset{y\to x^{+}}{lim}f(y)$$ $${\chi }_1(f)=\sum _{x\in \mathbb{R}}Df(x)$$ (Note that this sum always has only a finite number of nonzero terms.)

• If $d>1$, partition the coordinates of ${\mathbb{R}}^d$ into sets of $d-1$ and $1$ coordinate: $${\mathbb{R}}^d={\mathbb{R}}^{d-1}\times \mathbb{R}.$$ Thus we can represent any point in ${\mathbb{R}}^d$ as a pair $(x,z)$ where $x$ is in ${\mathbb{R}}^{d-1}$ and $z$ is in $\mathbb{R}$. For any function $f$ in $V^d$, and any $z$ in $\mathbb{R}$, let $f_z$ denote the restriction of $f$ to a $(d-1)$-dimensional cross-section: $f_z(x)=f(x,z)$, so $f_z$ is a function in $V^{d-1}$. We then define $${\chi }_d(f)=\sum _{z\in \mathbb{R}}\mathrm{D}{\chi }_{d-1}(f_z).$$

Because $\mathrm{D}$ and $\sum$ are linear operators, $\chi$ is a linear function from $V^d$ to $\mathbb{R}$. It can also be shown by a simple induction on dimension that, if $f$ is the characteristic function of a compact convex set $K$, then $\chi (f)=1$: By induction, $\chi (f_z)$ is the characteristic function of a closed interval, from which it is clear from the definition that $\sum \mathrm{D}\chi (f_z)$ is $1$. Thus also (since $V^d$ has the characteristic functions of convex compact sets as its basis) $\chi$ is well defined independently of the choice of coordinates for ${\mathbb{R}}^d$.

If $g$ is the characteristic function of the relative interior of a polytope $K$, it is in $V^d$ (by inclusion-exclusion of lower-dimensional faces) and a similar induction shows that $\chi (g)=(-1{)}^m$, where $m$ is the dimension of $K$: Because of the independence of $\chi$ from the coordinate system, we can assume $m=d$. Each cross-section of $K$ is itself a polytope, so by induction $\chi (g_z)$ is $(-1{)}^{m-1}$ times the characteristic function of an open interval, and the effect of the $\sum$ and $\mathrm{D}$ operators is to multiply by another factor of $-1$.

Now we let $K$ be a convex polytope, and evaluate $\chi$ on its characteristic function in two different ways, by partitioning $K$ into the disjoint union of the relative interiors of its faces. By linearity of $\chi$, the sum of its values on these relative interiors must be the same as its value on all of $K$, that is, $$1=\sum (-1{)}^m$$ where the sum is over the set of faces of $K$ (including $K$ itself). Grouping the faces by their dimensions, we get a form of Euler's formula: $$1=\sum _{i=0}^d(-1{)}^i{f}_i.$$

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