Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 2. (2008). pp. 1 – 41
c© Journal “Algebra and Discrete Mathematics”
Planar trees, free nonassociative algebras,
invariants, and elliptic integrals
Vesselin Drensky and Ralf Holtkamp
Communicated by V. A. Artamonov
Abstract. We consider absolutely free algebras with (maybe
infinitely) many multilinear operations. Such multioperator alge-
bras were introduced by Kurosh in 1960. Multioperator algebras
satisfy the Nielsen-Schreier property and subalgebras of free alge-
bras are also free. Free multioperator algebras are described in
terms of labeled reduced planar rooted trees. This allows to ap-
ply combinatorial techniques to study their Hilbert series and the
asymptotics of their coefficients. Then, over a field of characteristic
0, we investigate the subalgebras of invariants under the action of
a linear group, their sets of free generators and their Hilbert series.
It has turned out that, except in the trivial cases, the algebra of
invariants is never finitely generated. In important partial cases
the Hilbert series of the algebras of invariants and the generating
functions of their sets of free generators are expressed in terms of
elliptic integrals.
Introduction
Let K be an arbitrary field of any characteristic. Although probably most
of the K-algebras considered in the literature are K-algebras equipped
with just one binary operation, some classical objects are equipped with
more than one binary operations, or even some non-binary operations.
For example, quite often Jordan algebras are considered with the usual
The work of the first author was partially supported by Grant MI-1503/2005 of
the Bulgarian National Science Fund.
2000 Mathematics Subject Classification: 17A50, 17A36, 17A42, 15A72,
33E05.
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.2 Trees, algebras, invariants, and elliptic integrals
multiplication u ◦ v and one more ternary operation, the triple prod-
uct {uvw}. Poisson algebras have two binary operations – the Poisson
bracket and the commutative and associative multiplication. Apart from
the classical examples, there are of course also more recently introduced
very important algebra types that extend this list, such as dendriform
dialgebras and trialgebras. Then there are algebras with infinitely many
operations, such as homotopy algebras. The study of primitive elements
in free objects leads quite naturally to algebras with infinitely many op-
erations, cf. [Lo, HLR].
In contrast to the case of the free associative algebra, where the prim-
itive elements form the free Lie algebra, Akivis algebras (with up to
ternary operations) were introduced in 1976 and later used to model the
primitives of non-associative algebras. Then Shestakov and Umirbaev
[SU] showed that there exist primitive elements in the universal envelop-
ing algebras of free Akivis algebras which are not Akivis elements and
gave a description of the primitive elements. They arrived at algebras
with infinitely many operations, which they called hyperalgebras.
In 1960 Kurosh [K2] introduced multioperator algebras (or Ω-algebras)
as a generalization of multioperator groups introduced by Higgins [12] in
1956. In [K2] Kurosh established that free Ω-algebras enjoy many of the
combinatorial properties of free nonassociative algebras (with one binary
operation) and suggested their simultaneous study.
Recall that a variety of universal algebras M and its free algebras
satisfy the Schreier property if any subalgebra of a free algebra of M
is free in M again. For example, free groups are Schreier. A result of
Kurosh [K1] from 1947 states that absolutely free binary algebras are
also Schreier. In [K2] Kurosh proved that free multioperator algebras are
Schreier again. The variety M satisfies the Nielsen property if for any
system of generators of a free subalgebra S of a free algebra of M there
exists an effective procedure (a sequence of elementary transformations
similar to the Nielsen transformations in free groups) for obtaining a free
set of generators of S. In many important cases a variety satisfies the
Schreier property if and only if it satisfies the Nielsen property, see Lewin
[L]. We shall say that such varieties and their free algebras satisfy the
Nielsen-Schreier property. See for example the book by Mikhalev, Sh-
pilrain and Yu [MSY] for different aspects of Nielsen-Schreier varieties.
Schreier varieties of multioperator algebras have been considered by Bur-
gin and Artamonov in [BA]. In particular, they showed that the Nielsen
and Schreier properties are equivalent for varieties of multioperator al-
gebras defined by homogeneous polynomial identities. A survey on the
results before 1969 is given by Kurosh in [K3]. This article is also intro-
ductory for several other papers published in the same issue of Uspehi
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 3
Mat. Nauk (Russ. Math. Surv.) and devoted to different aspects of free
and close to free Ω-algebras.
All above mentioned algebras are algebras defined over operads. In
this paper, we consider Ω-algebras in the sense of Kurosh. Here Ω simply
is a set of multilinear operations, which can be quite arbitrary. The
only restriction is that we assume that Ω = Ω2 ∪ Ω3 ∪ · · · is a union
of finite sets of n-ary operations Ωn, n ≥ 2, otherweise our quantitative
results have no sense. Then we consider the absolutely free nonunitary
Ω-algebra K{X}Ω freely generated by a set X. The “Ω-monomials” form
the free Ω-magma {X}Ω = MagΩ(X) which is a basis of the vector space
K{X}Ω and can be described in terms of labeled reduced planar rooted
trees. In particular, if Ω = Ω2 consists of a single binary operation,
then K{X}Ω = K{X} is the free nonassociative algebra and {X} =
MagΩ(X) = Mag(X) is the usual free magma (the set of monomials
in noncommuting nonassociative variables). If X = {x} consists of one
element, then Mag(X) is canonically identified with the set of planar
rooted binary trees. Another special case is when Ωn consists of one
operation for each n ≥ 2. Then we obtain the algebra K{X}ω and for
X = {x} we may identify {X}ω = Magω(X) with the set of all reduced
planar rooted trees.
Labeled reduced planar rooted trees have interesting combinatorics.
This allows to apply classical enumeration techniques from graph theory
and to study the Hilbert series of K{X}Ω and the asymptotics of their
coefficients.
Since free Ω-algebras have bases which are easily constructed in algo-
rithmic terms, it is natural to develop a theory of Gro¨bner (or Gro¨bner-
Shirshov) bases. It was surprising for us that the theory of Gro¨bner bases
of free Ω-algebras is much simpler than the theory of Gro¨bner bases of
free associative algebras. For example, if an ideal of K{X}Ω is finitely
generated then its Gro¨bner basis is finite. If J is a homogeneous ideal of
K{X}Ω, we express the Hilbert series of the factor algebra K{X}Ω/J in
terms of the generating functions of Ω, X and the Gro¨bner basis of J .
Further, we assume that the base field K is of characteristic 0 and
study subalgebras of the invariants K{X}GΩ under the action of a linear
group G on the free Ω-algebra K{X}Ω for a finite set of free generators
X, in the spirit of classical algebraic invariant theory and its general-
ization to free and relatively free associative algebras, see the surveys
[Dr2, F1, KS]. We show that the algebra of invariants K{X}GΩ is never
finitely generated, except in the obvious cases, when all invariants (if any)
are expressed by G-invariant free generators. The proof uses ideas of a
similar result for relatively free Lie algebras, see Bryant [Br] and Dren-
sky [Dr1]. Results of Formanek [F1] and Almkvist, Dicks and Formanek
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.4 Trees, algebras, invariants, and elliptic integrals
[ADF], allow to express the Hilbert series of the algebra K{X}GΩ and the
generating function of the set of its free generators in terms of the Hilbert
series of K{X}Ω, which is an analogue of the Molien and Molien-Weyl
formulas in commutative invariant theory. In the important partial cases
of a unipotent action of the infinite cyclic group G and an action of the
special linear group SL2(K) we give explicit expressions for the Hilbert
series of the algebras of invariants and the generating functions of their
sets of free generators. Applying these formulas to the free binary alge-
bra K{X} we express the results in terms of elliptic integrals. We give
similar formulas when Ω has exactly one n-ary operation for each n ≥ 2.
1. Preliminaries
We fix a field K of any characteristic and a set of variables X. In
most of the considerations we assume that the set X is finite and X =
{x1, . . . , xd}. One of the main objects in our paper is the absolutely
free nonassociative and noncommutative K-algebra K{X} freely gener-
ated by the set X. As a vector space it has a basis consisting of all
non-associative words in the alphabet X. For example, we make a differ-
ence between (x1x2)x3 and x1(x2x3) and even between (xx)x and x(xx).
Words of length n correspond to planar binary trees with n labeled leaves,
see e.g. [GH, Ha]. We omit the parentheses when the products are left
normed. For example, uvw = (uv)w and xn = (xn−1)x.
More generally, following Kurosh [K2], we consider a set Ω of multi-
linear operations. We assume that Ω contains n-ary operations for n ≥ 2
only and for each n the number of n-ary operations is finite. We fix the
notation
Ωn = {νni | i = 1, . . . , pn}, n = 2, 3, . . . ,
for the set of n-ary operations. The free Ω-magma {X}Ω = MagΩ(X)
consists of all “Ω-monomials” and is obtained by recursion, starting with
{X}Ω := X and then continuing the process by
{X}Ω := {X}Ω ∪ {νni(u1, . . . , un) | νni ∈ Ω, u1, . . . , un ∈ {X}Ω}.
The set {X}Ω is a K-basis of the free Ω-algebra K{X}Ω, and the opera-
tions of K{X}Ω are defined using the multilinearity of the operations in
Ω. We call the elements of K{X}Ω Ω-polynomials.
The free Ω-magma {X}Ω can be described also in terms of labeled
reduced planar rooted trees. Recall that a finite connected graph ∅ 6=
T = (Ve(T ),Ed(T )), with a distinguished vertex ρT , is called a rooted
tree with root ρT , if for every vertex λ ∈ Ve(T ) there is exactly one path
connecting λ and ρT . Thinking of the edges as oriented towards the root,
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 5
at each vertex there are incoming edges and (except for the root) one
outgoing edge. The leaves of T have no incoming edges and the root has
no outgoing edges. The tree is reduced if there are no edges with one
incoming edge. A rooted tree T with a chosen order of incoming edges
at each vertex is called a planar rooted tree. We label the vertices λ of
the reduced planar rooted tree T in the following way. If λ is not a leaf
and has n incoming edges, then we label it with an n-ary operation νni.
We call such trees Ω-trees. If λ is a leaf of the Ω-tree T , we label it with
a variable xj ∈ X. We refer to such trees as Ω-trees with labeled leaves.
There is a one-to-one correspondence between the Ω-monomials and the
Ω-trees with labeled leaves. For example, the monomial
ν31(ν23(x1, x1), x3, ν32(x2, x1, x4))
corresponds to the following tree:
•x1
EE
EE
EE
EE
•x1 •x3 •x2 •x1
yy
yy
yy
yy
•x4
ll
ll
ll
ll
ll
ll
ll
l
•ν23
FF
FF
FF
FF
•ν32
xx
xx
xx
xx
•ν31
Fig. 1
We consider nonunitary alg bras only. If we want to deal with uni-
tary algebras, we need certain coherence conditions, because we have to
express the monomials of the form νni(u1, . . . , 1, . . . , un), uj ∈ {X}Ω, as
linear combinations of elements of {X}Ω, see e.g. [H].
The algebra K{X}Ω has a natural grading, defined by deg(xj) = 1,
xj ∈ X, and then extended on the Ω-monomials inductively by
deg(νni(u1, . . . , un)) =
n∑
j=1
deg(uj), uj ∈ {X}Ω.
Similarly, if |X| = d, then K{X}Ω has a Zd-grading, or a multigrad-
ing, counting the degree degj(u) of any Ω-word u in each free generator
xj ∈ X. For a graded vector subspace V of K{X}Ω we consider the
homogeneous component V (k) of degree k. In the multigraded case the
(multi)homogeneous component of V of degree (k1, . . . , kd) is denoted by
V (k1,...,kd). The formal power series with nonnegative integer coefficients
H(V, t) =
∑
k≥1
dim(V (k))tk,
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.6 Trees, algebras, invariants, and elliptic integrals
H(V, t1, . . . , td) =
∑
kj≥0
dim(V (k1,...,kd))tk11 · · · tkdd ,
are called the Hilbert series of V in the graded and multigraded cases,
respectively. Similarly, if W is a set of (multi)homogeneous elements in
K{X}Ω, the generating function of W is
G(W, t) =
∑
k≥1
#(W (k))tk,
G(W, t1, . . . , td) =
∑
kj≥0
#(W (k1,...,kd))tk11 · · · tkdd ,
where #(W (k)) and #(W (k1,...,kd)) are the numbers of homogeneous ele-
ments of the corresponding degree.
The above (multi)gradings work if the set X of free generators consists
of d elements. We may consider more general situation of Zd-grading,
when the set X is arbitrary (but still countable). We assign to each
xj ∈ X a degree
deg(xj) = (aj1, . . . , ajd), ajk ≥ 0,
and assume that for each (a1, . . . , ad) ∈ Zd there is a finite number of
generators of this degree. Again, the algebra K{X}Ω is Zd-graded and
we may speak about the Hilbert series of its graded vector subspaces and
generating functions of its subsets consisting of homogeneous elements.
2. Hilbert series and their asymptotics
The next result is standard and relates the Hilbert series of K{X}Ω and
the generating functions of its operations and generators. Compare with
the cases K{X} and K{X}ω. (For the relation between the Hilbert
series of K{X} with any Zd-grading and K{x} see e.g. Gerritzen [G]
and Rajaee [R]. For general references on enumeration techniques for
graphs see the book by Harary and Palmer [HP].)
Proposition 2.1. Let
G(Ω, t) =
∑
n≥2
#(Ωn)tn =
∑
n≥2
pntn
be the generating function of the set Ω.
(i) The Hilbert series
H(K{x}Ω, t) =
∑
k≥1
dim(K{x}(k)Ω )tk
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 7
satisfies the functional equation
G(Ω, H(K{x}Ω, t))−H(K{x}Ω, t) + t = 0. (1)
The equation (1) and the condition H(K{x}Ω, 0) = 0 determine the
Hilbert series H(K{x}Ω, t) uniquely.
(ii) If the set X is Zd-graded in an arbitrary way, then the Hilbert
series of K{X}Ω is
H(K{X}Ω, t1, . . . , td) = H(K{x}Ω, G(X, t1, . . . , td)).
Proof. (i) The Hilbert series of K{x}Ω coincides with the generating func-
tion of {x}Ω. The set of all elements νni(u1, . . . , un) 6= x from {x}Ω,
uj ∈ {x}Ω, is in one-to-one correspondence with the set
{(νni, u1, . . . , un) | νnj ∈ Ω, uj ∈ {x}Ω}.
For example, if we apply this correspondence to the Ω-monomial (Ω-tree,
respectively) given by the monomial ν31(ν23(x, x), x, ν32(x, x, x)), then
n = 3, νni = ν31, and u1, u2, u3 are given by the following Ω-trees:
•x
GG
GG
GG
GG
G
•x
zz
zz
zz
zz
•x
GG
GG
GG
GG
G
•x •x
zz
zz
zz
zz
u1 = •ν23 , u2 = •x, u3 = •ν32
Fig. 2
Hence
H(K{x}Ω, t)− t = G({x}Ω, t)− t =
∑
k≥2
#({x}(k)Ω )tk
=
∑
n≥2
#(Ωn)G({x}Ω, t)n = G(Ω, G({x}Ω, t)) = G(Ω, H(K{x}Ω, t)).
The condition H(K{x}Ω, 0) = 0 means that the formal power series
has no constant term, i.e., the algebra K{x}Ω is nonunitary. Since Ω
does not contain unary operations, its generating function does not have
constant and linear terms. This easily implies that the k-th coefficient
dim(K{x}(k)Ω ) of H(K{x}Ω, t) is determined by the first k−1 coefficients
dim(K{x}(k)Ω ), m = 1, . . . , k − 1, and the Hilbert series H(K{x}Ω, t) is
determined in a unique way.
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.8 Trees, algebras, invariants, and elliptic integrals
(ii) Let us fix an Ω-tree T with k leaves, and consider the set of all
possible ways to label the leaves of T with elements of X. Clearly, the
generating function of this set (with respect to the Zd-grading on X) is
G(X, t1, . . . , td)k. Hence
H(K{X}Ω, t1, . . . , td) =
∑
k≥1
#(Ω-trees with k leaves)G(X, t1, . . . , td)k
= H(K{x}Ω, G(X, t1, . . . , td)).
Remark 2.2. If G(Ω, t) is the generating function of the set Ω, and
u(t1, . . . , td), v(t1, . . . , td) ∈ C[[t1, . . . , td]] are formal power series such
that
G(Ω, v(t1, . . . , td))− v(t1, . . . , td) + u(t1, . . . , td) = 0 (2)
and satisfying
u(0, . . . , 0) = v(0, . . . , 0) = 0 (3)
then Proposition 2.1 (i) gives that
v(t1, . . . , td) = H(K{x}Ω, u(t1, . . . , td)).
Hence the functional equation (2) and the condition (3) determine uniquely
the series v(t1, . . . , td) as a function of u(t1, . . . , td).
Example 2.3. (i) If Ω consists of one binary operation only, i.e., K{x}Ω =
K{x}, then G(Ω, t) = t2 and Proposition 2.1 (i) gives
H(K{x}, t)2 −H(K{x}, t) + t = 0.
This equation has two solutions
H(K{x}, t) = 1±
√
1− 4t
2
and the condition H(K{x}, 0) = 0 implies that we have to choose the
negative sign. Hence
H(K{x}, t) = 1−
√
1− 4t
2 (4)
is the well known generating function of the Catalan numbers.
(ii) If Ωn consists of one operation νn := νn1 for each n ≥ 2, i.e.,
K{x}Ω = K{x}ω, then
G(Ω, t) = t2 + t3 + · · · = t
2
1− t .
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 9
Hence H(K{x}ω, t) satisfies the equation
H(K{x}ω, t)2
1−H(K{x}ω, t)
−H(K{x}ω, t) + t = 0,
2H(K{x}ω, t)2 − (1 + t)H(K{x}ω, t) + t = 0
and the solution satisfying the condition H(K{x}ω, 0) = 0 is
H(K{x}ω, t) =
1 + t−
√
1− 6t + t2
4 . (5)
This is the generating function of the super-Catalan numbers (cf. [Sl]
A001003).
(iii) Let Ω = n := {νn} consist of one n-ary operation only, i.e.,
G(Ω, t) = G(n, t) = tn. Then the Hilbert series of K{x}n satisfies the
algebraic equation of degree n
H(K{x}n, t)n −H(K{x}n, t) + t = 0
and is equal to the generating function of the planar rooted n-ary trees.
Remark 2.4. If f(z) is an analytic function in a neighbourhood of 0,
f(0) 6= 0, and
t = zf(z),
then the Lagrange inversion formula gives that
z =
∑
k≥1
aktk, ak =
1
k!
dk−1
dζk−1
( 1
f(ζ)
)k∣∣∣∣∣
ζ=0
.
The same holds if f(z) is a formal power series with complex coefficients
and f(0) 6= 0. Hence we may apply the formula for zf(z) = G(Ω, z) and
express H(K{x}Ω, t) in terms of G(Ω, t).
Example 2.5. To obtain the coefficients of the Hilbert series H(K{x}n, t)
of Example 2.3 (iii) we apply Remark 2.4. (For an approach using Koszul
duals of operads, compare also [BH]). We obtain f(z) = 1− zn−1,
( 1
f(ζ)
)k
= 1(1− ζn−1)k
= 1 +
(k
1
)
ζn−1 +
(k + 1
2
)
ζ2(n−1) +
(k + 2
3
)
ζ3(n−1) + · · · ,
ak =
1
k!
dk−1
dζk−1
1
(1− ζn−1)k
∣∣∣∣
ζ=0
, k ≥ 1.
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.10 Trees, algebras, invariants, and elliptic integrals
Direct calculations show that
ak =
1
m(n− 1) + 1
(mn
m
)
, for k = m(n− 1) + 1,m ≥ 0,
and ak = 0 otherwise. Hence
H(K{x}n, t) =
∑
m≥0
(mn
m
) tm(n−1)+1
m(n− 1) + 1
= t + tn + nt2n−1 + n(3n− 1)2 t
3n−2 + · · · .
For small m this can be seen also directly by counting the planar rooted
n-ary trees with the corresponding number of leaves.
The set of n-ary trees with n leaves consists of exactly one tree, the
so-called n-corolla. The set of n-ary trees with 2n − 1 leaves consists of
n elements. The set of n-ary trees with 3n− 2 leaves consists of
(n
2
)
+n2
elements, typical examples (for n = 3) are depicted in Fig. 3.
•
@@
@@
@@
@ • •
~~
~~
~~
~
•
OO
OO
OO
OO
OO
OO
OO •
@@
@@
@@
@ • • •
~~
~~
~~
~
•
oo
oo
oo
oo
oo
oo
oo
•
@@
@@
@@
@ • •
~~
~~
~~
~
•
@@
@@
@@
@ • •
~~
~~
~~
~
•
@@
@@
@@
@ • •
~~
~~
~~
~
• •
Fig. 3
For n = 2 we obtain the explicit formula for the Catalan numbers
ck =
1
k
(2k − 2
k − 1
)
, k = 1, 2, . . . .
Example 2.6. For Ω = ω, as in Example 2.3 (ii), Remark 2.4 gives
2z2 − (1 + t)z + t = 0, t = z(1− 2z)1− z , f(z) =
1− 2z
1− z .
1
fk(ζ) =
( 1− ζ
1− 2ζ
)k
=
(
1 + ζ1− 2ζ
)k
= 1 +
(k
1
) ζ
1− 2ζ +
(k
2
) ζ2
(1− 2ζ)2 + · · ·
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 11
+
( k
k − 1
) ζk−1
(1− 2ζ)k−1 +
(k
k
) ζk
(1− 2ζ)k
= 1 +
(k
1
)
ζ(1 + 2ζ + 22ζ2 + 23ζ3 + · · · )
+
(k
2
)
ζ2
(
1 +
(2
1
)
2ζ +
(3
1
)
22ζ2 +
(4
1
)
23ζ3 + · · ·
)
+
(k
3
)
ζ3
(
1 +
(3
2
)
2ζ +
(4
2
)
22ζ2 +
(5
2
)
23ζ3 + · · ·
)
+ · · ·
+
( k
k − 1
)
ζk−1
(
1 +
(k − 1
k − 2
)
2ζ +
( k
k − 2
)
22ζ2 +
(k + 1
k − 2
)
23ζ3 + · · ·
)
+
(k
k
)
ζk
(
1 +
( k
k − 11
)
2ζ +
(k + 1
k − 1
)
22ζ2 +
(k + 2
k − 1
)
23ζ3 + · · ·
)
,
ak =
1
k!
dk−1
dζk−1
( 1
f(ζ)
)k∣∣∣∣∣
ζ=0
= 1k
((k
1
)(k − 2
0
)
+
(k
2
)(k − 2
1
)
2
+
(k
3
)(k − 2
2
)
22 + · · ·+
( k
k − 1
)(k − 2
k − 2
)
2k−2
)
= 12k


