Volume 592, 2013
The number of right ideals of given codimension over a finite
Roland Bacher and Christophe Reutenauer
Abstract. The number of right ideals of codimension n of the ring of non-
commutative polynomials in two variables over the finite field Fq is a poly-
nomial q-analogue of the n-th Catalan number. A generalization involving a
q-analogue of Fuß-Catalan numbers holds for more variables. We discuss also
a few aspects of right congruences over a free monoid.
A free associative algebra A is a free ideal ring by a theorem of P.M.Cohn.
Every right ideal I = IA is thus a free right module over A. Special bases of these
ideals have been constructed in [BR], using combinatorics on words and linear
recurrences for noncommutative rational series due to Sch¨ utzenberger [S].
We use this construction for enumerating right ideals of codimension n of a free
associative algebra over a finite field. It turns out that in the case of two variables,
the number of such ideals is given by a q-analogue of Catalan numbers which is, up
to a simple transformation, due to Carlitz and Riordan (see Theorem 1). For m 2
variables, we get q-analogues of Fuß-Catalan numbers enumerating rooted m-ary
trees (see Theorem 2). These results are implicit in the article of Marcus Reineke
Our construction, a non-commutative version of Buchberger’s algorithm for
Gr¨ obner bases, gives a short proof of them, taking advantage of the fact that the
free associative algebra is a free ideal ring.
Motivations and ideas come from [B] containing the enumeration of noncom-
mutative rational series of given rank (in the terminology of Michel Fliess, see [BR];
it is called complexity in [B]) over a finite field.
Our paper is organized as follows:
Chapter 2 is a brief review of Catalan and q-Catalan numbers.
Chapter 3 states our main results, Theorem 1 enumerating right ideals of codi-
mension n over Fq x, y and Theorem 2 giving the corresponding formula over
Fq x1,...,xm . They are proven in Chapters 9 and 10.
Chapters 4-8 introduce a few (mostly well-known) concepts and tools for the
he gives a decomposition of the noncommutative Hilbert scheme (whose points
are, for fixed n and m, the right ideals of codimension n of the free associative algebra with m
generators) into aﬃne cells.
c 2013 American Mathematical Society