A BASIS FOR THE RIGHT QUANTUM

ALGEBRA AND THE “1 = q” PRINCIPLE

Dominique Foata and Guo-Niu Han

January 10, 2006

Abstract. We construct a basis for the right quantum algebra introduced by Garoufalidis, Lê and Zeilberger and give a method making it possible to go from an algebra subject to commutation relations (without the variable q) to the right quantum algebra by means of an appropriate weight-function. As a consequence, a strong quantum MacMahon Master Theorem is derived. Besides, the algebra of biwords is systematically in use.

1. Introduction

In their search for a natural q-analogue of the MacMahon Master Theorem Garoufalidis et al. [4] have introduced the right quantum algebra R_{q} defined to be the associative algebra over a commutative ring K, generated by r^{2} elements X_{xa} (1 ≤ x, a ≤ r) (r ≥ 2) subject to the following commutation relations:

\begin{aligned}X_{yb}X_{xa} − X_{xa}X_{yb} & = q^{−1}X_{xb}X_{ya} − qX_{ya}X_{xb}, \\ X_{ya}X_{xa} & = q^{−1}X_{xa}X_{ya}, \end{aligned} \begin{matrix}(x > y, a > b); \\ (x > y, all a); \end{matrix}

with q being an invertible element in K. The right quantum algebra in the case r = 2 has already been studied by Rodríguez-Romo and Taft [13], who set up an explicit basis for it. On the other hand, a basis for the full quantum algebra has been duly constructed (see [12, Theorem 3.5.1, p. 38]) for an arbitrary r ≥ 2. It then seems natural to do the same with the right quantum algebra for each r ≥ 2. This is the first goal of the paper.

In fact, the paper originated from a discussion with Doron Zeilberger, when he explained to the first author how he verified the quantum MacMahon Master identity for each fixed r by computer code. His computer program uses the fact, as he is perfectly aware, that the set of irreducible biwords—which will be introduced in the sequel—generates the right quantum algebra. For a better understanding of his joint paper [4] and also for deriving the “1 = q” principle, it seems essential to see whether the set of irreducible biwords has the further property of being a basis, and it does. Thanks to this result, a strong quantum MacMahon Master Theorem can be subsequently derived.

Typeset by AMS-TEX

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

Key words and phrases. Right quantum algebra, quantum MacMahon Master theorem.

When manipulating the above relations, the visible part of the commutations is made within the subcripts of the X_{xa}’s, written as such. It is then important to magnify them by having an adequate notation. To that end we replace each

X_{xa} by the biletter \binom{x}{a},

so that, in further computations, products X_{x_{1},a_{1}}X_{x_{2},a_{2}} ⋯ X_{x_{ℓ},a_{ℓ}} become biwords \binom{x_{1}x_{2}···x_{ℓ}}{a_{1}a_{2}···a_{ℓ}}, objects that have been efficiently used in combinatorial contexts [9, 10]. Accordingly, the commutation rules for the right quantum algebra can be written as:

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

We shall use the following notations. The positive integer r will be kept fixed throughout and 𝔸 will designate 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 biword α. 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. The product of two biwords is their concatenation.

Let 𝔹 denote the set of biletters and B the set of all biwords. Let α ∈ B such that ℓ(α) ≥ 2 and 1 ≤ i ≤ ℓ(α) − 1 be a positive integer. The biword α can be factorized as α = β(\begin{matrix}xy \\ ab \end{matrix})γ, where x, y, a, b ∈ 𝔸 and β, γ ∈ B with ℓ(β) = i − 1. Say that α has a double descent at position i if x > y and a ≥ b. Notice the discrepancy in the inequalities on the top word and the bottom one. A biword α without any double descent is said to be irreducible. The set of all irreducible biwords is denoted by B_{irr}.

Let ℤ be the ring of all integers and ℤ[q, q^{−1}] the ring of the polynomials in the variables q, q^{−1} subject 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. The formal sums ∑_{α} c(α)α will be called expressions. An expression ∑_{α} c(α)α is said to be irreducible if c(α) = 0 for all α ∉ B_{irr}. The set of all irreducible expressions is denoted by A_{irr}.

Similarly, let A_{q} = ℤ[q, q^{−1}]⟨⟨B⟩⟩ denote the large ℤ[q, q^{−1}]-algebra of the formal sums ∑_{α} c(α)α, where c(α) ∈ ℤ[q, q^{−1}] for all α ∈ B. Following Bergman’s method [1] we introduce two reduction systems (S) and (S_{q}) as being the sets of pairs (α, [α]) ∈ B × A and (α, [α]_{q}) ∈ B × A_{q}, respectively, defined by

