# Semiring analogies

Sigfpe has been posting on his blog about one of my minor obsessions, semirings. A semiring is a ring without subtraction. There are lots of semirings that arise in both pure and applied mathematics. Here are some examples that show just how common they are:

• Any collection of sets closed under union and intersection form a semiring, with union as addition and intersection as multiplication (or vice versa).
• Regular languages form a semiring. The sum of two regular languages is the union, while the product is juxtaposition.
• The reals with positive infinity added form a semiring where the “sum“ of two numbers is the minimum, and the “product“ is addition. (Including positive infinity is not strictly necessary, but it serves as a “zero“ for the min operation). This known as the min-plus semiring.

The last example has an interesting extra property: you can take infinite “sums“ by taking the infimum of an infinite set of elements. You can set up an extended analogy between the reals with usual arithmetic operations and the min-plus semiring. In this analogy, integration becomes optimization. You can even extend the analogy as far as the Fourier transform. The min-plus analogue of the Fourier transform is the Legendre transform that arises in classical mechanics. Sigfpe explains the analogy here.

He has also posted about an application of semirings to understanding the game Tetris.

## 4 thoughts on “Semiring analogies”

1. By the way, John Baez occasionally talks about semirings in This Week’s Finds but it doesn’t show up in web searches as he calls them rigs. The Classical/Quantum analogy came from there but I can’t find the exact link again, even with Google.

Anyway…I’m beginning to get obsessed with semirings myself…

2. Strictly speaking, in the third example you have to take infinite _infima_, not suprema; you have also to add a minus infinity to ensure they exist (or restrict to bounded sets). With the latter provision (summing only bounded infinite subsets) all three examples you give enjoy the “easy summability” property. This observation has been systematically developed by the French school (where sigfpe’s knowledge comes from) and by Russians including [Grigory Litvinov](http://arxiv.org/abs/math/0009128).

The subject is indeed fascinating, and therefore it has been rediscovered several times under different names. The most recent incarnation is called “tropical math” and deals mostly with algebraic geometry; the idea is basically that max-plus algebraic geometry deals with convex polygones instead of algebraic curves. There is a little known [arXiv article](http://arxiv.org/abs/math/0005163) by Oleg Viro, which makes for a very good and readable introduction into the “tropical algebraic geometry.” More recent literature can easily be found in arXiv if you look for keywords such as “tropical” and “amoeba”; I also keep a bibliography [at CiteULike](http://www.citeulike.org/user/ansobol/tag/tropical); sorry for the plug

A very complete bibliography up to the late 1990s exists at [StÃ©phane Gaubert’s site](http://amadeus.inria.fr/gaubert/PAPERS/abstract/abstract.html), but it does not cover the most recent “tropical” development.

3. Oops. I initially started with max-plus, but when I saw that sigfpe was min-plus, I changed it (but apparently not quite everywhere). Now fixed.

Comments are closed.