Séminaire Lotharingien de Combinatoire 54 (2006), Article B54d

IDEALS AND QUOTIENTS OF B-QUASISYMMETRIC POLYNOMIALS

J.-C. AVAL

Dédié à Xavier Viennot

Abstract. The space QSym_{n}(B) of B-quasisymmetric polynomials in 2 sets of n variables was recently studied by Baumann and Hohlweg [Trans. Amer. Math. Soc., to appear]. The aim of this work is a study of the ideal ⟨QSym_{n}(B)^{+}⟩ generated by B-quasisymmetric polynomials without constant term. In the case of the space QSym_{n} of quasisymmetric polynomials in 1 set of n variables, Aval, Bergeron and Bergeron [Proc. Amer. Math. Soc. 131 (2003), 1053–1062; Adv. in Math. 181 (2004), 353–367] proved that the dimension of the quotient of the space of polynomials by the ideal ⟨QSym_{n}^{+}⟩ is given by Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n}. In the case of B-quasisymmetric polynomials, our main result is that the dimension of the analogous quotient is equal to \frac{1}{2n+1} \binom{3n}{n}, the numbers of ternary trees with n nodes. The construction of a Gröbner basis for the ideal, as well as of a linear basis for the quotient are interpreted by a bijection with lattice paths. These results are finally extended to p sets of variables, and the dimension is in this case \frac{1}{pn+1} \binom{(p+1)n}{n}, the number of p-ary trees with n nodes.

Résumé. L’espace QSym_{n}(B) des polynômes B-quasisymétriques en deux ensembles de n variables a été récemment étudié par Baumann et Hohlweg [Trans. Amer. Math. Soc., à paraître]. Nous considérons ici l’idéal ⟨QSym_{n}(B)^{+}⟩ engendré par les polynômes B-quasisymétriques sans terme constant. Dans le cas de l’espace QSym_{n} des polynômes quasisymétriques en 1 ensemble de n variables, Aval, Bergeron et Bergeron [Proc. Amer. Math. Soc. 131 (2003), 1053–1062; Adv. in Math. 181 (2004), 353–367] ont montré que la dimension du quotient de l’espace des polynômes par l’idéal ⟨QSym_{n}^{+}⟩ est donnée par les nombres de Catalan C_{n} = \frac{1}{n+1} \binom{2n}{n}. Dans le cas des polynômes B-quasisymétriques, notre principal résultat est que la dimension du quotient analogue est ici \frac{1}{2n+1} \binom{3n}{n}, à savoir le nombre d’arbres ternaires à n nœuds. Nous construisons une base de Gröbner pour l’idéal, de même qu’une base du quotient, toutes deux explicites et en bijection avec des chemins. Nous étendons enfin ces résultats à p ensembles de variables, et montrons que dans ce cas la dimension est \frac{1}{pn+1} \binom{(p+1)n}{n}, le nombre d’arbres p-aires à n nœuds.

1. Introduction

To start with, we recall (a part of) the story of the study of ideals and quotients related to symmetric or quasisymmetric polynomials. The root of this work is a result of Artin [1]. Let us consider the set of variables X_{n} = x_{1}, x_{2}, …, x_{n}. The space of

This research has been supported by EC’s IHRP Programme, within the Research Training Network “Algebraic Combinatorics in Europe,” grant HPRN-CT-2001-00272.

polynomials in the variables X_{n} with rational coefficients is denoted by ℚ[X_{n}]. The subspace of symmetric polynomials is denoted by Sym_{n}. Symmetric polynomials may be seen (cf. [19]) as invariants of the symmetric group S_{n} under the action defined as follows: for σ ∈ S_{n} anf P ∈ ℚ[X_{n}],

σ · P (X_{n}) = P (x_{σ(1)}, x_{σ(2)}, …, x_{σ(n)}).

Let V be a subset of the polynomial ring. We denote by ⟨V^{+}⟩ the ideal generated by elements of a V with no constant term. Artin’s result is given by:

(1.1)  dim ℚ[X_{n}]/⟨Sym_{n}^{+}⟩ = n! .

Another, more recent, part of the story deals with quasisymmetric polynomials. The space QSym_{n} ⊂ ℚ[X_{n}] of quasisymmetric polynomials was introduced by Gessel [16] as generating functions for Stanley’s P -partitions [24]. This is the starting point of many recent works in several areas of combinatorics [10, 20, 15, 25]. Quasisymmetric polynomials may also be seen as S_{n}-invariants under Hivert’s quasisymmetrizing action ([18]), defined as follows.

Let I = {i_{1}, …, i_{k}} be a subset of {1, …, n} and a = (a_{1}, …, a_{k}) a sequence of positive (> 0) integers, of the same cardinality. We define X_{I}^{a} = x_{i_{1}}^{a_{1}} ⋯ x_{i_{k}}^{a_{k}}, where the elements of I are listed in increasing order. Hivert’s action is then defined on monomials by

