min-plus algebra
   HOME

TheInfoList



OR:

In idempotent analysis, the tropical semiring is a
semiring In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse. The term rig is also used occasionally—this originated as a joke, suggesting that rigs ar ...
of
extended real numbers In mathematics, the affinely extended real number system is obtained from the real number system \R by adding two infinity elements: +\infty and -\infty, where the infinities are treated as actual numbers. It is useful in describing the algebra on ...
with the operations of
minimum In mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, either within a given r ...
(or
maximum In mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, either within a given r ...
) and addition replacing the usual ("classical") operations of addition and multiplication, respectively. The tropical semiring has various applications (see
tropical analysis In the mathematical discipline of idempotent analysis, tropical analysis is the study of the tropical semiring. Applications The max tropical semiring can be used appropriately to determine marking times within a given Petri net and a vector fil ...
), and forms the basis of
tropical geometry In mathematics, tropical geometry is the study of polynomials and their geometric properties when addition is replaced with minimization and multiplication is replaced with ordinary addition: : x \oplus y = \min\, : x \otimes y = x + y. So f ...
. The name ''tropical'' is a reference to the Hungarian-born computer scientist
Imre Simon Imre Simon (August 14, 1943 – August 13, 2009) was a Hungarian-born Brazilian mathematician and computer scientist. His research mainly focused on theoretical computer science, automata theory, and tropical mathematics, a subject he founded, ...
, so named because he lived and worked in Brazil.


Definition

The ' (or or ) is the
semiring In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse. The term rig is also used occasionally—this originated as a joke, suggesting that rigs ar ...
(ℝ ∪ , ⊕, ⊗), with the operations: : x \oplus y = \min\, : x \otimes y = x + y. The operations ⊕ and ⊗ are referred to as ''tropical addition'' and ''tropical multiplication'' respectively. The unit for ⊕ is +∞, and the unit for ⊗ is 0. Similarly, the ' (or or or ) is the semiring (ℝ ∪ , ⊕, ⊗), with operations: : x \oplus y = \max\, : x \otimes y = x + y. The unit for ⊕ is −∞, and the unit for ⊗ 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. Tropical addition is
idempotent Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...
, thus a tropical semiring is an example of an
idempotent semiring In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse. The term rig is also used occasionally—this originated as a joke, suggesting that rigs ar ...
. A tropical semiring is also referred to as a , 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 (see ).


Valued fields

The tropical semiring operations model how valuations behave under addition and multiplication in a
valued field Value or values may refer to: Ethics and social * Value (ethics) wherein said concept may be construed as treating actions themselves as abstract objects, associating value to them ** Values (Western philosophy) expands the notion of value beyo ...
. A real-valued field ''K'' is a field equipped with a function : v \colon K \to \mathbb \cup \ 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) \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'' ≠ 0, * Q or its extensions with the
p-adic valuation In number theory, the valuation or -adic order of an integer is the exponent of the highest power of the prime number that divides . It is denoted \nu_p(n). Equivalently, \nu_p(n) is the exponent to which p appears in the prime factorization of ...
, ''v''(''p''''n''''a''/''b'') = ''n'' for ''a'' and ''b'' coprime to ''p'', * the field of
formal Laurent series In mathematics, a formal series is an infinite sum that is considered independently from any notion of convergence, and can be manipulated with the usual algebraic operations on series (addition, subtraction, multiplication, division, partial sum ...
''K''((''t'')) (integer powers), or the field of
Puiseux series In mathematics, Puiseux series are a generalization of power series that allow for negative and fractional exponents of the indeterminate. For example, the series : \begin x^ &+ 2x^ + x^ + 2x^ + x^ + x^5 + \cdots\\ &=x^+ 2x^ + x^ + 2x^ + x^ + ...
''K'', or the field of
Hahn series In mathematics, Hahn series (sometimes also known as Hahn–Mal'cev–Neumann series) are a type of formal infinite series. They are a generalization of Puiseux series (themselves a generalization of formal power series) and were first introduced ...
, with valuation returning the smallest exponent of ''t'' appearing in the series.


References

* {{refend
Semiring In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse. The term rig is also used occasionally—this originated as a joke, suggesting that rigs ar ...