Twisted Incidence Algebras and Kazhdan-Lusztig-Stanley functions

Francesco Brenti^{1}

Abstract

We introduce a new multiplication in the incidence algebra of a partially ordered set, and study the resulting algebra. As an application of the properties of this algebra we obtain a combinatorial formula for the Kazhdan-Lusztig-Stanley functions of a poset. As special cases this yields new combinatorial formulas for the parabolic and inverse parabolic Kazhdan-Lusztig polynomials, for the generalized (toric) h-vector of an Eulerian poset, and for the Lusztig-Vogan polynomials.

1 Introduction

The main purpose of this work is to introduce a new multiplication on the incidence algebra of a partially ordered set and to study the resulting algebra. The motivation for doing this comes from the desire to generalize the main result of [3] on Kazhdan-Lusztig polynomials to the much more general setting of P -kernels introduced and developed by Stanley in [14]. In fact, as an application of the general properties of this algebra we obtain (in a rather effortless way) a non-recursive combinatorial formula for any Kazhdan-Lusztig-Stanley function of a poset (see §2 for definitions) in terms of its kernel. This formula, in turn, can be specialized to obtain new combinatorial formulas for the parabolic and inverse parabolic Kazhdan-Lusztig polynomials, for the generalized h-vector of an Eulerian poset, and for the Lusztig-Vogan polynomials. In fact, all these formulas appear in the present context as computation of right inverses (with respect to the new multiplication) of certain elements of the corresponding incidence algebras.

The organization of the paper is as follows. In the next section we collect some definitions, notation, and results that are needed in the rest of this work, including some necessary background material on parabolic Kazhdan-Lusztig polynomials and Lusztig-Vogan polynomials (although this is not needed until §6). In §3 we define the main concept of this work, namely the twisted convolution, and derive some of its basic properties. Our main result here (Proposition 3.3) is that the twisted convolution is distributive over infinite (convergent) sums. In §4 we study, from an algebraic point of view, the incidence algebra of a poset under the new product defined in §3. In particular, we show that the regular representation of this algebra is faithful if P has no maximal elements, and that this algebra is nilpotent if P is finite. In §5 we use a standard construction to embed the algebra studied in §4 into a slightly larger one which has an identity, and we characterize and study the invertible elements of this “enlarged algebra”. In §6 we use the machinery developed in the previous sections to prove our main result (Theorem 6.3). More precisely, we show that a P -kernel and its KLS-function are inverses of each other in the enlarged algebra. From this, and the general results on invertible elements obtained in §5, we deduce immediately the existence and uniqueness of the KLS-function γ associated to a P -kernel K (thus generalizing slightly a previous result of Stanley in [14]), and a non-recursive formula for γ in terms of K. We then show how this last formula includes the combinatorial formulas obtained in [3] for the Kazhdan-Lusztig and inverse Kazhdan-Lusztig polynomials, and how it also yields new formulas for the parabolic and inverse parabolic Kazhdan-Lusztig polynomials introduced in [5], for the generalized (toric) h-vector of an Eulerian poset introduced in [13], and for the so-called Lusztig-Vogan polynomials introduced in [10].

1Partially supported by EC grant No. CHRX-CT93-0400, and by the Mathematical Sciences Research Institute under NSF grant No. DMS 9022140

2 Notation, Definitions, and preliminaries

In this section we collect some definitions, notation and results that will be used in the rest of this work. We let P =^{def} {1, 2, 3, …} , N=^{def}P ∪{0}, Z be the ring of integers, Q be the field of rational numbers, and R be the field of real numbers; for a ∈N we let [a] =^{def} {1, 2, …, a} (where [0] =^{def} ∅). Given n, m ∈ P, n ≤ m, we let [n, m] =^{def} [m] \ [n − 1], and we define similarly (n, m], (n, m), and [n, m). For S ⊆ R we write S = {a_{1}, …, a_{r}}_{<} to mean that S = {a_{1}, …, a_{r}} and a_{1} < … < a_{r}. The cardinality of a set A will be denoted by |A|, for r ∈ N we let (\begin{matrix}A \\ r \end{matrix}) =^{def} \{S ⊆ A : |S| = r}. Given a polynomial P (q), and i ∈ Z, we denote by [q^{i}](P (q)) the coefficient of q^{i} in P (q). For a ∈ Q we let ⌊a⌋ (respectively, ⌈a⌉) denote the largest integer ≤ a (respectively, smallest integer ≥ a). Given A(q) ∈ R[q] and d ∈ P we say that A(q) is symmetric (respectively, antisymmetric) with respect to d if q^{d}A (\frac{1}{q}) = A(q) (respectively, q^{d}A (\frac{1}{q}) = −A(q)).

For j ∈ Q we define operators U_{j}, D_{j} : R[q] → R[q] by letting

U_{j} (∑_{i≥0} a_{i}q^{i}) =^{def} ∑_{i≥j} a_{i}q^{i},  (1)

D_{j} (∑_{i≥0} a_{i}q^{i}) =^{def} ∑_{i=0}^{j} a_{i}q^{i}.

Note that U_{j} and D_{j} are linear and idempotent, and that D_{j} = D_{⌊j⌋} and U_{j} = U_{⌈j⌉}, for all j ∈ Q.

Given r ∈ P and α_{1}, …, α_{r} ∈ N we define a polynomial ĝ_{α_{1},...,α_{r}}(q) inductively as follows. We let

ĝ_{α_{1},...,α_{r}}(q) =^{def} (q − 1)^{α_{1}}U_{\frac{α′+1}{2}} (q^{α′} ĝ_{α_{2},...,α_{r}} (\frac{1}{q}))  (2)

(where α′ =^{def} α_{2} + … + α_{r}) if r ≥ 2, and

ĝ_{α_{1},...,α_{r}}(q) =^{def} (q − 1)^{α_{1}}  (3)

if r = 1. For example, ĝ_{2,2,3}(q) = 3q^{5} − 6q^{4} + 3q^{3}. Given n ∈ P and S = {s_{1}, …, s_{r}}_{<} ⊆ [n] we let

h_{S,n}(q) =^{def} \frac{ĝ_{s_{1},s_{2}−s_{1},s_{3}−s_{2},...,n+1−s_{r}}(q)}{(q − 1)}.  (4)

The polynomials ĝ_{α_{1},...,α_{r}}(q) have been first introduced and studied in [4, §3] (though the definition given there is different from the one given here). In particular, a combinatorial interpretation is known for them (see [4, Theorem 3.16]), and this implies a combinatorial interpretation for the polynomials h_{S,n}(q), which we now describe. Let n ∈ P, and T = {t_{1}, …, t_{r−1}}_{<} ⊆ [n − 1]. We say that a subset A ⊆ [n] is (T, n)-balanced if

(−1)^{i}|A ∩ (t_{i}, n]| ≤ \frac{(−1)^{i}|(t_{i}, n]| − 1}{2}

for all i = 1, …, r − 1. For example {3, 4} is ({2, 4}, 5)-balanced, but not ({1, 4}, 5)- balanced. Given T ⊆ [n − 1] we let

G_{n}(T) =^{def} {A ⊆ [n] : A is (T, n)-balanced}.  (5)

The following result is an immediate consequence of Theorem 3.16 of [4] and of the definition (4).

Theorem 2.1 Let n ∈ P and S =^{def} {s_{1}, …, s_{r}}_{<} ⊆ [n]. Then

(−1)^{S′+(n+1)(|S|+1)+1} h_{S,n}(−q) = ∑_{{A∈G_{n+1}(S):1∉A}} q^{|A|},

where S′ =^{def} ∑_{i=1}^{r}(−1)^{i−1}s_{i}.

For example, if n = 6 and S = {2, 4} then {A ∈ G_{7}({2, 4}): 1 ∉ A} = ⋃_{i=5}^{7}{{3, 4, i}, {2, 3, 4, i}} and hence (−1)^{20}h_{{2,4},6}(−q) = 3q^{3} + 3q^{4}.

We follow [12], Chap. 3, for notation and terminology concerning partially ordered sets. In particular, given a partially ordered set (or, poset, for short) P we let Int(P) =^{def} {(x, y) ∈ P^{2} : x ≤ y}, and given u, v ∈ P we let [u, v] =^{def} {x ∈ P : u ≤ x ≤ v}. We consider [u, v] as a poset with the partial ordering induced by P. We say that a poset P is locally finite if |[x, y]| < +∞ for all (x, y) ∈ Int(P), and in this case we denote by ξ (respectively, μ, δ) the zeta (respectively, Möbius, delta) function of P. Recall (see, e.g., [12], §3.6) that given a locally finite poset P and a commutative ring R the incidence algebra of P with coefficients in R, denoted I(P; R), is the set of all functions f : Int(P) → R with sum and product defined by

(f + g)(x, y) =^{def} f(x, y) + g(x, y)

and

(fg)(x, y) =^{def} ∑_{x≤z≤y} f(x, z) g(z, y),  (6)

for all f, g ∈ I(P; R) and (x, y) ∈ Int(P). It is well known (see, e.g., [12], §3.6, and Proposition 3.6.2) that I(P; R) is an associative algebra having δ as identity element, and that an element f ∈ I(P; R) is invertible if and only if f(x, x) ≠ 0 for all x ∈ P. If f is invertible then we denote by f^{−1} its (two-sided) inverse. Given f ∈ I(P; R) we define f^{∗} ∈ I(P^{∗}; R) (where P^{∗} denotes the order dual of P) by letting

