Federico Castillo

Fu Liu

Ehrhart Positivity for Generalized Permutohedra

Keywords: Ehrhart polynomials, Generalized permutohedra, Perturbations, Valuations

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Let P ⊂ R n be a lattice polytope. A natural enumerative problem is to compute |P ∩ Z n |, the number of integral points contained in P . To study this question, it is very helpful to consider a more general counting problem. Define

L P (n) := |nP ∩ Z n |
It is a classic result that L P (n) is a polynomial in n. More precisely:

Theorem 1.1 (Ehrhart) There exists a polynomial E P (x) such that E P (n) = L P (n) for any n ∈ Z ≥0 . Moreover, the degree of E P (x) is equal to the dimension of P .

We call L P (n) the Ehrhart polynomial of P. Some coefficients of L P (n) are well understood: the leading coefficient is equal to the normalized volume of P , the second coefficient is one half of the sum of the normalized volumes of facets, and the constant term is always 1. However, little is known about the other coefficients. They are not integers nor positive in general. We say a polytope has Ehrhart positivity or is Ehrhart positive if it has positive Ehrhart coefficients.

There are few families of polytopes known to be Ehrhart positive. Zonotopes, in particular the regular permutohedra, are Ehrhart positive (Theorem 2.2 [START_REF] Stanley | A zonotope associated with graphical degree sequences[END_REF]). Cyclic polytopes also have this property. Their Ehrhart coefficients are given by the volumes of certain projections of the original polytope [START_REF] Liu | Ehrhart polynomials of cyclic polytopes[END_REF]. Stanley-Pitman polytopes are defined in [START_REF] Stanley | A polytope related to empirical distributions, plane trees, parking functions, and the associahedron[END_REF] where a formula for the Ehrhart polynomial is given and from which Ehrhart positivity follows. Recently in [START_REF] Jesús | Ehrhart polynomials of matroid polytopes and polymatroids[END_REF] De Loera, Haws, and Koeppe study the case of matroid polytopes and conjecture they are Ehrhart positive. Both Stanley-Pitman polytopes and matroid polytopes fit into a bigger family: generalized permutohedra.

In [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF] Postnikov defines generalized permutohedra as polytopes obtained by moving the vertices of a usual permutohedron while keeping the same edge directions. That's what he called a generalized permutohedron of type z. He also considers a strictly smaller family, type y, consisting of sums of dilated simplices. He describes the Ehrhart polynomial for the type y family in [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF]Theorem 11.3], from which Ehrhart positivity follows. The type y family includes the Stanley-Pitman polytopes, associahedra, cyclohedra, and more, but fails to contain matroid polytopes, which are type z generalized permutohedra [1,Proposition 2.4].

We give the following conjecture:

Conjecture 1.2 Generalized permutohedra are Ehrhart positive.

Note that since generalized permutohedra contain the family of matroid polytopes, our conjecture is a generalization of the conjecture on Ehrhart positivity of matroid polytopes given in [START_REF] Jesús | Ehrhart polynomials of matroid polytopes and polymatroids[END_REF] by De Loera et al.

The main result of this paper is to reduce the above conjecture to another conjecture which only concerns regular permutohedron, a smaller family of polytopes. Before we give the other conjecture, we need to introduce a result of Berline and Vergne. In [START_REF] Berline | Local Euler-Maclaurin formula for polytopes[END_REF], Berline and Vergne show that for any integral polytope P the following exterior formula holds:

|P ∩ Λ| = F : a face of P vol(F )α(F, P ) (1)
where the volume is normalized and α(F, P ) is a rational number which only depends on the tangent cone of F at P . One immediate consequence of this formula is that if α(F, P ) is positive for each face F of P, then Ehrhart positivity follows. (See Theorem 3.8 and Lemma 3.9.) At present, the explicit computation of α(F, P ) is a recursive, complicated process, but we carry it out in the special example of regular permutohedra of small dimensions, whose symmetry simplifies the computations. Based on our empirical results, we conjecture the following:

Conjecture 1.3 For any face F of the regular permutohedron Π n , we have α(F, Π n ) > 0.

Then our main theorem is that the Ehrhart positivity of all generalized permutohedra follows from the positivity of all the α's arising from the regular permutohedra. The approach we will take to prove Theorem 1.4 is to use perturbation techniques, as in [START_REF] Liu | Perturbation of transportation polytopes[END_REF], to show that every generalized permutohedron can be slightly perturbed (in the sense of Definition 4.1) to get a generic generalized permutohedron (see Remark 2.10). More importantly, we show that these α values simply accumulate through perturbation; that is, each α for a generalized permutohedron is the sum of several α's for the regular permutohedron.

Since Π n is a much smaller family of polytopes than generalized permutohedra, and has a lot of symmetry, we are able to carry out direct computation to find values of α(F, Π n ). (See Section 5 for some details.) We've verified that all α(F, Π n ) are positive for n up to 7. (Note that the dimension of Π n is n -1.) Hence, the following result follows from Theorem 1.4.

Theorem 1.5 All the generalized permutohedra of dimension at most 6 are Ehrhart positive. Hence, all the matroid polytopes of dimension at most 6 are Ehrhart positive.

Finally, in order to obtain the desired perturbation, we use a precise description of generalized permutohedra.

Definition 1.6 Define the supermodular cone C n to be the set of all vectors z ∈ V n , the vector space with basis indexed by subsets of [n], such that

z I + z J ≤ z I∩J + z I∪J for all I, J, intersected with z ∅ = 0. This cone is 2 n -1 dimensional.
Theorem 1.7 The polytope

P z = x ∈ R n : n i=1 x i = z [n] , i∈I x i ≥ z I , ∀I ⊂ [n] is a generalized permutohedron if and only if z ∈ C n
The above theorem is known. It was stated in [START_REF] Morton | Convex rank tests and semigraphoids[END_REF] without proof and has been used implicitly since then. For example in [1], it is used to prove that matroid polytopes are indeed generalized permutohedra. Since it gives a very conceptual way to prove our important Proposition 4.4, and since we haven't found a proof in the literature, we include it here.

Generalized Permutohedra

Definition 2.1 A polyhedron P is the set of solutions of a system of inequalities Ax ≥ b in R n for some m × n matrix A and b ∈ R m . A polytope is a bounded polyhedron.

We will be studying a family of polytopes with a very special inequality description. First we present one of them as a convex hull of a finite number of points.

Definition 2.2 Given a point (x 1 , x 2 , • • • , x n ) ∈ R n , we construct the usual permutohedron P (x 1 , x 2 , • • • , x n ) := conv (x ω(1) , x ω(2) , • • • , x ω(n) ) : ω ∈ S n
For all tuples of distinct x 1 , x 2 , • • • , x n , the usual permutohedra will be similar in a sense that we now make precise. Definition 2.3 Given a polytope P ⊆ R n and any face F ⊆ P we define its normal cone as

N P (F ) := {w ∈ R n : w, a ≥ w, b a ∈ F, b ∈ P }
and the normal fan N (P ) is the collection of all normal cones over all its faces.

Definition 2.4

The Braid Arrangement is the complete fan in R n /(1, 1, • • • , 1) given by the hyperplanes

x i -x j = 0 for all i = j.

As long as x 1 , x 2 , • • • , x n are distinct numbers, the resulting permutohedron have the braid arrangement as its normal fan. We focus on Π n := P (1, 2, • • • , n), called the regular permutohedron. Its inequality description is given by the following theorem [START_REF] Rado | An inequality[END_REF].

Theorem 2.5 The inequality description of the regular permutohedron is given by:

Π n = t ∈ R n : i∈[n] t i = n(n + 1) 2 , i∈S t i ≥ |S| + 1 2 ∀S ⊆ [n] , S = ∅, [n]
Moreover, all those 2 n -2 inequalities define the facets.

For the rest of the paper we use the following notation:

Definition 2.6 Let M n be the 2 n × n matrix in which each row corresponds to the indicator vector of all subsets of [n]. Let V n be the vector space with basis indexed by subsets of [n].

With these definitions we can rewrite the previous theorem as

Π n = {x ∈ R n : M n x ≥ b} where b ∈ V n given by b S = |S|+1 2
, but for the rows [n] and ∅ we have equality. Now we come to the definition of the family of polytopes we study in this paper.We use the following definition which is equivalent to the original definition stated in [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF] by a simple transformation on S n : Definition 2.7 A generalized permutohedron is a polytope obtained from a usual permutohedron P (x 1 , • • • , x n ) by moving the vertices while keeping the direction of all the edges. In other words, a generalized permutohedron is the convex hull of n! points v ω ∈ R n labeled by permutations ω ∈ S n such that, for any ω ∈ S n and any adjacent transposition s i = (i, i + 1), we have,

v ω -v ωsi = k ω,i (e ω(i+1) -e ω(i) ), (2)
for some nonnegative number k ω,i ∈ R ≥0 , where e 1 , • • • , e n are the coordinate vectors in R.

In [START_REF] Postnikov | Faces of generalized permutohedra[END_REF], Postnikov, Reiner, and Williams give some equivalent definitions, among them the following: Proposition 2.8 A polytope P in R n is a generalized permutohedron if and only if its normal fan is refined by the braid arrangement fan.

Since we are moving the facets while keeping the normal vectors, we are simply changing the vector b, and hence every generalized permutohedron is the set of solutions to a systems of inequalities of the form M n x ≥ z for some vector z ∈ V n . We assume all inequalities are tight (but not necessarily facet defining). Under this assumption every generalized permutohedron corresponds to a unique vector z. Note that this forces z ∅ = 0.

However, not all vectors give a generalized permutohedron; it is possible to create unwanted edges. For our perturbation method we need to know a characterization of vectors that do give a generalized permutohedron. That is precisely the content of Theorem 1.7. For the completeness of the paper, we include a proof of the theorem. Proof of Theorem 1.7: Only if: We begin with the only if part. Suppose we have z I + z J > z I∩J + z I∪J for some I, J. Then for any feasible t,

z I∩J + z I∪J < z I + z J ≤ i∈I t i + j∈J t j = i∈I∩J t i + j∈I∪J t j
which means that for any point t only one of the inequalities corresponding to I ∩ J and I ∪ J can be attained. Since all the inequalities are attained at some point, the above means that no point maximizes both of them at the same time. We now show this is not possible. The two facets defined by the equations i∈I∩J t i = z I∩J and j∈I∪J t j = z I∪J meet in an ridge. In the braid arrangement the two corresponding edges span a two dimensional cone F of the fan. By Proposition 2.8, the normal fan of P z is a coarsening of the braid arrangement, which means that each of its cones are unions of cones of the braid arrangement. The cone containing F will correspond to a face which maximizes both e I∩J and e I∪J , contradicting the first paragraph. If: we assume all the inequalities z I + z J ≤ z I∩J + z I∪J . Note that for any permutation ω ∈ S n the intersection of the following n supporting hyperplanes

