Sminaire Lotharingien de Combinatoire 76 (2019), Article B76d

NON-SYMMETRIC MACDONALD POLYNOMIALS AND DEMAZURE–LUSZTIG OPERATORS

PER ALEXANDERSSON

Abstract. We extend the family non-symmetric Macdonald polynomials and define permuted-basement Macdonald polynomials. We show that these also satisfy a triangularity property with respect to the monomial basis and behave well under the Demazure–Lusztig operators. The symmetric Macdonald polynomials P_{λ} are expressed as a sum of permuted-basement Macdonald polynomials via an explicit formula.

By letting q = 0, we obtain t-deformations of key polynomials and Demazure atoms and we show that the Hall–Littlewood polynomials expand positively into these deformations. This generalizes a result by Haglund, Luoto, Mason and van Willigenburg. As a corollary, the Schur polynomials decompose with non-negative coefficients into t-deformations of general Demazure atoms and thus generalize the t = 0 case which was previously known. This gives a unified formula for the classical expansion of Schur polynomials in Hall–Littlewood polynomials and the expansion of Schur polynomials into Demazure atoms.

1. Introduction

We study a generalization of non-symmetric Macdonald polynomials by adding a permutation parameter σ to the combinatorial model for the classical non-symmetric Macdonald polynomials. These are called permuted-basement Macdonald polynomials and were previously introduced in [Fer11]. The parameter σ allows us to interpolate between two different parameterizations of the Macdonald polynomials. This makes some unpublished results by J. Haglund and M. Haiman mentioned in the introduction of [HMR12, TR13] explicit.

This extended family of polynomials satisfies many properties shared with the classical non-symmetric Macdonald polynomials:

2010 Mathematics Subject Classification. 05E10,05A30,33D52. Key words and phrases. Key polynomials, Demazure characters, standard bases,

Macdonald polynomials, Demazure operators, Hall–Littlewood polynomials.

• For each fixed value of σ, a triangularity property with respect to expansion in the monomial basis holds. Consequently, the permuted-basement Macdonald polynomials constitute a basis for ℚ(q, t)[x_{1}, …, x_{n}] for each fixed σ.

• The permuted-basement Macdonald polynomials behave nicely under certain affine Hecke algebra operators. These operators are known as the Demazure–Lusztig operators, which can be seen as a t-interpolation between the Demazure operators and the operations which perform a simple transposition on indices of variables. In particular, these operators act on the parameter σ in a simple way, see Proposition 15. Consequently, there is a combinatorial definition based on fillings of diagrams, as well as a recursive definition via such operators.

• We give the expansion of the classical symmetric Macdonald polynomial, P_{λ}, in the permuted-basement Macdonald polynomials in Theorem 29.

• The specialization q = 0 gives t-deformed Demazure atoms. In particular, in Corollary 30 we show that the Hall–Littlewood polynomials expand positively in permuted-basement Macdonald polynomials when q = 0, thus extending a result in [HLMvW11].

• The specialization t = q = 0 of the permuted-basement Macdonald polynomials give the Demazure characters (also known as key polynomials) and Demazure atoms.

• The result in [Mas09, Prop. 6.1] proves an equality between two combinatorial models for the key polynomials. In Proposition 27, we extend her result to incorporate the t parameter as well as showing the analogous statement for Demazure t-atoms,

Our goal with this paper is therefore to give a unified treatment of non-symmetric Macdonald polynomials and specializations of these, such as Demazure atoms, key polynomials and the related operators. The methods we use are based on the general theory of non-attacking fillings developed in [HHL08].

2. Preliminaries — Fillings and statistics

MACDONALD POLYNOMIALS AND DEMAZURE–LUSZTIG OPERATORS 3

Let σ = (σ_{1}, …, σ_{n}) be a list of n different positive integers and let α = (α_{1}, …, α_{n}) be a weak integer composition, that is, a vector with non-negative integer entries. An augmented filling of shape α and basement σ is a filling of a Young diagram of shape (α_{1}, …, α_{n}) with positive integers, augmented with a zeroth column filled from top to bottom with σ_{1}, …, σ_{n}. Note that we use English notation rather than the skyline fillings used in [HHL08, Mas09]. For example, the following figure illustrates the difference:

6 5 5 5 4 3 3 4 2 2 2 1 1 6

Our convention

2 6 4  5 1 2 3  5 1 2 3 4 5 6

Skyline convention

In the skyline convention, the basement appears in the bottom of the diagram, thus explaining the peculiar choice of terminology.

Definition 1. Let F be an augmented filling. Two boxes a, b, are attacking if F (a) = F (b) and the boxes are either in the same column, or they are in adjacent columns, with the rightmost box in a row strictly below the other box.

a ; ⋮ ; b or a ; ⋮ ; b

A filling is non-attacking if there are no attacking pairs of boxes.

Definition 2. A triple of type A is an arrangement of boxes, a, b, c, located such that a is immediately to the left of b, and c is somewhere below b, and the row containing a and b is at least as long as the row containing c. Similarly, a triple of type B is an arrangement of boxes, a, b, c, located such that a is immediately to the left of b, and c is somewhere above a, and the row containing a and b is strictly longer than the row containing c.

A type A triple is an inversion triple if the entries ordered increasingly form a counter-clockwise orientation. Similarly, a type B triple is an inversion triple if the entries ordered increasingly form a clockwise orientation. If two entries are equal, the one with largest subscript in (1) is considered largest.

Type A: a^{3} b^{1} ; ⋮ ; c_{2}  Type B: c_{2} ; ⋮ ; a^{3} b^{1}  (1)

If u = (i, j) let d(u) denote (i, j − 1). A descent in F is a nonbasement box u such that F (d(u)) < F (u). The set of descents in F is denoted Des(F).

Example 3. Below is a non-attacking filling of shape (4, 1, 3, 0, 1) and with basement (4, 5, 3, 2, 1). The bold entries are descents and the underlined entries form a type A inversion triple. There are 7 inversion triples (of type A and B) in total.

\underline{4} \underline{2} 1 2 4 5 5 3 3 4 3 2 1 \underline{1}

The leg of a box, denoted leg(u), in an augmented diagram is the number of boxes to the right of u in the diagram. The arm, denoted arm(u), of a box u = (r, c) in an augmented diagram α is defined as the cardinality of the sets

{(r′, c) ∈ α : r < r′ and α_{r′} ≤ α_{r}} and
{(r′, c − 1) ∈ α : r′< r and α_{r′} < α_{r}}.

We illustrate the boxes x and y (in the first and second set in the union, respectively) contributing to arm(u) below. The boxes marked l contribute to leg(u). The arm values for all boxes in the diagram are shown in the diagram on the right.

\begin{aligned}y \\ y \\ & u & l & l & l \\ & x \\ & x \end{aligned}  4 2 2 1 1 6 4 3 2 1 3 1 0 1 4 3 1 1

The major index, maj(F), of an augmented filling F is given by

maj(F) = ∑_{u∈Des(F)} leg(u) + 1.

The number of inversions, inv(F) of a filling is the number of inversion triples of either type. The number of coinversions, coinv(F), is the number of type A and type B triples which are not inversion triples.

Let NAF_{σ}(α) denote all non-attacking fillings of shape α, augmented with the basement σ ∈ S_{n}, and all entries in the fillings are in {1, …, n}.

Example 4. The set NAF_{3124}(1, 1, 0, 2) consists of the following augmented fillings:

3 1 1 2 2 4 4 3 coinv:1 maj:1  3 1 1 2 2 4 4 4 coinv:1 maj:1  3 2 1 1 2 4 4 3 coinv:0 maj:0  3 2 1 1 2 4 4 4 coinv:0 maj:0

3 3 1 1 2 4 4 2 coinv:1 maj:0  3 3 1 1 2 4 4 4 coinv:0 maj:0  3 3 1 2 2 4 4 1 coinv:2 maj:1  3 3 1 2 2 4 4 4 coinv:0 maj:1

Given a filling F of shape α we let x^{F} denote the product ∏ _{u∈α} x_{F (u)}. For example, the last filling in the previous example gives x^{F} = x_{2}x_{3}x_{4}^{2}. Note that the basement entries do not contribute to the product.

3. A generalization of non-symmetric Macdonald polynomials