f^{∗}(v, u) =^{def} f(u, v)  (7)

for all (v, u) ∈ Int(P^{∗}).

Let P be a locally finite poset. We say that a function ρ : Int(P) → N is a weak rank function for P if it has the following two properties:

i) if u < v then ρ(u, v) > 0;

ii) if u ≤ a ≤ v then ρ(u, v) = ρ(u, a) + ρ(a, v).

Note that a weak rank function always exists and that if ρ is a weak rank function for P then ρ^{∗} is a weak rank function for P^{∗}. The concept of a weak rank function enables us to extend the main definitions of §6 of [14] from the locally graded case (i.e., posets P such that [x, y] is a finite graded poset for all (x, y) ∈ Int(P)) to the locally finite case. Let P and ρ be as above and I(P; R[q]) be the incidence algebra of P with coefficients in R[q]. Following Stanley (see [14],p. 830, and Proposition 6.11, p. 835) we let

Ĩ(P) =^{def} {f ∈ I(P; R[q]) : deg(f(x, y)) ≤ ρ(x, y), for all (x, y) ∈ Int(P)},

and

I_{\frac{1}{2}} (P) =^{def} \{f ∈ Ĩ(P) : deg(f(u, v)) ≤ \frac{1}{2}(ρ(u, v) − 1) for u < v, and f(u, u) = 1\}.

Note that Ĩ(P) is a subalgebra of I(P; R[q]) and that, if f ∈ I(P; R[q]) is invertible, then f ∈ Ĩ(P) if and only if f^{−1} ∈ Ĩ(P). Given f ∈ Ĩ(P) we let

\overline{f}(u, v) =^{def} q^{ρ(u,v)}f(u, v) (\frac{1}{q}) ,  (8)

for all u, v ∈ P, u ≤ v. Notice that Ĩ(P), I_{\frac{1}{2}} (P), and the involution^{−} all depend also on ρ. However, throughout this work ρ will always be fixed, so no confusion should arise. Recall (see [14], Definition 6.2, p. 830) that an element K ∈ I(P; R[q]) is called a P -kernel if K(u, u) = 1 for all u ∈ P and there exists an element f ∈ I(P; R[q]) such that:

i) f is invertible in I(P; R[q]);

ii) fK = \overline{f}.

An element f ∈ I(P; R[q]) satisfying ii) above is called K-totally acceptable (see [14], Definition 6.2, p.830). The following result was first proved by Stanley in [14] (see Lemma 6.4, p. 831) in the case that Q is graded. However, his proof carries over unchanged to the present more general setting.

Lemma 2.2 Let Q be a finite poset with ˆ0 and ˆ1, and ρ be a weak rank function for Q. Let f, K ∈ Ĩ(Q) be such that K is a Q-kernel and

(fK)(ˆ0, s) = \overline{f}(ˆ0, s)

for all s < ˆ1. Then

(fK)(ˆ0, ˆ1) − f(ˆ0, ˆ1)

is antisymmetric with respect to ρ(ˆ0, ˆ1).

Following Stanley we call Lemma 2.2 the “generalized Dehn-Sommerville equations for the kernel K” (see [14], p. 831, for the reason behind this terminology). The next fundamental result is due to Stanley (see [14], Corollary 6.7). Although we don’t need it in what follows (in fact, we will give an independent proof of a more general result in this paper) we recall it here because of its importance and because it is one of the main motivations for the present work.

Theorem 2.3 Let P be a locally graded poset and K ∈ I(P; R[q]) a P -kernel. Then there exists a unique K-totally acceptable element γ ∈ I_{\frac{1}{2}} (P).

We call the element γ whose existence and uniqueness is guaranteed by the preceding theorem the Kazhdan-Lusztig-Stanley function (or KLS-function, for short) of P relative to K. As noted in [14], §§6 and 7, the function γ specializes to many interesting objects depending on the particular choice of the poset P and kernel K (see also §6 of the present work).

We follow [11] for general terminology regarding nonassociative algebras. In particular, by a (nonassociative) R-algebra we mean an R-vector space U with a multiplication such that (f + g)h = fh + gh, h(f + g) = hf + hg, and α(fg) = (αf)g = f(αg) for all α ∈ R and f, g ∈ U. Recall (see, e.g., [11, Chapter II, §2, p. 15] and [11, Chapter II, §2, p. 18]) that such an R-algebra U is called a division algebra if, for all f, g ∈ U, f ≠ 0, the equations fx = g and yf = g have unique solutions x, y ∈ U, and is called nilpotent if there exists a t ∈ P such that the product (no matter how associated) of any t elements of U equals 0. Let M be an R-vector space. Recall (see, e.g., [11, Chapter II, §4, p. 26]) that a representation of U in M is a pair of linear maps T, S : U → End(M). The regular representation of U is the pair R, L : U → End(U) where (R(f))(g) =^{def} gf and (L(f))(g) =^{def} fg for all f, g ∈ U.

The preliminaries that follow are only needed for the applications of the main result presented in §6. Therefore, readers who are not interested in these applications may skip the rest of this section.

Given a finite graded poset P and S ⊆ N we let P_{S} =^{def} {x ∈ P : l(x) ∈ S}, where l : P → N is the rank function of P, and α(P; S) be the number of maximal chains of P_{S}. We also let P_{i} =^{def} P_{{i}} if i ∈ N. We say that a finite graded poset P as above is Eulerian if P has a ˆ0 and ˆ1 and μ(x, y) = (−1)^{l(y)−l(x)} for all x, y ∈ P, x ≤ y. Recall (see, e.g., [12], §3.14, p. 138, or [13], §2, p. 190) that to any Eulerian poset P as above there are associated two polynomials, denoted f(P; q) and g(P; q), defined inductively as follows:

i) if |P | = 1 then f(P; q) =^{def} g(P; q) =^{def} 1;

ii) if P has rank n + 1 ≥ 1 then

g(P; q) =^{def} D\frac{n}{2} ((1 − q)f(P; q));  (9)

iii) if P has rank n + 1 ≥ 1 then

f(P; q) =^{def} ∑_{a∈P \{ˆ1}} g([ˆ0, a]; q) (q − 1)^{n−l(a)} .  (10)

The polynomials f(P; q) and g(P; q) were introduced in [13] and are two very subtle invariants of the Eulerian poset P (see [12], §3.14, and [13], §§2,3, for further information). We call g(P; q) the g-polynomial of P, and (h_{0}, …, h_{n}), where h_{i} =^{def} [q^{n−i}](f(P; q)) for i = 0, …, n, the (generalized) h-vector of P (sometimes also called the toric h-vector of P).

We follow [7] for general Coxeter groups notation and terminology. Given a Coxeter system (W, S) and σ ∈ W we denote by l(σ) the length of σ in W, with respect to S, and we let D(σ) =^{def} {s ∈ S : l(s σ) < l(σ)}. We denote by e the identity of W, and we let T =^{def} {σsσ^{−1} : σ ∈ W, s ∈ S} be the set of reflections of W. Given J ⊆ S we let

W^{J} =^{def} {σ ∈ W : l(σs) > l(σ) for all s ∈ J}.

Note that W^{∅} = W. We will always assume that W^{J} is partially ordered by (strong) Bruhat order. Recall (see, e.g., [7], §5.9) that this means that x ≤ y if and only if there exist r ∈ N and t_{1}, …, t_{r} ∈ T such that t_{r} … t_{1} x = y and l(t_{i} … t_{1} x) > l(t_{i−1} … t_{1}x) for i = 1, …, r. It is well known (see, e.g., [2], Proposition 1, iv)) that intervals of W^{J} are finite graded posets.

The following two results are due to Deodhar, and we refer the reader to [5, §2 and Lemma 2.8] and to [5, Proposition 3.1] for their proofs.

Theorem 2.4 Let (W, S) be a Coxeter system, and J ⊆ S. Then, for each x ∈ {−1, q}, there is a unique family of polynomials {R_{u,v}^{J,x}(q)}_{u,v∈W^{J}} ⊆ Z[q] such that, for all u, v ∈ W^{J}:

i) R_{u,v}^{J,x}(q) = 0 if u ≰ v;

ii) R_{u,u}^{J,x}(q) = 1;

iii) if u < v and s ∈ D(v) then

R_{u,v}^{J,x}(q) = \{ \begin{matrix}R_{su,sv}^{J,x}(q), & if s ∈ D(u), \\ (q − 1)R_{u,sv}^{J,x}(q) + qR_{su,sv}^{J,x}(q), & if s ∉ D(u) and su ∈ W^{J}, \\ (q − 1 − x)R_{u,sv}^{J,x}(q), & if s ∉ D(u) and su ∉ W^{J}. \end{matrix}

Theorem 2.5 Let (W, S) be a Coxeter system, and J ⊆ S. Then, for each x ∈ {−1, q}, there is a unique family of polynomials {P_{u,v}^{J,x}(q)}_{u,v∈W^{J}} ⊆ Z[q], such that, for all u, v ∈ W^{J}:

i) P_{u,v}^{J,x}(q) = 0 if u ≰ v;

ii) P_{u,u}^{J,x}(q) = 1;

iii) deg(P_{u,v}^{J,x}(q)) ≤ ⌊\frac{1}{2} (l(v) − l(u) − 1)⌋, if u < v;

iv)

q^{l(v)−l(u)} P_{u,v}^{J,x} (\frac{1}{q}) = ∑_{u≤z≤v} R_{u,z}^{J,x}(q) P_{z,v}^{J,x}(q) ,  (11)
if u ≤ v.