(S) (\binom{xy}{ab}, \left[{xy \atop ab}\right]) with \left[{xy \atop ab}\right] = \binom{yx}{ba} + \binom{yx}{ab} − \binom{xy}{ba}  (x > y, a > b); (\binom{xy}{aa}, \left[{xy \atop aa}\right]) with \left[{xy \atop aa}\right] = \binom{yx}{aa}  (x > y, all a).

(S_{q})

(\binom{xy}{ab}, \left[{xy \atop ab}\right]_{q}) with \left[{xy \atop ab}\right]_{q} = \binom{yx}{ba} + q\binom{yx}{ab} − q^{−1}\binom{xy}{ba} (x > y, a > b);
(\binom{xy}{aa}, \left[{xy \atop aa}\right]_{q}) with \left[{xy \atop aa}\right]_{q} = q\binom{yx}{aa}  (x > y, all a).

Notice that the equations \binom{xy}{ab} − \left[{xy \atop ab}\right]_{q} = 0, \binom{xy}{aa} − \left[{xy \atop aa}\right]_{q} = 0 are simple rewritings of the commutation rules of the right quantum algebra and that (S) is deduced from (S_{q}) by letting q = 1.

Let I (resp. I_{q}) be the two-sided ideal of A (resp. of A_{q}) generated by the elements γ − [γ] (resp. γ − [γ]_{q}) such that (γ, [γ]) ∈ (S) (resp. γ − [γ]_{q} ∈ (S_{q})). The quotient algebras R = A/I and R_{q} = A_{q}/I_{q} are called the 1-right quantum algebra and the q-right quantum algebra, respectively.

In Section 2 we define a ℤ-linear mapping E ↦ [E] of A onto the ℤ-module A_{irr} of the irreducible expressions, called reduction. Using Bergman’s “Diamond Lemma” [1] this reduction will serve to obtain a model for the algebra R, as stated in the next theorem.

Theorem 1. A set of representatives in A for R is given by the ℤ-module A_{irr}. The algebra R may be identified with the ℤ-module A_{irr}, the multiplication being given by E × F = [E × F] for any two irreducible expressions E, F. With this identification B_{irr} is a basis for R.

Four statistics counting various kinds of inversions will be needed. If α = (\begin{matrix}u \\ v \end{matrix}) =

(\begin{matrix}x_{1}x_{2}...x_{n} \\ a_{1}a_{2}...a_{n} \end{matrix}) is a biword, let

inv u = #{(i, j) | 1 ≤ i < j ≤ n, x_{i} > x_{j}};
imv v = #{(i, j) | 1 ≤ i < j ≤ n, a_{i} ≥ a_{j}};
inv^{−}(α) = inv v − inv u;
inv^{+}(α) = imv v + inv u.

The first (resp. second) statistic “inv” (resp. “imv”) is the usual number of inversions (resp. of large inversions) of a word. Notice that “inv^{−}” may be negative. The weight function ϕ defined for each biword α by ϕ(α) = q^{inv^{−}(α)}α can be extended to all of A_{q} by linearity. Clearly it is a ℤ[q, q^{−1}]-module isomorphism of A_{q} onto itself. The second result of the paper is stated next.

Theorem 2. The ℤ[q, q^{−1}]-module isomorphism ϕ of A_{q} onto itself induces a ℤ[q, q^{−1}]-module isomorphism \overline{ϕ} of A_{q}/I onto A_{q}/I_{q}. In particular, R_{q} has the same basis as R.

Now, a circuit is defined to be a biword whose top word is a rearrangement of the letters of its bottom word. The set of all circuits is denoted by C. It is clearly a submonoid of B. An expression E = ∑_{α} c(α)α is said to be circular if c(α) = 0 for all α ∉ C. Clearly, the sum and the product of two circular expressions is a circular expression, so that the set of circular expressions in A (resp. in A_{q}) is a subalgebra of A (resp. of A_{q}), which will be denoted by A^{cir} (resp. by A_{q}^{cir}).

Theorem 3. The restriction of the ℤ[q, q^{−1}]-module isomorphism \overline{ϕ} of Theorem 2 to A_{q}^{cir}/I is a ℤ[q, q^{−1}]-algebra isomorphism onto A_{q}^{cir}/I_{q}.

[figure: A_{q}^{cir}; A_{q}^{cir}; ϕ; module-iso; can; A_{q}^{cir}/I; A_{q}^{cir}/I_{q}; \overline{ϕ}; algebra-iso; can; A_{q}; A_{q}; ϕ; module-iso; can; A_{q}/I; A_{q}/I_{q}; \overline{ϕ}; module-iso; can; ⟶]

Accordingly, each identity holding in A_{q}^{cir}/I has an equivalent counterpart in A_{q}^{cir}/I_{q}. This is the “1 = q” principle. An illustration of this principle is given by the qMM Theorem derived by Garoufalidis et al. (op. cit.). Those authors have introduced the q-Fermion as being the sum

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