i∈[ω(k)] x i = z [ω(k)] for all k ∈ {1, 2, • • • , n} where [ω(i)] := {ω(1), ω(2), • • • , ω(i)} has unique solution v ω ∈ R n with (v ω ) ω(i) = z [ω(i)] -z [ω(i-1)] . (3)
In order to check they are all vertices, it is enough to verify that they satisfy all inequalities. We show it by induction on |I|. Without loss of generality we assume that ω = id:

1. If |I| = 1 then we need to check that v i = z [i] -z [(i-1)] ≥ z {i} or equivalently z [i] ≥ z {i} + z [(i-1)]
which is true by the supermodular inequality.

If

I = {i 1 , i 2 , • • • , i k } with i 1 < i 2 < • • • < i k , we need to show v i1 + v i2 + • • • + v i k-1 + v i k ≥ z I
By induction we can bound the first k -1 terms by z I-i k , and, since

v i k = z [i k ] -z [i k -1] ,
we are done if we can show

z I-i k + z [i k ] -z [i k -1] ≥ z I
Which is a direct application to the supermodular inequality to the sets I and

[i k -1].
Now we need to verify that there are no other vertices. For this we use the greedy algorithm for polymatroids which says that for any linear functional c if we want to solve

maximize c • x subject to i∈I x i ≥ z I ∀I ⊂ [n] i∈[n] x i = z [n]
x i ∈ R

We can find an optimal x * in the following way. Fix a permutation ω of

[n] such that c ω(1) ≤ c ω(2) ≤ • • • ≤ c ω(n) and then define x * ω(i) = z [ω(i)] -z [ω(i-1)]
as before. For a proof using weak duality see [START_REF] Schrijver | Combinatorial optimization. Polyhedra and efficiency[END_REF], chapter 44, page 771. This shows that all vertices are the ones we already found above.

To finish, according to Definition 2.7, we need to show that vertices v ω defined by ( 3) satisfies (2) with k ω,i ≥ 0. However, by direct calculation, we get

k ω,i = z [ω(i+1)] + z [ω(i-1)] -z [ω(i-1)]∪ω(i+1) -z ω(i) ≥ 0,
where the inequality follows from supermodularity. 2 Definition 2.9 For any z in the interior of the super modular cone C n , we call the corresponding generalized permutohedron generic.

Remark 2.10 By definition, in a generic generalized permutohedron all the 2 n -2 inequalities defining it are facets. It follows that the generic generalized permutohedra are precisely the ones having the braid arrangement as their normal fan.

Exterior Formula

In 1975 Danilov, based on algebraic evidence, asked if it is possible to assign values to cones such that the following exterior formula holds

|P ∩ Λ| = F :a face of P Vol (F )α(F, P ) (4)
where Λ is a lattice, and the volume is normalized and α(F, P ) depends only on the tangent cone of F in P .

McMullen [START_REF] Mcmullen | Valuations and dissections[END_REF] proved it was possible in a non constructive way. Berline and Vergne [START_REF] Berline | Local Euler-Maclaurin formula for polytopes[END_REF] were able to construct such α in a computable way. Before giving more details of Berline-Vergne's construction, we introduce some relevant definitions and results.

We assume the readers are familiar with the definition of algebra of polyhedra/polytopes and valuation presented in [START_REF] Barvinok | Integer points in polyhedra[END_REF]. Definition 3.1 Suppose P is a polyhedron and F is a face. The tangent cone of F at P is: tcone(F, P ) = {F + u : F + δu ∈ P for sufficiently small δ} The feasible cone of F at P is: fcone(F, P ) = {u : F + δu ∈ P for sufficiently small δ} In order to always work with pointed cones, we also define tcone p (F, P ) = tcone(F, P )/L and fcone p (F, P ) = fcone(F, P )/L where L is the subspace spanned by F . Then tcone p (F, P ) and fcone p (F, P ) are pointed cones with dimension dim P -dim F .

Given a polyhedron P ⊆ R n we define the indicator function [P ] : R n → R as:

[P ](x) = 1 if x ∈ P and zero otherwise.

Below is an important result on feasible cones. We have an immediate corollary to Property (P2), together with the fact that Ψ is a valuation:

Corollary 3.3 Suppose K 1 , K 2 , . . . , K k and K are cones satisfying [K] ≡ k i=1 [K i ] modulo polyhedra with lines. Then Ψ ([K]) = k i=1 Ψ ([K i ]) .
When the cone K is unimodular, computations are greatly simplified. In small dimensions we can even give a simple closed expression for α of unimodular cones. Here co

(v 1 , • • • , v k ) denotes the cone spanned by the vectors v 1 , • • • , v k . Lemma 3.4 If K = co(u 1 , u 2 )
where u 1 , u 2 are a basis for the lattice Λ then Recall the definition of α(F, P ) in ( 5), we have the following lemma: Proof: The first equality follows from applying the valuation Ψ to the identity in Theorem 3.2, Corollary 3.3, and noticing that in a lattice polytope a tangent cone is a lattice translation of the corresponding feasible cone. The second equality follows from Property (P4). The third equality follows from an analysis of the formula given in Lemma 3.4, which we omit. 2

Ψ(K) = 1 4 + 1 12
u 1 , u 2 u 1 , u 1 + u 1 ,

Applications

One application of the exterior formula (4) is that it provides another way to prove Ehrhart's theorem. Moreover, it gives a description of each Ehrhart coefficient. We state the following modified version of Theorem 1.1.

Theorem 1 . 4

 14 Conjecture 1.3 implies conjecture 1.2.

