## 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: $f_0(P) - f_1(P) +F_2(P) + \dots + (-1)^d f_{d-1}(P) = 1 - (-1)^d.$

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 $S \subset$ {-1,0,1,2,…,d-1,d}, $S=${ $i_1,i_2,\dots,i_k$} , $i_1, define the flag number $f_S$ as the number of chains of faces $F_1 \subset F_2 \subset \dots F_k$, where $\dim F_j=i_j$.  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 $c_d$ be the dth Fibonacci number. ($c_1=1$, $c_2=2$, $c_3=3$, $c_4=5$, etc.)  Bayer and Billera proved:

### Theorem: the affine dimension of flag numbers of d-polytopes is $c_d-1$

There are many linear relations among the flag numbers that are implied by Euler’s theorem. For example: $f_{01}=2f_1$. This follows from the fact that every 1-polytope has 2 vertices. (This is Euler’s formula for dimension 1.) Another example: $f_{02}=f_{12}$. 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: $f_{1569}=f_{1469}-f_{1369}+f_{1269}$ and $f_{1679}=f_{1579}-f_{1479}+f_{1379}-f_{1279}+2f_{179}$. Let’s understand the first of the two: Fix a flag of faces

$F_1 \subset F_6\subset F_9$, where $\dim F_1=1,$  $\dim F_6 =6$ and $\dim F_9=9$.

Consider all faces G between $F_1$ and $F_6$. This set of faces is in one to one correspondence with the set of faces of a 4-dimensional polytope Q.  A k-face $H$ between $F_1$ and $F_6$ corresponds to a (k-2)-face of Q. Euler’s formula asserts that $f_0(Q)-f_1(Q)+f_2(Q)-f_3(Q)=0$. Summing over all flags $F_1 \subset F_6 \subset F_9$ 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 $2f_{179}$ when we sum over all chains $F_1 \subset F_7 \subset F_9$

Now we can explain the connection to Fibonacci numbers.

If $S \subset$ {-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 $f_S$ in terms of the flag numbers $f_R$ and $f_{R \cup m}$, where m ranges over all integers between j and i.

Ha! but this shows that if S contains two consecutive elements then $f_S$ 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 $c_d$ 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 $f_S$ 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 $c_d$ parameters for d-polytopes, each given by a linear combination of flag numbers.

Define h flag numbers: $h_S = \sum_{T \subset S}$ $(-1)^{|S \backslash T|}f_T$ .

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:

$\Psi= \sum_S h(S) W(S).$

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

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

The cd-index of P are the coefficients of the $c_d$ 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?