THE NUMBER OF RIGHT IDEALS OF GIVEN CODIMENSION OVER A FINITE FIELD 3

4. Prefix-free and prefix-closed sets

Given a finite set X of noncommuting variables, we denote by F X the ring of

noncommutative polynomials with variables X over a field F. According to a result

of P.M.Cohn [C], each right ideal I = IF X in F X is free as a right F X -module.

We follow [BR], Section 2.3, for the construction of bases. To the purpose we

introduce the free monoid X∗ generated by a finite set X. The set X is called the

alphabet and elements of X∗ are words. We identify henceforth a word w ∈ X∗

with the corresponding (non-commutative) monomial of F X . A word u is a prefix

of a word w if w = uv for some word v. A subset C of X∗ is prefix-free if no

element of C is a proper prefix of another element of C. Notice that prefix-free

sets are called “prefix sets”in [BR] and [BPR]. A subset P of X∗ is prefix-closed

if P contains all prefixes of its elements. Equivalently, P ⊂ X∗ is prefix-closed if

u ∈ P whenever there exists v ∈ X∗ such that uv ∈ P . In particular, a non-empty

prefix-closed set contains the empty word representing the identity of the monoid

X∗.

We denote the empty word by 1 in the sequel. A prefix-free set C is maximal if

it is not contained in a strictly larger prefix-free set. A prefix-free set C is maximal

if and only if the right ideal

CX∗

intersects every (non-empty) right ideal I =

IX∗

of the monoid

X∗.

(A right ideal of a monoid M is of course defined in the obvious

way as a subset I of M such that IM = I.) Indeed a prefix-free set C giving rise

to a right ideal

CX∗

not intersecting a right ideal I of

X∗

can be augmented by

adjoining an element of I. Conversely, a prefix-free set C strictly contained in a

prefix-free set C ∪ {g} defines a right ideal

CX∗

which is disjoint from the right

ideal

gX∗.

A third characterization of maximal prefix-free sets is given by the fact

that a prefix-free set C is maximal if and only if every element w of

X∗

\C contains

either an element of C as a proper prefix or is contained as a proper prefix in an

element of C.

Proposition 4.1. The map C → P = X∗ \ CX∗ defines a canonical bijection

between maximal prefix-free sets and prefix-closed sets containing no (non-empty)

right ideals of

X∗.

Its restriction to finite maximal prefix-free sets induces a bijection beween finite

maximal prefix-free sets and finite prefix-closed sets.

We leave the easy proof to the reader.

The map C → P =

X∗ \CX∗

of Proposition 4.1 associates to a maximal prefix-

free set C the prefix-closed set P consisting of all proper prefixes of elements in C.

(The empty word 1 is by convention a proper prefix of any non-empty word in X∗.)

The inverse map is given by P → PX \ P except in the case of the empty prefix-

closed set P = ∅ which corresponds to the maximal prefix-free set {1} reduced to

the identity of X∗.

Examples:

(1) The set C =

{x2,xy,y}

is a maximal prefix-free set in {x,

y}∗

with asso-

ciated prefix-closed set P = {1,x}.

(2) The set C =

x∗y

of all words of the form

xky

for k ≥ 0 an arbitrary natural

integer is maximal prefix-free in {x,

y}∗.

The associated prefix-closed set

P =

X∗

\

CX∗

is the free monoid

x∗

generated by x.

(3) The set C =

x∗y∗yx

of all words of the form

xkylx

with k ≥ 0 and

l ≥ 1 is maximal prefix-free in {x,

y}∗.

The associated prefix-closed set

P =

X∗

\

CX∗

is the set

x∗y∗

of all words

xkyl

with k, l ≥ 0.