SHIFTED QUASI-SYMMETRIC FUNCTIONS AND THE HOPF ALGEBRA OF PEAK FUNCTIONS

NANTEL BERGERON, STEFAN MYKYTIUK, FRANK SOTTILE, AND STEPHANIE VAN WILLIGENBURG

Summary. In his work on P -partitions, Stembridge defined the algebra of peak functions Π, which is both a subalgebra and a retraction of the algebra of quasisymmetric functions. We show that Π is closed under coproduct, and therefore a Hopf algebra, and describe the kernel of the retraction. Billey and Haiman, in their work on Schubert polynomials, also defined a new class of quasi-symmetric functions — shifted quasi-symmetric functions — and we show that Π is strictly contained in the linear span Ξ of shifted quasi-symmetric functions. We show that Ξ is a coalgebra, and compute the rank of the nth graded component.

Résumé. Dans ses travaux sur les P-partitions, Stembridge définit l’algèbre Π des fonctions de pics. Cette algèbre peut être vue comme une sous-algèbre ou un quotient de l’algèbre des fonctions quasi-symétriques. Nous montrons ici que Π est fermée sous le coproduit, et est donc une algèbre de Hopf. Nous décrivons aussi le noyau du quotient ci-dessus. D’autre part, dans leurs travaux sur les polynômes de Schubert, Billey et Haiman ont défini une nouvelle classe de fonctions quasi-symétriques: les fonctions quasi-symétrique décalé. Nous montrons que Π est strictement contenue dans l’espace linéaire Ξ des fonctions quasi-symétrique gauchis. Puis nous montrons que Ξ est une coalgèbre et calculons les dimensions des composantes de degrée n.

1. Introduction

Schur Q functions first arose in the study of projective representations of S_{n} [8]. Since then they have appeared in variety of contexts including the representations of Lie superalgebras [9] and cohomology classes dual to Schubert cycles in isotropic Grassmanians [4, 7]. While studying the duality between skew Schur P and Q functions and their connection to the Schubert calculus of isotropic flag manifolds, we were led to their quasi-symmetric analogues: the peak functions of Stembridge [10]. We show that the linear span of peak functions is a Hopf algebra (Theorem 2.2). We also show that these peak functions are contained in the strictly larger set of shifted quasi-symmetric functions (Theorem 3.6) introduced by Billey and Haiman [1]. We remark that the quasi-symmetric functions here are not any apparent specialization of the quasi-symmetric q-analogues of Hivert [3].

Date: April 21, 1999. 1991 Mathematics Subject Classification. 05E15, 05E05, 05A15, 16W30. Key words and phrases. Pieri, graded operation, poset, quasi-symmetric functions. Bergeron supported in part by NSERC. Sottile supported in part by NSF grant DMS-9701755 and NSERC grant OGP0170279. van Willigenburg is supported in part by the Leverhulme Trust.

From extensive calculations, we believe that the set of all shifted quasi-symmetric functions form a Hopf algebra, but at present we can only show that:

The set of all shifted quasi-symmetric functions forms a graded coalgebra whose nth graded component has rank π_{n}, where π_{n} is given by the recurrence

π_{n} = π_{n−1} + π_{n−2} + π_{n−4},

with initial conditions π_{1} = 1, π_{2} = 1, π_{3} = 2, π_{4} = 4.

We shall prove this result (Theorems 3.2 and 4.3) and in addition shall establish some other properties of these functions.

A composition α = [α_{1}, α_{2}, …, α_{k}] of a positive integer n is an ordered list of positive integers whose sum is n. We denote this by α ⊨ n. We call the integers α_{i} the components of α, and denote the number of components in α by k(α). There exists a natural one-to-one correspondence between compositions of n and subsets of [n − 1]. If A = {a_{1}, a_{2}, …, a_{k−1}} ⊂ [n − 1], where a_{1} < a_{2} < … < a_{k−1}, then A corresponds to the composition, α = [a_{1} − a_{0}, a_{2} − a_{1}, …, a_{k} − a_{k−1}], where a_{0} = 0 and a_{k} = n. For ease of notation, we shall denote the set corresponding to a given composition α by I(α). For compositions α and β we say that α is a refinement of β if I(β) ⊂ I(α), and denote this by α ≼ β.

