Information Technology Reference
In-Depth Information
It will be convenient to identify the vector of distances
d
with a binary se-
quence
b
of length
v
which is zero except on
δ
.Then
S
i
=
{
i
−
d
:
b
d
=1
}
.
We may also treat
b
as an infinite sequence with
b
j
=0for
j
outside of the
interval [0
,v
1]. We say that difference
d
is “realized (at
j
)” if
b
j
=1
,b
j
+
d
=0
and call the ordered pair (
j, j
+
d
) a “realization of
d
”. We define
−
Definition 2
μ
b
(
d
)=#
{
i
|
b
i
=1
,b
i
+
d
=0
}
,
(2)
so
μ
b
(
d
)isthenumberoftimes
d
is realized in
b
(we may drop the subscript
b
when the context is clear). We then define the strength of the vector
b
as
μ
(
b
)=min
d
μ
b
(
d
)
,
(3)
consistent with the definition given above for
μ
(
S
). Then
b
is a
t
-
distance avoiding
sequence
if
μ
(
b
)
t
.
We can assume with no loss of generality that
b
0
=
b
v−
1
= 1. Changing
b
0
from zero to one does not destroy any realizations of any
d
; changing
b
v−
1
from
zero to one creates one new realization of
d
for every
d
, while destroying one
realization of each
d
with
b
v−d−
1
=1.Thus
μ
(
b
) might increase and cannot
decrease.
Note that we do not need to consider differences with absolute value greater
≥
than
v
; for such differences we clearly have
μ
d
=
i
b
i
, which is a trivial upper
bound on all
μ
d
. In fact we can limit our attention to positive differences:
Lemma 1.
For al l
d
,
μ
d
=
μ
−d
.
μ
−d
=
i
(
b
i
−
Proof.
μ
d
−
b
i
+
d
)=0
We can bound the maximum strength of a sequence for a given memory size
v
as follows:
Theorem 1.
For al l
b
of length
v
,
v
+2
3
μ
(
b
)
≤
.
(4)
Proof.
We in fact prove the stronger result that
v
+2
3
min(
μ
1
,μ
2
)
≤
.
(5)
Let
R
s
be the number of runs of
s
∈{
0
,
1
}
of length
. With no loss of generality
we may assume that
2; in a long run of ones or zeros, the third value can be
changed without decreasing
μ
1
or
μ
2
.Thenwehave
≤
v
=
R
1
+
R
1
+2
R
2
+2
R
2
.
(6)