where 𝔖_{J} is the permutation group acting on the set J = {i_{1} < i_{2} < ⋯ < i_{l}}, and the q-Boson as the sum

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

over all words w from the free monoid 𝔸^{∗} generated by 𝔸, where \overline{w} stands for the nondecreasing rearrangement of the word w. The q-Fermion and q-Boson belong to A_{q}. Garoufalidis et al. have proved ([4], see also [3] for another proof) the following identity

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

This identity may a priori be regarded as a q-version of the MacMahon Master Theorem, as it reduces to the classical MacMahon’s identity [11, p. 93–98], when q = 1 and the biletters are supposed to commute. By the “1 = q” principle (Theorem 3), we obtain the following result, which shows that the variable q is in fact superfluous.

Corollary 4. The identity Ferm(q) × Bos(q) ≡ 1 (mod I_{q}) holds if and only if Ferm(1) × Bos(1) ≡ 1 (mod I) holds.

When applying Theorem 1 to the quantum MacMahon Master Theorem, we obtain the following result, which can be regarded as a strong quantum MacMahon Master Theorem.

Corollary 5. The following identity holds:

[Ferm(1) × Bos(1)] = 1.

The proof of Theorem 1, given in Section 2, is based on Bergman’s “Diamond Lemma” ([1], Theorem 1.2). It consists of verifying that the conditions required by the “Diamond Lemma” hold in the present situation. Theorems 2 and 3 are proved in Section 3 and Corollaries 4 and 5 in the last section.

2. The Reduction Process

For applying Bergman’s “Diamond Lemma” [1] we need have a so-called reduction system that satisfies two conditions: (1) the descending chain condition holds;

(2) its ambiguities are resolvable. Those terms will be explained shortly. Let ℤ⟨B⟩ be the subalgebra of A of all sums ∑_{α} c(α)α (α ∈ B), where only a finite number of the c(α)’s are non-zero. The elements of ℤ⟨B⟩ will be called finite expressions. The reduction system for ℤ⟨B⟩ is simply the set (S) of pairs (α, [α]) ∈ B × ℤ⟨B⟩, already described in section 1. By means of this reduction system we introduce the reduction itself as being the mapping E ↦ [E] of ℤ⟨B⟩ onto the set ℤ⟨B_{irr}⟩ of the finite irreducible expressions, defined by the following axioms:

(C1) The reduction is linear, i.e. for E_{1}, E_{2} ∈ ℤ⟨B⟩,

[c_{1}E_{1} + c_{2}E_{2}] = c_{1}[E_{1}] + c_{2}[E_{2}].

(C2) [E] = E for every E ∈ ℤ⟨B_{irr}⟩.

(C3) For (\begin{matrix}xy \\ ab \end{matrix}) ∉ B_{irr}, i.e. x > y and a ≥ b, then

(C3.1)  \left[{xy \atop ab}\right] = \binom{yx}{ba} + \binom{yx}{ab} − \binom{xy}{ba}, if a > b;
(C3.2)  \left[{xy \atop aa}\right] = \binom{yx}{aa}, if a = b.

(C4) Let α ∉ B_{irr} be a reducible biword. For each factorization α = β(\begin{matrix}xy \\ ab \end{matrix})γ, where x, y, a, b ∈ 𝔸 and β(\begin{matrix}x \\ a \end{matrix}) ∈ B_{irr} and γ ∈ B we have

[α] = [β × [\begin{matrix}xy \\ ab \end{matrix}] × γ].

Although the reduction is recursively defined, it is well defined. Every time Condition (C3) is applied, the running biword α is transformed into either three new biwords (C3.1), or a new biword (C3.2). The important property is the fact that the statistic inv^{+} of each of the new biwords is strictly less than inv^{+}(α). Thus, after finitely many successive applications of (C3), an irreducible expression is derived. When the biword α has more than one double descent, Condition (C4) says that Condition (C3) must be applied at the first double descent position. Consequently, the final irreducible expression is unique.

There are several other ways to map each expression onto an irreducible expression, using relations (C3.1) and (C3.2). The reduction defined above is only one of those mappings. The important feature is the fact such a mapping involves finitely many applications of relations (C3.1) and (C3.2). Following Bergman we say that Condition (1) (the descending chain condition) holds for the pair (ℤ⟨B⟩, S).

Now an expression E is said to be reduction-unique under S if the irreducible expression derived from E does not depend on where the applications of (C3.1) and (C3.2) take place. More formally, each expression is reduction-unique under S if for every biword α and every factorization α = βα′γ (β, α′, γ ∈ B) we have

(Reduction-unique)  [α] = [β[α′]γ].

