Information Technology Reference
In-Depth Information
λ
(
q
D
)
It follows that
λ
(
D
(
σ
))
c
for some constant
c
.
Let
E
n
be the expected
π
-adic complexity of sequences with period
n
.
That is,
≥
−
p
n
a
1
λ
(
a
)=
1
p
n
E
n
=
λ
(
D
(
σ
))
(
D,σ
)
∈Γ
n
⎛
⎞
1
p
n
c
)=
1
p
n
⎝
⎠
−
(
λ
(
q
D
)
λ
(
q
D
)
≥
−
c,
(4)
(
D,σ
)
∈
Γ
n
(
D,σ
)
∈
Γ
n
where the first sum is over all sequences over
S
with period
n
.
There are two notions of minimality that we use for connection elements
of a sequence
a
. A connection element
q
R
is
λ
-minimal if it minimizes
λ
(
q
) over all connection elements of
a
.Itis
R
-minimal if it divides every
other connection element of
a
. The two notions are not equivalent, since we
might have
λ
(
zq
)
<λ
(
q
). However, when
d
=
p
=2,if
q
is
λ
-minimal, then
by Lemma 1 we have
λ
(
zq
)
∈
≥
log
2
(
|
N
(
zq
)
|
)=log
2
(
|
N
(
q
)
|
)+log
2
(
|
N
(
z
)
|
)
≥
1.
Let
μ
(
a
) denote the minimum
λ
(
q
C
)overall
C
that can output
a
.Even
if (
D, σ
)
log
2
(
|
N
(
q
)
|
)
≥
λ
(
q
)
−
Γ
n
and
D
(
σ
)=
a
,wemightnothave
μ
(
a
)=
λ
(
q
D
). However,
∈
λ
(
q
D
)
μ
(
a
). That is, for all
D
we have
λ
(
q
D
)
μ
(
D
(
σ
)). Let
Δ
n
(
q
)denote
the number of period
n
sequences with
q
as a connection element, and let
Δ
n
(
q
)
denote the number of period
n
sequences whose
λ
-minimal connection element
is an associate of
q
.Notethat
≥
≥
Δ
n
(
q
)=
p
n
,
(5)
q
|
∗
π
n
−
1
|
∗
π
n
where
q
−
1meanswechooseone
q
in each set of associates among the
divisors of
π
n
−
1. Gathering terms in equation (4) together, we have
1
p
n
1
p
n
E
n
≥
λ
(
q
)
Δ
n
(
q
)
μ
(
D
(
σ
))
−
c
≥
−
c.
(
D,σ
)
∈Γ
n
q|π
n
−
1
4When
p
=
d
=2
In this section we assume that
p
=
d
=2.Thus
R
is a PID and UFD, so that
the representation in equation (3) is unique (in the usual sense). It follows that,
up to multiplying by a unit, every divisor of
π
n
1isoftheform
w
=
i
=1
z
m
i
−
i
with 0
e
i
. Every period
n
sequence
a
has some such
w
as
R
-minimal
connection element. If
q
is the
λ
-minimal connection element of
a
,then
λ
(
w
)
≤
m
i
≤
≥
λ
(
q
)
−
1.
