Roots with multiplicity

[thofma]

We need a version of roots which counts multiplicties, aka, roots_with_multiplicites (see thofma/Hecke.jl#2176). Return value is Vector{Tuple{<: RingElement, Int}}}. Ideally we don't duplicate too much code. Most root functions go via factor anyway, so my idea would be to do the following:

roots_with_multiplicity(f::PolyRingElem) = internal_roots_with_multiplicity(f)

internal_roots_with_multiplicity(f::PolyRingElem) = throw(NotImplementedError(:internal_roots_with_multiplicity, f)

function roots(f::PolyRingElem)
  first.(internal_roots_with_multiplicity(f))
end

and then the different types just implement internal_roots_with_multiplicity. This should be non-breaking.

Types like nmod_poly with non-prime modulus can still implement roots directly. I don't think it is necessary at the moment, but we could also add the helper

_roots_with_multiplicity_from_roots(f) = [(a, valuation(f, a)) for a in roots(f)]

so that in principle one could do internal_roots_with_multiplicity(f::MyPolyType) = _roots_with_multiplicity_from_roots(f) (for example for nmod_poly).

Thoughts? Complains?

P.S.: Multiplicity of $a$ in $f \in R[X]$ is the maximal $k$ such that $(X - a)^k$ divides $f$. Division with remainder is well-defined and unique for any commutative ring if one divides by something monic.

[fingolfin]

What do we gain by having internal_roots_with_multiplicity as an intermediary, over just directly using roots_with_multiplicity like that?

[thofma]

Hmm, probably nothing. I think this was some overengineering on my side.