Now examine the second condition required by the “Diamond Lemma.” There is an ambiguity in S if there are two pairs (α, [α]) and (α′, [α′]) in S such that α = βγ, α′ = γδ for some nonempty biwords β, γ, δ ∈ B. This ambiguity is said to be resolvable if [[α]δ] = [β[α′]], i.e. [[βγ]δ] = [β[γδ]]. In our case this means that β = \binom{x}{a}, γ = \binom{y}{b}, δ = \binom{z}{c} with x > y > z and a ≥ b ≥ c. Using the first three integers instead of the letters x, y, z, a, b, c there are four cases to be studied:

(i) β = \binom{3}{3}, γ = \binom{2}{2}, δ = \binom{1}{1};

(ii) β = \binom{3}{2}, γ = \binom{2}{2}, δ = \binom{1}{1};

(iii) β = \binom{3}{2}, γ = \binom{2}{1}, δ = \binom{1}{1};

(iv) β = \binom{3}{1}, γ = \binom{2}{1}, δ = \binom{1}{1}.

Accordingly, the ambiguities in S are resolvable if the following four identities hold:

(2.1)  [\left[{32 \atop 32}\right]\binom{1}{1}] = [\binom{3}{3}\left[{21 \atop 21}\right]];
(2.2)  [\left[{32 \atop 22}\right]\binom{1}{1}] = [\binom{3}{2}\left[{21 \atop 21}\right]];
(2.3)  [\left[{32 \atop 21}\right]\binom{1}{1}] = [\binom{3}{2}\left[{21 \atop 11}\right]];
(2.4)  [\left[{32 \atop 11}\right]\binom{1}{1}] = [\binom{3}{1}\left[{21 \atop 11}\right]].

Let us prove (2.1), the other three identities being handled in a similar manner.

Proof of (2.1). For an easy reading of the coming calculations we have added subscripts A, B, …, J to certain brackets, which should help spot the subscripted brackets in the various equations. The left-hand side is evaluated as follows:

[[\begin{matrix}32 \\ 32 \end{matrix}](\begin{matrix}1 \\ 1 \end{matrix})] = [[\begin{matrix}23 \\ 23 \end{matrix}](\begin{matrix}1 \\ 1 \end{matrix})]_{A} + [[\begin{matrix}23 \\ 32 \end{matrix}](\begin{matrix}1 \\ 1 \end{matrix})]_{B} − [[\begin{matrix}32 \\ 23 \end{matrix}](\begin{matrix}1 \\ 1 \end{matrix})]_{C};
[[\begin{matrix}23 \\ 23 \end{matrix}](\begin{matrix}1 \\ 1 \end{matrix})]_{A} = [(\begin{matrix}2 \\ 2 \end{matrix})[\begin{matrix}31 \\ 31 \end{matrix}]] = [(\begin{matrix}2 \\ 2 \end{matrix})[\begin{matrix}13 \\ 13 \end{matrix}]]_{D} + [(\begin{matrix}2 \\ 2 \end{matrix})[\begin{matrix}13 \\ 31 \end{matrix}]]_{I} − [(\begin{matrix}2 \\ 2 \end{matrix})[\begin{matrix}31 \\ 13 \end{matrix}]]_{J};
[[\begin{matrix}23 \\ 32 \end{matrix}](\begin{matrix}1 \\ 1 \end{matrix})]_{B} = [(\begin{matrix}2 \\ 3 \end{matrix})[\begin{matrix}31 \\ 21 \end{matrix}]] = [(\begin{matrix}2 \\ 3 \end{matrix})[\begin{matrix}13 \\ 12 \end{matrix}]]_{E} + [(\begin{matrix}2 \\ 3 \end{matrix})[\begin{matrix}13 \\ 21 \end{matrix}]]_{F} − [(\begin{matrix}2 \\ 3 \end{matrix})[\begin{matrix}31 \\ 12 \end{matrix}]];
−[[\begin{matrix}32 \\ 23 \end{matrix}](\begin{matrix}1 \\ 1 \end{matrix})]_{C} = −[(\begin{matrix}3 \\ 2 \end{matrix})[\begin{matrix}21 \\ 31 \end{matrix}]] = −[(\begin{matrix}3 \\ 2 \end{matrix})[\begin{matrix}12 \\ 13 \end{matrix}]]_{G} − [(\begin{matrix}3 \\ 2 \end{matrix})[\begin{matrix}12 \\ 31 \end{matrix}]] + [(\begin{matrix}3 \\ 2 \end{matrix})[\begin{matrix}21 \\ 13 \end{matrix}]]_{H};
[(\begin{matrix}2 \\ 2 \end{matrix})[\begin{matrix}13 \\ 13 \end{matrix}]]_{D} = [[\begin{matrix}21 \\ 21 \end{matrix}](\begin{matrix}3 \\ 3 \end{matrix})] = [[\begin{matrix}12 \\ 12 \end{matrix}](\begin{matrix}3 \\ 3 \end{matrix})] + [[\begin{matrix}12 \\ 21 \end{matrix}](\begin{matrix}3 \\ 3 \end{matrix})] − [[\begin{matrix}21 \\ 12 \end{matrix}](\begin{matrix}3 \\ 3 \end{matrix})];
[(\begin{matrix}2 \\ 3 \end{matrix})[\begin{matrix}13 \\ 12 \end{matrix}]]_{E} = [[\begin{matrix}21 \\ 31 \end{matrix}](\begin{matrix}3 \\ 2 \end{matrix})] = [[\begin{matrix}12 \\ 13 \end{matrix}](\begin{matrix}3 \\ 2 \end{matrix})] + [[\begin{matrix}12 \\ 31 \end{matrix}](\begin{matrix}3 \\ 2 \end{matrix})] − [[\begin{matrix}21 \\ 13 \end{matrix}](\begin{matrix}3 \\ 2 \end{matrix})];
[(\begin{matrix}2 \\ 3 \end{matrix})[\begin{matrix}13 \\ 21 \end{matrix}]]_{F} = [[\begin{matrix}21 \\ 32 \end{matrix}](\begin{matrix}3 \\ 1 \end{matrix})] = [[\begin{matrix}12 \\ 23 \end{matrix}](\begin{matrix}3 \\ 1 \end{matrix})] + [[\begin{matrix}12 \\ 32 \end{matrix}](\begin{matrix}3 \\ 1 \end{matrix})] − [[\begin{matrix}21 \\ 23 \end{matrix}](\begin{matrix}3 \\ 1 \end{matrix})]_{I};
−[(\begin{matrix}3 \\ 2 \end{matrix})[\begin{matrix}12 \\ 13 \end{matrix}]]_{G} = −[[\begin{matrix}31 \\ 21 \end{matrix}](\begin{matrix}2 \\ 3 \end{matrix})] = −[[\begin{matrix}13 \\ 12 \end{matrix}](\begin{matrix}2 \\ 3 \end{matrix})] − [[\begin{matrix}13 \\ 21 \end{matrix}](\begin{matrix}2 \\ 3 \end{matrix})] + [[\begin{matrix}31 \\ 12 \end{matrix}](\begin{matrix}2 \\ 3 \end{matrix})];
[(\begin{matrix}3 \\ 2 \end{matrix})[\begin{matrix}21 \\ 13 \end{matrix}]]_{H} = [[\begin{matrix}32 \\ 21 \end{matrix}](\begin{matrix}1 \\ 3 \end{matrix})] = [[\begin{matrix}23 \\ 12 \end{matrix}](\begin{matrix}1 \\ 3 \end{matrix})] + [[\begin{matrix}23 \\ 21 \end{matrix}](\begin{matrix}1 \\ 3 \end{matrix})]_{J} − [[\begin{matrix}32 \\ 12 \end{matrix}](\begin{matrix}1 \\ 3 \end{matrix})].

The sum of the above nine equalities yields:

[[\begin{matrix}32 \\ 32 \end{matrix}](\begin{matrix}1 \\ 1 \end{matrix})] = −(\begin{matrix}231 \\ 312 \end{matrix}) − (\begin{matrix}312 \\ 231 \end{matrix}) + (\begin{matrix}123 \\ 123 \end{matrix}) + (\begin{matrix}123 \\ 213 \end{matrix}) − (\begin{matrix}213 \\ 123 \end{matrix})

+ (\begin{matrix}123 \\ 132 \end{matrix}) + (\begin{matrix}123 \\ 312 \end{matrix}) − (\begin{matrix}213 \\ 132 \end{matrix}) + (\begin{matrix}123 \\ 231 \end{matrix}) + (\begin{matrix}123 \\ 321 \end{matrix})

− (\begin{matrix}132 \\ 123 \end{matrix}) − (\begin{matrix}132 \\ 213 \end{matrix}) + (\begin{matrix}312 \\ 123 \end{matrix}) + (\begin{matrix}231 \\ 123 \end{matrix}) − (\begin{matrix}321 \\ 123 \end{matrix}).

As for the right-hand side we have:

