Information Technology Reference
In-Depth Information
Proof.
Due to space constraints, we only prove the forward direction of the
theorem. The other direction is straightforward and can be proved by reversing
the argument used for the forward case.
Consider any sequence
,
2
n
S
i,j,k,l
∈A
(
L
)
,
where
i, j, k, l
∈{
0
,
···
−
1
}
.
(10)
We assume
i
,
j
,
k
,and
l
are all different as two symbol changes are already
covered by Lemma 5. From equation (7) we have
w
H
(2
n
3and
L
=2
n
(2
n−r
1
+2
n−r
2
−
1
+
c
)
,
−
L
)
≥
−
(11)
for some 0
<c<
2
n−r
2
−
1
. From equations (5), (6), and (11), we have
ψ
r
1
−
1
L
(
S
)=
ψ
r
1
−
1
R
(
S
)and
ψ
r
L
(
S
)=
ψ
r
R
(
S
)
.
∀
S
∈A
(
L
)
,
(12)
By
P
i,j,k,l
denote the set of all permutations of
i
,
j
,
k
,and
l
.Wefirstassume
∃
(
a, b, c, d
)
∈P
i,j,k,l
:
L
(
S
a,b
)=
L
(
S
c,d
)=
L
(
S
)
.
(13)
From equation (7) we have
2
n
2
n−r
1
+1
<L<
2
n
2
n−r
1
.
−
−
(14)
From our assumption in equation (13), by Lemma 5 and equation (14), ignoring
order,
i
,
j
,
k
,and
l
must be in the first form as in equation (8).
If equation (13) does not hold, then from equation (10) and Lemma 5 we have
∀
(
a, b, c, d
)
∈P
i,j,k,l
:
L
(
S
a,b
)
>L
(
S
)and
L
(
S
c,d
)
>L
(
S
)
.
(15)
Equation (15) implies
b
mod 2
n−r
1
+1
.
∀
a, b
∈{
i, j, k, l
}
,
a
≡
(16)
Equation (16) implies that the integers
i
mod 2
n−r
1
+1
,
j
mod 2
n−r
1
+1
,
k
mod
2
n−r
1
+1
,and
l
mod 2
n−r
1
+1
are all different. Also, by Lemma 6 and equation
(11) the left and right halves are not equal during the first
r
1
−
2 steps of the
Games-Chan procedure for any
S
∈A
(
L
). Thus, by the procedure of the Games-
Chan algorithm and equation (16) we get
d
H
(
ψ
r
1
−
1
(
S
)
,ψ
r
1
−
1
(
S
i,j,k,l
)) = 4
.
(17)
By equations (12) and (17), the four positions where the vectors
ψ
r
1
−
1
(
S
),
ψ
r
1
−
1
(
S
i,j,k,l
)differareoftheform
1
+2
n−r
1
,
c
2
+2
n−r
1
,
c
1
,
2
,
and
(18)
2
n−r
1
for some 0
≤
c
1
<c
2
≤
−
1. From equations (12) and (17), we have
d
H
(
ψ
r
1
−
1
L
(
S
)
,ψ
r
1
−
1
L
(
S
i,j,k,l
)) = 2. This implies
d
H
(
ψ
r
1
(
S
)
,ψ
r
1
(
S
i,j,k,l
)) = 2
.
(19)
