Information Technology Reference
In-Depth Information
δ
D
∗
is a differential for the underlying graded group of
D
.Aperturbation
δ
D
∗
of
d
D
∗
satisfies the
nilpotency condition
with respect to a reduction
(
f, g, h
):
D
∗
∗
⇒
whenever the composition
δ
D
∗
h
is pointwise nilpotent, that is,
(
δ
D
∗
h
)
n
(
x
)=0
for an
n
C
∗
∈
N
depending on each
x
in
D
.
∗
Under certain conditions, reductions can be “perturbed” to obtain new reduc-
tions easier to work with. This is expressed in the BPL.
Theorem 1. Basic Perturbation Lemma
-Let
(
f, g, h
):
D
∗
⇒
C
be a
∗
chain complex reduction and
δ
D
∗
:
D
a
perturbation
of the differential
d
D
∗
satisfying the nilpotency condition with respect to the reduction
(
f, g, h
)
.
Then, a new reduction
(
f
,g
,h
):
D
∗
→
D
∗
C
∗
⇒
can be obtained where the underlying
∗
and
D
and
C
graded groups of
D
(resp.
C
) are the same, but the differentials
∗
∗
∗
∗
=
d
C
∗
+
δ
C
∗
,and
δ
C
∗
=
fφδ
D
∗
g
;
f
=
fφ
;
are perturbed:
d
D
∗
=
d
D
∗
+
δ
D
∗
,d
C
∗
)
g
;
h
=
hφ
,where
φ
=
i
=0
(
g
=(1
1)
i
(
δ
D
∗
h
)
i
.
−
hφδ
D
∗
−
The BPL is a key result in algorithmic homological algebra (in particular, it
is crucial for EAT [15] and Kenzo [5]). It ensures that when a perturbation
is discarded (usually in chain complexes of infinite nature), a new reduction
between chain complexes can be algorithmically obtained and thus the process
to obtain a chain complex with computable homology can be implemented in a
symbolic computation system. The BPL first appeared in [16] and was rewritten
in modern terms in [3]. Since then, plenty of proofs have been described in
the literature (see, for instance, [7, 14]). We are interested in a proof due to
Sergeraert [14]. This proof is divided into two parts:
Part 1.
Let
ψ
be
i
=0
(
1)
i
(
hδ
D
∗
)
i
. From the BPL hypothesis, the following
equalities are proved:
ψh
=
hφ
;
δ
D
∗
ψ
=
φδ
D
∗
;
ψ
=1
−
−
hδ
D
∗
ψ
=1
−
ψhδ
D
∗
=
1
δ
D
∗
ψh
.
Part 2.
With these equalities, it is possible to give a collection of lemmas pro-
viding the new reduction between the chain complexes (and therefore producing
the algorithm associated to the BPL).
In the rest of the paper, we focus on the second part. The collection of
lemmas will be now presented, and later the sketch of a proof, which combines
these lemmas, will be given. The sketch of the proof shows the constructive
nature of the proof, which would permit us to obtain an algorithm from it. In
the following sections we will explain the different attempts we have studied to
implement the proofs of these lemmas.
−
hφδ
D
∗
;
φ
=1
−
δ
D
∗
hφ
=1
−
φδ
D
∗
h
=1
−
Lemma 1.
Let
(
f, g, h
):
D
be a chain complex reduction. There exists
a canonical and explicit chain complex isomorphism between
D
∗
⇒
C
∗
and the direct
∗
and
F
−
1
:
C
sum
ker(
gf
)
im(
gf
)
,
defined by
F
(
x
)=
f
(
x
)
and
F
−
1
(
x
)=
g
(
x
)
, are inverse isomorphisms of chain
complexes and
im(
gf
)=ker(
id
D
∗
−
⊕
C
.Inparticular,
F
:im(
gf
)
→
C
∗
→
∗
∗
gf
)
.
Let
us
denote
by
inc
ker(
p
)
the
canonical
inclusion
homomorphism
inc
ker(
p
)
:ker(
p
)
→
D
given by
x
→
x
,with
p
=
d
D
∗
h
+
hd
D
∗
.Itiswell
∗
defined since ker(
p
)isachainsubcomplexof
D
.
∗
Search WWH ::
Custom Search