the min-plus semiring (Q∪{+∞},⊕,⊙) with a⊕b=min(a,b) and a⊙b=a+b,
the max-plus semiring (Q∪{−∞},⊕,⊙) with a⊕b=max(a,b) and a⊙b=a+b.
Whereas tropical semirings in [MS15] and [Jos21] are extensions of the real numbers, tropical semirings in OSCAR are an extension of the rational numbers to avoid precision issues.
Return the min-plus (default) or max-plus semiring.
Warning
+, *, /, and ^ are used for tropical addition, tropical multipliciation, tropical division, and tropical exponentiation, respectively.
There is no additive inverse or subtraction in the tropical semiring. Negating a tropical number or subtracting two tropical numbers will raise an error.
Zeroes of tropical semirings are printed as infty or -infty instead of their proper unicode characters. To enabled unicode in the current and future sessions, run allow_unicode(true).
Examples (basic arithmetic)
julia> T = tropical_semiring() # = tropical_semiring(min)Min tropical semiring
julia> T = tropical_semiring(max)
Max tropical semiring
julia>0*T(3) + 1*T(1)^2 + zero(T) # = max(0+3,1+2*1,-∞)(3)
julia> T(0) == 0# checks whether the tropical number is 0true
julia> iszero(T(0)) # checks whether the tropical number is neutral element of additionfalse
Examples (polynomials)
julia> T = tropical_semiring()
Min tropical semiring
julia> Tx,(x1,x2) = polynomial_ring(T,2)
(Multivariate polynomial ring in 2 variables over min tropical semiring, AbstractAlgebra.Generic.MPoly{TropicalSemiringElem{typeof(min)}}[x1, x2])
julia> f = x1 + -1*x2 + 0x1 + (-1)*x2 + (0)
julia> evaluate(f,T.([-1//2,1//2])) # warning: omitting T() gives an error(-1//2)
Return min if T is the min tropical semiring, return max if T is the max tropical semiring. Works similarly for tropical numbers, tropical vectors and matrices, and tropical polynomials.
Examples
julia> T = tropical_semiring(min)
Min tropical semiring
julia> convention(T)
min (generic function with 27 methods)
julia> T = tropical_semiring(max)
Max tropical semiring
julia> convention(T)
max (generic function with 27 methods)
Return the tropical determinant of A. That is, this function evaluates the tropicalization of the ordinary determinant considered as a multivariate polynomial at A.
That computation is equivalent to solving a linear assignment problem from combinatorial optimization. The implementation employs the Hungarian method, which is polynomial time. See Chapter 3 in [Jos21].
Note
This function effectively overwrites the det command for tropical matrices. This means that functions like minors will use the tropical determinant when used on a tropical matrix.
Return the tropical roots of a univariate tropical polynomial f, i.e., the variable values where the min or max is attained at least twice.
Examples
julia> R,x = polynomial_ring(tropical_semiring(min),:x)
(Univariate polynomial ring in x over min tropical semiring, x)
julia> f = 1*x^2+x+0(1)*x^2 + x + (0)
julia> roots(f)
2-element Vector{QQFieldElem}:
0
-1
julia> R,x = polynomial_ring(tropical_semiring(max),:x)
(Univariate polynomial ring in x over max tropical semiring, x)
julia> f = 1*x^2+x+0(1)*x^2 + x + (0)
julia> roots(f)
1-element Vector{QQFieldElem}:
-1//2
Given a polynomial f and a tropical semiring map nu, return the tropicalization of f as a polynomial over the tropical semiring.
Examples
julia> R, (x,y) = polynomial_ring(QQ,[:x, :y])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])
julia> nu = tropical_semiring_map(QQ,7)
Map into Min tropical semiring encoding the 7-adic valuation on Rational field
julia> f = 7*x+y+497*x + y + 49
julia> tropical_polynomial(f,nu)
(1)*x + y + (2)