Re: [Axiom-developer] Bug in GeneralizedMultivariateFactorize?

[William Sit]

The domain Factored R does not promise full factorization. Indeed, it only
promise to keep the elements of R in factored form, and a factor has a flag,
including "nil", "sqfr", "irred" or "prime". So returning a square free form is
not a bug.

The MultivariateSquareFree package has a squareFree operation when the
coefficient domain is a EuclideanDomain (and the PolynomialGcdPackage provides
gcd operations via Hensel lifting). However, I am not sure if there is a
squareFree operation when the coefficient ring is just an integral domain. There
is some indication from the +++ comments that the author (Gianni) believed a
squareFree factorization is possible for multivariate polynomial rings over
certain integral domains (but the algorithm then used requires a Euclidean
division algorithm) and hence the more relaxed requirement on the coefficient
domain in GENMFACT.

Disclaimer: I am not an expert on factorization.

William

Waldek Hebisch wrote:

> Stephen Wilson wrote:
> >
> > *,
> >
> > I was hoping for some help with GeneralizedMultivariateFactorize
> > (GENMFACT) in allfact.spad.pamphlet.
> >
> > The issue is with the following code, in particular with the call to
> > squareFree at the end:
> >
> >    T == add
> >     factor(p:P) : Factored P ==
> >       R has FiniteFieldCategory => factor(p)$MultFiniteFactorize(OV,E,R,P)
> >       R is Polynomial(S) and S has EuclideanDomain =>
> >          factor(p)$MPolyCatPolyFactorizer(E,OV,S,P)
> >       R is Fraction(S) and S has CharacteristicZero and
> >         S has EuclideanDomain =>
> >             factor(p)$MRationalFactorize(E,OV,S,P)
> >       R is Fraction Polynomial S =>
> >          factor(p)$MPolyCatRationalFunctionFactorizer(E,OV,S,P)
> >       R has CharacteristicZero and R has EuclideanDomain =>
> >                factor(p)$MultivariateFactorize(OV,E,R,P)
> >       squareFree p
> >
> >
> > Here, P satisfies a PolynomialCategory over an IntegralDomain.  But
> > such a P does not export squareFree unless the coefficient ring is a
> > GcdDomain.  This is a bug in GENMFACT, I believe.
> >
> > I do not have the experience necessary with the algebra code yet to be
> > terribly efficient in determining what the proper fix here is.
> > Perhaps it is as simple as requiring GcdDomain.
> >
> > Could anyone provide some insight here?
> >
>
> This looks like a frequent bug in Axiom, namely giving too general
> signature.  From correctness point of view the last call to squareFree
> is debatable: we promised to give full factorization, but we are
> giving only the square free one.
>
> So IMHO the correct thing to do would be to require that R is UFD.
> Since factorization algorithm for polynomials over UFD may be
> impractical, it is reasnable to signal error if we miss aproproate
> algoritm.
>
> Alternative approach is to work on "best effort" basis and just
> return the input unfactored if we have no idea how to factor it.
> However, I would not call such funtions factor, but rather
> maybeFactor.
>
> Looking at usage I see that in SYSSOLP GeneralizedMultivariateFactorize
> is used for R which is only IntegralDomain -- I am not sure if
> SYSSOLP can give sensible results for general IntegralDomain.
>
> In GROEBSOL GeneralizedMultivariateFactorize is used for GcdDomain.
> My impression is that GROEBSOL works on "best effort" basis, so
> using squareFree may be reasonable here.
>
> --
>                               Waldek Hebisch
> address@hidden
>
> _______________________________________________
> Axiom-developer mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/axiom-developer

--
William Sit
Department of Mathematics..Email: address@hidden
City College of New York................Tel: 212-650-5179
New York, NY 10031, USA.................Fax: 212-862-0004
Home page: .......http://scisun.sci.ccny.cuny.edu/~wyscc/