Small semirings

Small semirings

[Andrej Bauer]

Dear categorists,

I have no idea where to ask the following algebra question. Hoping that 
some of you are algebraists, I am asking it here.

I am looking for examples of small (finite and with few elements, say up 
to 8) commutative semirings with unit, by which I mean an algebraic 
structure which has +, *, 0 and 1, both operations are commutative and * 
distributes over +. The initial such structure are the natural numbers.

Here are the examples I know:

1) Modular arithmetic, i.e., (Z_n, +, *, 0, 1)

2) Distributive lattices with 0 and 1.

3) "Cut-off" semiring, in which we compute like with natural numbers, 
but if a value exceeds a given constant N, then we cut it off at N. For 
example, if N = 7 then we would have 3 + 3 = 6, 3 + 6 = 7, 4 * 4 = 7, 
etc. Do such semirings have a name?

There must be a census of small commutative rings, or even semirings. 
Does anyone know?

Andrej

Re: Small semirings

[Josh Nichols-Barrer]

Hi Andrej,

Here are some odds and ends:

You can build a semiring from any semiring R with no nonzero additive 
inverses by attaching an element at infinity (\infty+x = \infty for all x 
and and \infty * x = \infty for nonzero x).  Iterating this, you can have 
a hierarchy of elements at infinity, I suppose.  For example, take your 
cutoff semiring and add an element at infinity; this gives some new 
specimens.

More generally, you can use finitely generated semirings (over a given 
finite semiring, for example).  The above construction would be the 
quotient of R[x] where every polynomial of degree greater than 0 is 
identified with x.

For another example, any finite linearly ordered commutative monoid is 
naturally a semiring, where the addition is max and the multiplication is 
given by the monoid law.  For example, "cutoff monoids" of N.  This 
example is somehow lifted from tropical geometry, which is (speculatively) 
relative algebraic geometry over the semiring R\cup {-\infty}, where 
R here denotes the reals, the addition law is max and the multiplication 
is addition in R.

Maybe a easier question is what are the "minimal" finite semirings, for 
some appropriate notion of minimal.  I'm thinking something analogous to 
the notion of field for rings, although even to classify the finite fields 
takes a bit of clever work...

Here is a different approach to the question (after a conversation with K. 
Kedlaya):

Given a semiring R, you can "mod out by elements with additive inverses" 
by identifying a and b whenever there are x and y with a+x=b and b+y=a.  
This produces a new semiring R' where no element other than 0 has an 
additive inverse; the operation kills all rings and fixes distributive 
lattices and cutoff semirings.  The resulting semiring has a natural 
ordering, namely a <= b iff there is an x with a+x = b (so that 0 is the 
least element).  I don't know what to call these, maybe ordered semirings?

As a next step, you can take an ordered semiring R as above and identify 1 
with 2 to produce something even simpler.  We still have a partial 
ordering, of course, and moreover addition is join: if b <= a and c <= a, 
then b+c <= a+a = a.  This does nothing to distributive lattices or the 
ordered commutative monoids above, but it turns cutoff semirings into the 
semiring with elements {0,1} and 1+1=1.  You might call these "tropical 
semirings."

Finally, you might want to transform the multiplication in a tropical 
semiring R into meet.  I guess this would be done by identifying 
everything greater than or equal to 1 with 1, and then identifying x^2 
with x for each x.

Summarizing, I guess, the forgetful functors

BddDistLat --> TropSemiRing --> OrdSemiring --> Semiring

all seem to have left adjoints.  Maybe another way to look into semirings 
would be to study the fibres of the left adjoints?  The adjunction between 
bounded distributive lattices and tropical semirings already looks 
interesting...

Another thing that would be cool to see would be a duality theory for 
tropical semirings, maybe like the duality theory for bounded distributive 
lattices, as a way to get a handle on tropical semirings at least...  Of 
course, what I'd really like to see is a geometric picture of Spec R for 
any semiring R, but that might take a little more work...

Best,
Josh

On Wed, 3 Jan 2007, Andrej Bauer wrote:

> Dear categorists,
> 
> I have no idea where to ask the following algebra question. Hoping that
> some of you are algebraists, I am asking it here.
> 
> I am looking for examples of small (finite and with few elements, say up
> to 8) commutative semirings with unit, by which I mean an algebraic
> structure which has +, *, 0 and 1, both operations are commutative and *
> distributes over +. The initial such structure are the natural numbers.
> 
> Here are the examples I know:
> 
> 1) Modular arithmetic, i.e., (Z_n, +, *, 0, 1)
> 
> 2) Distributive lattices with 0 and 1.
> 
> 3) "Cut-off" semiring, in which we compute like with natural numbers,
> but if a value exceeds a given constant N, then we cut it off at N. For
> example, if N = 7 then we would have 3 + 3 = 6, 3 + 6 = 7, 4 * 4 = 7,
> etc. Do such semirings have a name?
> 
> There must be a census of small commutative rings, or even semirings.
> Does anyone know?
> 
> Andrej
> 