We call the polynomials R_{u,v}^{J,x}(q) and P_{u,v}^{J,x}(q), whose existence is guaranteed by the two previous theorems, the parabolic R-polynomials and parabolic Kazhdan-Lusztig polynomials (respectively) of W^{J} with respect to x. It follows immediately from Theorems 2.4 and 2.5 and from well known facts (see, e.g., [7, §7.5] and [7, §§7.9-11]) that R_{u,v}^{∅,−1}(q) (= R_{u,v}^{∅,q}(q)) and P_{u,v}^{∅,−1}(q) (= P_{u,v}^{∅,q}(q)) are the (usual) R-polynomials and Kazhdan-Lusztig polynomials of W. There is one more property of the polynomials R_{u,v}^{J,x}(q) that we will use in §6, and that we recall here for the reader’s convenience. A proof of it can be found in [6, Corollary 2.2].

Proposition 2.6 Let (W, S) be a Coxeter system, and J ⊆ S. Then

q^{l(v)−l(u)}R_{u,v}^{J,x} (\frac{1}{q}) = (−1)^{l(v)−l(u)}R_{u,v}^{J,q−1−x}(q)

for all u, v ∈ W^{J}, and x ∈ {−1, q}.

Fix two distinct primes p, l with p ≠ 2. Let G be a connected reductive group over \overline{F}_{p} and θ : G → G an involutive automorphism. Fix a subgroup K of G having finite index in {g ∈ G : θ(g) = g}. Following [10, Definition 1.1, p. 365] we let D be the set of all pairs (O, γ) where O is an orbit of K on the flag variety of all Borel subgroups of G, and γ is an isomorphism class of K-equivariant sheaves of one-dimensional \overline{Q}_{l}-vector spaces on O, and we denote by ≤ the Bruhat G-order on D (we refer the reader to [10], Definition 1.8, p. 367, for the definition of this partial ordering). Since it is known (see [10], Definition 1.1, p. 365) that if (O, γ) ∈ D then O is uniquely determined by γ we will simply write γ instead of (O, γ), and we let

l(γ) =^{def} dim(O).

Let M be the free Z[q, q^{−1}]-module with basis D. The following two results are due to Lusztig and Vogan and we refer the reader to [10, Theorem 1.10] and [10, Theorem 1.11], for their proofs.

Theorem 2.7 There exists a Z-linear map D : M → M such that:

i) D(q m) = q^{−1}D(m) for all m ∈ M;

ii) if δ ∈ D then

D(δ) = q^{−l(δ)} ∑_{γ≤δ} R_{γ,δ}(q)γ

where R_{γ,δ}(q) ∈ Z[q], R_{δ,δ}(q) = 1, and deg(R_{γ,δ}) ≤ l(δ) − l(γ).

Theorem 2.8 For each δ ∈ D there exists a unique element

C_{δ} = ∑_{γ≤δ} P_{γ,δ}(q)γ

of M subject to the following conditions:

i) D(C_{δ}) = q^{−l(δ)}C_{δ};

ii) P_{δ,δ}(q) = 1;

iii) if γ ≠ δ then P_{γ,δ}(q) ∈ Z[q] and deg(P_{γ,δ}) ≤ \frac{1}{2}(l(δ) − l(γ) − 1).

We call the polynomials P_{γ,δ}(q) defined by the previous theorem the Lusztig-Vogan polynomials of D. An algorithm for the computation of the polynomials R_{γ,δ}(q) defined in Theorem 2.7 is given in the proof of Lemma 6.8 of [15].

Throughout this work, unless otherwise explicitly stated, P denotes a locally finite poset and ρ : Int(P) → N a weak rank function for P.

3 The Twisted Convolution

In this section we define the crucial concept of this work, namely the twisted convolution, and we establish some of its basic properties.

For f, g ∈ Ĩ(P) we let

(f ∘ g)(u, v) =^{def} ∑_{a∈[u,v]} f(u, a) U_{\frac{ρ(a,v)+1}{2}} (\overline{g}(a, v)),  (12)

and call f ∘ g the twisted convolution of f and g. For example, if ξ ∈ Ĩ(P) is the zeta function of P then (ξ ∘ ξ)(u, v) = ∑_{a∈[u,v)} q^{ρ(a,v)}.

We can express the twisted convolution in terms of the ordinary convolution if we introduce the following operator D : I(P; R[q]) → Ĩ(P). For f ∈ I(P; R[q]) we define Df ∈ Ĩ(P) by letting

(Df)(u, v) =^{def} D_{\frac{ρ(u,v)−1}{2}} (f(u, v)),  (13)

for all (u, v) ∈ Int(P). Note that D is linear and idempotent, and that (Df)(u, u) = 0 for all f ∈ I(P; R[q]) and u ∈ P. We then have the following simple relation between the twisted convolution ∘ and the operator D.

Proposition 3.1 Let f, g ∈ Ĩ(P). Then

f ∘ g = f ∘ Dg = f\overline{Dg}.  (14)

Proof. We have from the definitions (1), (8), and (13) that

U_{\frac{ρ(a,v)+1}{2}} (\overline{g}(a, v)) = U_{\frac{ρ(a,v)+1}{2}} ((\overline{Dg})(a, v)) = (\overline{Dg})(a, v),

for all (a, v) ∈ Int(P). The result follows from (6) and (12). □

Note that Proposition 3.1 enables us to extend the definition of f ∘ g to any f, g ∈ I(P; R[q]), and we will do this freely in what follows.

Proposition 3.2 Let f, g, h ∈ I(P; R[q]). Then we have that:

i) (f + g) ∘ h = (f ∘ h) + (g ∘ h);

ii) f ∘ (g + h) = (f ∘ g) + (f ∘ h);

iii) f(g ∘ h) = (fg) ∘ h.

Proof. This follows easily from Proposition 3.1 and the fact that D(g+h) = Dg+Dh and \overline{g + h} = \overline{g} + \overline{h}. □

Note that the twisted convolution is not associative. For example, if u, v ∈ P, u < v, and ρ(u, v) = 2, then (ξ∘(ξ∘ξ))(u, v) = 0 but ((ξ∘ξ)∘ξ)(u, v) = (|[u, v]|−2)q^{2}.

Recall (see, e.g., [12], §3.6, p. 115) that given f, f_{1}, f_{2}, … ∈ I(P, R[q]) we write

f = ∑_{i≥1} f_{i}

if, for all u, v ∈ P, u ≤ v, f_{i}(u, v) ≠ 0 for only finitely many i ∈ P, and f(u, v) = ∑_{i≥1} f_{i}(u, v). In this case we say that ∑_{i≥1} f_{i} converges to f. Note that if f_{1}, f_{2}, … ∈ Ĩ(P) and f = ∑_{i≥1} f_{i} then f ∈ Ĩ(P). The following property of the twisted convolution is the main result of this section, and plays a fundamental role in the sequel.

Proposition 3.3 Let g, f, f_{1}, f_{2}, … ∈ Ĩ(P) be such that ∑_{i≥1} f_{i} = f. Then

∑_{i≥1}(g ∘ f_{i}) = g ∘ f,  (15)

and

∑_{i≥1}(f_{i} ∘ g) = f ∘ g.  (16)

Proof. Fix u, v ∈ P, u ≤ v. By the definition (12) we have that

(g ∘ f_{i})(u, v) = ∑_{u≤a≤v} g(u, a)U_{\frac{ρ(a,v)+1}{2}} (\overline{f_{i}}(a, v)).

Since ∑_{i≥1} f_{i} converges we have that, for each a ∈ [u, v], f_{i}(a, v) = 0 for almost all i ∈ P. But since P is locally finite, the interval [u, v] is finite. Therefore there exists k ∈ P such that if i > k then f_{i}(a, v) = 0 for all a ∈ [u, v], and hence (g ∘ f_{i})(u, v) = 0. This proves that ∑_{i≥1}(g ∘ f_{i}) converges. Furthermore, we have that

∑_{i≥1}(g ∘ f_{i})(u, v) = ∑_{i=1}^{k}(g ∘ f_{i})(u, v)
= (g ∘ (∑_{i=1}^{k} f_{i})) (u, v)
= ∑_{u≤a≤v} g(u, a)U_{\frac{ρ(a,v)+1}{2}} (∑_{i=1}^{k} \overline{f}_{i}(a, v))
= ∑_{u≤a≤v} g(u, a)U_{\frac{ρ(a,v)+1}{2}} (\overline{f}(a, v))
= (g ∘ f)(u, v),

and (15) follows. The proof of (16) is analogous. □

In Proposition 6.11 of [14] Stanley shows that there is a close relationship between I_{\frac{1}{2}} (P) and the set of all P -kernels of P. The next result gives a characterization of I_{\frac{1}{2}} (P) in terms of the twisted convolution, and will be used in §6. Notice that g ∈ I_{\frac{1}{2}} (P) if and only if Dg = g − δ.

Proposition 3.4 Let f, g ∈ Ĩ(P), and suppose that f is invertible in I(P; R[q]). Then the following are equivalent:

i) f ∘ g = f\overline{g} − f;

ii) g ∈ I_{\frac{1}{2}} (P).

Proof. Assume that ii) holds. Then we have from Proposition 3.1 and the definition (13) that

f ∘ g = f\overline{Dg} = f(\overline{g − δ}) = f(\overline{g} − \overline{δ}) = f\overline{g} − f,