k−1∑
j=1
(k
j
)(k − 2
j − 1
)
2j

 , k = 1, 2, . . . .
Hence ak is the constant term of the Laurent polynomial
1
kζ
(
1 + 1ζ
)k
(1 + 2ζ)k−2.
One of the important characteristics of a formal power series a(t) =∑
k≥0 aktk is its radius of convergency
r(a(t)) = 1lim supk→∞ k
√ak
.
By analogy with the (multilinear) codimension sequence for associative
PI-algebras, see Giambruno and Zaicev [GZ], we introduce the exponent
of free Ω-algebras.
Definition 2.7. Let |X| = d < ∞ and let
H(K{X}Ω, t) =
∑
k≥1
aktk
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.12 Trees, algebras, invariants, and elliptic integrals
be the Hilbert series of the free Ω-algebra K{X}Ω. We define the expo-
nent of K{X}Ω by
exp(K{X}Ω) = lim sup
k→∞
k
√ak.
It is easy to see that
exp(K{X}Ω) = d · exp(K{x}Ω),
i.e., it is sufficient to know the exponent of one-generated free Ω-algebras.
Example 2.8. Let Ω = n := {νn} consist of one n-ary operation only.
Applying the Stirling formula
k! =
√
2πkk
keϑ(k)
ek , |ϑ(k)| <
1
12k ,
to Example 2.5, we obtain
exp(K{x}n) = limm→∞ m(n−1)+1
√am(n−1)+1
= lim
m→∞
m(n−1)+1
√
1
m(n− 1) + 1
(mn
m
)
= lim
m→∞
m(n−1)+1
√(mn
m
)
= lim
m→∞
m(n−1)+1
√
nnm
(n− 1)(n−1)m =
n
n− 1
n−1√n.
Hence
lim
n→∞
exp(K{x}n) = 1.
Example 2.9. For Ω = ω, as in Example 2.3 (ii), in order to find the
coefficient ak of the Hilbert series of K{x}ω, we may expand the function
(5) as a power series. Let
τ1,2 = 3± 2
√
2
be the zeros of 1− 6t + t2. The function
gi =
√
1− τit, i = 1, 2,
is analytic in the open disc |t| < 1/τi and its radius of convergence is 1/τi.
Since
√
1− 6t + t2 = g1(t)g2(t) and the radius of convergence of the prod-
uct of two analytic functions is not less than the radius of convergence of
each of the factors, we conclude that r(H(K{x}ω, t)) ≥ 1/τ1 = τ2. More
precisely, r(H(K{x}ω, t)) = τ2 because the derivatives of H(K{x}ω, t)
have singularities for t = τ2. Hence
exp(K{x}ω) =
1
r(H(K{x}ω, t))
= τ1 ≈ 5.8284.
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 13
Problem 2.10. How does the exponent of K{x}Ω depend on the ana-
lytic properties of the generating function of Ω? For |Ω| < ∞, express
exp(K{x}Ω) in terms of the coefficients and the zeros of the polynomial
f(z) = (z − G(Ω, z))/z. What happens if the number of operations of
degree n is bounded by the same constant a > 0 for all n (or by ank or
by akn for a fixed positive integer k)?
3. Nielsen-Schreier property and Gro¨bner bases
We assume that the free Ω-magma {X}Ω is equipped with an admissible
ordering ≺. This means that the set ({X}Ω,≺) is well ordered and if
u ≺ v in {X}Ω, then
νni(w1, . . . , wj−1, u, wj+1, . . . , wn) ≺ νni(w1, . . . , wj−1, v, wj+1, . . . , wn)
for any νni ∈ Ω and w1, . . . , wj−1, wj+1, . . . , wn ∈ {X}Ω. If
f =
m∑
i=1
αiui ∈ K{X}Ω, 0 6= αi ∈ K,ui ∈ {X}Ω, u1 ≻ · · · ≻ um,
then f = u1 is the leading term of u.
Example 3.1. If X = {x1, x2, . . .} is countable, we order it by x1 ≺
x2 ≺ · · · . If u, v ∈ {X}Ω and deg(u) < deg(v), we assume that u ≺ v. If
deg(u) = deg(v) > 1,
u = νn1i1(u1, . . . , un1), v = νn2i2(v1, . . . , vn2),
we fix u ≺ v if n1 < n2, or n1 = n2, i1 < i2 or, if n1 = n2, i1 = i2, and
(u1, . . . , un1) ≺ (v1, . . . , vn1) lexicographically (i.e., u1 = v1, . . . , uk−1 =
vk−1, uk ≺ vk for some k).
By a result of Kurosh [K2] every subalgebra of the free Ω-algebra
K{X}Ω is free. His proof provides an algorithm which easily produces a
system of free generators of the subalgebra. We present this algorithm
and some of its consequences for self-containess of our exposition from
the point of view of admissible orders.
Algorithm 3.2. Let S be a subalgebra of K{X}Ω. Assuming that the
base field K is constructive and starting with any system U of generators
of the subalgebra S, we want to find a system of free generators of S.
Given f1, . . . , fm ∈ U which are algebraically dependent (i.e., the
homomorphism K{x1, . . . , xm}Ω → S defined by xj → fj , j = 1, . . . ,m,
has a nontrivial kernel), the procedure suggests in each step an elementary
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.14 Trees, algebras, invariants, and elliptic integrals
transformation which decreases one of the generators with respect to the
admissible ordering.
We may assume here that the leading coefficient of each fj is equal
to 1, i.e., fj = fj + · · · , where · · · denotes a linear combination of lower
Ω-monomials.
In the following we sketch how to find one generator fj such that the
Ω-monomial fj belongs to the subalgebra generated by the other fi, i 6= j.
(Then clearly we can replace in the generating set fj by lower elements.)
Let h(f1, . . . , fm) = 0 for some 0 6= h(x1, . . . , xm) ∈ K{x1, . . . , xm}Ω.
For every Ω-monomial hi(x1, . . . , xm) ∈ {x1, . . . , xm}Ω,
hi(f1, . . . , fm) = hi(f1, . . . , fm)
(because hi(f1, . . . , fm) 6= 0). Hence, there exist two different h1, h2 ∈
{x1, . . . , xm}Ω such that
h1(f1, . . . , fm) = h2(f1, . . . , fm). (6)
If h1 = xj then fj = h2(f1, . . . , fm). Since h2 6= xj , comparing
the degrees of fj and h2(f1, . . . , fm), we conclude that h2(x1, . . . , xm) =
h2(x1, . . . , xj−1, xj+1, . . . , xm) does not depend on xj . The Ω-polynomials
f1, . . . , fj−1, f∗j = fj − h2(f1, . . . , fj−1, fj+1, . . . , fm), fj+1, . . . , fm
generate the same algebra as f1, . . . , fm. If f∗j = 0, then we may remove
fj from the system of generators of S. Otherwise, f∗j ≺ fj and the
new set {f1, . . . , f∗j , . . . , fm} is lower in the lexicographic ordering than
{f1, . . . , fm}.
The case where h2 = xk is simi ar. In the remaining case, where
neither h1(x1, . . . , xm) nor h2(x1, . . . , xm) is equal to a single variable xj ,
may be treated recursively in view of equation (6).
The algorithm immediately gives the following well-known fact, see
[K2, K3, BA].
Corollary 3.3. Every graded subalgebra A of the Zd-graded Ω-algebra
K{X}Ω has a homogeneous system of free generators.
Let X = {x1, . . . , xd}. By analogy with the case of algebras with
one binary operation, we call the automorphism ϕ of the free algebra
K{X}Ω tame if it belongs to the subgroup of Aut(K{X}Ω) generated by
the linear and triangular automorphisms, defined, respectively, by
ϕ(xj) =
d∑
i=1
αijxi, αij ∈ K, j = 1, . . . , d,
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 15
where the matrix (αij) is invertible, and
ϕ(xj) = αjxj + fj(xj+1, . . . , xd), j = 1, . . . , d,
where αj ∈ K∗ = K \ {0} and the Ω-polynomials fj(xj+1, . . . , xd) do
not depend on the variables x1, . . . , xj . The discussion of Algorithm 3.2
shows also that all automorphisms of K{X}Ω are tame, which is a result
of Burgin and Artamonov [BA]. If the base field K is constructive, it
provides an algorithm which decomposes the given automorphism into a
product of linear and triangular automorphisms.
Corollary 3.4 (Burgin and Artamonov [BA]). If |X| < ∞, then every
automorphism of K{X}Ω is tame.
The following gives a relation between the Hilbert series of graded
subalgebras and generating functions of their systems of free generators.
Corollary 3.5. If A is a graded subalgebra of the Zd-graded Ω-algebra
K{X}Ω with Hilbert series H(A, t1, . . . , td), then the generating function
of every homogeneous free generating set Y of A is
G(Y, t1, . . . , td) = H(A, t1, . . . , td)−G(Ω, H(A, t1, . . . , td)). (7)
Proof. It is sufficient to use Corollary 3.3 and to apply (2) in Remark
2.2.
Existence of admissible orderings allows to develop the theory of
Gro¨bner (or Gro¨bner-Shirshov) bases of Ω-ideals J in K{X}Ω. The ob-
vious definition of Ω-subwords of an Ω-word (or an Ω-monomial) u =
νni(u1, . . . , un) ∈ {X}Ω is by induction. The subwords of u are the words
uj and the subwords of the uj . Now we fix an admissible ordering on
{X}Ω. The subset B = B(J) of the ideal J of K{X}Ω is a Gro¨bner basis
of J if, for every nonzero f ∈ J , there is an element g ∈ B such that the
leading term g of g is a subword of the leading term f of f . Most of the
standard properties of Gro¨bner bases for free noncommutative algebras
hold also for free Ω-algebras. In particular, the set of normal words, i.e.,
the Ω-words which do not contain as subwords g, g ∈ B(J), form a basis
of the factor algebra K{X}Ω/J . The set
I = I(J) = {f | 0 6= f ∈ J} ⊆ {X}Ω
is an ideal of {X}Ω generated by the set {g | g ∈ B(J)}. We call I the
initial ideal of J .
There is an algorithm to compute the Gro¨bner basis of an ideal J of
the free associative algebras K〈X〉 which is an analogue of the Buchberger
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.16 Trees, algebras, invariants, and elliptic integrals
algorithm for ideals of polynomial algebras. (Compare with the approach
based on the diamond lemma in the paper by Bergman [Be]. See also the
survey article by Ufnarovski [U].) If the ideal J of K〈X〉 is generated
by a set {fk}, we fix an admissible ordering and start the construction
of the Gro¨bner basis B(J) defining B(J) := {fk}. If the leading terms
of f1, f2 ∈ B(J) are f1, f2, respectively, and u1f1v1 = u2f2v2 for some
monomials uk, vk, k = 1, 2, then, for suitable nonzero α1, α2 ∈ K, the
S-polynomial f12 = α1u1f1v1 − α2u2f2v2, if not 0, is lower than u1f1v1
and u2f2v2 in the admissible ordering of K〈X〉. If f12 6= 0, we have
an “ambiguity” and, in order to solve it, we add f12 to B(J). We have
two kinds of S-polynomials. In the first case, f1 and f2 overlap, i.e.,
u1f1 = f2v2. In the second case f2 is a subword of f1, i.e., f1 = u2f2v2 (or
f1 is a subword of f2). In the case of Ω-algebras there are no overlaps and
it is sufficient to consider S-polynomials obtained when one of the leading
terms is an Ω-subword of the other. Hence the Buchberger algorithm has
the following form. (Of course, we fix an admissible ordering of K{X}Ω
and assume that the base field K is constructive.)
Algorithm 3.6. Let the Ω-ideal J of K{X}Ω be generated by the set
{fk}. We may assume that the coefficients of the leading terms fk are
all equal to 1. We define B(J) := {fk}. Let f2 be an Ω-subword of f1
for some f1, f2 ∈ B(J), e.g. f1 = νni(u1, . . . , un), where u1, . . . , un ∈
{X}Ω and f2 is a subword of some uj . Then we replace in B(J) the
Ω-polynomial f1 by
f˜1 = f1 − νni(u1, . . . , u˜j , . . . , un),
where the Ω-polynomial u˜j is obtained from the Ω-monomial uj by re-
placing f2 by f2. If f˜1 6= 0, we norm it (making the leading coefficient
equal to 1). If f˜1 = 0, we remove it from B(J). We continue the process
as long as possible.
Proposition 3.7. Finitely generated ideals of K{X}Ω have finite Gro¨b-
ner bases with respect to any admissible ordering.
Proof. Let the ideal J be generated by f1, . . . , fm. Following Algorithm
3.6, we start with B(J) := {f1, . . . , fm}. In each step we either remove
one of the elements of B(J) or replace it with a new polynomial, without
adding more elements to B(J). In a finite number of steps the procedure
will stop and we obtain a finite Gro¨bner basis of J .
Remark 3.8. Proposition 3.7 implies the solvability of the word problem
for Ω-algebras. This means that if A is a finitely presented Ω-algebra,
there is an algorithm which decides whether an element f ∈ A is equal
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 17
to 0. In other words, if A ∼= K{x1, . . . , xd}Ω/J for a finitely generated
Ω-ideal J , and the generators f1, . . . , fm of J are explicitly given, then
we can decide whether f ∈ K{x1, . . . , xd}Ω belongs to J . One should
pay attention to the fact that the solvability of decision problems cannot
be transferred to factor algebras. There exist finitely generated ideals J0
of the free associative algebra K〈x1, . . . , xd〉, such that the word problem
has no solution in A ∼= K〈x1, . . . , xd〉/J0. Of course, in this case A ∼=
K{x1, . . . , xd}/J for some ideal J of K{x1, . . . , xd} and J is not finitely
generated.
We conclude this section with an Ω-analogue of a theorem of Rajaee
[R] for K{X}. We assume that K{X}Ω is Zd-graded. Then, as in [R],
the reduced Gro¨bner basis of a (multi)homogeneous Ω-ideal J of K{X}Ω
consists of (multi)homogeneous elements.
Theorem 3.9. Let J be a homogeneous Ω-ideal of K{X}Ω with respect to
any Zd-grading of K{X}Ω. Then the Hilbert series of the factor algebra
A ∼= K{X}Ω/J and the generating functions of the set of generators X
and of the reduced Gro¨bner basis B(J) of J with respect to any admissible
ordering are related by
H(A, t1, . . . , td) = H(K{x}Ω, G(X, t1, . . . , td)−G(B(J), t1, . . . , td)). (8)
Proof. We follow the idea of the proof in [R]. For convenience, we denote
the Hilbert seriesH(P, t1, . . . , td) or the generating functionG(P, t1, . . . , td)
of the graded object P by H(P ) and G(P ), respectively. Clearly, the iso-
morphism A ∼= K{X}Ω/J implies H(A) = H(K{X}Ω) − H(J). Also,
H(K{X}Ω) = G({X}Ω) and H(J) = G(I), where I = I(J) ⊳ {X}Ω is
the initial ideal of J . Finally, G(B(J)) = G(B(I)), where B(I) is the
minimal generating set of the Ω-ideal I. Hence (8) is equivalent to
G({X}Ω)−G(I) = H(K{x}Ω, G(X)−G(B(I))).
The elements of I which do not belong to the minimal set of generators
B(I) are characterized by the property that they are of the form
u = νni(v1, . . . , vj−1, wj , vj+1, . . . , vn), vk ∈ {X}Ω, wj ∈ I.
Hence
I =


