Re: [Axiom-developer] Bug in GeneralizedMultivariateFactorize?

[Waldek Hebisch]

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