as desired.

Conversely, assume that i) holds. Then by Proposition 3.1 we conclude that

f(\overline{Dg} − \overline{g} + δ) = 0.

Since f is invertible this implies that \overline{Dg} = \overline{g} − δ, and ii) follows. □

We conclude this section by noting that the twisted convolution does not have either a left or a right neutral element. In fact, if f ∈ I(P; R[q]) were such that g ∘ f = g (respectively, f ∘ g = g) for all g ∈ I(P; R[q]), then, in particular, we would have that (δ ∘ f)(u, u) = δ(u, u) (respectively, (f ∘ δ)(u, u) = δ(u, u)) for all u ∈ P, which is a contradiction.

4 The Twisted Incidence Algebra

In this section we study the subspace Ĩ(P) of I(P; R[q]) with respect to the twisted convolution product. In particular, we show that if P has no maximal elements then the regular representation of Ĩ(P) is faithful, and that if P is finite then Ĩ(P) is a nilpotent algebra.

Proposition 4.1 The twisted convolution makes Ĩ(P) into a (nonassociative) Ralgebra.

Proof. It is clear that Ĩ(P) is a vector space over R. It is also clear from (12) that

α(f ∘ g) = (αf) ∘ g = f ∘ (αg)

for all α ∈ R and f, g ∈ Ĩ(P), so the result follows from Proposition 3.2. □

We call Ĩ(P) with the multiplication defined by (12) the twisted incidence algebra of P.

Since the (usual) incidence algebra of P has an identity its regular representation is faithful. This also holds for the twisted incidence algebra if P has no maximal elements.

Proposition 4.2 Let f ∈ Ĩ(P). Then the following conditions are equivalent:

i) g ∘ f = 0 for all g ∈ Ĩ(P);

ii) q^{⌊ \frac{ρ(u,v)+1}{2} ⌋} divides f(u, v) for all u, v ∈ P, u < v.

Proof. Since δ ∈ Ĩ(P) we have from Proposition 3.1 that g ∘ f = 0 for all g ∈ Ĩ(P) if and only if \overline{Df} = 0. This, by (13), happens exactly when q^{⌊^{\frac{ρ(u,v)−1}{2}}⌋+1} divides f(u, v) for all u, v ∈ P, u < v. □

Given a poset P we denote by M(P) the set of all the maximal elements of P.

Proposition 4.3 Let f ∈ Ĩ(P). Then the following conditions are equivalent:

i) f ∘ g = 0 for all g ∈ Ĩ(P);

ii) f(u, v) = 0 for all u ∈ P and v ∈ P \ M(P), with u ≤ v.

Proof. Assume first that ii) holds. Let u, v ∈ P, u ≤ v. Then we have from (12) and our hypothesis ii) that

(f ∘ g)(u, v) = ∑_{a∈[u,v]} f(u, a)U_{\frac{ρ(a,v)+1}{2}} (\overline{g}(a, v))
= f(u, v)U_{\frac{1}{2}} (\overline{g}(v, v))
= 0

for all g ∈ Ĩ(P), as desired.

Conversely, assume that i) holds. Since v ∈ P \ M(P) there exist b ∈ P such that v < b and g ∈ Ĩ(P) such that

g(a, b) = \{ \begin{matrix}1, & if a = v, \\ 0, & otherwise \end{matrix}  (17)

for all a ≤ b. Therefore we have from (12) and i) that

0 = (f ∘ g)(u, b)
= ∑_{a∈[u,b]} f(u, a)U_{\frac{ρ(a,b)+1}{2}} (\overline{g}(a, b))
= f(u, v)U_{\frac{ρ(v,b)+1}{2}} (\overline{g}(v, b))
= f(u, v) q^{ρ(v,b)},

by (17). □

Note that Ĩ(P) is neither a left nor a right division algebra. In fact, both equations

a ∘ x = b  (18)

and

x ∘ a = b  (19)

have no solutions in Ĩ(P) if b(u, u) ≠ 0 for some u ∈ P (since (a ∘ x)(u, u) = (x ∘ a)(u, u) = 0 for any a, x ∈ Ĩ(P) and u ∈ P, by (12)). Even when (18) and (19) do have solutions, these will not be unique, in general. For example, equation x ∘ δ = 0 does not have a unique solution (since any x ∈ Ĩ(P) satisfies it by Proposition 4.2) even though δ ≠ 0. Similarly, the equation δ ∘ x = 0 does not have a unique solution since both x = δ and x = \overline{ξ} satisfy it, as can be easily checked.

We now need to introduce some notation. For t ∈ P we let

I_{t}(P) =^{def} Ĩ(P),

if t = 1, and

I_{t}(P) =^{def} ⋃_{r=1}^{t−1}(I_{r}(P) ∘ I_{t−r}(P)),

if t ≥ 2, (where A ∘ B =^{def} {a ∘ b : a ∈ A, b ∈ B} for A, B ⊆ Ĩ(P)). Equivalently, I_{t}(P) is the set of elements of Ĩ(P) that can be expressed as the twisted convolution of at least t elements of Ĩ(P) (associated in some way). We can now state and prove the main result of this section, which plays a fundamental role in the rest of this work.

Theorem 4.4 Let P be a locally finite poset, u, v ∈ P, u ≤ v, and f ∈ I_{t}(P) (t ∈ P). Then:

i) f(u, v) = 0 if ρ(u, v) ≤ t − 2;

ii) q^{⌊ \frac{t}{2} ⌋} divides f(u, v) if ρ(u, v) ≤ t − 1.

Proof. We prove the theorem by induction on t ∈ P. Both i) and ii) clearly hold if t = 1. So let f ∈ I_{t}(P) with t ≥ 2. Then, by definition, there exist r, s ∈ [t − 1] and g ∈ I_{r}(P), h ∈ I_{s}(P) such that f = g ∘ h and r + s = t. Hence we have that

f(u, v) = ∑_{u≤a<v} g(u, a)U_{\frac{ρ(a,v)+1}{2}} (\overline{h}(a, v)) .

Consider now a ∈ [u, v). If ρ(u, a) ≤ r−2 then, by i) of our induction hypothesis, we conclude that g(u, a) = 0. If ρ(a, v) ≤ s − 1 then, by ii) of our induction hypothesis, we conclude that q^{⌊ \frac{s}{2} ⌋} divides h(a, v), which implies that deg(\overline{h}(a, v)) ≤ ρ(a, v)− ⌊\frac{s}{2}⌋ ≤ ρ(a, v) − ⌊\frac{ρ(a,v)+1}{2}⌋ < ⌈\frac{ρ(a,v)+1}{2}⌉, and hence that U_{\frac{ρ(a,v)+1}{2}} (\overline{h}(a, v)) = 0. Therefore

f(u, v) = ∑_{\{a∈[u,v):ρ(u,a)≥r−1, ρ(a,v)≥s\}} g(u, a)U_{\frac{ρ(a,v)+1}{2}} (\overline{h}(a, v)).

Now, if ρ(u, v) ≤ t − 2 then {a ∈ [u, v) : ρ(u, a) ≥ r − 1, ρ(a, v) ≥ s} = ∅, and hence i) and ii) hold. If ρ(u, v) = t − 1 then

{a ∈ [u, v) : ρ(u, a) ≥ r − 1, ρ(a, v) ≥ s} = {a ∈ [u, v) : ρ(u, a) = r − 1},

and hence

f(u, v) = ∑_{\{a∈[u,v): ρ(u,a)=r−1\}} g(u, a)U_{\frac{s+1}{2}} (q^{s}h(a, v) (\frac{1}{q})) .  (20)

But, since ρ(u, a) = r − 1, we conclude from ii) of our induction hypothesis that q^{⌊ \frac{r}{2} ⌋} divides g(u, a). Hence q^{⌊ \frac{r}{2} ⌋+⌈ \frac{s+1}{2} ⌉} divides every summand on the RHS of (20). Since ⌊\frac{r}{2}⌋ + ⌈\frac{s+1}{2}⌉ ≥ ⌊\frac{r+s}{2}⌋ = ⌊\frac{t}{2}⌋ we conclude that ii) holds also in this case. This concludes the induction step and hence the proof. □

The preceding theorem has the following consequence. (We refer the reader to, e.g., [11, Chapter II, §2, p.17], for the definition and main properties of solvable algebras.)

Corollary 4.5 Let P be a finite poset. Then Ĩ(P) is a nilpotent algebra. In particular, Ĩ(P) is solvable.

Proof. Let d be the rank of P. Then it follows from part i) of Theorem 4.4 that I_{d+2}(P) = 0 and this, by the definition of I_{t}(P), means that Ĩ(P) is nilpotent. The second statement follows immediately from the first one. □

5 The enlarged algebra

One of the most useful operations in the (usual) incidence algebra of a poset is that of taking inverses of invertible elements. This is of course impossible in the twisted incidence algebra since it doesn’t have an identity. However, given any nonassociative algebra U without identity there is a standard way (see, e.g., [11], Chapter II, §1, p. 11) to enlarge U to a nonassociative algebra U_{1} so that U_{1} has an identity, contains an ideal I isomorphic to U, and U_{1}/I is a one-dimensional vector space. In this section we apply this construction to the twisted incidence algebra Ĩ(P), and characterize and study the invertible elements in the resulting algebra.

Let Î(P) be the R-algebra consisiting of formal sums of the form

α + f

