Caching of universal polynomials in `change_base_ring`

[SoongNoonien]

With the new approach for the caching of universal polynomials we get some unexpected results. I first noticed this in oscar-system/GenericCharacterTables.jl#319.

julia> R,(x,y)=universal_polynomial_ring(QQ, [:x,:y])
(Universal polynomial ring over Rationals, UniversalRingElem{AbstractAlgebra.Generic.MPoly{Rational{BigInt}}, Rational{BigInt}}[x, y])

julia> f=x
x

julia> change_base_ring(ZZ, f)
x

julia> S,_=universal_polynomial_ring(ZZ, [:x,:y])
(Universal polynomial ring over Integers, UniversalRingElem{AbstractAlgebra.Generic.MPoly{BigInt}, BigInt}[x, y])

julia> z=gen(S,:z)
z

julia> change_base_ring(ZZ, f)
ERROR: length of exponent vector should match the number of variables
Stacktrace:
 [1] error(s::String)
   @ Base ./error.jl:44
 [2] push_term!(M::MPolyBuildCtx{AbstractAlgebra.Generic.MPoly{BigInt}, DataType}, c::BigInt, expv::Vector{Int64})
   @ AbstractAlgebra.Generic ~/Archiv/Computer/Programme/AbstractAlgebra.jl/src/generic/MPoly.jl:3761
 [3] _map(g::AbstractAlgebra.Integers{BigInt}, p::AbstractAlgebra.Generic.MPoly{Rational{BigInt}}, Rx::AbstractAlgebra.Generic.MPolyRing{BigInt})
   @ AbstractAlgebra ~/Archiv/Computer/Programme/AbstractAlgebra.jl/src/MPoly.jl:1437
 [4] #change_base_ring#403
   @ ~/Archiv/Computer/Programme/AbstractAlgebra.jl/src/MPoly.jl:1397 [inlined]
 [5] change_base_ring
   @ ~/Archiv/Computer/Programme/AbstractAlgebra.jl/src/MPoly.jl:1395 [inlined]
 [6] change_base_ring(R::AbstractAlgebra.Integers{…}, p::UniversalRingElem{…}; cached::Bool, parent::UniversalPolyRing{…})
   @ AbstractAlgebra ~/Archiv/Computer/Programme/AbstractAlgebra.jl/src/UnivPoly.jl:600
 [7] change_base_ring(R::AbstractAlgebra.Integers{BigInt}, p::UniversalRingElem{AbstractAlgebra.Generic.MPoly{Rational{BigInt}}, Rational{BigInt}})
   @ AbstractAlgebra ~/Archiv/Computer/Programme/AbstractAlgebra.jl/src/UnivPoly.jl:598
 [8] top-level scope
   @ REPL[9]:1
Some type information was truncated. Use `show(err)` to see complete types.

The problem is that the caching of universal polynomial ignores the supplied symbols. We've discussed this and decided that this should indeed be the way to go.

To resolve this problem here we would need to discuss how to deal with a supplied parent which has a different number of variables. Should we just silently ignore this and map the polynomial anyway? Or should we at least check that the first variables have the same name?

[fingolfin]

A maybe more concise way to show the problem, without even an error:

julia> R,(x,y)=universal_polynomial_ring(QQ, [:x,:y])
(Universal polynomial ring over Rational field, UniversalRingElem{QQMPolyRingElem, QQFieldElem}[x, y])

julia> S,_=universal_polynomial_ring(ZZ, [:y,:x])
(Universal polynomial ring over Integer ring, UniversalRingElem{ZZMPolyRingElem, ZZRingElem}[y, x])

julia> change_base_ring(ZZ, x)
y

Which is probably not what we want sigh.

[fingolfin]

While looking at this, we also realized that while some change_base_ring methods have parent and cached kwarg, many do not, and this may also cause further problems.

