Growth diagrams and non-symmetric Cauchy identities over near staircases

(1)

Growth diagrams and non-symmetric Cauchy identities over near staircases

Olga Azenhas, Aram Emami

CMUC, University of Coimbra

The 72nd S´eminaire Lotharingien de Combinatoire Lyon

March 25, 2014

(2)

Plan

(Symmetric) Cauchy identity over rectangle shapes Non-symmetric Cauchy identities

on staircases

on truncated staircases

on near staircases

Growth diagrams and non-symmetric Cauchy identities over near staircases

(3)

Symmetric Cauchy identity

(Symmetric ) Cauchy identity

Y

(i,j)∈[k]×[m]

(1−xiyj)⁻¹ =

k

Y

i=1 m

Y

j=1

(1−xiyj)⁻¹

= X

ν⁺

sν⁺(x1, . . . ,xk)sν⁺(y1, . . . ,ym)

over all partitionsν⁺of length≤min{k,m}.

Left hand side is symmetric in the variablesxi andyj separately.

m

k = (m^k)

Bijective proof: D. E. Knuth. Pacific J. Math, 1970.

(4)

Symmetric Cauchy identity

Y

(i,j)∈[k]×[m]

(1−xiyj)⁻¹ =

k

Y

i=1 m

Y

j=1

(1−xiyj)⁻¹

= X

ν⁺

sν⁺(x1, . . . ,xk)sν⁺(y1, . . . ,ym)

m

k = (m^k)

(5)

Symmetric Cauchy identity

Y

(i,j)∈[k]×[m]

(1−xiyj)⁻¹ =

k

Y

i=1 m

Y

j=1

(1−xiyj)⁻¹

= X

ν⁺

sν⁺(x1, . . . ,xk)sν⁺(y1, . . . ,ym)

m

k = (m^k)

(6)

RSK: Robinson-Schensted-Knuth correspondence

RSK correspondence

{multisets of cells of } → ]

ν⁺∈N^k

SSYT(ν⁺,k)×SSYT(ν⁺,m)

b₁··· b_r a₁··· a_r

→ (F,G)

The multivariate generating function for the multisets of cells in (m^k)

Y

(i,j)∈(m^k)

(1−xiyj)⁻¹ = X

ν⁺N^k

X

(F,G)∈SSTY(ν⁺,k)×SSTY(ν⁺,m)

x^Fy^G

= X

ν⁺N^k

s_ν+(x₁, . . . ,x_k)s_ν+(y₁, . . . ,y_m) RSK correspondence gives an expansion of the Cauchy kernel in the basis of Schur polynomials.

Schur polynomial

s_ν+= X

T∈SSYT_n(ν⁺)

x^T

(7)

Non-symmetric Cauchy identity over staircases

Non-symmetric Cauchy identity over staircases A. Lascoux (2003)

Y

i+j≤n+1

(1−xiyj)⁻¹= X

ν∈Nⁿ

bκν(x)κων(y)

The left hand side is no more symmetric on the variablesx_i andy_j.

k n

m A. Lascoux (2003) RSK for bicrystals in typeA.

A. M. Fu, A. Lascoux (2009) algebraic proof

(8)

Bases for Z [x

₁

, . . . , x

_n

]

Linear bases for the ring of integer polynomialsZ[x₁, . . . ,x_n] Key polynomials{κν :ν∈Nⁿ} lift the Schur polynomialssν⁺

κ(ν_n,...,ν₁)=sν⁺, νn≤. . .≤ν1

Demazure atoms{bκν :ν∈Nⁿ}

κ_ν=X

β≤ν

bκ_β s_ν+ = X

ν∈Snν⁺

bκ_ν

The Bruhat ordering onSnνis defined to be the transitive closure of the relations

(ν1, . . . , νi, . . . , νj, . . . , νn)<(ν1, . . . , νj, . . . , νi, . . . , νn), ifνj< νi.

(9)

Bases for Z [x

₁

, . . . , x

_n

]

Linear bases for the ring of integer polynomialsZ[x₁, . . . ,x_n] Key polynomials{κν :ν∈Nⁿ} lift the Schur polynomialssν⁺

κ(ν_n,...,ν₁)=sν⁺, νn≤. . .≤ν1

Demazure atoms{bκν :ν∈Nⁿ}

κ_ν=X

β≤ν

bκ_β s_ν+ = X

ν∈Snν⁺

bκ_ν

The Bruhat ordering onSnνis defined to be the transitive closure of the relations

(ν1, . . . , νi, . . . , νj, . . . , νn)<(ν1, . . . , νj, . . . , νi, . . . , νn), ifνj< νi.

(10)

Combinatorial structure of key polynomials

Combinatorial rules for monomial expansions of the linear bases {κα:α∈Nⁿ}and{bκα:α∈Nⁿ}

Lascoux-Sch¨utzenberger (late 80’s) SSYTn(λ) = ]

α∈Snλ

{T ∈SSYTn:K+(T) =key(α)}

key(1,0,4,0,2) = 5 3 5

1 3 3 3