where α ∈ R and f ∈ Ĩ(P), with sum and product defined in the natural ways (see, e.g., [11], Chapter II, §1, p. 11), namely

(α + f) + (β + g) =^{def} (α + β) + (f + g)

and

(α + f) ∘ (β + g) =^{def} (αβ) + (αg + βf + f ∘ g),

for α, β ∈ R, and f, g ∈ Ĩ(P). It is then clear that 1 + 0 is a two-sided identity for Î(P), and that {α + f ∈ Î(P) : α = 0} is an ideal of Î(P) isomorphic to Ĩ(P). Note that Î(P) is not a nilpotent algebra since it has a two-sided identity.

Our main goal in this section is to characterize and study the invertible elements of Î(P).

Theorem 5.1 Let α + f ∈ Î(P). Then the following are equivalent:

i) there exists a unique left inverse of α + f in Î(P);

ii) there exists a unique right inverse of α + f in Î(P);

iii) α ≠ 0.

Proof. It is clear that either i) or ii) imply iii). Assume now that iii) holds. Note that (αδ + \overline{Df})(u, u) = α ≠ 0 for all u ∈ P and hence that αδ + \overline{Df} is invertible in I(P; R[q]). We now define

g =^{def} −\frac{f}{α}(αδ + \overline{Df})^{−1}.  (21)

It is then clear that g ∈ Ĩ(P) and that, by Proposition 3.1,

\frac{f}{α} + αg + g ∘ f = \frac{f}{α} + αg + g\overline{Df} = \frac{f}{α} + g(αδ + \overline{Df}) = 0.

Hence \frac{1}{α} + g is a left inverse of α + f in Î(P). To prove that this left inverse is unique let β + h ∈ Î(P) be such that (β + h) ∘ (α + f) = 1 + 0. Then β = \frac{1}{α} and hence \frac{1}{α}f + αh + h ∘ f = 0. This, by Proposition 3.1, implies that h(αδ + \overline{Df}) = −\frac{f}{α} and hence, by (21), that h = g. This proves i).

We now show that iii) implies ii). We define an element g ∈ Ĩ(P) inductively as follows. We let

g(u, v) =^{def} −\frac{1}{α^{2}} f(u, v)  (22)

if u = v, and

g(u, v) =^{def} \frac{1}{α^{2}} A(u, v) − \frac{f(u, u)}{α^{3}}U_{\frac{ρ(u,v)+1}{2}} (\overline{A}(u, v)),  (23)

where

A(u, v) =^{def} −f(u, v) − α ∑_{u<a<v} f(u, a)U_{\frac{ρ(a,v)+1}{2}} (\overline{g}(a, v)),  (24)

if u < v (u, v ∈ P). Then we have that

(f ∘ g)(u, u) + \frac{1}{α}f(u, u) + αg(u, u) = 0  (25)

for all u ∈ P, and α^{2}g(u, v) + αf(u, u)U_{\frac{ρ(u,v)+1}{2}} (\overline{g}(u, v))

= A(u, v) − \frac{f(u, u)}{α} U_{\frac{d+1}{2}} (\overline{A}(u, v)) + \frac{f(u, u)}{α}

U_{\frac{d+1}{2}} (\overline{A}(u, v) − \frac{f(u, u)}{α}D_{\frac{d−1}{2}} (A(u, v))) = A(u, v)

(where d =^{def} ρ(u, v)) for all u < v, u, v ∈ P. By (24) and our definition (12) this implies that

αg(u, v) + \frac{1}{α}f(u, v) = −(f ∘ g)(u, v)  (26)

for all u, v ∈ P, u < v. Hence we conclude from (25) and (26) that αg+ \frac{1}{α}f +f ∘g = 0 and hence that (α + f) ∘ (\frac{1}{α} + g) = 1 + 0 in Î(P).

Now let β + h ∈ Î(P) be such that (α + f) ∘ (β + h) = 1 + 0 in Î(P). Then we have that β = \frac{1}{α} and

\frac{1}{α}f + αh + f ∘ h = 0.  (27)

Hence we deduce from (27) that

\frac{1}{α}f(u, u) = −αh(u, u),  (28)

for all u ∈ P, and that

α^{2}h(u, v) + αf(u, u)U_{\frac{ρ(u,v)+1}{2}} (\overline{h}(u, v)) = B(u, v)  (29)

where

B(u, v) =^{def} −f(u, v) − α ∑_{u<a<v} f(u, a)U_{\frac{ρ(a,v)+1}{2}} (\overline{h}(a, v)),  (30)

for all u, v ∈ P, u < v. Therefore we deduce from (29) that

α^{2}\overline{h}(u, v) + αf(u, u)D_{\frac{ρ(u,v)−1}{2}} (h(u, v)) = \overline{B}(u, v)

and hence that

α^{2}U_{\frac{ρ(u,v)+1}{2}} (\overline{h}(u, v)) = U_{\frac{ρ(u,v)+1}{2}} (\overline{B}(u, v)).  (31)

Substituting (31) in (29) we obtain that

α^{2}h(u, v) + \frac{f(u, u)}{α}U_{\frac{ρ(u,v)+1}{2}} (\overline{B}(u, v)) = B(u, v).  (32)

But from (22), (28), (23), (32), (24) and (30) we now conclude, by induction on ρ(u, v), that h(u, v) = g(u, v) for all u, v ∈ P, u ≤ v, and this concludes the proof. □

Note that the proof of the preceding theorem actually gives an explicit formula for the computation of the left inverse of an invertible element of Î(P). For this reason, we now concentrate mainly on the computation of the right inverse.

Given f ∈ I(P; R[q]) and i ∈ P we define an element f^{∘i} ∈ I(P; R[q]) inductively as follows. We let

f^{∘i} =^{def} \{ \begin{matrix}f, & if i = 1, \\ f ∘ (f^{∘(i−1)}), & if i ≥ 2. \end{matrix}  (33)

Proposition 5.2 Let α + f ∈ Î(P), with α ≠ 0. Then \frac{1}{α} + \frac{1}{α} ∑_{i≥1} (\frac{f}{α})^{∘i} is the (unique) right inverse of α − f in Î(P).

Proof. Note first that ∑_{i≥1} (\frac{f}{α})^{∘i} converges by Theorem 4.4. Therefore, from Proposition 3.3 we conclude that

f ∘ (\frac{1}{α} ∑_{i≥1} (\frac{f}{α})^{∘i}) = ∑_{i≥1} (\frac{f}{α})^{∘i} − \frac{f}{α}

and hence that

(α − f) ∘ (\frac{1}{α} + \frac{1}{α} ∑_{i≥1} (\frac{f}{α})^{∘i}) = 1 + 0  (34)

in Î(P), and the result follows from Theorem 5.1. □

Note that Proposition 5.2 gives an alternative proof of the existence of a right inverse of an element α + f ∈ Î(P) with α ≠ 0. However, we feel that the inductive procedure used in the proof of Theorem 5.1 is of independent interest and for this reason we have decided to present it.

Proposition 5.2 makes it natural to look in more detail at the operation of “taking the i-th power” in the twisted incidence algebra. Let f ∈ Ĩ(P) and i ∈ P. For a multichain a_{0} ≤ a_{1} ≤ … ≤ a_{i} in P we define a polynomial f_{a_{0},...,a_{i}}(q) ∈ R[q] inductively as follows. We let

f_{a_{0},...,a_{i}}(q) =^{def} f_{a_{0},a_{1}}(q)U_{\frac{d+1}{2}} (q^{d}f_{a_{1},...,a_{i}} (\frac{1}{q}))  (35)

(where d =^{def} ρ(a_{1}, a_{i})), if i ≥ 2, and

f_{a_{0},...,a_{i}}(q) =^{def} f(a_{0}, a_{1})  (36)

if i = 1. We call f_{a_{0},...,a_{i}}(q) the f-polynomial of the multichain a_{0} ≤ a_{1} ≤ … ≤ a_{i}. The f-polynomial of a multichain shares many of the properties of the R-polynomial of a multichain (which is a special case, see §6 for details) first defined and studied in [3]. In fact, most of the results in §3 of [3] continue to hold for the f-polynomial of a multichain. In particular, the reader can check that the following results hold, with essentially the same proofs as those given in §3 of [3].

Proposition 5.3 Let f ∈ Ĩ(P), and a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} (r ∈ P) be a multichain in P such that f_{a_{0},a_{1},...,a_{r+1}}(q) ≠ 0. Then ρ(a_{r}, a_{r+1}) ≥ 1 and ρ(a_{i}, a_{i+1}) ≥ 2 for i = 1, …, r − 1. □

Proposition 5.4 Let f ∈ Ĩ(P), k ∈ Z, and a_{0} ≤ a_{1} ≤ … ≤ a_{r+1} (r ∈ P) be a multichain in P. Then

[q^{k}](f_{a_{0},a_{1},...,a_{r+1}}) = ∑_{j_{1}≥⌈\frac{l(a_{1})+1}{2}⌉} … ∑_{j_{r}≥⌈\frac{l(ar)+1}{2}⌉} ∏_{i=0}^{r}[q^{l(a_{i})−j_{i}−j_{i+1}}](f(a_{i}, a_{i+1}))

where l(a_{j}) =^{def} ρ(a_{j}, a_{r+1}) for j = 0, …, r, j_{r+1} =^{def} 0, and j_{0} =^{def} l(a_{0}) − k. □

From our present point of view, the most important property of the f-polynomial of a multichain is the following.