E.g.

  [7] change_base_ring(S::Ring, M::SubquoModule)
     @ ~/Projekte/OSCAR/Oscar.spielwiese/src/Modules/UngradedModules/Methods.jl:408
  [8] change_base_ring(A::Ring, Q::MPolyQuoRing)
     @ ~/Projekte/OSCAR/Oscar.spielwiese/src/Rings/MPolyMap/base_change.jl:7
  [9] change_base_ring(A::Ring, P::MPolyDecRing)
     @ ~/Projekte/OSCAR/Oscar.spielwiese/src/Rings/MPolyMap/base_change.jl:16
 [10] change_base_ring(A::Ring, P::MPolyRing)
     @ ~/Projekte/OSCAR/Oscar.spielwiese/src/Rings/MPolyMap/base_change.jl:1

 [16] change_base_ring(R::Ring, p::LaurentPolyRingElem)
     @ ~/.julia/packages/AbstractAlgebra/a2EqM/src/algorithms/LaurentPoly.jl:193

[fingolfin]

OK in fairness, most of the method I flagged there are on "parent objects" (modules and rings); and so a parent kwarg makes no sense for them. Instead they return two things, a new "parent object", plus a map from old to new "parent object". As far as I can tell, this is undocumented (at least there seems to be no docstring describing it)

[fingolfin]

So, I can think of ways to resolve it (but am open to further suggestions):

1. we just disable caching in universal poly rings (at least for the time being). Not sure how breaking that would be for actual users. I wonder if there are any besides GenericCharacterTables? Who knows ... :-/ Not knowing of course is part of the problem, I don't know if changing this would really annoy someone out there...

2. we disable change_base_ring for universal rings, i.e., turn it into an error which suggests alternatives.. but what are they?! Also, might hurt existing users just like point 1.

3. we change the "conversion" performed by change_base_ring in this case, to not delegate to the change_base_ring method of the underlying MPolyRing (at least I assume that's what we are doing?); instead implement a (much slower) conversion based on variable names.

One classic argument against the name based mapping of variables (besides it being inefficient), at least for mpolyrings, is that it is also ambiguous: a poly ring can have multiple variables with equal name. But I'd argue this is irrelevant for us because the universal polynomial rings already assume as part of their interface that each variable is uniquely determined by its name (and let's face it, that's also what ordinary mathematicians will expect, and really also most of us if they are not explicitly thinking about it).

One saving grace in our case is that the mapping is purely a permutation, and we could in theory even lazily cache this permutation (under various constraints: "if the underlying mpolyring of source and destination have not changed, we can use this permutation; otherwise, we need to build a new permutation, but we can at least re-use the parts we already built up). Alas, then we'd also need a way to store these, meaning that we'd need to have a (weak ref based) map of ring correspondences ("canonical mappings", anyone? sigh). This is possible, but a lot of headaches, so I'd not implement it for now; instead wait for this to become a bottleneck...

Actually, if the speed of change_base_ring is an issue for a user, perhaps the suggested solution should be to provide a "map between universal rings", i.e. a "morphism" (if it is a morphism... in which category?!?) from a universal (polynomial) ring R to another universal ring, which maps variables to matching variables. Then this object is a natural place to take care of caching stuff for better speed. That might address the efficiency sufficiently. (Mind you, I am not asking that we implement this, I just sketch this as a potential future way out).

All in all, approach 3 seems more in line with the whole purpose of the universal polynomial rings. I wonder if @fieker, @thofma or @lgoettgens have any concerns or other ideas...

[fingolfin]

During triage, there was agreement (or at least no disagreement) to basically follow my 3rd proposal, i.e., track variables based on their names.

We could also enhance the constructor for universal rings to reject list of variable names with duplicates.

[SoongNoonien]

I've looked into the Oscar functionality MPolyHom_vars which should be useful to achieve this name based mapping. Unfortunately, it uses Hecke.MapHeader and thus can't just be copied over. But the actual mapping is done in the function im_func which doesn't depend on any Hecke types. So, we could copy this function over to AbstractAlgebra. But then Oscar should be adapted to use the AbstractAlgebra version of im_func once there is a new release.