σ ∗ X_{I}^{a} = X_{σ(I)}^{a}

where σ(I) is the set {σ(i_{1}), …, σ(i_{k})} arranged in increasing order.

In [2, 3], Aval et al. study the problem analogous to Artin’s work in the case of quasisymmetric polynomials. Their main result is that the dimension of the quotient is given by Catalan numbers:

(1.2)  dim ℚ[X_{n}]/⟨QSym_{n}^{+}⟩ = C_{n} = \frac{1}{n + 1}\binom{2n}{n}.

An interesting axis of research is the extension of these results to 2 (or p ≥ 2) sets of variables. In the case of two sets of variables, let A_{n} = A_{n}^{2} denote the alphabet

A_{n} = x_{1}, y_{1}, x_{2}, y_{2}, …, x_{n}, y_{n}.

The diagonal action of S_{n} on ℚ[A_{n}] is defined as simultaneous permutation of variables x’s and y’s:

σ · P (A_{n}) = P (x_{σ(1)}, y_{σ(1)}, …, x_{σ(n)}, y_{σ(n)}).

Invariants associated to this action are called diagonally symmetric polynomials. Their set is denoted by DSym_{n}.The diagonal coinvariant space ℚ[A_{n}]/⟨DSym_{n}^{+}⟩ has been studied extensively in the last 15 years by several authors [8, 9, 13, 14, 17]. A great achievment in this area is Haiman’s proof of the following equality (cf. [17]):

dim ℚ[A_{n}]/⟨DSym_{n}^{+}⟩ = (n + 1)^{n−1} .

In [5], the space DQSym_{n} of diagonally quasisymmetric polynomials is defined as the invariant space of the diagonal extension of Hivert’s action. This space was originally introduced by Poirier [22], and, with generalizations, has been recently studied in [21] and [7].

IDEALS AND QUOTIENTS OF B-QUASISYMMETRIC POLYNOMIALS 3

The coinvariant space ℚ[A_{n}]/⟨DQSym_{n}^{+}⟩ is investigated in [5], and conjectures are stated. In particular, a conjectural basis for this quotient is presented.

To end this presentation, we introduce the space QSym_{n}(B) of B-quasisymmetric polynomials, which is the focus of this article. This space, whose definition appears implicitly in [22], is studied with more details in [7]. A precise definition will be given in the next section, and we only mention here that QSym_{n}(B) is a subspace (and in fact a subalgebra, cf. [7]) of DQSym_{n}.

We now state the main result of this work, which appears as a generalization of equation (1.2).

Theorem 1.1.

(1.3)  dim ℚ[A_{n}]/⟨QSym_{n}(B)^{+}⟩ = \frac{1}{2n + 1}\binom{3n}{n}.

Observe that in equations (1.2) and (1.3), the dimensions \frac{1}{n+1} \binom{2n}{n} and \frac{1}{2n+1} \binom{3n}{n} are respectively the numbers of binary and ternary trees (cf. [23]). This will be generalized in the last section of this paper.

The content of this paper is divided into 5 main sections. After this introduction, the Section 2 defines the central objects of this work, the B-quasisymmetric polynomials. Sections 3 and 4 are the proof of the Theorem 1.1. In Section 3 is introduced a set G of polynomials, which is proved in Section 4 to be a Gröbner basis for ⟨QSym_{n}(B)^{+}⟩. The Gröbner basis G, as well as the basis of the quotient “deduced” from it, are interpreted in terms of plane paths. Finally, Section 5 gives a generalization of this work for p sets of variables, where the equation analogous to (1.3) replaces \frac{1}{2n+1} \binom{3n}{n} by \frac{1}{pn+1} \binom{(p+1)n}{n}, the number of p-ary trees.

2. QSym(B): definitions and notations

For these definitions, we follow [7], with some minor differences, for the sake of simplicity of the computations we will have to make.

Let ℕ and ℕ̄ denote two occurrrences of the set of nonnegative integers. We shall write ℕ̄ = {¯0, ¯1, ¯2, … } and make no difference between the elements of ℕ and ℕ̄ in any arithmetical expression. We distinguish ℕ and ℕ̄ for the ease of reading.

A bivector is a vector v = (v_{1}, v_{2}, …, v_{2k−1}, v_{2k}) such that the odd entries {v_{2i−1}, i = 1, …, k} are in ℕ, and the even entries {v_{2i}, i = 1, …, k} are in ℕ̄.

A bicomposition is a bivector in which there is no consecutive zeros, i.e., no pattern 0¯0 or ¯00.

The integer k is called the size of v. The weight of v is by definition the couple (|v|_{ℕ}, |v|ℕ̄) = (∑_{i=1}^{k} v_{2i−1}, ∑_{i=1}^{k} v_{2i}). We also set |v| = |v|_{ℕ} + |v|ℕ̄.