Proposition 5.5 Let f ∈ Ĩ(P). Then

f^{∘i}(u, v) = ∑_{u=a_{0}≤a_{1}≤...≤a_{i}=v} f_{a_{0},a_{1},...,a_{i}}(q)  (37)

for all i ∈ P and u, v ∈ P, u ≤ v.

Proof. We prove (37) by induction on i ∈ P. If i = 1 then (37) holds by the definitions (33) and (36). So suppose that i ≥ 2. Then by (33), (12), and our induction hypothesis we have that

f^{∘i}(u, v) = (f ∘ f^{∘(i−1)})(u, v)
= ∑_{u≤a≤v} f(u, a)U_{\frac{ρ(a,v)+1}{2}} (q^{ρ(a,v)}f^{∘(i−1)}(a, v) (\frac{1}{q}))
= ∑_{u≤a≤v} f(u, a)U_{\frac{ρ(a,v)+1}{2}} (q^{ρ(a,v)} ∑_{a=a_{1}≤a_{2}≤...≤a_{i}=v} f_{a_{1},...,a_{i}} (\frac{1}{q}))
= ∑_{u=a_{0}≤a_{1}...≤a_{i}=v} f_{a_{0},a_{1}}(q)U_{\frac{ρ(a_{1},v)+1}{2}} (q^{ρ(a_{1},v)}f_{a_{1},...,a_{i}} (\frac{1}{q}))

and (37) follows from (35). □

We can therefore reformulate Proposition 5.2 in the following more explicit way.

Proposition 5.6 Let α + f ∈ Î(P) with α ≠ 0, and \frac{1}{α} + g ∈ Î(P) be the (unique) right inverse of α − f in Î(P). Then, for all u, v ∈ P, u ≤ v,

g(u, v) = \frac{1}{α} ∑_{C∈M(u,v)} (\frac{f}{α})_{C}  (38)

where M(u, v) denotes the set of all the multichains in P from u to v. □

Note that, by Proposition 5.3, the sum on the right hand side of (38) is actually finite.

Propositions 5.3 and 5.5 can also be used to show in a quick way that Ĩ(P) is never a Jordan algebra. In fact, if Ĩ(P) were a (noncommutative) Jordan algebra then we would have that (f ∘g)∘(f^{∘2}) = f ∘(g∘f^{∘2}) for all f, g ∈ Ĩ(P). In particular, it would be true that (ξ^{∘2}) ∘ (ξ^{∘2}) = ξ^{∘4}. Now let u, v ∈ P, u < v, be such that ρ(u, v) = 4. Then by Propositions 5.3 and 5.5 we have that (ξ^{∘4})(u, v) = 0. On the other hand

(ξ^{∘2} ∘ ξ^{∘2})(u, v) = ∑_{u≤a<v} ( ∑_{u≤y<a} q^{ρ(y,a)}) U_{\frac{ρ(a,v)+1}{2}} (q^{ρ(a,v)} ∑_{a≤x<v} q^{−ρ(x,v)})
= ∑_{\{u≤y<a≤x<v: ρ(a,x)≥ \frac{1}{2} (ρ(a,v)+1)\}} q^{ρ(y,x)}
= αq^{3},

where α = |{(a, x) ∈ Int(P) : a, x ∈ [u, v], ρ(u, a) = 1, ρ(a, x) = 2}|.

We conclude this section with the following slightly surprising result which will be used in §6.

Proposition 5.7 Let f, g ∈ Ĩ(P) be such that (1 − f) ∘ (1 + g) = 1 + 0 in Î(P). Then the following are equivalent:

i) f(u, u) = 1 for all u ∈ P and f\overline{f} = δ;

ii) g ∈ I_{\frac{1}{2}} (P).

Proof. Assume that i) holds. By our hypothesis we know that

− f + g − f ∘ g = 0.  (39)

Hence if u ∈ P then from (39) we conclude that

g(u, u) = f(u, u) = 1.  (40)

We now prove that

deg(g(u, v)) ≤ \frac{1}{2}(ρ(u, v) − 1)  (41)

for all u, v ∈ P, u < v, by induction on ρ(u, v). If ρ(u, v) = 1 then u < v and hence we conclude from (39) that

f(u, v) = g(u, v) − U_{1}(\overline{g}(u, v)).  (42)

But since f\overline{f} = δ we also have that f(u, v) + \overline{f}(u, v) = 0, and this, using (42) and the fact that f, g ∈ Ĩ(P), implies that deg(g(u, v)) = 0. Now let ρ(u, v) ≥ 2 and assume that

deg(g(x, y)) ≤ \frac{1}{2}(ρ(x, y) − 1)  (43)

for all x, y ∈ P, x < y, with ρ(x, y) < ρ(u, v). Then from (39) and (14) we conclude that

−f(x, y) + g(x, y) = (f\overline{g})(x, y) − f(x, y)

for all x, y ∈ P, x < y, such that ρ(x, y) < ρ(u, v). Hence, in particular,

(f\overline{g})(x, v) = g(x, v)

for all u < x ≤ v. By the generalized Dehn-Sommerville equations for the P^{∗}-kernel f^{∗} applied to the finite poset [u, v]^{∗} (see Lemma 2.2) we then conclude that the polynomial

(f\overline{g})(u, v) − \overline{g}(u, v)

is antisymmetric with respect to ρ(u, v). On the other hand, we have from (39), (12), and (43), that

− f(u, v) + g(u, v) = ∑_{u≤a<v} f(u, a)U_{\frac{ρ(a,v)+1}{2}} (\overline{g}(a, v))
= U_{\frac{ρ(u,v)+1}{2}} (\overline{g}(u, v)) + ∑_{u<a<v} f(u, a)\overline{g}(a, v),

which implies that

g(u, v) − U_{\frac{ρ(u,v)+1}{2}} (\overline{g}(u, v)) = (f\overline{g})(u, v) − \overline{g}(u, v).

Hence the polynomial g(u, v) − U_{\frac{ρ(u,v)+1}{2}} (\overline{g}(u, v)) is antisymmetric with respect to ρ(u, v), and this implies that deg(g(u, v)) ≤ \frac{1}{2}(ρ(u, v) − 1). This concludes the induction step and hence proves ii).

Assume now that ii) holds. Then it follows immediately from the explicit formula (21) for the left inverse of an invertible element of Î(P) that

f = g(δ + \overline{Dg})^{−1} = g(δ + \overline{g} − δ)^{−1} = g(\overline{g})^{−1}

and i) follows. □

6 P -kernels and KLS-functions

In this section we prove the main result of this work. This gives a non-recursive formula for the KLS-function of P relative to a P -kernel K in terms of the kernel itself. We then show how this result generalizes and unifies previously known results on Kazhdan-Lusztig polynomials and inverse Kazhdan-Lusztig polynomials, and how it yields new formulas for parabolic (and inverse parabolic) Kazhdan-Lusztig polynomials, for generalized h-vectors of Eulerian posets, and for Lusztig-Vogan polynomials.

The key step in the proof of the main result is the following one, which shows that the relationship between P -kernels and KLS-functions takes a particularly simple form in the enlarged incidence algebra.

Theorem 6.1 Let P be a locally finite poset, K ∈ Ĩ(P) a P -kernel, and f ∈ Ĩ(P). Then the following conditions are equivalent:

i) fK = \overline{f} and f ∈ I_{\frac{1}{2}} (P);

ii) (1 − \overline{K^{∗}}) ∘ (1 + f^{∗}) = 1 + 0 in Î(P^{∗}).

Proof. Assume first that i) holds. Then we have that K^{∗}f^{∗} = \overline{f^{∗}} in I(P^{∗}; R[q]) and f^{∗} ∈ I_{\frac{1}{2}} (P^{∗}). Therefore we have from Proposition 3.4 that \overline{K^{∗}} ∘ f^{∗} = \overline{K^{∗}} \overline{f^{∗}} − \overline{K^{∗}}. Hence

\overline{K^{∗}} ∘ f^{∗} = \overline{K^{∗} f^{∗}} − \overline{K^{∗}} = f^{∗} − \overline{K^{∗}}

and ii) follows.

Conversely, assume that ii) holds. Then, since K\overline{K} = δ, we have that \overline{K}^{∗}K^{∗} = δ in I(P^{∗}; R[q]). Therefore we conclude from our hypothesis ii) and Proposition 5.7 that f^{∗} ∈ I_{\frac{1}{2}} (P^{∗}) and hence that f ∈ I_{\frac{1}{2}} (P). This, by our hypothesis ii) and Proposition 3.4 implies that

f^{∗} = \overline{K^{∗}} + \overline{K^{∗}} ∘ f^{∗} = \overline{K^{∗}f^{∗}}

in I(P^{∗}; R[q]), and hence that \overline{f} = fK in I(P; R[q]), as desired. □

The preceding theorem, together with Theorem 5.1, implies the following result which generalizes Theorem 2.3.

Theorem 6.2 Let P be a locally finite poset and K ∈ I(P; R[q]) a P -kernel. Then there exists a unique K-totally acceptable element γ ∈ I_{\frac{1}{2}} (P). □

Note that we have not used Theorem 2.3 in our derivation of Theorem 6.2, but only basic properties of the twisted and enlarged incidence algebras. Extending the terminolgy used in the locally graded case we call the function γ defined by the previous theorem the KLS-function of P relative to the P -kernel K (the dependence on ρ being tacitly understood, if there is no danger of confusion).