Kashiwara crystal bases (early 90’s); Haglund, Haiman, Loehr (2005); Mason (2009)

ˆ

κα(x) = X

T∈Bbα

x^T = X

K₊(T)=key(α)

x^T = X

sh(F)=α

x^F,

κα(x) = X

T∈B_α

x^T= X

K+(T)≤key(α)

x^T = X

sh(F)≤α

x^F.

(11)

Combinatorial structure of key polynomials

Combinatorial rules for monomial expansions of the linear bases {κα:α∈Nⁿ}and{bκα:α∈Nⁿ}

Lascoux-Sch¨utzenberger (late 80’s) SSYTn(λ) = ]

α∈Snλ

{T ∈SSYTn:K+(T) =key(α)}

key(1,0,4,0,2) = 5 3 5

1 3 3 3

Kashiwara crystal bases (early 90’s); Haglund, Haiman, Loehr (2005); Mason (2009)

ˆ

κα(x) = X

T∈Bbα

x^T = X

K₊(T)=key(α)

x^T = X

sh(F)=α

x^F,

κα(x) = X

T∈B_α

x^T= X

K+(T)≤key(α)

x^T = X

sh(F)≤α

x^F.

(12)

SSAFs encode SSYTs with the right keys (Mason,2008)

P

F Pe

η reverse Schensted row insertion Ψ

ρ

K+(P) =key(sh(F)) = 1 1 3 3 3 4 4 57

1 1 3 2 2 3 45 7 P=

7 3 2 5 2 4 13 1

Pe=

1 1

2 3 3

4 5 6 7 2 2

1 3 4 5 7 F =

(13)

A triangle of Robinson-Schensted-Knuth correspondences (Mason)

w

(eP,Q)e (F,G) (P,Q)

RSK Φ

reverse RSK

ρ Ψ

sh(F)⁺=sh(G)⁺=sh(P) =sh(Q) =sh(eP) =sh(eQ) key(sh(F)) =K+(P), key(sh(G)) =K+(Q)

(14)

RSK analogue restricted to truncated staircases

RSK analogue for staircases

{multisets of cells of } → ]

ν∈Nⁿ

{^(F^,G):sh(F^)=ν,^sh(G)≤ων}

b1··· br

a1··· ar

→ (F,G)

RSK analogue for truncated staircases {multisets of cells of } → ]

ν∈N^k

{(F,G):sh(F)=ν,(sh(G),0^n−m)≤(0^n−k,ων)}

b1··· br

a1··· ar

→ (F,G)

(15)

Bijective proof

Y

(i,j)∈

(1−x_iy_j)⁻¹ = X

ν∈N^k

X

F,G∈SSAFn

sh(G)=β∈N^m,sh(F)=ν (β,0^n−m)≤(0^n−k,ων)

x^Fy^G

= X

ν∈N^k

bκ_ν(x) X

Q∈B₍₀n−k,ων)

entries≤m

y^Q

= X

ν∈N^k

bκ_ν(x)π_σ(λ,SE)κ_(ων,0n−k)(y) (Lacoux,2003)

= X

ν∈N^k

bκν(x)κ₍₀m−k,α)(y)

The action of Demazure operatorsπi on key polynomialsκνcan be realised via bubble sorting operators acting onν, swapping entriesiandi+ 1 in the weak compositionν, ifνi> νi+1, and doing nothing, otherwise,

πiκα= (

κs_iα ifαi> αi+1

κα ifαi≤αi+1

.

(16)

Bijective proof

Y

(i,j)∈

(1−x_iy_j)⁻¹ = X

ν∈N^k

X

F,G∈SSAFn

sh(G)=β∈N^m,sh(F)=ν (β,0^n−m)≤(0^n−k,ων)

x^Fy^G

= X

ν∈N^k

bκ_ν(x) X

Q∈B₍₀n−k,ων)

entries≤m

y^Q

= X

ν∈N^k

bκν(x)πσ(λ,SE)κ_(ων,0^n−k₎(y) (Lacoux,2003)

= X

ν∈N^k

bκν(x)κ₍₀m−k,α)(y)

The action of Demazure operatorsπi on key polynomialsκνcan be realised via bubble sorting operators acting onν, swapping entriesiandi+ 1 in the weak compositionν, ifνi> νi+1, and doing nothing, otherwise,