For example (1, ¯0, 2, ¯1, 0, ¯2, 3, ¯0) is a bicomposition of size 4, and of weight (6, 3). To make notations lighter, we shall sometimes write bivectors or bicomposition

as words, for example 1¯02¯10¯23¯0 stands for (1, ¯0, 2, ¯1, 0, ¯2, 3, ¯0) (see also the following definition).

The fundamental B-quasisymmetric polynomials, indexed by bicompositions, are defined as follows

F_{c_{1}c_{2}...c_{2k−1}c_{2k}}(A_{n}) = ∑ x_{i_{1}} ⋯ x_{i_{|c|_{ℕ}}} y_{j_{1}} ⋯ y_{j_{|c|ℕ̄}} ∈ ℚ[A_{n}]

where the sum is taken over indices i’s and j’s such that

i_{1} ≤ ⋯ i_{c_{1}} ≤ j_{1} ≤ ⋯ j_{c_{2}} < i_{c_{1}+1} ≤ ⋯ i_{c_{1}+c_{3}} ≤ j_{c_{2}+1} ≤ ⋯ ≤ j_{c_{2}+c_{4}} < i_{c_{1}+c_{3}+1} ≤ ⋯

We give some examples: F_{1¯2} = ∑_{i≤j≤k} x_{i}y_{j}y_{k}, F_{0¯21¯0} = ∑_{i≤j<k} y_{i}y_{j}x_{k}.

It is clear from the definition that the bidegree (i.e., the couple (degree in x, degree in y)) of F_{c} in ℚ[A_{n}] is the weight of c. If the size of c is greater than n, we shall set F_{c}(A_{n}) = 0.

The space of B-quasisymmetric polynomials, denoted by QSym_{n}(B) is the vector subspace of ℚ[A_{n}] generated by the F_{c}(A_{n}), for all bicompositions c.

Let us denote by I_{n}^{2} the ideal ⟨QSym_{n}(B)^{+}⟩ generated by B-quasisymmetric polynomials with zero constant term.

3. Paths and G-set

The aim of this section is to construct a set G of polynomials, which will be proved in the next section to be a Gröbner basis of I_{n}^{2}. These two sections are greatly inspired from [2, 3].

Let v = (v_{1}, v_{2}, …, v_{2k−1}, v_{2k}) be a bivector of size n. We associate to v a path π(v) in the plane ℕ × ℕ, with steps (0,1) or (2,0). We start from (0,0) and add for each entry v_{i} (read from left to right): v_{i} steps (2,0), followed by one step (0,1).

As an example, the path associated to (1, ¯0, 1, ¯2, 0, ¯0, 1, ¯1) is

We have two kinds of path, regarding their position to the diagonal x = y. If a path always remains above this line, we call it a 2-Dyck path, and say that the corresponding vector is 2-Dyck. Conversely, if the path enters the region x < y, we call both the path and the vector transdiagonal. For example, v = (0, ¯0, 1, ¯0, 0, ¯1, 1, ¯0) is 2-Dyck, whereas w = (0, ¯0, 1, ¯1, 1, ¯0, 0, ¯0) is transdiagonal.

A simple but important observation is that a vector v = (v_{1}, v_{2}, …, v_{2k−1}, v_{2k}) is transdiagonal if and only if there exists 1 ≤ l ≤ k such that

(3.1)  v_{1} + v_{2} + ⋯ + v_{2l−1} + v_{2l} ≥ l.

Our next task is to construct a set G of polynomials, mentionned above. From now on, unless otherwise indicated, vectors are of size n. For w a vector of size k < n, w0^{∗} denotes the vector (of size n) obtained by adding the desired number of 0¯0 patterns. We shall define the length ℓ(v) of a vector v as the integer k such that v = v_{1} v_{2} … v_{2k−1} v_{2k} 0^{∗} with v_{2k−1} v_{2k} ≠ 0¯0. In the case of bicompositions, the notions of size and length coincide.

For v a vector (of length n), we denote by A_{n}^{v} the monomial

A_{n}^{v} = x_{1}^{v_{1}}y_{1}^{v_{2}} ⋯ x_{n}^{v_{2n−1}}y_{n}^{v_{2n}}.

To deal with leading terms of polynomials, we will use the lexicographic order induced by the ordering of the variables:

x_{1} > y_{1} > x_{2} > y_{2} > ⋯ > x_{n} > y_{n}.

The lexicographic order is defined on monomials as follows: A_{n}^{v} >_{lex} A_{n}^{w} if and only if the first non-zero entry of v − w (componentwise) is positive.

The set

G = {G_{v}} ⊂ I_{n}^{2}

is indexed by transdiagonal vectors. Let v be a transdiagonal vector.

For v = c0^{∗} with c a non-zero bicomposition of length ≥ n (which implies that v is transdiagonal), we define

G_{v} = F_{c}.