The main result of this work is now an immediate consequence of Theorem 6.1 and Proposition 5.2.

Theorem 6.3 Let P be a locally finite poset, K a P -kernel, and γ the KLS-function of P relative to K. Then

γ^{∗} = ∑_{i≥1}(\overline{K^{∗}})^{∘i}.□

Although we have no applications for it, we feel that the following curious special case of Theorem 6.3 is worth noting.

Corollary 6.4 Let P be a locally finite poset, and f ∈ I_{\frac{1}{2}} (P). Then

f^{∗} = ∑_{i≥1}(f^{∗}\overline{f^{−1}}^{∗})^{∘i}.

Proof. It is clear that f^{−1}\overline{f} is a P -kernel and that f is (f^{−1}\overline{f})-totally acceptable. Since f ∈ I_{\frac{1}{2}} (P) we conclude from Theorem 6.2 that f is the KLS-function of P relative to f^{−1}\overline{f}, and the result follows from Theorem 6.3. □

Using Proposition 5.6 we can reformulate our main result in the following more explicit way.

Corollary 6.5 Let P be a locally finite poset, K a P -kernel, and γ the KLSfunction of P relative to K. Then, for all u, v ∈ P, u ≤ v,

γ(u, v) = ∑_{C∈M^{∗}(v,u)}(\overline{K^{∗}})_{C}

where M^{∗}(v, u) denotes the set of all the multichains in P^{∗} from v to u. □

It is interesting to note that the preceding corollary can be restated in the following equivalent way.

Corollary 6.6 Let P be a locally finite poset, K a P -kernel, and γ the KLSfunction of P relative to K. Then ,for all u, v ∈ P, u < v,

∑_{C∈C^{∗}(v,u)}(\overline{K^{∗}})_{C} = γ(u, v) − \overline{γ}(u, v)

where C^{∗}(v, u) denotes the set of all the chains in P^{∗} from v to u.

Proof. Let, for brevity,

Γ_{u,v} =^{def} ∑_{C∈C^{∗}(v,u)}(\overline{K^{∗}})_{C}.

Note first that, by Proposition 5.3, we may rewrite Corollary 6.5 as

γ(u, v) = ∑_{C∈C^{∗}(v,u)}((\overline{K^{∗}})_{C} + (\overline{K^{∗}})_{v,C}).  (44)

This, by the definitions (35) and (36), implies that

γ(u, v)(q) = Γ_{u,v}(q) + U_{\frac{ρ(u,v)+1}{2}} (q^{ρ(u,v)}Γ_{u,v} (\frac{1}{q})) .

Since γ ∈ I_{\frac{1}{2}} (P) this implies that

γ(u, v)(q) = D_{\frac{ρ(u,v)−1}{2}} (Γ_{u,v}(q))  (45)

and

0 = U_{\frac{ρ(u,v)}{2}} (Γ_{u,v}(q)) + U_{\frac{ρ(u,v)+1}{2}} (q^{ρ(u,v)}Γ_{u,v} (\frac{1}{q})) .  (46)

But it follows from (45) that

q^{ρ(u,v)}γ(u, v) (\frac{1}{q}) = U_{\frac{ρ(u,v)+1}{2}} (q^{ρ(u,v)}Γ_{u,v} (\frac{1}{q}))

so we conclude from (46) that

U_{\frac{ρ(u,v)}{2}} (Γ_{u,v}(q)) = −q^{ρ(u,v)}γ(u, v) (\frac{1}{q}) .  (47)

Now summing (45) and (47) yields the desired result. □

Note that Corollaries 6.5 and 6.6, although equivalent, yield different formulas for γ(u, v). In fact, from Corollary 6.6 we deduce that

γ(u, v) = ∑_{C∈C^{∗}(v,u)} D_{\frac{ρ(u,v)−1}{2}} ((\overline{K^{∗}})_{C})  (48)

if u < v. However, formulas (44) and (48) are different since, in general, D_{\frac{ρ(u,v)−1}{2}} ((\overline{K^{∗}})_{C}) ≠ (\overline{K^{∗}})_{C} + (\overline{K^{∗}})_{v,C}, as simple examples show.

In the rest of this section we show how known and new results on Kazhdan-Lusztig polynomials, inverse Kazhdan-Lusztig polynomials, generalized h-vectors, parabolic and inverse parabolic Kazhdan-Lusztig polynomials, and Lusztig-Vogan polynomials, follow from Corollary 6.5.

Let (W, S) be a Coxeter system, J ⊆ S, and P be W^{J} partially ordered by (strong) Bruhat order. For (u, v) ∈ Int(W^{J}) let ρ(u, v) =^{def} l(v)−l(u). It is then clear from the definition of Bruhat order that ρ is a weak rank function for W^{J}. Recall that given u, v ∈ W^{J}, u ≤ v, and x ∈ {−1, q}, we denote by R_{u,v}^{J,x}(q) (respectively, P_{u,v}^{J,x}(q)) the parabolic R-polynomial (respectively, parabolic Kazhdan-Lusztig polynomial) of u, v with respect to x. For each x ∈ {−1, q} we define two elements R_{J,x}, P_{J,x} ∈ Ĩ(W^{J}) by letting

R_{J,x}(u, v) =^{def} (−1)^{l(v)−l(u)}R_{u,v}^{J,x}(q),  (49)

and

P_{J,x}(u, v) =^{def} P_{u,v}^{J,x}(q),

for all u, v ∈ W^{J}, u ≤ v.

Corollary 6.7 Let (W, S) be a Coxeter system, J ⊆ S, x ∈ {−1, q}, and u, v ∈ W^{J}, u ≤ v. Then

P_{u,v}^{J,x}(q) = ∑_{C∈M(u,v)}(R_{J,q−1−x})_{C}(q)

where M(u, v) denotes the set of all the multichains in W^{J} from u to v.

Proof. It follows immediately from Proposition 2.6 and Theorem 2.5 that \overline{R_{J,q−1−x}}P_{J,x} = \overline{P_{J,x}} and that P_{J,x} ∈ I_{\frac{1}{2}} (W^{J}). Therefore (\overline{R_{J,q−1−x}})^{∗} is a (W^{J})^{∗}-kernel and (P_{J,x})^{∗} is the KLS-function of (W^{J})^{∗} relative to (\overline{R_{J,q−1−x}})^{∗}. The result follows from Corollary 6.5. □

Note that, as observed after Theorem 2.5, (−1)^{l(v)−l(u)} R_{∅,−1}(u, v) (= (−1)^{l(v)−l(u)}R_{∅,q}(u, v)) and P_{u,v}^{∅,−1}(q) (= P_{u,v}^{∅,q}(q)) are the R-polynomial and Kazhdan-Lusztig polynomial, respectively, of u, v ∈ W. Hence Corollary 6.7 reduces to Theorem 4.1 of [3] if J = ∅.

Given u, v ∈ W^{J}, u ≤ v, and x ∈ {−1, q} we define a polynomial Q_{u,v}^{J,x}(q) ∈ Z[q] by letting

Q_{u,v}^{J,x}(q) =^{def} (−1)^{l(v)−l(u)}(P_{J,x})^{−1}(u, v).  (50)

(note that P_{J,x} is invertible in I(W^{J}) by part ii) of Theorem 2.5). It then follows immediately from the above comments and from well known results (see, e.g., [9], p. 190) that Q_{u,v}^{∅,q}(q) (= Q_{u,v}^{∅,−1}(q)) is the inverse Kazhdan-Lusztig polynomial of u, v. For this reason we call Q_{u,v}^{J,x}(q) the inverse parabolic Kazhdan-Lusztig polynomial of u, v with respect to x. Given a multichain C = (a_{0}, …, a_{r}) we let C^{∗} =^{def} (a_{r}, …, a_{0}).

Corollary 6.8 Let (W, S) be a Coxeter system, J ⊆ S, x ∈ {−1, q}, and u, v ∈ W^{J}, u ≤ v. Then

Q_{u,v}^{J,x}(q) = ∑_{C∈M(u,v)}(R_{J,x}^{∗})_{C^{∗}}(q),

where M(u, v) has the same meaning as in Corollary 6.7.

Proof. We have seen in the proof of Corollary 6.7 that (\overline{R_{J,q−1−x}})^{∗} is a (W^{J})^{∗}-kernel and that (P_{J,x})^{∗} is the KLS-function of (W^{J})^{∗} relative to (\overline{R_{J,q−1−x}})^{∗}. This implies that R_{J,q−1−x} is a W^{J}-kernel and, by Proposition 8.1 of [14], that (P_{J,x})^{−1} is the KLS-function of W^{J} relative to R_{J,q−1−x}. Therefore from (50) and Corollary 6.5 we have that

(−1)^{l(v)−l(u)}Q_{u,v}^{J,x}(q) = ∑_{C∈M(u,v)}(\overline{R_{J,q−1−x}})_{C^{∗}}^{∗}(q).  (51)

But it follows from Proposition 2.6 and from (49) that (\overline{R_{J,q−1−x}})(a, b) = (−1)^{l(b)−l(a)} R_{J,x}(a, b) for all a, b ∈ W^{J}, a ≤ b. Hence the result follows from (51), (35), and (36). □

Note that it is very easy to see that, for any multichain C in W, (R_{∅,−1}^{∗})_{C^{∗}}(q) is the dual R-polynomial of C as defined in §7 of [3]. Therefore Corollary 6.8 coincides with Theorem 7.5 of [3] if J = ∅.

