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.
Previous Page Next Page