[(\begin{matrix}3 \\ 3 \end{matrix})[\begin{matrix}21 \\ 21 \end{matrix}]] = [(\begin{matrix}3 \\ 3 \end{matrix})[\begin{matrix}12 \\ 12 \end{matrix}]]_{A} + [(\begin{matrix}3 \\ 3 \end{matrix})[\begin{matrix}12 \\ 21 \end{matrix}]]_{B} − [(\begin{matrix}3 \\ 3 \end{matrix})[\begin{matrix}21 \\ 12 \end{matrix}]]_{C};
[[\begin{matrix}31 \\ 31 \end{matrix}](\begin{matrix}2 \\ 2 \end{matrix})]_{A} = [[\begin{matrix}13 \\ 13 \end{matrix}](\begin{matrix}2 \\ 2 \end{matrix})]_{D} + [[\begin{matrix}13 \\ 31 \end{matrix}](\begin{matrix}2 \\ 2 \end{matrix})]_{I} − [[\begin{matrix}31 \\ 13 \end{matrix}](\begin{matrix}2 \\ 2 \end{matrix})]_{J};
[[\begin{matrix}31 \\ 32 \end{matrix}](\begin{matrix}2 \\ 1 \end{matrix})]_{B} = [[\begin{matrix}13 \\ 23 \end{matrix}](\begin{matrix}2 \\ 1 \end{matrix})]_{E} + [[\begin{matrix}13 \\ 32 \end{matrix}](\begin{matrix}2 \\ 1 \end{matrix})]_{F} − [[\begin{matrix}31 \\ 23 \end{matrix}](\begin{matrix}2 \\ 1 \end{matrix})];
−[[\begin{matrix}32 \\ 31 \end{matrix}](\begin{matrix}1 \\ 2 \end{matrix})]_{C} = −[[\begin{matrix}23 \\ 13 \end{matrix}](\begin{matrix}1 \\ 2 \end{matrix})]_{G} − [[\begin{matrix}23 \\ 31 \end{matrix}](\begin{matrix}1 \\ 2 \end{matrix})] + [[\begin{matrix}32 \\ 13 \end{matrix}](\begin{matrix}1 \\ 2 \end{matrix})]_{H};
[(\begin{matrix}1 \\ 1 \end{matrix})[\begin{matrix}32 \\ 32 \end{matrix}]]_{D} = [(\begin{matrix}1 \\ 1 \end{matrix})[\begin{matrix}23 \\ 23 \end{matrix}]] + [(\begin{matrix}1 \\ 1 \end{matrix})[\begin{matrix}23 \\ 32 \end{matrix}]] − [(\begin{matrix}1 \\ 1 \end{matrix})[\begin{matrix}32 \\ 23 \end{matrix}]];
[(\begin{matrix}1 \\ 2 \end{matrix})[\begin{matrix}32 \\ 31 \end{matrix}]]_{E} = [(\begin{matrix}1 \\ 2 \end{matrix})[\begin{matrix}23 \\ 13 \end{matrix}]] + [(\begin{matrix}1 \\ 2 \end{matrix})[\begin{matrix}23 \\ 31 \end{matrix}]] − [(\begin{matrix}1 \\ 2 \end{matrix})[\begin{matrix}32 \\ 13 \end{matrix}]];
[(\begin{matrix}1 \\ 3 \end{matrix})[\begin{matrix}32 \\ 21 \end{matrix}]]_{F} = [(\begin{matrix}1 \\ 3 \end{matrix})[\begin{matrix}23 \\ 12 \end{matrix}]] + [(\begin{matrix}1 \\ 3 \end{matrix})[\begin{matrix}23 \\ 21 \end{matrix}]] − [(\begin{matrix}1 \\ 3 \end{matrix})[\begin{matrix}32 \\ 12 \end{matrix}]]_{I};
−[(\begin{matrix}2 \\ 1 \end{matrix})[\begin{matrix}31 \\ 32 \end{matrix}]]_{G} = −[(\begin{matrix}2 \\ 1 \end{matrix})[\begin{matrix}13 \\ 23 \end{matrix}]] − [(\begin{matrix}2 \\ 1 \end{matrix})[\begin{matrix}13 \\ 32 \end{matrix}]] + [(\begin{matrix}2 \\ 1 \end{matrix})[\begin{matrix}31 \\ 23 \end{matrix}]];
[(\begin{matrix}3 \\ 1 \end{matrix})[\begin{matrix}21 \\ 32 \end{matrix}]]_{H} = [(\begin{matrix}3 \\ 1 \end{matrix})[\begin{matrix}12 \\ 23 \end{matrix}]] + [(\begin{matrix}3 \\ 1 \end{matrix})[\begin{matrix}12 \\ 32 \end{matrix}]]_{J} − [(\begin{matrix}3 \\ 1 \end{matrix})[\begin{matrix}21 \\ 23 \end{matrix}]].

The sum of the above nine equalities yields:

[(\begin{matrix}3 \\ 3 \end{matrix})[\begin{matrix}21 \\ 21 \end{matrix}]] = −(\begin{matrix}312 \\ 231 \end{matrix}) − (\begin{matrix}231 \\ 312 \end{matrix}) + (\begin{matrix}123 \\ 123 \end{matrix}) + (\begin{matrix}123 \\ 132 \end{matrix}) − (\begin{matrix}132 \\ 123 \end{matrix})