For any composition α = [α_{1}, α_{2}, …, α_{k}] we denote by M_{α} the monomial quasisymmetric function [2]

M_{α} = ∑_{i_{1}<i_{2}<...<i_{k}} x_{i_{1}}^{α_{1}} … x_{i_{k}}^{α_{k}}.

We define M_{0} = 1, where 0 denotes the unique empty composition of 0. We denote by F_{α} the fundamental quasi-symmetric function [2]

F_{α} = ∑_{α≼β}M_{β}.

Definition 1.1. For any subset A ⊂ [n − 1], let A + 1 be the subset of {2, …, n} formed from A by adding 1 to each element of A. Let α ⊨ n. Then we define

θ_{α} = ∑_{β ⊨ n_{I(α)⊂I(β)∪I(β)+1}} 2^{k(β)}M_{β}.

This is the natural extension of the definition of peak functions given in [10].

Example 1.2. We shall often omit the brackets that surround the components of a composition.

If α = 21, then I(α) = {2}, and I(α) + 1 = {3}. Hence

θ_{21} = 4M_{21} + 4M_{12} + 8M_{111}.

Let Σ^{n} be the ℤ-module of quasi-symmetric functions spanned by {M_{α}}_{α⊨n} and let Σ = ⊕_{n≥0}Σ^{n} be the graded ℤ-algebra of quasi-symmetric functions. This is a Hopf algebra [5] with coproduct given by

Δ(M_{α}) = ∑_{α=β·γ} M_{β} ⊗ M_{γ},

where β · γ is the concatenation of compositions β and γ.

Example 1.3. Δ(M_{32}) = 1 ⊗ M_{32} + M_{3} ⊗ M_{2} + M_{32} ⊗ 1.

We compute the coproduct of the functions θ_{α}.

Lemma 1.4. For any composition α ⊨ n we have that

(1)  Δ(θ_{α}) = ∑ θ_{ϵ·a} ⊗ θ_{ϕ(b·ζ)}

where the sum is over all ways of writing α as ε·(a+b)·ζ, that is, the concatenation of compositions ε and ζ, and a component of α written as the sum of numbers a, b ≥ 0. Also ϕ(b · ζ) = [1 + ζ_{1}, ζ_{2}, …] if b = 1 and b · ζ otherwise.

We shall use this result to show that certain subsets of functions θ_{α} span coalgebras (Theorems 2.2 and 3.2).

Proof. Definition 1.1 is equivalent to

θ_{α} = ∑_{{β ⊨ n \atop β^{∗} ≼ α}}2^{k(β)}M_{β},

where β^{∗} is the refinement of β obtained by replacing all components β_{i} > 1, for i > 1, by [1, β_{i} − 1]. Thus the LHS of equation (1) is equal to

(2)  ∑_{{β ⊨ n \atop β^{∗} ≼ α} ; β = γ · δ} 2^{k(β)}M_{γ} ⊗ M_{δ} = ∑_{γ · δ ⊨ n_{(γ·δ)^{∗}≼α}}2^{k(γ)}M_{γ} ⊗ 2^{k(δ)}M_{δ}.

Let 2^{k(γ)}M_{γ} ⊗ 2^{k(δ)}M_{δ} be a term of this sum, with γ ⊨ m. This term can only appear in one summand on the RHS of equation (1), namely θ_{ε·a} ⊗ θ_{ϕ(b·ζ)} with ε · a ⊨ m. To show that it does indeed appear, we need to prove that γ^{∗} ≼ ε · a and δ^{∗} ≼ ϕ(b · ζ). Let δ^{∗∗} be the refinement of δ^{∗} obtained by replacing the part δ_{1} by [1, δ_{1} − 1] if δ_{1} > 1. We have that

γ^{∗} · δ^{∗∗} = (γ · δ)^{∗} ≼ ε · (a + b) · ζ,

which implies that γ^{∗} ≼ ε · a, and δ^{∗∗} ≼ b · ζ ≼ ϕ(b · ζ).

