CONSTRUCTION OF FREE COMMUTATIVE INTEGRO-DIFFERENTIAL
ALGEBRAS BY THE METHOD OF GRÖBNER-SHIRSHOV BASES

arXiv:1302.0041v1 [math.AC] 1 Feb 2013

XING GAO, LI GUO, AND SHANGHUA ZHENG
Abstract. In this paper, we construct a canonical linear basis for free commutative integro-differential
algebras by applying the method of Gröbner-Shirshov bases. We establish the CompositionDiamond Lemma for free commutative differential Rota-Baxter algebras of order n. We also obtain
a weakly monomial order on these algebras, allowing us to obtain Gröbner-Shirshov bases for free
commutative integro-differential algebras on a set. We finally generalize the concept of functional
derivations to free differential algebras with arbitrary weight and generating sets from which to
construct a canonical linear basis for free commutative integro-differential algebras.

Contents
1. Introduction
1.1. Integro-differential algebras
1.2. Gröbner-Shirshov bases
1.3. Outline of the paper
2. Free commutative integro-differential algebras
2.1. The definitions
2.2. Free differential Rota-Baxter algebras
2.3. Free commutative operated algebras
3. Weakly monomial order
4. Composition-Diamond lemma
5. Groöbner-Shirshov bases and free commutative integro-differential algebras
5.1. Gröbner-Shirshov basis
5.2. Bases for free commutative integro-differential algebras
References

1
1
3
4
4
4
5
6
9
14
19
20
23
27

1. Introduction
1.1. Integro-differential algebras. The algebraic study in analysis has a long history. The first
monograph [30] of Ritt on algebraic study of differential equations appeared almost one hundred
years ago. The concept of a differential algebra was abstracted from the Leibniz formula
(1)

d(uv) = d(u)v + ud(v)

in calculus. After the fundamental works of Ritt [31] and Kolchin [28], the theory of differential
algebra has been expanded to a vast area of pure and applied mathematical study [13, 37]. The
Date: February 12, 2018.
2010 Mathematics Subject Classification. 16S15, 13P10, 16W99, 17A50, 12H05, 47G20 .
Key words and phrases. Differential algebra, Rota-Baxter algebra, integro-differential algebra, Gröbner-Shirshov
basis, free algebra, shuffle product, mixable shuffle product.
1

2

XING GAO, LI GUO, AND SHANGHUA ZHENG

algebraic study of the integral analysis began with the concept of a Baxter algebra [3], later called
a Rota-Baxter algebra. Here the basis of abstraction is the integration by parts formula,
(2)

P(u)P(v) = P(uP(v)) + P(P(u)v) + λP(uv),

Rx
rewritten in a form that only involves the integral operator P, defined by P(u)(x) := a u(t) dt.
The extra term parameterized by a constant λ allows both the integral operator (when λ = 0) and
the summation operator (when λ = 1), as well as quite a few other operators, to be encoded into
one equation. Since then, Rota-Baxter algebra has found broad applications from combinatorics
and number theory to classical Yang-Baxter equation and quantum field theory [2, 16, 18, 19, 25,
33, 34, 35].
Motivated by the close relationship between the differential and integral analysis as shown
in the First Fundamental Theorem of Calculus, coordinated studied of differential algebra and
Rota-Baxter algebra have emerged recently, beginning with the two simultaneously introduced
concepts of a differential Rota-Baxter algebra and an integro-differential algebra.
The concept of a differential Rota-Baxter algebra [22] is a simple coupling of a differential
operator d of weight λ:
(3)

d(uv) = d(u)v + ud(v) + λd(u)d(v), d(1) = 0,

with a Rota-Baxter operator P of the same weight by the abstraction of the First Fundamental
Theorem of Calculus
(4)

d ◦ P = id,

where id is the identity map. On the other hand, the concept of an integro-differential algebra,
first considered in the weight 0 case in [32] and in the general weight case in [23], also takes
into account the intertwining relationship of the two operators in the original definition of the
integration by parts formula
(5)

P(d(u)P(v)) = uP(v) − P(uv) − λP(d(u)v).

We note that Eq. (5) implies Eq. (2) at the presence of Eq. (4) when u is substituted by P(u).
Thus the variety of integro-differential algebras is the variety of differential Rota-Baxter algebras
modulo extra conditions. See [23] for further details.
As in the case of studying any algebraic structures, the free objects play an important role in the
study of previous algebras. While the construction of free differential algebras is straightforward
in terms of differential monomials, the construction of free Rota-Baxter algebras is more involved.
In fact, there are three constructions in the commutative case, with the first one given by Rota [33]
through an internal construction, and an external one given by Cartier [12]. In [20], a construction
is given by a generalization of the shuffle product, called the mixable shuffle product which is
closely related to the quasi-shuffle product [27] in the study of multiple zeta values.
By composing the construction of free differential algebras followed by that of the free RotaBaxter algebras, free differential Rota-Baxter algebras were obtained in [22]. Because of the
more intimate relationship of the differential and Rota-Baxter operators in an integro-differential
algebra, it is more challenging to construct free objects in the corresponding category even by the
previous remark on the variety of integro-differential algebras, free integro-differential algebras
are quotients of free differential Rota-Baxter algebras modulo the relation given by Eq. (5). The
first construction of free commutative integro-differential algebras was obtained in the recent paper [23]. There the construction makes essential use of an equivalent formulation of the condition
in Eq. (5) for the integro-differential algebra.

FREE COMMUTATIVE INTEGRO-DIFFERENTIAL ALGEBRAS AND GRÖBNER-SHIRSHOV BASES

3

1.2. Gröbner-Shirshov bases. In this paper, we apply the method of Gröbner-Shirshov bases to
give another construction of the free commutative integro-differential algebras on a set.
The method of Gröbner bases or Gröbner-Shirshov bases originated from the work of Buchburger [11] (for commutative polynomial algebras), Hironaka [26] (for infinite series algebras)
and Shirshov [36] (for Lie algebras). It has since become a fundamental method in commutative
algebra, algebraic geometry and computational algebra, and has been extended to many other
algebraic structures, notably associative algebras [4, 5]. In recent years, the method of GröbnerShirshov bases has been applied to a large number of algebraic structures to study problems on
normal forms, word problems, rewriting systems, embedding theorems, extensions, growth functions and Hilbert series. See [6, 8, 10] for further details.
This method also derives free objects in various categories, including the alternative constructions of free Rota-Baxter algebras and free differential Rota-Baxter algebras [7, 9]. The basic
idea is to prove a composition-diamond lemma that achieves a rewriting procedure to reduce any
element to certain “standard form”. Then the set of elements in standard form is a basis of the
free object.
We apply this method to construct a free commutative integro-differential algebra as the quotient of a free commutative differential Rota-Baxter algebra modulo the “hybrid” integral by part
formula in Eq. (5). In order to do so, we would expect to first establish a Composition-Diamond
Lemma for the free commutative differential Rota-Baxter algebra constructed in [22]. We should
then prove that the ideal generated by the defining relation of integro-differential algebras in
Eq. (5) has a Gröbner-Shirshov basis, thereby identifying a basis of a free commutative integrodifferential algebra as a canonical subset of the known basis of the free commutative differential
Rota-Baxter algebra. All these depend on the choice of a suitable monomial order on the set
of the basis elements of the free commutative differential Rota-Baxter algebra. However a moment’s thought reveals that such a monomial order does not exist for this algebra. To overcome
this difficulty, we consider this algebra as a filtered algebra with respect to the order of derivation
and study the filtration pieces first. Even there, we have to get along with a weakly monomial
order which fortunately suffices for our applications. So we are able to adapt the above process
of Gröbner-Shirshov bases and obtain a canonical basis for each of the filtration pieces. We then
check that this process is compatible with the filtration structure, allowing us to put these canonical bases for the filtration pieces together to form a canonical basis for the entire free commutative
integro-differential algebra. The following is our main theorem
Theorem 1.1. (=Theorem 5.13) Let X be a nonempty well-ordered set and A := k{X}. Let
X(k{X}) = X(k[∆X]), with the derivation d and Rota-Baxter operator P, be the free commutative differential Rota-Baxter algebra of weight λ on X. Let IID be the differential Rota-Baxter
ideal of X(k{X}) generated by
S := {P(d(u)P(v)) − uP(v) + P(uv) + λP(d(u)v) | u, v ∈ X(k{X})}.
Let A f be the submodule of A = k{X} spanned by functional monomials. Then the composition



M
 ֒→ X(A) → X(A)/IID
A ⊗ A⊗k
⊗
A
X(A) f := A ⊕ 
f
k≥0

of the inclusion and the quotient map is a linear bijection. Thus X(A) f gives an explicit construction of the free integro-differential algebra X(A)/IID .
It is interesting to note that our approach of Gröbner-Shirshov bases gives a different construction of free commutative integro-differential algebras than those in [23]. While the construction

4

XING GAO, LI GUO, AND SHANGHUA ZHENG

in [23] has a transparent product formula, the construction here has a simple description as a
submodule of the free differential Rota-Baxter algebra. By the uniqueness of the free objects, the
two constructions yield isomorphic integro-differential algebras. Thus it would be interesting to
compare the two constructions to reveal further the structure and properties of these free objects.
1.3. Outline of the paper. In Section 2, we first introduce the algebraic structures that lead up to
λ-integro-differential algebras and then recall the construction of free objects for these algebraic
structures, in particular the free commutative Rota-Baxter algebras and the free commutative
differential Rota-Baxter algebras. In Section 3, we first give definitions related to differential
Rota-Baxter monomials and then define a weakly monomial order on differential Rota-Baxter
monomials of order n. In Section 4, we start with defining various kinds of compositions and
then establish the Composition-Diamond Lemma for the n-th order free commutative differential
Rota-Baxter algebra. In Section 5, we consider a finite set X and obtain a Gröbner-Shirshov basis
for the defining ideal of a free commutative order n integro-differential algebra on X and thus
obtain an explicitly defined basis for this free object. Then as mentioned above, we put the order
n pieces together as a direct system to obtain a basis for the free commutative integro-differential
algebra on X. We then use a finiteness argument to treat the case when X is any well-ordered set.
2. Free commutative integro-differential algebras
We recall the definitions of algebras with various differential and integral operators and the
constructions of the free objects in the corresponding categories.
2.1. The definitions. We recall the algebraic structures considered in this paper. We also introduce variations with bounded derivation order that will be needed later.
Definition 2.1. Let k be a unitary commutative ring. Let λ ∈ k be fixed.
(a) A differential k-algebra of weight λ (also called a λ-differential k-algebra) is a unitary
associative k-algebra R together with a linear operator d : R → R such that
(6)

d(1) = 0, d(uv) = d(u)v + ud(v) + λd(u)d(v) for all u, v ∈ R.
Such an algebra (R, d) is said of order n, where n ≥ 1, if d n = 0.
(b) A Rota-Baxter k-algebra of weight λ is an associative k-algebra R together with a linear
operator P : R → R such that

(7)

P(u)P(v) = P(uP(v)) + P(P(u)v) + λP(uv) for all u, v ∈ R.
(c) A differential Rota-Baxter k-algebra of weight λ (also called a λ-differential RotaBaxter k-algebra) is a differential k-algebra (R, d) of weight λ and a Rota-Baxter operator
P of weight λ such that

(8)

d ◦ P = id.
(d) An integro-differential k-algebra of weight λ (also called a λ-integro-differential kalgebra) is a differential k-algebra (R, d) of weight λ with a linear operator P : R → R that
satisfies Eq. (8) and such that

(9)

P(d(u)P(v)) = uP(v) − P(uv) − λP(d(u)v) for all u, v ∈ R.

FREE COMMUTATIVE INTEGRO-DIFFERENTIAL ALGEBRAS AND GRÖBNER-SHIRSHOV BASES

5

2.2. Free differential Rota-Baxter algebras. We first recall the construction of free commutative differential algebras and introduce their order n variations.
Theorem 2.2. Let X be a set.
(a) Let ∆X = {x(n) | x ∈ X, n ≥ 0} and let k{X} = k[∆X] be the free commutative algebra on
the set ∆X. Define dX : k[∆X] → k[∆X] as follows. Let w = u1 · · · uk , ui ∈ ∆X, 1 ≤ i ≤ k,
be a commutative word from the alphabet set ∆X. If k = 1, so that w = x(n) ∈ ∆X, define
dX (w) = x(n+1) . If k > 1, recursively define
(10)

dX (w) = dX (u1 )u2 · · · uk + u1 dX (u2 · · · uk ) + λdX (u1 )dX (u2 · · · uk ).

Further define dX (1) = 0 and then extend dX to k[∆(X)] by linearity. Then (k[∆X], dX ) is
the free commutative differential algebra
of weight λ on othe set X.
n
(n+1)
(k)
(b) For a given n ≥ 1, let ∆X
:= x x ∈ X, k ≥ n + 1 . Then k{X}∆X (n+1) is the differential ideal In of k{X} generated by the set {x(n+1) | x ∈ X}. The quotient k{X}/In has a
canonical basis given by ∆n X := {x(k) | k ≤ n}.
Proof. Item (a) is from [22] and Item (b) is a direct consequence.



For a set Y, let C(Y) denote the free commutative monoid on Y. Thus elements in C(Y) are
commutative words, plus the identity 1, from the alphabet set Y. Then C(∆X) (resp. C(∆n X)) is a
linear basis of k[∆X] (resp. k[∆n X]).
We next recall the construction of free commutative Rota-Baxter algebras in terms of mixable
shuffles [20, 21]. The mixable shuffle product is shown to be the same as the quasi-shuffle product
of Hoffman [15, 25, 27]. Let A be a commutative k-algebra. Define
M
X(A) =
A⊗(k+1) = A ⊕ A⊗2 ⊕ · · · .
k≥0

and b = b0 ⊗ · · · ⊗ bn ∈ A⊗(n+1) . If m = 0 or n = 0, define


(a b ) ⊗ b1 ⊗ · · · ⊗ bn , m = 0, n > 0,


 0 0
(a
a⋄b=
0 b0 ) ⊗ a1 ⊗ · · · ⊗ am , m > 0, n = 0,


 ab,
m = n = 0.
0 0