+ (\begin{matrix}123 \\ 213 \end{matrix}) + (\begin{matrix}123 \\ 231 \end{matrix}) − (\begin{matrix}132 \\ 213 \end{matrix}) + (\begin{matrix}123 \\ 312 \end{matrix}) + (\begin{matrix}123 \\ 321 \end{matrix})

− (\begin{matrix}213 \\ 123 \end{matrix}) − (\begin{matrix}213 \\ 132 \end{matrix}) + (\begin{matrix}231 \\ 123 \end{matrix}) + (\begin{matrix}312 \\ 123 \end{matrix}) − (\begin{matrix}321 \\ 123 \end{matrix})

= [[\begin{matrix}32 \\ 32 \end{matrix}](\begin{matrix}1 \\ 1 \end{matrix})] (left-hand side).

Let I′ be the two-sided ideal of ℤ⟨B⟩ generated by the elements γ − [γ] such that (γ, [γ]) ∈ (S) and let R′ be the quotient ℤ⟨B⟩/I′. The pair (ℤ⟨B⟩, S) having the descending chain condition and the ambiguities being resolvable, Bergman’s “Diamond Lemma” implies the following theorem.

Theorem 6. A set of representatives in ℤ⟨B⟩ for R′ is given by the ℤ-module ℤ⟨B_{irr}⟩. The algebra R′ may be identified with ℤ⟨B_{irr}⟩, the multiplication being given by E × F = [E ×F] for any two finite irreducible expressions E, F. With this identification B_{irr} is a basis for R′.

For the proof of Theorem 1 we use the following argument. For each n ≥ 0 let A^{(n)} be the n-th degree homogeneous subspace of A consisting of all expressions ∑_{α} c(α)α such that ℓ(α) = 0 if ℓ(α) ≠ n ([6], I.6). As the starting alphabet 𝔸 is finite, all expressions in A^{(n)} are finite sums, so that A^{(n)} ⊂ ℤ⟨B⟩ for all n. Now, let each expression E from A be written as a sum

E = ∑_{n≥0} E^{(n)} with E^{(n)} ∈ A^{(n)}.

As both ideals I and I′ are generated by expressions from the second degree homogeneous space A^{(2)}, we have E ≡ 0 (mod I) if and only if for every n ≥ 0 we have E^{(n)} ≡ 0 (mod I′). In particular, [E^{(n)}] also belongs to A^{(n)}. Theorem 1 follows from Theorem 6 by taking the definition

[E] = ∑_{n≥0}[E^{(n)}].

3. The “1 = q” principle

Let E be an expression in A_{q}. Theorem 2 is equivalent to saying that the identity E ∈ I holds if and only if ϕ(E) ∈ I_{q} holds. First we prove the “only if” part. Because ϕ is linear, it suffices to consider all linear generators of I, which have the following form:

E_{1} = α\binom{rs}{i i}β − α\binom{s r}{i i}β

and

E_{2} = α\binom{rs}{ij}β − α\binom{sr}{ji}β − α\binom{sr}{ij}β + α\binom{rs}{ji}β,

where α, β are biwords and r, s, i, j integers such that r < s, i < j. Let k = inv^{−}(α\binom{rs}{ij}β), then

inv^{−}(α\binom{sr}{ji}β) = k, inv^{−}(α\binom{sr}{ij}β) = k − 1, inv^{−}(α\binom{rs}{ji}β) = k + 1,

so that

ϕ(E_{2}) = q^{k}(α\binom{rs}{ij}β − α\binom{sr}{ji}β − q^{−1}α\binom{sr}{ij}β + qα\binom{rs}{ji}β) ∈ I_{q}.

In the same way ϕ(E_{1}) ∈ I_{q}. The “if” part can be proved in the same manner.

For Theorem 3 it suffices to prove the identity ϕ(EF) = ϕ(E)ϕ(F) for any two circular expressions E and F. As ϕ is linear, it suffices to do it when E = (\begin{matrix}u \\ v \end{matrix}), F = (\begin{matrix}u′ \\ v′ \end{matrix}) are two circuits. Let inv(u, u′) denote the number of pairs (x, y) such that

x (resp. y) is a letter of u (resp. of u′) and x > y. As (\begin{matrix}uu′ \\ vv′ \end{matrix}) is a circuit, we have

inv uu′ = inv u + inv u′ + inv(u, u′);
inv vv′ = inv v + inv v′ + inv(v, v′);
inv(u, u′) = inv(v, v′);

so that

