2006/07/12

Specializations and Extensions of the quantum MacMahon Master Theorem

Dominique Foata and Guo-Niu Han

ABSTRACT. We study some specializations and extensions of the quantum version of the MacMahon Master Theorem derived by Garoufalidis, Lê and Zeilberger. In particular, we obtain a (t, q)-analogue for the Cartier-Foata noncommutative version and a semi-strong (t, q)-analogue for the contextual algebra.

1. Introduction

The Master Theorem derived by MacMahon ([Ma15, vol. 1, p. 97], [Z85], [BR91, pp. 61-72]) is a fundamental result in Combinatorial Analysis and has had many applications. To state it in a context relevant to its further noncommutative extensions we use the following notations. Let r be a positive integer and 𝔸 the alphabet {1, 2, …, r}. A biword on 𝔸 is a 2 × n matrix α = \binom{x_{1}···x_{n}}{a_{1}···a_{n}} (n ≥ 0), whose entries are in 𝔸, the first (resp. second) row being called the top word (resp. bottom word) of α. The number n is the length of α; we write ℓ(α) = n. The biword α can also be viewed as a word of biletters \binom{x_{1}}{a_{1}} ⋯ \binom{x_{n}}{a_{n}}, those biletters \binom{x_{i}}{a_{i}} being pairs of integers written vertically with x_{i}, a_{i} ∈ 𝔸 for all i = 1, …, n. Let 𝔹 denote the set of biletters and B the set of all biwords.

For each word w = x_{1}x_{2} … x_{m} ∈ 𝔸^{m} let inv w designate the number of inversions in w, that is, the number of pairs (i, j) such that 1 ≤ i < j ≤ m and x_{i} > x_{j}. Also let \overline{w} = x_{j_{1}}x_{j_{2}} … x_{j_{m}} be the non-decreasing rearrangement of w. The q-Boson is defined to be the infinite sum

Bos(q) := ∑_{w} q^{inv w} (\overline{w} ; w)

over all words w from the free monoid 𝔸^{∗} generated by 𝔸. The q-Fermion is defined by

Ferm(q) := ∑_{J⊂𝔸}(−1)^{|J|} ∑_{σ∈𝔖_{J}}(−1)^{inv σ} (\begin{matrix}σ(i_{1}) & σ(i_{2}) & ⋯ & σ(i_{l}) \\ i_{1} & i_{2} & ⋯ & i_{l} \end{matrix}) ,

where J = {i_{1} < i_{2} < ⋯ < i_{l}} is a subset of 𝔸 of cardinality |J| = ℓ and 𝔖_{J} is the permutation group acting on J.

2000 Mathematics Subject Classification. Primary 05A19, 05A30, 16W35, 17B37.

Key words and phrases. Right quantum algebra, quantum MacMahon Master theorem, reduction system, Denert statistic.

When q = 1 and when the biletters \binom{x}{a} are assumed to commute, the original MacMahon Master Theorem (op. cit.) asserts that the identity

(qMM)  Ferm(q) × Bos(q) = 1

holds. In the further noncommutative versions of the MacMahon Master Theorem (for an arbitrary q or for q = 1) specific commutation rules for the biletters \binom{x}{a} must be set. For instance, in the Cartier-Foata version [CF69] the biletters \binom{x}{a} and \binom{y}{b} commute only if x ≠ y and with q = 1 the above relation holds in the large algebra of the so-called monoid generated by those commutation rules. Recently, Garoufalidis, Lê and Zeilberger have established another noncommutative version [GLZ05] (called “quantum Master Theorem”) by using difference-operator techniques developed by Zeilberger [Z80]. They have borrowed their commutation rules (see the reduction system (SR_{q}) below) from the classical theory of Quantum Groups. The (qMM)-identity holds in a quotient algebra derived by those commutation rules, called the q-right quantum algebra. The identity also holds in another quotient algebra called the 1-right quantum algebra. Those two identities were reproved in our previous paper [FH05b] using a different approach.

