Information Technology Reference
In-Depth Information
The question of when a ring
R
=
Z
[
π
] is a UFD is a delicate one, not fully
understood. First, it is generally necessary to use the integral closure of
R
rather
than
R
. The quadratic fields
Z
[
√
p
] whose integral closures are UFDs are known
for negative
p
, but they are not yet all known for positive
p
. The negative
p
for
which the integral closure of
Z
[
√
p
]isaUFDare
.
The known positive
p
for which the integral closure of
Z
[
√
p
]isaUFDare
{
{−
163
,
−
67
,
−
43
,
−
19
,
−
11
,
−
7
,
−
3
,
−
2
,
−
1
}
2,3,5,6,7,11,13,14,17,19,21,22,23,29,33,37,41,53,57,61,69,73,77,89,93,97
}
.
3Exp ed
π
-Adic Complexity
The function
λ
is extended to states of an AFSR
D
by
λ
(
a
0
,
,a
r−
1
;
m
)=
r
+
λ
(
m
). We extend
λ
to AFSRs by letting
λ
(
D, σ
)denotethemaximumof
λ
(
τ
)overallstates
τ
that occur in the infinite execution of the AFSR starting
with initial state
σ
.Weextend
λ
to sequences by letting
λ
(
a
), the
π
-adic span
of
a
, be the minimum of
λ
(
D, σ
)overall(
D, σ
)with
D
(
σ
)=
a
. Also, let
Γ
n
denote the set of pairs (
D, σ
) such that
D
is an AFSR,
σ
is a state of
D
,and
D
(
σ
)hasperiod
n
.
Now suppose that
a
is a sequence over
S
. Suppose that
···
α
=
∞
r
a
i
π
i
=
u
q
q
i
π
i
and
q
=
−
q
0
,
i
=0
i
=1
where
q
i
∈
S
for
i
=0
,
···
,r
,
D
q
(
σ
)=
a
for some initial state
σ
,and
λ
(
a
)=
λ
(
D
q
,σ
).
Lemma 3.
If
a
is strictly periodic, then
λ
(
a
)
∈
λ
(
q
)+
O
(log(
λ
(
q
))) =
r
+
O
(log(
r
))
.
Thus the size of the carry
m
has little effect on the
π
-adic complexity.
Let
Γ
n
denote the set of pairs (
D, σ
)
Γ
n
for which
λ
(
D, σ
) is minimal among
all pairs (
C, τ
)with
C
(
τ
)=
D
(
σ
). Suppose (
D, σ
)
∈
Γ
n
and
q
D
=
i
=1
q
i
π
i
∈
−
q
0
.
Then
r
q
i
π
i
)+
c
3
λ
(
D
(
σ
))
≥
r
≥
λ
(
i
=1
by S4. Furthermore,
r
r
λ
(
q
D
)=
λ
(
q
i
π
i
q
i
π
i
)
,λ
(
q
0
)) +
c
1
−
q
0
)
≤
max(
λ
(
i
=1
i
=1
r
q
i
π
i
)+max(
λ
(
s
):
s
≤
λ
(
∈
S
)+
c
1
.
i
=1