Let a = a0 ⊗ · · · ⊗ am ∈ A
(11)

⊗(m+1)

If m > 0 and n > 0, inductively (on m + n) define

a ⋄ b = (a0 b0 ) ⊗ (a1 ⊗ a2 ⊗ · · · ⊗ am ) ⋄ (1 ⊗ b1 ⊗ · · · ⊗ bn )

(12)

+ (1 ⊗ a1 ⊗ · · · ⊗ am ) ⋄ (b1 ⊗ · · · ⊗ bn )

+λ (a1 ⊗ · · · ⊗ am ) ⋄ (b1 ⊗ · · · ⊗ bn ) .

Extending by additivity, we obtain a k-bilinear map

⋄ : X(A) × X(A) → X(A).
Alternatively,
a ⋄ b = (a0 b0 ) ⊗ (aXλ b),
where ā = a1 ⊗ · · · ⊗ am , b̄ = b1 ⊗ · · · ⊗ bn and Xλ is the mixable shuffle (quasi-shuffle) product of
weight λ [19, 20, 27], which specializes to the shuffle product X when λ = 0.
Define a k-linear endomorphism PA on X(A) by assigning
PA (x0 ⊗ x1 ⊗ · · · ⊗ xn ) = 1A ⊗ x0 ⊗ x1 ⊗ · · · ⊗ xn ,

6

XING GAO, LI GUO, AND SHANGHUA ZHENG

for all x0 ⊗ x1 ⊗ · · · ⊗ xn ∈ A⊗(n+1) and extending by additivity. Let jA : A → X(A) be the canonical
inclusion map.
Theorem 2.3. ([20, 21])
(a) The pair (X(A), PA ), together with the natural embedding jA : A → X(A), is the free
commutative Rota-Baxter k-algebra on A of weight λ. In other words, for any Rota-Baxter
k-algebra (R, P) and any k-algebra map ϕ : A → R, there exists a unique Rota-Baxter
k-algebra homomorphism ϕ̃ : (X(A), PA ) → (R, P) such that ϕ = ϕ̃ ◦ jA as k-algebra
homomorphisms.
(b) Let Y be a set and let k[Y] be the free commutative algebra on Y. The pair (X(Y), PY ) :=
(X(k[Y]), Pk[Y] ), together with the natural embedding jY : Y → k[Y] → X(k[Y]), is the
free commutative Rota-Baxter k-algebra of weight λ on Y.
Since ⋄ is compatible with the multiplication in A, we will often suppress the symbol ⋄ and
simply denote xy for x ⋄ y in X(A), unless there is a danger of confusion.
A linear basis of X(k[Y]) is given by
o
n
(13)
B(Y) := x0 ⊗ · · · ⊗ xk xi ∈ C(Y), 1 ≤ i ≤ k, k ≥ 0 ,

called the set of Rota-Baxter monomials in Y. The integer dep(x0 ⊗ · · · ⊗ xk ) := k + 1 is called
the depth of x0 ⊗ · · · ⊗ xk . To simplify notations, we also let P denote Pk[Y] . Then 1 ⊗ u and P(u)
stand for the same element and will be be used as convenience in this paper.
We now put the differential and Rota-Baxter algebra structures together. Let (A, d0 ) be a commutative differential k-algebra of weight λ. Extend d0 to X(A) by
dA (x0 ⊗ x1 ⊗ . . . ⊗ xk )
= d0 (x0 ) ⊗ x1 ⊗ . . . ⊗ xk + x0 x1 ⊗ x2 ⊗ . . . ⊗ xk + λd0 (x0 )x1 ⊗ x2 ⊗ . . . ⊗ xk ,

k ≥ 0.

Theorem 2.4. ([22]) Let X be a set and let k[∆X] be the free commutative differential algebra of
weight λ on X in Theorem 2.2.(a). The triple (X(k[∆X]), dk[∆X] , Pk[∆X]), together with jX : X →
∆X → X(k[∆X]), is the free commutative differential Rota-Baxter k-algebra of weight λ on X.
Apply the notations in Eq. (13) to Y := ∆X. The set
o
n
(14)
B(∆X) := u0 ⊗ · · · ⊗ uk ui ∈ C(∆X), 0 ≤ i ≤ k, k ≥ 0

is a k-basis of the free commutative differential Rota-Baxter algebra X(∆X), called the set of
differential Rota-Baxter (DRB) monomials on X.
Similarly with Y := ∆n X, n ≥ 1, B(∆n X) is a basis of X(∆n X) and is called the set of DRB
monomials of order n on X. We note that in X(k[∆n X]), the property d n+1 (u) = 0 only applies
to u ∈ X, but not to tensors of length greater than two. For example, taking n = 1, then d 2 (x) = 0,
but d(1 ⊗ x) = x and hence d 2 (1 ⊗ x) = d(x) = x(1) , 0.
2.3. Free commutative operated algebras. We now construct the free commutative operated
algebra on a set X that has the free commutative (differential) Rota-Baxter algebra as a quotient.
At the same time, the explicit construction X(X) of free commutative Rota-Baxter algebra in
Theorem 2.3 can be realized on a submodule of the free commutative operated algebra spanned
by reduced words under a rewriting rule defined by the Rota-Baxter axiom.
This construction is parallel to that of the free (noncommutative) operated algebra on a set
in [9, 17, 19, 24]. See [29] for the non-unitary case.

FREE COMMUTATIVE INTEGRO-DIFFERENTIAL ALGEBRAS AND GRÖBNER-SHIRSHOV BASES

7

Definition 2.5. A commutative operated monoid with operator set Ω is a commutative monoid
G together with maps αω : G → G, ω ∈ Ω. A homomorphism between commutative operated
monoids (G, {αω }ω ) and (H, {βω }ω ) is a monoid homomorphism f : G → H such that f ◦ αω =
βω ◦ f for ω ∈ Ω.
We next construct the free objects in the category of commutative operated monoids.
Fix a set Y. We define monoids Cn := Cn (Y) for n ≥ 0 by a recursion. First denote C0 := C(Y).
Let ⌊C(Y)⌋ω := {⌊u⌋ω | u ∈ C(Y)}, ω ∈ Ω, be disjoint sets in bijection with and disjoint from C(Y).
Then define
C1 := C(Y ⊔ (⊔ω∈Ω ⌊C(Y)⌋ω )).
Note that elements in ⌊C(Y)⌋ω are only symbols indexed by elements in C(Y). For example, ⌊1⌋ω is
not the identity, but a new symbol. The inclusion Y ֒→ Y ⊔(⊔ω∈Ω ⌊C0 ⌋ω ) induces a monomorphism
i0,1 : C0 = C(Y) ֒→ C1 = C(Y ⊔ (⊔ω ⌊C0 ⌋ω )) of free commutative monoids through which we
identify C0 with its image in C1 . Inductively assume that Cn−1 have been defined for n ≥ 2 and
that the embedding
in−2,n−1 : Cn−2 → Cn−1
has been obtained. We then define
Cn := C(Y ⊔ (⊔ω ⌊Cn−1 ⌋ω )).

(15)
We also have the injection
Thus by the freeness of Cn−1

⌊Cn−2 ⌋ω ֒→ ⌊Cn−1 ⌋ω , ω ∈ Ω.
= C(Y ⊔ (⊔ω ⌊Cn−2 ⌋ω )) as a free commutative monoid, we have

Cn−1 = C(Y ⊔ (⊔ω ⌊Cn−2 ⌋ω )) ֒→ C(Y ⊔ (⊔ω ⌊Cn−1 ⌋ω )) = Cn .
We finally define the commutative monoid
C(Y) :=