inv^{−}(EF) = inv vv′ − inv uu′
= inv v + inv v′ − inv u − inv u′
= inv^{−}(E) + inv^{−}(F).

4. The quantum MacMahon Master Theorem

For proving Corollary 4 we apply Theorem 3 to Ferm(1) × Bos(1). As Ferm(1) and Bos(1) are both circular expressions, the relation

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

is equivalent to

ϕ(Ferm(1)) × ϕ(Bos(1)) ≡ 1 (mod I_{q}).

Finally, it is straightforward to verify

Ferm(q) = ϕ(Ferm(1)) and Bos(q) = ϕ(Bos(1)).

Now to prove Corollary 5 we start with Garoufalidis et al.’s result (for q = 1), which says that Ferm(1) × Bos(1) ≡ 1 (mod I). But by Theorem 1 we have E ≡ F (mod I) if and only if [E] = [F]. Hence [Ferm(1) × Bos(1)] = [1] = 1.

5. Concluding Remarks

It is worth noticing that Rodríguez and Taft have introduced two explicit left quantum groups for r = 2 in [13] and [14]. As mentioned in the introduction, the former one has been extended to an arbitrary dimension r ≥ 2 by Garoufalidis et al. [4] and been given an explicit basis in the present paper, while the latter one has been recently modeled after SL_{q}(r) by Lauve and Taft [8] also for each r ≥ 2.

We should like to thank Doron Zeilberger and Stavros Garoufalidis for several fruitful discussions. We are grateful to Christian Kassel, who gave us the references to the book by Parshall and Wang [12], the two papers by Rodríguez and Taft [13, 14] and the fundamental paper by Bergman [1]. Finally, we have greatly benefited from Jean-Pierre Jouanolou’s ever-lasting mathematical expertise.

Since the paper has been submitted for publication, several works about the quantum MacMahon Master Theorem have been completed. Hai and Lorenz [5] have derived the identity using Koszul complex techniques. Konvalinka and Pak [7] have worked out a several basis (q_{ij})-analogue of the quantum MacMahon Master Theorem and extended the “1 = q” principle developed in our paper to a “1 = q_{ij}” case. Etingof and Pak [2] have derived an extension taking up again the Koszul duality to obtain a new identity having several enumerative applications.

Acknowledgements. The authors should like to thank the two referees for their careful readings and their knowledgeable remarks.

References

1. George M. Bergman, The Diamond Lemma for Ring Theory, Adv. Math. 29 (1978), 178–218.

2. Pavel Etingof and Igor Pak, An algebraic extension of the MacMahon Master Theorem, Proc. Amer. Math. Soc. (to appear).

3. Dominique Foata and Guo-Niu Han, A new proof of the Garoufalidis-Lê-Zeilberger Quantum MacMahon Master Theorem, J. of Algebra 307 (2007), 424-431.

4. S. Garoufalidis, T. TQ Lê, D. Zeilberger, The quantum MacMahon Master Theorem, Proc. Natl. Acad. of Sci. USA 103 (2006), 13928-13931.

5. Phung Ho Hai and Martin Lorenz, Koszul algebras and the quantum MacMahon Master Theorem, Bull. London Math. Soc. (to appear).

6. C. Kassel, Quantum groups, Graduate texts in math., vol. 155, Springer-Verlag, New York, 1995.

7. Matjaz Konvalinka and Igor Pak, Non-commutative extensions of the MacMahon Master Theorem, Adv. in Math. (to appear).

8. A. Lauve and E.J. Taft, A class of left quantum groups modeled after SL_{q}(r), J. of Pure and Applied Algebra 208 (2007), 797-803.

9. M. Lothaire, Combinatorics on Words, Addison-Wesley, London, (Encyclopedia of Math. and its Appl., 17), 1983.

10. M. Lothaire, Algebraic Combinatorics on Words, Cambridge Univ. Press, (Encyclopedia of Math. and its Appl., 90), 2002.

11. P. A. MacMahon, Combinatory Analysis, 1, Cambridge Univ. Press, (reprinted by Chelsea Publ. Co., New York, 1960), 1915.

12. B. Parshall, J.-P. Wang, Quantum linear groups, Memoirs Amer. Math. Soc. 89, 1991.

13. Suemi Rodríguez-Romo, Earl Taft, Some quantum-like Hopf algebras which remain noncommutative when q = 1, Lett. Math. Phys. 61 (2002), 41–50.

14. Suemi Rodríguez-Romo, Earl Taft, A left quantum group, J. Algebra 286 (2005), 154–160.

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

E-mail address: foata@math.u-strasbg.fr

I.R.M.A. UMR 7501, Université Louis Pasteur et CNRS, 7 rue René-Descartes, F-67084 Strasbourg, France

E-mail address: guoniu@math.u-strasbg.fr