at each step, is to
compute 
by using integer arithmetic. Let M be the companion matrix to 
, so
that the eigenvalues of M are the conjugates of 
. If 
, as above, is
such that 
, then the eigenvalues of 
are the conjugates
of 
and the eigenvalues of 
are the conjugates of 
.
Now, 
has exactly two real conjugates corresponding to the two
conjugates 
and 
of 
. Since 
for all k,
it is easy to see that the conjugate of 
corresponding to 
is 
. Let us denote this
conjugate by 
. For 
, 
has two real
conjugates 
and 
itself. By definition, 
. Since all other conjugates are nonreal, the sign of
the product of all conjugates is determined by that of 
, and thus
which is a compuation involving only
finding the determinant of a finite number of matrices with integer entries.
Note that the matrix 
is as good a representation of 
as is 
and can be computed from the recursion 
without explicitly
computing the coefficients of 
. Of course, 
has 
integer entries
rather than the d entries of the coefficient vector of 
.
Since the determinant computed above is just the resultant of 
and 
,
another alternative is to use the coefficient vector of 
to represent
and replace the determinant computation by the computation of a resultant at
each step. Or, combining the approaches of § 5.1 and § 5.2, one could compute 
using floating point except in ``delicate'' cases.
Experiments showed that the approach of § 5.2 was generally considerably slower than
that of § 5.1.
![[Annotate]](/organics/icons/sannotate.gif){kind=icon}
![[Shownotes]](../gif/annotate/sshow-71.gif)