[
n≥0

Cn = lim Cn .
−→

Elements in C(Y) are called bracketed monomials in Y. Defining
(16)

⌊ ⌋ω : C(Y) → C(Y), u 7→ ⌊u⌋ω , ω ∈ Ω,

(C(Y), {⌊ ⌋ω }ω ) is a commutative operated monoid and its linear span (kC(Y), ⌊ ⌋ω ) is a commutative
(unitary) operated k-algebra.
Proposition 2.6. Let jY : Y → C(Y) be the natural embedding.
(a) The triple (C(Y), {⌊ ⌋ω }ω , jY ) is the free commutative operated monoid on Y. More precisely,
for any commutative operated monoid G and set map f : Y → G, there is a unique
extension of f to a homomorphism f¯ : C(Y) → G of operated monoids.
(b) The triple (kC(Y), {⌊ ⌋ω }ω , jY ) is the free commutative operated unitary k-algebra on Y.
More precisely, for any commutative k-algebra R and set map f : Y → R, there is a
unique extension of f to a homomorphism f¯ : kC(Y) → R of operated k-algebras.
Proof. We only need to show that C(Y) is a free commutative operated monoid. The proof is
similar to the noncommutative case [17, 19], so we just give a sketch.
Let a commutative operated monoid (G, {αω }ω ) and a map f : Y → G be given. Then by
the universal property of C0 := C(Y), there is a unique monoid homomorphism f0 : C0 → G
extending f . Then f0 extends uniquely to
f1 : ⌊C0 ⌋ω → G,

⌊u⌋ω 7→ αω ( f0 (u)), u ∈ C0 ,

8

XING GAO, LI GUO, AND SHANGHUA ZHENG

such that ( f1 ◦ ⌊ ⌋ω )(u) = (αω ◦ f1 )(u), ω ∈ Ω, when defined. We then further get a monoid
homomorphism
f1 : C1 := C(Y ⊔ (⊔ω ⌊C0 ⌋ω )) → G.
By induction on n ≥ 0 we obtain a unique fn : Cn → G, n ≥ 0, compatible with the direct system,
yielding the unique homomorphism f¯ : C(Y) → G of operated monoids.

By the universal property of kC(Y), we obtain the following conclusion from general principles
of universal algebra [1, 14].
Proposition 2.7. Let Ω = {d, P} and denote d(u) := ⌊u⌋d , P(u) := ⌊u⌋P . Let IDRB be the operated
ideal of kC(Y) generated by the set




d(uv) − d(u)v − ud(v) − λd(u)d(v),






P(u)P(v)
−
P(uP(v))
−
P(P(u)v)
−
λP(uv),
.
u,
v
∈
C(Y)







 (d ◦ P)(u) = u
Then the quotient operated algebra kC(Y)/IDRB , with the quotient of the operator d and P, is the
free commutative differential Rota-Baxter algebra.
Combining Proposition 2.7 with Theorem 2.3, we have
Proposition 2.8. The natural embedding
X(k[∆X])

→ k C(∆X),

x0 ⊗ x1 ⊗ · · · ⊗ xk 7→ x0 P(x1 P(· · · P(xk ) · · · ))

composed with the quotient map ρ : k C(∆X) → k C(∆X)/IDRB gives a linear bijection (in fact,
an isomorphism of differential Rota-Baxter algebras)
θ : X(k[∆X]) → k C(∆X)/IDRB .
Through θ, we can identify the basis B(∆X) of X(k∆X) with its image in kC(∆X):
(17)

u0 ⊗ u1 ⊗ · · · ⊗ uk ↔ u0 ⌊u1 ⌊· · · ⌊uk ⌋ · · ·⌋⌋ ↔ u0 P(u1 P(· · · P(uk ) · · · )).

Thus we also use P for P∆X on X(k[∆X]) and d ℓ (x) = x(ℓ) for x ∈ X and ℓ ≥ 0.
As a consequence of Proposition 2.8, we have
Corollary 2.9. Let n ≥ 1. Let IDRB,n be the operated ideal of C(X) generated by IDRB together
with the set {x(n+1) = d n+1 (x) | x ∈ X}. The natural embedding
X(k[∆n X])

→ kC(X),

x0 ⊗ x1 ⊗ · · · ⊗ xk 7→ x0 P(x1 P(· · · P(xk ) · · · ))

composed with the quotient map ρ : k C(Y) → kC(Y)/IDRB,n gives a linear bijection
θn : X(k[∆n X]) → kC(X)/IDRB,n .
Proof. The map θn is obtained by starting from the isomorphism θ : X(k[∆X])  kC(X)/IDRB
and then taking the quotients of both the domain and range by the operated ideal generated by
d n+1 (x), x ∈ X. Since θ restricted to the identity on X. The corollary follows.

Define the reduction map
(18)

Red := Redn := θn−1 ◦ ρ : k C(X) → kC(Y)/IDRB,n → X(k[∆n X]).

It reduces any bracketed monomial to a DRB monomial. For example, if u, v ∈ C(X), then
Red(⌊u⌋⌊v⌋) = 1 ⊗ u ⊗ v + 1 ⊗ v ⊗ u + λ ⊗ uv.

FREE COMMUTATIVE INTEGRO-DIFFERENTIAL ALGEBRAS AND GRÖBNER-SHIRSHOV BASES

9

3. Weakly monomial order
In this section, we will give a weak form of the monomial order on filtered pieces of the set
of differential Rota-Baxter monomials. It will be sufficient for us to establish the compositiondiamond lemma for integro-differential algebras.
Let Y be a set with well order ≤Y . Define the length-lexicographic order ≤∗Y,lex on the free
monoid M(Y) by
(
ℓ < m,
∗
(19)
u <Y,lex v ⇔
or ℓ = m and ∃1 ≤ i0 ≤ ℓ such that ui = vi for 1 ≤ i < i0 and ui0 < vi0 ,
where u = u1 · · · uℓ and v = v1 · · · vm with ui ∈ Y, 1 ≤ i ≤ ℓ, v j ∈ Y, 1 ≤ j ≤ m, m, n ≥ 1. It is
well-known [1] that ≤∗Y,lex is still a well order. An element 1 , u of the free commutative monoid
C(Y) can be uniquely expressed as
(20)

u = u0j0 · · · ukjk , where u0 , · · · , uk ∈ Y, j0 , · · · , jk ∈ Z≥1 and u0 > · · · > uk .

This expression is called the standard form of u. If k = −1, we take u ∈ k by convention.
Any 1 , u ∈ C(Y) can also be expressed uniquely as
u = u1 · · · uℓ , u1 ≥ u2 ≥ · · · ≥ uℓ ∈ Y.
With this notation, C(Y) can be identified with a subset of the free monoid M(Y) on Y. Then the
well order <∗Y,lex on M(Y) restricts to a well order on C(Y).
Lemma 3.1. Let (Y, ≤Y ) is a well-ordered set and u, v ∈ C(Y). If u < v, then uw ≤∗Y,lex vw for
w ∈ C(Y).
Proof. Such a result is well-known for free noncommutative monoid. The proof for the commutative case is different and we sketch a proof for completeness.
From the standard decomposition of u ∈ C(Y) in Eq. (20), u can be expressed uniquely as a
function
(
ji , y = ui , 1 ≤ i ≤ k,
(21)
f := fu : Y → Z≥0 , fu (y) =
0, otherwise.
Thus C(Y) can be identified with
F := { f : Y → Z≥0 | Supp( f ) := Y\ f −1(0) is finite }
P
with 1 ∈ C(Y) corresponding to f1 ≡ 0. Denote deg( f ) := y∈Y f (y). Under this identification,
the order ≤∗Y,lex on C(Y) is identified with the order ≤ on F defined by
(22)
(
deg( f ) < deg(g)
f <g⇔
or deg( f ) = deg(g) and ∃y0 ∈ Y such that f (y) = g(y) for y < y0 and f (y0 ) < g(y0 ).
Let u, v, w ∈ C(Y) be given. We apply the identification of u, v, w with fu , fv , fw ∈ F given in
Eq (21). We note that fuw = fu + fw and fvw = fv + fw . Thus we have
deg( fuw ) = deg( fu ) + deg( fw ), deg( fvw ) = deg( fv ) + deg( fw ), and fu (y) < fv (y) ⇔ fuw (y) < fvw (y).
Then it follows that fu < fv if and only if fuw < fvw . This proves the lemma.



For a set X, recall that ∆X = {x(k) | x ∈ X, k ≥ 0} and ∆n X := {x(k) | x ∈ X, 0 ≤ k ≤ n} for
n ≥ 0. Then C(∆n X), n ≥ 0, define an increasing filtration on C(∆X) and hence give a filtration
B(∆n X) ⊆ B(∆X). Elements of B(∆n X) are called DRB monomials of order n.

10

XING GAO, LI GUO, AND SHANGHUA ZHENG

Definition 3.2. Let X be a set, ⋆ a symbol not in X and ∆n X ⋆ := ∆n (X ∪ {⋆}).
(a) By a ⋆-DRB monomial on ∆n X, we mean any expression in B(∆n X ⋆ ) with exactly one
occurrence of ⋆. The set of all ⋆-DRB monomials on ∆n X is denoted by B⋆ (∆n X).
(b) For q ∈ B⋆ (∆n X) and u ∈ B(∆n X), we define
q|u := q|⋆7→u
to be the bracketed monomial in C(∆n X) obtained by replacing the letter ⋆ in q by u, and
call q|u a u-monomial
P on ∆n X.
(c) Further, for s = i ci ui ∈ kB(∆n X), where ci ∈ k, ui ∈ B(∆n X) and q ∈ B⋆ (∆n X), we
define
X
q| s :=
ci q|ui ,
i

which is in k C(∆n X).
We note that a ⋆-DRB monomial q is a DRB monomial in ∆n X ⋆ while its substitution q|u might
not be a DRB monomials. For example, for q = P(x1 )⋆ ∈ B(∆n X ⋆ ) and u = P(x2 ) ∈ B(∆n X)
where x1 , x2 ∈ X, the u-monomial q|u = P(x1 )P(x2 ) is no longer in B(∆n X).
Lemma 3.3. Let S be a subset of kC(∆n (X)) and Id(S) be the operated ideal of kC(∆n (X)) generated by S . Then

 k


X




⋆
c
∈
k,
q
∈
C
(∆
X),
s
∈
S
,
1
≤
i
≤
k,
k
≥
1
.
Id(S) = 
c
q
|

i
i
n
i
i i si




i=1

Proof. It is easy to see that the right hand side is contained in the left side. On the other hand, the
right hand side is already an operated ideal of kC(∆n (X)) containing S .

Definition 3.4. If q = p|dℓ (⋆) for some p ∈ B⋆ (∆n X) and ℓ ∈ Z≥1 , then we call q a type I ⋆-DRB
monomial. Let B⋆I (∆n X) denote the set of type I ⋆-DRB monomials on ∆n X and call
B⋆II (∆n X) := B⋆ (∆n X) \ B⋆I (∆n X)
the set of type II ⋆-DRB monomials.
Lemma 3.5. Any element q ∈ B⋆ (∆n X) is one of the following three forms
(a) q ∈ B⋆I (∆n X), or
(b) q = s ⋆ t with s ∈ C(∆n X) and t ∈ B(∆n X), or
(c) q = sP(p) for some s ∈ C(∆n X) and p ∈ B⋆II (∆n X).
Proof. Any element q ∈ B⋆ (∆n X) is of the form u0 ⊗ u1 ⊗ · · · ⊗ uk with ui ∈ C(∆n X), 1 ≤ i ≤ k,
except a unique ui which is in C(∆n X ⋆ ) with exactly one occurrence of ⋆. In turn, this unique
ui ∈ C(∆n X ⋆ ) is of the form ui1 · · · uim with ui j ∈ ∆n X, 1 ≤ j ≤ m, except a unique ui j which is in
∆n X ⋆ with exactly one occurrence of ⋆. Thus this unique ui j ∈ ∆n X ⋆ is of the for d ℓ (⋆) for some
ℓ ≥ 0. If ℓ ≥ 1, then q is of type I. If ℓ = 0, then d ℓ (⋆) = ⋆. So if i = 0, namely this ⋆ is in u0 , then
q = (u01 · · · u0( j−1) ⋆u0( j+1) · · · u0m )⊗u1 ⊗· · · uk is of the form s⋆t with s = u01 · · · u0( j−1) u0( j+1) · · · u0m
and t = 1 ⊗ u2 · · · uk . If i ≥ 1, then q = sP(p), where p := u2 ⊗ · · · uk ∈ B⋆II (∆n X). This proves the
lemma.

Definition 3.6. Let X be a set, ⋆1 , ⋆2 two distinct symbols not in X and ∆n X ⋆1 ,⋆2 := ∆n (X ∪
{⋆1 , ⋆2 }). We define a (⋆1 , ⋆2 )-DRB monomial on ∆n X to be an expression in B(∆n X ⋆1 ,⋆2 ) with
exactly one occurrence of ⋆1 and exactly one occurrence of ⋆2 . The set of all (⋆1 , ⋆2 )-DRB

FREE COMMUTATIVE INTEGRO-DIFFERENTIAL ALGEBRAS AND GRÖBNER-SHIRSHOV BASES

11

monomials on ∆n X is denoted by B⋆1 ,⋆2 (∆n X). For q ∈ B⋆1 ,⋆2 (∆n X) and u1 , u2 ∈ kB(∆n X), we
define
q|u1 ,u2 := q|⋆1 7→u1 ,⋆2 7→u2
to be the bracketed monomial obtained by replacing the letter ⋆1 (resp. ⋆2 ) in q by u1 (resp. u2 )
and call it a (u1 , u2 )-bracketed monomial on ∆n X .
A (u1 , u2)-DRB monomial on ∆n X can also be recursively defined by
(23)

q|u1 ,u2 := (q⋆1 |u1 )|u2 ,

where q⋆1 is q when q is regarded as a ⋆1 -DRB monomial on the set ∆n X ⋆2 . Then q⋆1 |u1 is in
B⋆2 (∆n X). Similarly, we have
(24)

q|u1 ,u2 := (q⋆2 |u2 )|u1 .

Let X be a well-ordered set and let Y = ∆X. Let n ≥ 0 be given. For x(i0 0 ) , x(i1 1 ) ∈ ∆X (resp. ∆n X)
with x0 , x1 ∈ X, define


(25)
x(i0 0 ) ≤ x(i1 1 ) resp.x0(i0 ) ≤n x1(i1 ) ⇔ (x0 , −i0 ) ≤ (x1 , −i1 ) lexicographically.

(2)
For example x(2) < x(1) < x. Also, x1 < x2 implies x(2)
1 < x2 . Then by [1], the order ≤n is a well
order on ∆n X and hence is extended to a well order on C(∆n X) by Eq. (19) which we still denote
by ≤n .
We next extend the well order ≤n on C(∆n X) defined above to B(∆n X). Note that

B(∆n X) = {u0 ⊗ u1 ⊗ · · · uk | ui ∈ C(∆n X), 1 ≤ i ≤ k, k ≥ 0} = ⊔k≥1C(∆n X)⊗k
can be identified with the free semigroup on the set C(∆n X). Thus the well order ≤n on C(∆n X)
extends to a well order ≤∗n,lex [1] which we will still denote by ≤n for simplicity. More precisely,
for any u = u0 ⊗ · · · ⊗ uk ∈ C(∆n X)⊗(k+1) and v = v0 ⊗ · · · ⊗ vℓ ∈ C(∆n X)⊗(ℓ+1) , define
(26)

u ≤n v if (k + 1, u0, · · · , uk ) ≤ (ℓ + 1, v0 , · · · , vℓ ) lexicographically.

This is the order on B(∆n X) that we will consider in this paper.
Definition 3.7. Let ≤n be the well order on B(∆n X) defined in Eq. (26). Let q ∈ B⋆ (∆n X) and
s ∈ kB(∆n X).
P
(a) For any 0 , f ∈ kB(∆n X), let f denote the leading term of f : f = c f + i ci ui , where
0 , c, ci ∈ k, ui ∈ B(∆n X), ui < f . f is called monic if c = 1.
(b) Denote
q| s := Red(q| s ),
where Red : kC(∆n X) → X(∆n X) = kB(∆n X) is the reduction map in Eq. (18).
(c) The element q| s ∈ k C(∆n X) is called normal if q| s is in B(∆n X). In other words, if
Red(q| s ) = q| s .
Remark 3.8.
(a) By definition, q| s is normal if and only if q| s is normal if and only if the
s-DRB monomial q| s is already a DRB monomial, that is, no further reduction in X(∆n X)
is possible.
(b) Examples of not normal (abnormal) s-DRB monomials are
(i) q = ⋆P(x) and s̄ = P(x), giving q| s = P(x)P(x) which is reduced to P(xP(y)) +
P(P(x)y) + λP(xy) in X(∆n X);
(ii) q = d(⋆) and s̄ = P(x), giving q| s̄ = d(P(x)) which is reduced to x in X(∆n X);

12

XING GAO, LI GUO, AND SHANGHUA ZHENG

(iii) q = d(⋆) and s̄ = x2 , giving q| s̄ = d(x2 ) which is reduced to 2xx(1) + λ(x(1) )2 in
X(∆n X);
(iv) q = d n (⋆) and s̄ = d(x), giving q| s̄ = d n+1 (s) which is reduced to 0 in X(∆n X).
Definition 3.9. A weakly monomial order on B(∆n X) is a well order ≥ satisfying the following
condition:
for u, v ∈ B(∆n X), u > v ⇒ q|u > q|v if either q ∈ B⋆II (∆n X), or q ∈ B⋆I (∆n X) and q|u is normal.
We shall prove that the order defined in Eq. (26) is a weakly monomial order on B(∆n X). We
need the following lemmas.
Lemma 3.10. Let ℓ ≥ 1 and s ∈ B(∆n X). Then d ℓ (⋆)| s is normal if and only if s ∈ ∆n−ℓ X.
Proof. If s ∈ ∆n−ℓ X, then d ℓ (s) is in ∆n X and hence d ℓ (⋆)| s is normal. Conversely, if s < ∆n−ℓ X,
then either dep(s) ≥ 2, or dep(s) = 1 and deg∆n X (u) ≥ 2, or s ∈ ∆n X \ ∆n−ℓ X. In all these cases,
d ℓ (⋆)| s is not normal.

Lemma 3.11. Let ≤n be the order defined in Eq. (26). Let u, v ∈ B(∆n X) and ℓ ∈ Z≥1 . If u >n v
and d ℓ (⋆)|u is normal, then d ℓ (u) >n d ℓ (v).
Proof. We prove the result by induction on ℓ. We first consider ℓ = 1 and prove d(u) >n d(v).
Since d(⋆)|u is normal, we have u = x(i1 1 ) ∈ ∆n−1 X by Lemma 3.10. Since u >n v, by the definition
of >n , we have we have v = x2(i2 ) ∈ ∆n X with either x1 > x2 or x1 = x2 and i1 < i2 . So d(u) >n d(v).
Next, suppose the result holds for 1 ≤ m < ℓ. Then by the induction hypothesis, we have
d ℓ (u) = d(d ℓ−1(u)) = d(d ℓ−1 (u)) >n d(d ℓ−1 (v)) = d(d ℓ−1 (v)) = d ℓ (v).

Proposition 3.12. The order ≤n defined in Eq. (26) is a weakly monomial order.
Proof. Let u, v ∈ B(∆n X) with u >n v and q ∈ B⋆ (∆n X). By Lemma 3.5 we have the following
three cases to consider.
Case 1. Consider q = s ⋆ t where s ∈ C(∆n X) and t ∈ B(∆n X). Note that B(∆n X) = C(∆n X) ⊔
C(∆X)P(B(∆n X)). We consider the following four subcases depending on t or u in C(∆n X) or
C(∆X)P(B(∆n X)).
Subcase 1.1. Let t, u ∈ C(∆n X). Since u >n v, we have that v ∈ C(∆n X) and so by Lemma 3.1,
q|u = sut >n svt = q|v .
Subcase 1.2. Let t ∈ C(∆n X)P(B(∆n X)) and u ∈ C(∆n X). Let t = t0 ⊗ · · · ⊗ tm with m ≥ 1. Since
u >n v, we have v ∈ C(∆n X). By Lemma 3.1 and Eq. (26), we have
(m + 1, sut0, t1 , · · · , tm ) > (m + 1, svt0 , t1, · · · , tm )

lexicographically.

So q|u = (sut0 ) ⊗ t1 ⊗ · · · ⊗ tm >n (svt0 ) ⊗ t1 ⊗ · · · ⊗ tm = q|v .
Subcase 1.3. Let t ∈ C(∆n X) and u ∈ C(∆n X)P(B(∆n X)). Let u = u0 ⊗ · · · ⊗ uk with k ≥ 1. If
v ∈ C(∆n X), it is obvious that
q|u = (stu0) ⊗ · · · ⊗ uk >n q|v = svt.
If v ∈ C(∆n X)P(B(∆n X)), let v = v0 ⊗ · · · ⊗ vm with m ≥ 1. Then q|v = (stv0 ) ⊗ · · · ⊗ vm . Since
u >n v, by Eq. (26), we have that
(k + 1, u0, · · · , uk ) > (m + 1, v0 , · · · , vm )

lexicographically.

FREE COMMUTATIVE INTEGRO-DIFFERENTIAL ALGEBRAS AND GRÖBNER-SHIRSHOV BASES

13

By Lemma 3.1, it follows that
(k + 1, stu0, u1 , · · · , uk ) > (m + 1, stv0, v1 , · · · , vm )

lexicographically,

that is, q|u >n q|v .
Subcase 1.4. Let t, u ∈ C(∆n X)P(B(∆n X)). Let t = t1 ⊗ t˜ = t0 P(t˜) and u = u0 ⊗ ũ = u0 P(ũ), where
t0 , u0 ∈ C(∆n X), t˜, ũ ∈ B(∆n X). If v ∈ C(∆n X), then
q|v = (svt0 )P(t˜)

and

q|u = st0 u0 P(t˜)P(ũ) = st0 u0 P(t˜)P(ũ).

Thus dep(q|u ) > dep(q|v ) and so q|u >n q|v . If v ∈ C(∆X)P(B(∆n X)), let v = v0 ⊗ ṽ = v0 P(ṽ).
Then q|v = st0 v0 P(t˜)P(ṽ) = st0v0 P(t˜)P(ṽ). Since u >n v, we have dep(ũ) + 1 = dep(u) ≥ dep(v) =
dep(ṽ) + 1 by Eq. (26) and so dep(ũ) ≥ dep(ṽ). If dep(ũ) > dep(ṽ), then dep(q|u ) > dep(q|v ) and
so q|u >n q|v . Suppose dep(ũ) = dep(ṽ). Then dep(q|u ) = dep(q|v ). If u0 >n v0 , then st0 u0 >n st0 v0
by Lemma 3.1 and so q|u >n q|v by Eq. (26). We are left to consider the case dep(ũ) = dep(ṽ) and
u0 = v0 . In this case, since u >n v, we have that ũ >n ṽ. If ũ >n ṽ ≥ t˜, then
q|u = (st0 u0 )P(t˜)P(ũ) = (st0 u0 )P(ũP(t˜)) = (st0 u0 ) ⊗ ũ ⊗ t˜
>n (st0 v0 ) ⊗ ṽ ⊗ t˜ = (st0 v0 )P(ṽP(t˜)) = (st0 v0 )P(t˜)P(ṽ) = q|v .
If t˜ ≥ ũ >n ṽ, then
q|u = (st0 u0 )P(t˜)P(ũ) = (st0 u0 )P(t˜P(ũ)) = (st0 u0 ) ⊗ t˜ ⊗ ũ
>n (st0 v0 ) ⊗ t˜ ⊗ ṽ = (st0 u0 )P(t˜P(ṽ)) = (st0 u0 )P(t˜)P(ṽ) = q|v .
If ũ >n t˜ >n ṽ, then
q|u = (st0 u0 )P(t˜)P(ũ) = (st0 u0 )P(ũP(t˜)) = (st0 u0 ) ⊗ ũ ⊗ t˜
>n (st0 v0 ) ⊗ t˜ ⊗ ṽ = (st0 u0 )P(t˜P(ṽ)) = (st0 u0 )P(t˜)P(ṽ) = q|v .
Case 2. Consider q = sP(p) for some s ∈ C(∆n X) and p ∈ B⋆ (∆n X). This case can be verified by
induction on dep(q) and the fact that, for u, v ∈ B(∆n X), u >n v implies P(u) >n P(v).
Case 3. Consider q ∈ B⋆I (∆n X). Then q = p|dℓ (⋆) for some p ∈ B⋆ (∆n X) and ℓ ∈ Z≥1 . Take such ℓ
maximal so that p ∈ B⋆II (∆n X). We need to show that if u >n v and q|u is normal, then q|u >n q|v .
But if q|u is normal then d ℓ (⋆)|u is normal. Then by Lemma 3.11, we have d ℓ (u) >n d ℓ (v). Then

by Cases 1 and 2, we have q|u = p|dℓ (u) >n p|dℓ (v) = q|v . This completes the proof.
We give the following consequences of Proposition 3.12 to be applied in Section 4.
Lemma 3.13. Let q ∈ B⋆ (∆n X) and s ∈ kB(∆n X) be monic. If q| s is normal, then q| s = q| s .
P
P
Proof. Let s = s + i ci si with 0 , ci ∈ k and si < s. Then q| s = q| s + i ci q| si . Since q| s is normal,
it follows that q| s ∈ B(∆n X) and so q| s = q| s . We have the following two cases to consider.
Case I. q ∈ B⋆II (∆n X). Then q| si < q| s = q| s by Definition 3.9 and Proposition 3.12. Hence
q| s = q| s = q| s .
Case II. q ∈ B⋆I (∆n X). Then q = p|dℓ (⋆) for some p ∈ B⋆ (∆n X) and ℓ ∈ Z≥1 . Since q| s = p|dℓ (s) is
normal, we have s ∈ ∆n−ℓ X by Lemma 3.10. Furthermore, si < s implies that si ∈ ∆n X. Thus by
Definition 3.9 and Proposition 3.12, we have q| si < q| s . So q| s = q| s .

Lemma 3.14. Let u, v ∈ B(∆n X) with u > v and q ∈ B⋆ (∆n X). If q|u is normal, then either q|v = 0
or q|v is also normal.

14

XING GAO, LI GUO, AND SHANGHUA ZHENG

Proof. Suppose that q|v is not normal. Then q|v < B(∆n X). We have the following cases to
consider.
Case I. dep(v) ≥ 2, that is, v ∈ C(∆n X)P(B(∆n X)), and q = p|⋆P(w) for some p ∈ B⋆ (∆n X) and
w ∈ B(∆n X). Since u > v, it follows that dep(u) ≥ dep(v) ≥ 2 and so u ∈ C(∆n X)P(B(∆n X)).
This implies that q|u can be reduced by the Rota-Baxter relation and so q|u < B(∆n X). Hence q|u
is not normal, a contradiction.
Case II. q = p|dℓ (⋆) for some p ∈ B⋆ (∆n X) and ℓ ≥ 1. If dep(v) ≥ 2, then since u > v, we have
dep(u) ≥ 2 and so u ∈ C(∆n X)P(B(∆n X)). This implies that q|u is not normal, a contradiction.
If dep(v) = 1, then v ∈ C(∆n X). If further deg∆n X (v) ≥ 2, then since u > v, we have either
dep(u) ≥ 2, or dep(u) = 1 and deg∆n X (u) ≥ 2. In either case, we have that q|u is not normal,
a contradiction. Thus we must have dep(v) = 1 and deg∆n X (v) = 1. So v = x(r) , r ≥ 1. Since
q|v = p|dℓ (v) = p| x(ℓ+r) is supposed to be not normal, we have ℓ + r > n. That is, q|v = p|dℓ (v) = 0. 
4. Composition-Diamond lemma
In this section, we shall establish the composition-diamond lemma for the order n free commutative differential Rota-Baxter algebra X(k[∆n X]).
Definition 4.1.
(a) Let u, w ∈ B(∆n X). We call u a subword of w if w is in the operated
ideal of C(∆n X) generated by u. In terms of ⋆-words, u is a subword of w if there is a
q ∈ B⋆ (∆n X) such that w = q|u .
(b) Let u1 and u2 be two subwords of w. u1 and u2 are called separated if u1 ∈ C(∆n X),
u2 ∈ B(∆n X) and there is a q ∈ B⋆1 ,⋆2 (∆n X) such that w = q|u1 ,u2 .
(c) For any u ∈ B(∆n X), u can be expressed as u = u1 · · · uk , where u1 , · · · , uk−1 ∈ ∆n X and
uk ∈ ∆n X ∪ P(B(∆n X)). The integer k is called the breath of u and is denoted by bre(u).
(d) Let f, g ∈ B(∆n X). A pair (u, v) with u ∈ B(∆n X) and v ∈ C(∆n X) is called an intersection
pair for ( f, g) if the differential Rota-Baxter monomial w := f u equals vg and satisfies
bre(w) < bre( f ) + bre(g). Then we call f and g to be overlapping. Note that if f and g
are overlapping, then f ∈ C(∆n X).
There are four kinds of compositions.
Definition 4.2. Let ≤ be a weakly monomial order on B(∆n X) and f, g ∈ kB(∆n X) monic with
respect to ≤.
(a) If f ∈ C(∆n X)P(B(∆n X)), then define a composition of (right) multiplication to be f u
where u ∈ C(∆n X)P(B(∆n X)).
(b) If f < ∆n X, then define a composition of derivation to be d ℓ ( f ), where ℓ ∈ Z≥1 .
(c) If there is an intersection pair (u, v) for ( f , g), then we define
( f, g)w := ( f, g)u,v
w := f u − vg
and call it an intersection composition of f and g.
(d) If there exists a q ∈ B⋆ (∆n X) such that w := f = q|g , then we define ( f, g)w := ( f, g)qw :=
f − q|g and call it an including composition of f and g with respect to q. Note that if this
is the case, then q|g is normal.
In the last two cases, ( f, g)w is called the ambiguity of the composition.
Definition 4.3. Let ≤ be a weakly monomial order on B(∆n X), S ⊆ kB(∆n X) be a set of monic
differential Rota-Baxter polynomials and w ∈ B(∆n X).

FREE COMMUTATIVE INTEGRO-DIFFERENTIAL ALGEBRAS AND GRÖBNER-SHIRSHOV BASES

15

(a) An element h ∈ kB(∆n X) is called trivial mod [S ] and denote this by
h ≡ 0 mod [S ]
if h = i ci qi | si , where ci ∈ k, qi ∈ B⋆ (∆n X), si ∈ S , qi | si is normal and qi | si ≤ h. This
applies in particular to a composition of multiplication f u and a composition of derivation
d ℓ ( f ) where f ∈ kB(∆n X), u ∈ P(B(∆n X)) and ℓ ≥ 1. We use mod [S ] to distinguish from
the usual notion of u ≡ 0 mod (S ) when u is in the ideal generated by S .
(b) For u, v ∈ kB(∆n X), we call u and v congruent modulo (S , w) and denote this by
P

u ≡ v mod (S , w)
if u − v = i ci qi | si , where ci ∈ k, qi ∈ B⋆ (∆n X), si ∈ S , qi | si is normal and qi | si < w.
(c) For f, g ∈ kB(∆n X) and suitable u, v or q that give an intersection composition ( f, g)u,v
w or
q
an including composition ( f, g)w , the composition is called trivial modulo (S , w) if
P

q
( f, g)u,v
w or ( f, g)w ≡ 0 mod (S , w).

(d) The set S ⊆ kB(∆n X) is a Gröbner-Shirshov basis if all compositions of multiplication
and derivation are trivial mod [S ], and, for f, g ∈ S , all intersection compositions ( f, g)u,v
w
and all including compositions ( f, g)qw are trivial modulo (S , w).
We give some preparational lemmas before establishing the Composition-Diamond Lemma.
Lemma 4.4. Let ≥ be the weakly monomial order on B(∆n X) defined in Eq. (26), s1 , s2 ∈
kB(∆n X), q1 , q2 ∈ B⋆ (∆n X) and w ∈ B(∆n X) such that w = q1 | s1 = q2 | s2 , where each qi | si is
normal, i = 1, 2. If s1 and s2 are separated in w, then q1 | s1 ≡ q2 | s2 mod (S , w).
Proof. Let q ∈ B⋆1 ,⋆2 (∆n X) be the (⋆1 , ⋆2 )-DRB monomial obtained by replacing this occurrence
of s1 in w by ⋆1 and this occurrence of s2 in w by ⋆2 . Then we have
q⋆1 | s1 = q2 , q⋆2 | s2 = q1 and q| s1 ,s2 = q1 | s1 = q2 | s2 ,
⋆2
⋆1
⋆
where in the
P first two equalities,Pwe have identified B (∆n X) and B (∆n X) with B (∆n X). Let
s1 − s1 = i ci ui and s2 − s2 = j d j v j with ci , d j ∈ k and ui , v j ∈ B(∆n X). Then by the linearity
of s1 and s2 in q| s1 ,s2 , we have

q1 | s1 − q2 | s2 = (q⋆2 | s2 )| s1 − (q⋆1 | s1 )| s2
= q| s1 ,s2 − q| s1 ,s2
= q| s1 ,s2 − q| s1 ,s2 + q| s1 ,s2 − q| s1 ,s2
= −q| s1 ,s2 −s2 + q| s1 −s1 ,s2
= −(q⋆2 | s2 −s2 )| s1 + (q⋆1 | s1 −s1 )| s2
X
X
=−
d j (q⋆2 |v j )| s1 +
ci (q⋆1 |ui )| s2
j

=−

X
j

i

d j q| s1 ,v j +

X

ci q|ui ,s2 .

i

Since (q⋆1 | s1 )| s2 = q| s1 ,s2 = (q⋆2 | s2 )| s1 = q1 | s1 is normal and v j < s2 , by Definition 3.9 and Proposition 3.12, we have
q| s1 ,v j = (q⋆1 | s1 )|v j < (q⋆1 | s1 )| s2 = q1 | s1 = q1 | s1 = w.
Similarly, since (q⋆2 | s2 )| s1 = q| s1 ,s2 = (q⋆1 | s1 )| s2 = q2 | s2 is normal and ui < s1 , we have
q|ui ,s2 = (q⋆2 | s2 )|ui < (q⋆2 | s2 )| s1 = q2 | s2 = q2 | s2 = w.

16

XING GAO, LI GUO, AND SHANGHUA ZHENG

Hence q1 | s1 ≡ q2 | s2 mod (S , w).



For q ∈ B⋆ (∆n X), let dep⋆ (q) be the depth of the symbol ⋆ in q. For example, dep⋆ (q) = 1 if
q = P(⋆) and dep⋆ (q) = 2 if q = P(xP(⋆)).
Lemma 4.5. Let ≤n be the weakly monomial order on B(∆n X) defined in Eq. (26) and let S ⊆
kB(∆n X). If each composition of multiplication and derivation of S is trivial mod [S ], then, for
s ∈ S and q ∈ B⋆ (∆n X), q| s is trivial mod [S ]:
X
q| s =
ci qi | si ,
i

where, for each i, 0 , ci ∈ k, si ∈ S , qi | si is normal and qi | si ≤ q| s .
Proof. We have the following two cases to consider.
Case I. q ∈ B⋆II (∆n X). In this case, we prove the result by induction on dep⋆ (q). If dep⋆ (q) = 0,
then q = u ⋆ v, where u ∈ C(∆n X) and v ∈ B(∆n X). If s ∈ S is such that s ∈ C(∆n X) or
v ∈ C(∆n X), then it is obvious that q| s is normal by Definition 3.7 (c). Suppose s, v < C(∆n X).
Then s, v ∈ C(∆n X)P(B(∆n X)). Since the composition of multiplication of S is trivial mod [S ],
we have
X
sv =
di pi |ti ,
i

where 0 , di ∈ k, ti ∈ S , pi |ti is normal and pi |ti ≤ sv. Let qi := upi ∈ B⋆ (∆n X). Since
u ∈ C(∆n X), we have qi |ti = upi |ti is normal. Moreover,
X
X
q| s = usv =
di upi |ti =
di qi |ti ,
i

i

where qi |ti = upi |ti ≤ usv = usv = q| s . Hence q| s is trivial mod [S ].
Suppose the claim has been proved for q ∈ C(∆n X) with dep⋆ (q) = k ≥ 0 and consider q with
dep⋆ (q) = k + 1. Then q = uP(p), where uP∈ C(∆n X) and p ∈ B⋆II (∆n X) with dep⋆ (p) = k.
By the induction hypothesis we have p| s = i ci pi |ti , where 0 , ci ∈ k, ti ∈ S , pi |ti is normal
P
and pi |ti ≤ p| s . Let qi := uP(pi ) ∈ B⋆ (∆n X). Then q| s = i ci qi |ti , qi |ti = uP(pi |ti ) is normal and
qi |ti = uP(pi |ti ) ≤ uP(p| s ) = uP(p| s ) = q| s , as desired. This completes the induction.
Case II. q ∈ B⋆I (∆n X). Then q = p|dℓ (⋆) for some p ∈ B⋆ (∆n X) and ℓ≥ 1. Choose such an ℓ to be
maximal so that p is in B⋆II (∆n X). By our hypothesis, the composition of derivation is trivial mod
P
[S ]. So d ℓ (s) = ci pi | si , where 0 , ci ∈ k, si ∈ S , pi | si is normal and pi | si ≤ d ℓ (s). Since p is in
B⋆II (∆n X), by Cases I that has been proved above, the result holds.

Lemma 4.6. Let ≥ be the weakly monomial order on B(∆n X) defined in Eq. (26) and let S ⊆
kB(∆n X). If S is a Gröbner-Shirshov basis, then for each pair s1 , s2 ∈ S for which there exist
q1 , q2 ∈ B⋆ (∆n X) and w ∈ B(∆n X) such that w = q1 | s1 = q2 | s2 with q1 | s1 and q2 | s2 normal, we have
q1 | s1 ≡ q2 | s2 mod (S , w).
Proof. Let s1 , s2 ∈ S , q1 , q2 ∈ B⋆ (∆n X) and w ∈ B(∆n X) be such that w = q1 | s1 = q2 | s2 . According
to the relative location of s1 and s2 in w, we have the following three cases to consider.
Case I. s1 and s2 are separated in w. This case is covered by Lemma 4.4.
Case II. s1 and s2 are overlapping in w. Then there are u ∈ B(∆n X) and v ∈ C(∆X) such that
w1 := s1 u = vs2 is a subword in w with bre(w1 ) < bre(s1 )+bre(s2 ). Since S is a Gröbner-Shirshov

FREE COMMUTATIVE INTEGRO-DIFFERENTIAL ALGEBRAS AND GRÖBNER-SHIRSHOV BASES

17

basis, we have
s1 u − vs2 =

X

c j p j |t j ,

j

where p j |t j is normal and p j |t j = p j |t j < s1 u = vs2 = w1 .
Let q ∈ B⋆1 ,⋆2 (∆n X) be obtained from q1 by replacing ⋆ by ⋆1 , and the u on the right of ⋆ by
⋆2 . Let p ∈ B⋆ (∆n X) be obtained from q by replacing ⋆1 ⋆2 by ⋆. Then we have
q⋆2 |u = q1 , q⋆1 |v = q2 and p| s1 u = q| s1 ,u = q1 | s1 = w,
where in the first two equalities, we have identified B⋆2 (∆n X) and B⋆1 (∆n X) with B⋆ (∆X). Thus
we have
X
q1 | s1 − q2 | s2 = (q⋆2 |u )| s1 − (q⋆1 |v )| s2 = p| s1 u−vs2 =
c j p| p j |t j .
j

Since p j |t j < w1 and p|w1 = w ∈ B(∆n X) is normal, we have p| p j |t is either zero or normal by
j
Lemma 3.14. If p| p j |t = 0, there is nothing to prove. If p| p j |t is normal, then by Lemma 3.13, we
j

j

have p| p j |t j = p| p j |t < p|w1 = w. Hence q1 | s1 ≡ q2 | s2 mod (S , w).
j

Case III. One of s1 or s2 is a subword of the other. Without loss of generality, we may suppose
that s1 = q| s2 for some q ∈ B⋆ (∆n X). Since s1 = q| s2 ∈ B(∆n X), it follows that q| s2 is normal
by Definition 3.7 and q| s2 = q| s2 . For the inclusion composition (s1 , s2 )qs1 , since S is a GröbnerP
Shirshov basis, we have (s1 , s2 )qs1 = s1 − q| s2 = j c j p j |t j , where c j ∈ k, p j ∈ B⋆ (∆n X), t j ∈ S and
p j |t j is normal with p j |t j < s1 . Let p ∈ B⋆ (∆n X) be obtained from q1 by replacing ⋆ with q. Then
w = q2 | s2 = q1 | s1 = q1 |q|s2 = p| s2 . Since S is a Gröbner-Shirshov basis, by Cases I and II, we have
X
p| s2 − q2 | s2 =
di ri |vi ,
i

where di ∈ k, ri ∈ B⋆ (∆n X), vi ∈ S and ri |vi is normal with ri |vi = ri |vi < q2 | s2 = w. So
X
q2 | s2 − q1 | s1 = (p| s2 −
di ri |vi ) − q1 | s1
i

= p| s2 − q1 | s1 −

X

di ri |vi

i

= q1 |q|s2 − q1 | s1 −

X

di ri |vi

i

= −q1 | s1 −q|s2 −

X

di ri |vi

i

=−

X
j

c j q1 | p j |t j −

X

di ri |vi .

i

Since p j |t j < s1 and q1 | s1 = w ∈ B(∆n X) is normal by our hypothesis, we have q1 | p j |t = 0 or q1 | p j |t
j
j
is normal by Lemma 3.14. If q1 | p j |t = 0, there is noting to prove. If q1 | p j |t is normal, then by
j

Lemma 3.13, q1 | p j |t j = q1 | p j |t < q1 | s1 = w. Hence q2 | s2 − q1 | s1 ≡ 0 mod (S , w).
j

j



18

XING GAO, LI GUO, AND SHANGHUA ZHENG

Lemma 4.7. Let ≤n be the weakly monomial order on B(∆n X) defined in Eq. (26), S ⊆ kB(∆n X)
and Irr(S) := B(∆n X) \ {q| s | q ∈ B⋆ (∆n X), s ∈ S , q| s is normal }. Then for any f ∈ kB(∆n X), f
has an expression
X
X
f =
ci ui +
d jq j |s j ,
i

j

where 0 , ci , d j ∈ k, ui ∈ Irr(S), ui ≤ f , s j ∈ S , q j | s j is normal and q j | s j ≤ f .
Proof.PSuppose the lemma does not hold and let f be a counterexample with minimal f . Write
f = i ci ui where 0 , ci ∈ k, ui ∈ B(∆n X) and u1 > u2 > · · · . If u1 ∈ Irr(S), then let
f1 := f − c1 u1 . If u1 < Irr(S ), that is, there exists s1 ∈ S such that u1 = q1 | s1 and q1 | s1 is normal,
then let f1 := f − c1 q1 | s1 . In both cases f1 < f . By the minimality of f , we have that f1 has the
desired expression. Then f also has the desired expression. This is a contradiction.

Now we are ready to derive the Composition-Diamond Lemma.
Theorem 4.8. (Composition-Diamond Lemma) Let ≥ be the weakly monomial order on B(∆n X)
defined in Eq. (26), S n a set of monic DRB polynomials in kB(∆n X) and Id(Sn ) the Rota-Baxter
ideal of kB(∆n X) generated by S n . Then the following conditions are equivalent:
(a) S n is a Gröbner-Shirshov basis in kB(∆n X).
(b) If 0 , f ∈ Id(Sn ), then f = q| s for some q ∈ B⋆ (∆n X), s ∈ S n and q| s is normal.
(c) Irr(Sn ) := B(∆n X)\{q| s | q ∈ B⋆ (∆n X), s ∈ S n , q| s is normal} is a k-basis of kB(∆n X)/Id(Sn ).
In other words, kIrr(Sn ) ⊕ Id(Sn ) = kB(∆n X).
Proof. (a) ⇒ (b): Let 0 , f ∈ Id(Sn ). Then by Lemmas 3.3 and 4.5,
(27)

f =

k
X

ci qi | si , where 0 , ci ∈ k, si ∈ S n , qi | si is normal, 1 ≤ i ≤ k.

i=1

Let wi = qi | si , 1 ≤ i ≤ k. We rearrange them in non-increasing order by
w1 = w2 = · · · = wm > wm+1 ≥ · · · ≥ wk .
If for each 0 , f ∈ Id(Sn ), there is a choice of the above sum such that m = 1, then f = q1 | s1 and
we are done. So suppose the implication (a) ⇒ (b) does not hold. Then there is a 0 , f ∈ Id(Sn )
such that for any expression in Eq. (27), we have that m ≥ 2. Fix such an f and choose an
expression in Eq. (27) such that q1 | s1 is minimal and then with m ≥ 2 minimal, that is, with the
fewest qi | si such that qi | si = q1 | s1 . Since m ≥ 2, we have q1 | s1 = w1 = w2 = q2 | s2 .
Since S n is a Gröbner-Shirshov basis in kB(∆n X), by Lemma 4.6, we have
X
q2 | s2 − q1 | s1 =
d j p j |r j ,
j

where d j ∈ k, r j ∈ S n , p j ∈ B⋆ (∆X) and p j |r j are normal with p j |r j < w1 . Hence
f =

k
X
i=1

ci qi | si = (c1 + c2 )q1 | s1 + c3 q3 | s3 + · · · + cm qm | sm +

k
X

i=m+1

ci qi | si +

X

c2 d j p j |r j .

j

By the minimality of m, we must have c1 + c2 = c3 = · · · = cm = 0. Then we obtain an expression
of f in the form of Eq. (27) for which q1 | s1 is even smaller, a contradiction.

FREE COMMUTATIVE INTEGRO-DIFFERENTIAL ALGEBRAS AND GRÖBNER-SHIRSHOV BASES

19

(b) ⇒ (c): Obviously 0 ∈ kIrr(Sn ) + Id(Sn ) ⊆ kB(∆n X). Suppose the inclusion is proper. Then
kB(∆n X)\(kIrr(Sn )+Id(Sn )) contains only nonzero elements. Let f ∈ kB(∆n X)\(kIrr(Sn )+Id(Sn ))
be such that
f = min{g | g ∈ kB(∆n X) \ (kIrr(Sn ) + Id(Sn ))}.
Case I. f ∈ Irr(Sn ). Then f , f since f < Irr(Sn ). By f − f < f and the minimality of f , we
must have f − f ∈ kIrr(Sn ) + Id(Sn ) and so f ∈ kIrr(Sn ) + Id(Sn ), a contradiction.
Case II. f < Irr(Sn ). Then by the definition of Irr(Sn ), we have f = q| s for some q ∈ B⋆ (∆X),
s ∈ S n and q| s is normal. Thus q| s = q| s = f and so f − q| s < f . If f = q| s , then f ∈ Id(Sn ),
a contradiction. If f , q| s , then f − q| s , 0 with f − q| s < f . By the minimality of f , we have
f − q| s ∈ kIrr(Sn ) + Id(Sn ). This implies that f ∈ kIrr(Sn ) + Id(Sn ), again a contradiction.
Hence kIrr(Sn ) + Id(Sn ) = kB(∆n X). Suppose kIrr(Sn ) ∩ Id(Sn ) , 0 and let 0 , f ∈ kIrr(Sn ) ∩
Id(Sn ). Then
f = c1 v1 + c2 v2 + · · · + ck vk ,
where v1 > v2 > · · · > vk ∈ Irr(Sn ). Since f ∈ Id(Sn ), by Item (b), we have v1 = f = q| s for
some q ∈ B⋆ (∆n X), s ∈ S n and q| s is normal. This is a contradiction to the construction of Irr(Sn ).
Therefore kIrr(Sn ) ⊕ Id(Sn ) = kB(∆n X) and Irr(Sn ) is a k-basis of kB(∆X)/Id(Sn ).
(c) ⇒ (a) : Suppose f, g ∈ S n give an intersection or including composition. Let F = f u and
G = vg in the case of intersection composition and let F = f and G = q|g in the case of including
composition. Then we have w := F = G. If ( f, g)w = F − G = 0, then there is nothing to prove.
If ( f, g)w , 0, then we have
X
( f, g)w =
ci qi , 0 , ci ∈ k, q1 > q2 > · · · > qk ∈ B(∆n X).
i

Then qi < F = G = w. Since ( f, g)w ∈ Id(Sn ), by Item(c), we have that the qi are not in Irr(Sn ).
By the definition of Irr(Sn ), there are qi ∈ B⋆ (∆n X), si ∈ S n such that qi = qi | si and qi | si is normal.
Since qi | si = qi | si < w, we have ( f, g)w ≡ 0 mod (S n , w).
For any composition of multiplication f u where
f ∈ S n and u ∈ C(∆n X)B(∆n X), we have f u ∈
P
Id(S n ). By Lemma 4.7, it follows that f u = i ci qi | si where 0 , ci ∈ k, si ∈ S n , qi ∈ B⋆ (∆n X),
qi | si is normal and qi | si ≤ f u. Hence the composition of multiplication is trivial mod [S n ].
For any composition of derivation
d ℓ ( f ) where f ∈ S n and ℓ ∈ Z≥1 , we have d ℓ ( f ) ∈ Id(Sn ). By
P
Lemma 4.7, we have d ℓ ( f ) = i ci qi | si where 0 , ci ∈ k, si ∈ S n , qi ∈ B⋆ (∆n X), qi | si is normal
and qi | si ≤ f P(v). Hence the composition of derivation d ℓ ( f ) is trivial mod [S n ].
Therefore S n is a Gröbner-Shirshov basis.

5. Groöbner-Shirshov bases and free commutative integro-differential algebras
In this section we begin with a finite set X and prove that the relation ideal of the free commutative differential Rota-Baxter algebra on X of order n, where n ≥ 1, that defines the corresponding
commutative integro-differential algebra of order n possesses a Gröbner-Shirshov basis. This is
done in Section 5.1. Then in Section 5.2, we apply the Composition-Diamond Lemma in Theorem 4.8 to construct a canonical basis for the commutative integro-differential algebra of order
n. Taking n to go to the infinity, we obtain a canonical basis of the free commutative integrodifferential algebra on the finite set X. Finally for any well-ordered set X, by showing that the
canonical basis of the free commutative integro-differential algebra on each finite subset of X is

20

XING GAO, LI GUO, AND SHANGHUA ZHENG

compatible with the inclusion of the subset in X, we obtain a canonical basis of the free commutative integro-differential algebra on X.
5.1. Gröbner-Shirshov basis. We begin with a lemma that simplifies the defining ideal of the
integro-differential algebra.
Lemma 5.1. Let X be a finite set and let X(k[∆n X]) be the free commutative differential RotaBaxter algebra on X. The differential Rota-Baxter ideal of X(k[∆n X]) generated by the set
o
n
P(d(u)P(v)) − uP(v) + P(uv) + λP(d(u)v) u, v ∈ X(k[∆n X]).
is generated by
o
n
(28) S n := P(d(u)P(v)) − uP(v) + P(uv) + λP(d(u)v) u, v ∈ X(k[∆n X]), u < P(X(k[∆n X])) .

Proof. If u is in P(X(k[∆n X])), let u = P(û) for some û ∈ X(k[∆n X]). Then P(d(u)P(v))−uP(v)+
P(uv) + λP(d(u)v) vanishes since P is a Rota-Baxter algebra. This proves the lemma.

We show that S n is a Gröbner-Shirshov basis of the ideal Id(S n ) ⊆ X(k[∆n X]).
Lemma 5.2. Let φ(u, v) ∈ S n with u ∈ B(∆n X) \ P(B(∆n X)) and v ∈ B(∆n X). Then φ(u, v) =
1 ⊗ d(u0 ) ⊗ w for some u0 ∈ C(∆n X) and w ∈ B(∆n X).
Proof. Let u = u0 ⊗ û with 1 , u0 ∈ C(∆n X) and û ∈ B(∆n X) (take û = 1 ∈ k when u ∈ C(∆n X)).
Then
φ(u, v) = P(d(u)P(v)) = P(d(u0 ⊗ û)(1 ⊗ v)) = P(d(u0 ) ⊗ (ûXλ v))
(29)
= P(d(u0 ) ⊗ w) = P(d(u0 ) ⊗ w) = 1 ⊗ d(u0 ) ⊗ w,
where w = ûXλ v ∈ B(∆n X).



By the above lemma, we see that φ(u, v) ∈ P(B(∆n X)) and so φ(u, v) < C(∆n X). So from
Definition 4.1, there is no intersection compositions in S n . The following two lemmas show that
other kinds of compositions in S n are trivial.
Lemma 5.3. The compositions of multiplication and derivation are trivial mod [S n ].
Proof. Let
f := φ(u, v) := P(d(u)P(v)) − uP(v) + P(uv) + λP(d(u)v) ∈ S n ,
where u ∈ B(∆n X) \ P(B(∆n X)) and v ∈ B(∆n X). First, we check that the compositions of
derivation are trivial mod (S n ). By Eq. (6) and Eq. (8), we have
d( f ) = d(u)P(v) − d(uP(v)) + uv + λd(u)v = d(u)P(v) − d(u)P(v) − uv − λd(u)v + uv + λd(u)v = 0.
Hence d ℓ ( f ) ≡ 0 mod [S n ] for any ℓ ∈ ≥ 1.
Next, we check that the compositions of multiplication φ(u, v)w0 P(w) with w0 ∈ C(∆n X) and
w ∈ B(∆n X) are trivial. Since w0 ∈ C(∆n X), it is sufficient to show that φ(u, v)P(w) is trivial. Note
that φ(u, v) ∈ P(B(∆n X)) by Lemma 5.2. From Eq. (7) we obtain
φ(u, v)P(w) =P(d(u)P(v))P(w) − (uP(v))P(w) + P(uv)P(w) + λP(d(u)v)P(w)
=P(P(d(u)P(v))w) + P(d(u)P(v)P(w)) + λP(d(u)P(v)w)
− uP(v)P(w) + P(uv)P(w) + λP(d(u)v)P(w)
(30)
=P(P(d(u)P(v))w) + P(d(u)P(P(v)w + vP(w) + λvw)) + λP(d(u)P(v)w)
− uP(v)P(w) + P(uv)P(w) + λP(d(u)v)P(w)

FREE COMMUTATIVE INTEGRO-DIFFERENTIAL ALGEBRAS AND GRÖBNER-SHIRSHOV BASES

21

Since φ(u, v) = P(d(u)P(v)) − uP(v) + P(uv) + λP(d(u)v), we have
(31)

(32)

P(P(d(u)P(v))w) = P(φ(u, v)w) + P(uP(v)w) − P(P(uv)w) − λP(P(d(u)v)w),
P(d(u)P(P(v)w + vP(w) + λvw))
=φ(u, P(v)w + vP(w) + λvw) + uP(P(v)w + vP(w) + λvw)
− P(u(P(v)w + vP(w) + λvw)) − λP(d(u)(P(v)w + vP(w) + λvw))
=φ(u, P(v)w + vP(w) + λvw) + uP(wP(v)) + uP(vP(w)) + λuP(vw) − P(uwP(v))
− P(uvP(w)) − λP(uvw) − λP(d(u)wP(v)) − λP(d(u)vP(w)) − λ2 P(d(u)vw)

and
(33)

− uP(v)P(w) + P(uv)P(w) + λP(d(u)v)P(w)
= − uP(P(v)w) − uP(vP(w)) − λuP(vw) + P(P(uv)w) + P(uvP(w)) + λP(uvw)
+ λP(P(d(u)v)w) + λP(d(u)vP(w)) + λ2 P(d(u)vw).

Substituting Eq. (31), Eq. (32) and Eq. (33) into Eq. (30), we have
φ(u, v)P(w) = P(φ(u, v)w) + φ(u, wP(v)) + φ(u, vP(w)) + λφ(u, vw)
The last three terms are already in S n and hence are of the form q| s with q = ⋆ and s ∈ S n . So we
just need to bound the leading terms. Note that
P(aP(b)), P(bP(a)), P(ab) ≤ P(a)P(b) for a, b ∈ B(∆n X).
So we have
φ(u, wP(v)) = P(d(u)P(wP(v))) ≤ P(d(u)P(v)P(w)) ≤ P(d(u)P(v))P(w) = φ(u, v)P(w).
We similarly show that φ(u, vP(w)), φ(u, vw) ≤ φ(u, v)P(w). So φ(u, wP(v)) + φ(u, vP(w)) +
λφ(u, vw) ≡ 0 mod [S n ]. Hence φ(u, v)P(w) ≡ 0 mod [S n ] if and only if P(φ(u, v)w) ≡ 0 mod
[S n ]. We prove the latter statement by induction on dep(w).
If dep(w) = 1, that is, w ∈ C(∆n X), let q := P(⋆w) ∈ B⋆ (∆n X). Then q|φ(u,v) = P(φ(u, v)w) and
q|φ(u,v) is normal by w ∈ C(∆n X). Since
P(φ(u, v)w) = P(φ(u, v)w) = P(P(d(u)P(v))w) ≤ P(d(u)P(v))P(w) = φ(u, v)P(w) = φ(u, v)P(w),
we have P(φ(u, v)w) ≡ 0 mod [S n ].
Suppose w ∈ C(∆n X)P(B(∆n X)) and let w = w1 P(w̃) with w1 ∈ C(∆n X) and w̃ ∈ B(∆n X).
Since dep(w̃) < dep(w), by the induction hypothesis, we may assume that
X
φ(u, v)P(w̃) =
ci pi | si ,
i

⋆

where 0 , ci ∈ k, pi ∈ B (∆n X), si ∈ S n , pi | si is normal and pi | si ≤ φ(u, v)P(w̃). Let qi := P(w1 pi ).
Since pi | si is normal and w1 ∈ C(∆n X), it follows that qi | si is normal. Furthermore, we have
X
X
P(φ(u, v)w) = P(φ(u, v)w1 P(w̃)) =
ci P(w1 pi | si ) =
ci qi | si
i

i

and
qi | si = P(w1 pi | si ) ≤ P(w1 φ(u, v)P(w̃)) = P(φ(u, v)w) ≤ φ(u, v)P(w).
Therefore P(φ(u, v)w) ≡ 0 mod [S n ]. This completes the induction. Hence φ(u, v)P(w) ≡ 0 mod
[S n ], as needed.


22

XING GAO, LI GUO, AND SHANGHUA ZHENG

Lemma 5.4. The including compositions in S n are trivial.
Proof. We need to show that the ambiguities of all possible including compositions of the polynomials in S n are trivial. The ambiguities of all such compositions are of the form
P(d(u)P(q|P(d(v)P(w)) )) and P(d(q|P(d(u)P(v)) )P(w)).
Let two elements f and g of S n be given. They are of the form
f := φ(u, v),

g := φ(r, s),

u, v ∈ B(∆n X) \ P(B(∆n X)) and r, s ∈ B(∆n X).

Case I. Suppose v = p|g = p|φ(r,s) = p|P(d(r)P(s)) for some p ∈ B⋆ (∆n X) and
w := f = φ(u, v) = P(d(u)P(v)) = P(d(u)P(p|g )) = q|g = q|g ,
with q = P(d(u)P(p)) ∈ B⋆ (∆n X) and q|g being normal. Then
f = φ(u, v) = P(d(u)P(p|P(d(r)P(s)) )) − uP(p|P(d(r)P(s))) + P(up|P(d(r)P(s)) ) + λP(d(u)p|P(d(r)P(s)))
and
q|g = q|φ(r,s) = P(d(u)P(p|P(d(r)P(s)) )) − P(d(u)P(p|rP(s) )) + P(d(u)P(p|P(rs) )) + λP(d(u)P(p|P(d(r)s) )).
So we have
(34)

( f, g)w := f − q|g
= − uP(p|P(d(r)P(s))) + P(up|P(d(r)P(s))) + λP(d(u)p|P(d(r)P(s)))
+ P(d(u)P(p|rP(s) )) − P(d(u)P(p|P(rs) )) − λP(d(u)P(p|P(d(r)s) )).

Since φ(u, v) = P(d(u)P(v)) − uP(v) + P(uv) + λP(d(u)v), we have
−uP(p|P(d(r)P(s)) ) = −uP(p|φ(r,s) ) − uP(p|rP(s) ) + uP(p|P(rs) ) + λuP(p|P(d(r)s) )
P(up|P(d(r)P(s)) ) = +P(up|φ(r,s) ) + P(up|rP(s) ) − P(up|P(rs) ) − λP(up|P(d(r)s) )
(35)

λP(d(u)p|P(d(r)P(s)) ) = +λP(d(u)p|φ(r,s) ) + λP(d(u)p|rP(s) ) − λP(d(u)p|P(rs) ) − λ2 P(d(u)p|P(d(r)s) )
P(d(u)P(p|rP(s) )) = φ(u, p|rP(s) ) + uP(p|rP(s) ) − P(up|rP(s) ) − λP(d(u)p|rP(s) )
−P(d(u)P(p|P(rs) )) = −φ(u, p|P(rs) ) − uP(p|P(rs) ) + P(up|P(rs) ) + λP(d(u)p|P(rs) )
−λP(d(u)P(p|P(d(r)s) )) = −λφ(u, p|P(d(r)s) ) − λuP(p|P(d(r)s) ) + λP(up|P(d(r)s) ) + λ2 P(d(u)p|P(d(r)s) ).

From Eq. (34) and Eq. (35), it follows that
( f, g)w = −uP(p|φ(r,s) ) + P(up|φ(r,s) ) + λP(d(u)p|φ(r,s) ) + φ(u, p|rP(s)) − φ(u, p|P(rs)) − λφ(u, p|P(d(r)s)).
By Lemma 3.3, we have
uP(p|φ(r,s) ), P(up|φ(r,s) ), λP(d(u)p|φ(r,s)) ∈ Id(S n )
and
φ(u, p|rP(s)), φ(u, p|P(rs)), φ(u, p|P(d(r)s)) ∈ S n ⊆ Id(S n ).
Since
uP(p|φ(r,s) ),

P(up|φ(r,s)),

P(d(u)p|φ(r,s) ) < φ(u, p|φ(r,s)) = φ(u, v) = w

φ(u, p|rP(s)),

φ(u, p|P(rs)),

φ(u, p|P(d(r)s)) < φ(u, p|φ(r,s)) = φ(u, v) = w,

and
we have that ( f, g)w ≡ 0 mod (S n , w).
Case II. Suppose u = p|g = p|φ(r,s) = p|P(d(r)P(s)) for some p ∈ B⋆ (∆n X) and
w := f = φ(u, v) = P(d(u)P(v)) = P(d(p|φ(r,s) )P(v)) = q|g = q|g ,

FREE COMMUTATIVE INTEGRO-DIFFERENTIAL ALGEBRAS AND GRÖBNER-SHIRSHOV BASES

23

with q = P(d(p)P(v)) ∈ B⋆ (∆n X) and q|g being normal. Then
f = φ(u, v) = P(d(p|P(d(r)P(s)) )P(v)) − p|P(d(r)P(s)) P(v) + P(p|P(d(r)P(s)) v) + λP(d(p|P(d(r)P(s)))v)
and
q|g = q|φ(r,s) = P(d(p|P(d(r)P(s)))P(v)) − P(d(p|rP(s) )P(v)) + P(d(p|P(rs))P(v)) + λP(d(p|P(d(r)s) )P(v)).
We have
( f, g)w := f − q|g
= − p|P(d(r)P(s)) P(v) + P(p|P(d(r)P(s))v) + λP(d(p|P(d(r)P(s)))v)
+ P(d(p|rP(s) )P(v)) − P(d(p|P(rs))P(v)) − λP(d(p|P(d(r)s) )P(v))
= − p|φ(r,s) P(v) − p|rP(s) P(v) + p|P(rs) P(v) + λp|P(d(r)s) P(v)
+ P(p|φ(r,s) v) + P(p|rP(s) v) − P(p|P(rs) v) − λP(p|P(d(r)s) v)
+ λP(d(p|φ(r,s) )v) + λP(d(p|rP(s))v) − λP(d(p|P(rs))v) − λ2 P(d(p|P(d(r)s) )v)
+ φ(p|rP(s) , v) + p|rP(s) P(v) − P(p|rP(s) v) − λP(d(p|rP(s))v)
− φ(p|P(rs) , v) − p|P(rs) P(v) + P(p|P(rs) v) + λP(d(p|P(rs))v)
− λφ(p|P(d(r)s) , v) − λp|P(d(r)s) P(w) + λP(p|P(d(r)s) v) + λ2 P(d(p|P(d(r)s) )v)
= − p|φ(r,s) P(v) + P(p|φ(r,s) v) + λP(d(p|φ(r,s))v) + φ(p|rP(s) , v) − φ(p|P(rs) , v) − λφ(p|P(d(r)s) , v).
By Lemma 3.3, we have
p|φ(r,s) P(v), P(p|φ(r,s) v), P(d(p|φ(r,s) )v) ∈ Id(S n )
and
φ(p|rP(s), v), φ(p|P(rs), v), φ(p|P(d(r)s), v) ∈ S n ⊆ Id(S n ).
Since
p|φ(r,s) P(v),

P(p|φ(r,s) v),

P(d(p|φ(r,s) )v) < φ(p|φ(r,s), v) = φ(u, v) = w

φ(p|rP(s) , v),

φ(p|P(rs), v),

φ(p|P(d(r)s) , v) < φ(p|φ(r,s) , v) = φ(u, v) = w,

and
it follows that ( f, g)w ≡ 0 mod (S n , w).



By the remark before Lemma 5.3, Lemmas 5.3 and 5.4, it follows immediately that
Theorem 5.5. S n is a Gröbner-Shirshov basis in kB(∆n X). Hence Irr(S n ) in Theorem 4.8 is a
linear basis of X(k[∆n X])/Id(S n ).
5.2. Bases for free commutative integro-differential algebras. We next identify Irr(S n ) and
thus obtaining a canonical basis of X(k[∆n X])/Id(S n ).
Lemma 5.6. Let ≤ be the linear order on C(∆X) defined in Eqs. (25) and (19), and u = u0 u1 · · · uk ∈
C(∆X) with u0 , · · · , uk ∈ ∆X and u0 ≥ · · · ≥ uk . Then dX (u) = u0 u1 · · · uk−1 dX (uk ). If u is in
C(∆n X), then dX (u) = u0 u1 · · · uk−1 dX (uk ) provided uk ∈ ∆n−1 X.
Proof. We prove the first statement by induction on k ≥ 0. If k = 0, then u = u0 ∈ ∆X and there
is nothing to prove.
Assume the result holds for k ≤ m, where m ≥ 0, and consider the case when k = m + 1. Then
u = u0 u1 · · · um+1 with u0 , · · · , um+1 ∈ ∆X and u0 ≥ · · · ≥ um+1 . Let û = u0 u1 · · · um . Then
dX (u) = dX (ûum+1 ) = ûdX (um+1 ) + dX (û)um+1 + λdX (û)d(um+1 ).

24

XING GAO, LI GUO, AND SHANGHUA ZHENG

By the induction hypothesis, we have dX (û) = u0 u1 · · · dX (um ). So dX (û)um+1 = u0 u1 · · · dX (um )um+1
and dX (û)dX (um+1 ) = u0 u1 · · · dX (um )dX (um+1 ). If dX (um ) ≥ um+1 , then since um > dX (um ) and
um+1 > dX (um+1 ), we have
ûdX (um+1 ) = u0 u1 · · · um dX (um+1 ) > u0 u1 · · · dX (um )um+1 > u0 u1 · · · dX (um )dX (um+1 )
and so dX (u) = u0 u1 · · · um dX (um+1 ). If um+1 > dX (um ) and um > um+1 , then since um > dX (um ), we
have
ûdX (um+1 ) = u0 u1 · · · um dX (um+1 ) > u0 u1 · · · um+1 dX (um ), u0 u1 · · · dX (um )dX (um+1 )
and hence dX (u) = u0 u1 · · · um dX (um+1 ). If um+1 > dX (um ) and um = um+1 , then since um > dX (um ),
we have
ûdX (um+1 ) = u0 u1 · · · um dX (um+1 ) = u0 u1 · · · um+1 dX (um ) > u0 u1 · · · dX (um )dX (um+1 )
and so dX (u) = u0 u1 · · · um dX (um+1 ). This completes the induction. The proof of the second
statement then follows since under the condition uk ∈ ∆n−1 X, dX (uk ) does not change in ∆X or in
∆n X.

We now give the key concept to define Irr(S n ).
Definition 5.7. Let u ∈ C(∆X) with standard form in Eq. (20):
u = u0j0 · · · ukjk , where u0 , · · · , uk ∈ ∆X, u0 > · · · > uk and j0 , · · · , jk ∈ Z≥1 .
Call u functional if either u ∈ {1} ∪ X or jk > 1. Denote
A f := {u ∈ C(∆n X) | u is functional },

k{X} f := kA f and A f,0 = k(A f \{1}).

Proposition 5.8. Let X be a finite well-ordered set. Let (A, dX ) := (k{X}, dX ) := (k[∆X], dX ) be
the free commutative differential algebra on X. Then A = A f ⊕ dX (A).
Proof. We prove the result by induction on |X| ≥ 1. The case when |X| = 1 has been proved
in [23]. Suppose the result holds for all X such that |X| < m and consider the case when |X| = m.
Let X = {x1 , x2 , · · · , xm } with x1 > · · · > xm , B = k{x1 , · · · , xm−1 } and C = k{xm }. Also denote
A f := k{X} f , B f := k{x1 , · · · , xm−1 } f , C f := k{xm } f , C f,0 = k{xm } f,0 .
By the induction hypothesis, we have
B = B f ⊕ dX (B) and C = C f ⊕ dX (C).
Then by the definition of A f , we have
(36) A f = (B f ⊗k)⊕(B⊗C f,0 ) = (B f ⊗k)⊕(B f ⊗C f,0 )⊕(dX (B)⊗C f,0 ) = (B f ⊗C f )⊕(dX (B)⊗C f,0 ).
Therefore B f = B f ⊗ 1 ⊆ A f and C f = 1 ⊗ C f ⊆ A f . Thus B = B f ⊕ dX (B) ⊆ A f + dX (A) and
C = C f ⊕ dX (C) ⊆ A f + dX (A). Since A = B ⊗ C is generated as an algebra by B ⊗ 1 and 1 ⊗ C,
we have A ⊆ A f + dX (A) and so A f + dX (A) = A.
We are left to show that A f ∩ dX (A) = 0. Let B := B ∩ C(∆X) (resp. B f := B f ∩ C(∆X), resp.
C := C ∩ C(∆X), resp. C f := C f ∩ C(∆X)) be the basis of monomials of B (resp. B f , resp. C,
resp. C f ). Then a nonzero element w of A = B ⊗ C is a sum
w=

k
X
i=1

ui ⊗

ni
X
j=1

αi j vi j =

X
i, j

αi j ui ⊗ vi j ,

FREE COMMUTATIVE INTEGRO-DIFFERENTIAL ALGEBRAS AND GRÖBNER-SHIRSHOV BASES

25

where u1 > · · · > uk ∈ B, vi1 > · · · > vini ∈ C, 0 , ki j ∈ k, 1 ≤ j ≤ ni . Then we have


X
 X 

(37)
dX (w) = dX  ki j ui ⊗ vi j  =
αi j dX (ui ) ⊗ vi j + ui ⊗ dX (vi j ) + λdX (ui ) ⊗ dX (vi j ) .
i, j

i, j

We distinguish the following three cases.

Case 1. If v11 , 1, then the leading term in the sum in Eq. (37) is u1 ⊗ dX (v11 ). Since C f ∩ dX (C) =
0, we have dX (v11 ) < C f . Then u1 ⊗ dX (v11 ) < B ⊗ C f . Since B ⊗ C f is a basis of B ⊗ C f , we have
P
u1 ⊗ dX (v11 ) < B ⊗ C f . Therefore dX ( i j ki j ui ⊗ vi j ) < B ⊗ C f . By Eq. (36) we have
B ⊗ C f = B f ⊗ C f ⊕ dX (B) ⊗ C f = B f ⊗ C f ⊕ dX (B) ⊗ C f,0 ⊕ dX (B) ⊗ k = A f ⊕ dX (B) ⊗ k.

Therefore dX (w) < A f .
Case 2. If v11 = 1 and either dX (u1 ) > u2 or dX (u1 ) = u2 and v21 = 1, then since dX (1) = 0, by
the definition of the order defined on ∆X, the leading term in the sum in Eq. (37) is dX (u1 )⊗1 where
dX (u1 ) ∈ B denotes the leading term of dX (u1 ). Since B f ∩ dX (B) = 0, we have dX (u1 ) ⊗ 1 < B f .
Then dX (u1 ) ⊗ 1 < B f ⊗ C and hence not in B f ⊗C. Also 1 < C f,0 implies that dX (u1 ) ⊗ 1 < B ⊗ C f,0 .
Here C f,0 = C\{1} is the standard basis of C f,0 . Thus dX (u1 ) ⊗ 1 < (B f ⊗ C) ∪ (B ⊗ C f,0 ). Then we
P
have dX (u1 ) ⊗ 1 < (B f ⊗ C) + (B ⊗ C f,0 ) and hence dX ( i j ki j ui ⊗ v j ) < (B f ⊗ C) + (B ⊗ C f,0 ). Then
dX (w) is not in A f by Eq. (36).
Case 3. If v11 = 1, dX (u1 ) = u2 and v21 , 1 (note that dX (u1 ) < u2 is impossible since u1 > u2 ),
then the leading term of the sum in Eq. (37) is u2 ⊗ v21 . Then the proof is the same as for Case 1.
In summary, we have proved that dX (w) < A f and hence A f ∩ dX (A) = 0.

Lemma 5.9. Let A f = k{X} f , An = k[∆n X], An, f = An ∩ A f and dAn to be the restriction d|An
except d(x(n) ) = 0 for x ∈ X. Then An = An, f ⊕ dAn (An ).
Proof. Since An, f ⊂ A f , dAn (An ) ⊆ dX (A) and A f ∩ dX (A) = 0 by Proposition 5.8, we have
An, f ∩ im(dAn ) = 0. Thus we only need to show An ⊆ An, f + dAn (An ) since An ⊇ An, f + dAn (An ) is
clear. Suppose An * An, f + dAn (An ). There is a monomial u ∈ C(∆n X) in An \(An, f + dAn (An )) that
is minimal under the order ≤n on C(∆n X) defined in Eqs. (19) and (25). Then u < A f . Assume
the minimum variable in u is x and ℓ is the highest differential order of x in u. Then u can be
expressed as u = û(x(ℓ−1) )m x(ℓ) with û ∈ C(∆X) and m ≥ 0. Let v = û(x(ℓ−1) )m+1 ∈ C(∆X). By
P
Lemma 5.6, we have u = dAn (v). So we can write u = dAn (v) − i ci ui with 0 , ci ∈ k and u > ui .
Then dAn (v) ∈ dAn (An ) and ui ∈ An, f + im(dAn ) by the minimality of u in An \(An, f + im(dAn )). Thus
u ∈ An, f + im(dAn ). This is a contradiction.

Lemma 5.10.
(a) Let Ad := {dX (u) | u ∈ C(∆X)} and A f := {u ∈ C(∆X) | u is functional}.
Then C(∆X) is the disjoint union of Ad and A f , that is, C(∆X) = Ad ⊔ A f .
(b) We have C(∆n X) = (Ad ∩ C(∆n X)) ⊔ (A f ∩ C(∆n X)).
Proof. (a) First we show that Ad ∩ A f = ∅. Let dX (u) ∈ Ad with u ∈ C(∆X). Suppose the standard
expression of u is û(x(ℓ) )m for some û ∈ C(∆X). Thus
dX (u) = ûdX ((x(ℓ) )m ) = û(x(ℓ) )m−1 x(ℓ+1) = û(x(ℓ) )m−1 x(ℓ+1)
and so dX (u) < A f . Next we show that C(∆X) = Ad ∪ A f . Let u ∈ C(∆X) \ A f . Suppose the
minimum variable in u is x and ℓ is the largest differential degree of x. Then u can be expressed

26

XING GAO, LI GUO, AND SHANGHUA ZHENG

as u = û(x(ℓ−1) )m x(ℓ) with û ∈ C(∆X) and m ≥ 0. Let v = û(x(ℓ−1) )m+1 ∈ C(∆X). By Lemma 5.6,
we have that u = dX (v) ∈ Ad . Hence C(∆X) = Ad ⊔ A f .
(b) Since C(∆n X) ⊆ C(∆X), the result holds from Item (a).

Theorem 5.11. Let An , An, f be as defined in Lemma 5.9 and let IID,n be the differential RotaBaxter ideal of X(An ) generated by S n in Eq. (28). Then as tensor product of modules



M
⊗k
X(An )/IID,n  An ⊕ 
An ⊗ An, f ⊗ An  .
k≥0

Proof. For any s = φ(u, v) ∈ S n , by Lemma 5.2, we have s = 1 ⊗ d(u1) ⊗ w, where d(u1) ∈
Ad ∩ C(∆n X) and w ∈ B(∆n X). Recall that
B(∆n X) = ⊔m≥1C(∆n X)⊗m = {a1 ⊗ · · · ⊗ am | a1 , · · · , am ∈ C(∆n X), m ≥ 1}.
By Theorems 4.8 and 5.5, and Lemmas 5.9 and 5.10, we have

Irr(Sn ) = B(∆n X) \ q| s | q ∈ B⋆ (∆n X), s ∈ S n , q| s is normal

= B(∆n X) \ {q|1⊗d(u1 )⊗w | q ∈ B⋆ (∆n X), d(u1 ) ∈ Ad ∩ C(∆n X), w ∈ B(∆n X)}

= B(∆n X) \ {a1 ⊗ · · · ⊗ ak ∈ C(∆n X)⊗k | ai ∈ Ad ∩ C(∆n X) for some 1 < i < k, k ≥ 1}
= {a1 ⊗ · · · ⊗ ak | a1 , ak ∈ C(∆n X), ai ∈ A f ∩ C(∆n X) for 1 < i < k, k ≥ 1}
is a k-basis of kB(∆n X)/IID . Since An = kC(∆n X) and An, f = kA f ∩ C(∆n X), the theorem
follows.

Let
o
n
(38) S := P(d(u)P(v)) − uP(v) + P(uv) + λP(d(u)v) u ∈ X(∆n X) \ P(X(∆n X)), v ∈ X(∆X) .

Lemma 5.12. Let IID,n (resp. IID ) be the differential Rota-Baxter ideal of X(∆n X) (resp. X(∆X))
generated by S n (resp. S ). Then as k-modules we have IID,1 ⊆ IID,2 ⊆ · · · , IID = ∪n≥1 IID,n and
IID,n = IID ∩ kX(∆n X).
Proof. Since kX(∆n X) ⊆ kX(∆n+1 X) for any n≥ 1, we have IID,1 ⊆ IID,2 ⊆ · · · and IID = ∪n≥1 IID,n
by Eq. (28). We next show IID,n = IID ∩ X(∆n X). Obviously, IID,n ⊆ IID ∩ X(∆n X). So we only
need to verify IID ∩ X(∆n X) ⊆ IID,n . By Theorem 5.11 we have




M

⊗k
X(∆n X)  An ⊕ 
An ⊗ An, f ⊗ An  ⊕ IID,n .
k≥0

Let



M

⊗k
Jn := An ⊕ 
An ⊗ An, f ⊗ An  .
k≥0

Then X(∆n X) = Jn ⊕ IID,n and J1 ⊆ J2 ⊆ · · · . Let n, k≥ 1. Since Jn+k ∩ IID,n+k = 0 and Jn ⊆ Jn+k ,
we have Jn ∩ IID,n+k = 0. Since IID,n ⊆ IID,n+k , by modular law we have
(39)

IID,n+k ∩ X(∆n X) = IID,n+k ∩ (Jn ⊕ IID,n ) = (IID,n+k ∩ Jn ) ⊕ IID,n = IID,n .

Let u ∈ IID ∩ X(∆n X). By IID = ∪n≥1 IID,n , we have u ∈ IID,N for some N ∈ Z≥1 . If N ≥ n, by
Eq. (39), u ∈ IID,N ∩ X(∆n X) = IID,n . If N < n, then u ∈ IID,N ⊆ IID,n . Hence IID ∩ X(∆n X) ⊆ IID,n
and so IID ∩ X(∆n X) = IID,n .

Now we are ready to prove the main result of this paper.

FREE COMMUTATIVE INTEGRO-DIFFERENTIAL ALGEBRAS AND GRÖBNER-SHIRSHOV BASES

27

Theorem 5.13. (=Theorem 1.1) Let X be a nonempty well-ordered set. Let X(k{X}) = X(∆X)
be the free commutative differential Rota-Baxter algebra on X. Let IID be the ideal of X(k{X})
generated by S defined in Eq. (38). Then the composition


M

 ֒→ X(A) → X(A)/IID
X(A) f := A ⊕ 
A ⊗ A⊗k
⊗
A
f
k≥0

of the inclusion and the quotient map is a linear isomorphism. In other words,
X(A)

= X(A) f ⊕ IID .

Proof. First assume that X is finite. Denote A = k[∆X] and An = k[∆n X], n ≥ 1. By Theorem
5.11 and Lemma 5.12 we have the linear isomorphisms



M
⊗k
An ⊗ An, f ⊗ An   X(∆n X)/IID,n = X(∆n X)/(IID ∩ X(∆n X))  (X(∆n X) + IID )/IID
An ⊕ 
k≥0

that are compatible with the direct system lim An . Since A = lim An as k-module, we have
−→
−→





M


M

 = lim An ⊕ 
  lim ((X(∆n X)+IID )/IID ) = X(A)/IID .
A⊕
A ⊗ A⊗k
An ⊗ A⊗k
f ⊗ A
n, f ⊗ An 
k≥0

−→

−→

k≥0

Now let X be a nonempty well-ordered set. Let Y be a finite subset of X. Denote AX, f =
A f , AY, f = k{Y} f . Then by the definition of A f we have

(40)

AY ∩ AX, f = AY, f and dX (AY ) = dY (AY ).

Let a ∈ AX . Then there is a finite Y ⊆ X such that a ∈ AY . Thus by Proposition 5.8, we have
a ∈ AY, f + dX (AY ) which is contained in AX, f + dX (AX ) by Eq. (40). Thus AX = AX, f + dX (AX ).
On the other hand, let 0 , a ∈ dX (AX ). Then a = dX (b) for b ∈ AX . Then there is a finite
Y ⊆ X such that b ∈ AY and hence a ∈ dY (AY ). Then by Proposition 5.8 and Eq. (40), we have
a < AY, f = AY ∩ AX, f . Hence a < AX, f . This proves AX, f ∩ dX (AX ) = 0. Hence AX = AX, f ⊕ dX (AX ).
Now let u ∈ X(AX ). Then there is a finite subset Y ⊆ X such that a ∈ X(AY ). Then by
the case of finite sets proved above, u ∈ X(AY ) f + IY,ID . By definition, X(AY ) f ⊆ X(A) f and
IY,ID ⊆ IID . Hence u ∈ X(A) f + IID . Further, if 0 , u ∈ IID , then there is a finite Y ⊆ X
such that u ∈ IY,ID . Thus u is not in X(AY ) f since X(AY ) f ∩ IY,ID = 0. By the definition of
X(AX ) f , we have X(AY ) ∩ X(AX ) f = X(AY ) f . Therefore u is not in X(AX ) f . This proves
X(AX ) = X(AX ) f ⊕ IX,ID .

Acknowledgements: Xing Gao thanks support from NSFC grant 11201201. Li Guo acknowledges support from NSF grant DMS 1001855.
References
[1] F. Baader T. and Nipkow, Term Rewriting and All That, Cambridge U. P., Cambridge, 1998. 8, 9, 11
[2] C. Bai, A unified algebraic approach to classical Yang-Baxter equation, J. Phys. A 40 (2007), 1107311082. 2
[3] G. Baxter, An analytic problem whose solution follows from a simple algebraic identity, Pacific J. Math.
10 (1960), 731–742. 2
[4] G. M. Bergman, The diamond lemma for ring theory, Adv. Math. 29 (1978), 178-218. 3
[5] L. A. Bokut, Imbeddings into simple associative algebras, Algebra i Logika 15 (1976), 117-142. 3
[6] L. A. Bokut, Y. Chen, Y. Chen, Composition-Diamond lemma for tensor product of free algebras, J.
Algebra 323 (2010), 2520-2537. 3

28

XING GAO, LI GUO, AND SHANGHUA ZHENG

[7] L. A. Bokut, Y. Chen and X. Deng, Gröbner-Shirshov bases for Rota-Baxter algebras, Siberian Math. J.
51 (2010), 978-988. 3
[8] L. A. Bokut, Y. Chen and Y. Li, Gröbner-Shirshov bases for categories, in “Operads and Universal
Algebra”, World Scientific Press, (2012) 1-23. 3
[9] L. A. Bokut, Y. Chen and J. Qiu, Greobner-Shirshov bases for associative algebras with multiple operators and free Rota-Baxter algebras, J. Pure Appl. Algebra 214 (2010) 89-110. 3, 6
[10] L.A. Bokut, V. Latyshev, I. Shestakov, E. Zelmanov (Eds.), Selected Works of A.I. Shirshov, Birkhäser,
Basel, Boston, Berlin, 2009, vii, 241 pp. transl. M. Bremner, M. Kotchetov. 3
[11] B. Buchberger, An algorithm for finding a basis for the residue class ring of a zero-dimensional polynomial ideal [in German], Ph.D. thesis, University of Innsbruck, Austria, (1965). 3
[12] P. Cartier, On the structure of free Baxter algebras, Adv. Math. 9 (1972), 253-265. 2
[13] P. Cassidy, L.Guo, W. Keigher, W. Sit (Eds.), Differential Algebra and Related Topics (Proceedings for
the International Workshop in Newark, NJ, 2000), World Sci. Publishing, 2002. 1
[14] P. M. Cohn, Algebra, Vol. 3, 2nd ed., J. Wiley & Sons, Chichester, 1991. 8
[15] K. Ebrahimi-Fard and L. Guo, Mixable shuffles, quasi-shuffles and Hopf algebras, J. Algebraic Combinatorics, 24 (2006), 83–101, arXiv:math.RA/0506418. 5
[16] K. Ebrahimi-Fard, L. Guo and D. Kreimer, Spitzer’s identity and the algebraic Birkhoff decomposition
in pQFT, J. Phys. A: Math. Gen. 37 (2004), 11037-11052. 2
[17] L. Guo, Operated semigroups, Motzkin paths and rooted trees, J. Algebraic Combin. 29 (2009), 35-62.
6, 7
[18] L. Guo, WHAT IS a Rota-Baxter algebra, Notice of Amer. Math. Soc. 56 (2009) 1436-1437. 2
[19] L. Guo, Introduction to Rota-Baxter Algebra, Higher Education Press and International Press, 2012. 2,
5, 6, 7
[20] L. Guo and W. Keigher, Baxter algebras and shuffle products, Adv. Math., 150 (2000), 117–149,
arXiv:math/0407155. 2, 5, 6
[21] L. Guo and W. Keigher, On free Baxter algebras: completions and the internal construction, Adv. Math.
151 (2000), 101–127, arXiv:math/0407156. 5, 6
[22] L. Guo and W. Keigher, On differential Rota-Baxter algebras, J. Pure Appl. Algebra, 212 (2008), 522540. 2, 3, 5, 6
[23] L. Guo, G. Regensburger and M. Rosenkranz, On integro-differential algebras, arXiv:1212.0266. 2, 3, 4,
24
[24] L. Guo, W. Sit and R. Zhang, Differemtail type operators and Gröbner-Shirshov bases, J. Symolic Comput. (2012). 6
[25] L. Guo and B. Zhang, Renormalization of multiple zeta values, J. Algebra, 319 (2008), 3770–3809. 2, 5
[26] H. Hironaka, Resolution of singulatities of an algebraic variety over a field if characteristic zero, I, Ann.
Math. 79 (1964), 109-203. 3
[27] M. Hoffman, Quasi-shuffle products, J. Algebraic Combin., 11 (2000), 49–68. 2, 5
[28] E. R. Kolchin, Differential Algebras and Algebraic Groups, Academic Press, New York, 1973. 1
[29] J. Qiu, Gröbner-Shirshov bases for commutative algebras with multiple operators and free commutative
Rota-Baxter algebras, Asian-European Jour. Math., to appear. 6
[30] J.F. Ritt, Differential Equations from the Algebraic Standpoint, Amer. Math. Sco. Colloq. Pub. 14, Amer.
Math. Soc., New York (1934). 1
[31] J.F. Ritt, Differential Algebra, Amer. Math. Sco. Colloq. Pub. 33, Amer. Math. Soc., New York (1950). 1
[32] M. Rosenkranz and G. Regensburger, Solving and factoring boundary problems for linear ordinary differential equations in differential algebra, J. Symbolic Comput. 43 (2008), 515–544. 2
[33] G.-C. Rota, Baxter algebras and combinatorial identities I, II, Bull. Amer. Math. Soc. 75 (1969), 325–
329, 330–334. 2
[34] G.-C. Rota, Baxter operators, an introduction, In: “Gian-Carlo Rota on Combinatorics, Introductory
papers and commentaries”, Joseph P. S. Kung, Editor, Birkhäuser, Boston, 1995. 2
[35] M. A. Semenov-Tian-Shansky, What is a classical r-matrix?, Funct. Ana. Appl., 17 (1983) 259-272. 2
[36] A. I. Shirshov, Some algorithmic problem for Å-algebras, Sibirsk. Mat. Z., 3(1962), 132-137. 3
[37] M. Singer and M. van der Put, Galois Theory of Linear Differential Equations, Springer, 2003. 1

FREE COMMUTATIVE INTEGRO-DIFFERENTIAL ALGEBRAS AND GRÖBNER-SHIRSHOV BASES

Department of Mathematics, Lanzhou University, Lanzhou, Gansu 730000, China
E-mail address: gaoxing@lzu.edu.cn
Department of Mathematics and Computer Science, Rutgers University, Newark, NJ 07102, USA
E-mail address: liguo@rutgers.edu
Department of Mathematics, Lanzhou University, Lanzhou, Gansu 730000, China
E-mail address: zheng2712801@163.com

29

