Euler’s Formula, Fibonacci, the Bayer-Billera Theorem, and Fine’s CD-index

Bill Gessley proving Euler’s formula (at UMKC)

In the earlier post about Billerafest I mentioned the theorem of Bayer and Billera on flag numbers of polytopes. Let me say a little more about it.

1. Euler

Euler’s theorem asserts that for a 3-polytope P

V-E+F=2.

The extension to d-dimensions asserts that for every d-polytope

The Euler Relation: 

There were several incomplete proofs of Euler’s theorem in the late 19th century, but the first complete proof came via Poincare’s work in algebraic topology and the Euler-Poincare theorem. Later, simple geometric proofs were found and the gap in certain 19th theory proofs which relied on an unproved assumption of shellability was completed when Bruggesser and Mani proved in 1970 that the boundary of every d-polytope is shellable.

2. Fibonacci

Let’s move now to flag numbers. Consider a d-polytopes P. for a set {-1,0,1,2,…,d-1,d}, { } , , define the flag number as the number of chains of faces , where .  We will assume from now on that S contains both ‘-1’, and ‘d’. (Adding or deleting these entries from S does not change the value of the flag number.) Let  be the dth Fibonacci number. (, , , , etc.)  Bayer and Billera proved:

Theorem: the affine dimension of flag numbers of d-polytopes is

There are many linear relations among the flag numbers that are implied by Euler’s theorem. For example: . This follows from the fact that every 1-polytope has 2 vertices. (This is Euler’s formula for dimension 1.) Another example: . This follows from the fact that a polygon has the same number of vertices as edges which is Euler’s formula for d=2. Here are two, more complicated, examples: and . Let’s understand the first of the two: Fix a flag of faces

, where   and .

Consider all faces G between and . This set of faces is in one to one correspondence with the set of faces of a 4-dimensional polytope Q.  A k-face between and corresponds to a (k-2)-face of Q. Euler’s formula asserts that . Summing over all flags gives us the required formula.

The proof of the second relation is similar except that in this case Q is 5-dimensional, so Euler’s theorem asserts that the alternating sum is 2. This accounts for the term when we sum over all chains .

Now we can explain the connection to Fibonacci numbers.

If {-1,0,1, …,d} and S contains two consecutives integers i and i+1, consider the pair i and i+1 of consecutive integers that S contains with i nonnegative and minimal. Let j be the maximal element of S below i. Write R= S\i. Just like the two examples above, we can express in terms of the flag numbers and , where m ranges over all integers between j and i.

Ha! but this shows that if S contains two consecutive elements then can be expressed as a linear combination of flag numbers with “smaller” indices! This implies that every flag number can be expressed as a linear combination of those with no consecutive integers and this gives us the Fibonacci numbers.

The harder part of the Bayer-Billera Theorem was to construct d-polytopes whose sequences of flag numbers are affinely independent.  The construction is simple: It is based on polytopes expressed by words of the form PBBPBPBBBPBP  where you start with a point, and P stands for “take a pyramid” and B stands for “take a bipyramid.”  And the word starts with a P (to the left) and has no two consecutive B’s. But proving that the flag numbers of all these polytopes are affinely independent is harder. By now there are a few other constructions.

3. The CD index

Every flag number of d-polytopes can be expressed as a linear combination of flag numbers with -1 and d elements of S and with no two consecutive integers. Are there other Fibonacci numbers of parameters of d-polytopes?  The cd-index discovered by Fine is a beautiful mysterious parameters for d-polytopes, each given by a linear combination of flag numbers.

Define h flag numbers:   .

Associate for every  subset S of {0,1,…,d-1} a monomial W(S) in non commuting variables a and b. You simply take a word in a’s and b’s where you take a for indices in S and b for indices not in S. For example, if d=10 and S={0,3,6,7} associate to S the monomial W(S)=abbabbaabb.

Write a polynomial with non commutative variables a and b:

consider two new variables c=a+b d=ab+ba.

Express   as a polynomial in c and d. This is possible! (But requires a proof.)

The cd-index of P are the coefficients of the  monomials in the new variables c and d.

Excercise (A solution by Jonathan Vos Post appears in the comment part): What is the cd-index of the 24-cell?