If v cannot be written as c0^{∗}, the polynomial G_{v} is defined recursively. We look at the rightmost occurrence of two consecutive zeros (on the left of a non-zero entry: we do not consider the subword 0^{∗}). Two cases are to be distinguished according to the parity of the position of this pattern:

• if v = w0¯0αβc0^{∗}, with w a vector of size k −1, α ∈ ℕ (by definition non-zero), β ∈ ℕ̄, c a bicomposition, we define

(3.2)  G_{w0¯0αβc0^{∗}} = G_{wαβc0^{∗}} − x_{k} G_{w(α−1)βc0^{∗}};

• if v = wα¯00βc0^{∗}, with w a vector of size k − 1, α ∈ ℕ, β ∈ ℕ̄ (by definition non-zero), c a bicomposition, we define

(3.3)  G_{wα¯00βc0^{∗}} = G_{wαβc0^{∗}} − y_{k} G_{wα(β−1)c0^{∗}}.

We easily check that both terms on the right of (3.2) and (3.3) are indexed by vectors that are transdiagonal as soon as v is transdiagonal. We do it for (3.2) : let us denote v′ = wαβc0^{∗} and v′′ = w(α − 1)βc0^{∗}. Let l be the smallest integer such that (3.1) holds for v. If l ≥ k − 1 then w is transdiagonal thus so are v′ and v′′, and if not:

v′_{1} + v′_{2} + ⋯ + v′_{2l−3} + v′_{2l−2} ≥ l and v′′_{1} + v′′_{2} + ⋯ + v′′_{2l−3} + v′′_{2l−2} ≥ l − 1.

Since v′ and v′′ are of length equal to ℓ(v)−1, this defines any G_{v} for v transdiagonal by induction on ℓ(v).

It is interesting to develop an example, where we take n = 3.

G_{0¯01¯00¯2} = G_{0¯01¯20¯0} − y_{2} G_{0¯01¯10¯0}
= (G_{1¯20¯00¯0} − x_{1} G_{0¯20¯00¯0}) − y_{2} (G_{1¯10¯00¯0} − x_{1} G_{0¯10¯00¯0})
= (F_{1¯2} − x_{1} F_{0¯2}) − y_{2}(F_{1¯1} − x_{1} F_{0¯1})
= (x_{1}y_{1}^{2} + x_{1}y_{1}y_{2} + x_{1}y_{1}y_{3} + x_{1}y_{2}^{2} + x_{1}y_{2}y_{3} + x_{1}y_{3}^{2} + x_{2}y_{2}^{2} + x_{2}y_{2}y_{3}
+x_{2}y_{3}^{2} + x_{3}y_{3}^{2} − x_{1}(y_{1}^{2} + y_{1}y_{2} + y_{1}y_{3} + y_{2}^{2} + y_{2}y_{3} + y_{3}^{2}))
−y_{2}(x_{1}y_{1} + x_{1}y_{2} + x_{1}y_{3} + x_{2}y_{2} + x_{2}y_{3} + x_{3}y_{3} − x_{1}(y_{1} + y_{2} + y_{3}))
= x_{2}y_{3}^{2} − y_{2}x_{3}y_{3} + x_{3}y_{3}^{2}

The monomials of the result are ordered with respect to the lexicographic order and we observe that the leading monomial (denoted LM) of G_{0¯01¯00¯2} is A_{3}^{0¯01¯00¯2}. The following proposition shows that this fact holds in general for the family G.

Proposition 3.1. Let v be a transdiagonal vector. The leading monomial of G_{v} is

(3.4)  LM(G_{v}) = A_{n}^{v}.

The proof of this proposition is, as the definition of the G_{v} polynomials, inductive on the length of v. First observe that the definitions of the F_{c} and of the lexicographic order imply (3.4) when v = c0^{∗} with c a bicomposition. Now Proposition 3.1 is a consequence of the following lemma.

We shall write A_{n\k} = x_{k+1}, y_{k+1}, …, x_{n}, y_{n}.

Lemma 3.2. Let w be a vector of size k, and c a bicomposition, then we have

(3.5)  G_{wc0^{∗}}(A_{n}) = A_{k}^{w}F_{c}(A_{n\k}) + (terms < A_{k}^{w}).

Proof. If w is a bicomposition, then (3.5) is a consequence of the definition of the polynomials F ’s. If not this is readily done by induction on ℓ(w), by using the recursive definition of the G’s.

We suppose that we are in the case of recursion (3.2), i.e., w can be written w = u0¯0αβd with u a bivector of size l, α ∈ ℕ, α > 0, β ∈ ℕ̄, and d a bicomposition.

We first observe that the F polynomials obey to recursive relations. We suppose we have a bicomposition γδg, with γ > 0. Then the definition of the fundamental quasisymmetric polynomials implies:

(3.6)  F_{γδg}(A_{n}) = F_{γδg}(A_{n\1}) + x_{1}F_{(γ−1)δg}(A_{n})

if γδ ≠ 1¯0, and

