Contemporary Mathematics

Volume 592, 2013

http://dx.doi.org/10.1090/conm/592/11865

The number of right ideals of given codimension over a finite

field

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.

1. Introduction

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

[R]

1.

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

proofs.

1Actually,

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

1