⋃
νni∈Ω
n⋃
j=1
νni({X}Ω, . . . , {X}Ω︸ ︷︷ ︸
j−1 times
, I, {X}Ω, . . . , {X}Ω︸ ︷︷ ︸
n−j times
)


⋃
B(I),
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.18 Trees, algebras, invariants, and elliptic integrals
G(I) =
∑
νni∈Ω
G


n⋃
j=1
νni({X}Ω, . . . , {X}Ω︸ ︷︷ ︸
j−1 times
, I, {X}Ω, . . . , {X}Ω︸ ︷︷ ︸
n−j times
)

+G(B(I)).
By the principle of inclusion and exclusion,
G


n⋃
j=1
νni({X}Ω, . . . , {X}Ω︸ ︷︷ ︸
j−1 times
, I, {X}Ω, . . . , {X}Ω︸ ︷︷ ︸
n−j times
)


=
n∑
k=1
(−1)k−1
(n
k
)
Gn−k({X}Ω)Gk(I)
= Gn({X}Ω)− (G({X}Ω)−G(I))n.
This implies
G(I) =
∑
νni∈Ω
(Gn({X}Ω)− (G({X}Ω)−G(I))n) + G(B(I))
= G(Ω, G({X}Ω))−G(Ω, G({X}Ω)−G(I)) + G(B(I)).
Applying (1) and Proposition 2.1 (ii) we obtain
G(I) = G({X}Ω)−G(X)−G(Ω, G({X}Ω)−G(I)) + G(B(I)),
G(Ω, G({X}Ω)−G(I))− (G({X}Ω)−G(I)) + (G(X)−G(B(I))) = 0.
By (2) in Remark 2.2 we conclude that
H(A) = G({X}Ω)−G(I) = H(K{x}Ω, G(X)−G(B(I)))
and this completes the proof.
Corollary 3.10. Let J be a homogeneous Ω-ideal of K{X}Ω with respect
to any Zd-grading of K{X}Ω. Let B(J) be the reduced Gro¨bner basis of
J with respect to any admissible ordering. Then
G(B(J), t1, . . . , td) = G(Ω, H(K{X}Ω/J, t1, . . . , td))
−H(K{x}Ω/J, t1, . . . , td) + G(X, t1, . . . , td).
Proof. Applying (2) in Remark 2.2 to (8) we obtain for A ∼= K{X}Ω/J
that
G(Ω, H(A))−H(A) + G(X)−G(B(J)) = 0,
which gives the expression for the generating function of the reduced
Gro¨bner basis B(J) of J .
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 19
Example 3.11. Let Ω = n = {νn} consist of one n-ary operation only,
as in Example 2.3 (iii), and let A be the free commutative and associative
n-ary algebra in one variable, i.e., A is the homomorphic image of K{x}n
modulo the ideal generated by all
νn(u1, . . . , un)− νn(uσ(1), . . . , uσ(n)), σ ∈ Sn,
νn(u1, . . . , νn(uj , v2, . . . , vn), . . . , un)
−νn(νn(u1, v2, . . . , vn), . . . , uj , . . . , un), j = 2, . . . , n,
where Sn is the symmetric group and uj , vk ∈ K{x}n. Hence the homo-
geneous component A(k) is one-dimensional for k = (n− 1)m + 1 and is
equal to zero for all other k. We may assume that A((n−1)m+1) is spanned
by
x(n−1)m+1 = νn(x(n−1)(m−1)+1, x, . . . , x), m ≥ 1.
Since G(Ω, t) = tn and
H(A, t) =
∑
m≥0
t(n−1)m+1 = t1− tn−1 ,
Corollary 3.10 gives that the generating function of the reduced Gro¨bner
basis with respect to any admissible ordering is
G(B(J), t) =
( t
1− tn−1
)n
− t1− tn−1 + t
= tn
∑
m≥1
((m + n− 1
n− 1
)
− 1
)
t(n−1)m.
We fix the admissible ordering on {x}n which compares the monomi-
als first by degree and then by inverse lexicographic ordering: If u =
νn(u1, . . . , un), v = νn(v1, . . . , vn), then u ≺ v if either deg(u) < deg(v)
or deg(u) = deg(v) and uk ≺ vk, uk+1 = vk+1, . . . , un = vn. In this way
x(n−1)m+1 is the smallest monomial of degree (n − 1)m + 1. Then the
reduced Gro¨bner basis of J consists of all
νn(x(n−1)m1+1, . . . , x(n−1)mn+1)− xm(n−1)+1,
m1 + · · · + mn = m, (m1, . . . ,mn) 6= (m, 0, . . . , 0). The number of such
polynomials of degree (n−1)m+1 is equal to the number of all monomials
zm11 · · · zmnn 6= zm1 of total degree m in n variables z1, . . . , zn.
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.20 Trees, algebras, invariants, and elliptic integrals
4. Invariant theory
Till the end of the paper we fix a field K of characteristic 0. We assume
that the set X = {x1, . . . , xd} is finite and consists of d elements. The
general linear group GLd(K) acts canonically on the d-dimensional vector
space KX with basis X and we identify it with the group of invertible
d× d matrices. If
g =


