Tropical Semirings

Tropical Semirings

AUTHORS:

  • Travis Scrimshaw (2013-04-28) - Initial version
class sage.rings.semirings.tropical_semiring.TropicalSemiring(base, use_min=True)

Bases: sage.structure.parent.Parent, sage.structure.unique_representation.UniqueRepresentation

The tropical semiring.

Given an ordered additive semigroup \(R\), we define the tropical semiring \(T = R \cup \{+\infty\}\) by defining tropical addition and multiplication as follows:

\[a \oplus b = \min(a, b), \quad \quad a \odot b = a + b.\]

In particular, note that there are no (tropical) additive inverses (except for \(\infty\)), and every element in \(R\) has a (tropical) multiplicative inverse.

There is an alternative definition where we define \(T = R \cup \{-\infty\}\) and alter tropical addition to be defined by

\[a \oplus b = \max(a, b).\]

To use the \(\max\) definition, set the argument use_min = False.

Warning

zero() and one() refer to the tropical additive and multiplicative identities respectively. These are not the same as calling T(0) and T(1) respectively as these are not the tropical additive and multiplicative identities respectively.

Specifically do not use sum(...) as this converts \(0\) to \(0\) as a tropical element, which is not the same as zero(). Instead use the sum method:

sage: T = TropicalSemiring(QQ)

sage: sum([T(1), T(2)]) # This is wrong
0
sage: T.sum([T(1), T(2)]) # This is correct
1

Be careful about using code that has not been checked for tropical safety.

INPUT:

  • base – The base ordered additive semigroup \(R\).
  • use_min – (Default: True) If True, then the semiring uses \(a \oplus b = \min(a, b)\); otherwise uses \(a \oplus b = \max(a, b)\)

EXAMPLES:

sage: T = TropicalSemiring(QQ)
sage: elt = T(2); elt
2

Recall that tropical addition is the minimum of two elements:

sage: T(3) + T(5)
3

Tropical multiplication is the addition of two elements:

sage: T(2) * T(3)
5
sage: T(0) * T(-2)
-2

We can also do tropical division and arbitrary tropical exponentiation:

sage: T(2) / T(1)
1
sage: T(2)^(-3/7)
-6/7

Note that “zero” and “one” are the additive and multiplicative identities of the tropical semiring. In other words, they are not \(0 \in R\) and \(1 \in R\) respectively, but instead the (tropical) additive and multiplicative identities \(+\infty\) and \(0\) respectively:

sage: T.zero() + T(3) == T(3)
True
sage: T.one() * T(3) == T(3)
True
Element

alias of TropicalSemiringElement

additive_identity()

Return the (tropical) additive identity element \(+\infty\).

EXAMPLES:

sage: T = TropicalSemiring(QQ)
sage: T.zero_element()
+infinity
gens()

Return the generators of self.

EXAMPLES:

sage: T = TropicalSemiring(QQ)
sage: T.gens()
(1, +infinity)
infinity()

Return the (tropical) additive identity element \(+\infty\).

EXAMPLES:

sage: T = TropicalSemiring(QQ)
sage: T.zero_element()
+infinity
multiplicative_identity()

Return the (tropical) multiplicative identity element \(0\).

EXAMPLES:

sage: T = TropicalSemiring(QQ)
sage: T.one_element()
0
one()

Return the (tropical) multiplicative identity element \(0\).

EXAMPLES:

sage: T = TropicalSemiring(QQ)
sage: T.one_element()
0
one_element()

Return the (tropical) multiplicative identity element \(0\).

EXAMPLES:

sage: T = TropicalSemiring(QQ)
sage: T.one_element()
0
zero()

Return the (tropical) additive identity element \(+\infty\).

EXAMPLES:

sage: T = TropicalSemiring(QQ)
sage: T.zero_element()
+infinity
zero_element()

Return the (tropical) additive identity element \(+\infty\).

EXAMPLES:

sage: T = TropicalSemiring(QQ)
sage: T.zero_element()
+infinity
class sage.rings.semirings.tropical_semiring.TropicalSemiringElement

Bases: sage.structure.element.RingElement

An element in the tropical semiring over an ordered additive semigroup \(R\). Either in \(R\) or \(\infty\). The operators \(+, \cdot\) are defined as the tropical operators \(\oplus, \odot\) respectively.

multiplicative_order()

Return the multiplicative order of self.

EXAMPLES:

sage: T = TropicalSemiring(QQ)
sage: T.one().multiplicative_order()
1
sage: T.zero().multiplicative_order()
+Infinity
class sage.rings.semirings.tropical_semiring.TropicalToTropical

Bases: sage.categories.map.Map

Map from the tropical semiring to itself (possibly with different bases). Used in coercion.

Previous topic

Non Negative Integer Semiring

This Page