πiκα= (

κs_iα ifαi> αi+1

κα ifαi≤αi+1

.

(17)

X

ν∈N^k

bκν(x)π_σ(λ,SE)κ_(ων,0n−k)(y) (Lascoux,2003)

1 2

.. .

.. . n-k

.. . ...

...

k- n+m

k . . . m-1 .. . m-1

m k

1≤k≤m≤n,andn−k≤m−1,

σ(λ,SE) = (sn−k. . .s1)· · ·(sm−2· · ·s_{k−(n+m)−1})(sm−1. . .sk−n+m)· · ·(sm−1· · ·sk)

(18)

Non-symmetric Cauchy identity over near staircases

We want to give a bijective proof for the identity:

Y

(i,j)∈

(1 − x

_i

y

_j

)

⁻¹

=

X

ν∈Nⁿ

π_r₁. . . π_r_pbκ_ν

(x )κ

_ων

(y)

=

X

ν∈Nⁿ

bκν

(x)π

n−rp. . . πn−r1κων

(y)

(Lascoux 2003)

Look at the biggest staircase contained inside the near staircases

(19)

Algebraic proof (Lascoux, 2003)

r+1

s⁼ⁿ⁻^r^{+ 1}

λ1=red shape∪green box∪blue box λ2= red shape∪green box

λ3=red shape

F_λ₃= Y

(i,j)∈λ₃

(1−x_iy_j)⁻¹, F_λ₂ = (1−x_ry_s)⁻¹F_λ₃= X

ν∈Nⁿ

bκ_ν(x)κ_ων(y).

π_rF_λ₂= (π_r(1−x_ry_s)⁻¹)F_λ₃=F_λ₂(1−x_r+1y_s)⁻¹=F_λ₁ Fλ₁= X

ν∈Nⁿ

πrbκν(x)κων(y) = X

ν∈Nⁿ

bκν(x)π_n−rκων(y).

The operatorπr reproduce cells.

(20)

Biwords in a Ferrers shape

w =

1 1 2 2 3 3 4 5 5 6 7

3 4 2 6 3 4 4 3 4 1 1

. The biwordw in the Ferrers shapeλ= (7,6,5,5,3,2,1) is represented by putting a cross×in the cell (i,j) ofλif

j i

is a biletter ofw.

×

× ×

×

× × λ= (7,6,5,5,3,2,1)

(21)

×

× ×

×

−→ ←−

e

_r²

f

_r²

1 3

1 4

3 3

3 4

4 4

5 3

5

(

4

)

¹

3 1 4

3 3

4 4

5 3

5

(

3

)

Apply the crystal operator e

_r

as long as it is possible to the second row of the biword w.

×

× ×

×

× × →

×

× ×

(

¹ 3 1 4

2 2

2 6

3 3 3 4

4 4

5 3

5 4 6 1

7

1

) → (

¹ 3 1 4 2 2 2 6 3 3 3 3 4 4 5 3 5 3 6 1 7 1

)

(22)

Growth diagram for the analogue of RSK

×

52 42 41 4 3 2 1

∅

4241413121 2 1 ∅

→

×

52 42 32 22 21 2 1

∅

4241413121 2 1 ∅

3 4 3 3

4 4 3

4 4 F

3 4 3 3 3 3 3

4 4

F

e

1 2 3 4 5 4 1

5 5 3 3 1

G = G

e

(23)

The shape of SSAF changes

×

× ×

×

× × →

×

× ×

(F

,

G ) ←− ( ˜ F

,

G ) sh(F ) = s

r

sh( ˜ F )

>

sh( ˜ F )

sh(G ) ≤

ωsh( ˜

F ) =

ωsr

sh(F )

sh(G )

ωsh(F

)

(24)

The shape of SSAF changes

×

× ×

×

× × →

×

× ×

(F

,

G ) ←− ( ˜ F

,

G ) sh(F ) = s

r

sh( ˜ F )

>

sh( ˜ F ) sh(G ) ≤

ωsh( ˜

F ) =

ωsr

sh(F )

sh(G )

ωsh(F

)

(25)

RSK analogue restricted to near staircases

RSK analogue for near staircases











multisets of cells with the sited boxes of











→ A^H_z^z =











(F,G):

sh(F)=ν sh(G)ωs_riz···bs_rim···s_ri

1ν, m=1,2,...,z sh(G)≤ωs_riz···s_ri

1ν











b₁··· b_r a₁··· a_r

→ (F,G)

(26)

Let 0≤p<nand 0<r1<r2<· · ·<rp≤n.

n . .

... ..r1

. .. rp

•

Y

(i,j)∈λ

(1−x_iy_j)⁻¹ = Y

i+j≤n+1

(1−x_iy_j)⁻¹

p

Y

i=1

(1−x_r_i₊₁y_n−r_i₊₁)⁻¹

= X

(F,G)∈A

x^Fy^G+

p

X

z=1

X

Hz∈(^[p]z) X

(F,G)∈A^Hz_z

x^Fy^G

(27)

X

ν∈Nⁿ

(πr₁. . . πr_pκbν(x))κων(y) =πr₁

X

ν∈Nⁿ

πr₂. . . πr_pκbν(x)κων(y)

!

= π_r₁







p−1

X

z=0

X

Hz∈(^[2,p]z ) X

(F,G)∈A^Hzz

x^Fy^G







=

p−1

X

z=0

X

Hz∈(^[2,p]z )





 X

(F,G)∈A^Hz_z

x^Fy^G+ X

(F,G)∈A^H

1 z+1 z+1

x^Fy^G







=

p

X

z=0

X

H_z∈(^[p]_z) X

(F,G)∈A^Hz_z

x^Fy^G

π_r₁bκ_α=







κbs_r₁α+bκα ifαr > αr+1

bκα ifαr₁=αr₁+1

0 ifαr₁< αr₁+1

.