for 
, and 
for 
. Consider first how one would compute
these quantities using an approximation to the real number 
. If an approximation
to 
is used which has 
, then the error in
the corresponding approximation to 
is about 
. Thus, for
large n it will be impossible to compute 
correctly. In addition, even for small
n, it would be impossible to decide whether or not 
for some 
.
On the other hand, if 
is an algebraic integer, then all 
lie in
. Specifically, if 
has degree d and minimal polynomial P,
and if 
is the polynomial of degree d-1 definied by 
, where 
is as in § 1, then 
. The 
thus
provide an exact representation of 
, so the question 
can
be effectively answered. Since the 
satisfy the recurrence
the computation simply involves a shift
of the coefficients of 
followed by the replacement of 
by 
.
The only difficulty is the determination of 
. This can be computed using an approximation 
to 
of modest
accuracy unless 
is unusually close to an integer c. If 
is a Salem number, standard arguments from transcendence theory show that
where 
denotes
the sum of the absolute values of the coefficients of 
. One simply observes
that there is an obvious bound on the conjugates of 
owing to the fact
that the other conjugates of 
all have absolute value 
, and that the
product of all the conjugates is a nonzero integer.
In practice, we can simply choose an approximation 
to 
of fixed
accuracy 
. (We usually chose 
to be 
or 
.) The number 
is an approximation to
whose accuracy is easily estimated. If 
, and if 
, then
. Thus, if the distance from 
to the nearest
integer is at least 
, then 
.
Our algorithm begins with 
(double precision). If at
some point in the computation, the criterion of the previous paragraph fails, the
computation of 
is repeated with a 
having accuracy 
(quadruple precision). If the criterion fails at this level of accuracy, then
the computation is terminated. This occurred for only five values of 
in our
entire project, one of which can be recognized in
Table 2
: 
is not given, but the
corresponding lower bound on D is 
.
For each 
, the values of n for which a change from double precision to
quadruple precision was necessary were recorded in a file during the computation. We
indicate below how these values were used in some cases to determine some of the larger
values of 
.
As a sample of the accuracy needed, suppose we were to take 
for
the 
with 
. Then for n = 167305 one computes 
, suggesting that 
, while in fact 
, so 
. On the other hand, for most values of n, a far less
accurate value of 
would suffice. The two-tier arrangement described in the
previous paragraph allows one to make use of the fast double-precision multiplication on
the machine used (an Amdahl 5860) while retaining the benefits of a higher-precision
calculation when required. One could easily envision a multiple-tier approach.
The sequence 
is periodic if and only if 
is bounded. Thus,
if 
is a beta number, its expansion can be computed using an approximation
of some fixed accuracy (which depends on 
, of course).
![[Annotate]](/organics/icons/sannotate.gif){kind=icon}
![[Shownotes]](../gif/annotate/sshow-61.gif)