Small semirings

[Vaughan Pratt]

Example (1) of section 3.2 of "Temporal Structures", MSCS 1:2 179-213 
(1991), also at http://boole.stanford.edu/pub/man.pdf, enumerates the 
commutative semirings both of whose operations are idempotent (thus 
defining two partial orders), with the additive order furthermore being 
linear.  We showed there are 2^{n-2} of these having n elements, and 
indicated where the first three (those with n = 2 or 3) have previously 
appeared in the literature.

Interestingly the linearity of the additive order implies that of the 
multiplicative order.  Once this has been shown it is an easy step to 
the following pleasant representation.

Start with an n-element chain, n>1, viewed as a string of n beads with 0 
at the bottom.  Select any nonzero element as the (multiplicative) unit, 
and then determine the multiplication by allowing the portions of the 
string on either side of the unit to dangle down, with the beads 
interleaving arbitrarily subject to 0 remaining below the rest.  One can 
then readily show that there are 2^{n-2} choices for the unit and 
multiplication.

For each n exactly one of these is a Heyting algebra (example 2 of 
Andrej's list), namely the one for which the additive top was selected 
as the unit.  (So for n = 2 or 3 only the one non-Heyting semiring will 
be at all unfamiliar.)  I would be interested to hear of appearances in 
the literature of any of the three non-Heyting such with four elements.

As a class exercise around 1989 I assigned the enumeration problem for 
various weakenings of these conditions, which I can't locate right now 
though Ken Ross, kar at cs columbia edu, might conceivably have kept a 
record.

Vaughan Pratt

Andrej Bauer wrote:
> Dear categorists,
> 
> I have no idea where to ask the following algebra question. Hoping that
> some of you are algebraists, I am asking it here.
> 
> I am looking for examples of small (finite and with few elements, say up
> to 8) commutative semirings with unit, by which I mean an algebraic
> structure which has +, *, 0 and 1, both operations are commutative and *
> distributes over +. The initial such structure are the natural numbers.
> 
> Here are the examples I know:
> 
> 1) Modular arithmetic, i.e., (Z_n, +, *, 0, 1)
> 
> 2) Distributive lattices with 0 and 1.
> 
> 3) "Cut-off" semiring, in which we compute like with natural numbers,
> but if a value exceeds a given constant N, then we cut it off at N. For
> example, if N = 7 then we would have 3 + 3 = 6, 3 + 6 = 7, 4 * 4 = 7,
> etc. Do such semirings have a name?
> 
> There must be a census of small commutative rings, or even semirings.
> Does anyone know?
> 
> Andrej

re: Small semirings

[Marco Grandis]

This site lists a lot of algebraic structures and often gives  
information on finite examples:

     http://math.chapman.edu/cgi-bin/structures

-----
Thus, for commutative rings (with 1) you have:

http://math.chapman.edu/structuresold/files/ 
Commutative_rings_with_identity.pdf

where you can find that there are:

- 1 structure with 1 element (or 2, 3, 5, 6 elements)
- 4 structures with 4 elements.

-----
The case of semirings is not (yet?) much developed: just a few  
results and trivial examples.
See:

http://math.chapman.edu/structuresold/files/ 
Semirings_with_identity_and_zero.pdf
http://math.chapman.edu/structuresold/files/Semirings_with_zero.pdf

-------
Commutative semirings are not in the list, I think.

Marco Grandis


On 3 Jan 2007, at 23:09, Andrej Bauer wrote:

> Dear categorists,
>
> I have no idea where to ask the following algebra question. Hoping  
> that
> some of you are algebraists, I am asking it here.
>
> I am looking for examples of small (finite and with few elements,  
> say up
> to 8) commutative semirings with unit, by which I mean an algebraic
> structure which has +, *, 0 and 1, both operations are commutative  
> and *
> distributes over +. The initial such structure are the natural  
> numbers.
>
> Here are the examples I know:
>
> 1) Modular arithmetic, i.e., (Z_n, +, *, 0, 1)
>
> 2) Distributive lattices with 0 and 1.
>
> 3) "Cut-off" semiring, in which we compute like with natural numbers,
> but if a value exceeds a given constant N, then we cut it off at N.  
> For
> example, if N = 7 then we would have 3 + 3 = 6, 3 + 6 = 7, 4 * 4 = 7,
> etc. Do such semirings have a name?
>
> There must be a census of small commutative rings, or even semirings.
> Does anyone know?
>
> Andrej
>
>
>