Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Evaluating tropical polynomials at QQFieldElem gives promotion error #4014

Open
oskarhenriksson opened this issue Aug 15, 2024 · 12 comments
Open
Labels
bug Something isn't working topic: tropical geometry

Comments

@oskarhenriksson
Copy link

oskarhenriksson commented Aug 15, 2024

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 oskarhenriksson added the bug Something isn't working label Aug 15, 2024
@oskarhenriksson
Copy link
Author

oskarhenriksson commented Aug 15, 2024

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
Copy link
Member

YueRen commented Aug 15, 2024

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
Copy link
Member

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
Copy link
Member

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
Copy link
Member

YueRen commented Aug 15, 2024

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
Copy link
Member

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
Copy link
Member

YueRen commented Aug 15, 2024

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
Copy link
Collaborator

thofma commented Aug 16, 2024

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
Copy link
Collaborator

thofma commented Aug 22, 2024

@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
Copy link
Member

YueRen commented Aug 22, 2024

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
Copy link
Collaborator

thofma commented Aug 22, 2024

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

@YueRen
Copy link
Member

YueRen commented Aug 22, 2024

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).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working topic: tropical geometry
Projects
None yet
Development

No branches or pull requests

5 participants