A Coxeter theoretic interpretation of Euler numbers

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_nzⁿ n!

D´esir´e Andr´e showed that T_n is the number of alternating permutations in S_n, i.e. thosew 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 classin Sn, there is an analogue of Tn 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 chainin P(n) is a sequence π1<· · ·< πn where

◮ π₁={{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 isT_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 areflecting hyperplaneif the orthogonal reflection through it is in W.

Definition

The set partition latticeP(W)is the set of all subspaces H₁∩ · · · ∩H_r

where each Hi is a reflecting hyperplane.

It is ordered by reverse inclusion.

In type A_n−1,W =S_n acts on V ={v∈Rⁿ : P

v_i = 0} by permuting coordinates.

w ∈S_nis a reflection if it permutesv_i andv_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_i1j1∩ · · · ∩H_ikjk

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

H_1,7∩H_2,4∩H_4,5={v ∈V : v₁ =v₇, v₂ =v₄=v₅}

↔ {{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) =Tn.

(Remark: In Springer’s problem of the largest descent class, T_n is the number associated toS_n i.e. typeA_n−1 and notA_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₁, . . . ,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 containingL_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₁, and W₂ have ranks m and n, we have:

K(W₁×W₂) =

m+n m

K(W₁)K(W₂).

Proof.

A maximal chain in P(W1×W₂) is obtained by “shuffling” two maximal chains in P(W₁) andP(W₂). For example from x₀ <· · ·<x_m andy₀<· · ·<y_n we can form

(x0,y₀)<(x0,y₁)<(x1,y₁)<(x2,y₁)< . . .. 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

(type A

)

Let V ={v ∈Rⁿ : P

v_i = 0}. The coatoms are the 2-block set partitions and a set of orbit representatives is:

L_i ={v ∈V : v₁ =· · ·=v_i, v_i+1 =· · ·=v_n} with 1≤i ≤ ⁿ₂.

◮ If i < ⁿ₂,Fix(L_i) =Stab(L_i) =S_i ×Sn−i.

◮ If i = ⁿ₂,Fix(Li) =S_i ×S_i andStab(Li) = (Si ×S_i)⋊S₂ whereS₂ 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₂ where the S₂-action has no fixed point, so

#(M(Fix(L_i))/Stab(L_i)) = 1

2K(S_i×S_i).

Case of the symmetric group S

(type A

)

Let a_n=K(An), we obtain:

a_n−1= X

1≤i<ⁿ₂

n−2 i−1

a_i−1a_n−i−1+χ[n even]1 2

n−2 n/2−1

a_n/2−1² .

This is equivalent to a_n−1 = 1

2

n−1

X

i=1

n−2 i−1

a_i−1a_n−i−1.

So A(z) = P

n≥0

a_n^z_n!ⁿ satisfiesA^′(z) = ¹₂(1 +A(z)²) withA(0) = 1.

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

Case of B

Let V =Rⁿ. In the caseB_n, the reflecting hyperplanes are:

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

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

L_i ={v ∈V : v₁ =· · ·=v_i = 0, v_i+1=· · ·=v_n}, with 0≤i ≤n−1. We have

Fix(Li) =Bi×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_ia_n−i−1.

Case of B

Let B(z) = P

n≥0

b_n^z_n!ⁿ. The recursion

b_n =

n−1

X

i=0

n−1 i

b_ia_n−i−1, b₀= 1.

is equivalent to B^′(z) =B(z)A(z) andB(0) = 1.

The solution is B(z) =A^′(z) = _1−sin(z)¹ .

So b_n=T_n+1 (number of alternating permutations inS_n+1).

Case of D

Let V =Rⁿ. In type Dn, 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₁=· · ·=v_i = 0, v_i+1 =· · ·=v_n},

withi = 0 or 2≤i ≤n−1. We haveFix(Li) =D_i×A_n−i−1,

Stab(L_i) =







(Di ×A_n−i−1)⋊{±Id}ifn is even,

(D_i ×A_n−i−1)⋊{Id,(1,−1, . . . ,−1)} ifn is odd and i >0.

(Di ×A_n−i−1) ifn is odd and i = 0.

◮ And if n is even, we also include L^′₀ ={v ∈V : −v1=v₂=· · ·=v_n}.

We have Fix(L^′₀) =Stab(L^′₀) =A_n−1.

Case of D

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_ia_n−1−i if n is even, and

d_n=a_n−1+ X

2≤i≤n−1 n−ieven

n−1 i

d_ia_n−1−i + X

2≤i≤n−1 n−iodd

n−1 i

d¯_ia_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_ntoo and gives:

d¯_n=a_n−1+

n−1

X

i=2

n−1 i

d¯_ia_n−1−i.

Let ¯D(z) = P

n≥0

d¯_n^z_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)−zsin(z) 1−sin(z) . It follows ¯d_n = 2T_n+1−(n+ 1)Tn ifn≥2.

So for odd n≥2, we haved_n= 2T_n+1−(n+ 1)T_n.

From the recursions for ¯d_n andd_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!ⁿ, 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 haved_n= (d_n−d¯_n) +d_n= 2T_n+1−nT_n.

Remaining cases

Dihedral groups:

K(I₂(m)) =

(1 ifn is odd, 2 ifn 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₆) = 82, K(E₇) = 768, K(E₈) = 4056.

In all cases except E₆, 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₁, . . . ,H_n so that the orthogonal reflections are simple generators and

L_i =\

j6=i

H_j.

Then L₁, . . . ,L_n are representatives, except that if L_i =w₀(L_j) we only take one of L_i and L_j (w₀ is the longest element).

thanks for your attention