Theorem 3 . 2 ( 1 (

 321 Theorem 6.6 of[START_REF] Barvinok | Integer points in polyhedra[END_REF]) Suppose P is a nonempty polytope. Then [0] ≡ v: a vertex of P fcone(v, P ) modulo polyhedra with lines 3.1 Berline-Vergne's construction Berline and Vergne constructed in [3] a valuation Ψ on rational cones and show it has the following properties (P1) The exterior formula (4) holds if we set α(F, P ) := Ψ(tcone p (F, P )). (5) (P2) If a cone C contains a line, then Ψ(C) = 0. (P3) Ψ is invariant under lattice translation, i.e., Ψ(C) = Ψ(C + p) for any lattice point p. (P4) Its value on a lattice point is 1, i.e. Ψ([0]) = P5) It can be computed in polynomial time fixing the dimension.

Lemma 3 . 7

 37 Suppose P is a nonempty lattice polytope. Then v: a vertex of P α(v, P ) = 1; α(P, P ) = 1; α(F, P ) = 1/2, for any facet F of P .

Theorem 3 . 8

 38 For a lattice polytope P ,L P (n) = |nP ∩ Λ| is a polynomial in n of degree dim P. Furthermore, the coefficient of n k in L P (n) is F :dim(F )=kα(F, P )Vol (F ).

  u 2 u 2 , u 2 Lemma 3.5 If K = co(u 1 , u 2 , u 3 ) where u 1 , u 2 , u 3 are a basis for the lattice Λ then Remark 3.6 The apparent simplicity breaks down for dimension 4.

	Ψ(K) =	1 8	+	1 24	u 1 , u 2 u 1 , u 1	+	u 1 , u 2 u 2 , u 2	+	u 1 , u 3 u 1 , u 1	+	u 1 , u 3 u 3 , u 3	+	u 3 , u 2 u 2 , u 2	+	u 3 , u 2 u 3 , u 3

Acknowledgements

The authors thank Federico Ardila for discussions about generalized permutohedra, specially about Theorem 1.7. We also thank Michele Vergne for providing a code used in some of the computations.

† Fu Liu is partially supported by NSF grant DMS-1265702.

1365-8050

Proof: When we dilate the polytope by a factor of n, each face F of P becomes nF, a face of nP. It is clear that the tangent/feasible cone does not change. Hence, applying the exterior formula to nP, we get

Then our conclusion follows.

2

The formula [START_REF] Liu | Perturbation of transportation polytopes[END_REF] for the coefficients of the Ehrhart polynomial L P (n) gives a sufficient condition for Ehrhart positivity. It is our first step to reduce conjecture 1.2 to conjecture 1.3. Lemma 3.9 Let P be a lattice polytope. If for every face F of P , we have α(F, P ) > 0, then P is Ehrhart positive.

In the next section, we will apply the idea of perturbation to generalized permutohedra to finish the second step of reduction, and complete the proof for Theorem 1.4.

Perturbation of generalized permutohedra

We start with definitions and results on perturbation methods that will be used. We say b(t) provides a perturbation for P if for each t = 0 in the interval, b(t) defines a nonempty polyhedron P (t) = {x : Ax ≤ b(t)} with exactly l vertices: w t,1 , • • • , w t,l and the feasible cone of P (t) at w t,j does not depend on t, that is, for each j : 1 ≤ j ≤ l, there exists a fixed cone K j such that fcone(P (t), w t,j ) = K j for all t = 0. (Note that this is equivalent to say that all P (t) with t = 0 have the same normal fan.)

The following is a result in [START_REF] Liu | Perturbation of transportation polytopes[END_REF].

Theorem 4.2 Suppose b(t) provides a perturbation for the nonempty polyhedron P and assume the setup is the same as in Definition 4.1. Then we have the following:

• For each fixed j : 1 ≤ j ≤ l, the set of vertices {w t,j } converges to some vertex of P as t goes to 0.

• For each vertex v ∈ Vert(P ), let J v be the set of j's where {w t,j } converges to v. Then

with lines

The above theorem only deals with vertices and vertex cones. We will generalize it to all faces. We need a preliminary definition and observation: Assume the same setup as in Definition 4.1. We say a set J ⊆ {1, 2, . . . , l} defines a face of P (t) if conv(w t,j | j ∈ J) is a face of P (t). We observe that a set J defines a face of P (t 0 ) for some t 0 if and only if J defines a face of P (t) for all t. Therefore, when we say J defines a face of P (t), we mean it is true for all t in the interval. Theorem 4.3 Suppose b(t) provides a perturbation for the nonempty polyhedron P and assume the setup is the same as in Definition 4.1. Then we have the following:

• For each set J that defines a face F (t) of P (t), F = conv {lim t→0 w t,j | j ∈ J} is a face of P. In this case, we say F (t) converges to F.

• For each F of P , let F 1 (t), F 2 (t), . . . , F k (t) be all the faces of P (t) of dimension dim F that converge to F. Then

[fcone p (F i (t), P (t))] modulo polyhedra with lines

When we restrict faces to be 0-dimensional in Theorem 4.3, we recover Theorem 4.2. The idea of the proof for Theorem 4.3 is to reduce the higher-dimensional faces to vertices, and then apply Theorem 4.2. We omit the proof from this extended abstract.

We will apply Theorem 4.3 to generalized permutohedra. First, for any generalized permutohedron P z given by M n x ≥ z, we would like to perturb it to obtain a generic generalized permutohedron. For this we appeal to Theorem 1.7.

Proposition 4.4 Let z ∈ K C be any vector in the supermodular cone. There exists a continous function z(t) such that

is generic for t > 0 and P z(0) = P z .

Proof: Recall that by Remark 2.10 being generic is the same as being an interior point of C n . By convexity, the line segment connecting z with any interior point is contained in the cone K C . Furthermore every point in the segment, except for z, is an interior point, hence the conclusion. 2 for some set of faces F i (t) of P z(t) . However, by the construction of z(t), P z(t) is a generic generalized permutohedron, which has the same normal fan as Π n . Then the conclusion follows. 2

We can finally present the proof of Theorem 1.4. Proof of Theorem 1.4; By Lemma 3.9, in order to show a generalized permutohedra P is Ehrhart positive, it is enough to show α(F, P ) is positive for each face F of P. However, by Corollary 4.5, the positivity of α's for P follows from the positivity of α's for Π n . 2

Regular Permutohedron

In this section we show how to compute the α for all faces of the regular permutohedron. There are two facts that will make this computations much easier than the general case:

. We will go through each face of this cone:

• The vertex itself. Its α value is equal to 1/24, because by symmetry all vertices have the same value and they add up to 1 by Lemma 3.7.

• Edges. There are two types let's do the edge in direction (1, -1, 0, 0) (the edge (0, 0, 1, -1) gives the same value), which in the picture corresponds to an edge in a square. First we need to compute its pointed tangent cone. Since A 3 is unimodular, this can be seen computed as the cone generated by (0, 1, -1, 0), (0, 0, 1, -1) in R 4 / (1, -1, 0, 0), (

. Their images are (1/2, 1/2, -1, 0), (0, 0, 1, -1), and the cone they generate is unimodular in the lattice

. We are in position to apply lemma 3.4 and obtain a value of 11/72. The edge (0, 1, -1, 0) is different, this correspond to an edge contained in two hexagons. In this case the value is 14/72.

• Facets. They always have a value of 1/2.

• The whole cone. Its value is always 1.

Applying the exterior formula

we get the left hand side equal to:

The terms correspond to the contribution of vertices, square edges, hexagonal edges, square faces, hexagonal faces (note they have normalized volume 3), and finally the whole polytope. This information gives the Ehrhart polynomial 1 + 6n + 15n 2 + 16n 3

The above computations have been carried out up to Π 7 , verifying Conjecture 1.3 up to dimension six. We don't have a conjecture for the exact values, but in the computations, all faces of codimension k have values close to 1/k!. In the example above note that the edges corresponds to faces of codimension 2 of A 3 , and their values 11/72 and 14/72 are close to 1/3! = 1/6 = 12/72.


Yi Sun
email: yisun@math.mit.edu.

A representation-theoretic proof of the branching rule for Macdonald polynomials

Keywords: Macdonald polynomials, quantum groups, Gelfand-Tsetlin basis, double affine Hecke algebras

We give a new representation-theoretic proof of the branching rule for Macdonald polynomials using the Etingof-Kirillov Jr. expression for Macdonald polynomials as traces of intertwiners of Uq(gl n ). In the Gelfand-Tsetlin basis, we show that diagonal matrix elements of such intertwiners are given by application of Macdonald's operators to a simple kernel. An essential ingredient in the proof is a map between spherical parts of double affine Hecke algebras of different ranks based upon the Dunkl-Kasatani conjecture.

Résumé. Nous donnons une nouvelle preuve représentation-théorique de la règle de branchement pour les polynômes de Macdonald en utilisant l'expression Etingof-Kirillov Jr. pour les polynômes de Macdonald comme des traces de intertwiners de Uq(gl n ). Dans la base de Gelfand-Tsetlin, nous montrons que les éléments de matrice diagonaux de ces intertwiners sont donnés par action des opérateurs de Macdonald à un noyau simple. Un ingrédient essentiel dans la preuve est une application entre les parties sphériques des algèbres de Hecke double affines de rangs différents basés sur la conjecture Dunkl-Kasatani.

Introduction

The Macdonald polynomials P λ (x; q, t) are a two-parameter family of symmetric polynomials indexed by partitions λ which form an orthogonal basis for the ring of symmetric functions with respect to a (q, t)deformation of the standard inner product. They were originally introduced by Macdonald (see [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF]) as a generalization of many known families of special functions, including Schur functions, Jack and Hall-Littlewood polynomials, and Heckman-Opdam hypergeometric functions. Macdonald proved a branching rule for the P λ (x; q, t) and conjectured three additional symmetry, evaluation, and norm identities collectively known as Macdonald's conjectures. These conjectures were proven by Cherednik using techniques from double affine Hecke algebras. Etingof and Kirillov Jr. realized the Macdonald polynomials in [START_REF] Etingof | Macdonald's polynomials and representations of quantum groups[END_REF] in terms of traces of intertwiners of the quantum group U q (gl n ); using this interpretation, they gave new proofs of Macdonald's conjectures in [START_REF] Etingof | Representation-theoretic proof of the inner product and symmetry identities for Macdonald's polynomials[END_REF].

The purpose of this work is to give a representation-theoretic proof and interpretation of Macdonald's branching rule from the perspective of quantum groups. We give a new expression for diagonal matrix Yi Sun elements of U q (gl n )-intertwiners in the Gelfand-Tsetlin basis as the application of Macdonald's difference operators to a simple kernel. We then show that the resulting summation expression for P λ (x; q, t) becomes Macdonald's branching rule after a summation by parts procedure. A key ingredient is the construction of a map Res l (q 2 ) between spherical parts of double affine Hecke algebras of different ranks. Our construction makes use of the Dunkl-Kasatani conjecture and is compatible with Cherednik's SL 2 (Z)action on spherical DAHA.

In the remainder of this extended abstract, we state our results on matrix elements of quantum group intertwiners and maps between spherical double affine Hecke algebras and then explain in more detail how they may be used to give a new proof of Macdonald's branching rule. Full details, background, and a complete list of references can be found in [START_REF] Sun | A representation-theoretic proof of the branching rule for Macdonald polynomials[END_REF].

Macdonald polynomials

Let ρ = n-1 2 , . . . , 1-n 2
and let e r denote the elementary symmetric polynomial. For a partition λ, the Macdonald polynomial P λ (x; q 2 , t 2 ) is the joint polynomial eigenfunction with leading term x λ and eigenvalue e r (q 2λ t 2ρ ) of the operators

D r n,x (q 2 , t 2 ) = t r(r-n) |I|=r i∈I,j / ∈I t 2 x i -x j x i -x j T q 2 ,I ,
where T q 2 ,I = i∈I T q 2 ,i and

T q 2 ,i f (x 1 , . . . , x n ) = f (x 1 , . . . , q 2 x i , . . . , x n ). An integral signature λ is a sequence λ = (λ 1 ≥ • • • ≥ λ n ) with λ i -λ j ∈ Z.
We extend the definition of Macdonald polynomials to arbitrary signatures by setting P (λ1+c,...,λn+c) (x;

q 2 , t 2 ) = (x 1 • • • x n ) c P λ (x; q 2 , t 2 ). Say that integral signatures µ = (µ 1 ≥ • • • ≥ µ n-1 ) and λ = (λ 1 ≥ • • • ≥ λ n ) interlace if λ 1 ≥ µ 1 ≥ λ 2 ≥ • • • ≥ µ n-1 ≥ λ n . Denote interlacing by µ ≺ λ and write |λ| = i λ i . A Gelfand-Tsetlin pattern subordinate to λ is an interlacing sequence µ = {µ l } 1≤l≤n = {µ 1 ≺ µ 2 ≺ • • • ≺ µ n-1 ≺ µ n =
λ} ending in λ. Define the q-Pochhammer symbol by (u; q) = n≥0 (1 -uq n ). In [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF], Macdonald showed that P λ (x) satisfies the following branching rule, which yields an explicit summation expression for P λ (x) over Gelfand-Tsetlin patterns subordinate to λ.

Theorem 1.1 ([Mac95, VI.7.13']). The Macdonald polynomials satisfy the branching rule

P λ (x 1 , . . . , x n ) = µ≺λ ψ λ/µ (q, t)P µ (x 1 , . . . , x n-1 )x |λ|-|µ| n ,
where the branching coefficient is

ψ λ/µ (q, t) = 1≤i≤j≤ (µ)
(q µi-µj t j-i+1 ; q)(q λi-λj+1 t j-i+1 ; q)(q λi-µj +1 t j-i ; q)(q µi-λj+1+1 t j-i ; q) (q µi-µj +1 t j-i ; q)(q λi-λj+1+1 t j-i ; q)(q λi-µj t j-i+1 ; q)(q µi-λj+1 t j-i+1 ; q) .

Corollary 1.2. The Macdonald polynomials admit the summation formula

P λ (x, q, t) = µ 1 ≺•••≺µ n-1 ≺µ n =λ n i=1 ψ µ i /µ i-1 (q, t) n i=1 x |µ i |-|µ i-1 | i .
1.2 The quantum group U q (gl n )

Let U q (gl n ) be the finite type quantum group with generators e i , f i for i = 1, . . . , n -1 and q h i 2 for i = 1, . . . , n and relations

[h i , h j ] = 0, [h i , e i ] = e i , [h i , f i ] = -f i , [h i , e i+1 ] = -e i+1 , [h i , f i+1 ] = f i+1 , [h i , e j ] = [h i , f j ] = 0 for j = i, i + 1, [e i , f j ] = δ ij q hi-hi+1 -q hi+1-hi q -q -1 , [e i , e j ] = [f i , f j ] = 0 for |i -j| > 1
e 2 i e j -(q + q -1 )e i e j e i + e j e 2 i = 0,

f 2 i f j -(q + q -1 )f i f j f i + f j f 2 i = 0 for |i -j| = 1.
We take the coproduct on U q (gl n ) defined by ∆(e i ) = e i ⊗ q

h i+1 -h i 2 + q h i -h i+1 2 ⊗ e i , ∆(f i ) = f i ⊗ q h i+1 -h i 2 + q h i -h i+1 2 ⊗ f i , and ∆(h i ) = h i ⊗ 1 + 1 ⊗ h i .
Denote the subalgebra generated by f i and q hi/2 by U q (b -). For each r < n, embed U q (gl r ) inside U q (gl n ) as the subalgebra generated by e 1 , . . . , e r-1 , f 1 , . . . , f r-1 , and q h1/2 , . . . , q hr/2 . Finally, denote the finite dimensional irreducible U q (gl n )-representation corresponding to an integral signature λ by L λ .

Etingof-Kirillov Jr. approach to Macdonald polynomials

In [START_REF] Etingof | Macdonald's polynomials and representations of quantum groups[END_REF], Etingof and Kirillov Jr. realized Macdonald polynomials via traces of U q (gl n )-intertwiners.

Let W k-1 denote the representation L ((k-1)(n-1),-(k-1),...,-(k-1)) = Sym (k-1)n (C n ) ⊗ (det) -(k-1) , and choose an isomorphism W k-1 [0] C • w k-1 for some w k-1 ∈ W k-1 [0] which spans the 1- dimensional zero weight space W k-1 [0]. Define the weight ρ n = n-1 2 , . . . , 1-n 2
. Writing ρ for ρ n , for a signature λ there exists a unique intertwiner Φ n λ : L λ+(k-1)ρ → L λ+(k-1)ρ ⊗ W k-1 normalized to send the highest weight vector v λ+(k-1)ρ in L λ+(k-1)ρ to v λ+(k-1)ρ ⊗ w k-1 + (lower order terms), where (lower order terms) denotes terms of weight lower than λ + (k -1)ρ in the first tensor coordinate. Traces of these intertwiners lie in W k-1 [0] = C•w k-1 and yield Macdonald polynomials when interpreted as scalar functions via the identification w k-1 → 1.

Theorem 1.3 ([EK94, Theorem 1]). The Macdonald polynomial is given by P λ (x; q 2 , q 2k ) =

Tr(Φ n λ x h ) Tr(Φ n 0 x h ) .
Proposition 1.4 ([EK94, Main Lemma]). On L (k-1)ρ , the trace may be expressed explicitly as

Tr(Φ n 0 x h ) = (x 1 • • • x n ) -(k-1)(n-1) 2 k-1 s=1 i<j (x i -q 2s x j ).
Remark. Our notation is related to that of [START_REF] Etingof | Macdonald's polynomials and representations of quantum groups[END_REF] via P EK λ (x; q, t) = P λ (x; q 2 , t 2 ).

Gelfand-Tsetlin basis

The representation L λ of U q (gl n ) admits a basis {v µ } indexed by Gelfand-Tsetlin patterns µ subordinate to λ. The weight of a basis vector v µ is wt

(v µ ) = |µ n | -|µ n-1 |, . . . , |µ 2 | -|µ 1 |, |µ 1 | . It was shown in [UTS90]
that these basis vectors may be expressed in terms of lowering operators d r,i in U q (gl r ) ∩ U q (b -) ⊂ U q (gl n ) applied to the highest weight vector v λ .

Proposition 1.5 ([UTS90, Theorem 2.9]). The Gelfand-Tsetlin basis vectors may be realized as

v µ = d µ 1 1 d µ 2 -µ 1 2 • • • d µ n -µ n-1 n v λ for d r,i ∈ U q (gl r ) ∩ U q (b -) and d τ r = d τ1 r,1 • • • d τr r,r
for a partition τ .

Statement of the main results

Our main result shows that diagonal matrix elements of the U q (gl n )-intertwiners of Theorem 1.3 are given by application of Macdonald's operators to a simple kernel.

Theorem 1.6. In the Gelfand-Tsetlin basis, the diagonal matrix element of Φ n λ on the basis vector corresponding to the Gelfand-Tsetlin pattern

{σ 1 ≺ • • • ≺ σ n-1 ≺ λ + (k -1)ρ} with σ l i = µ i + (k -1) n-i 2 is given by c(µ, λ) = k-1 a=1 D n-1,q 2 μ (q 2a ; q -2 , q 2(k-1) ) i≤j [λ i -µ j + k(j -i)] k-1 i<j [µ i -λ j + k(j -i) + k -2] k-1 i≤j [µ i -µ j + k(j -i) + k -1] k-1 i<j [λ i -λ j + k(j -i) -1] k-1
,

where μi = µ i -k(i -1), [m] = q m -q -m q-q -1 , [m] k = [m] • • • [m -k + 1],
and

D n-1,q 2 μ (u; q 2 , t 2 ) = n-1 r=0 (-1) n-1-r u n-1-r D r n-1,q 2 μ (q 2 , t 2 ).
Using Theorem 4.4, we give a new representation-theoretic proof of Macdonald's branching rule.

Theorem 1.7. At t = q k for positive integer k, we have

P λ (x 1 , . . . , x n ; q 2 , q 2k ) = µ≺λ x |λ|-|µ| n P µ (x 1 , . . . , x n-1 ; q 2 , q 2k )ψ λ/µ (q 2 , q 2k ) with ψ λ/µ (q 2 , q 2k ) = i≤j [λ i -µ j + k(j -i) + k -1] k-1 i<j [µ i -λ j + k(j -i) -1] k-1 i≤j [µ i -µ j + k(j -i) + k -1] k-1 i<j [λ i -λ j + k(j -i) -1] k-1 .
Remark. This formulation is equivalent to that of Theorem 1.1. To see this, note that for each λ and µ the branching coefficients ψ λ/µ (q, t) are rational functions in q and t and are therefore uniquely determined by their values at (q 2 , q 2k ) for all positive integers k.

Remark. Theorem 1.3 gives P λ (x; q 2 , q 2k ) as a summation over Gelfand-Tsetlin patterns subordinate to λ + (k -1)ρ and Macdonald's branching rule gives it as a summation over Gelfand-Tsetlin patterns subordinate to λ. Our result explains how these summations over different index sets are related.

Degenerations of our results and connections to recent work

We discuss now the Heckman-Opdam, Hall-Littlewood, and Jack limits of our results.

• In the quasi-classical limit q = e ε , t = q k , λ = ε -1 Λ , x = e εX , and ε → 0, the Macdonald polynomials become the Heckman-Opdam hypergeometric functions introduced in [HO87, Opd88]. These functions were realized as integrals over Gelfand-Tsetlin polytopes in [BG13] by a scaling limit of Corollary 1.2. In [START_REF] Sun | A new integral formula for Heckman-Opdam hypergeometric functions[END_REF], the expression of [START_REF] Borodin | General β Jacobi corners process and the Gaussian free field[END_REF] was lifted to an integral over dressing orbits of a Poisson-Lie group by integration over Liouville tori and adjunction for Calogero-Sutherland Hamiltonians. The techniques of this paper degenerate to the techniques of [START_REF] Sun | A new integral formula for Heckman-Opdam hypergeometric functions[END_REF].

• In the specialization q = 0, the Macdonald polynomials become the Hall-Littlewood polynomials.

In [START_REF] Venkateswaran | On the expansion of certain vector-valued characters of U q (gl n ) with respect to the Gelfand-Tsetlin basis[END_REF], a summation expression was given for matrix elements of the U q (gl n )-intertwiners Φ n λ in the Gelfand-Tsetlin basis; this expression factors in the Hall-Littlewood limit. It would be interesting to understand if it may be realized as a degeneration of Proposition 4.3 or Theorem 4.4.

• The Jack polynomials are a scaling limit of Macdonald polynomials under the specialization t = q k and the limit q → 1 and have a similar branching rule. They were given in [START_REF] Etingof | Quantum integrable systems and representations of Lie algebras[END_REF] as traces of intertwiners of U (gl n )-modules using a degeneration of the Etingof-Kirillov Jr. construction, and we expect our methods to degenerate to a representation-theoretic proof of the Jack branching rule.

2 Quantum groups and Macdonald polynomials

Notations

Set ρ n,i = n+1 2 -i and 1 = (1, . . . , 1). For any set of indices I, let 1 I denote the vector with 1's in those indices and 0's elsewhere. Define ρ n = ρ n -n-1 2 1 so that ρ n,i = -(i -1) and ρ n-1,i = ρ n,i . For any signature λ, define the shifts λ = λ + (k -1) ρ and λ = λ + k ρ. Denote by [a] = q a -q -a q-q -1 the q-number,

[a]! = [a] • [a -1] • • • [1] the q-factorial, and [a] m = [a] • [a -1] • • • [a -m + 1] the falling q-factorial.

Macdonald symmetry identity

We now produce Macdonald operators acting on indices. We abuse notation to write D r n-1,q 2 μ for difference operators acting on additive indices μ as well as multiplicative variables q 2μ . Proposition 2.1 (Macdonald symmetry identity). We have

P λ (q 2µ+2kρ ; q 2 , q 2k ) = i<j [λ i -λ j + k(j -i) + k -1] k [µ i -µ j + k(j -i) + k -1] k P µ (q 2λ+2kρ ; q 2 , q 2k ).
Proposition 2.2. The operator

D r n-1,q 2 μ (q 2 , q 2k ) = i<j [μ i -μj + k -1] k • D r n-1,q 2 μ (q 2 , q 2k ) • i<j [μ i -μj + k -1] -1 k satisfies D r n-1,q 2 μ (q 2 , q 2k ) = |I|=r i∈I,j / ∈I,i>j [μ i -μj + k][μ i -μj -k + 1] [μ i -μj ][μ i -μj + 1] T q 2 ,I
and D r n-1,q 2 μ (q 2 , q 2k )P µ (x; q 2 , q 2k ) = e r (x)P µ (x; q 2 , q 2k ).

Proof. The expression for D r n-1,q 2 μ (q 2 , q 2k ) follows by direct computation, and the eigenvalue identity from the Macdonald symmetry identity.

Yi Sun

Adjoints of Macdonald difference operators

We now consider adjoints of Macdonald operators with respect to a Jackson-type inner product. Fix lower and upper limits

ζ = (ζ -, ζ + ) with ζ -= (ζ - 1 , . . . , ζ - n-1 ), ζ + = (ζ + 1 , . . . , ζ + n-1 ), and ζ + i -ζ - i ∈ Z ≥0 . Define the inner product f, g ζ := ζ + µ=ζ -f (q 2µ )g(q 2µ
), with iterated summation defined by

ζ + µ=ζ - := ζ + 1 µ1=ζ - 1 • • • ζ + n-1 µn-1=ζ - n-1
.

(1)

We consider situations where g vanishes along a border of the region of summation. Say that the function

g(q 2µ ) is (ζ, l)-adapted if g(q 2µ ) = 0 on the set {µ | ζ + i < µ i ≤ ζ + i + l or ζ - i -l ≤ µ i < ζ - i for any i}. Proposition 2.3. If f (q 2µ ) is (ζ, l)-adapted, we have for any g that l i=1 D r l+1-i n-1,q 2 μ (q 2 , q 2k ) † f, g ζ -,ζ + +l1 = f, l i=1 D ri n-1,q 2 μ (q 2 , q 2k )g ζ , where D r n-1,q 2 μ (q 2 , q 2k ) † = i<j [μ i -μj + k -1] -1 k-1 • D r n-1,q 2 μ (q -2 , q 2(k-1) ) • i<j [μ i -μj + k -1] k-1 .
Proof. By a direct computation for l = 1 and induction on l.

Reformulating the Etingof-Kirillov Jr. construction

We shift the weights used in the Etingof-Kirillov Jr. construction to make restriction from U q (gl n ) to U q (gl n-1 ) more notationally convenient. For a partition λ, define the intertwiner Φ n λ :

L λ+(k-1) ρ → L λ+(k-1) ρ ⊗ W k-1 to be Φ n λ = Φ n λ ⊗ id (det) -(k-1)(n-1)

2

. We rephrase Theorem 1.3 in terms of Φ n λ .

Corollary 2.4. The Macdonald polynomial P λ (x; q 2 , q 2k ) is given by P λ (x; q 2 , q 2k ) =

Tr( Φ n λ x h ) Tr( Φ n 0 x h ) .
Corollary 2.5. The denominator in Corollary 2.4 is given by

Tr( Φ n 0 x h ) = (x 1 • • • x n ) -(k-1)(n-1) k-1 s=1 i<j (x i -q 2s x j ).
3 Spherical subalgebras of DAHAs of different ranks

Double affine Hecke algebras

Let H n (q, t) denote the double affine Hecke algebra (DAHA) of GL n defined by [START_REF] Cherednik | Double affine Hecke algebras[END_REF]. It is defined as the algebra generated by X ± 1 , . . . , X ± n , Y ± 1 , . . . , Y ± n , and T ± 1 , . . . , T ± n-1 subject to the relations

• (T i -t)(T i + t -1 ) = 0, T i T i+1 T i = T i+1 T i T i+1 , [T i , T j ] = 0 for |i -j| = 1; • T i X i T i = X i+1 , T -1 i Y i T -1 i = Y i+1 , and [T i , X j ] = [T i , Y j ] = 0 for |i -j| > 1; • [X i , X j ] = 0, [Y i , Y j ] = 0, Y 1 X 1 • • • X n = qX 1 • • • X n Y 1 , and X -1 1 Y 2 = Y 2 X -1 1 T -2 1 .
For a reduced decomposition

σ = s i1 • • • s i l , let T σ = T i1 • • • T i l . For e = (1-t 2 ) n
(t 2 ;t 2 )n σ∈Sn t (σ) T σ , the spherical DAHA is the subalgebra eH n (q, t)e.

Polynomial representation of DAHA and Macdonald operators

The DAHA H n (q, t) admits a faithful polynomial representation ρ on C[X ± 1 , . . . , X ± n ] given by

ρ(X i ) = X i ρ(T i ) = ts i + t -t -1 X i /X i+1 -1 (s i -1) ρ(Y i ) = ρ(T i ) • • • ρ(T n-1 )s n-1 • • • s 1 T q,X1 ρ(T -1 1 ) • • • ρ(T -1 i-1 ),
where s i exchanges X i and X i+1 and T q,X1 is the q-shift operator in X 1 . The action of elements of eH n (q, t)e on the symmetric part of the polynomial representation yields the Macdonald operators.

Proposition 3.1. When restricted to C[X ± 1 , . . . , X ± n ] Sn , the action of e • e r (Y 1 , . . . , Y n ) • e is via ρ(e • e r (Y 1 , . . . , Y n ) • e) = D r n,X (q 2 , t 2 ).
Remark. By faithfulness, we will refer interchangeably to elements of the DAHA and spherical DAHA and their images under the polynomial representation in what follows.

SL 2 (Z)-action on DAHA

Define the isomorphisms ε(q, t) : H n (q, t) → H n (q -1 , t -1 ) given by ε(q, t) :

X i → Y i , Y i → X i , T i → T -1 i , q → q -1 , t → t -1
and τ + (q, t) : H n (q, t) → H n (q, t) given by

τ + : X i → X i , T i → T i , Y 1 • • • Y r → q -r/2 X 1 • • • X r Y 1 • • • Y r .
Define also the composition τ -= ετ + ε.

Proposition 3.2 ([Che05]

). The map 1 1 0 1 → τ -and 1 0 1 1 → τ + defines an action of SL 2 (Z) on H n (q, t) which preserves eH n (q, t)e.

Multiwheel condition and the restriction map

Following [START_REF] Kasatani | Subrepresentations in the polynomial representation of the double affine Hecke algebra of type GL n at t k+1 q r-1 = 1[END_REF], we say that (X 0 1 , . . . , X l-1 n ) ∈ C nl satisfies the multiwheel condition if the indices may be permuted so that

X a i = X 0 i t a-1 for 1 ≤ i ≤ n and 0 ≤ a ≤ l -1. Define the ideal I nl (t) ⊂ C[(X a i ) ± ] by I nl (t) = {f | f (X) = 0 if X satisfy the multiwheel condition}.

Yi Sun

Proposition 3.3 ([Kas05, Theorem 6.3] and [ES09, Theorem 5.10]). The subspace

I nl (t) ⊂ C[(X a i ) ± ] is a H nl (q, t)-submodule and C[(X a i ) ± ]/I nl (t) is irreducible. Define the map Res l (t 2 ) : C[(X a i ) ± ] S nl → C[X ± i ] Sn by Res l (t 2 )(X a i ) = t 1-l+2a X i . The kernel of Res l (t 2 ) is I S nl nl (t 2
), so Res l (q 2 ) induces by Proposition 3.3 an action of eH nl (q -2l , q 2 )e on C[X ± i ] Sn , giving a map Res l (q 2 ) : eH nl (q -2l , q 2 )e → End(C[X ± i ] Sn ). We claim that this map factors through the polynomial representation via a map of algebras Res l (q 2 ) : eH nl (q -2l , q 2 )e → eH n (q -2 , q 2l )e.

Theorem 3.4. The map Res l (q 2 ) : eH nl (q -2l , q 2 )e → eH n (q -2 , q 2l )e defined by Res l (q 2 )(ep(X a i )e) = ep(q 1-l X 1 , . . . , q l-1 X 1 , . . . , q 1-l X n , . . . , q l-1 X n )e for p ∈ C[(X a i ) ± ] S nl , and

Res l (q 2 )(ep(Y a i )e) = ep(q 1-l Y 1 , . . . , q l-1 Y 1 , . . . , q 1-l Y n , . . . , q l-1 Y n )e
is well defined and satisfies (a) for any h ∈ eH nl (q -2l , q 2 )e, as operators on C[(X a i ) ± ] S nl we have

Res l (q 2 ) • h = Res l (h) • Res l (q 2 );
(b) as operators on eH nl (q -2l , q 2 )e, we have

Res l (q -2 ) • ε nl (q -2l , q 2 ) = ε n (q -2 , q 2l ) • Res l (q 2 );

(c) as operators on eH nl (q -2l , q 2 )e, we have

Res l (q 2 ) • τ + = τ + • Res l (q 2 ).
Corollary 3.5. The map Res l (q 2 ) commutes with the action of SL 2 (Z) on the spherical DAHA.

The assignment Res l (q 2 )((X a i ) 1/2 ) = q a-(l-1)/2 X 1/2 i extends Res l (q 2 ) to an operator C[(X a i ) ±1/2 ] S nl → C[X 1/2 i ] Sn . Identify elements of the spherical DAHA with difference operators on i,a (X a i )

1/2 •C[(X a i ) ± ] S nl ⊂ C[(X a i ) ±1/2
] S nl . They may not satisfy the spherical DAHA relations, but we still have the following. Corollary 3.6. For any h ∈ eH nl (q -2l , q 2 )e, we have Res l (q 2 ) • h = Res l (h) • Res l (q 2 ) as operators on

i,a (X a i ) 1/2 • C[(X a i ) ± ] S nl .
3.5 Computing Res l (q 2 ) on a specific operator Define the operator D n,X (u; q, t) = r (-1) n-r u n-r D r n,X (q, t).

(2)

Identify eH nl (q -2l , q 2 )e with its image under the polynomial representation; in this identification, we now compute the image of a specific operator under Res l .

Lemma 3.7. We have the relation Res l (q 2 )(D nl,X (q l+1 ; q -2l , q 2 )) = l a=1 D n,X (q 2a ; q -2 , q 2l ). Proof. Compute using the definition of Res l (q 2 ) and the fact that D nl,X (q l+1 ; q -2l , q 2 ) is the image of n i=1 l-1 a=0 (Y a i -q l+1 ) in the polynomial representation.

Yi Sun

Proposition 4.3. Let µ = µ + (k -1)1, and ν = ν + (k -1)1. Then c(µ, λ) is given by c(µ, λ) = (-1) (n-1)(k-1) q (n-1)k(k-1)

∆ k-1 2 (λ)∆ k-1 1 (µ) μ ν =μ -(k-1)1 (-1) |ν |-|μ | q k(|ν |-|μ |) i 1 [ν i -μ i + (k -1)]![μ i -ν i ]! i<j [μ i -μ j + k -1] 2k-1 i<j [ν i -ν j ] i<j [ν i -μ j + (k -1)] k [μ i -ν j ] k i≤j [ λi -ν j + (k -1)] k-1 i<j [ν i -λj -1] k-1 . Theorem 4.4. Let µ = µ + (k -1)1. The matrix element c(µ, λ) is given by c(µ, λ) = k-1 a=1 D n-1,q 2 μ (q 2a ; q -2 , q 2(k-1) )∆ k-1 (µ , λ) ∆ k-1 1 (µ)∆ k-1 2 (λ) ,
where D n-1,q 2 μ (q 2a ; q -2 , q 2(k-1) ) was defined in (2).

Proof. By Lemma 3.7, we have Res l (q 2 )D (n-1)l,q 2 μ (q l+1 ; q -2l , q 2 ) = l a=1 D n-1,q 2 μ (q 2a ; q -2 , q 2l ).

Compute its action on Res

l (q 2 ) l-1 a=0 i≤j [ λi -μa j + k/2] i<j [μ a i -λj -k/2] = i≤j [ λi -μj + k -1] k-1 i<j [μ i -λj -1] k-1
in two ways and compare with Proposition 4.3.

Proving Macdonald's branching rule

In this section, we prove the branching rule. We use Proposition 4.2 to express the trace in the Gelfand-Tsetlin basis as a sum of products. Inducting on n and using the expression of Theorem 4.4 for c(µ, λ), we obtain an expression related to the desired by the summation by parts procedure of Proposition 2.3.

of Theorem 1.7. We induct on n. The base case is trivial because P λ (x 1 ; q 2 , q 2k ) = x |λ| 1 . For the inductive step, by Lemma 4.1, it is enough to consider matrix elements for basis vectors v µ . By Proposition 4.2 and the inductive hypothesis, we thus have

Tr( Φ n λ x h ) = µ 1 <•••< µ n-1 < λ c(µ 0 , µ 1 ) • • • c(µ n-1 , λ) i x (| µ i |-| µ i-1 |) i = µ< λ c(µ, λ)x |λ|-|µ|-(k-1)(n-1) n µ 1 <•••< µ n-2 < µ c(µ 0 , µ 1 ) • • • c(µ n-2 , µ n-1 ) n-1 i=1 x | µ i |-| µ i-1 | i = µ< λ c(µ, λ)x |λ|-|µ|-(k-1)(n-1) n P µ (x; q 2 , q 2k )Tr( Φ n-1 0 x h ),
where x = (x 1 , . . . , x n-1 ). By Corollary 2.5, we have that

Tr( Φ n-1 0 x h ) Tr( Φ n 0 x h ) = (x 1 • • • x n-1 ) k-1 x (k-1)(n-1) n k-1 s=1 n-1 i=1 (x i -q 2s x n ) -1 .
We conclude that

Tr( Φ n λ x h ) Tr( Φ n 0 x h ) = (x 1 • • • x n-1 ) k-1 k-1 s=1 n-1 i=1 (x i -q 2s x n ) -1 µ< λ c(µ, λ)x |λ| n P µ (x/x n ; q 2 , q 2k ) = (x 1 • • • x n-1 ) k-1 k-1 s=1 n-1 i=1 (x i -q 2s x n ) -1 λ ↑ µ=λ ↓ -(k-1)1
c(µ, λ)x |λ| n P µ (x/x n ; q 2 , q 2k ) = x (k-1)(n-1)

n k-1 s=1 n-1 i=1 (x i -q 2s x n ) -1 λ ↑ +(k-1)1 µ =λ ↓ c(µ -(k -1)1, λ)
x |λ| n P µ (x/x n ; q 2 , q 2k ),

where λ ↓ = (λ 2 , . . . , λ n ) and λ ↑ = (λ 1 , . . . , λ n-1 ) are vectors of lower and upper indices for µ so that

µ≺λ = λ ↑
µ=λ ↓ in the notation of (1). Note that µ < λ if and only if λ i ≥ µ i ≥ λ i+1 -(k -1). By the expression for c(µ -(k -1)1, λ) given in Theorem 4.4, we obtain P λ (x; q 2 , q 2k ) = Tr( Φ n λ x h ) Tr( Φ n 0 x h ) = x (k-1)(n-1)

n k-1 s=1 n-1 i=1 (x i -q 2s x n ) -1 λ ↑ +(k-1)1 µ =λ ↓
x |λ| n P µ (x/x n ; q 2 , q 2k ) k-1 a=1 D n-1,q 2 μ (q 2a ; q -2 , q 2(k-1) ) i≤j [ λi -

μ j + k -1] k-1 i<j [μ i -λj -1] k-1 i≤j [μ i -μ j + k -1] k-1 i<j [ λi -λj -1] k-1
.

Define the operator D n-1,q 2 μ (q 2a ; q 2 , q 2k ) = r (-1) n-1-r q 2a(n-1-r) D r n-1,q 2 μ (q 2 , q 2k ), and note that it is diagonalized on P µ (x; q 2 , q 2k ) by Proposition 2.2. Notice now that the function

i≤j [ λi -μ j + k -1] k-1 i<j [μ i -λj -1] k-1
is 0 for λ i+1 -(k -1) ≤ µ i < λ i+1 and λ i < µ i ≤ λ i + (k -1), so it is (λ ↓ , λ ↑ , k -1)-adapted. Applying Proposition 2.3 to this function yields the desired P λ (x; q 2 , q 2k ) = x (k-1)(n-1)

n k-1 s=1 n-1 i=1 (x i -q 2s x n ) -1 λ ↑ µ =λ ↓ x |λ| n k-1 a=1
D n-1,q 2 μ (q 2a ; q 2 , q 2k )P µ (x/x n ; q 2 , q 2k ) i≥j [ λj -

μ i + k -1] k-1 i<j [μ i -λj -1] k-1 i≤j [μ i -μ j + k -1] k-1 i<j [ λi -λj -1] k-1 = x (k-1)(n-1) n k-1 s=1 n-1 i=1 x i /x n -q 2s x i -q 2s x n λ ↑ µ =λ ↓ x |λ|-|µ | n P µ (x; q 2 , q 2k ) i≥j [ λj -μ i + k -1] k-1 i<j [μ i -λj -1] k-1 i≤j [μ i -μ j + k -1] k-1 i<j [ λi -λj -1] k-1 = µ ≺λ x |λ|-|µ | n P µ (x; q 2 , q 2k ) i≥j [ λj -μ i + k -1] k-1 i<j [μ i -λj -1] k-1 i≤j [μ i -μ j + k -1] k-1 i<j [ λi -λj -1] k-1
.

Acknowledgements

The author thanks P. Etingof for helpful discussions.

Supported by a NSF graduate research fellowship (NSF Grant #1122374).

1365-8050

4 Diagonal matrix elements in the Gelfand-Tsetlin basis

Factorization of matrix elements

For µ 1 , . . . , µ n = λ so that µ i ≺ • • • ≺ µ n = λ forms a Gelfand-Tsetlin pattern subordinate to λ, denote the pattern by µ. Let c( µ, λ) be the diagonal matrix coefficient of v µ in Φ λ . For µ ≺ λ, define gt(µ) by gt(µ) l i = µ i for l < n. Define c(µ, λ) to be the diagonal matrix coefficient c(gt( µ), λ) of v gt( µ) in Φ λ . We show that Φ λ has non-zero diagonal matrix elements only on basis vectors indexed by patterns of the form µ and that these elements admit a level-by-level factorization.

Lemma 4.1. If v µ is not of the form v µ , v µ has zero diagonal matrix element in Φ λ .

Proof. For some r < n, we cannot write µ r = τ for any τ . Let U ⊂ W k-1 be the U q (gl r )-submodule of vectors of weight 0 for q hr+1 , . . . , q hn so that U L (k-1)(r-1,-1,...-1) as a U q (gl r )-module. Let µ r denote the truncation of µ r so that µ r i = µ r i . Consider the pattern ξ given by ξ

be the U q (gl r )-submodule with highest weight µ r generated by v ξ . By Proposition 1.5, the diagonal matrix element of v µ lies in L µ r ⊗ U , hence is a multiple of the matrix element of v µ in the induced U q (gl r )-intertwiner

. By Proposition 1.5, the basis vector v µ lies in the U q (gl n-1 ) submodule L µ ⊂ L λ with highest weight vector v gt( µ) . Let U ⊂ W k-1 be the U q (gl n-1 )-submodule consisting of elements of weight 0 under q hn . Consider the U q (gl n-1 )-intertwiner φ : L µ → L µ ⊗ U given by composing Φ λ with the projection onto L µ ⊗ U . The matrix element c( µ, λ) lies in U , hence is the matrix element of v µ in φ. Notice that φ maps the U q (gl n-1 )-highest weight vector v gt( µ) to c(µ, λ)v gt( µ) ⊗ w k-1 + (l.o.t.) so that φ = c(µ, λ) Φ µ and the matrix element of v µ is the desired c(µ, λ)c

Matrix elements as applications of Macdonald difference operators

Our main technical result expresses matrix elements of U q (gl n )-intertwiners as the application of Macdonald difference operators on an explicit kernel. Define the elements ∆

and the element ∆ k-1 (µ, λ) by

We compute the diagonal matrix elements of Φ λ , resulting in the following expression after manipulation. We omit the proof, which relies on the summation expression of [START_REF] Ališauskas | Multiplicity-free u q (n) coupling coefficients[END_REF] for matrix elements.


Ryan Kaliszewski

Huilan Li
email: huilan@math.drexel.edu

The (m, n)-rational q, t-Catalan polynomials for m = 3 and their q, t-symmetry

Keywords: Dyck path, Catalan number, rank word

We introduce a new statistic, skip, on rational (3, n)-Dyck paths and define a marked rank word for each path when n is not a multiple of 3. If a triple of valid statistics (area, skip, dinv) are given, we have an algorithm to construct the marked rank word corresponding to the triple. By considering all valid triples we give an explicit formula for the (m, n)-rational q, t-Catalan polynomials when m = 3. Then there is a natural bijection on the triples of statistics (area, skip, dinv) which exchanges the statistics area and dinv while fixing the skip. Thus we prove the q, t-symmetry of (m, n)-rational q, t-Catalan polynomials for m = 3.

Résumé. Nous introduisons une nouvelle statistique, le skip, sur les chemins de (3, n)-Dyck rationnels et définissons le mot de rang marqué pour chaque chemin quand n n'est pas un multiple de 3. Si un triplet valide de statistiques (aire, skip, dinv) est donné, nous avons un algorithme pour construire le mot de rang marqué correspondant au triplet. En considérant tous les triplets valides, nous donnons une formule explicite pour les polynômes de q, t-Catalan (m, n)rationnels quand m = 3. Enfin, il existe une bijection naturelle sur les triplets de statistiques (aire, skip, dinv)) qui échange les statistiques aires et dinv en conservant le skip. Ainsi, nous prouvons la q, t-symétrie des polynômes de q, t-Catalan (m, n)-rationnels pour m = 3.

Introduction

In the early 1990's Garsia and Haiman introduced an important sum of rational functions in q, t, the classic q, t-Catanlan polynomial C n (q, t), which has since been shown to have interpretations in terms of algebraic geometry and representation theory. Now it is well-known that the classic q, t-Catalan polynomial is C n (q, t) = π q dinv(π) t area (π) (1)

= π q area(π) t bounce(π) , (2)
where the sums are over all Dyck paths π from (0, 0) to (n, n) and ( 2) is due to [START_REF] Haglund | Conjectured statistics for the q, t-Catalan numbers[END_REF]. Though the symmetry problem of the classic q, t-Catalan polynomials has been solved through the use of Macdonald polynomials, no bijective proof has been found, where the bijection means an involution on the set of Dyck paths that exchanges (dinv, area) or (area, bounce). For an overview of the classical q, t-Catalan polynomials and Dyck paths, see, [START_REF] Garsia | Some natural bigraded S n -modules and q, t-Kostka coefficients[END_REF], [START_REF] Garsia | A proof of the q, t-Catalan positivity conjecture[END_REF], Haglund et al. (2005), and [START_REF] Haglund | The q,t-Catalan numbers and the space of diagonal harmonics[END_REF].

Let m and n be coprime. An (m, n)-Dyck path is a path in m × n lattice which proceeds by north and east steps from (0, 0) to (m, n) and which always remains weakly above the main diagonal y = m n x. The number of full cells between an (m, n)-Dyck path Π and the main diagonal is denoted area(Π). The collection of cells above a Dyck path Π forms an English Ferrers diagram λ(Π). For any cell x ∈ λ(Π), let leg(x) and arm(x) denote number of cells in λ(Π) which are strictly south or strictly east of x, respectively. Then define dinv(Π) is the number of cells above the path Π satisfying arm(x) leg(x) + 1 < m n < arm(x) + 1 leg(x) .

(3)

The (m, n)-rational q, t-Catalan polynomial is C m,n (q, t) = Π q dinv(Π) t area (Π) ,

where the sum is over all (m, n)-Dyck paths. Note that for every (m, n)-Dyck path there is a complementary (n, m)-Dyck path with identical statistics. For example, .

Thus the (m, n)-rational q, t-Catalan polynomial is symmetric in the parameters m and n.

The classic q, t-Catalan polynomials correspond to the cases m = n+1.

It is an open conjecture that the (m, n)-rational q, t-Catalan polynomials are symmetric in q and t. [START_REF] Gorsky | Compactified Jacobians and q, t-Catalan numbers[END_REF] have proven the q, t-symmetry for the case when m ≤ 3 without giving an explicit formula for the polynomials. Also, independently, [START_REF] Lee | Combinatorics of certain higher q, t-Catalan polynomials: chains, joint symmetry, and the Garsia-Haiman formula[END_REF] have proven the q, t-symmetry when m ≤ 4.

Using the definition of [START_REF] Hikita | Affine Springer fibers of type A and combinatorics of diagonal coinvariants[END_REF], parking functions and their statistics can be extended to the (m, n)-rational case. [START_REF] Hikita | Affine Springer fibers of type A and combinatorics of diagonal coinvariants[END_REF] defined polynomials

H m,n (X; q, t) = PF t area(PF) q dinv(PF) F ides(PF) (X), (4)
where the sum is over all parking functions PF over all (m, n)-Dyck paths and the F are the (Gessel) fundamental quasisymmetric functions indexed by the inverse descent composition of the reading word of the parking functions PF. When m = 2 or n = 2, the structure of Hikita's polynomials have been completely described by [START_REF] Leven | Two special cases of the Rational Shuffle Conjecture[END_REF]. Since, for each (m, n)-rational Dyck path there is a parking function on that path with the same statistics as the underlying Dyck path, the (m, n)-rational q, t-Catalan polynomial appears as the coefficient of F (1 n ) in the expansion of the Hikita's polynomial H m,n . Thus, describing the structure of the (m, n)-rational q, t-Catalan polynomials is the first step to uncovering the structure of the Hikita's polynomials.

In this paper, we prove that C 3,n (q, t) = n/3 s=0 a,d≥s a+s+d+1=n q d t a

(5)

= n/3 s=0 n-2s-1 a=s q n-a-s-1 t a (6)
and the q, t-symmetry, i.e. C 3,n (q, t) = C 3,n (t, q). (7)

For each (3, n)-Dyck path, we define a marked rank word corresponding to the path and a new statistic skip on the path or the marked rank word. If a triple of valid statistics area, skip and dinv are given, we have an algorithm to construct a marked rank word corresponding to the triple. Then there is a natural bijection on the triples of statistics (area, skip, dinv) which switched the statistics area and dinv. Thus the symmetry in q, t is proved. [START_REF] Gorsky | Compactified Jacobians and q, t-Catalan numbers[END_REF] use a construction similar to our rank words, but the skip statistic in this paper only arises from the markings we place upon the words.

In Section 2, we introduce the notations, background and define the new statistic skip on (3, n)-Dyck paths. In Section 3, we show that every (3, n)-Dyck path is uniquely determined by the triple of statistics area, skip and dinv. We use this triple to construct an explicit formula for C 3,n (q, t). The formula and the uniqueness of the triple allows us to find a unique bijection on (3, n)-Dyck paths which switches the area and dinv statistics while fixing skip. Therefore, the q, t-symmetry of (m, n)-rational q, t-Catalan polynomials for m = 3 is proved.

Notation and Background

Suppose n is a non-negative integer that is not divisible by 3. Let L 3,n be the finite Z-sublattice in the first quadrant with n rows and 3 columns. We use coordinates to describe the location of each cell in L 3,n by first listing the column and then the row. Rows are labeled from bottom to top and columns are labeled from left to right. So the lower-left corner of cell (1,1) rests on the origin. We fill each (a, b) cell in the diagram by it's rank: R(a, b) = -an + 3(b -1). If we denote a cell by a variable, x, then we will denote the rank of x by rk(x).

The rank word of L 3,n is a list of the positive ranks of L 3,n in increasing order with those ranks in the first column colored with subscript 1's and those in the second column colored with subscript 2's. The rank word of the sublattice L 3,n will be denoted by rk(L 3,n ).

Example 2.1 The rank word rk(L 3,5 ) is [ 1 1 , 2 2 , 4 1 , 7 1 ] .
One can think of the rank word as being composed of two interleaved sublists, one colored with 1's and the other with 2's. Sublist 1 contains all of the positive integers that are less than 2n and equivalent to 2n modulo 3, and sublist 2 contains all of the positive integers that are less than n and equivalent to n modulo 3. Thus there are n/3 entries with subscript 2 and 2n/3 entries with subscript 1. This means that there are n -1 entries in rk(L 3,n ).

The rank word of a (3, n)-Dyck path is the rank word of the underlying diagram, L 3,n , with those entries above the Dyck path are marked. In this paper we will mark entries by putting a box around them.

Example 2.2 If Π = -5 -2 1 4 7 -10 -7 -4 -1 2 -15 -12 -9 -6 -3 , then rk(Π) = [ 1 1 , 2 2 , 4 1 , 7 1 ] .
If Π is a (3, n)-Dyck path, define its skip as a collection of adjacent unboxed entries in the rank word with one or more boxed entries to the right and left. In the above example, the 4 is a skip because the 2 and 7 are both in boxes. The 1 is not a skip because there are no boxed entries to the left. Define the skip statistic of Π to be the total number of skips, denoted by skip(Π). 4 1 ,5 2 ,7 1 ,10 1 ,13 1 ] .

(Π 1 ) = [ 1 1 , 2 2 , 4 1 , 5 2 , 7 1 , 10 1 , 13 1 ] rk(Π 2 ) = [ 1 1 , 2 2 ,
Therefore skip(Π 1 ) is 2 because the entries 4 and 7 are each skips. However, skip(Π 2 ) is only 1 because the 7 and 10 entries comprise a single skip. It is useful to confirm that for the Dyck paths above, area(Π 1 ) = 3, area(Π 2 ) = 5, dinv(Π 1 ) = 2, and dinv(Π 2 ) = 1.

We will turn our discussion to the dinv statistic for the rest of this section. Note that the ranks in rk(L 3,n ) only lie in the first and second columns of L 3,n .

Proposition 2.4 Any cell in the second column that is above a (3, n)-Dyck path satisfies the inequality (3), and thus contributes to the dinv.

Proof: As stated earlier, there are at most n/3 cells above the path that lie in the second column. Let x be one such cell. This means that arm(x) = 0 and leg(x) < n/3. Since arm(x) = 0 the left inequality in (3) certainly holds, so we just need to show that 3 • leg(x) < n. But this is exactly what we just claimed. 2 Proposition 2.5 Let Π be a (3, n)-Dyck path. Any cell x in the first column and above Π that does not satisfy the inequality (3) must satisfy one of the following:

arm(x) = 1 and leg(x) < n 3 -1, (8)
arm(x) = 0 and leg(x) > n 3 .

(9)

Proof: Let x be a cell in the first column above the path Π that does not satisfy the inequality (3). Then arm(x) = 1 or arm(x) = 0. Suppose arm(x) = 1. Then the inequality (3) becomes

1 leg(x) + 1 < 3 n < 2 leg(x)
.

From the right inequality, then we have leg(x) < 2n 3 . As we previously discussed, there are never more than 2n/3 positive entries above the path in the first column. So the right inequality is always satisfied. Therefore, the left inequality does not hold, which is equivalent to leg(x) < n 3 -1, which is line (8). Suppose arm(x) = 0. Then the inequality (3) becomes

0 leg(x) + 1 < 3 n < 1 leg(x)
, so the left inequality is immediately satisfied. Therefore, the right inequality does not hold, which is equivalent to leg(x) > n 3 , which is line (9). 2

This proposition tells us that the only cells above the Dyck path that do not contribute to the dinv are those without a cell immediately to the right (above the path) with many cells below or those with a cell immediately to the right (above the path) with few cells below. Thus we can have one case or the other, but not both. Now consider:

Proposition 2.6 If Π is a (3, n)-Dyck path then area(Π) + skip(Π) + dinv(Π) = |rk(L 3,n )| = n -1.
Proof: It is sufficient to show that for every cell above the path that does not contribute to the dinv of Π there is a unique corresponding skip in the rank word of Π. Let x be a such cell that does not satisfy the inequality (3). Then by Proposition 2.5, x satisfies one of two cases: Case 1: arm(x) = 1 and leg(x) < n 3 -1. In this case it is certainly true that leg(x) < n/3 . Let x be the cell that is directly n/3 cells below x. We know that x must lie below the path. We will show that for each x i that does not contribute to the dinv, the rank of x i will lie in a distinct skip.

Suppose x is a cell with arm(x) = 1 that does not contribute to the dinv. From arm(x) = 1, rk(x) > n. So rk(x) = rk(x) -3 • n/3 > 0. Let x be the cell immediately to the right of x. So rk(x) = rk(x) -n.

From n > 3 • n/3 , rk(x) < rk(x) < rk(x).
Since x and x are both above the path, rk(x) must be in a skip. Suppose that x and y are two cells with arm(x) = arm(y) = 1 that do not contribute to the dinv. Assume that rk(x) > rk(y). So rk(x) -3 ≥ rk(y) and rk(y) > rk(x). From 3

• n/3 + 3 > n, rk(y) = rk(y) -3 • n/3 ≤ rk(x) -3 • n/3 -3 < rk(x) -n = rk(x).

So

rk(ŷ) < rk(y) < rk(x) < rk(x) < rk(x),

i.e., rk(x) and rk(y) must be in distinct skips.

Case 2: arm(x) = 0 and leg(x) > n 3 . From arm(x) = 0, x must lie below the path. We will show that for each x i that does not contribute to the dinv, the rank of xi will lie in a distinct skip.

Let x be the cell n/3 below cell x. Since leg(x) > n 3 then cell x is above the path. From 3• n/3 > n, rk(x) = rk(x) -3 • n/3 < rk(x) -n = rk(x). So we have rk(x) < rk(x) < rk(x).

Since x and x are both above the path, rk(x) must be in a skip.

Suppose that x and y are two cells with arm(x) = arm(y) = 0 that do not contribute to the dinv. Assume that rk(x) > rk(y). So rk(x) -3 ≥ rk(y) and rk(y) > rk(x). From 3

• n/3 > n + 3, rk(ŷ) = rk(y) -n ≤ rk(x) -n -3 < rk(x) -3 • n/3 = rk(x). So rk(ȳ) < rk(ŷ) < rk(x) < rk(x) < rk(x),
i.e., rk(x) and rk(ŷ) must be in distinct skips.

Uniqueness of rank words

In this section we will show that every (3, n)-Dyck path is uniquely determined by the dinv, area, and skip statistics. That is if Π 1 and Π 2 are Dyck paths such that

area(Π 1 ) = area(Π 2 ), skip(Π 1 ) = skip(Π 2 ), dinv(Π 1 ) = dinv(Π 2 ), then Π 1 = Π 2 . We know that area(Π 1 ) + skip(Π 1 ) + dinv(Π 1 ) = | rk(L 3,n )| = n -1.
Therefore it is immediate that both paths must be inscribed in the same lattice. So let us consider an algorithm that generates a rank word, given a Dyck path (later we will prove that it is the rank word associated to the Dyck path): We can compute that dinv(Π 1 ) = 2 and skip(Π 1 ) = 2. If we follow the algorithm we have:

Path
Initial: 4 1 ,5 2 ,7 1 ,10 1 ,13 1 ] because we skipped the 7 which has color 1 and boxed the rightmost entry that hasn't been skipped or boxed, the 5. i = 2:

[ 1 1 , 2 2 , 4 1 , 5 2 , 7 1 , 10 1 , 13 1 ] because d = 2. i = 1: [ 1 1 , 2 2 ,
[ 1 1 , 2 2 , 4 1 , 5 2 , 7 1 , 10 1 , 13 1 ] because we skip the 4, and boxed the rightmost entry that hasn't been skipped or boxed, the 2. Since s = 2 we only perform two iterations of the loop, so we are done.

Similarly for Π 2 we have:

Initial: [ 1 1 , 2 2 , 4 1 , 5 2 , 7 1 , 10 1 , 13 1 ] because d = 1. i = 1:
[ 1 1 , 2 2 , 4 1 , 5 2 , 7 1 , 10 1 , 13 1 ] we skip the 10 and the 7 because they are adjacent and have the same color. Then we box the rightmost entry which hasn't been boxed or skipped, which is the 5. We have finished the algorithm at this point because s = 1, so we only performed one iteration of the loop.

This leads us to the following proposition:

Proposition 3.2 If Π is a (3, n)-
Dyck path and we use the path rank word construction algorithm to generate a word ω(Π), then ω(Π) = rk(Π).

Proof: To construct a (3, n)-Dyck path it is equivalent to choose a number of cells in the first column as well as a number of cells in the second column (subject to constraints) to be above the path. This is essentially choosing a number of entries colored 1 as well as a number of entries colored 2 in the rk(L 3,n ) to box . Moreover, all of the boxed entries of a specific color must be the rightmost entries. For instance, in the previous example, when we constructed the rank word of Π 1 we boxed the two rightmost entries colored with 1 and the two rightmost entries colored with 2. Suppose that there are k cells above the path in the first column and cells above the path in the second column.

Case 1: Suppose that k < n/3. We will show that k = dinv(Π) and = skip(Π). From Proposition 2.5, each cell in column one that has arm equal to zero will contribute to the dinv of Π because the leg is certainly less than n/3. Every cell in column one that has arm equal to one does not contribute to the dinv.

Suppose > 0. Consider the upper left cell, call it x. We have arm(x) = 1 and leg(x) = k-1 < n 3 -1, i.e., x does not contribute to dinv. The other cells in column one with arm one have shorter legs. They will not contribute to dinv either.

In rk(L 3,n ) the rightmost dinv(Π) = k entries will be boxed, and they are all color 1. Then the remaining rightmost 1-colored entries will be skipped (due to skipping) and the rightmost skip(Π) = 2-colored entries will be boxed. This concludes the proof of this case.

Case 2: Suppose that k > n/3 and k -> n 3 + 1. From Proposition 2.5, skip(Π) is equal to the number of cells with arm zero and whose leg is greater than n/3. There are k --n/3 such cells so skip(Π) = k --n/3 and dinv(Π) = 2 + n/3 .

In rk(L 3,n ) there are n/3 entries with color 1 on the right and then the entries alternate in color, beginning with 2. Thus we will box n/3 color 1 entries, then entries with color 2 and entries with color 1. Since the last entry we boxed was 1, we will begin skipping color 2 entries and box k --n/3 color 1 entries. Therefore the rightmost color 2 entries are boxed and the rightmost n/3 + + (k --n/3 ) = k color 1 entries are boxed. This completes the proof for this case.

Case 3: Suppose that k > n/3 and k -< n 3 + 1. From Proposition 2.5, skip(Π) is equal to the number of cells with arm equal to one and whose leg is less than n 3 -1. There are -k + n/3 of these. Thus skip(Π) = -k + n/3 and dinv(Π) = 2k -n/3 .

In rk(L 3,n ) there are n/3 color 1 entries on the right and then the entries alternate in color, beginning with 2. Thus we will box n/3 color 1 entries. Then we will box 2k-n/3 -n/3 = 2k-2• n/3 -1 entries: k -n/3 color 2 entires and k -n/3 -1 color 1 ones. Then we will box -k + n/3 color 2 entries at the same time skip -k + n/3 color 1 entries. So we have boxed n/3 + k -n/3 -1 = k entries with color 1 and k -n/3 + -k + n/3 = entries with color 2. This completes the proof. 2

Remark 1 Any rank word with the rightmost k color 1 entries boxed, the rightmost color 2 entries boxed, and k ≥ corresponds uniquely to a (3, n)-Dyck path.

In order to satisfy these conditions, the following inequalities must hold for any (3, n)-Dyck path Π:

1. 0 ≤ skip(Π) < n/3, 2. skip(Π) ≤ dinv(Π) ≤ n -1 -2 • skip(Π), 3. skip(Π) ≤ area(Π) ≤ n -1 -2 • skip(Π).
The first inequality is clear because either the rank word skips only color 2 entries (of which there are n/3 ) or skips only color 1 entries. There are 2n/3 color 1 entries, but the first n/3 entries only contribute at most one skip. We know 2n/3 -n/3 ≤ n/3 . When 2n/3 -n/3 < n/3 , the first entry of the rank work has color 2. So, totally, there are at most n/3 entries with color 1 that contribute skips. When 2n/3 -n/3 = n/3 , the first entry of the rank work is color 1, which can not be a skip. Again, totally, there are at most n/3 entries with color 1 that contribute skips.

For the second inequality, if dinv(Π) ≥ n/3 , from skip(Π) < n/3 we have skip(Π) ≤ dinv(Π). If dinv(Π) < n/3 , then only color 1 entries are skipped. The number of boxed color 1 entries is dinv(Π) and the number of boxed color 2 entries is skip(Π). Recall that there must be at least as many color 1 ranks boxed as color 2 ranks boxed in the rank word of a path. So skip(Π) ≤ dinv(Π).

The right part of the second inequality equivalent to skip(Π) ≤ area(Π) (recall that area(Π) + skip(Π) + dinv(Π) = n -1). It follows from the fact that the area of a path is the number of unboxed entries in the rank word and a skip must always skip at least one entry. From this argument one can also see that the second and third inequalities are actually equivalent.

The definition of ω, above, does not actually require a path. If we have three non-negative integers that satisfy the above inequalities we can generate a rank word, call it ω(area, skip, dinv). Proof: Set n = a + s + d + 1. We only need to check that ω(a, s, d) has enough entries to ensure that s skips can be performed. If d ≥ n/3 then each skip corresponds to two entries, one skipped and one not skipped. So we need 2s + d ≤ s + a + d, which is true. If d < n/3 then the first skip and the rightmost d entries together encompass n/3 + 1 of the total entries. The remaining skips then correspond to two entries. Again, we need 2(s -1) + n/3 + 1 ≤ s + a + d, which is equivalent to s -1 + n/3 ≤ a + d.

(10)

Recall that area is the unboxed entries. Since there were n/3 -d skipped entries at the first skip and s -1 skipped entries in the middle, a ≥ n/3 -d + s -1, which is exactly inequality (10). 2

Remark 2 Note that if s ≤ a, d and n = a + s + d + 1 then immediately s < n/3. This leads us to the following theorem:

Theorem 3.4

C 3,n (q, t) = n/3 s=0 a,d≥s a+s+d+1=n

q d t a (11)
= n/3 s=0 n-2s-1 a=s q n-a-s-1 t a (12) Theorem 3.5 There is a unique bijection on the set of (3, n)-Dyck paths that exchanges area and dinv while fixing skip.

Proof: This follows from the fact that the area, skip, and dinv statistics uniquely define a path and for every (a, s, d) triple corresponding to a path, (d, s, a) also corresponds to a path. 2

Corollary 3.6 The (3, n)-rational q, t-Catalan polynomials are symmetric in q and t, i.e., C 3,n (q, t) = C 3,n (t, q). (13)

This theorem leads us in two natural directions for further research. First, generalize the skip statistic to arbitrary (m, n)-Dyck paths, which would give insight into finding an involution that exchanges area and dinv. Second, completely describe Hikita's polynomial H 3,n (4) since we know the coefficient of

F (1 n ) .

  rank word construction algorithm Data: Three non-negative integers, a, s, and d such that a = area(Π), s = skip(Π), and d = dinv(Π) for some (3, n)-Dyck path. Result: The rank word of Π, rk(Π). Let n = a + s + d + 1 and set r = rk(L 3,n ), the rank word of the diagram. Put boxes around the rightmost d entries of r. For i = 1 to s Moving left, skip all successive entries of the same color. Box the rightmost entry that hasn't been skipped or boxed. end Example 3.1 Consider the (3, 8)-Dyck paths:

Corollary 3. 3

 3 Given three non-negative integers a, s, d that satisfy1. s ≤ a, 2. s ≤ d, 3. a + s + d + 1 is not divisible by 3,then there is a unique (3, a + s + d + 1)-Dyck path Π with a = area(Π), s = skip(Π), and d = dinv(Π).

Acknowledgements

We would like to thank Adriano Garsia and Jim Haglund for the motivation to work on this problem. We wish to thank Emily Leven for inspiring conversations on this topic. We are also grateful to the anonymous reviewers for providing useful comments and papers to compare to our work.

The (m, n)-rational q, t-Catalan polynomials for m = 3 and their q, t-symmetry