If δ_{1} = 1 then δ^{∗} = δ^{∗∗} ≼ ϕ(b · ζ). However, if δ_{1} > 1 then there are two possible cases: either δ_{1} ≤ b, or b = 1 and δ_{1} − 1 ≤ ζ_{1}. In the former case δ^{∗} ≼ b · ζ = ϕ(b · ζ), while in the latter, δ_{1} ≼ 1 + ζ_{1}, whence δ^{∗} ≼ [1 + ζ_{1}, ζ_{2}, …] = ϕ(b · ζ).

Conversely, let 2^{k(γ)}M_{γ} ⊗ 2^{k(δ)}M_{δ} be a term belonging to a tensor θ_{ε·a} ⊗ θ_{ϕ(b·ζ)} on the RHS of equation (1). To show that it appears in equation (2) we must prove that (γ · δ)^{∗} ≼ ε · (a + b) · ζ. We have that γ^{∗} ≼ ε · a and δ^{∗} ≼ ϕ(b · ζ), which imply that

(γ · δ)^{∗} = γ^{∗} · δ^{∗∗} ≼ γ^{∗} · δ^{∗} ≼ ε · a · ϕ(b · ζ).

If b > 1 then

(γ · δ)^{∗} ≼ ε · a · ϕ(b · ζ) = ε · a · b · ζ ≼ ε · (a + b) · ζ.

If b = 1 then δ^{∗} ≼ ϕ(b · ζ) = [1 + ζ_{1}, ζ_{2}, …] implies that

δ^{∗∗} = [1, …] ≼ [1, ζ_{1}, …] = b · ζ.

Therefore,

(γ · δ)^{∗} = γ^{∗} · δ^{∗∗} ≼ ε · a · b · ζ ≼ ε · (a + b) · ζ

as desired.

2. The peak Hopf algebra

Definition 2.1. For any composition α = [α_{1}, α_{2}, …, α_{k}] we say that θ_{α} is a peak function if α_{i} = 1 ⇒ i = k.

Observe that if θ_{α} is a peak function and α ⊨ n, then I(α) ⊂ {2, …, n − 1} such that no two i in I(α) are consecutive.

Let Π^{n} be the ℤ-module spanned by all peak functions θ_{α}, α ⊨ n, and let Π = ⊕_{n≥0}Π^{n}. This was studied by Stembridge [10] who showed that the peak functions are Fpositive, are closed under product, and form a basis for Π, and so the rank of Π^{n} is the nth Fibonacci number. In addition we also know the following about the algebra of peaks, Π.

Theorem 2.2. Π is closed under coproduct.

Proof. If all components of a composition α, except perhaps the last, are greater than 1, then the same is true for all compositions ε · a and ϕ(b · ζ) appearing in the RHS of equation (1).

Let Θ be the ℤ-linear map from Σ to Π defined by Θ(F_{α}) = θ_{Λ(α)}, where Λ(α) is the composition formed from α = [α_{1}, α_{2}, …, α_{k}] by adding together adjacent components α_{i}, α_{i+1}, …, α_{i+j} where α_{i+l} = 1 for l = 0, …, j−1, and either α_{i+j} ≠ 1, or i + j = k.

Example 2.3. If α = 31125111 then Λ(α) = 3453.

Stembridge [10] showed that Θ : Σ → Π is a graded surjective ring homomorphism, and was an analogue of the retraction from the algebra of symmetric functions to Schur Q functions. It is clear from our proof above that this morphism is in fact a Hopf homomorphism. We can describe the kernel of Θ as follows.

Lemma 2.4. The non-zero differences F_{α} − F_{Λ(α)} form a basis of the kernel of Θ.

Proof. Each difference F_{α} − F_{Λ(α)} is in the kernel of Θ as Θ(F_{α} − F_{Λ(α)}) = 0 since Λ(Λ(α)) = Λ(α). In addition, the non-zero differences are linearly independent as they have different leading terms. Letting f_{n} denote the nth Fibonacci number, there are 2^{n−1} − f_{n} such differences, and since

dim ker Θ = dim Σ^{n} − dim Π^{n}
= 2^{n−1} − f_{n},

our result follows.