(3.7)  F_{1¯0g}(A_{n}) = F_{1¯0g}(A_{n\1}) + x_{1}F_{g}(A_{n\1}).

The same kind of equalities holds when γ = 0, with recursive terms multiple of y_{1}.

We now prove (3.5). We have to distinguish two cases. We first suppose αβ ≠ 1¯0, and use (3.2) and (3.6) to write:

G_{u0¯0αβdc0^{∗}} = G_{uαβdc0^{∗}} − x_{l+1} G_{u(α−1)βdc0^{∗}}
= A_{l}^{u} (F_{αβdc}(A_{n\l}) − x_{l+1}F_{(α−1)βdc}(A_{n\l})) + (terms < A_{l}^{u})
= A_{l}^{u} (F_{αβdc}(A_{n\(l+1)})) + (terms < A_{l}^{u})
= A_{n}^{u0¯0αβdc0^{∗}} (F_{c}(A_{n\k})) + (terms < A_{n}^{w}).

Now if αβ = 1¯0, the computation is almost the same:

G_{u0¯01¯0dc0^{∗}} = G_{u1¯0dc0^{∗}} − x_{l+1} G_{u0¯0dc0^{∗}}
= A_{l}^{u} F_{1¯0dc}(A_{n\l}) + (terms < A_{l}^{u}) − x_{l+1}F_{dc}(A_{n\(l+1)}) + (terms < A_{l+1}^{u0¯0})
= A_{l}^{u} F_{αβdc}(A_{n\(l+1)}) + (terms < A_{l}^{u})
= A_{n}^{u0¯01¯0dc0^{∗}} (F_{c}(A_{n\k})) + (terms < A_{n}^{w}).

All this process can be done in the case of recurrence (3.3), and this completes the proof. □

4. Proof of the main theorem

The aim of this section is to prove Theorem 1.1, by showing that the set G constructed in the previous section is a Gröbner basis for I_{n}^{2}. This will be achieved in several steps.

We introduce the notation Q_{n} = ℚ[A_{n}]/I_{n}^{2} and define

B_{n} = {A_{n}^{v} / π(v) is a 2−Dyck path}.

Lemma 4.1. Any polynomial P ∈ ℚ[A_{n}] is in the span of B_{n} modulo I_{n}^{2}. That is

(4.1)  P (A_{n}) ≡ ∑_{A_{n}^{v}∈B_{n}} c_{v}A_{n}^{v}.

Proof. It clearly suffices to show that (4.1) holds for any monomial A_{n}^{v}, with v transdiagonal. We assume that there exists A_{n}^{v} not reducible of the form (4.1) and we choose A_{n}^{w} to be the smallest amongst them with respect to the lexicographic order. Let us write

A_{n}^{w} = LM(G_{w})
= (A_{n}^{w} − G_{w}) + G_{w}
≡ A_{n}^{w} − G_{w} (mod I_{n}^{2}).

All monomials in (A_{n}^{w} − G_{w}) are lexicographically smaller than A_{n}^{w}, thus they are reducible. This contradicts our assumption and completes our proof. □

This lemma implies that B_{n} spans the quotient Q_{n}. We will now prove its linear independence. The next lemma is a crucial step.

Lemma 4.2. If we denote by L[S] the linear span of a set S, then

(4.2)  ℚ[A_{n}] = L[A_{n}^{v}F_{c} / A_{n}^{v} ∈ B_{n}, |c| ≥ 0].

Proof. We have already obtained the following reduction for any monomial A_{n}^{w} in ℚ[A_{n}]:

A_{n}^{w} ≡ ∑_{A_{n}^{v}∈B_{n}} c_{v}A_{n}^{v} (mod I_{n}^{2}),

which is equivalent to

(4.3)  A_{n}^{w} = ∑_{A_{n}^{v}∈B_{n}} c_{v}A_{n}^{v} + ∑_{|c|>0} Q_{c}F_{c}.

We then apply the reduction (4.1) to each monomial of the Q_{c}’s. Now we use the algebra structure of QSym(B) (cf. Proposition 37 of [7]) to reduce products of fundamental B-quasisymmetric polynomials as linear combinations of F_{c}’s. We obtain (4.2) in a finite number of operations since degrees strictly decrease at each operation, because |c| > 0 implies deg Q_{c} < |w|. □

Now we come to the final step in the proof. Before stating this lemma, we introduce some notations, and make an observation.

For v = (v_{1}, v_{2}, v …, v_{2k−1}, v_{2k}) a bivector, let r(v) denote the reverse bivector: r(v) = (v_{2k}, v_{2k−1}, …, v_{2}, v_{1}). In the same way, let R(A_{n}) denote the reverse alphabet of A_{n}: R(A_{n}) = y_{n}, x_{n}, …, y_{1}, x_{1}. Then one has for any bicomposition c:

(4.4)  F_{c}(R(A_{n})) = F_{r(c)}(A_{n}).

