Re: [Axiom-developer] Bug in GeneralizedMultivariateFactorize?

[William Sit]

Waldek Hebisch wrote:

> Well, if you look just at types factor can return anything.  However,
> we have:
>
>     factor      :      P  ->  Factored P
>       ++ factor(p) factors the multivariate polynomial p over its coefficient
>       ++ domain

> The ++ comment does not mention possibility of unfactored output. Other factor
> functions give completly factored output, so giving unfactored output is
> inconsistent with other functions.

It did not say "completely factors into irreducibles" but it does not preclude 
it
either (but that is quibbling :-).

> Given that there are functions like subtractIfCan it is natural that function 
> which
> factorizes on "best effort" basis should have different name.

Following that logic, we should also have integrateIfCan, solveIfCan,  and lots 
of
other IfCan's so that there would be no need for errors messages (like addIfCan 
on
vectors instead of signalling error when the summands have different 
dimensions).
There has to be some freedom in the way errors or incomplete solutions are 
handled.
Given a choice, I would prefer to signal an error at run time instead of using 
IfCan's
and asks the compiler to verify the right branch. IfCan requires 
Union("failed", ...)
as its target domain, leading to unnecessary overhead. Union("failed", ...) 
would be
useful if it is possible to handle the "failed" case, but then there would be 
no need
for error signalling anyway.

> Mathematically, to have well-defined (unique) factorizations we need
> something like Krull ring.  But Krull ring such that gcd exists for
> all pairs of elements is a unique factorisation domain.  I suspect
> that similar things holds for square free decomposition.
>
> Practically, when working with polynomils we may want to ignore
> problems due to coefficient ring, that is consider degree 0 factors
> as trivial.  But it is still not clear if we can do square free
> decomposition (without for example extending coefficient ring to a
> field).   However, assuming that we can compute such a decomposition
> it would be a different operation than the normal square free
> decomposition, so I feel that it deserves different name.

In that case, the domanis Factored R should also be restricted to hold only 
completely
factored forms. You will then need new names for all the intermediately factored
forms.

> Similarly, it may happen that some elements of a ring which is
> not a unique factorisation domain happen to have unique factorisation.
> Again, a operation which factors elements which are factorizable
> and returns other unfactored is IMHO a different operation than
> Axiom factor function.

In the case a domain does not have UFD, if we use factorIfCan, we would be hard
pressed to come up with a general algorithm that can detect which elements can 
be
factored uniquely. The complexity is much higher than subtractIfCan. Is this 
even
decidable? What domain would have such an algorithm?

William