α11 · · · α1d
... . . . ...
αd1 · · · αdd

 ∈ GLd(K), αpq ∈ K,
then the action on KX is defined by
g(xj) = α1jx1 + · · ·+ αdjxd, j = 1, . . . , d.
This action is extended diagonally on K{X}Ω by
g(u(x1, . . . , xd)) = u(g(x1), . . . , g(xd)), u(x1, . . . , xd) ∈ K{X}Ω.
If G is a subgroup of GLd(K), then the algebra of G-invariants is defined
in the obvious way as
K{X}GΩ = {f ∈ K{X}Ω | g(f) = f, g ∈ G}.
One of the main problems in classical invariant theory is the problem
for finite generation of the algebra of invariants which is a partial case
of the 14th Hilbert problem. The same problem has been intensively
studied in noncommutative invariant theory. See the surveys [F1] and
[Dr2] for free and relatively free associative algebras and the papers [Br]
and [Dr1] for free and relatively free Lie algebras. It has turned out that
in the noncommutative case the algebra of invariants is finitely generated
in very special cases only.
For example, if G is a finite linear group acting on the free associa-
tive algebra K〈X〉, a theorem established independently by Dicks and
Formanek [DF] and Kharchenko [Kh2] states that K〈X〉G is finitely gen-
erated if and only if G is cyclic and acts on KX by scalar multiplication.
A simplified version of the proof of Kharchenko is given by Dicks in [C2].
Koryukin [Ko1] considered the case of the action of any linear group G
on K〈X〉. Let d1 be the minimal integer with the property that there
exist linearly independent y1, . . . , yd1 in the vector space KX such that
K〈X〉G ⊂ K〈y1, . . . , yd1〉. Changing linearly the system of free genera-
tors X = {x1, . . . , xd}, we may assume that K〈X〉G ⊂ K〈x1, . . . , xd1〉.
The theorem of Koryukin [Ko1] gives that K〈X〉G is finitely generated if
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 21
and only if G acts on Kx1 ⊕ · · · ⊕Kxd1 as a finite cyclic group of scalar
multiplications.
In the case of the free Lie algebra L(X) Bryant [Br] showed that
L(X)G is not finitely generated if G 6= 〈e〉 is any finite group. The same
result holds from [Dr1].
It is natural to expect that something similar holds for free Ω-algebras.
If J is an Ω-ideal ofK{X}Ω which isGLd(K)-invariant, i.e., GLd(K)(J) =
J , then the action of GLd(K) on K{X}Ω induces an action on the factor
algebra K{X}Ω/J . Hence the G-invariants of K{X}Ω go to G-invariants
of K{X}Ω/J . If the group G is finite or, more generally, acts as a reduc-
tive group on KX, then every invariant of K{X}Ω/J can be lifted to an
invariant of K{X}Ω. Hence, in this case we may study G-invariants of
factor algebras and then lift the obtained results to the algebra K{X}GΩ
itself.
In the case of ordinary polynomial algebras, if the group G is finite,
the algebra of invariants K[X]G is always nontrivial and even of the same
transcendence degree d as K[X]. Lifting the invariants, we obtain that
the algebras K〈X〉G and K{X}G are also nontrivial. In the case of (non-
binary) free Ω-algebras, the picture is completely different:
Example 4.1. Let G = {e,−e}, where e is the identity d×d matrix and
let Ω = 3 = {ν3} consist of a single ternary operation. Since
(−e)(u(x1, . . . , ud)) = (−1)ku(x1, . . . , ud),
k = deg(u), u(x1, . . . , ud) ∈ {X}3,
K{X}G3 is spanned by all homogeneous monomials of even degree. By
Example 2.5 (or by easy induction), K{X}3 is spanned by monomials of
odd degree only. Hence K{X}G3 = {0}.
Let T be an Ω-tree with N leaves. It is a reduced tree such that every
internal vertex (i.e., vertex which is not a leaf) is labeled by an element of
Ωn, where n is the number of incoming edges of the vertex. We denote by
νT the corresponding composition of operations from Ω. If we label the
leaves of T by x1, . . . , xN and denote the corresponding Ω-monomial by
νT (x1, . . . , xN ), then the labeling of the leaves of T by xj1 , . . . , xjN gives
rise to the monomial νT (xj1 , . . . , xjN ). For example, if T is the Ω-tree in
Fig. 4, then
νT (x1, . . . , x6) = ν31(ν23(x1, x2), x3, ν32(x4, x5, x6)),
and νT (x1, x1, x3, x2, x1, x4) corresponds to the Ω-tree with labeled leaves
given in Fig. 1.
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.22 Trees, algebras, invariants, and elliptic integrals
•x1
EE
EE
EE
EE
•x2 •x3 •x4 •x5
yy
yy
yy
yy
•x6
ll
ll
ll
ll
ll
ll
ll
l
•ν23
FF
FF
FF
FF
•ν32
xx
xx
xx
xx
•ν31
Fig. 4
Clearly, the GLd(K)-module νT (KX, . . . ,KX) is isomorphic to the N -th
tensor power (KX)⊗N by the isomorphism which deletes the operations
πT : νT (xj1 , . . . , xjN ) → xj1 ⊗ · · · ⊗ xjN . (9)
As in the classical case, if G is a subgroup of GLd(K), then the algebra
of invariants K{X}GΩ is graded with respect to the usual grading defined
by deg(xj) = 1, j = 1, . . . , d. Even more holds in K{X}Ω. The following
proposition easily implies that we may use results on the G-invariants
K〈X〉G in the free associative algebra K〈X〉 to describe the G-invariants
K{X}GΩ for an arbitrary subgroup G of GLd(K).
Proposition 4.2. (i) Let
f(x1, . . . , xd) =
∑
fT (x1, . . . , xd) ∈ K{X}Ω,
where fT (x1, . . . , xd) ∈ νT (KX, . . . ,KX). Then f(x1, . . . , xd) is G-inva-
riant if and only if πT (fT (x1, . . . , xd)) ∈ K〈X〉G for all Ω-trees T ;
(ii) The Hilbert series of K〈X〉G, K{x}Ω and K{X}GΩ are related as
follows. If
H(K〈X〉G, t) =
∑
m≥1
amtm, H({x}Ω, t) =
∑
m≥1
bmtm,
then
H({X}GΩ , t) =
∑
m≥1
ambmtm.
Proof. Since GLd(K) sends νT (xj1 , . . . , xjN ) to a linear combination of
monomials of the same kind, we obtain immediately that each G-invariant
is a linear combination of G-invariants fT ∈ νT (KX, . . . ,KX), which
establishes (i). The proof of (ii) follows from the equality
K{X}GΩ =
⊕
νT (KX, . . . ,KX)G,
where the direct sum of vector spaces is on all Ω-trees T .
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 23
Let G be an arbitrary subgroup of GLd(K) and let us consider the
action of G on KX. Since every basis of the vector space KX is a system
of free generators of K{X}Ω, we fix a basis of the subspace of G-invariants
(KX)G and assume that {x1, . . . , xd0} ⊂ X is a basis of (KX)G. Then
we complete this system to a basis of the whole KX by xd0+1, . . . , xd.
Obviously, every Ω-polynomial f(x1, . . . , xd0) is a G-invariant. We call
such polynomials obvious invariants.
Example 4.3. Let d = 4, let G be the cyclic subgroup of GL4(K)
generated by the matrix
g =