3. The coalgebra of shifted quasi-symmetric functions

Definition 3.1. For any composition α = [α_{1}, α_{2}, …, α_{k}] ⊨ n we say that θ_{α} is a shifted quasi-symmetric function (sqs-function) if n ≤ 1 or α_{1} > 1.

Observe that if θ_{α} is an sqs-function and α ⊨ n, then I(α) ⊂ {2, …, n − 1}.

For integers n ≥ 0, let Ξ^{n} be the ℤ-module spanned by all sqs-functions θ_{α}, α ⊨ n, and let Ξ = ⊕_{n≥0}Ξ^{n}.

Theorem 3.2. Ξ is closed under coproduct.

Proof. If the first component of a composition α is greater than 1, then the same is true for all compositions ε · a and ϕ(b · ζ) appearing in the RHS of equation (1).

Unlike peak functions [10], sqs-functions are not F -positive since

θ_{211} = F_{22} + F_{112} + 2F_{121} + F_{211} − F_{1111}.

Definition 3.3. For any composition, α ⊨ n, we define the complement α^{c} of α to be the composition for which I(α^{c}) = (I(α))^{c}, the set complement of I(α) in [n − 1]. We define the graph G(α) of α to be the graph obtained from

by removing the edge (i, i + 1) if and only if i ∈ I(α).

Observe that G(α^{c}) contains the edge (i, i+1) if and only if this edge is not contained in G(α). These graphs will be used later to simplify the proof of Theorem 3.6.

Let a word of length n be any n-tuple, w_{1}w_{2} … w_{n}, and let a binary word of length n be a word w_{1}w_{2} … w_{n} wuch that w_{i} ∈ {0, 1} for all i. For 2 ≤ i ≤ n−1, let us denote by 3^{(i)} the composition [1^{i−2}, 3, 1^{n−i−1}] of n. For some subset S ⊂ {2, …, n − 1}, let us denote by ⋀_{i∈S} 3^{(i)} the composition of n for which G(⋀_{i∈S} 3^{(i)}) has an edge between vertices i and i + 1 if and only if an edge exists between vertices i and i + 1 in G(3^{(i)}) for some i ∈ S.

Example 3.4. Let S = {2, 3} ⊂ [3]. Then G(3^{(2)}) is

and G(3^{(3)}) is

hence G(⋀_{i∈S} 3^{(i)}) is

so ⋀_{i∈S} 3^{(i)} is the composition 4.

Definition 3.5. [1] Let α be a composition of n. Let A(I(α)) denote the set of all sequences j_{1} ≤ j_{2} ≤ … ≤ j_{n} in ℕ such that we do not have j_{i−1} = j_{i} = j_{i+1} for any i ∈ I(α). The shifted quasi-symmetric function θ_{α}^{BH} is given by

θ_{α}^{BH} = ∑_{J = (j_{1}, …, j_{n}) ; j_{1} ≤ … ≤ j_{n}_{J∈A(I(α))}} 2^{|j|}x_{j_{1}} … x_{j_{n}},

where |j| denotes the number of distinct values j_{i} in J.

Theorem 3.6. For any sqs-function θ_{α} we have that θ_{α} = θ_{α}^{BH}.

Proof. For each i ∈ I(α) ⊂ [n − 1], j_{i−1} = j_{i} = j_{i+1} is forbidden in any monomial

x_{j_{1}}x_{j_{2}} … x_{j_{i}} … x_{j_{n}}

appearing as a summand of the function θ_{α}^{BH}. This is equivalent to saying that M_{β} is a summand of θ_{α}^{BH} if and only if G(3^{(i)}) ⊄ G(β) for all i ∈ I(α). Therefore at least one of i − 1 or i must be the largest label of a vertex in a connected component in G(β).

Now when going from compositions of n to subsets of [n − 1] we can do so using our graphs, G. All we have to do is list the label of the vertex that is the largest in each connect component, not listing n. We call these vertices the end-points. We are now in a position to prove the equivalence of Definitions 1.1 and 3.5 for sqs-functions.