Lemma 4.3. The set G is a linear basis of I_{n}^{2}, i.e.

(4.5)  I_{n}^{2} = L[G_{w} / w transdiagonal].

Proof. The proof will be achieved in several steps. The first one is to use Lemma 4.2 and observation (4.4) to obtain:

(4.6)  ℚ[A_{n}] = L[R(A_{n})^{v}F_{c} / A_{n}^{v} ∈ B_{n}, |c| ≥ 0].

We shall denote C_{n} = {R(A_{n})^{v} / A_{n}^{v} ∈ B_{n}}.

Now we reduce the problem, using (4.6) and the algebra structure of QSym_{n}(B) to write:

\begin{aligned}I_{n}^{2} & = ⟨F_{c}, |c| > 0⟩_{ℚ[A_{n}]} = L[A_{n}^{v} F_{c} F_{c′} / A_{n}^{v} ∈ C_{n}, |c| > 0, |c′| ≥ 0] \\ & = L[(A_{n})^{v} F_{c′′}/ A_{n}^{v} ∈ C_{n}, |c′′| > 0]. \end{aligned}

Now we have to prove that for any monomial A_{n}^{v} ∈ C_{n} and any non-zero bicomposition c:

(4.7)  A_{n}^{v} F_{c} ∈ L[G_{w} /w transdiagonal].

Thanks to Lemma reflem1, any monomial of degree at least equal to n is in I_{n}^{2}, thus we can restrict to |v| + |c| < n.

We consider the product

(4.8)  y_{n}^{v_{2n}}(x_{n}^{v_{2n−1}}(⋯ (y_{1}^{v_{2}}(x_{1}^{v_{1}}F_{c})))).

To reduce (4.8), we use the following relations, where w denotes a bivector, d a bicomposition, α and β elements of ℕ and ℕ̄, not simultaneously zero:

(4.9)  x_{k} G_{wαβd0^{∗}} = G_{w(α+1)βd0^{∗}} − G_{w0¯0(α+1)βd0^{∗}}

or

(4.10)  x_{k} G_{w0^{∗}00^{∗}} = G_{w0^{∗}10^{∗}} − G_{w0^{∗}0¯010^{∗}}

for the x_{k} factors and:

(4.11)  y_{k} G_{wαβd0^{∗}} = G_{wα(β+1)d0^{∗}} − G_{w0¯0α(β+1)d0^{∗}}

or

(4.12)  y_{k} G_{w0^{∗}¯00^{∗}} = G_{w0^{∗}¯10^{∗}} − G_{w0^{∗}¯00¯10^{∗}}

for the y_{k} factors. All these equations are direct consequences of the recursive definition of the G polynomials.

The reduction of the product (4.8) is made possible because of the order of the multiplications: the successive “shifts” are processed from left to right.

Our final task is to show that all vectors u generated in this process are transdiagonal and that their length never exceeds n.

Let us first check that the generated vectors are all transdiagonal. In the case of relations (4.10) and (4.12), this is obvious. Now, let us consider, for example relation (4.9). Let us denote u = wαβd0^{∗}, u′ = w(α + 1)βd0^{∗} and u′′ = w0¯0(α + 1)βd0^{∗}. Since u is transdiagonal, there exists 1 ≥ l ≥ ℓ(u) such that

u_{1} + u_{2} + ⋯ + u_{2l−1} + u_{2l} ≥ l.

If l > ℓ(w), u′ and u′′ are clearly transdiagonal, and if not:

u′_{1} + u′_{2} + ⋯ + u′_{2l−1} + u′_{2l} ≥ l + 1 ≥ l and u′′_{1} + u′′_{2} + ⋯ + u′′_{2l+1} + u′′_{2l+2} ≥ l + 1

whence u′ and u′′ are transdiagonal.

Let us now check that the length of the generated vectors never exceeds n. We keep track of the couple e = u_{2ℓ(u)−1}, u_{2ℓ(u)}. We distinguish two cases.

(1) e comes from c_{2ℓ(c)−1}, c_{2ℓ(c)} that is shifted to the right by relations (4.9) and/or (4.11). It may be shifted at most |v| steps to the right, thus:

ℓ(u) ≤ ℓ(c) + |v| ≤ |c| + |v| ≤ n.

(2) e comes from a 1¯0 or 0¯1 generated by relation (4.10) or (4.12), then shifted to the right (by any relations). We suppose it is created by a multiplication by x_{k} or y_{k}, and we consider the vector

t = v_{2n}v_{2n−1} … v_{2k}v_{2k−1}0^{∗}.

Since A_{n}^{v} is in C_{n}, the word t is 2-Dyck. Thus:

|t| < ℓ(t) = n − k + 1.

This implies that the term 1¯0 or 0¯1 can be shifted at most to position

k + |t| ≤ k + n − k = n.
□

To illustrate the recursive reduction of a product of the form (4.8), we give the following example, where n = 5:

x_{1} y_{2} F_{1¯00¯1} = y_{2}(x_{1} F_{1¯00¯1})
= y_{2}(G_{2¯00¯10¯00¯00¯0} − G_{0¯02¯00¯10¯00¯0})
= y_{2} G_{2¯00¯10¯00¯00¯0} − y_{2} G_{0¯02¯00¯10¯00¯0}
= G_{2¯00¯20¯00¯00¯0} − G_{2¯00¯00¯2} − G_{0¯02¯10¯10¯00¯0} + G_{0¯02¯00¯10¯10¯0}.

Now we are able to complete the proof of Theorem 1.1. We can even state a more precise result.

Theorem 4.4. A basis of the quotient Q_{n} is given by the set

B_{n} = {A_{n}^{v} / π(v) is a 2−Dyck path},

which implies

(4.13)  dim Q_{n} = \frac{1}{2n + 1}\binom{3n}{n}.

Since I_{n}^{2} is bihomogeneous, the quotient Q_{n} is bigraded and we can consider H_{k,l}(Q_{n}) the subspace of Q_{n} consisting of polynomials of bidegree (k, l), then

(4.14)  dim H_{k,l}(Q_{n}) = \binom{n + k − 1}{k}\binom{n + l − 1}{l}\frac{n − k − l}{n}.

Proof. By Lemma 4.1, the set B_{n} spans Q_{n}. Assume we have a linear dependence:

P = ∑_{A_{n}^{v}∈B_{n}} a_{v} A_{n}^{v} ∈ I_{n}^{2}.

By Lemma 4.3, the set G spans I_{n}^{2}, thus

P = ∑_{u transdiagonal} b_{u} G_{u}.

This implies LM(P) = A_{n}^{u}, with u transdiagonal, which is absurd. Hence B_{n} is a basis of the quotient Q_{n}.

For the combinatorial part, we refer to [6], but we give a short proof of (4.13). A ternary tree is a tree in which every internal node has exactly 3 sons. Ternary

trees are known [23] to be enumerated by

C_{3}(n) = \frac{1}{2n + 1}\binom{3n}{n}.

To conclude we observe that the depth-first search [11] of a tree gives a bijection between ternary trees and 2-Dyck paths ; we recall that we search recursively the left son, the middle son, the right son, and finally the root, and associate to each external node (except the leftmost one) a (0, 1) step, and to each internal node a (2, 0) step.

Below is given an illustration of this bijection, where we put in dashed lines the final horizontal sequence, to coincide with our definition of 2-Dyck paths.

Now if we denote by D_{n,k,l} the set of 2-Dyck paths with k horizontal steps at even height (corresponding to x terms) and l horizontal steps at odd height (corresponding to y terms), then the following equality is proven in [6]:

# D_{n,k,l} = \binom{n + k − 1}{k}\binom{n + l − 1}{l}\frac{n − k − l}{n}.

□

5. Quotient of polynomials by QSym(G^{p})

Every results of this paper can be extended to p sets of variables. Because of the great similarity to the previous sections, we shall only present here the result and a short sketch of the proof.

We denote by A_{n}^{p} the alphabet of p × n variables:

A_{n}^{p} = x_{1}^{(1)}x_{1}^{(2)} … x_{1}^{(p)}x_{2}^{(1)} … x_{2}^{(p)} … x_{n}^{(1)} … x_{n}^{(p)}.

We define p-vectors of size k as vectors of p × k integers. For the ease of reading, we can write for example when p = 3: v = 0˙1¨21˙0¨02˙0¨1. A p-composition is a p-vector avoiding 3 consecutive zeros.

The set QSym(G^{p}) of G^{p}-quasisymmetric polynomials is the vector subspace of ℚ[A_{n}^{p}] spanned by fundamental G^{p}-quasisymmetric polynomials, defined for a pcomposition c by:

F_{c} = ∑ ∏ x_{i^{(1)}}^{(1)} ⋯ ∏ x_{i^{(p)}}^{(p)}

with

i_{1}^{(1)} ≤ ⋯ ≤ i_{c_{1}}^{(1)} ≤ i_{c_{1}+1}^{(2)} ≤ ⋯ ≤ i_{c_{1}+c_{2}}^{(2)} ≤ ⋯ ≤ ⋯ ≤ i_{c_{1}+···+c_{p}}^{(p)} < i_{c_{1}+···+c_{p}+1}^{(1)} ≤ · · · .

We give an example (here p = 3 and we use letters x, y, z for the alphabets x^{(1)}, x^{(2)}, x^{(3)}):

F_{0˙1¨02˙0¨1} = ∑_{i<j≤k≤l} y_{i} x_{j} x_{k} z_{l}.

We define the ideal I_{n}^{p} = ⟨QSym(G^{p})^{+}⟩ and the quotient Q_{n}^{p} = ℚ[A_{n}^{p}]/I_{n}^{p}. The result which generalizes Theorem 4.4 is Theorem 5.1. For p ≥ 1,

