## A Coxeter theoretic interpretation of Euler numbers

Matthieu Josuat-Verg`es

Universit´e de Marne-la-Vall´ee

SLC 69, Strobl, September 2012.

## Introduction

The Euler numbers *T*_{n} are defined via the generating function
tan(z) + sec(z) =X

n≥0

*T*_{n}*z*^{n}
*n!*

D´esir´e Andr´e showed that *T*_{n} is the number of alternating
permutations in *S*_{n}, i.e. those*w* such that

*w*(1)>*w*(2)<*w*(3)> . . .

Since then, a lot of interest has been given to these numbers and these permutations [Stanley, a survey of alternating permutations (2010)]

## Outline

Springer showed that, considering alternating permutations as the
largest *descent class*in *S*n, there is an analogue of *T*n for other
finite irreducible Coxeter groups (he also computed the value in
each case of the ABDE... classification).

There is another way to relate *T*_{n} with the symmetric group as a
Coxeter group, relying on a result of Stanley about orbits of
maximal chains in the set partition lattice. We present a method
to compute the value in each case of the classification.

Let P(n) be the lattice of set partitions of {1, . . . ,*n}. It is ordered*
by refinement: µ≤π if every block of µis contained in a block of
π.

For example: {{1,2,4},{3,6},{5}} ≤ {{1,2,4},{3,5,6}}.

A *maximal chain*in P(n) is a sequence π1<· · ·< πn where

◮ π_{1}={{1},{2}, . . . ,{n}},

◮ π_{n}={{1, . . . ,*n}},*

◮ π_{i+1} is obtained by joining two blocks of πi.

For example: {{1},{2},{3},{4}} <{{1,3},{2},{4}} <

{{1,3},{2,4}} <{{1,2,3,4}}.

*S*_{n} acts on these maximal chains in an “obvious way”, and Stanley
proved that the number of orbits is*T*_{n−1}.

In this talk, we see a finite Coxeter group *W* as a real reflection
group, i.e. we have a *defining representation W* ⊂*GL(V*) for some
Euclidian space *V*, such that *W* is generated by orthogonal

reflections.

*H* is a*reflecting hyperplane*if the orthogonal reflection through it
is in *W*.

Definition

*The set partition lattice*P(W)*is the set of all subspaces*
*H*_{1}∩ · · · ∩*H*_{r}

*where each H*i *is a reflecting hyperplane.*

*It is ordered by reverse inclusion.*

In type *A*_{n−1},*W* =*S*_{n} acts on *V* ={v∈R^{n} : P

*v*_{i} = 0} by
permuting coordinates.

*w* ∈*S*_{n}is a reflection if it permutes*v*_{i} and*v*_{j} for some *i* <*j*, i.e. is
the orthogonal reflection through the subspace

*H*_{ij} ={v ∈*V* : *v*_{i} =*v*_{j}}.

Then the set of all subspaces

*H*_{i}_{1}_{j}_{1}∩ · · · ∩*H*_{i}_{k}_{j}_{k}

is in bijection with set partitions. For example if *n*= 7:

*H*_{1,7}∩*H*_{2,4}∩*H*_{4,5}={v ∈*V* : *v*_{1} =*v*_{7}, *v*_{2} =*v*_{4}=*v*_{5}}

↔ {{1,7},{2,4,5},{3},{6}}.

And the refinement order on set partitions corresponds to reverse
inclusion in subspaces of *V*.

Let M(W) the set of maximal chains of the set partition lattice P(W).

There is an action of *W* on M(W), we consider the number of
orbits *K*(W) = #(M(W)/W).

So Stanley’s result is *K*(An) =*T*n.

(Remark: In Springer’s problem of the largest descent class, *T*_{n} is
the number associated to*S*_{n} i.e. type*A*_{n−1} and not*A*_{n}.)

What is *K*(W) for the other cases of the classification ?

## The general method

W acts on lines (=coatoms) in P(W). Let *L*_{1}, . . . ,*L*_{k} be some
orbit representatives. For each line *L*_{i}, let

Fix(L_{i}) ={w ∈*W* : *w*(x) =*x,*∀x ∈*L*_{i}},
Stab(L_{i}) ={w ∈*W* : *w*(L_{i}) =*L*_{i}}.

Proposition

Fix(L_{i})*is itself a Coxeter group, so* P(Fix(L_{i}))*and* M(Fix(L_{i}))
*are defined, they are acted on by* Stab(Li) *, and*

*K*(W) =

k

X

i=1

# M(Fix(L_{i}))/Stab(L_{i})
.

Remark If

◮ Stab(L_{i}) =Fix(L_{i}), or

◮ Stab(L_{i}) =Fix(L_{i})⋊{±Id},
then we have

# M(Fix(Li))/Stab(Li)

=*K*(Fix(Li)),
which we assume we already know by induction.

(note that {±Id} acts trivially onP(W))

Proof.

From each orbit of maximal chains, we can extract an orbit of
lines. It suffices to show that the number of orbits of maximal
chains associated to the orbit of *L*_{i} is # M(Fix(Li))/Stab(Li)

.
Fix(Li) is seen as a Coxeter group with defining representation
acting on *L*^{⊥}_{i} . The interval [ˆ0,*L*_{i}] inP(W) is identified with
P(Fix(L_{i})) (we use the bijection: subspaces containing*L*_{i} ↔
subspaces in *L*^{⊥}_{i} ).

The number of *W*-orbits of chains ˆ0<· · ·<*w*(L_{i})<ˆ1 for some
*w* ∈*W*, is also the number ofStab(Li)-orbits of chains

ˆ0<· · ·<*L*_{i} <ˆ1. Hence it is # M(Fix(Li))/Stab(Li)
.

Another useful result:

Proposition

*If W*_{1}*, and W*_{2} *have ranks m and n, we have:*

*K*(W_{1}×*W*_{2}) =

*m*+*n*
*m*

*K*(W_{1})K(W_{2}).

Proof.

A maximal chain in P(W1×*W*_{2}) is obtained by “shuffling” two
maximal chains in P(W_{1}) andP(W_{2}). For example from
*x*_{0} <· · ·<*x*_{m} and*y*_{0}<· · ·<*y*_{n} we can form

(x0,*y*_{0})<(x0,*y*_{1})<(x1,*y*_{1})<(x2,*y*_{1})< . . ..
The number of shuffles is the binomial coefficient.

This operation is still well-defined for the orbits of maximal chains.

## Case of the symmetric group S

_{n}## (type A

_{n−1}## )

Let *V* ={v ∈R^{n} : P

*v*_{i} = 0}. The coatoms are the 2-block set
partitions and a set of orbit representatives is:

*L*_{i} ={v ∈*V* : *v*_{1} =· · ·=*v*_{i}, *v*_{i+1} =· · ·=*v*_{n}}
with 1≤*i* ≤ ^{n}_{2}.

◮ If *i* < ^{n}_{2},Fix(L_{i}) =Stab(L_{i}) =*S*_{i} ×*S*n−i.

◮ If *i* = ^{n}_{2},Fix(Li) =*S*_{i} ×*S*_{i} andStab(Li) = (Si ×*S*_{i})⋊*S*_{2}
where*S*_{2} permutes the two factors in *S*_{i} ×*S*_{i}.

In the second case, we have

M(Fix(L_{i}))/Stab(L_{i}) =M(S_{i} ×*S*_{i})/(S_{i} ×*S*_{i})/S_{2}
where the *S*_{2}-action has no fixed point, so

#(M(Fix(L_{i}))/Stab(L_{i})) = 1

2*K*(S_{i}×*S*_{i}).

## Case of the symmetric group S

_{n}## (type A

_{n−1}## )

Let *a*_{n}=*K*(An), we obtain:

*a*_{n−1}= X

1≤i<^{n}_{2}

*n*−2
*i*−1

*a*_{i}_{−1}*a*_{n−i−1}+χ[n even]1
2

*n*−2
*n/2*−1

*a*_{n/2−1}^{2} .

This is equivalent to
*a*_{n−1} = 1

2

n−1

X

i=1

*n*−2
*i*−1

*a*_{i−1}*a*_{n−i−1}.

So *A(z*) = P

n≥0

*a*_{n}^{z}_{n!}^{n} satisfies*A*^{′}(z) = ^{1}_{2}(1 +*A(z)*^{2}) with*A(0) = 1.*

The solution is *A(z*) = tan(z) + sec(z).

## Case of B

_{n}Let *V* =R^{n}. In the case*B*_{n}, the reflecting hyperplanes are:

{v ∈*V* : *v*i = 0},{v ∈*V* : *v*i =*v*j}, and{v ∈*V* : *v*i =−vj}
(i <*j*).

As orbit representatives of the lines in P(Bn), we can take:

*L*_{i} ={v ∈*V* : *v*_{1} =· · ·=*v*_{i} = 0, *v*_{i+1}=· · ·=*v*_{n}},
with 0≤*i* ≤*n*−1. We have

Fix(Li) =*B*i×*A*_{n−i−1}, and Stab(Li) = (Bi×*A*_{n−i−1})⋊{±Id}.

So

*b*_{n}=

n−1

X

i=0

*n*−1
*i*

*b*_{i}*a*_{n−i−1}.

## Case of B

_{n}Let *B(z) =* P

n≥0

*b*_{n}^{z}_{n!}^{n}. The recursion

*b*_{n} =

n−1

X

i=0

*n*−1
*i*

*b*_{i}*a*_{n−i−1}, *b*_{0}= 1.

is equivalent to *B*^{′}(z) =*B(z*)A(z) and*B*(0) = 1.

The solution is *B*(z) =*A*^{′}(z) = _{1−sin(z)}^{1} .

So *b*_{n}=*T*_{n+1} (number of alternating permutations in*S*_{n+1}).

## Case of D

_{n}Let *V* =R^{n}. In type *D*n, the reflecting hyperplanes are:

{v ∈*V* : *v*_{i} =*v*_{j}}and {v ∈*V* : *v*_{i} =−v_{j}}(i <*j*).

As orbit representatives of the lines in P(Dn), we can take:

◮ *L*_{i} ={v ∈*V* : *v*_{1}=· · ·=*v*_{i} = 0, *v*_{i+1} =· · ·=*v*_{n}},

with*i* = 0 or 2≤*i* ≤*n*−1. We haveFix(Li) =*D*_{i}×*A*_{n−i−1},

Stab(L_{i}) =

(Di ×*A*_{n−i−1})⋊{±Id}if*n* is even,

(D_{i} ×*A*_{n−i−1})⋊{Id,(1,−1, . . . ,−1)} if*n* is odd and *i* >0.

(Di ×*A*_{n−i−1}) if*n* is odd and *i* = 0.

◮ And if *n* is even, we also include
*L*^{′}_{0} ={v ∈*V* : −v1=*v*_{2}=· · ·=*v*_{n}}.

We have Fix(L^{′}_{0}) =Stab(L^{′}_{0}) =*A*_{n−1}.

## Case of D

_{n}Let *d*_{n} =*K*(D_{n}) and ¯*d*_{n}= #(M(D_{n})/B_{n}). The recursion for *d*_{n} is:

*d*_{n}= 2a_{n−1}+

n−1

X

i=2

*n*−1
*i*

*d*_{i}*a*_{n−1−i}
if *n* is even, and

*d*_{n}=*a*_{n−1}+ X

2≤i≤n−1 n−ieven

n−1 i

*d*_{i}*a*_{n−1−i} + X

2≤i≤n−1 n−iodd

n−1 i

*d*¯_{i}*a*_{n−1−i}

if *n* is odd.

We need to compute ¯*d*_{n}= #(M(D_{n})/B_{n}).

The scheme for computing *K*(W) works for ¯*d*_{n}too and gives:

*d*¯_{n}=*a*_{n−1}+

n−1

X

i=2

*n*−1
*i*

*d*¯_{i}*a*_{n−1−i}.

Let ¯*D(z*) = P

n≥0

*d*¯_{n}^{z}_{n!}^{n}, the recursion is equivalent to:

*D*¯^{′}(z) = ( ¯*D(z)*−*z*)A(z), *D(0) = 1.*

This is solved by

*D(z*¯ ) = 2−cos(z)−*z*sin(z)
1−sin(z) .
It follows ¯*d*_{n} = 2T_{n+1}−(n+ 1)Tn if*n*≥2.

So for odd *n*≥2, we have*d*_{n}= 2T_{n+1}−(n+ 1)T_{n}.

From the recursions for ¯*d*_{n} and*d*_{n}, we have for even *n:*

(d_{n}−*d*¯_{n}) =*a*_{n−1}+

n−1

X

i=2

(d_{n}−*d*¯_{n})a_{n−i−1}.
Let *U*(z) = 1 + P

n≥2

(d_{n}−*d*¯_{n})^{z}_{n!}^{n}, the recursion is equivalent to:

*U*^{′}(z) =*U*(z) tan(z), *U*(0) = 1.

This is solved by *U*(z) = sec(z).

So for even *n*≥2 we have*d*_{n}= (d_{n}−*d*¯_{n}) +*d*_{n}= 2T_{n+1}−*nT*_{n}.

## Remaining cases

Dihedral groups:

*K*(I_{2}(m)) =

(1 if*n* is odd,
2 if*n* is even.

Exceptional groups: one method is to see them as symmetry groups of some semiregular polytopes, and use the geometry of these polytopes.

*K*(H3) = 4, *K*(H4) = 12, *K*(F4) = 16,
*K*(E_{6}) = 82, *K*(E_{7}) = 768, *K*(E_{8}) = 4056.

In all cases except *E*_{6}, the polytope is centrally symmetric and this
ensures we have Stab(L_{i}) =Fix(L_{i})⋊{±Id}.

The general method to find orbit representatives of lines in P(W) is the following.

Let *H*_{1}, . . . ,*H*_{n} so that the orthogonal reflections are simple
generators and

*L*_{i} =\

j6=i

*H*_{j}.

Then *L*_{1}, . . . ,*L*_{n} are representatives, except that if *L*_{i} =*w*_{0}(L_{j}) we
only take one of *L*_{i} and *L*_{j} (w_{0} is the longest element).

thanks for your attention