Evaluating tropical polynomials at QQFieldElem gives promotion error

[oskarhenriksson]

Suppose we form a simple tropical polynomial in the following way:

using Oscar

Qt, t = rational_function_field(QQ, "t")
nu = tropical_semiring_map(Qt, t)
Qtx, (x,) = polynomial_ring(Qt, ["x"])

f = tropical_polynomial(t^(-2)*x^3,nu)

If we try to evaluate it at x=4, we get the expected answer 10 if 4 is entered as a anInt or Rational{Int64}, but we get a promotion error when it is a QQFieldElem.

julia> evaluate(f,[4])
(10)

julia> evaluate(f,[4//1])
(10)

julia> evaluate(f,[QQ(4)])
ERROR: Cannot promote to common type
Stacktrace:
 [1] error(s::String)
   @ Base ./error.jl:35
 [2] promote(x::TropicalSemiringElem{typeof(min)}, y::QQFieldElem)
   @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/tABFQ/src/NCRings.jl:54
 [3] *(x::TropicalSemiringElem{typeof(min)}, y::QQFieldElem)
   @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/tABFQ/src/NCRings.jl:80
 [4] evaluate(a::AbstractAlgebra.Generic.MPoly{TropicalSemiringElem{typeof(min)}}, vals::Vector{QQFieldElem})
   @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/tABFQ/src/MPoly.jl:888
 [5] top-level scope
   @ REPL[6]:1

The issue seems to be that *(x::TropicalSemiringElem{typeof(min)}, y::QQFieldElem) doesn't work, but I haven't been able to figure out if the best way to fix it is to add a new version of *. It's also not clear to me why this isn't caught by any of the promotion/parent strategies in NCRings.jl.

[oskarhenriksson]

A naive attempt to fix this by manually adding a *(x::TropicalSemiringElem{typeof(min)}, y::QQFieldElem) function as follows:

function Base.:(*)(x::TropicalSemiringElem, y::QQFieldElem)
    iszero(x) && return x # if x is zero, return it
    return parent(x)(data(x) + y) # otherwise, return their sum
end

gives the expected multiplication

julia> tropical_semiring(min)(-2)*(12)
(10)

but tropical polynomials are still not evaluated correctly, so I suppose I miss something about how tropical polynomials work in Oscar:

julia> evaluate(f,[QQ(4)])
(62)

[YueRen]

I guess the question is what function needs to exist so that conversion from QQFieldElem to TropicalSemiringElem works. There already is (R::TropicalSemiring{typeof(max)})(x::QQFieldElem; preserve_ordering::Bool=false) in semiring.jl, but that doesn't seem to do the job.

[joschmitt]

I assume one would have to add promotion rules for TropicalSemiringElem like here https://nemocas.github.io/AbstractAlgebra.jl/stable/ring_interface/#Promotion-rules. If these exist, then x * y with x a TropicalSemiringElem and y a QQFieldElem should automatically be converted to x * parent(x)(y) (assuming that this is what should happen).

[joschmitt]

Concretely, if one adds

AbstractAlgebra.promote_rule(::Type{TropicalSemiringElem{minOrMax}}, ::Type{QQFieldElem}) where {minOrMax<:Union{typeof(min), typeof(max)}} = TropicalSemiringElem{minOrMax}

then the multiplication of a TropicalSemiringElem by a QQFieldElem seems to work (as far as I can tell).
However, the example above now gives:

julia> evaluate(f,[QQ(4)])
(62)

which I suppose is wrong. This is the "fault" of evaluate which uses ^ for QQFieldElem. That it works for Int seems to be more of a coincidence: evaluate does some type acrobatics for types which are not a RingElem.

[YueRen]

Concretely, if one adds

AbstractAlgebra.promote_rule(::Type{TropicalSemiringElem{minOrMax}}, ::Type{QQFieldElem}) where {minOrMax<:Union{typeof(min), typeof(max)}} = TropicalSemiringElem{minOrMax}

then the multiplication of a TropicalSemiringElem by a QQFieldElem seems to work (as far as I can tell). However, the example above now gives:

julia> evaluate(f,[QQ(4)])
(62)

which I suppose is wrong. This is the "fault" of evaluate which uses ^ for QQFieldElem. That it works for Int seems to be more of a coincidence: evaluate does some type acrobatics for types which are not a RingElem.

There is working exponentiation for tropical numbers (which is just normal multiplication, as tropical multiplication is normal addition):

julia> T = tropical_semiring()
Min tropical semiring

julia> T(1)^3
(3)

Is there a way to make evaluate convert the input point to the coefficient ring of the polynomial before doing any arithmetic with it?

[joschmitt]

Is there a way to make evaluate convert the input point to the coefficient ring of the polynomial before doing any arithmetic with it?

We could tinker with evaluate I suppose.
Honestly, I think we should forbid multiplying elements from the tropical semiring by elements of QQ etc. It is simply ambiguous:

julia> AbstractAlgebra.promote_rule(::Type{TropicalSemiringElem{minOrMax}}, ::Type{QQFieldElem}) where {minOrMax<:Union{typeof(min), typeof(max)}} = TropicalSemiringElem{minOrMax}

julia> T = tropical_semiring();

julia> QQ(1)*T(1)
(2)

julia> QQ(1)*QQ(1)*T(1)
(2)

julia> QQ(1)*(QQ(1)*T(1))
(3)

julia> QQ(1)^2*T(1)
(2)

julia> T(1)*QQ(1)*QQ(1)
(3)

The same problem already exists on master with Int, so 1*1*T(1) != T(1)*1*1.

[YueRen]

I think evaluate and tropical addition / multiplication are two seperate issues.

I believe changing evaluate to conversion first makes sense. It is natural to assume that conversion commutes with arithmetic, i.e., it is a homomorphism, but that need not be the case.

As for forbidding operations with tropical and rational numbers because it is not associative, I am strongly against it. I'm open to having a warning (as long as it can be disabled) and a rule that such code shouldn't make it into production, but having to write T() around every tropical number would make OSCAR significantly less user-friendly.

[thofma]

You can overload evaluate(...) for a specific type if you want a different behavior. But this helps only till someone finds the next wrong result.

All the code for commutative rings assumes that the commutative ring has a one element and that n -> R(n) is the canonical map. It was a neat hack just reusing the existing code for tropical rings, but maybe there should be separate implementation of tropical polynomials and matrices (or maybe over semirings in general).

[thofma]

@YueRen can you confirm that the polynomials we want are the same as implemented here: https://github.com/sagemath/sage/pull/38536/files#diff-fe963133a558d88dbe26710f804ba7682f40f80e7e35b3999543fe13423b8862?

[YueRen]

Yeah, the examples looks about right. Thought that implementation comes with many functions that I wouldn't consider absolutely necessary. Highest priority would be that the type plays well with existing functions.

[thofma]

My point would be that they disallow 2*x and only allow R(2)*x.

[YueRen]

Ah, I didn't see that. I'm against disallowing 2*x, because that will make it a pain to use. If we want to discourage the use of 2*x, I don't mind printing a warning (as long as said warning can be disabled).