The length of a permutation, ℓ(σ), is the number of inversions in σ. We use the standard convention and let ω_{0} denote the unique longest permutation in S_{n}, that is, ω_{0} = (n, n − 1, …, 1) in one-line notation. Permutations act on weak compositions by permuting the entries, and S_{n} act on R[x_{1}, …, x_{n}] (R will mainly be the ring ℂ(q, t)) by permuting the indices of the variables. Throughout the paper, α and γ denote weak compositions while λ and μ are integer partitions.

Definition 5. Let σ ∈ S_{n} and let α be a composition with n parts. The non-symmetric permuted basement Macdonald polynomial E_{α}^{σ}(x; q, t) is defined as

E_{α}^{σ}(x; q, t) = ∑_{F ∈NAF_{σ} (α)} x^{F}q^{maj(F)}t^{coinv(F)} ∏_{u∈F u is in the basement or F (d(u))≠F (u)} \frac{1 − t}{1 − q^{1+leg(u)} t^{1+arm(u)}} . (2)

The product is over all boxes u in F, such that either u is in the basement or F (d(u)) ≠ F (u).

When σ = ω_{0}, we recover^{1} the non-symmetric Macdonald polynomials defined in [HHL08], E_{α}(x; q, t). We refer to this particular value of σ as the key basement and we simply write E_{α}(x; q, t) for E_{α}^{ω_{0}} (x; q, t).

1There is a slight difference in notation, the index α is reversed compared to [HHL08].

3.1. Properties of non-symmetric Macdonald polynomials. The following relation is a part of the Knop–Sahi recurrence relations for Macdonald polynomials [Kno97, Sah96]:

Eα̂(x; q, t) = q^{α_{1}} x_{1}E_{α}(x_{2}, …, x_{n}, q^{−1} x_{1}; q, t),  (3)

where α̂ = (α_{2}, …, α_{n}, α_{1} + 1). Also note that

E_{(α_{1}+1,...,α_{n} +1)}^{σ} (x; q, t) = (x_{1} ⋯ x_{n})E_{(α_{1},...,α_{n})}^{σ} (x; q, t),

which allows us to extend the definition of non-symmetric Macdonald “polynomials” to compositions α with negative entries.

Proposition 6 (see [HHL08, Cor. 3.6.4]). We have the relation

E_{α}^{ω_{0}} (x_{1}, …, x_{n}; q, t) = E_{α}^{id}(x_{n}, …, x_{1}; q^{−1} , t^{−1} ).

The polynomials appearing on the right-hand side above is the version of non-symmetric Macdonald polynomials studied by D. Marshall in [Mar99].

Question 7. Can Proposition 6 be generalized to basements?

Using Eq. (2) and Proposition 6, we obtain the following diagram of specializations, where we recover the key polynomial K_{α}(x) and Demazure atom, A_{α}(x). These specializations were proved in [Mas09] — we give the classical definition (as described in [LS90, RS95]) of key polynomials and Demazure atoms in Section 6.

E_{α}^{σ}(x; q, t) −−−→^{σ=ω_{0}} E_{α}^{ω_{0}} (x; q, t) −−−→^{t=q=0} K_{α}(x) −−−→^{α=λ} s_{λ}(x)
↓^{σ=id}  ↓ \begin{matrix}t=q=∞ \\ x_{i}→x_{n+1−i} \end{matrix}
E_{α}^{id}(x; q, t) −−−→^{t=q=0} A_{α}(x)

It is also easy to verify that semi-standard augmented fillings of partition shape λ and basement ω_{0} can be put in bijection with semistandard Young tableaux of shape λ. This shows that the key polynomial K_{λ} is the Schur polynomial s_{λ} (in n variables) whenever λ is a partition.

The classical non-symmetric Macdonald polynomials specialize to other well-known families of polynomials: the elementary symmetric functions, e_{λ}, the monomial symmetric functions, m_{λ}, and the symmetric Macdonald polynomials, P_{λ}(x_{1}, …, x_{n}; q, t). See [Mac95] for definitions.

E_{α}(x; q, t) −−−→^{∗} P_{λ}(x; q, t)
↓ \begin{matrix}α=λ \\ q=1 \\ t=0 \end{matrix}  ↓ \begin{matrix}q=1 \\ t=0 \end{matrix}
e_{λ′}(x)  m_{λ}(x).

Here, ∗ is indicate the relation

E_{(λ,0^{n})}(x_{1}, …, x_{n}, 0, …, 0; q, t) = P_{λ}(x_{1}, …, x_{n}; q, t)

for partitions λ with n parts. The polynomials E_{α}(x; 1, 0) can thus be interpreted as non-symmetric analogues of the elementary symmetric functions e_{λ}. See the subsequent work [AS17, AS19] for further details on this interpretation.

Some specializations of non-symmetric Macdonald polynomials, such as E_{α}(x; q, 0) and E_{α}(x; q^{−1} , ∞) have representation-theoretical interpretations, see [FM15, FM17, FMO18]. In particular, we note that [FM15] consider the combinatorial model defined in (2) in an expansion of some E_{α}(x; q^{−1} , ∞).

3.2. Alcove walk model. Another interesting article concerning nonsymmetric Macdonald polynomials is [RY11], which gives a combinatorial model using alcove walks. The basic idea is to repeatedly use Proposition 17 below, expand the product and interpret the terms. This method expresses a Macdonald polynomials as a sum over alcove walks starting at the fundamental alcove and ending at the alcove representing the particular Macdonald polynomial we are interested in.

Permuted-basement Macdonald polynomials can also be generated in this way — the choice of a starting alcove — which can be done in n! ways — corresponds to the basement, see [FMO18].

This interpretation should allow us to extend permuted-basement Macdonald polynomials to other Lie types. Note that the notion of key polynomials is known in other types, defined via crystal operators, see for example [HL16].

3.3. Triangularity. In this subsection, we prove that the permutedbasement Macdonald polynomials satisfy a triangularity property with respect to the monomial basis.

Definition 8. We define the Bruhat order on compositions of m with n parts as the transitive closure of the following relations. Here, e_{i} denotes the unit vector with an 1 at position i.

• If i < j and α_{j} > α_{i} then α >_{st} s_{ij} (α), where s_{ij} is the transpo-

sition (i, j).

• If i < j and α_{j} − α_{i} > 1 then s_{ij} (α) >_{st} α + e_{i} − e_{j}.

Just as for the classical non-symmetric Macdonald polynomials, the E_{α}^{σ}(x; q, t) satisfy a triangularity condition with respect to the monomial basis:

E_{α}^{σ}(x; q, t) ∈ x^{σ^{−1} (α)} + ℚ(q, t){x^{σ^{−1} (γ)} : γ <_{st} α}.  (4)

Alternatively, this can be expressed in a slightly more pleasant way as

E_{α}^{σ}(σx; q, t) ∈ x^{α} + ℚ(q, t){x^{γ} : γ <_{st} α}.  (5)

We prove triangularity with respect to a lexicographic total ordering, similar to what is done in [Mac95] for the classical symmetric Macdonald polynomials. This ordering extends the Bruhat order defined above. Here, λ(α) denotes the unique partition obtained from α by sorting the parts in a decreasing manner, and >_{lex} is the standard lexicographic order, comparing elements component-wise from left to right.

Proposition 9 (Triangularity). Let γ and α be weak compositions of m with n parts. Then for any basement σ ∈ S_{n},