1 0 1 0
0 1 0 1
0 0 1 0
0 0 0 1

 ,
and let Ω = 3 = {ν3} consist of one ternary operation only. The subspace
of G-invariants of KX is two-dimensional and is spanned by x1, x2. The
polynomial
f(x1, x2, x3, x4) = ν3(x3, x1, x2)− ν3(x1, x1, x4)
is a nonobvious G-invariant because g(f) = f and f depends on variables
different from x1, x2.
The next result shows that the algebra of invariants is not finitely
generated in all nontrivial cases.
Theorem 4.4. Let G be any subgroup of GLd(K) and let K{X}GΩ contain
nonobvious invariants. Then the algebra K{X}GΩ is not finitely generated.
Proof. We choose a homogeneous nonobvious invariant of minimal degree.
We may assume that it is of the form
f =
m∑
j=1
αjwj , αj ∈ K,wj = νT (xj1 , . . . , xjN ) ∈ {X}Ω, (10)
where all wj correspond to the same Ω-tree T and there is no wj which
depends only on the G-invariant variables x1, . . . , xd0 . Let, for some k =
1, . . . , N , and some wj , the k-th coordinate xjk in wj = νT (xj1 , . . . , xjN )
be a noninvariant variable, i.e., jk > d0. We order the operations from
Ω first by degree and then in an arbitrary way. We fix the admissible
ordering on {X}Ω which compares the Ω-monomials w = νni(u1, . . . , un)
first by total degree deg(w), then by the degree degnoninv(w) with re-
spect to the noninvariant variables xd0+1, . . . , xd, then by the first (outer)
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.24 Trees, algebras, invariants, and elliptic integrals
operation νni, and then lexicographically. In the special case of w =
νT (xp1 , . . . , xpN ), where the Ω-tree T is as in (10), we start the lexico-
graphic ordering with the k-th position. Hence,
w′ = νn1i1(u1, . . . , un1) ≺ νn2i2(v1, . . . , vn2) = w′′
means that
1) deg(w′) < deg(w′′);
2) or deg(w′) = deg(w′′), degnoninv(w′) < degnoninv(w′′);
3) or deg(w′) = deg(w′′), degnoninv(w′) = degnoninv(w′′), n1 < n2 or
n1 = n2, i1 < i2;
4) deg(w′) = deg(w′′), degnoninv(w′) = degnoninv(w′′), νn1i1 = νn2i2 and
u1 = v1, . . . , uc−1 = vc−1, uc ≺ vc.
If in 4) both w′ and w′′ are of the same type w′ = νT (xp1 , . . . , xpN )
and w′′ = νT (xq1 , . . . , xqN ) for T from (10), we assume that first uk ≺ vk
and if uk = vk, then u1 = v1, . . . , uc−1 = vc−1, uc ≺ vc. So, without loss
of generality we may assume that k = 1, i.e., the first coordinate xj1 of
some wj is noninvariant.
We construct a sequence f1, f2, . . . of G-invariants, starting with f1 =
f . If in (10) each wj has the form
wj = νT (xj1 , . . . , xjN ) = νn1(ujr1 , . . . , ujrn), ujrs ∈ {X}Ω,
we define
fk+1 =
m∑
j=1
αjνn1(ujr1 , . . . , ujrn−1 , νn1(ujrn , fk, . . . , fk︸ ︷︷ ︸
n−1
)).
In order to prove that fk+1 is G-invariant, we use the GLd(K)-module
isomorphism (9) which is also a G-module isomorphism and define the
G-module isomorphism
ϕk+1 : νT (KX, . . . ,KX︸ ︷︷ ︸
n−1
, νn1(KX, fk, . . . , fk︸ ︷︷ ︸
n−1
)) → (KX)⊗n ⊗ (Kfk)⊗(n−1)
by
ϕk+1 : νT (xj1 , . . . , xjN−1 , νn1(xjN , fk, . . . , fk)) → xj1⊗· · ·⊗xjN ⊗f
⊗(n−1)
k .
Then
ϕk+1(fk+1) =
m∑
j=1
αjπT (f)⊗ f⊗(n−1)k+1 ,
which is G-invariant.
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 25
If the leading term of f with respect to the introduced admissible
ordering is
f = νn1(u01, . . . , u0n−1, u0n), u01, . . . , u0n−1, u0n ∈ {X}Ω,
then the Ω-monomial u01 depends also on a noninvariant variable. Also,
it is easy to see that the leading term of fk+1 is
νn1(u01, . . . , u0n−1, νn1(u0n, fk, . . . , fk︸ ︷︷ ︸
n−1
)).
Now, let the algebra K{X}GΩ of G-invariants be finitely generated by
some h1, . . . , hm. We may assume that the generators are homogeneous.
We choose a sufficiently large k such that deg(fk+1) > deg(hs), s =
1, . . . ,m. Since fk+1 belongs to the Ω-subalgebra of K{X}Ω generated
by h1, . . . , hm, the leading term fk+1 of fk+1 can be expressed as an
Ω-monomial of the leading terms hs and is different from them. Hence
fk+1 = νn1(u01, . . . , u0n−1, νn1(u0n, fk, . . . , fk︸ ︷︷ ︸
n−1
)) = νn1i1(v1, . . . , vn1),
where each vp is the leading term of an element of the Ω-subalgebra gener-
ated by h1, . . . , hm. This implies that νn1 = νn1i1 and u01 = v1, . . . , u0n−1 =
vn−1, νn1(u0n, fk, . . . , fk) = vn. Hence u01 is a leading term of a G-invariant
element. This is impossible because deg(f) > deg(u01) and deg(f) is the
minimal degree of an invariant depending not only on G-invariant vari-
ables.
As an illustration of the proof, continuing Example 4.3, we can now
start with
f1 = f = f(x1, x2, x3, x4) = ν3(x3, x1, x2)− ν3(x1, x1, x4)
and construct
fk+1 = ν3(x3, x1, ν3(x2, fk, fk))− ν3(x1, x1, ν3(x4, fk, fk)).
Remark 4.5. The main steps of the description of Koryukin [Ko1] of the
finitely generated algebras of invariants K〈X〉G can be applied also to the
case of the free binary algebra K{X}. Tracing his proof we obtain that
if K{X}G is finitely generated and K{X}G ⊂ K{x1, . . . , xd1}, where d1
is minimal with this property (with respect to all linear changes of the
system of generators of K{X}), then G acts on Kx1 ⊕ · · · ⊕Kxd1 as a
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.26 Trees, algebras, invariants, and elliptic integrals
finite cyclic group by scalar multiplications. If the order of this cyclic
group is equal to r, then the final arguments of our proof of Theorem 4.4
show that the elements xr−11 (x1xrk1 ), k = 1, 2, . . ., do not belong to any
finitely generated subalgebra of K{X}G.
Corollary 4.6. Let Ω 6= ∅, i.e., K{X}Ω is not the vector space KX with
trivial multiplication and let G 6= 〈e〉 be a finite subgroup of GLd(K).
If the algebra of invariants K{X}GΩ is nonzero, then it is not finitely
generated.
Proof. If K{X}GΩ contains a nonobvious invariant, then we apply directly
Theorem 4.4. Let us assume that all invariants are obvious and depend on
the G-invariant variables x1, . . . , xd0 . Since K{X}GΩ 6= 0 and G 6= 〈e〉, we
derive that 0 < d0 < d. We use the well known fact that the tensor pow-
ers of any faithful representation of a finite group contain all irreducible
representations of the group, including the trivial representation. Ap-
plying the theorem of Maschke, we choose the variables xd0+1, . . . , xd to
span a G-invariant complement of Kx1⊕· · ·⊕Kxd0 . The representation
of G in span{xd0+1, . . . , xd} is faithful. Hence there exists a G-invariant
h ∈ (span{xd0+1, . . . , xd})⊗p of the form
h(xd0+1, . . . , xd) =
m∑
j=1
αjxj1 ⊗ · · · ⊗ xjp , αj ∈ K, j1, . . . , jp > d0.
We choose an Ω-tree T with N leaves, N > p, and consider the associ-
ated operation νT . Now we consider the isomorphism πT from (9). The
variable x1 is G-invariant and the Ω-polynomial
π−1T