As other algebras previously introduced appear to be factor algebras of the q-right or 1-right quantum algebras, it is natural to determine whether the (qMM)-identity still hold in those algebras and in which form. We can then show that there is a true (t, q)-analogue of the Cartier-Foata noncommutative version (§ 6) and also a (qMM)-identity in the contextual algebra introduced in [Ha92] (§ 7).

The two right quantum algebras are defined by means of a reduction system (S) (see §§ 2, 3), which make it possible to construct an explicit leftmost reduction α ↦ [α]_{S} mapping each biword α onto a linear combination of so-called irreducible biwords. We say that there is a strong quantum Master Theorem, if the further identity [Ferm(q) × Bos(q)]_{S} = 1 holds. This means that if (FB)_{n} denotes the linear combination of all biwords of length n in the expansion of the product Ferm(q) × Bos(q), then (FB)_{0} = 1 and for every n ≥ 1 the expression (FB)_{n} can be reduced to zero by applying the leftmost reduction inductively.

Borrowing the theory from Bergman [Be78] we give the definition of a reduction system in section 2. In section 3 we recall the results on the (qMM)-identity that holds in the right quantum algebras in its weak and strong forms. Various factor algebras of the right quantum algebra are introduced in section 4. The list of results is presented in a table in section 5. The (t, q)-analogue of the classical Master Theorem is proved in section 6. Finally, we discuss in section 7 what we mean by semi-strong analogue of the Master Theorem for the contextual algebra.

2. Reduction system and quotient algebra

Let ℤ be the ring of all integers and ℤ[q, q^{−1}] the ring of polynomials in the variables q, q^{−1} submitted to the rule qq^{−1} = 1 with integral coefficients. The set A = ℤ⟨⟨B⟩⟩ of the formal sums ∑_{α} c(α)α, where α ∈ B and c(α) ∈ ℤ, together with the above biword multiplication, the free addition and the free scalar product, forms an algebra over ℤ, called the free biword large ℤ-algebra. Similarly, let A_{q} = ℤ[q, q^{−1}]⟨⟨B⟩⟩ denote the large ℤ[q, q^{−1}]-algebra of the formal sums ∑_{α} c(α)α with c(α) ∈ ℤ[q, q^{−1}] for all α ∈ B. The subset of the finite formal sums is a subalgebra denoted by ℤ[q, q^{−1}]⟨B⟩. The formal sums ∑_{α} c(α)α in all those algebras are called expressions.

Following Bergman’s method [Be78] each finite set of pairs (α, E_{α}) ∈ B × ℤ[q, q^{−1}]⟨B⟩ such that the first components α are distinct is called a reduction system. Let F (S) = {α | (α, E_{α}) ∈ S}. With S we can associate an oriented graph G = (B, E) defined as follows. The set of vertices is the set B of all biwords. There is an oriented edge from β to β′ if the following two conditions hold:

(1) there is a factorization β = β_{1}αβ_{2} such that β_{1}, α, β_{2} ∈ B with α ∈ F (S);

(2) β′ occurs in the expansion of the expression β_{1}E_{α}β_{2} with a non zero coefficient.

We assume that all positively oriented paths in the graph G terminate. This assumption, usually called the descending chain condition (see [Be78]), is assumed to hold for all reduction systems defined in the sequel.

A biword β is said to be irreducible if each factor α of β is not a first component of S. The set of irreducible biwords is denoted by B_{irr}(S). An expression ∑_{α} c(α)α is said to be irreducible if c(α) = 0 for all α ∉ B_{irr}. The set of irreducible expressions is denoted by A_{irr}(S). Associated with the reduction system S a linear mapping [ ]_{S} : E ↦ [E]_{S} of A_{q} onto the A_{irr}(S), called the leftmost-reduction, is defined by the following axioms:

