Regarding the MPolyFactor code: using it, testing it, further development

[fingolfin]

I am unsure how to use the code in src/algorithms/MPolyFactor.jl. A comment there says:

# experimental module whose parts can be overridden for specific types
# main functions are mfactor_squarefree_char_zero and mfactor_char_zero

and I think it is used by @thofma in Hecke. (Hecke also contains a file src/Misc/MPolyFactor.jl which seems to be a different (perhaps older?) version of the same code, but it also doesn't seem to be used or even included in Hecke?).

Unfortunately there are no real tests for it. In test/algorithms/MPolyFactor-test.jl a few helpers are tested and there is a comment saying:

# not much to test because we would need working univariate factorization

But in practice it still seems to work in many cases, at least in char 0 and if the coefficients support factorization (for AA that means: coefficients are in a field):

julia> R,(x,y)=QQ[:x,:y]
(Multivariate polynomial ring in 2 variables over rationals, AbstractAlgebra.Generic.MPoly{Rational{BigInt}}[x, y])

julia> AbstractAlgebra.MPolyFactor.mfactor_char_zero((x+1)^2*(x-y+2))
1 * (x + 1)^2 * (x - y + 2)

julia> collect(ans)
2-element Vector{Pair{AbstractAlgebra.Generic.MPoly{Rational{BigInt}}, Int64}}:
     x + 1 => 2
 x - y + 2 => 1

Now it does sometimes run into an error due to missing `factor, e.g.::

julia> AbstractAlgebra.MPolyFactor.mfactor_char_zero((x+1)^2*(x-y+2)*(y^2-x))
ERROR: function factor is not implemented for argument
AbstractAlgebra.Generic.Poly{Rational{BigInt}}: x^2 + 2*x

But ironically in this example it can actually factor the polynomial itself:

julia> AbstractAlgebra.MPolyFactor.mfactor_char_zero(x^2 + 2*x)
1 * (x + 2) * x

But alas one can construct examples where it really fails:

julia> AbstractAlgebra.MPolyFactor.mfactor_char_zero(x^2 + 2*x + 2)
ERROR: function factor is not implemented for argument
AbstractAlgebra.Generic.Poly{Rational{BigInt}}: x^2 + 2*x + 2

This raises two questions in my mind:

1. would it make be useful for us to add a generic factor(::MPolyRingElem) method delegating to AbstractAlgebra.MPolyFactor.mfactor_char_zero at least if if the characteristic is 0 (and keeping issue Bug (?) in MPolyFactor when coefficients are are not in a field #1960 in mind)

• we have plenty of precedent for such functions, i.e., functions that only work if certain other functions are implemented, possibly functions for the coefficient ring

2. what about non-zero characteristic? What would be needed for that? Is anyone interested in this functionality? And is someone interested in implementing that?

[fieker]

On Thu, Jan 16, 2025 at 01:36:14AM -0800, Max Horn wrote: I am unsure how to use the code in `src/algorithms/MPolyFactor.jl`. A comment there says: > `#` experimental module whose parts can be overridden for specific types > `#` main functions are mfactor_squarefree_char_zero and mfactor_char_zero and I think it is used by @thofma in Hecke. (Hecke also contains a file `src/Misc/MPolyFactor.jl` which seems to be a different (perhaps older?) version of the same code, but it also doesn't seem to be used or even `include`d in Hecke?). Unfortunately there are no real tests for it. In `test/algorithms/MPolyFactor-test.jl` a few helpers are tested and there is a comment saying: > `#` not much to test because we would need working univariate factorization But in practice it still seems to work in many cases, at least in char 0 and if the coefficients support factorization (for AA that means: coefficients are in a field): ``` julia> R,(x,y)=QQ[:x,:y] (Multivariate polynomial ring in 2 variables over rationals, AbstractAlgebra.Generic.MPoly{Rational{BigInt}}[x, y]) julia> AbstractAlgebra.MPolyFactor.mfactor_char_zero((x+1)^2*(x-y+2)) 1 * (x + 1)^2 * (x - y + 2) julia> collect(ans) 2-element Vector{Pair{AbstractAlgebra.Generic.MPoly{Rational{BigInt}}, Int64}}: x + 1 => 2 x - y + 2 => 1 ``` Now it *does* sometimes run into an error due to missing `factor, e.g.:: ``` julia> AbstractAlgebra.MPolyFactor.mfactor_char_zero((x+1)^2*(x-y+2)*(y^2-x)) ERROR: function factor is not implemented for argument AbstractAlgebra.Generic.Poly{Rational{BigInt}}: x^2 + 2*x ``` But ironically in this example it can actually factor the polynomial itself: ``` julia> AbstractAlgebra.MPolyFactor.mfactor_char_zero(x^2 + 2*x) 1 * (x + 2) * x ``` But alas one can construct examples where it really fails: ``` julia> AbstractAlgebra.MPolyFactor.mfactor_char_zero(x^2 + 2*x + 2) ERROR: function factor is not implemented for argument AbstractAlgebra.Generic.Poly{Rational{BigInt}}: x^2 + 2*x + 2 ``` This raises two questions in my mind: 1. would it make be useful for us to add a generic `factor(::MPolyRingElem`) method delegating to `AbstractAlgebra.MPolyFactor.mfactor_char_zero` at least if if the characteristic is 0 (and keeping issue #1960 in mind) - we have plenty of precedent for such functions, i.e., functions that only work if certain other functions are implemented, possibly functions for the coefficient ring 2. what about non-zero characteristic? What would be needed for that? Is anyone interested in this functionality? And is someone interested in implementing that?

Definitely NOT in AA, in Nemo we have the MPoly Factor in char p, well over a FinField. In general, we'd like to do this over any fin. pres. exact field, but in my opinion, not in AA. The AA code is mostly "tested" via Hecke/ Oscar. The MPoly Factoring over a number field as well as the absolute factorisation is using this code - or parts of it. The weird one where the "unit" is not factored: I'd not worry about it. Maybe we unexport it. That behaviour is part of a discussion about factoring over Q/Z and what people want. I regard the weired functions as internal. Use factor if you want, but we won't get far as I think no factoring is implemented in AA itself - only the helper functions for the more generic stuff in Nemo/ Hecke/ Oscar

…

-- Reply to this email directly or view it on GitHub: #1961 You are receiving this because you are subscribed to this thread. Message ID: ***@***.***>

[thofma]

That there is not test within AA is a consequence of moving the code to not have "type piracy". If there is no univariate factorization, there cannot be useful tests. I don't think there is anything that can be done.

The file in Hecke should indeed be removed.

Regarding the non-zero characteristic, there is no generic algorithm to reduce it to the univariate case.