Computational algebraic integers
Tim Sweeney
- One can construct a finitary computational model of the integers in
many ways. One way is to represent them as a string of binary digits,
with the classic two's-completement algorithms for binary addition,
subtraction, multiplication, division, and comparison. If the
representation is constrained to have no redundent leading digits,
then the mapping from integers to representations is bijective.
- Given a computational model of the integers, one can construct a
finitary model of the rational numbers, by representing each rational
number as a pair (numerator,denominator). The elementary operations
can be defined in the obvious way, i.e. (a,b)+(c,d)=(a*d+b*c,b*d). If
the representation is constrained to be in lowest terms with positive
denominator, the mapping from rational numbers to representations is
bijective.
Now a few questions:
- Does there exist a finitary computational model of the algebraic
numbers, such that there exists a bijection between mathematical
algebraic numbers and their model, and there exist terminating
algorithms for addition, subtraction, multiplication, division, and
comparison? To clarify "finitary" here, I mean a representation such
that if you start with a finite set of rational numbers and perform a
finite sequence of field operations and polynomial-solving operations
on them, then the result is guaranteed to be representable in finite
space.
- Does there exist a halting algorithm that, for every finite set of
polynomial coefficients (a0+a1*x+a2*x^2+..=0), can determine all of
its solutions in the algebraic numbers in such a representation?
- Any references to computer implementations of the above?
Thanks for any pointers.
ma...@mimosa.csv.warwick.ac.uk
I think the answer to all of the above questions is yes.
The KANT system, which can be accessed through Magma, allows you to
create and compute in algebraic number fields (and also within their
rings of integers).
You have to bear in mind that the roots of an irreducible polynomial,
like x^2 -5 over Q are conjugate under the automorphism group of
the algebraic numbers A, and hence are indistinguishable over A.
A computation within KANT would always take place within a particular
finite extension of Q, which might be constructed as a sequence of
simple extensions.
To do exactly what you are asking for, I think you would need to first
decide on a particular enumeration of the irreducible polynomials over Q.
You would then insist that you were going to always contruct your
finite algebraic extensions of Q by adjoining the roots of these equations
in the order specified. That way, you could perform any calcualtion
involving algebraic numbers in a well-defined manner.
Derek Holt.
Mitch Harris
> decide on a particular enumeration of the irreducible polynomials over Q.
do you have one in mind?
er.. one that is "reasonable" to compute with?
That is you -could- just enumerate tuples of integer coeffs (reasonably
easy) reduce the poly (also reasonable) and throw out ones you've
already seen (-not- reasonable).
Is there a method for enumertaing them similar to enumerating the
rationals via Farey sequences (or the related Stern-Brocot tree)?
--
Mitch Harris
Lehrstuhl fuer Automatentheorie, Fakultaet Informatik
Technische Universitaet Dresden, Deutschland
http://tcs.inf.tu-dresden.de/~harris
ma...@mimosa.csv.warwick.ac.uk
Mitch Harris <har...@tcs.inf.tu-dresden.de> writes:
>ma...@mimosa.csv.warwick.ac.uk wrote:
>
>> decide on a particular enumeration of the irreducible polynomials over Q.
>
>do you have one in mind?
>er.. one that is "reasonable" to compute with?
>That is you -could- just enumerate tuples of integer coeffs (reasonably
>easy) reduce the poly (also reasonable) and throw out ones you've
>already seen (-not- reasonable).
I don't think the particular enumeration is very important in terms of
practical computation.
The way I described things, for every irreducible polynomial
encountered, you explicitly construct its splitting field over the
extension of Q that you have constructed so far. As far as
practical computation is concerned, this extension building process
will grind to a halt long before the problem of discarding irreducibles
you have seen already becomes noticeable.
In practice is it only possible to compute using extensions of reasonably
small degree over Q. So I guess this procedure for computing in A is
notional, and is not recommended for real computation. Real computations
would always be carried out in the smallest possible extension of Q
in which the particular algebraic numbers lie.
>Is there a method for enumertaing them similar to enumerating the
>rationals via Farey sequences (or the related Stern-Brocot tree)?
I don't know, but probably not!
Derek Holt.
William Hale
> In article <3F4CAE...@tcs.inf.tu-dresden.de>,
> Mitch Harris <har...@tcs.inf.tu-dresden.de> writes:
> >ma...@mimosa.csv.warwick.ac.uk wrote:
> >
> >> decide on a particular enumeration of the irreducible polynomials over Q.
> >
> >do you have one in mind?
> >er.. one that is "reasonable" to compute with?
> >That is you -could- just enumerate tuples of integer coeffs (reasonably
> >easy) reduce the poly (also reasonable) and throw out ones you've
> >already seen (-not- reasonable).
>
> I don't think the particular enumeration is very important in terms of
> practical computation.
The enumeration is needed only when you want to "model" *all* of the
algebraic numbers at once. Is that correct?
> The way I described things, for every irreducible polynomial
> encountered, you explicitly construct its splitting field over the
> extension of Q that you have constructed so far.
The hard part is to find the irreducible factors of a polynomial
with coefficients in a finite extension of Q.
Newton knew how to find the irreducible factors of a polynomial
with coeffients in Q (although not with an efficient method).
In the 1980's there appeared several papers on how to do the
more general problem (Zassenhaus, Berkelamp, others).
Note that when you have an irreducible polynomial p(X) and
adjoin a root r to the base field, then you need to find
the irreducible factors of p(X) / (X - r) to continue on.
> As far as
> practical computation is concerned, this extension building process
> will grind to a halt long before the problem of discarding irreducibles
> you have seen already becomes noticeable.
>
> In practice is it only possible to compute using extensions of reasonably
> small degree over Q.
You didn't specify how "small" small is. But certain polynomials are
easier than others. For example, X^p - 1 might be reasonalbe up to
primes less than or equal to 257. This is so because such X^p - 1
split completely when you add just one non-trivial root.
> So I guess this procedure for computing in A is
> notional, and is not recommended for real computation. Real computations
> would always be carried out in the smallest possible extension of Q
> in which the particular algebraic numbers lie.
I wrote a Scheme program that essentially followed the original
poster's idea of starting with just the integers and building up
everything from there, even the rational numbers as being ordered
pairs of integers. The Scheme interpreter was implemented in Java,
so the program was not too fast. I recall that X^19 - 1 took several
minutes to computer the "model" of the algebraic integers for the
spitting field of X^19 - 1. My goal was to solve equations like
X^7 - 1 in terms of radicals.
-- Bill Hale
Mitch Harris
>Mitch Harris <har...@tcs.inf.tu-dresden.de> writes:
>>ma...@mimosa.csv.warwick.ac.uk wrote:
>>
>>>decide on a particular enumeration of the irreducible polynomials over Q.
>>
>>do you have one in mind?
>>er.. one that is "reasonable" to compute with?
>>That is you -could- just enumerate tuples of integer coeffs (reasonably
>>easy) reduce the poly (also reasonable) and throw out ones you've
>>already seen (-not- reasonable).
>
>
> I don't think the particular enumeration is very important in terms of
> practical computation.
Suppose we want to compute x*y, and our representation is "kth root of
polynomial p(z)"
let x = the 2nd root of z^7 - 3z^3 + 1
let y = the 5th root of z^9 + z^6 + 2z^5 + 1
given a particular ordering mechanism for all roots.
(mathematica tells me these are irreducible)
we want to know what x*y is.
it is a root of some 69 degree polynomial.
it is very conceivable to me that the index of this root can change
depending on the ordering mechanism.
> The way I described things, for every irreducible polynomial
> encountered, you explicitly construct its splitting field over the
> extension of Q that you have constructed so far.
OK, which would avoid any cares about root ordering during the
computation. But it still seems like you'd have to at some point (at the
very end) compute the index of the root in the given ordering.
> As far as
> practical computation is concerned, this extension building process
> will grind to a halt long before the problem of discarding irreducibles
> you have seen already becomes noticeable.
However it works, I suppose the algorithms are known somehow since at
least Mathematica does computations this way.
If the representation is just using radicals (a subset of the
algebraics), then some variations of the problem seems to be open as of
a short time ago:
Susan Landau, Tangling with nested radicals:
http://www.cs.umass.edu/Dienst/UI/2.0/Describe/ncstrl.umassa_cs%2FUM-CS-1991-076
which talks about one particular kind of normal form, that of reducing
the depth of radical nesting. There might exist other unique normal
forms where nesting depth is not an issue.
> In practice is it only possible to compute using extensions of reasonably
> small degree over Q. So I guess this procedure for computing in A is
> notional, and is not recommended for real computation. Real computations
> would always be carried out in the smallest possible extension of Q
> in which the particular algebraic numbers lie.
--