m∑
j=1
αjxj1 ⊗ · · · ⊗ xjp

⊗ x⊗(N−p)1


=
m∑
j=1
αjνT (xj1 , . . . , xjp , x1, . . . , x1︸ ︷︷ ︸
N−p
)
is a nonobvious G-invariant. This contradiction completes the proof.
Let us add in Example 4.1 one more variable x0 which is fixed by G.
Then G is generated by the (d + 1)× (d + 1) matrix
g =


1 0 · · · 0
0 −1 · · · 0
... ... . . . ...
0 0 · · · −1

 ,
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 27
and f = ν3(x1, x1, x0) is a nonobvious G-invariant because
g(f) = ν3(g(x1), g(x1), g(x0)) = ν3(−x1,−x1, x0) = ν3(x1, x1, x0) = g.
The proof of Dicks and Formanek [DF] that the finite cyclic groups
G which act by scalar multiplication are the only groups such that the
algebra K〈X〉G is finitely generated uses ideas very different from the
proof of Theorem 4.4 given above. Dicks and Formanek proved that for
any finite group G the Hilbert series of K〈X〉G satisfies
H(K〈X〉G, t) = 1|G|
∑
g∈G
1
1− trKX(g)t
, (11)
where trKX(g) is the trace of the linear operator g in the d-dimensional
vector space KX. This is an analogue of the classical Molien formula
H(K[X]G, t) = 1|G|
∑
g∈G
1
det(1− gt) . (12)
Later, Formanek [F1] generalized this result to the case of any factor
algebra K〈X〉/J of K〈X〉 modulo a GLd(K)-invariant ideal J . The al-
gebra K〈X〉/J inherits the multigrading of K〈X〉. Let G be any finite
subgroup of GLd(K) and let ξ1(g), . . . , ξd(g) be the eigenvalues of the
d× d matrix g ∈ G. Then
H((K〈X〉/J)G, t) = 1|G|
∑
g∈G
H(K〈X〉/J, ξ1(g)t, . . . , ξd(g)t). (13)
Since the Hilbert series of K[X] and K〈X〉 are, respectively,
H(K[X], t1, . . . , td) =
d∏
j=1
1
1− tj
,
H(K〈X〉, t1, . . . , td) =
1
1− (t1 + · · ·+ td)
,
and since
d∏
j=1
(1− ξj(g)t) = det(1− gt),
d∑
j=1
ξj(g)t = tr(gt),
the formula (13) gives immediately (12) and (11). Applied to invariants
of free Ω-algebras, (13) implies the following.
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.28 Trees, algebras, invariants, and elliptic integrals
Proposition 4.7. Let G be a finite subgroup of GLd(K). Then
H(K{X}GΩ , t) =
1
|G|
∑
g∈G
H(K{X}Ω, ξ1(g)t, . . . , ξd(g)t), (14)
where ξ1(g), . . . , ξd(g) are the eigenvalues of the d× d matrix g ∈ G.
Proof. We recall the main steps of the proof of [F1], see also Section 6.3
of [Dr3], where the proof of (13) is given as a sequence of exercises. The
first fact we need is that for a finite dimensional vector space W and a
finite subgroup G of GL(W ), the vector space of G-invariants in W , i.e.,
WG = {w ∈ W | g(w) = w, g ∈ G} coincides with the image of the
Reynolds operator φ : W → W defined by
φ(w) = 1|G|
∑
g∈G
g(w)
and dim(WG) = trW (φ), the trace of φ acting on W . Further, if g is a
diagonalizable matrix acting on KX (which is true when g is of finite or-
der), and W is a GLd(K)-invariant multihomogeneous finite dimensional
vector subspace of K〈X〉, then the Hilbert series H(W, t1, . . . , td) of W
is a symmetric polynomial in t1, . . . , td and the trace of g acting on W is
trW (g) = H(W, ξ1(g), . . . , ξd(g)). (15)
In particular, for the homogeneous components W (k) of degree k
trW (k)(g)tk = H(W (k), ξ1(g)t, . . . , ξd(g)t). (16)
Finally, the equations (15) and (16) imply for the graded subspace of the
G-invariants in W
H(WG, t) =
∑
k≥0
dim((WG)(k))tk =
∑
k≥0
trW (k)(φ)tk
= 1|G|
∑
g∈G
∑
k≥0
trW (k)(g)tk =
1
|G|
∑
g∈G
H(W, ξ1(g)t, . . . , ξd(g)t).
Since each homogeneous component K{X}(k)Ω of K{X}Ω is isomorphic
as a GLd(K)-module to a direct sum of several copies of K〈X〉(k), the
equations (15) and (16) hold also for the finite dimensional GLd(K)-
submodules W of K{X}Ω. This implies the formula (14).
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 29
Example 4.8. Let G = {e,−e} act on the free nonassociative binary
algebra K{x}, where−e changes the sign of x. As in Example 4.1, K{x}G
is spanned by all homogeneous monomials of even degree. Proposition
4.7 gives that
H(K{x}G, t) = 12 (H(K{x}, t) + H(K{x},−t))
(which can be seen also directly). One can replace H(K{x}, t) with its
explicit form (4), as the generating function of the Catalan numbers, and
obtain
H(K{x}G, t) = 14
(
2−
√
1− 4t−
√
1 + 4t
)
.
Using the formula (7) we derive for the generating function of any homo-
geneous set Y of free generators of K{x}G
G(Y, t) = 1−
√
1− 16t2
8 =
1
4H(K{x}, 4t
2). (17)
Instead, we may proceed in the following way, with possible generaliza-
tions. Let H = H(K{x}, t) = H0 + H1, where
H0 =
1
2(H(t) + H(−t)), H1 =
1
2(H(t)−H(−t))
are, respectively, the even and the odd components of the series H. Since
0 = H2 −H + t = (H20 + H21 −H0) + (2H0H1 −H1 + t),
we separate the even and odd parts of this equation and obtain
H20 + H21 −H0 = 2H0H1 −H1 + t = 0, H1 =
t
1− 2H0
,
H20 +
t2
(1− 2H0)2
−H0 = 0, (H20 −H0)(1 + 4(H20 −H0)) + t2 = 0.
Using that H20 −H0 + G(Y, t) = 0, we derive
−G(Y, t)(1− 4G(Y, t)) + t2 = 0, (4G(Y, t))2 − (4G(Y, t)) + 4t2 = 0.
Hence, by (2) we obtain 4G(Y, t) = H(4t2), i.e., (17) and
g2k =
1
4k−1 ck, k ≥ 1, (18)
where g2k are the nonzero coefficients of the generating function G(Y, t).
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.30 Trees, algebras, invariants, and elliptic integrals
Since K{x}G is spanned by all nonassociative monomials of even de-
gree, the monomials of the form uv, where both u, v are of odd degree
form a free generating set of K{x}G. Applying the Stirling formula to
c2k and g2k we obtain
c2k =
1
2k
(4k − 2
2k − 1
)
= (2(2k − 1))!2k((2k − 1)!)2 ≈
42k
8k
√
π(2k − 1)
,
g2k =
4k−1(2(k − 1))!
k((k − 1)!)2 ≈
42k
16k
√
π(k − 1)
,
g2k
c2k
≈ 12
√
2k − 1
k − 1 , limk→∞
g2k
c2k
=
√
2
2 .
Hence the quotient between the number of nonassociative monomials
which are products of two monomials of odd degree to the number of
all monomials of the same degree tends to
√
2/2. For example,
c2 = 1, g2 = 1,
g2
c2
= 1,
c4 = 5, g4 = 4,
g4
c4
= 0.8,
c6 = 42, g6 = 32,
g6
c6
≈ 0.761905,
c8 = 429, g8 = 320,
g8
c8
≈ 0.745921,
c10 = 4862, g10 = 3584,
g10
c10
≈ 0.737145,
c12 = 58786, g12 = 43008,
g12
c12
≈ 0.731603,
c14 = 742900, g14 = 540672,
g14
c14
≈ 0.727786,
c16 = 9694845, g16 = 7028736,
g16
c16
≈ 0.724997,
g20
c20
≈ 0.721197, g30c30
≈ 0.716308, g40c40
≈ 0.713938,
g50
c50
≈ 0.712539, g100c100
≈ 0.709790,
which is very close to √
2
2 ≈ 0.707105.
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 31
The monomials which are products of two monomials of odd degree can
be labeled by planar binary rooted trees with two branches with an odd
number of leaves for each branch. Hence there are much more of such
trees (about √
2/2
1−
√
2/2
≈ 2.41420
times) than of planar binary rooted trees with the same number of leaves
which have two branches with an even number of leaves.
In the case of infinite groups G the Molien formula (12) has no formal
sense. Nevertheless, if G is compact, one can define Haar measure on
G, replace the sum with an integral and obtain the Molien-Weyl formula
for the Hilbert series of the algebra of invariants, see [We1, We2]. The
analogue of (11) for G infinite is given by Almkvist, Dicks and Formanek
[ADF]. For other applications of the Molien-Weyl formula for objects
related with noncommutative algebra see also [F1], [Dr2] and the books
[F2], [DrF]. We shall consider such applications in the next section.
Without presenting a comprehensive survey, we shall mention several
results of action of other objects, different from groups, in the spirit of
invariant theory. Instead of invariants of linear groups one may consider
constants of derivations. A theorem of Jooste [J] and Kharchenko [Kh1]
gives that for a Lie algebra D of linear derivations the algebra of constants
K〈X〉D = {f ∈ K〈X〉 | δ(f) = 0, δ ∈ D}
is free again. See also Koryukin [Ko2] and Ferreira and Murakami [FM1]
for the problem of finite generation of K〈X〉D. One may study also
invariants of Hopf algebras acting on K〈X〉. We shall mention only [FMP]
and [FM2] which show that the algebra of invariants of K〈X〉 under the
linear action of a Hopf algebra H is free and, under some mild restrictions
on H, the algebra K〈X〉H is finitely generated only if the action of H is
scalar. It is a natural problem to study algebras of constants of derivations
and invariants of Hopf algebras also in the case of free Ω-algebras.
5. Weitzenbo¨ck derivations, special linear groups and el-
liptic integrals
As in the previous section, we assume that K is a field of characteristic 0
and X = {x1, . . . , xd}. Almkvist, Dicks and Formanek [ADF] studied in-
variants of the special linear group SLp(K) and the unitriangular group
UTp(K) acting on the free associative algebra K〈X〉. They expressed
the Hilbert series of the algebra of invariants in terms of multiple inte-
grals. We shall transfer these results to the case of K{X}Ω. We shall
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.32 Trees, algebras, invariants, and elliptic integrals
consider in detail the case p = 2 only. Also, instead for the unitriangular
group UT2(K) we shall state the results for Weitzenbo¨ck derivations and
unipotent actions of the infinite cyclic group.
For details on representation theory of general linear groups see e.g.
the books by Macdonald [Mc] and Weyl [We2]. Let W (λ) = W (λ1, λ2)
be the irreducible GL2(K)-module corresponding to the partition λ =
(λ1, λ2). The role of the character of W (λ) is played by the Schur function
sλ(u1, u2). This means that if the matrix g ∈ GL2(K) has eigenvalues
ξ1, ξ2, then g acts as a linear operator on W (λ) with trace trW (λ)(g) =
sλ(ξ1, ξ2). In the case of two variables sλ(u1, u2) has the simple form
sλ(u1, u2) = uλ11 uλ22 + uλ1−11 uλ2+12 + · · ·+ uλ2+11 uλ1−12 + uλ21 uλ12
= (u1u2)λ2
uλ1−λ2+11 − uλ1−λ2+12
u1 − u2
.
The Schur functions form a basis of the vector space of symmetric poly-
nomials in K[u1, u2].
Recall that a linear operator δ of the K-algebra R is called a derivation
if δ(uv) = δ(u)v + uδ(v) for all u, v ∈ R. Similarly, the linear operator δ
is a derivation of the Ω-algebra R if
δ(νni(v1, . . . , vn)) =
n∑
j=1
νni(v1, . . . , δ(vj), . . . , vn) (19)
for all vj ∈ R and all νni ∈ Ω. The derivation is locally nilpotent if for
any v ∈ R there is a k such that δk(v) = 0. If δ is a locally nilpotent
derivation, then the exponential of δ
exp(δ) = 1 + δ1! +
δ2
2! + · · ·
is well defined and is an automorphism of R. The kernel ker(δ) = Rδ
of δ is called the algebra of constants of δ. It coincides with the algebra
Rexp(δ) of the fixed points of the automorphism exp(δ). Every mapping
δ : X → K{X}Ω can be extended to a derivation of K{X}Ω: If v1, . . . , vn
are monomials in {X}Ω, then we define δ(νni(v1, . . . , vn)) inductively by
(19).
Let g ∈ GLd(K) be a unipotent linear operator acting on the vector
space KX = Kx1 ⊕ · · · ⊕Kxd. By the classical theorem of Weitzenbo¨ck
[W], the (commutative and associative) algebra of invariants
K[X]g = {f ∈ K[X] | f(g(x1), . . . , g(xd)) = f(x1, . . . , xd)}
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 33
is finitely generated. All eigenvalues of g are equal to 1 and, up to a change
of the basis, g is determined uniquely by its Jordan normal form. Hence,
for each fixed d we may consider only a finite number of linear unipotent
operators. Equivalently, we may consider the linear locally nilpotent
derivation δ = log g called a Weitzenbo¨ck derivation. Clearly, the algebra
of invariants K[X]g coincides with the algebra of constants K[X]δ (=
ker(δ)). See the book of Nowicki [N] for concrete generators of K[X]δ
for small d and the book by Freudenburg [Fr] for general information
on locally nilpotent derivations of polynomial algebras. The paper by
Drensky and Gupta [DrG] deals with Weitzenbo¨ck derivations for free and
relatively free associative and Lie algebras. We present a short account
on the properties of the algebra of constants K{X}δΩ and show how to
calculate the Hilbert series of K{X}δΩ. The proofs are based on the
description of the invariants of the group of unitriangular matrices given
by De Concini, Eisenbud and Procesi [DEP] and the work of Almkvist,
Dicks and Formanek [ADF]. We assume that δ is a linear locally nilpotent
derivation. It acts on KX as a nilpotent linear operator, with Jordan
normal form consisting of k cells of size n1 + 1, . . . , nk + 1, respectively,
and X is a Jordan basis of δ. Hence either δ(xj) = xj−1 or δ(xj) = 0,
j = 1, . . . , d.
We equip KX with a GL2(K)-module structure in the following way.
If Xr = {xj0 , xj0+1, . . . , xj0+nr} is the part of the basis X correspond-
ing to the r-th Jordan cell of δ, we assume that GL2(K) acts on KXr
as on the GL2(K)-module of commutative and associative polynomials,
homogeneous of degree nr, in two variables x, y: If g ∈ GL2(K) and
g(xnr−mym) =
nr∑
q=0
αqmxnr−qyq
for some αqm ∈ K, then
g(xj0+m) =
nr∑
q=0
αqmxj0+q.
Hence KX is isomorphic to the direct sum W (n1, 0) ⊕ · · · ⊕ W (nk, 0)
as GL2(K)-module. We extend the action of GL2(K) diagonally to
K{X}Ω. Then, see [DEP] and [ADF], each irreducible GL2(K)-sub-
module W (λ1, λ2) of K{X}Ω contains a one-dimensional δ-constant sub-
space and the algebra K{X}δΩ is spanned by these subspaces. We define
on K{X}Ω a Z3-grading assuming that the degree of xj0+m from Xr is
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.34 Trees, algebras, invariants, and elliptic integrals
equal to (nr −m,m, 1) and consider the Hilbert series
Hδ(K{X}Ω, u1, u2, z) = H(K{x}Ω, z
k∑
q=1
s(nr,0)(u1, u2)). (20)
It is obtained from the Hilbert series H(K{X}Ω, t1, . . . , td) by replacing
the variables t1, t2, . . . , td respectively by
un11 z, un1−11 u2z, . . . , u1un1−12 z, un12 z, . . . ,
unk1 z, u
nk−1
1 u2z, . . . , u1u
nk−1
2 z, u
nk
2 z.
The variables u1, u2 take into account the bigrading related to the GL2(K)-
action and the extra variable z counts the usual grading.
The function Hδ(K{X}Ω, u1, u2, z) is symmetric in u1, u2. The coef-
ficient of its linear in z component is equal to
k∑
i=1
s(ni,0)(u1, u2)
which is the character of the GL2(K)-module KX.
Hence Hδ(K{X}Ω, u1, u2, z) is the character of the GL2(K)-module
K{X}Ω. By [ADF], this means that if
Hδ(K{X}Ω, u1, u2, z) =
∑
q≥1


