Tropical semiring

Definition

The min tropical semiring (or min-plus semiring or min-plus algebra) is the semiring (\mathbb{R} \cup {+\infty}, \oplus, \otimes), with the operations: : x \oplus y = \min{x, y }, : x \otimes y = x + y. The operations \oplus and \otimes are referred to as tropical addition and tropical multiplication respectively. The identity element for \oplus is +\infty, and the identity element for \otimes is 0.

Similarly, the max tropical semiring (or max-plus semiring or max-plus algebra or arctic semiring) is the semiring (\mathbb{R} \cup {-\infty}, \oplus, \otimes), with operations:

: x \oplus y = \max{x, y }, : x \otimes y = x + y. The identity element unit for \oplus is -\infty, and the identity element unit for \otimes is 0.

The two semirings are isomorphic under negation x \mapsto -x, and generally one of these is chosen and referred to simply as the tropical semiring. Conventions differ between authors and subfields: some use the min convention, some use the max convention.

The two tropical semirings are the limit ("tropicalization", "dequantization") of the log semiring as the base goes to infinity (max-plus semiring) or to zero (min-plus semiring).

Tropical addition is idempotent, thus a tropical semiring is an example of an idempotent semiring.

A tropical semiring is also referred to as a tropical algebra, though this should not be confused with an associative algebra over a tropical semiring.

Tropical exponentiation is defined in the usual way as iterated tropical products.

Valued fields

Main article: Valued field

The tropical semiring operations model how valuations behave under addition and multiplication in a valued field. A real-valued field K is a field equipped with a function : v:K \to \R \cup {\infty} which satisfies the following properties for all a, b in K: : v(a) = \infty if and only if a = 0, : v(ab) = v(a) + v(b) = v(a) \otimes v(b), : v(a + b) \geq \min{v(a), v(b) } = v(a) \oplus v(b), with equality if v(a) \neq v(b). Therefore the valuation v is almost a semiring homomorphism from K to the tropical semiring, except that the homomorphism property can fail when two elements with the same valuation are added together.

Some common valued fields:

• \Q or \C with the trivial valuation, v(a)=0 for all a\neq 0,
• \Q or its extensions with the p-adic valuation, v(p^na/b)=n for a and b coprime to p,
• the field of formal Laurent series K((t)) (integer powers), or the field of Puiseux series K{{t}}, or the field of Hahn series, with valuation returning the smallest exponent of t appearing in the series.

References

References

1. Pin, Jean-Éric. (1998). "Idempotency". [[Cambridge University Press]].
2. Perrin, D.. (June 1992). "Automata Theory: Infinite Computations". Schloss Dagstuhl.
3. (2009). "Tropical and Idempotent Mathematics: International Workshop Tropical-07, Tropical and Idempotent Mathematics". American Mathematical Society.