Let P be an Eulerian poset and l : P → N be its rank function. It is then obvious that ρ(u, v) =^{def} l(v) − l(u) is a weak rank function for P. We define two elements G, λ ∈ Ĩ(P) by letting

λ(u, v) =^{def} (q − 1)^{l(v)−l(u)}  (52)

and

G(u, v) =^{def} g([u, v]^{∗}; q)

(where g(P; q) is defined by (9)) for all u, v ∈ P, u ≤ v. Recall that given n ∈ P and S ⊆ [n] we denote by h_{S,n}(q) the polynomial defined by (4).

Corollary 6.9 Let P be an Eulerian poset of rank n + 1 (n ∈ N). Then

f(P^{∗}; q) = (−1)^{n} ∑_{S⊆[n]} α(P; S) h_{S,n}(q).  (53)

Proof. It follows from the definition (10) that

(q − 1)f([u, v]^{∗}; q) = ∑_{u<a≤v} g([a, v]^{∗}; q) (q − 1)^{l(a)−l(u)}

for all u, v ∈ P, u < v. On the other hand, by (9) and Theorem 2.4 of [13] we have that

(q − 1)f([u, v]^{∗}; q) = q^{l(v)−l(u)}g ([u, v]^{∗}; \frac{1}{q}) − g([u, v]^{∗}; q)  (54)

for all u, v ∈ P, u < v. Therefore λG = \overline{G} and since, by (9), G ∈ I_{\frac{1}{2}} (P) we conclude that λ^{∗} is a P^{∗}-kernel (a fact that also follows from Proposition 7.1 of [14]) and G^{∗} is the KLS-function of P^{∗} relative to λ^{∗}. Hence we have from (54) and Corollary 6.6 that

(1 − q) f(P^{∗}; q) = ∑_{C∈C}(\overline{λ})_{C}(q)  (55)

where C is the set of all the chains in P from ˆ0 to ˆ1. But it follows immediately from the definitions (2), (3), (35), (36), and (52), that

(\overline{λ})_{a_{0},...,a_{i}}(q) = (−1)^{l(a_{i})−l(a_{0})}ĝ_{l(a_{1})−l(a_{0}),...,l(a_{i})−l(a_{i−1})}(q)  (56)

for any multichain a_{0} ≤ a_{1} ≤ … ≤ a_{i} in P, so the result follows from (55), (56), and (4). □

The preceding corollary expresses the generalized h-vector of an Eulerian poset P as an explicit linear combination of the flag f-vector {α(P^{∗}; S)}_{S⊆[n]} of P^{∗} (or, equivalently, of P). For example, if n = 3 then we obtain from (2), (3), (4), and Corollary 6.9 that

f(P^{∗}; q) = (1 − 3q + 3q^{2} − q^{3})α(P; ∅) + (q^{3} − 3q^{2})α(P; {1})

+(q^{2} − q^{3})α(P; {2}) + (q^{3} − 2q^{2} + q)α(P; {3}) + q^{2}α(P; {1, 3}).

Other (different) formulas expressing the generalized h-vector of an Eulerian poset in terms of its flag f-vector have been obtained by M. Bayer and J. Fine (see [13, p. 191], and [1, §1.2], for details).

Note that if we multiply both sides of (53) by (1−q) and then apply the operator D\frac{n}{2} then, by (9), we obtain a formula for g(P^{∗}; q) in terms of the flag f-vector of P.

This formula is also explicit since the polynomials D\frac{n}{2} (ĝ_{α_{1},...,α_{r}}(q)) can be computed through simple recursions and have a combinatorial interpretation (see (2), (3), and Theorem 3.16 of [4]). On the other hand, if one uses (44) (i.e., Corollary 6.5) instead of Corollary 6.6 in the proof of Corollary 6.9 then one obtains the formula

g(P^{∗}; q) = (−1)^{n+1} ∑_{S⊆[n]} α(P; S)(ĝ_{s_{1},s_{2}−s_{1},...,n+1−s_{r}}(q) + ĝ_{0,s_{1},s_{2}−s_{1},...,n+1−s_{r}}(q))

(where s_{1} < s_{2} < … < s_{r} are the elements of S). The polynomials ĝ_{α_{1},...,α_{r}}(q) + ĝ_{0,α_{1},...,α_{r}}(q) have been introduced and studied in [4] (where they are denoted g_{α_{1},...,α_{r}}(q)). They also satisfy rather simple recursions (see Proposition 3.5 of [4]), but no combinatorial interpretation is known for them.

Let P be the set D defined in §2, partially ordered by the Bruhat G-order. Recall that, given γ, δ ∈ D, γ ≤ δ, we denote by R_{γ,δ}(q) the polynomial defined by part ii) of Theorem 2.7, and by P_{γ,δ}(q) the Lusztig-Vogan polynomial of γ, δ. We define two elements L, V ∈ Ĩ(D) by letting

L(γ, δ) =^{def} R_{γ,δ}(q)  (57)

and

V(γ, δ) =^{def} P_{γ,δ}(q)  (58)

for (γ, δ) ∈ Int(D).

Corollary 6.10 Let γ, δ ∈ D, γ ≤ δ. Then

P_{γ,δ}(q) = ∑_{C∈M(γ,δ)} L_{C}(q),

where M(γ, δ) is the set of all the multichains in D from γ to δ.

Proof. Note first that, by Lemma 5.9 of [15], ρ : Int(D) → N defined by

ρ(γ, δ) =^{def} l(δ) − l(γ)

for (γ, δ) ∈ Int(D) is a weak rank function for D. Furthermore, from part i) of Theorem 2.8 and Theorem 2.7 we conclude that

q^{−l(δ)} (∑_{γ≤δ} P_{γ,δ}(q)γ) = D (∑_{γ≤δ} P_{γ,δ}(q)γ)
= ∑_{γ≤δ} P_{γ,δ}(q^{−1})D(γ)
= ∑_{γ≤δ} P_{γ,δ}(q^{−1})q^{−l(γ)} ∑_{β≤γ} R_{β,γ}(q)β  (59)

in M, for all δ ∈ D. Equating coefficients on both sides of (59) therefore yields that

P_{β,δ}(q) = ∑_{β≤γ≤δ} R_{β,γ}(q)q^{ρ(γ,δ)}P_{γ,δ} (\frac{1}{q})

for all (β, δ) ∈ Int(D). By (57) and (58) this implies that L\overline{V} = V in I(D; R[q]), and hence that V^{∗}\overline{L^{∗}} = \overline{V^{∗}} in I(D^{∗}; R[q]). But parts ii) and iii) of Theorem 2.8 imply that V^{∗} ∈ I_{\frac{1}{2}} (D^{∗}), therefore \overline{L^{∗}} is a D^{∗}-kernel and V^{∗} is the KLS-function of D^{∗} relative to \overline{L^{∗}}. The thesis follows from Corollary 6.5. □ Acknowledgements I would like to thank Margaret Bayer, Louis Billera, George Lusztig, and Richard Stanley for useful comments, and Tony Springer for suggesting that the main result of [3] might generalize to the Lusztig-Vogan polynomials.

References

[1] M. Bayer, Face numbers and subdivisions of convex polytopes, Polytopes: Abstract, Convex and Computational (T. Bisztriczky et al., eds.), Kluwer Academic Pub., The Netherlands, 1994, 155-171.

[2] A. Björner, Orderings of Coxeter groups, Combinatorics and Algebra, Contemporary Math. vol. 34, Amer. Math. Soc. 1984, 175-195.

[3] F. Brenti, A combinatorial formula for Kazhdan-Lusztig polynomials, Invent. Math., 118 (1994), 371-394.

[4] F. Brenti, Combinatorial expansions of Kazhdan-Lusztig polynomials, J. London Math. Soc., to appear.

[5] V. Deodhar, On some geometric aspects of Bruhat orderings. II. The parabolic analogue of Kazhdan-Lusztig polynomials, J. Algebra, 111 (1987), 483-506.

[6] V. Deodhar, Duality in parabolic setup for questions in Kazhdan-Lusztig theory, J. Algebra, 142 (1991), 201-209.

[7] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, no.29, Cambridge Univ. Press, Cambridge, 1990.

[8] D. Kazhdan, G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math., 53 (1979), 165-184.

[9] D. Kazhdan, G. Lusztig, Schubert varieties and Poincaré duality, Geometry of the Laplace operator, Proc. Sympos. Pure Math. 34, Amer. Math. Soc., Providence, RI, 1980, pp. 185-203.

[10] G. Lusztig, D. Vogan Jr., Singularities of closures of K-orbits on flag manifolds, Invent. Math. 71 (1983), 365-379.

[11] R. D. Schafer, An Introduction to Nonassociative Algebras, Pure and Applied Mathematics, no.22, Academic Press, New York and London, 1966.

[12] R. P. Stanley, Enumerative Combinatorics , vol.1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.

[13] R. P. Stanley, Generalized h-vectors, intersection cohomology of toric varieties, and related results, Adv. Studies Pure Math., 11 (1987), 187-213.

[14] R. P. Stanley, Subdivisions and local h-vectors, J. Amer. Math. Soc., 5 (1992), 805-851.

[15] D. Vogan Jr., Irreducible characters of semisimple Lie groups III. Proof of Kazhdan-Lusztig conjecture in the integral case, Invent. Math. 71 (1983), 381-417.

Mathematical Sciences Research Institute 1000 Centennial Drive Berkeley, CA 94720-5070 U.S.A.