∑
λ⊢q
mλsλ(u1, u2)

 zq,
then the homogeneous component of degree q decomposes as
K{X}(q)Ω =
⊕
λ⊢q
mλW (λ1, λ2). (21)
Theorem 5.1. Let δ be a linear locally nilpotent derivation of K{X}Ω,
X = {x1, . . . , xd}, which, when acting on KX, has a Jordan normal
form consisting of k cells of size n1 + 1, . . . , nk + 1, respectively. Then
the Hilbert series of the algebra of constants K{X}δΩ is given by
H(K{X}δΩ, z) = 2
∫ 1
0
cos2(πu)Hδ(K{X}Ω, e2piiu, e−2piiu, z)du, (22)
where Hδ(K{X}Ω, u1, u2, z) is defined in (20). Equivalently,
H(K{X}δΩ, z) = 2
∫ 1
0
cos2(πu)H
(
K{x}Ω, z
k∑
i=1
sin(2π(ni + 1)u)
sin(2πu)
)
du.
(23)
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 35
Proof. We follow the proof of Almkvist, Dicks, and Formanek [ADF] for
the Hilbert series of K〈X〉δ. If K{X}(q)Ω decomposes as in (21), then the
Hilbert series of the algebra of δ-constants is
H(K{X}δΩ, z) =
∑
q≥1


∑
λ⊢q
mλ

 zq.
Hence, for the proof of (22) it is sufficient to show that
2
∫ 1
0
cos2(πu)sλ(e2piiu, e−2piiu)du = 1,
which was already used in the proof of [ADF] (or may be verified directly).
The expression (23) follows from the formula
s(n,0)(e2piiu, e−2piiu) =
e2pii(n+1)u − e−2pii(n+1)u
e2piiu − e−2piiu =
sin(2π(n + 1)u)
sin(2πu) .
Example 5.2. Let K{X}Ω = K{X} be the free nonassociative algebra,
i.e., Ω consist of one binary operation only.
(i) Let d = 2 and δ(x1) = 0, δ(x2) = x1, i.e.,
δ =
(
0 1
0 0
)
. (24)
By [DrG] the Hilbert series of K〈X〉δ (for the nonunitary algebra K〈X〉)
is
H(K〈X〉δ, t) =
∑
p≥0
(2p + 1
p
)
t2p+1 +
∑
p≥1
(2p
p
)
t2p.
The algebra K〈X〉δ is a free associative algebra and has a homogeneous
set of free generators Y with generating function
G(Y, t) = t +
∑
p≥1
cp+1t2p. (25)
Hence Proposition 4.2 gives
H(K〈X〉δ, t) =
∑
p≥0
(2p + 1
p
)
c2p+1t2p+1 +
∑
p≥1
(2p
p
)
c2pt2p,
where cn are the Catalan numbers.
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.36 Trees, algebras, invariants, and elliptic integrals
Applying Theorem 5.1 we obtain
H(K{x}, t) = 1−
√
1− 4t
2 ,
Hδ(K{X}, u1, u2, z) =
1−
√
1− 4(u1 + u2)z
2 ,
H(K{X}δ, z) =
∫ 1
0
cos2(πu)
(
1−
√
1− 8z cos(2πu)
)
du,
which is an elliptic integral. If Y is a homogeneous set of free generators
of K{X}δ, then its generating function is
G(Y, z) = H(K{X}δ, z)−H(K{X}δ, z)2.
The beginning of the expansion of G(Y, z) as a formal power series is
G(Y, z) = z + z2 + 2z3 + 14z4 + 56z5 + 404z6 + 2020z7 + · · · .
(Compare with the expansion of the generating function (25) of the free
generators of K〈X〉δ.) For the free generators of degree ≤ 3 of K{X}δ
one may choose
x1, x1x2 − x2x1, (x1x1)x2 − (x2x1)x1, x1(x1x2)− x2(x1x1).
(ii) Let d = 3 and
δ =


0 1 0
0 0 1
0 0 0

 . (26)
