Re: [Axiom-developer] PFE, Complex and INT

[Martin Rubey]

Dear Waldek,


many thanks for looking into this.  Unfortunately, I'm an absolute beginner
concerning factorization and number theory, as you probably noticed...

Waldek Hebisch <address@hidden> writes:

> Martin Rubey wrote:
> > Dear all,
> > 
> > regarding Issue #352 and possibly #351, I experimented a little.  The 
> > starting
> > point is the documentation of PFECAT, in catdef.spad:

[...]

> I think that this requres deeper investigation.  Namely, gcd and
> factorization is currently provided by different packages using somewhat
> different method.  We have to check which method is better and turn it on.
> Also, it looks that in the meantime better algorithms appeared, so we may
> prefer to implement them and forget abot old ones.

Definitively.  But, lacking somebody who knows about these things (or do you?),
what can we do?  For myself, it's also a matter of time.

By the way, a collegue (Dietrich Burde, a number theorist) experimented a
little with various packages like pari, maple, mathematica, reduce, etc., what
algorithms they use for factoring integers.  It turned out that pari is by far
the most intelligent package.  I believe we should interface to pari,
therefore...

> > diff -c 
> > /home/martin/lib/axiom/target/i686-pc-linux/src/algebra/gaussian.spad
> > /home/martin/gaussian.spad
> > *** /home/martin/lib/axiom/target/i686-pc-linux/src/algebra/gaussian.spad
> > 2007-05-02 20:39:25.000000000 +0200
> > --- /home/martin/gaussian.spad  2007-05-03 09:30:12.000000000 +0200
> > ***************
> > *** 91,96 ****
> > --- 91,97 ----
> >            ++ "failed" if x is not a rational number.
> >        if R has PolynomialFactorizationExplicit and R has EuclideanDomain 
> > then
> >           PolynomialFactorizationExplicit
> > +      if R has UniqueFactorizationDomain then UniqueFactorizationDomain
> 
>                   ^^^^^^^^^^^^^^^^^^^^^^^^^
> 
> That looks like overgeneralization.  First, Complex R may have zero
> divisors (so we will hit bug 351).  Even if Complex R is an integral
> domain, it is not clear if it has unique factorization (do you know
> about any theorem asserting this?).  Finally, even if Complex R
> has unique factorization AFAICS we do not have any factorization
> algorithm working in Complex R.  So I would just write:
> 
>         if R is Integer then UniqueFactorizationDomain
>   
> which seem to agree with implementation. 

Yes.  Maybe, IntegerNumberSystem, though.  (I think we want to support
factorization in Complex SingleInteger, too.

Martin