[x^{σ^{−1} (γ)}]E_{α}^{σ}(x; q, t) = \{ \begin{matrix}0 if λ(γ) >_{lex} λ(α), \\ 0 if λ(γ) = λ(α) and γ >_{lex} α, \\ 1 if γ = α. \end{matrix}

Proof. First note that [x^{σ^{−1} (γ)}]E_{α}^{σ}(x; q, t) = [x_{σ_{1}}^{γ_{1}} x_{σ_{2}}^{γ_{2}} ⋯ x_{σ_{k}}^{γ_{k}}]E_{α}^{σ}(x; q, t), so we focus on non-attacking fillings of shape α and γ_{i} entries with value σ_{i} for i = 1, …, n.

Case λ(γ) >_{lex} λ(α): Let λ = λ(γ) and μ = λ(α). The condition implies that there is some j ≥ 1 such that

λ_{1} = μ_{1}, λ_{2} = μ_{2}, … λ_{j−1} = μ_{j−1} and λ_{j} > μ_{j}.

Suppose there is a way to create a non-attacking filling with these properties. Then there must be λ_{1} equal entries in different columns, then λ_{2} equal entries in different columns and so on.

If j = 1, it is evident that there is no such non-attacking filling, since λ_{1} entries must appear in different columns but there are only μ_{1}(< λ_{1}) columns available.

In the case j > 1, it is straightforward to show by induction that, after placing the first λ_{1} + λ_{2} + λ_{j−1} entries, the number of columns with available empty boxes is μ_{j}. Since μ_{j} < λ_{j}, there is no nonattacking filling with weight x_{σ_{1}}^{γ_{1}} x_{σ_{2}}^{γ_{2}} ⋯ x_{σ_{n}}^{γ_{n}} , shape γ and basement σ if λ(γ) >_{lex} λ(α).

Case λ(γ) = λ(α) and γ >_{lex} α: Assume that there is a filling T with shape α and weight x_{σ_{1}}^{γ_{1}} x_{σ_{2}}^{γ_{2}} ⋯ x_{σ_{n}}^{γ_{n}} . Let γ_{i} be a largest entry in γ. This implies that there is exactly one entry σ_{i} in each column of T and in particular, at the end of some longest row with length α_{l} = γ_{i}. The non-attacking condition for adjacent columns now implies that, if column c has an entry equal to σ_{i} in row r_{1}, and column c + 1 has an entry equal to σ_{i} in row r_{2}, then r_{1} ≥ r_{2}. Hence T is of the form exemplified in (6), where ∗ marks entries with value σ_{i}.

\begin{matrix}σ^{1} & & & & α^{1} \\ σ^{2} & & & & ∗ & ∗ & ∗ & α^{2} \\ σ^{3} & & ∗ & ∗ & & α^{3} \\ σ^{4} & ∗ & α^{4} \\ σ^{5} & & & α^{5} \end{matrix}  (6)

It follows that i ≥ l. By removing the last box in row l, we obtain a smaller filling T′, with weight and shape given by

γ′= (γ_{1}, …, γ_{i−1} , γ_{i} − 1, γ_{i+1} , …, γ_{n}),
α′ = (α_{1}, …, α_{l−1} , α_{l} − 1, α_{i+1} , …, α_{n}).

Finally, note that λ(γ′) = λ(α′) and γ′>_{lex} α′, since γ_{i} = α_{l} and i ≥ l. However, this is absurd, since repeating this procedure eventually yields the empty filling, where γ >_{lex} α is no longer true. Therefore, there cannot be a valid filling T satisfying all conditions to begin with.

Case γ = α: As in the previous case, suppose that there is a filling, T, satisfying the conditions, and repeatedly remove a box from some longest row as before. This operation preserves the property γ ≥_{lex} α, but we know that, as soon as a strict inequality is obtained, there is no such filling.

In order to have equality γ = α after each removal of a box, we need that all σ_{i} appear in the same row. It follows that T must be the unique filling where every row i is filled with boxes with value σ_{i}. This filling has no inversions and no two different horizontally adjacent boxes, so T contributes with the monomial x_{σ_{1}}^{γ_{1}} x_{σ_{2}}^{γ_{2}} ⋯ x_{σ_{n}}^{γ_{n}} . This proves the triangularity statement in (4). □

Question 10. Is there a natural inner product (depending on σ) for which the E_{α}^{σ}(x; q, t) form an orthogonal basis?

4. Demazure–Lusztig operators

In this section we introduce a set of operators acting on polynomials in x_{1}, …, x_{n}. These appear in the study of key polynomials and Demazure atoms, see e.g. the paper [RS95] by V. Reiner and M. Shimozono for a background on key polynomials and properties of these operators.

Let s_{i} ∈ S_{n} denote the simple transposition (i, i + 1) and define

∂_{i} = \frac{1 − s_{i}}{x_{i} − x_{i+1}} , π_{i} = ∂_{i}x_{i}, θ_{i} = π_{i} − 1.

Note that ∂_{i}(f) is indeed a polynomial if f is, since f −s_{i}f is divisible by x_{i}−x_{i+1} . The operators π_{i} and θ_{i} are used to define the key polynomials and Demazure atoms, respectively, and we give this definition further down. It should be mentioned that θ_{i} and π_{i} are closely related to crystal operators and i-strings, see [Mas09] for details. Now define the following t-deformations of the above operators:

π̃_{i}(f) = (1 − t)π_{i}(f) + ts_{i}(f) θ̃_{i}(f) = (1 − t)θ_{i}(f) + ts_{i}(f).  (7)

The θ̃_{i} are called the Demazure–Lusztig operators and are generators for the affine Hecke algebra that appear in [HHL08] (where θ̃_{i} is denoted T_{i}). A similar set of operators appears in [LLT97, p. 4], in the definition of Hall–Littlewood functions.

It should be mentioned that [Fer11] provides a nice characterization of the permuted-basement Macdonald polynomials as simultaneous eigenfunctions of certain products of Demazure–Lusztig operators and the operation in (3). This is a generalization of Cherednik’s representation [Che95] of the affine Hecke algebra mentioned above.

4.1. Some properties of θ̃_{i} and π̃_{i}. Using the definition above, it is straightforward to show that θ̃_{i}^{2} = (t − 1)θ̃_{i} + t, which implies that π̃_{i} θ̃_{i}(f) = θ̃_{i}π̃_{i}(f) = tf. Hence, θ̃_{i} and π̃_{i} are essentially inverses of each other. We also see that π̃_{i} can be expressed in θ̃_{i} as

π̃_{i}(f) = θ̃_{i}(f) + (1 − t)(f).  (8)

The θ̃_{i} and π̃_{i} satisfy the braid relations:

• θ̃_{i}θ̃_{j} = θ̃_{j} θ̃_{i} whenever |i − j| ≥ 2 and

• θ̃_{i}θ̃_{j} θ̃_{i} = θ̃_{j} θ̃_{i}θ̃_{j} when |i − j| = 1.

The same relations are satisfied by the π̃_{i}. This implies that, if ω = ω_{1} ⋯ ω_{ℓ} and ω′= ω′_{1}⋯ ω′_{ℓ} are both reduced words for the same permutation in S_{n}, then θ̃_{ω_{1}} θ̃_{ω_{2}} ⋯ θ̃_{ω_{ℓ}} = θ̃_{ω′_{1}} θ̃_{ω′_{2}} ⋯ θ̃_{ω′_{ℓ}}. Hence, if τ ∈ S_{n} is a permutation, we can define θ̃_{τ} as θ̃_{ω_{1}} θ̃_{ω_{2}} ⋯ θ̃_{ω_{ℓ}}, where ω is any reduced word for τ. The braid relations above ensure that this is independent of the choice of reduced word and thus well-defined. We define π̃_{τ} in a similar fashion.

The following lemma is a straightforward consequence of the definitions above.

Lemma 11. If f is symmetric in x_{i} and x_{i+1} then

• θ̃_{i}(f) = tf,

• π̃_{i}(f) = f,

• θ̃_{i}(f · g) = f · θ̃_{i}(g) for any g, and

• θ̃_{j}f is symmetric in x_{i} and x_{i+1} for j ∉ {i − 1, i + 1}.

The following lemma is an important tool in Section 4.4.

Lemma 12 ([HHL08]). We have θ̃_{i}(f) = g if and only if f + g and tx_{i+1} f + x_{i}g are both symmetric in x_{i} and x_{i+1} .

Lemma 13. The following mixed braid relations hold for π̃_{i} and θ̃_{i}:

\{ \begin{matrix}π̃_{i} π̃_{i−1} θ̃_{i} = θ̃_{i−1} π̃_{i} π̃_{i−1} \\ π̃_{i−1} π̃_{i} θ̃_{i−1} = θ̃_{i}π̃_{i−1} π̃_{i} \end{matrix}  and \{ \begin{matrix}π̃_{i−1} θ̃_{i}θ̃_{i−1} = θ̃_{i}θ̃_{i−1} π̃_{i} \\ π̃_{i} θ̃_{i−1} θ̃_{i} = θ̃_{i−1} θ̃_{i}π̃_{i−1} . \end{matrix}

Proof. Express π̃_{i} and π̃_{i−1} in terms of θ̃_{i} and θ̃_{i−1} , respectively, and expand. □

4.2. Something about knots. There is a deep connection between Macdonald polynomials and knot theory, see for example the connection between Jones polynomials and Macdonald polynomials [Che12]. It is not surprising, given the braid relations involving θ̃_{i} and π̃_{i}. For a background on the braid group, see the introduction and definitions in [Deh08]. Intuitively, θ̃_{i} and π̃_{i} can be seen as ŝ_{i} and ŝ_{i}^{−1} in the Artin presentation of the braid group. The relations in Lemma 13 are compatible with this interpretation, the only caveat here is that θ̃_{i}π̃_{i} = t, while ŝ_{i}ŝ_{i}^{−1} = id. This has the consequence that, if ŝ_{i_{1}}^{±1} ŝ_{i_{2}}^{±1} ⋯ ŝ_{i_{ℓ}}^{±1} is a reduced word in the braid group, then substitution of ŝ_{i} ↦ θ̃_{i} and ŝ_{i}^{−1} ↦ π̃_{i} gives a reduced word of operators.

4.3. Symmetries of diagram fillings. In this subsection, we introduce the necessary notation to state an important proposition proved in [HHL08]. The complete proof is fairly involved and closely related to the theory of LLT polynomials, see the Appendix in [Hag07]. We first generalize the notion of diagrams, arm values, leg values, major index and inversions. A lattice-square diagram D is subset of boxes (i, j) ∈ ℕ^{2}. The reading order of a lattice diagram is the total order given by reading squares column by column from right to left, and from top to bottom within each column, as in (9).

12 8 4 13 9 6  2 1 10 5 3 14 11 15  7  (9)

Arm and leg values for each box in a lattice-square diagram are arbitrary fixed non-negative integers. We say that two boxes u, v form an inversion pair in a filling F if they are attacking, v precedes u in reading order and F (u) < F (v). Similarly, the descent set, Des(F), of a filling is the set of boxes u ∈ F such that d(u) ∈ F and F (d(u)) < F (u). Define inv and maj statistics for arbitrary lattice-square fillings as

inv(F) = |{(u, v) : u, v is an inversion pair inF }| − ∑_{s∈Des(F)} arm(s)
maj(F) = ∑_{s∈Des(F)} (1 + leg(s)).

It is shown in [HHL08] that these definitions extend the corresponding statistics on augmented fillings.

The following powerful proposition appears in [HHL08, Prop. 4.2.5] which is later used to determine symmetries of expressions obtained as a sum over non-attacking fillings.

Proposition 14 (see [HHL08]). Consider two disjoint lattice diagrams, S and B, and two disjoint subsets Y, Z ⊆ S. Let Ŝ = B ∪ S, and suppose we have a fixed filling B : B → [n] that does not contain the entries i and i + 1. Fix arm and leg values for all boxes u such that u ∈ S and d(u) ∈ Ŝ. For any filling F : S → [n], set F̂ = B ∪F. Then the sum

∑_{F:S→[n] F̂ non-attacking F (Y)∩\{i,i+1\}=∅ F (Z)⊆\{i,i+1\}}x^{F}q^{maj(F̂)}t^{− inv(F̂)} ∏_{\begin{matrix}u∈S, d(u)∈Ŝ \\ F̂(u)=F̂(d(u)) \end{matrix}} (1 − q^{1+leg(u)} t^{1+arm(u)} ) ∏_{u∈S u is in the basement or F̂(u)≠F̂(d(u))} (1 − t)

is symmetric in x_{i} and x_{i+1} .

The fixed filling B plays the role of a basement and the sets Z and Y are subsets of S that specify which boxes should and should not contain i and i + 1.

4.4. Permuting the basement. The following two properties in Proposition 15 are essentially inverses of each other — we can use θ̃_{i} to decrease the length of the basement and π̃_{i} to increase the length. The result in the following proposition appears without proof in [Fer11], referencing a private communication with J. Haglund. We provide a full proof below.

Proposition 15 (Basement permuting operators). Let α be a composition and let σ be a permutation. Furthermore, let γ_{i} be the length of the row with basement label i, that is, γ_{i} = α_{σ_{i}^{−1}} .

If ℓ(σs_{i}) < ℓ(σ), then

θ̃_{i}E_{α}^{σ}(x; q, t) = E_{α}^{σs_{i}} (x; q, t) × \{ \begin{matrix}t, if γ_{i} ≤ γ_{i+1} , \\ 1, otherwise. \end{matrix}  (10)

Similarly, if ℓ(σs_{i}) > ℓ(σ), then

π̃_{i}E_{α}^{σ}(x; q, t) = E_{α}^{σs_{i}} (x; q, t) × \{ \begin{matrix}t, if γ_{i} < γ_{i+1} , \\ 1, otherwise. \end{matrix}  (11)

Proof. Using Lemma 12, to prove (10), it is enough to show two symmetries in x_{i} and x_{i+1} . There are two cases to consider.

Case γ_{i} ≤ γ_{i+1} : It suffices to show that

E_{α}^{σ}(x; q, t) + t · E_{α}^{σs_{i}} (x; q, t) and tx_{i+1} · E_{α}^{σ}(x; q, t) + tx_{i} · E_{α}^{σs_{i}} (x; q, t)

(12)

are symmetric in x_{i} and x_{i+1} . We show these symmetries using Proposition 14. For the first symmetry, let Ŝ be the augmented diagram with shape α and let B be all boxes in the basement σ not containing {i, i + 1}. Now consider non-attacking fillings σ̂ : Ŝ → [n]. Each such filling has i and i + 1 appearing in the basement column exactly once. Thus, every such filling σ̂ corresponds to either a filling for E_{α}^{σ} or E_{α}^{σs_{i}} . However, there is an extra inversion of type A in the leftmost diagram in (13), compared to the diagram on the right, given by the boxes marked {i, i + 1, ∞}.

∞ i+1  ⋯; ⋮ ; i  and ^{∞ i  ⋯} ; ⋮ ; i+1  (13)

It follows that the sum over non-attacking fillings with basement σ in (13) is, up to a constant, t^{−1} E_{α}^{σ}, and the sum over fillings with basement σs_{i} is, up to the same constant, E_{α}^{σs_{i}} . Proposition 14 states that the total sum t^{−1} E_{α}^{σ} + E_{α}^{σs_{i}} is symmetric in x_{i} and x_{i+1} which implies the first symmetry in (12).

To show the second symmetry, let Ŝ be the augmented diagram of shape α, with an additional box u in row σ_{i+1}^{−1} and column −1. The set B is again all boxes in the basement σ except the boxes containing {i, i+1}. Let Z = {u} in Proposition 14, such that the box u may only contain {i, i + 1}. The non-attacking condition then forces the fillings of Ŝ to be of the forms in (14) — ignoring u, these fillings produce E_{α}^{σ} and E_{α}^{σs_{i}} .

i+1 i+1  ⋯; ⋮ ; i  and ^{i i  ⋯} ; ⋮ ; i+1  (14)

There are no extra inversions in this case, so Proposition 14 implies that x_{i+1} E_{α}^{σ} + x_{i}E_{α}^{σs_{i}} is symmetric in x_{i} and x_{i+1} , giving the second requirement in (12).

Case γ_{i} > γ_{i+1} : Using the exact same strategy as in the previous case, we must show that

E_{α}^{σ}(x; q, t)+E_{α}^{σs_{i}} (x; q, t) and tx_{i+1} ·E_{α}^{σ}(x; q, t)+x_{i}·E_{α}^{σs_{i}} (x; q, t)(15)

are symmetric in x_{i} and x_{i+1} . As before, fix the basement entries which are not in {i, i + 1} and consider fillings of the two types in (16).

∞_{2} i+1 ; ⋮ ; ^{∞_{1} i  ⋯}  and ^{∞_{2} i} ; ⋮ ; ^{∞_{1} i+1  ⋯}  (16)

In this case, there is no extra inversion in either of these (we can imagine that the boxes marked ∞_{1} and ∞_{2} are greater than all other boxes, and ∞_{2} > ∞_{1}) so the first symmetry in (15) is straightforward. Finally, we add an extra box u ∈ Z, filled with either i or i + 1. The fillings in (17) then give E_{α}^{σ}(x; q, t) and E_{α}^{σs_{i}} (x; q, t).

i+1 i+1 ; ⋮ ; ^{∞ i  ⋯}  and ^{i i} ; ⋮ ; ^{∞ i+1  ⋯}  (17)

We note that the second filling in (17) has an extra inversion of type B, given by the entries {i, i + 1, ∞} with i and ∞ in the leftmost column. Hence, x_{i+1} · E_{α}^{σ}(x; q, t) + t^{−1} x_{i} · E_{α}^{σs_{i}} (x; q, t) is symmetric in x_{i} and x_{i+1} which implies the last symmetry in (15).

Relation (11) now follows from the first by applying π̃_{i} on both sides of (10) and use the fact that π̃_{i} θ̃_{i}(f) = tf for all f. □

Repeated application of these operators gives us the following corollary.

Corollary 16. Let σ and α be given, and define twinv_{θ}(α, σ) and twinv_{π}(α, σ) as

twinv_{θ}(α, σ) = |{(i, j) : i < j, α_{i} ≤ α_{j} and σ_{i} < σ_{j}}| ,
twinv_{π}(α, σ) = |{(i, j) : i < j, α_{i} < α_{j} and σ_{i} < σ_{j}}| .

Then

θ̃_{σ}E_{α}^{ω_{0}} (x; q, t)= t^{twinv_{θ}(ω_{0}α,σ)} E_{α}^{ω_{0}σ} (x; q, t),  (18)
π̃_{σ}E_{α}^{id}(x; q, t)= t^{twinv_{π} (α,σ)} E_{α}^{σ}(x; q, t).  (19)

Proof. The proof is more or less immediate via induction on ℓ(σ) by unraveling (10) and (11). □

4.5. Permuting the shape. We now prove a more general version of an identity in [HHL08], where the case σ = ω_{0} is proved.

Proposition 17 (Shape permuting operators). If α_{j} < α_{j+1} , σ_{j} = i + 1 and σ_{j+1} = i for some i, j, then

E_{s_{j} α}^{σ} (x; q, t) = ( θ̃_{i} + \frac{1 − t}{1 − q^{1+leg(u)} t^{arm(u)}} ) E_{α}^{σ}(x; q, t),  (20)

where u = (j + 1, α_{j} + 1) in the diagram of shape α.

Proof. The case σ = ω_{0} is our base case in an inductive argument on different basements. It is enough to show the following equalities (for fixed α):

(1) Equation (20) holds for the triple (σ, i, j) if and only if it holds for (σs_{k}, i, j) if k ≠ {i − 1, i, i + 1}.

(2) Equation (20) holds for (σ, i, j) with (σ_{j−1} , σ_{j}, σ_{j+1} ) = (i−1, i+ 1, i) if and only if it holds for (σs_{i−1} s_{i}, i − 1, j).

(3) Equation (20) holds for (σ, i, j), where (σ_{j}, σ_{j+1} , σ_{j+2} ) = (i + 1, i, i − 1) if and only if it holds for (σs_{i−1} s_{i}, i − 1, j).

The first equality ensures that we are free to permute the basement labels not involving i and i + 1. The last two equalities allow us to increase (decrease) the basement labels on rows j, j+1 by one, provided that there is also a third row where the label is decreased (increased) by two. It is easy to see that, with these operations, one can reach any configuration (σ, i, j) satisfying the conditions in Proposition 17 from the base case.

Consider the statement

E_{s_{j} α}^{σ} (x; q, t) = ( θ̃_{i} + C_{u}) E_{α}^{σ}(x; q, t), C_{u} = \frac{1 − t}{1 − q^{1+leg(u)} t^{arm(u)}} . (21)

Case 1: We want to show that (20) holds for the left configuration in (22) if and only if it holds for the right-hand side. Note that (22) only illustrates one of several possible relative positions of k, k + 1 and i.

k ⋯; ⋮ ; ^{i+1 ⋯} ; ^{i ⋯  u ⋯} ; ⋮ ; ^{k+1 ⋯} ⟺ ^{k+1 ⋯} ; ⋮ ; ^{i+1 ⋯} ; ^{i ⋯  u ⋯} ; ⋮ ; ^{k ⋯}  (22)

We apply θ̃_{k} or π̃_{k} depending on if k + 1 appears below or above k, respectively, on both sides of (21). Both θ̃_{k} and π̃_{k} commute with θ̃_{i} since |k − i| ≥ 2 and we obtain

t^{∗} · E_{s_{j} α}^{σs_{k}} (x; q, t) = t^{∗} · ( θ̃_{i} + C_{u}) E_{α}^{σs_{k}} (x; q, t)  (23)

using Proposition 15. The factor t^{∗} depends on the relative lengths of rows with basement label k and k + 1, but it is the same on both sides. Since going from (21) to (23) is invertible, we have the desired equality.

Case 2: To get from the basement σ on the left-hand side in (24) to the basement on the right-hand side, we need to perform s_{i−1} followed by s_{i} as right multiplication.

\begin{matrix}i−1 & ⋯ \\ i+1 & ⋯ \\ i & ⋯ & u & ⋯ \end{matrix} ⟺ \begin{matrix}i+1 & ⋯ \\ i & ⋯ \\ i−1 & ⋯ & u & ⋯ \end{matrix}  (24)

Note that ℓ(σ) < ℓ(σs_{i−1} ) < ℓ(σs_{i−1} s_{i}), so to transform the basement in (21) from σ to σs_{i−1} s_{i}, we need to apply π̃_{i−1} followed by π̃_{i}. We get

(π̃_{i} π̃_{i−1} )E_{s_{j} α}^{σ} (x; q, t) = (π̃_{i} π̃_{i−1} )( θ̃_{i} + C_{u}) E_{α}^{σ}(x; q, t).

The right-hand side is expanded and the square brackets has been rewritten using Lemma 13:

(π̃_{i} π̃_{i−1} )E_{s_{j} α}^{σ} (x; q, t)= [θ̃_{i−1} π̃_{i} π̃_{i−1} ] E_{α}^{σ}(x; q, t) + C_{u} (π̃_{i} π̃_{i−1} )E_{α}^{σ}(x; q, t)
= ( θ̃_{i−1} + C_{u}) (π̃_{i} π̃_{i−1} )E_{α}^{σ}(x; q, t).

The composition π̃_{i} π̃_{i−1} now acts on the basement, giving a factor t^{∗}. Note that this factor is the same on both sides since the comparisons performed on row lengths are the same for α and s_{j}α. The end result is the relation

E_{s_{j} α}^{σs_{i−1} s_{i}} (x; q, t) = [θ̃_{i−1} + C_{u}] E_{α}^{σs_{i−1} s_{i}} (x; q, t),

which is what we wish to prove. Since every step is invertible we have the desired equivalence.

Case 3: This case, showing the equivalence in Eq. (25), is performed in the same manner as in the previous case, now using θ̃_{i−1} followed by θ̃_{i} to go from the configuration on the left-hand side to the one on the right-hand side.

\begin{matrix}i+1 & ⋯ \\ i & ⋯ & u & ⋯ \\ i−1 & ⋯ \end{matrix} ⟺ \begin{matrix}i & ⋯ \\ i−1 & ⋯ & u & ⋯ \\ i+1 & ⋯ \end{matrix}  (25)

We apply θ̃_{i}θ̃_{i−1} on both sides of (21) and obtain

( θ̃_{i}θ̃_{i−1} ) E_{s_{j} α}^{σ} (x; q, t) = ( θ̃_{i}θ̃_{i−1} ) ( θ̃_{i} + C_{u}) E_{α}^{σ}(x; q, t).

Expanding the right-hand side, where the braid relation has been used in the square bracket, we get

( θ̃_{i}θ̃_{i−1} ) E_{s_{j} α}^{σ} (x; q, t)= [θ̃_{i−1} θ̃_{i}θ̃_{i−1} ] E_{α}^{σ}(x; q, t) + C_{u} ( θ̃_{i}θ̃_{i−1} ) E_{α}^{σ}(x; q, t)
= [θ̃_{i−1} + C_{u}] ( θ̃_{i}θ̃_{i−1} ) E_{α}^{σ}(x; q, t).

A similar argument as before gives the equality. □

Note that for any A not depending on x_{i}, we can invert the operator (θ̃_{i} + A). We have

(θ̃_{i} + A)^{−1} = \frac{(A + t − 1 − θ̃_{i})}{(A − 1)(A − t)} ,

which is easy to prove using θ̃_{i}^{2} = (t − 1)θ̃_{i} + t. This fact together with Proposition 17 gives the following proposition.

Proposition 18 (Shape permuting operators II). If α_{j} > α_{j+1} , σ_{j} = i + 1 and σ_{j+1} = i for some i, j, then

E_{s_{j} α}^{σ} (x; q, t) = \frac{(C_{u} + t − 1 − θ̃_{i})E_{α}^{σ}(x; q, t)}{(C_{u} − 1)(C_{u} − t)} ,  (26)

where C_{u} = \frac{1−t}{1−q^{1+leg (u)} t^{1+arm (u)}} and u = (j, α_{j+1} + 1) in the diagram with shape α.

These two identities tell us how the θ̃_{i} act on non-symmetric Macdonald polynomials. The case α_{j} = α_{j+1} is discussed in the next section. The special cases with σ = ω_{0} or σ = id appear in various places, see [MN98, BF97, Mar99].

5. Partial symmetries

The goal of this section is to prove partial symmetries of the permutedbasement Macdonald polynomials. More specifically, if the shape α and basement σ are such that the augmented diagram is of the form

⋮ ; ^{i+1  ⋯} ; ^{i  ⋯} ; ⋮  or  ⋮ ; ^{i  ⋯} ; ^{i+1  ⋯} ; ⋮ ,  (27)

where two adjacent rows have equal lengths and the basement labels differ by 1, then the corresponding Macdonald polynomial E_{α}^{σ}(x; q, t) is symmetric in x_{i} and x_{i+1} . We first show a few implications and then perform induction on the basement and the shape.

In [Mar99], the polynomials E_{α}^{id}(x, q, t) were studied. For example, he derives the analogous formulas for the shape-permuting operators. We need the following statement — now translated to our notation — appearing in [Mar99, Eq. (3.4)].

Lemma 19. Suppose α_{i} = α_{i+1} . Then θ_{i}E_{α}^{id}(x; q, t) = tE_{α}^{id}(x; q, t).

It would be interesting to give a combinatorial proof of this identity using Proposition 14.

Lemma 20. Suppose α_{j} = α_{j+1} and {σ_{j}, σ_{j+1} } = {i, i + 1} for some j, i. Then the following statements are equivalent:

(1) E_{α}^{σ}(x; q, t) is symmetric in x_{i} and x_{i+1} ,

(2) θ̃_{i}E_{α}^{σ}(x; q, t) = tE_{α}^{σ}(x; q, t),

(3) E_{α}^{σs_{i}} (x; q, t) is symmetric in x_{i} and x_{i+1} ,

(4) E_{α}^{σs_{k}} (x; q, t), k ∉ {i − 1, i, i + 1}, is symmetric in x_{i} and x_{i+1} .

Proof. We have (1) ⇔ (2) using Lemma 12, (2) ⇔ (3) using Proposition 15 and Lemma 11, and finally (1) ⇔ (4) by using Lemma 11. □

Lemma 21. Suppose α_{j} = α_{j+1} and {σ_{j}, σ_{j+1} } = {i, i + 1} for some j, i ≥ 2. Then the following statements are equivalent:

(1) E_{α}^{σ}(x; q, t) is symmetric in x_{i} and x_{i+1} ,

(2) E_{α}^{σs_{i−1} s_{i}} (x; q, t) is symmetric in x_{i−1} and x_{i}.

Proof. Proposition 15 implies that either

θ̃_{i}θ̃_{i−1} E_{α}^{σ}(x; q, t) = t^{∗}E_{α}^{σs_{i−1} s_{i}} (x; q, t) or π̃_{i} π̃_{i−1} E_{α}^{σ}(x; q, t) = t^{∗}E_{α}^{σs_{i−1} s_{i}}

depending on whether the basement label i − 1 appears earlier or later than i in σ. By linearity, it suffices to verify the stronger statement that θ̃_{i}θ̃_{i−1} and π̃_{i} π̃_{i−1} map a monomial symmetric in x_{i} and x_{i+1} to a monomial symmetric in x_{i−1} and x_{i}. This calculation is tedious, but can be verified explicitly with the definition of the Demazure–Lusztig operators. Note that it is enough perform the computation with θ̃_{2}θ̃_{1} on the monomial x_{1}^{a}x_{2}^{b}x_{3}^{b}, and this can be done symbolically in a modern computer algebra system such as Mathematica. □

We are now ready to prove the main theorem of this section.

Theorem 22 (Partial symmetry). Suppose α_{j} = α_{j+1} and that {σ_{j}, σ_{j+1} } take the values {i, i + 1} for some j, i. Then E_{α}^{σ}(x; q, t) is symmetric in x_{i} and x_{i+1} .

Proof. The first two items in Lemma 20 together with Lemma 19 imply that the statement is true whenever σ = id. We now argue in the same manner as in the proof of Proposition 17. Lemma 20 together with Lemma 21 imply that we can permute the basement as long as σ_{j} and σ_{j+1} differ by one, and still having the statement in the theorem to be true. In other words, we can reach any basement where {σ_{j}, σ_{j+1} } take the values {i, i + 1}, using the operations on the basement described in the previous two lemmas, all while preserving the symmetry property.

□

Let α ∼ γ denote that α and γ are permutations of the same partition.

Corollary 23. Fix a shape α and let V be the subspace in ℚ(q, t)[x] spanned by {E_{γ}^{ω_{0}} (x; q, t) : γ ∼ α} and let γ ∼ α. Then

θ̃_{i}E_{γ}^{ω_{0}} (x; q, t) ∈ V, π̃_{i}E_{γ}^{ω_{0}} (x; q, t) ∈ V and E_{γ}^{σ}(x; q, t) ∈ V, (28)

for any i and σ.

Proof. It is straightforward to show that θ̃_{i}E_{γ}^{ω_{0}} (x; q, t) ∈ V; whenever the rows with basement label i and i + 1 have different lengths the statement follows from Proposition 17 or Proposition 18. In the case of equal lengths, it follows from Theorem 22, since then θ̃_{i}E_{γ}^{ω_{0}} (x; q, t) = tE_{γ}^{ω_{0}} (x; q, t). This implies that the θ̃_{i} preserve V. That π̃_{i}E_{γ}^{ω_{0}} (x; q, t) ∈ V now follows from expressing π̃_{i} in terms of θ̃_{i} as in Eq. (8). Finally, the last statement is a consequence of Proposition 15 using the fact that the basement-permuting operators preserve V. □

6. Properties of permuted basement t-atoms

We define the Demazure t-atoms as A_{α}(x; t) = E_{α}^{id}(x; 0, t) and the permuted-basement Demazure t-atoms as A_{α}^{σ}(x; t) = E_{α}^{σ}(x; 0, t). Similarly, the t-key polynomials are defined as K_{α}(x; t) = E_{α}^{ω_{0}} (x; 0, t). The Demazure t-atoms were previously introduced in [HLMvW11] and they have remarkable similarities with Hall–Littlewood polynomials.

Remark 24. Note that the permuted-basement Demazure atoms we obtain from A_{α}^{σ}(x; 0) do not agree in general with the extension of Demazure atoms introduced in [HMR12, TR13]. The authors of these papers impose an extra restriction (called the B-increasing condition) on the underlying fillings which they call permuted basement fillings (PBF). One underlying reason for imposing this extra condition is to be able to do an analogue of RSK on these fillings. The connection with Demazure operators is unfortunately lost under this restriction.

Lemma 25. Suppose α_{j} < α_{j+1} . If σ_{j} = i + 1 and σ_{j+1} = i for some i, j, then

π̃_{i}A_{α}^{σ}(x; t) = A_{s_{j} α}^{σ} (x; t).  (29)

Similarly, if σ_{j} = i and σ_{j+1} = i + 1 for some i, j, then

π̃_{i}A_{α}^{σ}(x; t) = tA_{s_{j} α}^{σ} (x; t).  (30)

Proof. To obtain (29), put q = 0 in Proposition 17 and use the fact that θ̃_{i}+ (1 − t) = π̃_{i}. The second equation is a consequence of the first as follows. Start with σ_{j} = i + 1 and σ_{j+1} = i and apply θ̃_{i} on both sides of (29):

θ̃_{i}π̃_{i}A_{α}^{σ}(x; t) = θ̃_{i}A_{s_{j} α}^{σ} (x; t).

The right-hand side is rewritten using (10). In the left-hand side we use the same identity after using the fact that π̃_{i} and θ̃_{i} commute:

π̃_{i}A_{α}^{σs_{i}} (x; t) = tA_{s_{j} α}^{σs_{i}} (x; t).

This now implies (30). □

Corollary 26. The operators θ̃_{i} and π̃_{i} act on the shape of the Demazure t-atom and t-key in the following manner:

θ̃_{i}A_{α}(x; t) = A_{s_{i}α} (x; t) if α_{i} > α_{i+1} ,  (31)
π̃_{i}K_{α}(x; t) = K_{s_{i}α} (x; t) if α_{i} < α_{i+1} .  (32)

Proof. The first statement is a direct consequence of applying θ̃_{i} on both sides of (30) followed by using θ_{i} π̃_{i} = t and substituting α with s_{i}α. The second statement is (29) with σ = ω_{0}. □

The following two identities generalize a result which appears in [Mas09, Prop. 6.1]. The conclusion is that any t-key and Demazure t-atom can be obtained from a permuted-basement t-atom with a partition or reverse partition shape, respectively.

Proposition 27. Let σ be a fixed permutation, let λ be a partition and let μ̄ be the reverse of a partition μ. Then

K_{σλ}(x; t) = A_{λ}^{ω_{0}σ} (x; t)  and  A_{σμ̄}(x; t) = Aσ ; μ̄(x; t),

where σ is the shortest permutation taking λ to σλ, and μ̄ to σμ̄, respectively.

Proof. This follows from Corollary 16 and Proposition 15 using induction on the length of σ. We note that the identities are clearly true when σ = id. The first equation is now proved as follows. We apply π̃_{i} on both sides, where identity (29) is used on the left-hand side and (11) is used on the right-hand side. A similar reasoning proves the second identity. The condition on σ being the shortest permutation ensures that only parts of α with different lengths are interchanged. □

Finally, we note that Corollary 26 with t = 0 implies (under the same conditions as in Proposition 27) that π_{σ}x^{λ} = K_{σλ̄}(x) and θ_{σ}x^{μ} = A_{σμ} (x). This is the standard definition of key polynomials and the Demazure atoms, see [LS90, RS95, Mas09].

We are now ready to prove the following proposition.

Proposition 28. Given α and σ, there is a sequence ρ̃_{i_{1}} ⋯ ρ̃_{i_{ℓ}} such that

A_{α}^{σ}(x; t) = ρ̃_{i_{1}} ⋯ ρ̃_{i_{ℓ}}x^{λ},  (33)

where λ is the partition with the parts of α in decreasing order and each ρ̃_{i_{j}} is one of θ̃_{i} or π̃_{i}.

Proof. The case α = λ and σ = id is clear since

A_{λ}^{id}(x; t) = x^{λ},  (34)

which follows from the triangularity property. Using (31) repeatedly on both sides of (34), we have

A_{α}^{id}(x; t) = θ̃_{τ}x^{λ},  (35)

where τ is the shortest permutation such that α = τλ. Now apply a sequence of π̃_{i} on both sides in order to transform the basement into σ while fixing the shape, using the second identity in Proposition 15. However, this will in general introduce a power of t, corresponding to how many times we interchange basement labels of rows where the top row is shorter than the bottom row. Using Corollary 16, we obtain

t^{twinv_{π} (α,σ)} A_{α}^{σ}(x; t) = π̃_{σ} θ̃_{τ}x^{λ}.  (36)

Note now that the word π̃_{σ} θ̃_{τ} is not reduced, meaning that we can use the non-mixed brad relations as well as the mixed braid relations in Lemma 13 together with the cancellation π̃_{i} θ̃_{i} = t.

Since the left-hand side is a multiple of t^{twinv_{π} (α,σ)} , we must have at least this number of cancellations on the right-hand side. On the other hand, after these cancellations we have

A_{α}^{σ}(x; t) = t^{− twinv_{π} (α,σ)} π̃_{σ} θ̃_{τ}x^{λ},  (37)

where the left-hand side is a non-zero polynomial when t = 0. Therefore, the number of cancellations must be equal to t^{twinv_{π} (α,σ)} , giving the desired form. □

For further results on Demazure t-atoms, see [AS19].

7. Polynomial expansions

As before, let γ ∼ μ indicate that the parts of γ is a permutation of the parts of μ, where γ and μ are compositions with the same number of parts.

Theorem 29. The symmetric Macdonald polynomials P_{λ}(x; q, t), indexed by partitions λ, expand in the permuted basement Macdonald polynomials as

P_{λ}(x; q, t) = ∏_{u∈λ} (1 − q^{1+leg(u)} t^{arm(u)}) ∑_{γ∼λ} \frac{t^{twinv_{π} (γ,σ)}E_{γ}^{σ}(x; q, t)}{∏ _{v∈γ} (1 − q^{1+leg(v)} t^{arm(v)})} .

(38)

Proof. In [HHL08, Prop. 5.3.1], the following expansion is obtained:

P_{λ}(x; q, t) = ∏_{u∈λ} (1 − q^{1+leg(u)} t^{arm(u)}) ∑_{γ∼λ} \frac{E_{γ}^{id}(x; q, t)}{∏ _{v∈γ} (1 − q^{1+leg(v)} t^{arm(v)})} .

We apply π̃_{σ} on both sides. The resulting expression on the right-hand side follows from Corollary 16, and Lemma 11 implies that π̃_{σ} acts as the identity on the symmetric polynomial on the left-hand side. □

As a corollary, we get the following positive expansion of Hall–Littlewood polynomials in permuted-basement t-atoms, by letting q = 0 in (38). This extends a result in [HLMvW11].

Corollary 30 (Hall–Littlewood in permuted-basement t-atoms). The Hall–Littlewood polynomials P_{λ}(x; t) expand positively in permuted-basement t-atoms:

P_{λ}(x; t) = ∑_{γ∼λ} t^{twinv_{π} (γ,σ)}A_{γ}^{σ}(x; t).  (39)

Recall the classical expansion of Schur polynomials in terms of Hall– Littlewood polynomials,

s_{λ}(x) = ∑_{μ⊢|λ|} K_{λμ} (t)P_{μ}(x; t),

where K_{λμ} (t) ∈ ℕ[t] are the Kostka–Foulkes polynomials. These are known to be polynomials with non-negative integer coefficients and have a combinatorial interpretation, see [LS78]. Corollary 30 implies the following positive expansion.

Corollary 31 (Schur in permuted-basement t-atoms). If λ is a partition, then

s_{λ}(x) = ∑_{γ⊢|λ|} t^{twinv_{π} (γ,σ)}K_{λγ}(t)A_{γ}^{σ}(x; t),  (40)

where the sum now is taken over compositions of |λ| and K_{λγ}(t) = K_{λμ} (t) if γ ∼ μ.

A combinatorial proof of this identity in the case t = 0 appears in [Mas08] in the case σ = id.

To give an overview over positive expansions of polynomials in other bases, we present an overview in Fig. 1. The proofs of these expansions can be found in the references.

Quasisymmetric Schur S_{α}(x) Demazure atom A_{α}(x) Key K_{α}(x) General atom A_{α}^{σ}(x) General t-atom A_{α}^{σ}(x; t) Elementary e_{λ}(x) Schur s_{λ}(x) Schubert, 𝔖_{w}(x) Hall–Littlewood, P_{λ}(x; t) Gessel fundamental F_{α}(x)

Figure 1. This graph shows various families of polynomials. The arrows indicate the relation expands positively in which means that the coefficients are polynomials with non-negative coefficients. A proof of the dashed edge can be found in [Pun16] and a generalization of the dotted edge is given in [AS19].

Acknowledgement. The author would like to thank Jim Haglund for suggesting the topic and for providing insightful comments. Many thanks goes to Anna Pun for interesting discussions regarding permutedbasement atoms. The author is also also grateful for the warm hospitality at University of Pennsylvania, where this research was conducted. This work has been funded by the Knut and Alice Wallenberg Foundation (2013.03.07).

Appendix: Examples of permuted-basement Macdonald polynomials

Here are some explicitly computed non-symmetric Macdonald polynomials with a permuted basement.

E_{110}^{321}(x; q, t)= \frac{(1 − t)^{2}x_{1}x_{2}}{(1 − qt) (1 − qt^{2})} + \frac{t(1 − t)x_{1}x_{2}}{1 − qt^{2}} + \frac{(1 − t)x_{1}x_{3}}{1 − qt} + x_{2}x_{3} (♡)

E_{110}^{312}(x; q, t)= \frac{qt(1 − t)^{2}x_{1}x_{2}}{(1 − qt) (1 − qt^{2})} + \frac{(1 − t)x_{1}x_{2}}{1 − qt^{2}} + \frac{q(1 − t)x_{2}x_{3}}{1 − qt} + x_{1}x_{3}(♢)

E_{110}^{213}(x; q, t)= \frac{q(1 − t)^{2}x_{1}x_{3}}{(1 − qt) (1 − qt^{2})} + \frac{qt(1 − t)x_{1}x_{3}}{1 − qt^{2}} + \frac{q(1 − t)x_{2}x_{3}}{1 − qt} + x_{1}x_{2}(♠)

E_{110}^{231}(x; q, t)= \frac{qt(1 − t)^{2}x_{1}x_{3}}{(1 − qt) (1 − qt^{2})} + \frac{(1 − t)x_{1}x_{3}}{1 − qt^{2}} + \frac{(1 − t)x_{1}x_{2}}{1 − qt} + x_{2}x_{3} (♡)

E_{110}^{132}(x; q, t)= \frac{q(1 − t)^{2}x_{2}x_{3}}{(1 − qt) (1 − qt^{2})} + \frac{qt(1 − t)x_{2}x_{3}}{1 − qt^{2}} + \frac{(1 − t)x_{1}x_{2}}{1 − qt} + x_{1}x_{3}(♢)

E_{110}^{123}(x; q, t)= \frac{q^{2}t(1 − t)^{2}x_{2}x_{3}}{(1 − qt) (1 − qt^{2})} + \frac{q(1 − t)x_{2}x_{3}}{1 − qt^{2}} + \frac{q(1 − t)x_{1}x_{3}}{1 − qt} + x_{1}x_{2}(♠)

Note that the indicated pairs of polynomials coincide when simplified. This is a consequence of Theorem 22.

Here are the Macdonald polynomials associated with a slightly larger shape:

E_{012}^{321} = \frac{q(1 − t)x_{2}x_{3}x_{1}}{1 − qt^{2}} + x_{2}x_{1}^{2}, E_{012}^{312} = \frac{q(1 − t)tx_{1}x_{3}x_{2}}{1 − qt^{2}} + x_{1}x_{2}^{2}

E_{012}^{213} = \frac{(1 − t)x_{1}x_{2}x_{3}}{1 − qt^{2}} + x_{1}x_{3}^{2}, E_{012}^{231} = \frac{q(1 − t)tx_{2}x_{3}x_{1}}{1 − qt^{2}} + x_{3}x_{1}^{2}

E_{012}^{132} = \frac{(1 − t)x_{1}x_{3}x_{2}}{1 − qt^{2}} + x_{3}x_{2}^{2}, E_{012}^{123} = \frac{(1 − t)tx_{1}x_{2}x_{3}}{1 − qt^{2}} + x_{2}x_{3}^{2}

References

[AS17] Per Alexandersson and Mehtaab Sawhney, A major-index preserving map on fillings, Electron. J. Combin. 24 (2017), no. 4, 1–30.

[AS19] , Properties of non-symmetric Macdonald polynomials at q = 1 and q = 0, Ann. Combin. 23 (2019), no. 2, 219–239.

[BF97] Timothy H. Baker and Peter J. Forrester, A q-analogue of the type A Dunkl operator and integral kernel, Internat. Math. Res. Notices (1997), no. 12, 667–686.

[Che95] Ivan Cherednik, Double affine Hecke algebras and Macdonald’s conjectures, Ann. Math. 141 (1995), no. 1, 191–216.

[Che12] , Jones polynomials of torus knots via DAHA, Internat. Math. Res. Notices 2013 (2012), no. 23, 5366–5425.

[Deh08] Patrick Dehornoy, Efficient solutions to the braid isotopy problem, Discrete Appl. Math. 156 (2008), no. 16, 3091–3112.

[Fer11] Jeffrey Paul Ferreira, Row-strict quasisymmetric Schur functions, characterizations of Demazure atoms, and permuted basement nonsymmetric Macdonald polynomials, Ph.D. thesis, University of California at Davis, 2011.

[FM15] Evgeny Feigin and Ievgen Makedonskyi, Nonsymmetric Macdonald polynomials and PBW filtration: Towards the proof of the Cherednik– Orr conjecture, J. Combin. Theory, Ser. A 135 (2015), 60–84.

[FM17] , Generalized Weyl modules, alcove paths and Macdonald polynomials, Selecta Math. 23 (2017), no. 4, 2863–2897.

[FMO18] Evgeny Feigin, Ievgen Makedonskyi, and Daniel Orr, Generalized Weyl modules and nonsymmetric q-Whittaker functions, Adv. Math. 330 (2018), 997–1033.

[Hag07] James Haglund, The q, t-Catalan numbers and the space of diagonal harmonics, University Lecture Series, vol. 41, Amer. Math. Soc., R.I., 2008.

[HHL08] James Haglund, Mark Haiman, and Nick Loehr, A combinatorial formula for nonsymmetric Macdonald polynomials, Amer. J. Math. 130 (2008), no. 2, 359–383.

[HL16] Patricia Hersh and Cristian Lenart, From the weak Bruhat order to crystal posets, Math. Zeitschr. 286 (2016), no. 3–4, 1435–1464.

[HLMvW11] James Haglund, Kurt W. Luoto, Sarah K. Mason, and Stephanie van Willigenburg, Quasisymmetric Schur functions, J. Combin. Theory, Ser. A 118 (2011), no. 2, 463–490.

[HMR12] James Haglund, Sarah K. Mason, and Jeffrey B. Remmel, Properties of the nonsymmetric Robinson–Schensted–Knuth algorithm, J. Algebr. Combin. 38 (2012), no. 2, 285–327.

[Kno97] Friedrich Knop, Integrality of two variable Kostka functions, J. reine angew. Math. 482 (1997), 177–190.

[LLT97] Alain Lascoux, Bernard Leclerc, and Jean-Yves Thibon, Ribbon tableaux, Hall–Littlewood functions, quantum affine algebras and unipotent varieties, J. Math. Phys. 38 (1997), 1041–1068.

[LS78] Alain Lascoux and Marcel-Paul Schützenberger, Sur une conjecture de H. O. Foulkes, C. R. Acad. Sci. Paris Sér. A-B 286 (1978), no. 7, A323–A324.

[LS90] , Keys & standard bases, Invariant theory and tableaux (Minneapolis, MN, 1988), IMA Vol. Math. Appl., vol. 19, Springer, New York, 1990, pp. 125–144.

[Mac95] Ian Grant Macdonald, Symmetric functions and Hall polynomials, second ed., Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York, 1995, With contributions by A. Zelevinsky, Oxford Science Publications.

[Mar99] Dan Marshall, Symmetric and nonsymmetric Macdonald polynomials, Ann. Combin. 3 (1999), no. 2, 385–415.

[Mas08] Sarah K. Mason, A decomposition of Schur functions and an analogue of the Robinson-Schensted-Knuth algorithm, Sém. Lothar. Combin. 57 (2008), Art. B57e, 24 pp.

[Mas09] , An explicit construction of type A Demazure atoms, J. Algebr. Combin. 29 (2009), no. 3, 295–313.

[MN98] Katsuhisa Mimachi and Masatoshi Noumi, A reproducing kernel for nonsymmetric Macdonald polynomials, Duke Math. J. 91 (1998), no. 3, 621–634.

[Pun16] Anna Pun, On decomposition of the product of Demazure atoms and Demazure characters, Ph.D. thesis, University of Pennsylvania, PA, USA, November 2016, pp. 1–127.

[RS95] Victor Reiner and Mark Shimozono, Key polynomials and a flagged Littlewood–Richardson rule, J. Combin. Theory, Ser. A 70 (1995), no. 1, 107–143.

[RY11] Arun Ram and Martha Yip, A combinatorial formula for Macdonald polynomials, Adv. Math. 226 (2011), no. 1, 309–331.

[Sah96] Siddhartha Sahi, Interpolation, integrality, and a generalization of Macdonald’s polynomials, Internat. Math. Res. Notices 1996 (1996), no. 10, 457.

[TR13] Janine LoBue Tiefenbruck and Jeffrey B. Remmel, A Murnaghan– Nakayama rule for generalized Demazure atoms, 25th International Conference on Formal Power Series and Algebraic Combinatorics (Paris, France), Discrete Mathematics and Theoretical Computer Science, 2013, pp. 969–980.

28 PER ALEXANDERSSON

Dept. of Mathematics, Royal Institute of Technology, SE-100 44 Stockholm, Sweden

E-mail address: per.w.alexandersson@gmail.com