Then (22) and (23) give
H(K{X}δ, z) =
∫ 1
0
cos2(πu)
(
1−
√
1− 4z(1 + 2 cos(4πu))
)
du.
The beginning of the generating expansion for the free generators is
z + 2z2 + 8z3 + 58z4 + 440z5 + 3728z6 + 33088z7 + · · · .
Example 5.3. Let K{X}Ω = K{X}ω, i.e., Ωn consists of one operation
for each n ≥ 2. Applying Theorem 5.1 to (5) in Example 2.3 (ii) we
obtain for d = 2 and δ from (24)
H(K{X}δω, z) =
1
2
∫ 1
0
cos2(πu)f(2z cos(2πu))du,
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 37
where
f(t) = 1 + t−
√
1− 6t + t2.
For d = 3 and δ from (26), we obtain again elliptic integrals:
H(K{X}δω, z) =
1
2
∫ 1
0
cos2(πu)f(z(1 + 2 cos(4πu)))du,
which is, in low degrees,
z + 3z2 + 21z3 + 209z4 + 2295z5 + 27777z6 + 354879z7 + · · ·
Following Almkvist, Dicks and Formanek [ADF], we consider a poly-
nomial representation of GL2(K) in KX, i.e., we assume that KX has
the GL2(K)-module structure
KX ∼= W (λ(1)1 , λ
(1)
2 )⊕ · · · ⊕W (λ
(k)
1 , λ
(k)
2 ). (27)
This induces also a representation of SL2(K) ⊂ GL2(K). We translate
the results of [ADF] for the Hilbert series of K〈X〉SL2(K) to the case of
K{X}SL2(K)Ω .
Theorem 5.4. Let the GL2(K)-module structure of KX, X = {x1, . . . , xd},
be given by (27). Then the Hilbert series of the algebra of SL2(K)-
invariants in K{X}Ω is
H(K{X}SL2(K)Ω , z) =
= 2
∫ 1
0
sin2(2πu)H
(
K{x}Ω, z
k∑
i=1
s(λ(i)1 ,λ(i)2 )(e
2piiu, e−2piiu)
)
du =
= 2
∫ 1
0
sin2(2πu)H
(
K{x}Ω, z
k∑
i=1
sin(2π(λ(i)1 − λ
(i)
2 + 1)u)
sin(2πu)
)
du.
Proof. As in the proof of Theorem 5.1, it is sufficient to take into account
that W (λ1, λ2) contains a one-dimensional SL2(K)-invariant if λ1 = λ2
and does not contain SL2(K)-invariants otherwise. Then we need to
show that
2
∫ 1
0
sin2(2πu)sλ(e2piiu, e−2piiu)du = δλ1λ2 ,
where δpq is the Kronecker delta. This can be checked directly and was
already used in [ADF].
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.38 Trees, algebras, invariants, and elliptic integrals
Example 5.5. If d = 2 and GL2(K) acts naturally on KX, i.e. KX ∼=
W (1, 0), then the results in [DrG] for the Hilbert series H(K〈X〉SL2(K), t)
of the SL2(K)-invariants of the nonunitary free associative algebra give
H(K〈X〉SL2(K), t) =
∑
p≥1
cp+1t2p =
1− 2t2 −
√
1− 4t2
2t2 .
By Proposition 4.2 (ii) we obtain that
H({X}SL2(K), z) =
∑
p≥1
c2pcp+1z2p.
On the other hand, Theorem 5.4 gives
H(K{X}SL2(K), z) =
∫ 1
0
sin2(2πu)
(
1−
√
1− 8z sin(2πu)
)
du
which is again an elliptic integral.
Remark 5.6. In order to obtain Ω-analogues of the results in [ADF] for
the invariants of SLr(K) and UTd(K) we equip KX with the structure
of a GLr(K)-module with character (the trace of g ∈ GLr(K) acting on
KX)
TKX(u1, . . . , ur) =
k∑
i=1
sλ(i)(u1, . . . , ur).
Then we replace in [ADF] the GLr-character
H(K〈X〉, u1, . . . , ur) =
1
1− zTKX(u1, . . . , ur)
withH(K{x}Ω, z
∑k
i=1 zTKX(u1, . . . , ur)) and obtain integral expressions
for H(K{X}SLr(K)Ω , z) and H(K{X}
UTr(K)
Ω , z).
Acknowledgements
The first author wants to thank for the hospitality at the Department
of Mathematics of the Ruhr University in Bochum during his visit there.
Both authors thank Lothar Gerritzen for stimulating discussions about
the subject. They are especially indebted to the anonymous referee for
the historical comments which led to the improvement of the exposition
and the extension of the list of references.
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 39
References
[ADF] G. Almkvist, W. Dicks, E. Formanek, Hilbert series of fixed free algebras and
noncommutative classical invariant theory, J. Algebra 93 (1985), 189-214.
[Be] G.M. Bergman, The diamond lemma for ring theory, Adv. Math. 29 (1978),
178-218.
[Br] R.M. Bryant, On the fixed points of a finite group acting on a free Lie algebra,
J. London Math. Soc. (2) 43 (1991), 215-224.
[BA] M.S. Burgin, V.A. Artamonov, Certain properties of subalgebras in varieties of
linear Ω-algebras (Russian), Mat. Sbornik 87 (1972), No. 1, 67-82. Translation:
Math. USSR, Sb. 16 (1972), 69-85.
[BH] E. Burgunder, R. Holtkamp, Partial magmatic bialgebras, Preprint 2007.
[C1] P.M. Cohn, Subalgebras of free associative algebras, Proc. Lond. Math. Soc.,
III. Ser. 14 (1964), 618-632.
[C2] P.M. Cohn, Free Rings and Their Relations, Se ond Edition, London Mathe-
matical Society Monographs, 19, Academic Press, London, 1985.
[DEP] C. De Concini, D. Eisenbud, C. Procesi, Young diagrams and determinantal
varieties, Invent. Math. 56 (1980), 129-165.
[DF] W. Dicks, E. Formanek, Poincare´ series and a problem of S. Montgomery, Lin.
Multilin. Algebra 12 (1982), 21-30.
[Dr1] V. Drensky, Fixed algebras of residually nilpotent Lie algebras, Proc. Amer.
Math. Soc. 120 (1994), 1021-1028.
[Dr2] V. Drensky, Commutative and noncommutative invariant theory, Math. and
Education in Math., Proc. of the 24-th Spring Conf. of the Union of Bulgar.
Mathematicians, Svishtov, April 4-7, 1995, Sofia, 1995, 14-50.
[Dr3] V. Drensky, Free Algebras and PI-Algebras, Springer-Verlag, Singapore, 1999.
[DrF] V. Drensky, E. Formanek, Polynomial Identity Rings, Advanced Courses in
Mathematics, CRM Barcelona, Birkha¨user, Basel – Boston, 2004.
[DrG] V. Drensky, C.K. Gupta, Constants of Weitzenbo¨ck derivations and invariants
of unipotent transformations acting on relatively free algebras, J. Algebra 292
(2005), 393-428.
[FM1] V.O. Ferreira, L.S.I. Murakami, Finitely generated constants of free algebras,
Groups, Rings and Group Rings, 149-153, Lect. Notes Pure Appl. Math., 248,
Chapman & Hall/CRC, Boca Raton, FL, 2006.
[FM2] V.O. Ferreira, L.S.I. Murakami, Finitely generated invariants of Hopf algebras
on free associative algebras, Linear Algebra Appl. 420 (2007), 70-78.
[FMP] V.O. Ferreira, L.S.I. Murakami, A. Paques, A Hopf-Galois correspondence for
free algebras, J. Algebra 276 (2004), 407-416.
[F1] E. Formanek, Noncommutative invariant theory, Contemp. Math. 43 (1985),
87-119.
[F2] E. Formanek, The Polynomial Identities and Invariants of n × n Matrices,
CBMS Regional Conf. Series in Math. 78, Published for the Confer. Board of
the Math. Sci. Washington DC, AMS, Providence RI, 1991.
[Fr] G. Freudenburg, Algebraic Theory of Locally Nilpotent Derivations, Ency-
clopaedia of Mathematical Sciences, 136, Invariant Theory and Algebraic
Transformation Groups, VII. Springer-Verlag, Berlin, 2006.
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.40 Trees, algebras, invariants, and elliptic integrals
[G] L. Gerritzen, Hilbert series and non-associative Gro¨bner bases, Manuscr. Math.
103 (2000), 161-167.
[GH] L. Gerritzen, R. Holtkamp, Hopf co-addition for free magma algebras and the
non-associative Hausdorff series, J. Algebra 265 (2003), 264-284.
[GZ] A. Giambruno, M. Zaicev, On codimension growth of finitely generated asso-
ciative algebras, Adv. Math. 140 (1998), 145-155.
[Ha] M. Hall Jr., Combinatorial Theory, Reprint of the Second Edition, Wiley Clas-
sics Library, Chichester, John Wiley & Sons, 1998.
[HP] F. Harary, E.M. Palmer, Graphical Enumeration, Academic Press, New York
– London, 1973.
[Hi] P.J. Higgins, Groups with multiple operators, Proc. London Math. Soc. (3) 6
(1956), 366-416.
[H] R. Holtkamp, On Hopf algebra structures over free operads, Adv. Math. 207
(2006), 544-565.
[HLR] R. Holtkamp, J.-L. Loday, M. Ronco, Coassociative magmatic bialgebras and
the Fine numbers, J. Algebraic Combin. (to appear).
[J] T.W. Jooste, Primitive derivations in free associative algebras, Math. Z. 164
(1978), 15-23.
[Kh1] V.K. Kharchenko, Constants of derivations of primary rings (Russian) Izv.
Akad. Nauk SSSR, Ser. Mat. 45 (1981), 435-462. Translation: Math. USSR,
Izv. 18 (1982), 381-401.
[Kh2] V.K. Kharchenko, Noncommutative invariants of finite groups and Noetherian
varieties, J. Pure Appl. Algebra 31 (1984), 83-90.
[KS] O.G. Kharlampovich, M.V. Sapir, Algorithmic problems in varieties, Intern. J.
Algebra and Computation 5 (1995), 379-602.
[Ko1] A.N. Koryukin, Noncommutative invariants of reductive groups (Russian), Al-
gebra i Logika 23 (1984), 419-429. Translation: Algebra Logic 23 (1984), 290-
296.
[Ko2] A.N. Koryukin, Noncommutative invariants of bialgebras (Russian), Algebra i
Logika 33 (1994), 654-680. Translation: Algebra Logic 33 (1994), 366-380.
[K1] A.G. Kurosh, Non-associative free algebras and free products of algebras (Rus-
sian), Mat. Sbornik, 20 (1947), 239-260 (English summary, 260-262).
[K2] A.G. Kurosh, Free sums of multiple operator algebras (Russian), Siberian
Math. J., 1 (1960), 62-70.
[K3] A.G. Kurosh, A cycle of papers on multioperator rings and algebras (Russian),
Uspehi Mat. Nauk 24 (1969), No. 1 (145), 3-15. Translation: Russ. Math.
Surv. 24 (1969), No. 1, 1-13.
[L] J. Lewin, On Schreier varieties of linear algebras, Trans. Amer. Math. Soc.
132 (1968), 553-562.
[Lo] J.-L. Loday, Generalized bialgebras and triples of operads, Preprint 2006.
[Mc] I.G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford Univ.
Press (Clarendon), Oxford, 1979, Second Edition, 1995.
[MSY] A.A. Mikhalev, V. Shpilrain, J.-T. Yu, Combinatorial Methods. Free Groups,
Polynomials, and Free Algebras, CMS Books in Mathematics 19, Springer,
New York, 2004.
Jo
ur
na
l A
lg
eb
ra
 D
isc
re
te 
M
ath
.V. Drensky, R. Holtkamp 41
[N] A. Nowicki, Polynomial Derivations and Their Rings of Constants, Uniwer-
sytet Mikolaja Kopernika, Torun, 1994.
[R] S. Rajaee, Non-associative Gro¨bner bases, J. Symb. Comp. 41 (2006), 887-904.
[Sl] N. Sloane (Edt.), The On-Line Encyclopedia of Integer Sequences, 2004,
http://www.research.att.com/˜njas/sequences/index.html
[SU] I.P. Shestakov, U.U. Umirbaev, Free Akivis algebras, primitive elements, and
hyperalgebras, J. Algebra 250 (2002), 533-548.
[U] V.A. Ufnarovski, Combinatorial and asymptotic methods in algebra, in A.I.
Kostrikin, I.R. Shafarevich (Eds.), “Algebra VI”, Encyclopedia of Math. Sci-
ences 57, Springer-Verlag, 1-196, 1995.
[W] R. Weitzenbo¨ck, U¨ber die Invarianten von linearen Gruppen, Acta Math. 58
(1932), 231-293.
[We1] H. Weyl, Zur Darstellungstheorie und Invariantenabza¨hlung der projektiven,
der Komplex- und der Drehungsgruppe, Acta Math. 48 (1926), 255-278;
reprinted in “Gesammelte Abhandlungen”, Band III, Springer-Verlag, Berlin
– Heidelberg – New York, 1968, 1-25.
[We2] H. Weyl, The Classical Groups, Their Invariants and Representations, Prince-
ton Univ. Press, Princeton, N.J., 1946, New Edition, 1997.
Contact information
V. Drensky Institute of Mathematics and Informatics,
Bulgarian Academy of Sciences, 1113 Sofia,
Bulgaria
E-Mail: drensky@math.bas.bg
R. Holtkamp Fakulta¨t fu¨r Mathematik, Ruhr-Universita¨t,
44780 Bochum, Germany
E-Mail: ralf.holtkamp@ruhr-uni-bochum.de
Received by the editors: 03.01.2008
and in final form 15.07.2008.