The powers of 2 agree so we need only show that the indices of summation do too. To see this, take any sqs-function θ_{α} and let i ∈ I(α). Then M_{β} is a summand in θ_{α}^{BH} if at least one of i − 1 or i is an end-point in G(β). Therefore i or i − 1 belongs to I(β), and M_{β} is a summand of θ_{α}. Conversely, if M_{β} is a summand of θ_{α}, then this implies that for each i ∈ I(α), we have that i − 1 or i belongs to I(β), so one of i − 1 or i is an end-point in G(β), so M_{β} is a summand of θ_{α}^{BH}.

4. A basis for Ξ

Definition 4.1. Let θ_{α} be an sqs-function and α ⊨ n. We define an internal peak i ∈ I(α) such that i − 1, i + 1 ∉ I(α), and i ∈ {3, … n − 2}.

Remark Observe that the occurrence of an internal peak in the ith position in I(α) = {w_{1}, w_{2}, … }, where w_{1} < w_{2} < …, is equivalent to having two components of α, say α_{i}, α_{i+1} such that α_{i+1} ≥ 2, and α_{i} ≥ 2 if i ≠ 1, or α_{i} ≥ 3 if i = 1.

We can now describe the basis of Ξ as follows.

Theorem 4.2. The coalgebra Ξ has a basis consisting of all sqs-functions θ_{α} where I(α) contains no internal peak.

We sketch the proof of Theorem 4.2 later.

Theorem 4.3. The rank of Ξ^{n} is given by the recurrence

π_{n} = π_{n−1} + π_{n−2} + π_{n−4},

with initial conditions π_{1} = 1, π_{2} = 1, π_{3} = 2, π_{4} = 4.

This recurrence was suggested by a superseeker query [6].

Proof. By direct calculation we obtain that π_{1} = 1, π_{2} = 1, π_{3} = 2, and π_{4} = 4.

To obtain our recurrence, we observe that for each sqs-function, θ_{α} where α ⊨ n, we can encode I(α) as a binary word of length n − 2, by placing a 1 in position i − 1 if i is contained in I(α), and 0 otherwise. By this one-to-one correspondence we see that I(α) contains no internal peak if its corresponding binary word does not contain 010 as a subword.

We therefore count binary words of length n that avoid the subword 010. Appending either 1 or 0 to such a binary word of length n − 1 gives one of length n, provided that we have not created the subword 010 in the last three positions. Let a_{n}, b_{n}, c_{n}, and d_{n} enumerate those binary words of length n − 2 that avoid the subword 010 and end in, respectively 00, 01, 10, and 11. We then obtain the following 4 simultaneous recursions.

a_{n} = a_{n−1} + c_{n−1}, b_{n} = a_{n−1} + c_{n−1}, c_{n} = d_{n−1}, d_{n} = b_{n−1} + d_{n−1}.

Clearly the number of I(α)s in [n − 1] with no internal peaks is given by

π_{n} = a_{n} + b_{n} + c_{n} + d_{n},

However by substituting in our recurrences we obtain

π_{n} = a_{n} + b_{n} + c_{n} + d_{n}
= 2a_{n−1} + b_{n−1} + 2c_{n−1} + 2d_{n−1}
= π_{n−1} + a_{n−1} + c_{n−1} + d_{n−1}
= π_{n−1} + a_{n−2} + b_{n−2} + c_{n−2} + 2d_{n−2}
= π_{n−1} + π_{n−2} + d_{n−2}
= π_{n−1} + π_{n−2} + b_{n−3} + d_{n−3}
= π_{n−1} + π_{n−2} + a_{n−4} + b_{n−4} + c_{n−4} + d_{n−4}
= π_{n−1} + π_{n−2} + π_{n−4}.

We say that M_{β} is a maximal term of θ_{α} if for any γ higher in the partial order of compositions M_{γ} is not a summand of θ_{α}. The following lemma is stated without proof.

Lemma 4.4. Let θ_{α} be an sqs-function. Consider the collection S of all possible sets derived from I(α) by adding either i−1 or i+1 to I(α) for all internal peaks i ∈ I(α). If M_{β} is a maximal term of θ_{α}, then β is derived from

⋀_{i ∈ (I(α̃))^{c}_{I(α̃)∈S}} 3^{(i)}