(C1) The leftmost-reduction is ℤ[q, q^{−1}]-linear, i.e. for E_{1}, E_{2} ∈ A_{q} and c_{1}, c_{2} ∈ ℤ[q, q^{−1}] we have [c_{1}E_{1} + c_{2}E_{2}]_{S} = c_{1}[E_{1}]_{S} + c_{2}[E_{2}]_{S};

(C2) For every β ∈ B_{irr}(S) we have [β]_{S} = β;

(C3) For every (α, E_{α}) ∈ S we have [α]_{S} = E_{α};

(C4) Let β ∉ B_{irr} be a reducible biword, so that β can be factorized in a unique manner as β = β_{1}β_{2}\binom{x}{a}β_{3}, where β_{1}, β_{2}, β_{3} ∈ B, \binom{x}{a} ∈ 𝔹, β_{1}β_{2} ∈ B_{irr} and β_{2}\binom{x}{a} ∈ F (S). Then [β]_{S} = [ β_{1} [β_{2}\binom{x}{a}]_{S} β_{3}]_{S}.

Although the leftmost-reduction is recursively defined, it is well defined. Starting with a biword β and applying (C3) finitely many times an irreducible expression is derived (this is the descending chain condition, true by assumption). When the biword β has more than one factor α ∈ F (S), condition (C4) says that condition (C3) must be applied at the occurrence of the leftmost factor α. Consequently, the final irreducible expression is unique.

Some reduction systems in the sequel will satisfy the further condition: (C5) Let β ∈ B be a biword and β = β_{1}β_{2}β_{3} be any factorization where

β_{1}, β_{2}, β_{3} ∈ B. Then [β]_{S} = [ β_{1} [β_{2}]_{S} β_{3}]_{S}.

A reduction system S is said to be reduction-unique if it satisfies condition (C5).

In practice, a reduction system is written as the set of equations (or commutation relations) {α = E_{α}}. Let I(S) be the two-sided ideal of A_{q} generated by the elements (α − E_{α}) such that (α, E_{α}) ∈ S. Our main algebraic structure is the quotient algebra U(S) = A_{q}/I(S), that will be studied for several reduction systems.

3. Master Theorems on the right quantum algebra

The reduction system SR is defined by

