Geometry monoid of the left distributivity and the left idempotency
We construct here the geometry monoids of LDI (left distributive idempotent) and of LDLI (left distributive left idempotent) identities. We study their properties and construct a monoid with solvable word problem based on relations of the geometry monoid of LDLI.
Збережено в:
| Дата: | 2006 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2006
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/157392 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Geometry monoid of the left distributivity and the left idempotency / P. Jedlicka // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 4. — С. 12–39. — Бібліогр.: 14 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-157392 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1573922019-06-21T01:28:24Z Geometry monoid of the left distributivity and the left idempotency Jedlicka, P. We construct here the geometry monoids of LDI (left distributive idempotent) and of LDLI (left distributive left idempotent) identities. We study their properties and construct a monoid with solvable word problem based on relations of the geometry monoid of LDLI. 2006 Article Geometry monoid of the left distributivity and the left idempotency / P. Jedlicka // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 4. — С. 12–39. — Бібліогр.: 14 назв. — англ. 1726-3255 http://dspace.nbuv.gov.ua/handle/123456789/157392 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We construct here the geometry monoids of LDI
(left distributive idempotent) and of LDLI (left distributive left
idempotent) identities. We study their properties and construct
a monoid with solvable word problem based on relations of the
geometry monoid of LDLI. |
| format |
Article |
| author |
Jedlicka, P. |
| spellingShingle |
Jedlicka, P. Geometry monoid of the left distributivity and the left idempotency Algebra and Discrete Mathematics |
| author_facet |
Jedlicka, P. |
| author_sort |
Jedlicka, P. |
| title |
Geometry monoid of the left distributivity and the left idempotency |
| title_short |
Geometry monoid of the left distributivity and the left idempotency |
| title_full |
Geometry monoid of the left distributivity and the left idempotency |
| title_fullStr |
Geometry monoid of the left distributivity and the left idempotency |
| title_full_unstemmed |
Geometry monoid of the left distributivity and the left idempotency |
| title_sort |
geometry monoid of the left distributivity and the left idempotency |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2006 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/157392 |
| citation_txt |
Geometry monoid of the left distributivity and the left idempotency / P. Jedlicka // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 4. — С. 12–39. — Бібліогр.: 14 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT jedlickap geometrymonoidoftheleftdistributivityandtheleftidempotency |
| first_indexed |
2025-07-14T09:49:45Z |
| last_indexed |
2025-07-14T09:49:45Z |
| _version_ |
1837615374200209408 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 4. (2006). pp. 12 – 39
c© Journal “Algebra and Discrete Mathematics”
Geometry monoid of the left distributivity and
the left idempotency
Přemysl Jedlička
Communicated by L. Marki
Abstract. We construct here the geometry monoids of LDI
(left distributive idempotent) and of LDLI (left distributive left
idempotent) identities. We study their properties and construct
a monoid with solvable word problem based on relations of the
geometry monoid of LDLI.
Introduction
Geometry monoids and geometry groups are structures that describe the
action of identities on terms. The most known ones are the Thompson
group F as the geometry group of the associativity and the Thompson
group V as the geometry group of the associativity and the commutativity
[8]. Actually, every identity has its geometry monoid and its geometry
group but the monoid can be too complicated and the group can be too
far away from the monoid to tell us something about the investigated
identity.
Nevertheless, in some cases, like of the left distributivity [5], studying
the geometry monoid brought a solution of the world problem. And the
method can be used also for some other identities, like x(yz) = (xy)(yz)
[6]. Hence a question arose whether this approach can or cannot solve
the world problem of the left distributivity and the idempotency (LDI),
that means of identities x(yz) = (xy)(xz) and x = xx. Regrettably, only
little progress has been achieved so far.
When studying the problem, the author focused on the identity of
the left idempotency xy = (xx)y which appears naturally in some left
distributive structures (e.g. left distributive left quasigroups). It seems
that the combination of the left distributivity and the left idempotency
P. Jedlička 13
(LDLI) is very close to LDI [9] and that their word problems could be of
the same difficulty to solve.
It is likely that any attempt to attack the word problem of LDI consid-
ering its monoid of geometry is hopeless. However, the geometry monoid
of LDLI looks more friendly and we manage here to construct a monoid
with solvable word problem based on the geometry monoid. This monoid
can serve as a corner stone for further constructions involving the geo-
metric monoid of LDLI.
We use in the paper the same approach as Dehornoy used for prov-
ing properties of the geometry monoid of the left distributivity [4]. In
Section 1 we introduce the geometry monoids for LDI and LDLI. In Sec-
tion 2 we study some relations in the geometry monoids and write them
down in a presentation. Monoids with this presentations are called syn-
tactical. In Section 3 we study the syntactical monoids and establish
some more complex relations. In Section 4 we prove that for any pair of
elements there exists a common right multiple. We use the result in Sec-
tion 5 where we prove by the word reversing method that the syntactical
monoid of LDLI is left cancellative, has solvable word problem and its
left divisibility order forms a lattice.
1. The geometry monoids
The construction of geometry monoids is already standard. We give thus
only a brief description of the monoids properties and leave some propo-
sitions unproved. A more detailed description is given in [10].
We fix an infinite set of variables {x1, x2, x3, . . .} and we denote by T
the set of all terms with these variables. We shall consider three types of
identities
left distributivity (LD) x(yz) = (xy)(xz)
idempotency (I) x = xx
left idempotency (LI) xy = (xx)y
To avoid excessive uses of parenthesis we write xyz instead of x(yz).
We shall consider two families of identities: left distributivity + idem-
potency (LDI) and left distributivity + left idempotency (LDLI). We
denote by
LDI
= and
LDLI
= the congruences on T generated by these families
respectively.
Applying an identity means replacing a subterm of a specific form
by a term of another specific form. We shall formalise this situation
introducing addresses of subterms. Each subterm is represented by a
14 Geometry monoid of LDLI
sequence from {0, 1}∗ where 0 means left and 1 means right. The empty
sequence is denoted by ∅. The set of all addresses is denoted A.
Definition. For each address α, we define dα as the partial function
from T to T that replaces the subterm t1t2t3 on the address α by the
term t1t2 · t1t3. We also define iα as the partial function from T to T
that replaces the subterm t1 on the address α by the term t1t1. We
write t • dα, respectively t • iα to be the images of a term t under these
mappings.
Example 1.1. Consider t = x1x2x3x4 (see Figure 1). The term belongs
to the domain of the operators d∅, d1, i∅, i0, i1, i10, i11, i110 and i111.
x1
x2
x3 x4
x1
x2 x3 x2 x4
d1 : 7→
x1
x2
x3 x4
x1
x2
x3 x4
x2
x3 x4
i1 : 7→
Figure 1: The operators d1 and i1 and their actions on the
term x1 · x2 · x3 · x4.
We have not defined what is an LI-operator. In fact, we do not need
it if we notice that replacing a subterm t1t2 on an address α by t1t1 · t2 is
the same as doubling the subterm on the address α0, i.e., applying the
operator iα0.
We also need a formal notation for an operator that can mean either
an dα or an iα. Since we will work in different contexts (LD, LDI or
LDLI), we should be careful and give an exact definition of what such an
operator diα means.
Definition. Let ALD and AI be two disjoint copies of the address set A.
We denote by ALDI the set ALD ∪AI and, for each α in ALDI, we define diα
either as dα if α belongs to ALD, or as iα if α belongs to AI. We denote
also by ALI the subset of AI defined as {α ∈ AI; ∃γ : α = γ0} and we
denote by ALDLI the set ALD ∪ ALI.
The following lemma results immediately from the definition of the
operators:
P. Jedlička 15
Lemma 1.2. For each address α in ALDI, the operator diα is a partial
injective mapping to T ; its inverse is the operator di
−1
α defined as diα but
exchanging the roles of t1t2t3 and t1t2 · t1t3, respectively t1 and t1t1.
All the following material in the section is written for the family LDI
but we can formulate all the things the same way for the family LDLI.
Definition. The geometry monoid of LDI is the monoid GLDI generated
by the operators di
±1
α with α in ALDI using the composition. Analogi-
cally, the positive geometry monoid is the monoid G+
LDI
generated by the
operators diα with α in ALDI
The monoid GLDI is not a group because the mapping di−1
α ◦diα is
not generally the identical mapping on T , it is only the identity on the
domain of diα.
By definition, the elements of G+
LDI
are finite products of operators diα
hence they are of the form
diαp ◦ · · · ◦ diα2
◦diα1
.
Such elements can be expressed as finite sequences of addresses in ALDI,
i.e., by words on ALDI. We denote by A
∗
LDI
the set of such words. The
product of two words u and v is the concatenation of the words, denoted
by uv or u · v. We write the ε symbol for the empty word.
Remark 1.3. We should not confuse ∅ and ε. The word ε is a word of
length 0. The word ∅ is a word of length 1 that consists of the address ∅
(the empty address).
We consider that the operators diα act on the right, i.e., that we
compose the operators from the left to the right. Therefore, in order not
to confuse the composition to the right with the composition ◦, we use
the symbol •.
Definition. For α1 · · · · · αp in A
∗
LDI
, the operator diu is defined as diα1
•
· · · • diαp , i.e., as diαp ◦ · · · ◦ diα1
. The operator diε is defined as the
identity.
Consider now the monoid GLDI. Its elements are of the form
di
e1
α1
• di
e2
α2
• · · · • di
ep
αp
with αi in ALDI and ei = ±1, for i between 1 and p. To specify such a
product, it is natural to introduce the formal inverse α−1 of an address α
in ALDI. We write A
−1
LDI
for the set of formal inverses of addresses in ALDI,
and A
±1
LDI
for the set ALDI ∪ A
−1
LDI
.
16 Geometry monoid of LDLI
Definition. For w = αe1
1 · · · · ·α
ep
p in (A±1
LDI
)∗, the operator diw is defined
as the product di
e1
α1
• · · · • di
ep
αp .
The elements in A
∗
LDI
are called positive words and the ones in (A±1
LDI
)∗
are called simply words.
Definition. For a term t and a word w in (A±1
LDI
)∗, the term t • w is
defined as the image of t under the mapping diw, if it exists.
By construction, one has the relation t • w
LDI
= t for each word w
in (A±1
LDI
)∗, if t belongs to the domain of diw. In fact, if we consider the
definition of an equivalence on terms, we get immediately an equivalence:
Proposition 1.4. Let t and t′ be two terms in T . The terms t and t′ are
LDI-equivalent if and only if an operator in GLDI sends t to t′, i.e., if we
have t′ = t • w for a word w on A
±1
LDI
.
In order to be able to study the operators more deeply, we have to
describe their domains. This can be done by a rather standard technique
and hence there is no need to prove the results here properly. The reader
can look into Dehornoy’s book [4], where the results were proved properly
for the left distributivity, and check that it works exactly the same way
for LDI (one needs only to notice that a term belongs to the domain of a
positive operator diα if and only if it is large enough). We give here thus
the results of the investigation only.
Definition. A substitution h is a homomorphism h : T → T . A substitute
of a term t is a term h(t) for a substitution h.
Proposition 1.5. [10] For each positive word u on ALDI there exists a
unique (up to renaming of variables) pair of terms (tLu , tRu ) such that the
operator diu sends a term t on a term t′ if and only if there exists a
substitution h such that (tLu )h = t and (tRu )h = t′.
Example 1.6. Take, for instance, du = d0 • i10. Every term in the
domain of du has to contain the addresses 010 and 10. The most general
such a term is tLu = x1x2x3 ·x4x5 and one has tRu = tLu • u = (x1x2 ·x1x3) ·
x4x4 · x5.
Proposition 1.7. [10] Let u1, . . . , um be two words on ALDI. Then the
intersection of the domains of the operators diu1
, . . . ,dium is the set of
all the substitutes of a unique term tLu1,...,um
.
Example 1.8. Consider diu1
= d0 • i10 and diu2
= d∅
• d1 • i00.
Any term in the domain of both the operators have to contain the ad-
dresses 010 and 10 (from u1) as well as the addresses 10, 110 and 0
(from u2). The most general such a term is tLu1,u2
= x1x2x3 · x4x5x6.
P. Jedlička 17
2. Relations in the positive geometry monoids
In this section we find some relations true in the positive geometry
monoids. We consider the monoid G+
LDLI
as a submonoid of the monoid G+
LDI
and hence it suffices to state all the found results for G+
LDI
.
Definition. Let t be a term. An address α is called internal if there
exists a subterm of t at the address α. The set of all internal addresses is
called the skeleton of t and denoted by Skel(t). The outline of t, denoted
by Out(t) is the set of all addresses of all leaves of t. An addresses α is
called a prefix of an address β if we have αγ = β for some address γ. We
write then α ⊑ β. If neither α is a prefix of β nor β is a prefix of α then
we say that they are orthogonal and we write α ⊥ β.
We first notice that if two operators act on orthogonal addresses then
they act independently on independent subterms. Therefore we can com-
mute them and obtain, for all α, β, γ,
diα0γ • diα1β = diα1β • diα0γ .
Hence we can consider only pairs of addresses where one is a prefix of the
other. For facilitating the notation we introduce the shifting of addresses.
Definition. For w a word on A
±1
LDI
and γ an address in A, we denote
by shγ(w), or simply by γw, the γ-shift of w defined as the word obtained
from w replacing each address α±1 by the address γα±1.
Example 2.1. For diu = d01 • i110 • i∅ one has di1u = d101 • i1110 • i1.
Analogously, di1ε = diε = idT since ε is the empty address.
We immediately see
Lemma 2.2. For each α, diw = diw′ implies diαw = diαw′ .
Hence we can suppose from now on that one of the operators is di∅.
Let us start with i∅. If an operator diα acts on a term t and we then
double the term, it is the same as to apply di0α • di1α on the term t · t.
Therefore we get
diα • i∅ = i∅ • di0α • di1α .
Now consider the operator d∅. If an operator acts in the left subterm
of a term t, for instance di0α, its image is copied by d∅ to two addresses,
namely 00α and 10α. Therefore we obtain
di0α • d∅ = d∅
• di00α • di10α .
18 Geometry monoid of LDLI
Analogically, the subterm 10 is sent to 01 and the subterm 11 is left
untouched. Therefore we have
di10α • d∅ = d∅
• di01α,
di11α • d∅ = d∅
• di11α .
However, not all relations are that simple. We present here a “relation”
where we have to be careful about the domain of the operators.
Lemma 2.3. For each term t which is not a variable, we have
t • i1 • d∅ = t • i∅ .
Proof. Let t = t1 · t2. Left side makes t 7→ t1 · t2 · t2 7→ (t1 · t2) · (t1 · t2)
which is clearly the image of t under i∅.
Although i1 • d∅ = i∅ is not true (no variable is in the domain of
the left hand side operator), once you multiply the “equality” on the left
by anything, you obtain a real equality. Analogously, if you multiply the
“equality” by something (not i∅ nor i0 nor i1) on the right, you demand
that each term in the domain of both operators is more complex than a
variable and hence you obtain an equality.
Now there are three more relations that are not so evident:
Lemma 2.4. One has
d1 • d∅
• d1 • d0 = d∅
• d1 • d∅,
i10 • d∅
• d0 = d∅
• i0,
i1 • d∅
• d1 • d0 = d∅
• i∅ .
Proof. (i) The left side treats a term t1 ·t2 ·t3 ·t4 followingly: t1 ·t2 ·t3 ·t4 7→
t1 · (t2 · t3) · t2 · t4 7→ (t1 · t2 · t3) · t1 · t2 · t4 7→ (t1 · t2 · t3) · (t1 · t2) · t1 · t4 7→
((t1 · t2) · t1 · t3) · (t1 · t2) · t1 · t4. The right side makes: t1 · t2 · t3 · t4 7→
(t1 · t2) · t1 · t3 · t4 7→ (t1 · t2) · (t1 · t3) · t1 · t4 7→ ((t1 · t2) · t1 · t3) · (t1 · t2) · t1 · t4.
(ii) The left side sends a term t1 · t2 · t3 to t1 · (t2 · t2) · t3 7→ (t1 · t2 ·
t2) · t1 · t3 7→ ((t1 · t2) · t1 · t2) · t1 · t3 which is clearly the same as the image
of t1·t2·t3 under the right side. The third relation is d∅
• i∅ = i∅ • d1 • d0
combined with Lemma 2.3.
We finish at this point the study of relations in the geometry monoid
since it is not too comfortable: we have to check every time equality of
mappings and for more complicated relations it becomes too technical. In
order to avoid this computation with operators, we are going to present
formal monoids that could be isomorphic to geometry monoids; we simply
P. Jedlička 19
give the presentations of the formal monoids. These formal monoids
are called syntactical monoids. Since the monoids can differ from the
geometry ones, we have to use formally different elements.
Definition. The set ALDI is defined as the set of symbols dα and iα,
with α in ALDI. An LDI-relation is a pair of words in ALDI among the
following relations:
(dγ0α · dγ1β , dγ1β · dγ0α) type ⊥
(iγ0α · dγ1β , dγ1β · iγ0α) type ⊥
(dγ0α · iγ1β , iγ1β · dγ0α) type ⊥
(iγ0α · iγ1β , iγ1β · iγ0α) type ⊥
(dγ0α · dγ , dγ · dγ00α · dγ10α) type D0
(dγ10α · dγ , dγ · dγ01α) type D10
(dγ11α · dγ , dγ · dγ11α) type D11
(dγ1 · dγ · dγ1 · dγ0 , dγ · dγ1 · dγ) type D1
(iγα · iγ , iγ · iγ0α · iγ1α) type I
(dγα · iγ , iγ · dγ0α · dγ1α) type DI
(iγ0α · dγ , dγ · iγ00α · iγ10α) type ID0
(iγ10α · dγ , dγ · iγ01α) type ID10
(iγ10 · dγ · dγ0 , dγ · iγ0) type ID10+
(iγ11α · dγ , dγ · iγ11α) type ID11
(iγ1 · dγ · dγ1 · dγ0 , dγ · iγ) type ID1
(dγα · iγ1 · dγ , dγα · iγ) type C
(iγα · iγ1 · dγ , iγα · iγ) type C
(dγ · iγ11 · dγ1 , dγ · iγ1) type C
(iγ1 · dγ · iγα , iγ · iγα) lg(α) ≥ 2 type C
(iγ1 · dγ · dγα , iγ · dγα) type C
The set ALDLI is defined as the set of symbols dα and iα, with α in ALDLI.
An LDLI-relation is an LDI-relation (u, v) such that u and v belong
to ALDLI. The relation ≡+
LDI
is defined as the congruence of the monoid A∗
LDI
generated by the LDI-relations. The relation ≡+
LDLI
is defined analogously.
If we want to prove that syntactical monoids are isomorphic to geom-
etry monoids, we have to prove diu ≡+
LDI
div if and only if diu = div, for
all pairs u, v. One implication is immediate:
Proposition 2.5. For u, v in A
∗
LDI
, the relation diu ≡+
LDI
div gives diu =
div.
20 Geometry monoid of LDLI
Proof. If (diu, div) is an LDI-relation, the equality diu = div falls to one
of the types discussed before the definition (possibly up to a shift, which
does not make a difference due to Lemma 2.2). The rest is evident.
We will not prove here the other direction, its validity is unknown for
LDI and known to be false for LDLI, as we will see in the last section.
Nevertheless, the monoids given by these presentations are rich enough
to have all the properties we need in our further study. And, of course,
since the geometry monoids are factors of the syntactical monoids, all
relations, which are proved in the syntactical monoids, hold also in the
geometry monoids.
3. Syntactical relations
In this section we establish some more complex relations. We will work
with both the relations ≡+
LDI
and ≡+
LDLI
at once. To facilitate the expression,
we will write only the symbol ≡+: the expression “u ≡+ v, for all words u
and v” shall mean u ≡+
LDI
v, for all words u and v in A
∗
LDI
, as well as
u ≡+
LDLI
v, for all words u and v in A
∗
LDLI
. If some relation involves ≡+
LDI
only, we write ≡+
LDI
explicitly.
Proposition 3.1. For u, u′ two words and α in A, the relation diu ≡+
diu′ gives diαu ≡+
diαu′ .
Lemma 3.2. Let u1 and u2 be two words such that each address in u1 is
orthogonal to each address in u2. Then we have
diu1
· diu2
≡+
diu2
· diu1
diu1
· diu2
· i∅ ≡+
LDI
i∅ · di0u1
· di0u2
· di1u1
di1u2
di0u1
· di0u2
· d∅ ≡+
d∅ · di00u1
· di00u2
· di10u1
di10u2
di10u1
· di10u2
· d∅ ≡+
d∅ · di01u1
di01u2
di11u1
· di11u2
· d∅ ≡+
d∅ · di11u1
di11u2
Proof. Use the induction on lg(u1) + lg(u2).
Now we define the heirs of a set B. The heirs are addresses obtained
as images of B by an operator diu.
Definition. Let B a set of addresses of A, and let u be a word on ALDI.
The set Heir(B, u) of all heirs of addresses in B by the operator diu is
defined inductively:
(i) Heir(B, u) exists if and only if Heir({β}, u) exists for each β in B,
and, in this case, we have Heir(B, u) =
⋃
β∈B Heir({β}, u);
P. Jedlička 21
(ii) For each B we have Heir(B, ε) = B;
(iii) For each α in ALDI, Heir({β}, α) is defined as:
Heir({β}, α) =
{β} for β ⊥ α or β = α11γ,
{α00γ, α10γ} for β = α0γ,
{α01γ} for β = α10γ,
is not defined for β ⊑ α1,
for α ∈ ALD,
Heir({β}, α) =
{β} for β ⊥ α,
{α0γ, α1γ} for β = αγ,
is not defined for β ⊏ α.
for α ∈ AI,
(iv) For u = α ·u0, we have Heir(B, u) = Heir(Heir(B, α), u0), if it exists.
The following lemma is easy to see:
Lemma 3.3. Let u be a word on ALDI and let β be an address.
(i) If Heir({β}, u) is defined then Heir({βγ}, u) is also defined, for each
address γ, and we have Heir({βγ}, u) = {β′γ; β′ ∈ Heir({β}, u)}.
(ii) The elements in every set Heir({β}, u) are pairwise orthogonal.
(iii) Suppose t′ = t • u and β in Skel(t). If Heir({β}, u) is defined then
the subterms of t′ at all addresses in Heir({β}, u) are equal.
Proposition 3.4. Suppose that u is a word, that β is an address in A
and that Heir({β}, u) is defined. Then we have
dβ · diu ≡+
diu ·
∏
β′∈Heir({β},u)
dβ′ ,
iβ · diu ≡+
diu ·
∏
β′∈Heir({β},u)
iβ′ .
The latter equivalence is true for LDLI only if Heir({β}, u) contains only
addresses from ALI.
Proof. We show the result by the induction on lg(u). For u = ε, the
result is evident. Suppose now diu = iα. The set Heir({β}, u) exists and
so α is either orthogonal to β, or it is a prefix of β. The orthogonal case
is solved by Lemma 3.2. Suppose αγ = β. But the relation diβ · iα ≡+
iα · diα0γ · diα1γ is an LDI-relation of type DI or I.
For diu = dα there are four possibilities:
a) β ⊥ γ is solved by Lemma 3.2 (i);
b) β = α0γ gives diβ · dα ≡+
dα · diα00γ · diα10γ (types D0 or ID0);
c) β = α10γ gives diβ · dα ≡+
diα · diα01γ (types D10 or ID10), except of
22 Geometry monoid of LDLI
the case diβ = iα10 where the relation is not true for LDLI since iα01 is
not in ALDLI;
d) β = α11γ gives diβ · dα ≡+
dα · diβ (types D11 or ID11).
No other possibilities occur since the set Heir({β}, u) is defined.
Suppose now lg(u) ≥ 2, let us say u = α · u0. By construction,
the hypothesis that Heir({β}, u) exists gives the existence of the set
Heir({β}, α) and of the set Heir(Heir({β}, α), u0) and that the latter is
equal to Heir({β}, u). By the induction hypothesis, one has
diβ · diu ≡+
diα ·
∏
β′∈Heir({β},α)
diβ′ · diu0
.
By the induction hypothesis again, one has, for each β′ in Heir({β}, α),
diβ′ · diu0
≡+
diu0
·
∏
β′′∈Heir({β′},u0)
diβ′′ ,
and one gets
diβ · diu ≡+
diα ·
∏
β′∈Heir({β},α)
∏
β′′∈Heir({β′},u0)
diβ′′ .
Now, according to Lemma 3.3 (ii), the addresses β′ are pairwise orthog-
onal, the operators commute and the double product in the formula is
equal to the expression
∏
β′∈Heir({β},u) diβ′ .
One has to be more careful in the case of LDLI. If an address γ ends
by 1, there is always a heir of γ that ends by 1. Therefore, if the set
Heir({β}, u) contains no address ending by 1, neither does Heir({β}, α).
Hence, the induction step is correct for iβ and LDLI-equivalence too.
Definition. The image of a term t under an element diu from A∗
LDI
, writ-
ten t • diu, is understood to be the term t • diu.
Note that, due to Proposition 2.5, two ≡+-equivalent words have the
same action on terms.
We are going to establish now a few relations tied to a distributive
action called the uniform distribution.
Definition (uniform distribution). Let t0, t be two terms. We define the
term t0 ∗ t inductively:
t0 ∗ t =
{
t0 · t for t a variable
(t0 ∗ t1) · (t0 ∗ t2) when t = t1 · t2.
P. Jedlička 23
The uniform distribution consist of distributing t0 into every leaf of t,
that means of replacing every variable x in t by t0·x [4]. Now we introduce
a word δt associated with the uniform distribution. More precisely said,
any term t0 · t is sent by δt to t0 ∗ t.
Definition. [4] For t a term, we define the word δt on ALD by:
δt =
{
ε when t is a variable,
d∅ · sh1(δt2) · sh0(δt1) for t = t1 · t2,
where shγ(du) stands for dγu and the symbol ε means in fact diε (the
neutral element of the syntactical monoid).
Proposition 3.5. [4] For all terms t0, t in T , we have t0t • δt = t0 ∗ t.
In the following parts of the paper we are going to make some more
technical computations. Although many of the calculations can be rep-
resented using terms, all the work has to be done in a formal way. To
facilitate the comprehension, we use the following notation:
diu ·
∧
div · diα · diw ≡+
diu · diα · div′ · diw (XY)
meaning that we want to push the symbol diα forward in front of the word
div. We do this using the relation of type XY which, in this situation,
gives div · diα ≡+
diα · div′ .
The first technical proposition says that if we have an action t → t′
and a uniform distribution t0 · t → t0 ∗ t then we can swap them, what
means that t0 · t → t0 ∗ t → t0 ∗ t′ and t0 · t → t0 · t
′ → t0 ∗ t′ give the
same results.
Proposition 3.6. Suppose that u is a word, that t is not a variable and
that diu sends t on t′. Then we have
δt · diu ≡+
di1u · δt′ .
Proof. The proof for u in A
∗
LD
, is done in [4] hence suppose u 6∈ A
∗
LD
.
We show the result by the induction on lg(u). For u = ε, the result
is vacuously true, for u = α, we do the induction on the length of α.
Denote t = t1 · t2. For diα = i∅, we have
δt · diu = d∅ ·
∧
1δt2 · 0δt1 · i∅ (DI)
≡+
LDI
∧
d∅ · i∅ · 01δt2 · 11δt2 · 00δt1 · 10δt1 (ID1)
≡+
LDI
i1 · d∅ · d1 ·
∧
d0 · 01δt2 · 11δt2
∧
· 00δt1 · 10δt1 (⊥)
≡+
LDI
i1 · d∅ · 1δt · 0δt = di1u · δt′ .
24 Geometry monoid of LDLI
Now suppose diα = i0. We have, for t1 a variable,
δt · diu = d∅ ·
∧
1δt2 · i0 (⊥)
≡+
LDLI
∧
d∅ · i0 · 1δt2 (ID10+)
≡+
LDLI
i10 · d∅ · 1δt2 · d0 = di1u · δt′ .
For t1 = t3 · t4, we have
δt · diu = d∅ · 1δt2 · 0δt1 · i0 = d∅ ·
∧
1δt2 · d0 · 01δt4 · 00δt3 · i0 (DI)
≡+
LDLI
∧
d∅ · i0 · 1δt2 · d00 · d01 · 001δt4 · 011δt4 · 000δt3 · 010δt3 (ID10+)
≡+
LDLI
i10 · d∅ · 1δt2 · d0 · 01δt1 · 00δt1 = di1u · δt′ .
Suppose now α = 0β with β nonempty in AI, respectively in ALI. We
write t′ = t′1 · t
′
2 and we know that diβ sends t1 on t′1. By the induction
hypothesis we have δt1 · iβ ≡+
i1β · δt′
1
. According to Proposition 3.1, we
have 0δt1 · i0β ≡+
i01β · 0δt′
1
and we find
δt · diu = d∅ · 1δt2 · 0δt1 · i0β
∧
≡+
d∅ ·
∧
0δt1 · i0β · 1δt2 (⊥), (hyp.)
≡+
∧
d∅ · i01β ·
∧
0δt′
1
· 1δt2 (ID10), (⊥)
≡+
di10β · d∅ · 1δt2 · 0δt′
1
= di1α · δt′ .
The argument for α = 1β is similar and the induction on lg(u) is simple.
The following lemma expresses that making t0 ∗ (t1 ∗ t2) is in fact
replacing each variable x of the term t2 by the term (t0 ∗ t1) · (t0 · x).
Lemma 3.7. For each t1, t2, we have
δt1∗t2 ≡+ δt2 ·
∏
α∈Out(t2)
(
dα · α0δt1
)
.
Proof. This product is correctly defined because all the addresses from the
outline of t2 are pairwise orthogonal. We show the lemma by induction
on t2. When t2 is a variable, one has δt1∗t2 = δt1·t2 = d∅ ·0δt1 = δt2 · (d∅ ·
0δt1). Hence suppose t2 = t3 · t4. One computes
δt1∗t2 = δ(t1∗t3)·(t1∗t4) = d∅ · 1δt1∗t4 · 0δt1∗t3 (def.)
≡+
d∅ · 1δt4 ·
∏
α∈Out(t4)
(d1α · 1α0δt1) · 0δt3 ·
∏
β∈Out(t3)
(d0β · 0β0δt1) (hyp.)
≡+ δt2 ·
∏
α∈Out(t2)
(dα · α0δt1) (⊥)
and this is the searched form.
P. Jedlička 25
Proposition 3.8. For each term t and each u a word, we have
di0u · δt ≡
+ δt ·
∏
α∈Out(t)
diα0u .
Proof. The idea of the proof is the following: let t0 be a term in the
domain of diu and let t′0 be its inverse under diu. Then the left-hand side
encodes t0t → t′0t → t′0 ∗ t and the right hand side encodes t0t → t0 ∗ t →
t′0 ∗ t.
More precisely, δt applied to t0t distributes t0 into every leaf of t.
Therefore Heir({0}, δt) is {α0, α ∈ Out(t)} and analogously Heir({0β}, δt)
is {α0β, α ∈ Out(t)} (see [4]). Hence, applying Proposition 3.4, we get
the result.
4. Confluence
In this section we prove the existence of a common right multiple of
an arbitrary pair of elements. The geometric idea (which is to be proved
further in the section) is the following: let t be a term and let t1, t2,. . . be
terms obtained by different positive operators diαi
with t in its domain.
Then there exists a term, denoted by ∂t, and positive words u1, u2,. . .
such that ∂t is the image of ti under diui
for each i. The term ∂t is
described inductively:
Definition. [14] Let t be a term. We define the terms ∂LDIt et ∂LDLIt by:
∂LDIt =
{
t · t if t is a variable,
∂LDIt1 ∗ ∂LDIt2 for t = t1 · t2,
∂LDLIt =
{
t if t is a variable,
∂LDIt1 ∗ ∂LDLIt2 for t = t1 · t2.
We write only ∂t when a statement is declared for both ∂LDIt and ∂LDLIt.
We translate the geometrical situation introducing the elements ∆t
which send t to ∂t.
Definition. For t a term, we define the elements ∆LDI
t and ∆LDLI
t induc-
tively:
∆LDI
t =
{
i∅ when t is a variable,
sh0(∆
LDI
t1
) · δt2 · ∆
LDI
t2
for t = t1 · t2,
∆LDLI
t =
{
ε when t is a variable,
sh0(∆
LDI
t1
) · δt2 · ∆
LDLI
t2
for t = t1 · t2,
Again, we write simply ∆t when a statement is true for both ∆LDI
t and ∆LDLI
t .
26 Geometry monoid of LDLI
Lemma 4.1. We define ∆̂t as ∆t, for t a variable, and as 0∆̂LDI
t1
·1∆̂t2 ·δ∂t2,
for t = t1t2. Then ∆̂t sends t to ∂t, for each t.
Proof. When t is a variable, the result holds. Suppose now t = t1 · t2 and
t • ∆̂t = (t1 · t2) • (0∆̂LDI
t1
· 1∆̂t2 · δ∂t2) = (∂LDIt1 · t2) • (1∆̂t2 · δ∂t2) =
= (∂LDIt1 · ∂t2) • δ∂t2 = ∂LDIt1 ∗ ∂t2 = ∂t
is obtained.
Lemma 4.2. Suppose t = t1 · t2. Then one has
(i) ∆t ≡
+ 1∆t2 · 0∆LDI
t1
· δ∂t2 ,
(ii) ∆t ≡
+ δt2 ·
∏
α∈Out(t2)
α0∆LDI
t1
· ∆t2 .
(i) We prove the relation by induction on t2 as well as ∆t ≡+ ∆̂t
from Lemma 4.1. When t2 is a variable, the result is true for ∆LDLI
t since
δt2 = δ∂t2 = ε. For ∆LDI
t one has
∆LDI
t = 0∆LDI
t1
· i∅ ≡+
LDI
0∆LDI
t1
· i1 · d∅ = 0∆LDI
t1
· 1∆LDI
t2
· δ∂t2 = ∆̂LDI
t (C)
≡+
LDI
1∆LDI
t2
· 0∆LDI
t1
· δ∂t2 . (⊥)
When t2 is not a variable, we use Proposition 3.6, Lemma 4.1 and the
induction hypothesis to obtain ∆t ≡
+ 0∆t1 · 1∆t2 · δ∂t2 ≡+ ∆̂t. The idea
is that ∆t2 , being equivalent to ∆̂t2 , sends t to ∂t.
(ii) This follows from (i) and Proposition 3.8.
Proposition 4.3. For each t, one has t • ∆t = ∂t.
Proof. It was already proved in the proof of Lemma 4.2 (i).
Lemma 4.4. For each term t we have ∆LDI
t ≡+
LDI
i∅ · 0∆LDLI
t · 1∆LDLI
t .
Proof. We use the induction on t. The result holds trivially when t is a
variable. For t = t1 · t2 we obtain
∆LDI
t ≡+
LDI
0∆LDI
t1
·
∧
δt2 · i∅ · 0∆LDLI
t2
· 1∆LDLI
t2
(hyp.), (DI)
≡+
LDI
∧
0∆LDI
t1
· i∅ · 0δt2 ·
∧
1δt2 · 0∆LDLI
t2
· 1∆LDLI
t2
(I),(DI), (⊥)
≡+
LDI
i∅ · 00∆LDI
t1
·10∆LDI
t1
· 0δt2 · 0∆LDLI
t2
∧
· 1δt2 · 1∆LDLI
t2
(⊥)
≡+
LDI
i∅ · 0∆LDLI
t · 1∆LDLI
t ,
which finishes the proof.
P. Jedlička 27
Now we show the geometric idea from the beginning of the section.
Proposition 4.5. Suppose that t belongs to the domain of diα, with α an
address. Then there exists a positive word u satisfying diα · diu ≡+ ∆t.
Proof. When t is a variable then the result holds by definition. Sup-
pose t = t1 · t2. We use the induction on α. For diα = d∅, the result
follows from Lemma 4.2 (ii). For diα = i∅ or diα = i0, we use Lemma 4.4.
Suppose now α = 0β. By definition, the word ∆t begins by 0∆t1 . By
the induction hypothesis, the word ∆t1 is equivalent to diβ · diu′ for a
word u′. Hence we obtain ∆t ≡
+
diα · di0u′ · δt2 · ∆t2 . The argument is
similar for α = 1β due to Lemma 4.2 (i).
Now a few lemmas come in the direction of finding a common right
multiple.
Lemma 4.6. If α sends t on t′ then there exists a positive word u such
that diα · ∆t′ ≡
+ ∆t · diu.
Proof. We show the result by the induction on α. For diα = i∅, one has
diα · ∆LDI
t′ ≡+
LDI
i∅ · 0∆LDI
t · 1∆LDI
t
∧
· δ∂LDIt ≡
+
LDI
∆LDI
t · i∅ · δ∂LDIt.
For diα = i0 and t = t1 · t2, one has
diα ·∆LDLI
t′ ≡+
LDLI
i0 · 0∆LDI
t1·t1 · 1∆LDLI
t2
· δ∂LDLIt2 (L 4.2)
≡+
LDLI
i0 · 00∆LDI
t1
· 01∆LDI
t1
∧
·
∧
0δ∂LDIt1 · 1∆LDLI
t2
· δ∂LDLIt2 (I, DI), (⊥)
≡+
LDLI
0∆LDI
t1
· 1∆LDLI
t2
·
∧
i0 · 0δ∂LDIt1 · δ∂LDLIt2 (P 3.8)
≡+
LDLI
0∆LDI
t1
· 1∆LDLI
t2
· δ∂LDLIt2 · Π(iβ0 · β0δ∂LDIt1) (L 4.2)
≡+
LDLI
∆LDLI
t · Πβ∈Out(∂LDLIt2)(iβ0 · β0δ∂LDIt1).
Suppose diα = d∅ and t = t1 · (t2 · t3). One has
dα · ∆t′ = d∅ · ∆(t1·t2)·(t1·t3)
≡+
d∅ · 0∆LDI
t1·t2 · 1∆t1·t3 · δ∂(t1·t3) (L 4.2)
≡+
d∅ · 00∆LDI
t1
∧
· 01∆LDI
t2
· 0δ∂LDIt2 · 10(∆LDI
t1
)
· 11∆t3 · 1δ∂t3 · δ∂LDIt1∗∂t3 (⊥, D0, ID0)
≡+ 0∆LDI
t1
· d∅ · 01∆LDI
t2
∧
· 11∆t3 · 0δ∂LDIt2
· 1δ∂t3 · δ∂LDIt1∗∂t3 (D10, ID10)
28 Geometry monoid of LDLI
≡+ 0∆LDI
t1
· 10∆LDI
t2
· d∅ · 11∆t3
∧
· 0δ∂LDIt2
· 1δ∂t3 · δ∂LDIt1∗∂t3 (D11, ID11)
≡+ 0∆LDI
t1
· 10∆LDI
t2
· 11∆t3 · d∅ · 0δ∂LDIt2
· 1δ∂t3 · δ∂LDIt1∗∂t3 (L 3.7)
≡+ 0∆LDI
t1
· 10∆LDI
t2
· 11∆t3 ·
∧
δ∂LDIt2·∂t3 · δ∂t3
· Π(dα · α0δ∂LDIt1) (P 3.6)
≡+ 0∆LDI
t1
· 10∆LDI
t2
· 11∆t3 · 1δ∂t3
· δ∂LDIt2∗∂t3 · Π(dα · α0δ∂LDIt1) (L 4.2)
≡+ 0∆LDI
t1
· 1∆t2·t3 · δ∂(t2·t3) · Π(dα · α0δ∂LDIt1) (L 4.2)
≡+ ∆t1·(t2·t3) · Π(dα · α0δ∂LDIt1).
Suppose now α = 0β and t = t1 · t2. Since diβ sends t1 on a term t′1,
the hypothesis gives us diβ · ∆t′
1
≡+ ∆t1 · diu′ for a word u′. Hence one
has
diα · ∆t′ = di0β · ∆t′
1
·t2 = di0β · 0∆LDI
t′
1∧
· δt2 · ∆t2 (hyp)
≡+ 0∆LDI
t1
· di0u′ · 1∆t2 · δ∂t2
∧
(P 3.8)
≡+ 0∆LDI
t1
· 1∆t2 · δ∂t2 · Π(diβ0u′)
≡+ ∆t · Π(diβ0u′).
Finally, we suppose α = 1β and t′ = t1 · t
′
2. By the induction hypoth-
esis, one has diβ · ∆t′
2
≡+ ∆t2 · diu′ . One finds
diα · ∆t′ ≡
+
di1β · 1∆t′
2∧
· 0∆LDI
t1
· δ∂t′
2
(hyp)
≡+ 1∆t2 · di1u′ · 0∆LDI
t1
· δ∂t′
2∧
(P 3.6)
≡+ 1∆t2 · 0∆LDI
t1
· δ∂t2 · diu′ ≡+ ∆t · diu′
where the equality di1u′ · δ∂t′
2
≡+ δ∂t2 · du′ follows from Proposition 3.6
since one has t2 • (diβ · ∆t′
2
) = ∂t′2 = t2 • (∆t2 · diu′) and hence one
has ∂t′2 = ∂t2 • diu′ .
Lemma 4.7. Suppose that u is a positive word and that diu sends t on t′.
Then there exists a positive word u′ satisfying
diu · ∆t′ ≡
+ ∆t · diu′ .
Proof. We use the induction on lg(u). For u = ε, the result is triv-
ial. For lg(u) = 1, the result is Lemma 4.6. Suppose now u = u1 · u2,
P. Jedlička 29
where neither u1 nor u2 are empty. Let t1 = t • diu. By the induc-
tion hypothesis, there exist u′
1 and u′
2 satisfying diu1
·∆t1 ≡+ ∆t · diu′
1
and diu2
·∆t′ ≡
+ ∆t1 ·diu′
2
. We thus deduce diu ·∆t′ ≡
+
diu1
·∆t1 ·diu′
2
≡+
∆t · diu′
1
· diu′
2
.
The following definition encodes iterative usage of the ∂ operation in
the obvious way that k∆t sends t to ∂kt.
Definition. For each term t, we put 0∆LDI
t = ε and k∆LDI
t = ∆LDI
t · ∆LDI
∂LDIt
·
· · · · ∆LDI
∂k−1
LDI t
for k ≥ 1. The word k∆LDLI
t is defined analogously.
Lemma 4.8. Let u be a positive word of length at most k and let t be
a term from the domain of diu. Then there exists a positive word v′
satisfying diu · div′ ≡+ k∆t.
Proof. We use the induction on k. For k = 0, the result is trivial. Other-
wise, we write u = u0 ·α with α an address. By the induction hypothesis,
there exists a positive word v′0 satisfying diu0
· div′
0
≡+ k−1∆t. Let t′ be
the image of t by diu0
. By the hypothesis, the term t′ belongs to the
domain of diα and therefore, according to Proposition 4.5, there exists
a positive word v satisfying diα · div ≡+ ∆t′ . Applicating Lemma 4.7 on
the terms t′ and ∂k−1t, we see that there exists a positive word v′′0 that
satisfies div′
0
· ∆∂k−1t ≡
+ ∆t′ · div′′
0
. We then deduce
diu · div · div′′
0
= diu0
· diα · div · div′′
0
≡+
diu0
· ∆t′ · div′′
0
≡+
≡+
diu0
· div′
0
· ∆∂k−1t ≡
+ k−1∆t · ∆∂k−1t = k∆t.
Hence we obtain the result putting v′ = v · v′′0 .
Proposition 4.9. Let u, v be two positive words of the length at most k.
Then there exist positive words u′, v′ satisfying
diu · div′ ≡+
div · diu′ ≡+ k∆tLu,v
.
Proof. The intersection of the domains of the operators diu and div con-
tains the term tLu,v, due to Proposition 1.7. According to Lemma 4.8,
there exist two positive words u′ and v′ such that diu · div′ and div · diu′
are ≡+-equivalent to k∆tLu,v
.
We have just proved that all pairs of elements have common right
multiples and we have proved it at once for the ≡+
LDI
and ≡+
LDLI
relations
as well as for the positive geometry monoids G+
LDI
and G+
LDLI
.
30 Geometry monoid of LDLI
5. Syntactical monoid
In this section we study the monoid generated by the LDLI-relations using
the method of complemented presentations, described in [7]. This method
gives an algorithm for resolving the word problem of this monoid and it
enables us to say that the monoid is left cancellative and that the left
divisibility order forms a lattice. We are not interested in LDI-relations
because there are too many of them and the corresponding monoid seems
to be less useful than the monoid of LDLI.
Definition. [4] Let A be an alphabet. We say that f is a complement
on A if f is a partial mapping from A × A to A∗ satisfying f(x, x) = ε,
for each x in A, and that f(x, y) exists if f(y, x) exists. We denote by ≡+
f
the relation generated by the relations (xf(x, y), yf(y, x)) with (x, y) in
the domain of f . The monoid associated on the right is the monoid A∗
factored by ≡+
f .
Let us define the syntactical monoid of LDLI MLDLI as the monoid
(ALDLI)
∗ factored by the LDLI-relations. It is not immediate to see but
after a closer look we observe that the monoid MLDLI is associated to a
right complement: we have
f(dα, diβ) =
ε for diα = diβ ,
diβ for β ⊥ α or α11 ⊑ β or (β ⊏ α and α 6= β1),
iβ for diβ = iβ and (α = β or α = β1),
diα10γ · diα00γ for β = α0γ,
diα01γ for β = α10γ and diβ 6= iα10,
iα0 for diβ = iα10,
dβ · dα for β = α1,
dβ · dα · dβ0 for α = β1,
f(iα, diβ) =
ε for diα = diβ ,
diβ for β ⊥ α or (β ⊏ α and (α 6= β10 or β ∈ ALI)),
diα0γ · diα1γ for β = αγ and diα 6= diβ ,
dβ · dβ0 for α = β10 and β ∈ ALD.
The LDI-relations do not give a complement because there is, e.g., the
relation i∅ · i∅ ≡+
LDI
i∅ · i0 · i1.
The complemented presentations permit the usage of a combinatorial
method called the word reversing. The reversing consists of iteratively
replacing a subword x−1 · y by the subword f(x, y) · f(y, x)−1.
P. Jedlička 31
Definition. [7] Let w, w′ be two words. We say that w is reversed to the
right into w′, denoted by w y w′, if there exists a sequence of words w =
w1, . . . , wk = w′ satisfying, for each i < k,
wi = w′
i · x
−1
i · yi · w
′′
i and wi+1 = w′
i · f(xi, yi) · f(yi, xi)
−1 · w′′
i
where xi and yi are letters.
We see that w y w′ implies w ≡f w′. Hence we can possibly obtain
by the reversing a word equivalent to w which is a product of a positive
word and a negative word. A priori, the reversing needs not to be a
deterministic process, at each step we can reverse arbitrary pair of let-
ters x−1y. Though, the process is confluent and if we reach a word vu−1,
then it is unique.
Proposition 5.1. [4] Each word w can be reversed into at most one word
of the form v · u−1 with u and v positive words.
Definition. [4] Let u and v be two positive words. We define u\v as
the unique word u′ such that v−1u is reversed into v′u′−1 with u′ and v′
positive, if such a word exists.
We can see particularly that we have x\y = f(x, y) for all x, y in A.
Remark also a “symmetry” of the definition: a word v−1u is reversed
always into (v\u)(u\v)−1.
If there is u\v = v\u = ε, then we have u ≡+
f v. We would like
this implication to be an equivalence, that means, we would like to have
u ≡+
f v if and only if u−1v y ε.
Definition. [7] We say that a complement f on an alphabet A is right
homogeneous if there exists a mapping λ : A∗ → N satisfying
λ(xv) > λ(v) and λ(u) = λ(v)
for all x in A and u ≡+
f v positive words.
Proposition 5.2. [7] Let M be a monoid associated with a right homo-
geneous right complement f : A × A → A∗. Then the relation u ≡+
f v
implies u−1v y ε if and only if the following condition is satisfied for
all x, y, z in A:
((x\y) \ (x\z)) \ ((y\x) \ (y\z)) = ε (⋆)
We want to show that the monoid MLDLI satisfies the conditions of
Proposition 5.2. We start with the homogeneity of the complement f .
32 Geometry monoid of LDLI
Lemma 5.3. The complement f of the monoid MLDLI is right homoge-
neous.
Proof. We define, for each positive word u,
λ(diu) = lg(tRu ) − lg(tLu ),
where the length of a term is the number of all addresses in its skeleton.
Since diu ≡+
LDLI
div implies diu = div, we have tLu = tLv and tRu = tRv and
also λ(diu) = λ(div). By definition, we have tRα·u = tLα·u • α • u, hence
there exists a substitution h satisfying tLα·u • α = (tLu )h and tRα·u = (tRu )h.
We deduce
λ(diα · diu) = lg(tRα·u) − lg(tLα·u)
= lg(tRα·u) − lg(tLα·u • α) + lg(tLα·u • α) − lg(tLα·u)
= lg((tRu )h) − lg((tLu )h) + lg(tLα·u • α) − lg(tLα·u)
> lg((tRu )h) − lg((tLu )h) ≥ lg(tRu ) − lg(tLu ) = λ(diu).
Hence f is right homogeneous.
Now we want to prove the condition (⋆). We need an auxiliary lemma.
We write diu =⊥
div for two positive words u and v if the word v is
obtained from u using only replacements of a subword α1 · α2 by a sub-
word α2 · α1 with α1 ⊥ α2.
Lemma 5.4. Let diu, div and diw be words on ALDLI. Then
(i) diu \(div · diw) = diu \ div · (div \ diu)\ diw,
(ii) (diu · div)\ diw = div \(diu \ diw),
(iii) diu =⊥
div implies diu \ div = div \ diu = ε.
Proof. (i) Denote di
−1
v · diu y div′ · di
−1
u′ and di
−1
w · div′ y diw′ · di
−1
v′′
Then
di
−1
w · di
−1
v · diu y di
−1
w · div′ · di
−1
u′ y diw′ · di
−1
v′′ · di
−1
u′ .
(ii) Denote di
−1
w · diu y diw′ · di
−1
u′ and di
−1
u′ · div y diu′′ · di
−1
v′ . Then
di
−1
w · diu · div y diw′ · di
−1
u′ · div y diw′ · diu′ · di
−1
v′ .
(iii) For u = ε the result is trivial. Suppose u = α · u0. The word v is of
the form v0 · α · v1, where each address of v0 is orthogonal to α. Now we
have
di
−1
u · div y di
−1
u0
· div0
· di
−1
α · diα · div1
y di
−1
u0
· div0
· div1
y ε
by the induction hypothesis because diu0
=⊥
div0
· div1
.
P. Jedlička 33
Proposition 5.5. The complement f of the monoid MLDLI satisfies the
condition (⋆).
Proof. We consider all the triples diα, diβ , diγ from ALDLI. Since the
LDLI-relations are closed under shifts, we can consider that the greatest
common prefix of α, β and γ is the address ∅ or the address 0.
Case 1. Two elements are equal. Suppose diα = diβ . One has
(diα \ diβ)\(diα \ diγ) = ε\(diα \ diγ) = diα \ diγ ,
(diβ \ diα)\(diβ \ diγ) = ε\(diβ \ diγ) = diβ \ diγ ;
(diβ \ diγ)\(diβ \ diα) = (diβ \ diγ)\ε = ε,
(diγ \ diβ)\(diγ \ diα) = (diγ \ diα)\(diγ \ diα) = ε;
and this suffices because α and β play a symmetrical role.
Case 2. An address is orthogonal to the greatest common prefix of the
other two addresses. Suppose that γ is orthogonal to the greatest common
prefix of α and β. In this case, γ is also orthogonal to each address in
the words diα \ diβ and diβ \ diα. One has
(diα \ diβ)\(diα \ diγ) = (diα \ diβ)\ diγ = diγ ,
(diβ \ diα)\(diβ \ diγ) = (diβ \ diα)\ diγ = diγ ;
(diβ \ diγ)\(diβ \ diα) = diγ \(diβ \ diα) = (diβ \ diα),
(diβ \ diγ)\(diβ \ diα) = diγ \(diβ \ diα) = (diβ \ diα);
and this suffices because α and β play a symmetrical role.
Case 3. One of the elements is i0 and 0 is the greatest common prefix of
all addresses. Suppose diγ = i0. We can suppose that the other addresses
are different from i0, otherwise we are in the case 1. We write β = 0β0
and γ = 0γ0. One has
(diα \ diβ)\(diα \ diγ) = (di0α0
\ di0β0
)\ i0 = i0,
(diβ \ diα)\(diβ \ diγ) = (di0β0
\ di0α0
)\ i0 = i0;
(diβ \ diγ)\(diβ \ diα) = i0 \(di0β0
\ di0α0
)
=⊥ (di00β0
\ di00α0
) · (di01β0
\ di01α0
),
(diγ \ diβ)\(diγ \ diα) = (di00β0
· di01β0
)\(di00α0
· di01α0
)
= (di00β0
\ di00α0
) · (di01β0
\ di01α0
);
Case 4. An address is a proper prefix of the greatest common prefix of
the other two addresses. We suppose that γ is a prefix of the greatest
common prefix γ′ of α and β. We can suppose diγ = d∅, otherwise we
are in the case 3.
34 Geometry monoid of LDLI
Case 4.1. The address 0 is a prefix of α and of β. We write α = 0α0
and β = 0β0. One has
(diα \ diβ)\(diα \ diγ) = sh0(diα0
\ diβ0
)\ d∅ = d∅,
(diβ \ diα)\(diβ \ diγ) = sh0(diα0
\ diβ0
)\ d∅ = d∅;
(diβ \ diγ)\(diβ \ diα) = d∅ \ sh0(diβ0
\ diα0
)
=⊥ sh10(diβ0
\ diα0
) · sh00(diβ0
\ diα0
),
(diγ \ diβ)\(diγ \ diα) = (di10β0
· di00β0
)\(di10α0
· di00α0
)
= sh10(diβ0
\ diα0
) · sh00(diβ0
\ diα0
);
and this suffices because α and β play a symmetrical role.
Case 4.2. The address 1 is a proper prefix of a common prefix of α
and β.
Case 4.2.1. One of the elements is i10. We suppose diβ = i10 and
diα = di10α0
6= i10.
(diα \ diβ)\(diα \ diγ) = i10 \ d∅ = d∅ · d0,
(diβ \ diα)\(diβ \ diγ) = (di100α0
· di101α0
)\(d∅ · d0)
= d∅ ·((di010α0
· di011α0
)\ d0) = d∅ · d0;
(diβ \ diγ)\(diβ \ diα) = (d∅ · d0)\(di100α0
· di101α0
)
= d0 \(di010α0
· di011α0
) = di001α0
· di011α0
,
(diγ \ diβ)\(diγ \ diα) = i0 \ di01α0
= di001α0
· di011α0
;
(diγ \ diα)\(diγ \ diβ) = di01α0
\ i0 = i0,
(diα \ diγ)\(diα \ diβ) = d∅ \ i10 = i0 .
Case 4.2.2. None of the elements is i10. We write α = 1eα0 and β =
1eβ0 with e = 0 or e = 1. One has
(diα \ diβ)\(diα \ diγ) = sh1e(diα0
\ diβ0
)\ d∅ = d∅,
(diβ \ diα)\(diβ \ diγ) = sh1e(diβ0
\ diα0
)\ d∅ = d∅;
(diβ \ diγ)\(diβ \ diα) = d∅ \ sh1e(diβ0
\ diα0
) = she1(diβ0
\ diα0
),
(diγ \ diβ)\(diγ \ diα) = die1β0
\ die1α0
= she1(diβ0
\ diα0
);
and this suffices because α and β play a symmetrical role.
Case 4.3. The address 1 is the greatest common prefix of α and β.
Case 4.3.1. The addresses α and β are orthogonal.
Case 4.3.1.1 One of the elements is i10. We suppose diβ = i10
and α = 11α0. One has
(diα \ diβ)\(diα \ diγ) = i10 \ d∅ = d∅ · d0,
(diβ \ diα)\(diβ \ diγ) = di11α0
\(d∅ · d0) = d∅ · d0;
P. Jedlička 35
(diβ \ diγ)\(diβ \ diα) = (d∅ · d0)\ di11α0
= di11α0
,
(diγ \ diβ)\(diγ \ diα) = i0 \ di11α0
= di11α0
;
(diγ \ diα)\(diγ \ diβ) = di11α0
\ i0 = i0,
(diα \ diγ)\(diα \ diβ) = d∅ \ i10 = i0 .
Case 4.3.1.2 None of the elements is i10. We suppose β = 10β0
and α = 11α0.
(diα \ diβ)\(diα \ diγ) = di10β0
\ d∅ = d∅,
(diβ \ diα)\(diβ \ diγ) = di11α0
\ d∅ = d∅;
(diβ \ diγ)\(diβ \ diα) = d∅ \ di11α0
= di11α0
,
(diγ \ diβ)\(diγ \ diα) = di10β1
\ di11α0
= di11α0
;
(diγ \ diα)\(diγ \ diβ) = di11α0
\ di10β0
= di10β0
,
(diα \ diγ)\(diα \ diβ) = d∅ \ di10β0
= di10β0
.
Case 4.3.2. The addresses α and β are comparable. We can suppose
that β is a proper prefix of α, hence diβ = d1. (The element i1 does not
belong to MLDLI.)
Case 4.3.2.1 The address 10 is a prefix of α.
Case 4.3.2.1.1. The element diα is i10. One has
(diα \ diβ)\(diα \ diγ) = d1 \(d∅ · d0) = d∅ · d1 · d0 ·((d1 · d∅)\ d0)
= d∅ · d1 · d0 ·(d∅ \ d0) = d∅ · d1 · d0 · d10 · d00,
(diβ \ diα)\(diβ \ diγ) = (i100 · i110)\(d∅ · d1 · d0)
= d∅ ·((i010 · i110)\(d1 · d0)) = d∅ · d1 · d10 · d0 · d00;
(diβ \ diγ)\(diβ \ diα) = (d∅ · d1 · d0)\(i100 · i110) = (d1 · d0)\(i010 · i110)
= i00 · i10,
(diγ \ diβ)\(diγ \ diα) = (d1 · d∅)\ i0 = d∅ \ i0 = i10 · i00;
(diγ \ diα)\(diγ \ diβ) = i0 \(d1 · d∅) = d1 · d∅,
(diα \ diγ)\(diα \ diβ) = (d∅ · d0)\ d1 = d0 \(d1 · d∅) = d1 · d∅ .
Case 4.3.2.1.2. The element diα is not i10. We write α = 10α0.
One has
(diα \ diβ)\(diα \ diγ) = d1 \ d∅ = d∅ · d1 · d0,
(diβ \ diα)\(diβ \ diγ) = (di110α0
· di100α0
)\(d1 \ d∅ = d∅ · d1 · d0)
= d1 \ d∅ = d∅ · d1 · d0;
36 Geometry monoid of LDLI
(diβ \ diγ)\(diβ \ diα) = (d∅ · d1 · d0)\(di110α0
· di100α0
)
= (d1 · d0)\(di110α0
· di010α0
) = di101α0
· di001α0
,
(diγ \ diβ)\(diγ \ diα) = (d1 · d∅)\ di01α0
= d∅ \ di01α0
= di101α0
· di001α0
;
(diγ \ diα)\(diγ \ diβ) = di01α0
\(d1 · d∅) = d1 · d∅,
(diα \ diγ)\(diα \ diβ) = d∅ \ d1 = d1 · d∅;
Case 4.3.2.2 The address 11 is a proper prefix of α.
Case 4.3.2.2.1. The element diα is i110. One has
(diα \ diβ)\(diα \ diγ) = (d1 · d10)\ d∅ = d10 \(d∅ · d1 · d0)
= d∅ ·(d01 \(d1 · d0)) = d∅ · d1 · d0 · d01 · d00,
(diβ \ diα)\(diβ \ diγ) = i10 \(d∅ · d1 · d0)
= d∅ · d0 ·(i0 \(d1 · d0)) = d∅ · d0 · d1 · d00 · d01;
(diβ \ diγ)\(diβ \ diα) = (d∅ · d1 · d0)\ i10 = i0,
(diγ \ diβ)\(diγ \ diα) = (d1 · d∅)\ i110 = d∅ \ i10 = i0;
(diγ \ diα)\(diγ \ diβ) = i110 \(d1 · d∅) = d1 · d10 ·(i10 \ d∅)
= d1 · d10 · d∅ · d0,
(diα \ diγ)\(diα \ diβ) = d∅ \(d1 · d10) = d1 · d∅ ·((d∅ · d1 · d0)\ d10)
= d1 · d∅ ·((d1 · d0)\ d01) = d1 · d∅ · d01 · d0;
and one finds
d
−1
0 · d−1
∅
· d−1
10 · d−1
1 · d1 · d∅ · d01 · d0 y d
−1
0 · d−1
∅
· d−1
10 · d∅ · d01 · d0
y d
−1
0 · d−1
∅
· d∅ · d−1
01 · d01 · d0 y d
−1
0 · d0 y ε.
Case 4.3.2.1.2. The element diα is not i110. We write α =
11eα0. One has
(diα \ diβ)\(diα \ diγ) = d1 \ d∅ = d∅ · d1 · d0,
(diβ \ diα)\(diβ \ diγ) = di1e1α0
\(d∅ · d1 · d0 = d∅ · d1 · d0;
(diβ \ diγ)\(diβ \ diα) = (d∅ · d1 · d0)\ di1e1α0
= (d1 · d0)\ die11α0
= die11α0
,
(diγ \ diβ)\(diγ \ diα) = (d1 · d∅)\ di11eα0
= d∅ \ di1e1α0
= die11α0
;
(diα \ diγ)\(diα \ diβ) = di11eα0
\(d1 · d∅) = d1 · d∅,
(diα \ diγ)\(diα \ diβ) = d∅ \ d1 = d1 · d∅ .
P. Jedlička 37
Case 4.3.2.3 The address α is 11. This is the most complicated
one but we do not need to consider it here because all these three ad-
dresses belong to ALD and this one is shown in [4].
Case 5. The address ∅ is the greatest common prefix of α and β. We
can suppose α ⊥ β, otherwise we are in the case 1. We write α = 0α0.
Case 5.1. The address 1 is a proper prefix of β.
Case 5.1.1. The element diβ is i10. One has
(diα \ diβ)\(diα \ diγ) = i10 \ d∅ = d∅ · d0,
(diβ \ diα)\(diβ \ diγ) = di0α0
\(d∅ · d0) = d∅ · d0;
(diβ \ diγ)\(diβ \ diα) = (d∅ · d0)\ di0α0
= d0 \(di10α0
· di00α0
)
= di10α0
· di010α0
· di000α0
,
(diβ \ diγ)\(diβ \ diα) = i0 \(di10α0
· di00α0
) = di00α0
· di000α0
· di010α0
;
(diα \ diγ)\(diα \ diβ) = (di10α0
· di00α0
)\ i0 = i0,
(diα \ diγ)\(diα \ diβ) = d∅ \ i10 = i0 .
Case 5.1.2. The element diβ is not i10. We write β = 1eβ0 and we
have
(diα \ diβ)\(diα \ diγ) = di1eβ0
\ d∅ = d∅,
(diβ \ diα)\(diβ \ diγ) = di0α0
\ d∅ = d∅;
(diβ \ diγ)\(diβ \ diα) = d∅ \ di0α0
= di10α0
· di00α0
,
(diβ \ diγ)\(diβ \ diα) = die1β0
\(di10α0
· di00α0
) = di10α0
· di00α0
;
(diα \ diγ)\(diα \ diβ) = (di10α0
· di00α0
)\ die1β0
= die1β0
,
(diα \ diγ)\(diα \ diβ) = d∅ \ di1eβ0
= di1eβ0
.
Case 5.2. The address β is equal to 1. We find
(diα \ diβ)\(diα \ diγ) = d1 \ d∅ = d∅ · d· d0,
(diβ \ diα)\(diβ \ diγ) = di0α0
\(d∅ · d· d0) = d∅ · d· d0;
(diβ \ diγ)\(diβ \ diα) = (d∅ · d1 · d0)\ di0α0
= (d1 · d0)\(di10α0
· di00α0
)
= di110α0
· di100α0
· di010α0
· di000α0
,
(diβ \ diγ)\(diβ \ diα) = (d1 · d∅)\(di10α0
· di00α0
)
= di110α0
· di010α0
· di100α0
· di000α0
;
(diα \ diγ)\(diα \ diβ) = (di10α0
· di00α0
)\(d1 · d∅) = d1 · d∅,
(diα \ diγ)\(diα \ diβ) = d∅ \ d1 = d1 · d∅ .
38 Geometry monoid of LDLI
Case 6. The greatest common prefix of two addresses is a prefix of the
third one. Suppose that the greatest prefix γ′ of α and β is a prefix of γ.
If we have β = γ′ or γ = γ′, then we are in the case 4 or in the case 5.
If α and β are orthogonal, then we are in the case 1. We have considered
all the cases and the proof is finished.
We deduce from Proposition 5.2:
Proposition 5.6. : The word problem of MLDLI is solvable.
Each monoid satisfying the conditions of Proposition 5.2 has some
good properties:
Proposition 5.7. The monoid MLDLI is left cancellative and the left di-
visibility order on MLDLI forms a lattice.
Proof. It is shown in [4] that each monoid satisfying the conditions of
Proposition 5.2 is left cancellative, each two elements have a unique
greatest common left divisor and each two elements having a common
right multiple have also the least one. According to Proposition 4.9, each
pair of elements in MLDLI has a common right multiple and hence the left
divisibility order on MLDLI forms a lattice.
Remark 5.8. The canonical projection MLDLI ։ G+
LDLI
is not injective. We
have i0 · i00 · i0 6≡+
LDLI
i0 · i0 · d0, because MLDLI is left cancellative and i00 •
i0 6= i0 • d0: the operator i00 • i0 sends (x·y)·z onto (((x·x)·y)·((x·x)·y))·z
and the operator i0 • d0 sends (x · y) · z onto (((x · y) · x) · ((x · y) · y)) · z.
However, we have
i0 · i00 · i0 ≡+
LDI
i0 · i0 · i000 · i010 ≡+
LDI
i0 · i01 · d0 · i000 · i010 ≡+
LDI
≡+
LDI
i0 · i01 · i00 · d0 ≡+
LDI
i0 · i0 · d0
and hence also the equality i0 • i00 • i0 = i0 • i0 • d0.
The solution of the word problem of the LD identity actually uses
the geometry group, not the geometry monoid nor the positive geometry
monoid. The geometry group is obtained as the fraction group of the
positive geometry monoid. In the cases of LDI and LDLI the positive
geometry monoids are not cancellative and it is unlikely that their group
of fractions could describe the identities well. Nevertheless, the monoid
MLDLI is (at least left) cancellative and it has all the important properties
of the positive geometry monoid of LDLI. Hence it might be possible to
attack the word problem from this direction.
P. Jedlička 39
References
[1] S.N. Burris, H. P. Sankappanavar: “A Course in Universal Algebra”, Grad.
texts in Math., Springer-Verlag, 1981
[2] J.W. Cannon, W. J. Floyd, W.R. Parry: Introductory Notes to Richard
Thompson’s Groups, L’Enseignement Mathématique 42, 1996, 215–256
[3] P. Dehornoy: The structure group for the associativity identity, J. of Pure and
Appl. Algebra 111, 1996, 59–82
[4] P. Dehornoy: “Braids and Self-Distributivity”; Prog. in Math. 192; Birkhäuser,
2000
[5] P. Dehornoy: The fine structure of LD-equivalence, Adv. in Math., 155, 2000,
264–316
[6] P. Dehornoy: Study of an identity, Alg. Univ. 48, 2002, 223–248
[7] P. Dehornoy: Complete positive group presentation, J. of Alg. 268, 2003, 156–
197
[8] P. Dehornoy: Geometric presentations for Thompson’s groups, J. Pure Appl.
Alg., 203, 2005, 1–44
[9] P. Jedlička: On Left Distributive Left Idempotent Groupoids, Comment. Math.
Univ. Carol. 46,1, 2005, 15–20
[10] P. Jedlička: “Treillis, groupes de Coxeter et les systèmes LDI” (french and
czech), Ph.D. thesis, University of Caen, 2004, Caen
[11] T. Kepka: Notes On Left Distributive Groupoids, Acta Univ. Carolinae – Math.
et Phys. 22.2, 1981, 23–37
[12] T. Kepka, Non-idempotent left symmetric left distributive groupoids, Commen-
tat. Math. Univ. Carol. 35.1, 1994, 181–186
[13] T. Kepka, P. Němec: Selfdistributive Groupoids Part A1: Non-Idempotent Left
Distributive Groupoids, Acta Univ. Carolinae – Math. et Phys. 44.1, 2003, 3–94
[14] D. Larue: Left-Distributive Idempotent Algebras, Commun. Alg. 27/5, 1999,
2003–2009
Contact information
P. Jedlička Czech University of Agriculture
Faculty of Engineering
Department of Mathematics
Kamýcká 129
165 21, Prague 6 – Suchdol
Czech Republic
E-Mail: jedlickap@tf.czu.cz
URL: http://tf.czu.cz/~jedlickap
Received by the editors: 26.02.2007
and in final form 12.04.2007.
|