(5.1)  dim Q_{n}^{p} = \frac{1}{pn + 1}\binom{(p + 1)n}{n}.

Proof. We shall only give a brief description of the proof, which is very similar to the one of Theorem 4.4.

We first associate to any monomial a plane path, as in Section 3, with the difference that horizontal steps are of length p. Paths (and associated monomials) are said to be p-Dyck if they stay above the diagonal, and transdiagonal if not.

The construction of the set G indexed by transdiagonal path is the same, with p cases of recurrence. We prove that G is a Gröbner basis of I_{n}^{p} as in Section 4, and conclude that a basis of the quotient Q_{n}^{p} is given by the monomials associated to p-Dyck paths.

To conclude, we observe that the depth-first search [11] gives a bijection between p-ary trees, enumerated by the right-hand side of (5.1), and p-Dyck paths. □

Acknowledgement. The author thanks C. Hohlweg for introducing him to B-quasisymmetric polynomials, and for valuable comments and explanations.

References

[1] E. Artin, Galois Theory, Notre Dame Mathematical Lecture 2 (1944), Notre Dame, IN.

[2] J.-C. Aval and N. Bergeron, Catalan Paths and Quasi-Symmetric Functions, Proc. Amer. Math. Soc. 131 (2003), 1053–1062.

[3] J.-C. Aval, F. Bergeron and N. Bergeron, Ideals of Quasi-Symmetric Functions and Super-Coinvariant Polynomials for S_{n}, Adv. in Math. 181 (2004), 353–367.

[4] J.-C. Aval and N. Bergeron, Quasi-symmetric polynomials and Temperley-Lieb algebra of type B, in preparation.

[5] J.-C. Aval, F. Bergeron and N. Bergeron, Diagonal Temperley-Lieb invariants and harmonics, Séminaire Lotharingien Combin. 54A (to appear).

[6] J.-C. Aval, Multivariate Fuss-Catalan numbers, preprint.

[7] P. Baumann and C. Hohlweg, A Solomon theory for the wreath product G ≀ 𝔖_{n}, Trans. Amer. Math. Soc. (to appear).

[8] F. Bergeron, N. Bergeron, A. Garsia, M. Haiman and G. Tesler, Lattice Diagram Polynomials and Extended Pieri Rules, Adv. in Math. 142 (1999), 244–334.

[9] F. Bergeron, A. Garsia, M. Haiman and G. Tesler, Identities and Positivity Conjectures for Some Remarkable Operators in the Theory of Symmetric Functions, Methods and Applications of Analysis 6 (1999), 363–420.

[10] N. Bergeron, S. Mykytiuk, F. Sottile, and S. van Willigenburg, Pieri Operations on Posets, J. Combin. Theory Ser. A 91 (2000), 84–110.

[11] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, second edition, MIT Press and McGraw-Hill, 2001.

[12] D. Cox, J. Little and D. O’Shea, Ideals, Varieties, and Algorithms, Springer-Verlag, New-York, 1992.

[13] A. M. Garsia and M. Haiman, A graded representation model for Macdonald’s polynomials, Proc. Nat. Acad. Sci. U.S.A. 90 (1993), 3607–3610.

[14] A. Garsia, M. Haiman, Orbit Harmonics and Graded Representations, Éditions du Lacim, to appear.

[15] I. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V. Retakh, and J.-Y. Thibon, Noncommutative symmetric functions, Adv. in Math. 112 (1995), 218–348.

[16] I. Gessel, Multipartite P -partitions and products of skew Schur functions, in Combinatorics and Algebra (Boulder, Colo., 1983), C. Greene, ed., vol. 34 of Contemp. Math., AMS, 1984, pp. 289–317.

[17] M. Haiman, Vanishing theorems and character formulas for the Hilbert scheme of points in the plane, Invent. Math. 149 (2002), 371–407.

[18] F. Hivert, Hecke algebras, difference operators, and quasi-symmetric functions, Adv. in Math. 155 (2000), 181–238.

[19] I. Macdonald, Symmetric Functions and Hall Polynomials, second edition, Oxford Univ. Press, 1995.

[20] C. Malvenuto and C. Reutenauer, Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra 177 (1995), 967–982.

[21] J.-C. Novelli and J.-Y. Thibon, Free quasi-symmetric functions of arbitrary level, preprint.

[22] S. Poirier, Cycle type and descent set in wreath products, Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995). Discrete Math. 180 (1998), 315–343.

[23] N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, New York and London, 1973.

[24] R. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brooks/Cole, 1986.

[25] R. Stanley, Enumerative Combinatorics Vol. 2, no. 62 in Cambridge Studies in Advanced Mathematics, Cambridge University Press, 1999. Appendix 1 by Sergey Fomin.

LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence cedex, FRANCE

E-mail address: aval@labri.fr

  URL: http://www.labri.fr/∼aval/