(SR)  \{ \begin{matrix}\binom{xy}{aa} = \binom{yx}{aa}, & (x > y, all a); \\ \binom{xy}{ab} = \binom{yx}{ba} + \binom{yx}{ab} − \binom{xy}{ba}, & (x > y, a > b). \end{matrix}

The quotient algebra R := U(SR) = A_{q}/I(SR) is called the 1-right quantum algebra.

Theorem 1 (1-quantum Master Theorem). The following identity holds:

Ferm(1) × Bos(1) ≡ 1 (mod I(SR)).

The above Theorem was first proved in [GLZ05]. We can find another proof in [FH05b].

Theorem 2 (Strong 1-quantum Master Theorem). The following identity holds:

[Ferm(1) × Bos(1)]_{SR} = 1,

where [ ]_{SR} is the leftmost-reduction associated with the reduction system (SR).

This Theorem was proved in [FH05a] and is based on the following property.

Theorem 3 (Reduction-uniqueness). The reduction system SR is reduction-unique.

The above definitions and results have the following q-analogues. Consider the reduction system

(SR_{q})  \{ \begin{matrix}\binom{xy}{aa} = q\binom{yx}{aa}, & (x > y, all a); \\ \binom{xy}{ab} = \binom{yx}{ba} + q\binom{yx}{ab} − q^{−1}\binom{xy}{ba}, & (x > y, a > b). \end{matrix}

The quotient algebra R_{q} := U(SR_{q}) = A_{q}/I(SR_{q}) is called the q-right quantum algebra.

Theorem 1q (q-quantum Master Theorem). We have the following identity:

Ferm(q) × Bos(q) ≡ 1 (mod I(SR_{q})).

This Theorem was first proved in [GLZ05]. We can find another proof in [FH05a] by using the “1 = q” principle. For each biword \binom{u}{v} define the statistic “inv^{−}” by

inv^{−}\binom{u}{v} = inv(v) − inv(u).

Notice that “inv^{−}” may be negative. The “1 = q” principle is based on the weight function ϕ defined for each biword α by ϕ(α) = q^{inv^{−}(α)}α and extended to all of A_{q} by linearity. A circuit is defined to be a biword whose top word is a rearrangement of the letters of its bottom word. An expression E = ∑_{α} c(α)α is said to be circular if c(α) = 0 except when α is circular.

Theorem 4 (“1 = q” principle). We have

ϕ([E]_{SR}) = [ϕ(E)]_{SR_{q}} for E ∈ A_{q};
ϕ(EF) = ϕ(E)ϕ(F) if E and F are two circular expressions.

As proved in [FH05a], Theorems 3 and 1q imply the following theorem.

Theorem 2q (Strong q-quantum Master Theorem). We have

[Ferm(q) × Bos(q)]_{SR_{q}} = 1,

where [ ]_{SR_{q}} is the leftmost-reduction associated with the reduction system (SR_{q}).

4. Factor algebras of the right quantum algebra Let S be a reduction system and let U(S) = A_{q}/I(S) be the quotient

algebra as defined in section 2. If the commutation relations α = E_{α} derived from the reduction system SR (resp. SR_{q}) hold whenever the commutation relations α′ = E′_{α′} derived from S hold, then U(S) is a factor algebra of R (resp. of R_{q}). We examine several subalgebras U(S) of R and R_{q} derived by specific reduction systems S. In most cases the implication {α′ = E′_{α′}} ⇒ {α = E_{α}} is immediate.

(a) The commutative algebra M = U(SM) is defined by means of the reduction system

(SM)  \binom{xy}{ab} = \binom{yx}{ba} (x > y, all a, b).

This means that all biletters commute. The algebra M is a factor algebra of R. The original Master Theorem identity due to MacMahon [Ma15] holds in M (see also [Ca72]).

(b) The Cartier-Foata algebra F = U(SF) is defined by means of the reduction system

(SF)  \binom{xy}{ab} = \binom{yx}{ba} (x > y).

The algebra F was first considered by Cartier and Foata [CF69]. It is a factor algebra of R. A version of F was also used in [Fo65] to derive a noncommutative version of the MacMahon Master Theorem.

(c) The Cartier-Foata q-algebra F_{q} = U(SF_{q}) is a q-version of the previous algebra. It is defined by means of the reduction system

(SF_{q})  \{ \begin{matrix}\binom{xy}{ab} = \binom{yx}{ba}, & if x > y and a > b; \\ \binom{xy}{ab} = q\binom{yx}{ba}, & if x > y and a = b; \\ \binom{xy}{ab} = q^{2}\binom{yx}{ba}, & if x > y and a < b. \end{matrix}

The algebra F_{q} is a factor algebra of R_{q}.

(d) The quantum algebra Q_{q} = U(SQ_{q}) can only be defined in its qversion (see, for example, [PW91]). The underlying reduction system is given by

(SQ_{q})  \{ \begin{matrix}\binom{xy}{aa} = q\binom{yx}{aa}, & if x > y; \\ \binom{xx}{ab} = q\binom{xx}{ba}, & if a > b; \\ \binom{xy}{ab} = \binom{yx}{ba}, & if x > y and a < b; \\ \binom{xy}{ab} = \binom{yx}{ba} + (q − q^{−1})\binom{yx}{ab}, & if x > y and a > b. \end{matrix}

Notice that Q_{q} is a factor algebra of R_{q} and Q_{q}|_{q=1} = M.

(e) The contextual algebra H = U(SH) is defined by the reduction system [Ha92]

(SH)  \{ \begin{matrix}\binom{xy}{ab} = \binom{yx}{ab}, & if x > y and V (x, y, a, b) > 0; \\ \binom{xy}{ab} = \binom{yx}{ba}, & if x > y and V (x, y, a, b) < 0; \end{matrix}

where V (x, y, a, b) = (a − x − 1/2)(a − y − 1/2)(b − x − 1/2)(b − y − 1/2). In Proposition 6 we show that the relations displayed in (SH) imply the relations displayed in (SR). The algebra H is then a factor algebra of R. By convention, we define the q-version of H as being H_{q} = H itself. Therefore, H_{q} is not a factor algebra of Q_{q}.

5. List of results

In sections 2 and 3 we have stated six theorems: Theorem 1—Theorem 4 and Theorem 1q, Theorem 2q. They all relate to the algebras R or R_{q} (see the last row in the following table). On the other hand, three factor algebras M, F, H of R and two factor algebras Q_{q}, F_{q} of R_{q} have been introduced. Our purpose is to state and prove, whenever possible, the analogues of those theorems for those factor algebras. As can be seen in the table twenty-six statements are to be made. Each of them refers to an algebra (the row index) and a Theorem (the column index).

Th.1 Th.2 Th.3 Th.4 Th.1q Th.2q
M  ⊗^{(7)} ⊗^{(15)} ⊗^{(11)} −  −  −  −
Q = M ⊗^{(8)} ⊗^{(16)} ⊗^{(13)} −  ⊗^{(17)} ⊗^{(21)}  Q_{q}
F  ⊗^{(9)} ⊗^{(14)} ⊗^{(12)} ⊗^{(18)} ⊗^{(19)} ⊗^{(20)}  F_{q}
H  ⊗^{(10)} −^{(23)} −^{(22)} ⊗^{(24)} ⊗^{(25)} ⊘^{(26)}  H_{q} = H
R  ⊗^{(1)} ⊗^{(5)} ⊗^{(3)} ⊗^{(4)} ⊗^{(2)} ⊗^{(6)}  R_{q}

Comments on the content of the table:

(1) This is Theorem 1 (quantum Master Theorem), first proved in [GLZ05] and reproved in [FH05b].

(2) This q-version of the quantum Master Theorem for the right quantum algebra can be deduced from (1) and the “1 = q” principle (4) [FH05a].

(3) See [FH05a].

(4) See [FH05a]. The weight function for the “1 = q” principle is “inv^{−}”.

(5) This is Theorem 2 (strong 1-quantum Master Theorem). It can be deduced from (1) and (3) (see [FH05a]).

(6) This q-version of the strong quantum Master Theorem for the right quantum algebra can be deduced from (2) and (3).

(7-10) All those theorems are corollaries of (1) because M, Q, F, H are all factor algebras of R. Also, notice that (7) = (8).

(11-12) The bases of those two algebras are easy to construct

(13) See Parshall and Wang [PW91] in its q-version. If q = 1, then (13) = (11).

(14) See Foata [Fo65] and Cartier-Foata [CF69]. It can be deduced from (9) and (12).

(15-16) As q = 1 for those two cases, we have (15) = (16). The result can be deduced from (7) and (11).

(17) This is a corollary of (2). Notice that it cannot be deduced from (8) because of the lack of any “1 = q” principle for Q. See [GLZ05].

(18) See section 6 in this paper. The weight function is “inv^{−}”.

(19) This is a corollary of (2). It can also be deduced from (9) and the “1 = q” principle for Q (18).

(20) This q-version of the strong quantum Master Theorem for the right quantum algebra can be deduced from (19) and (12). See section 6.

(21) This q-version of the strong quantum Master Theorem for the right quantum algebra can be deduced from (17) and (13). See [GLZ05].

(22-23) The leftmost-reduction process is not unique. See section 7. There is no strong Master Theorem for H.

(24) The “1 = q” principle uses the weight function defined by the Denert statistics [Ha92].

(25) It can be deduced from (10) and (24). But it is not a corollary of (2), because H_{q} is not a factor algebra of R_{q}.

(26) Even though there is no strong Master Theorem for q = 1 (23), there is a semi-strong Master Theorem in its q-version. See section 7.

6. A (t, q)-version of the classical Master Theorem In this section we derive a (t, q)-analogue of the MacMahon Master

Theorem for the classical noncommutative case [CF69]. We could give a short proof based on the method used in [FH05b], because the further properties needed are straightforward. However we prefer to deduce this (t, q)-analogue identity from the classical noncommutative version [CF69]. To that end we consider the reduction system (SF_{q}) and the quotient algebra F_{q} defined in section 4. It is easy to see that (SF_{q}) is a reductionunique system and that F_{q} is a factor algebra of R_{q}.

The (t, q)-Boson is defined to be the infinite sum

Bos(t, q) := ∑_{w} t^{exc}^{\binom{\overline{w}}{w}}q^{inv w} (\overline{w} ; w)

over all words w from the free monoid 𝔸^{∗} generated by 𝔸. The definition of the statistic “exc” (“number of exceedances”) for biwords is classical and can be found in [Ha92]. The (t, q)-Fermion is an extension of the q-Fermion and reads

Ferm(t, q) := ∑_{J⊂𝔸}(−1)^{|J|} ∑_{σ∈𝔖_{J}} t^{exc α}(−q)^{inv σ} (\begin{matrix}σ(i_{1}) & σ(i_{2}) & ⋯ & σ(i_{l}) \\ i_{1} & i_{2} & ⋯ & i_{l} \end{matrix}) .

In the above definition α denotes the biword (\begin{matrix}σ(i_{1}) & σ(i_{2}) & ··· & σ(i_{l}) \\ i_{1} & i_{2} & ··· & i_{l} \end{matrix}).

Theorem 1Fq (q-quantum Master Theorem). The following identity holds:

Ferm(t, q) × Bos(t, q) ≡ 1 (mod I(SF_{q})).

Theorem 2Fq (Strong q-quantum Master Theorem for SF_{q}). The following identity holds:

[Ferm(t, q) × Bos(t, q)]_{SF_{q}} = 1,

where [ ]_{SF_{q}} is the leftmost-reduction associated with the reduction system (SF_{q}).

Theorem 1Fq is an immediate consequence of Theorem 2Fq. To prove Theorem 2Fq we first recall the classical noncommutative version of the Master Theorem [CF69] that we express as follows.

Theorem 2F (Classical noncommutative version). The following identity holds:

[Ferm(1) × Bos(1)]_{SF} = 1,

where [ ]_{SF} is the leftmost-reduction associated with the reduction system (SF).

Now, introduce the weight function ϕ_{SF} : A_{q} → ℤ[t, t^{−1}, q, q^{−1}]⟨⟨B⟩⟩ defined for each biword α by ϕ_{SF} (α) = t^{exc(α)}q^{inv^{−}(α)}α and extended to all of A_{q} by linearity. The “1 = q” principle for F is stated next as Theorem 4F. The proof is straightforward and omitted.

Theorem 4F (“1 = q” principle for F). We have

ϕ_{SF} ([E]_{SF}) = [ϕ_{SF} (E)]_{SF_{q}}  for E ∈ A_{q};
ϕ_{SF} (EF) = ϕ_{SF} (E)ϕ_{SF} (F) if E and F are two circular expressions.

We complete the proof of Theorem 2Fq as follows. We have

[Ferm(1) × Bos(1)]_{SF} = 1,  [by Theorem 2F]
ϕ_{SF} ([Ferm(1) × Bos(1)]_{SF}) = ϕ_{SF} (1) = 1,
[ϕ_{SF} (Ferm(1) × Bos(1))]_{SF_{q}} = 1, [by Theorem 4F (i)]
[ϕ_{SF} (Ferm(1)) × ϕ_{SF} (Bos(1))]_{SF_{q}} = 1. [by Theorem 4F (ii)]

Finally, it is easy to verify that ϕ_{SF} (Ferm(1)) = Ferm(t, q) and also ϕ_{SF} (Bos(1)) = Bos(t, q).

7. Semi-strong (t, q)-analogue of the Master Theorem for H The contextual algebra H introduced in § 4(e) provides an example of an

algebra in which the “qMM” theorem holds, but not the “strong qMM” one. Those two assertions are proved in this section. We also obtain a (t, q)-version of the quantum Master Theorem, that can be regarded as a semi-strong extension, because the product Ferm(1) × Bos(1) is reduced to 1 after two steps: first, by a leftmost reduction (this is the strong part), second, by taking a homomorphic image of the product thereby reduced.

Consider the reduction system (SH) defined in section 4, a system that has been extensively studied in [Ha92] and [Cl97].

Proposition 5. The algebra H is a factor algebra of R.

Proof. If x > y and V (x, y, a, b) > 0, then \binom{xy}{ab} = \binom{yx}{ab} by definition.

As V (x, y, b, a) = V (x, y, a, b) > 0, we also have \binom{xy}{ba} = \binom{yx}{ba}. On

the other hand, if x > y and V (x, y, a, b) < 0, then \binom{xy}{ab} = \binom{yx}{ba}. As

V (x, y, b, a) = V (x, y, a, b) < 0, we also have \binom{xy}{ba} = \binom{yx}{ab}. In both

cases

\binom{xy}{ab} = \binom{yx}{ba} + \binom{yx}{ab} − \binom{xy}{ba}.

Proposition 6. The reduction system (SH) is not reduction-unique.

Proof. It suffices to provide this following counter-example:

\binom{321}{213} ≡^{1} \binom{231}{213} ≡^{2} \binom{213}{231} ≡^{1} \binom{123}{321} (mod I(SH));

\binom{321}{213} ≡^{2} \binom{312}{213} ≡^{1} \binom{132}{123} ≡^{2} \binom{123}{132} (mod I(SH));

where ≡^{i} means that the reduction relations (SH) are applied at positions (i, i + 1). Both \binom{123}{321} and \binom{123}{132} belong to B_{irr}(SH) and are derived by reduction from the same circuit.

The integral-valued statistic “den” is the Denert statistic for biwords. Its definition, as well as the definition of “exc,” can be found in [Ha92].

Proposition 7. Let u and v be two circuits. If α ≡ β (mod I(SH)), then

(exc, den)α = (exc, den)β.

See [Ha92] for the proof. Note that Clarke [Cl97] has shown that the converse is also true for each pair of bipermutations α, β. Using Proposition 5 and Theorem 1 we can deduce the following “1-quantum Master Theorem” for H.

Theorem 1H (1-quantum Master Theorem for H). The following identity holds:

Ferm(1) × Bos(1) ≡ 1 (mod I(SH)).

However there is no “strong q-quantum Master Theorem” for H, as shown in the next proposition.

Proposition 8. We have [Ferm(1) × Bos(1)]_{SH} ≠ 1, where [ ]_{SH} is the leftmost-reduction associated with the reduction system (SH).

Proof. For r = 3 we calculate

[Ferm(1) × Bos(1)]_{SH} = 1 + \binom{123}{213} − \binom{123}{312} − \binom{123}{321} + \binom{123}{132}

+ \binom{1123}{2113} − \binom{1123}{3121} − \binom{1123}{3112} + \binom{1123}{1312}

+ \binom{1223}{2123} − \binom{1223}{3122} − \binom{1223}{3212} + \binom{1223}{1322}

+ \binom{1233}{2133} − \binom{1233}{3123} − \binom{1233}{3213} + \binom{1233}{1323}

+ ⋯

≠ 1.

Now, let the weight function ψ : A_{q} → ℤ[t, t^{−1}, q, q^{−1}]⟨⟨𝔸^{∗}⟩⟩ be defined for each biword α = \binom{u}{v} by

ψ\binom{u}{v} = t^{exc(α)}q^{den(α)}u

and be extended to all of A_{q} by linearity. From Theorem 1H and Proposition 7 we deduce the following result.

Theorem 2H (Semi-strong quantum Master Theorem for H). We have

ψ([Ferm(1) × Bos(1)]_{SH}) = 1,

where [ ]_{SH} is the leftmost-reduction associated with the reduction system (SH).

For example, take r = 3, we have

ψ([Ferm(1) × Bos(1)]_{SH}) = 1 + tq(123) − tq(123) − tq^{2}(123) + tq^{2}(123)

+ tq(1123) − tq^{2}(1123) − tq(1123) + tq^{2}(1123) + tq(1223) − tq(1223) − tq^{2}(1223) + tq^{2}(1223) + tq(1233) − tq(1233) − tq^{2}(1233) + tq^{2}(1233)

+ ⋯
= 1.

References

[Be78] George M. Bergman. — The Diamond Lemma for Ring Theory, Adv. Math., 29 (1978), pp. 178–218.

[BR91] Richard A. Brualdi, Herbert J. Ryser. — Combinatorial Matrix Theory, Cambridge Univ. Press, 1991 (Encyclopedia of Math. and its Appl., 39).

[Ca72] P. Cartier. — La série génératrice exponentielle, Applications probabilistes et algébriques, Publ. I.R.M.A., Université Louis Pasteur, Strasbourg, 1972, 68 pages.

[Cl97] Robert. J. Clarke. — Han’s conjecture on permutations, European J. Combin., 18 (1997), pp. 511–524.

[CF69] P. Cartier, D. Foata. — Problèmes combinatoires de permutations et réarrangements, Berlin, Springer-Verlag, 1969 (Lecture Notes in Math., 85).

[Fo65] D. Foata. — Etude algébrique de certains problèmes d’Analyse Combinatoire et du Calcul des Probabilités, Publ. Inst. Statist. Univ. Paris, 14 (1965), pp. 81–241.

[FH05a] D. Foata, G.-N. Han. — A basis for the right quantum algebra and the “1 = q” principle, preprint, 2005.

[FH05b] D. Foata, G.-N. Han. — A New Proof of the Garoufalidis-Lê-Zeilberger Quantum MacMahon Master Theorem, to appear in J. of Algebra, 2006.

[GLZ05] S. Garoufalidis, T. Tq Lê, D. Zeilberger. — The Quantum MacMahon Master Theorem, to appear in Proc. Natl. Acad. Sci., 2006.

[Ha92] Guo-Niu Han. — Une transformation fondamentale sur les réarrangements de mots, Adv. Math., 105 (1994), pp. 26–41.

[Ma15] P. A. MacMahon. — Combinatory Analysis vol. I, II, Cambridge Univ. Press, 1915. Reprinted by Chelsea, New York, 1960.

[PW91] B. Parshall, J.-P. Wang. — Quantum linear groups, Memoirs Amer. Math. Soc, 89, 1991.

[Z80] D. Zeilberger. — The algebra of linear partial difference operators and its applications, SIAM J. Math. Anal., 11, no. 6 (1980), pp. 919–932.

[Z85] D. Zeilberger. — A combinatorial approach to matrix algebra, Discrete Math., 56 (1985), pp. 61–72.

Dominique Foata Institut Lothaire 1, rue Murner F-67000 Strasbourg, France

foata@math.u-strasbg.fr

Guo-Niu Han

I.R.M.A. UMR 7501

Université Louis Pasteur et CNRS 7, rue René-Descartes F-67084 Strasbourg, France

                       guoniu@math.u-strasbg.fr