by adding adjacent components equal to 1 together to give a component equal to 2 as often as possible.

Lemma 4.5. Let θ_{α} be an sqs-function, and let I(α) have an internal peak in the jth position, then we have the following linear relation

θ_{α} = θ_{[α_{1},... ,α_{j}−1,1,α_{j+1},... ,α_{k}]} + θ_{[α_{1},... ,α_{j},1,α_{j+1}−1,... ,α_{k}]}
−θ_{[α_{1},... ,α_{j}−1,1,1,α_{j+1}−1,... ,α_{k}]}.

Proof. By Definition 3.5 we have that the leading terms of θ_{α} determine the other summands that belong to θ_{α}. Hence by Lemma 4.4 it follows that the summands of θ_{α} will be the union of the summands of θ_{[α_{1},... ,α_{j}−1,1,α_{j+1},... ,α_{k}]} and θ_{[α_{1},... ,α_{j},1,α_{j+1}−1,... ,α_{k}]}. However, those summands that appear in both will be duplicated. By definition these will be the summands of θ_{[α_{1},... ,α_{j}−1,1,1,α_{j+1}−1,... ,α_{k}]}, and the result follows.

Sketch of proof of Theorem 4.2. From our relation in Lemma 4.5, it follows that any θ_{α} can be rewritten as a linear combination of functions θα̃, where I(α̃) contains no internal peaks. In addition, by Lemma 4.4 and definition 3.5 we have that the set of all sqs-functions θ_{α} where I(α) contains no internal peaks is linearly independent and thus form a basis for Ξ.

References

[1] S. Billey, and M. Haiman, Schubert polynomials for the classical groups, Journal of AMS, 8 (1995) 443–482.

[2] I. Gessel, Multipartite P -partitions and inner products of skew Schur functions, Contemporary Mathematics, 34 (1984) 289–301.

[3] F. Hivert, Quasi-symmetric functions and Hecke algebra action, Proceeding of the 10th FPSAC, Toronto (1998) 377–388.

[4] T. Józefiak, Schur Q functions and cohomology of isotropic Grassmanians, Math. Proc. Camb. Phil. Soc., 109 (1991) 471–478.

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

[6] N.J.A. Sloane,An on-line version of the Encyclopedia of integer sequences, Elect. J. Combin., 1 No.1, (1994) F1.

    http://akpublic.research.att.com/~njas/sequences/ol.html.

[7] P. Pragacz, Algebro-geometric applications of Schur S- and Q- polynomials, Topics in Invariant Thoery, Séminaire d’Algèbre Dubreil-Malliavin 1989-90, Springer-Verlag, (1991) 130–191.

[8] I. Schur, Über die Darstellung der symmetrischen und der alternierenden Gruppe durch gebrochene lineare Substitutionen, J. reine angew. Math. , 139 (1911) 155–250.

[9] A.N. Sergeev, The tensor algebra of the identity representation as a module over the Lie superalgebras gl(n, m) and Q(n), Math. USSR Sbornik, 51 (1985) 419–427.

[10] J. Stembridge, Enriched P-partitions, Trans. AMS, 349 (1997) 763–788.

(Nantel Bergeron and Stefan Mykytiuk and Stephanie van Willigenburg) Department of Mathematics and Statistics, York University, Toronto, Ontario M3J 1P3, CANADA

(Frank Sottile) Department of Mathematics, University of Wisconsin, Van Vleck Hall, 480 Lincoln Drive, Madison, Wisconsin 53706-1388, USA

E-mail address, Nantel Bergeron: bergeron@mathstat.yorku.ca

URL, Nantel Bergeron: http://www.math.yorku.ca/bergeron
E-mail address, Stefan Mykytiuk: Mykytiuk@pascal.math.yorku.ca

E-mail address, Frank Sottile: sottile@math.wisc.edu

URL, Frank Sottile: http://www.math.wisc.edu/~sottile

E-mail address, Stephanie van Willigenburg: steph@pascal.math.yorku.ca

URL, Stephanie van Willigenburg: http://www-theory.dcs.st-and.ac.uk/~stephvw