Jens Zumbrägel's Website Mathematics and More

# An Introduction to Semirings

Semirings are generalised rings where negative elements do not have to exist. To be more precise, a semiring is a structure (R,+,*) such that (R,+) is a commutative semigroup, (R,*) is a semigroup and such that both distributive laws hold. We also assume the existence of a 0-element, which is neutral in (R,+) and absorbing in (R,*).

Every ring is also a semiring, and we call a semiring that is not a ring a proper semiring. A very prominent example of a proper semiring is the set of the natural numbers N={0,1,2,...} with their usual operations. But here we are interested mainly in finite semirings. The smallest example of a proper semiring with 1 is the so-called Boolean semiring:

```    R2 = {0,1}

+  0 1     *  0 1

0  0 1     0  0 0
1  1 1     1  0 1```

The Boolean semiring is a semifield, i.e. all nonzero elements have a multiplicative inverse. Interestingly, it is the only finite proper semifield. Here is another example of a semiring with 1, with 6 elements (note that the element d is additively absorbing):

```    R6 = {0,1,a,b,c,d}

+  0 a b c 1 d     *  0 a b c 1 d

0  0 a b c 1 d     0  0 0 0 0 0 0
a  a a b c 1 d     a  0 0 0 a a b
b  b b b 1 1 d     b  0 a b a b b
c  c c 1 c 1 d     c  0 0 0 c c d
1  1 1 1 1 1 d     1  0 a b c 1 d
d  d d d d d d     d  0 c d c d d```

The square matrices over a semiring form again a semiring. For example, the 2x2-matrices over the Boolean semiring result in the following semiring with 16 elements.

```    R16 = {0,1,a,b,c,d,e,f,g,h,i,j,k,l,m,n}

+  0 a b c d e 1 f g h i j k l m n     *  0 a b c d e 1 f g h i j k l m n

0  0 a b c d e 1 f g h i j k l m n     0  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a  a a c c e e f f h h j j l l n n     a  0 0 0 0 a a a a b b b b c c c c
b  b c b c 1 f 1 f i j i j m n m n     b  0 a b c 0 a b c 0 a b c 0 a b c
c  c c c c f f f f j j j j n n n n     c  0 a b c a a c c b c b c c c c c
d  d e 1 f d e 1 f k l m n k l m n     d  0 0 0 0 d d d d g g g g k k k k
e  e e f f e e f f l l n n l l n n     e  0 0 0 0 e e e e i i i i n n n n
1  1 f 1 f 1 f 1 f m n m n m n m n     1  0 a b c d e 1 f g h i j k l m n
f  f f f f f f f f n n n n n n n n     f  0 a b c e e f f i j i j n n n n
g  g h i j k l m n g h i j k l m n     g  0 d g k 0 d g k 0 d g k 0 d g k
h  h h j j l l n n h h j j l l n n     h  0 d g k a e h l b 1 i m c f j n
i  i j i j m n m n i j i j m n m n     i  0 e i n 0 e i n 0 e i n 0 e i n
j  j j j j n n n n j j j j n n n n     j  0 e i n a e j n b f i n c f j n
k  k l m n k l m n k l m n k l m n     k  0 d g k d d k k g k g k k k k k
l  l l n n l l n n l l n n l l n n     l  0 d g k e e l l i m i m n n n n
m  m n m n m n m n m n m n m n m n     m  0 e i n d e m n g l i n k l m n
n  n n n n n n n n n n n n n n n n     n  0 e i n e e n n i n i n n n n n```

All semirings displayed so far are congruence-simple, which means that there is no nonzero homomorphism onto some smaller semiring. For rings, being congruence-simple is equivalent to being ideal-simple, and the Wedderburn-Artin-Theorem implies that the finite ideal-simple rings are exactly the matrix rings over finite fields.

Here is another congruence-simple semiring, which consists of 20 elements. It is in fact isomorphic to the endomorphism semiring of the monoid ({0,1,2,3},max).

```R20 = {0,1,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r}

+  0 a b c d e f g h i j k l m 1 n o p q r    *  0 a b c d e f g h i j k l m 1 n o p q r

0  0 a b c d e f g h i j k l m 1 n o p q r    0  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
a  a a b c d e f g h i j k l m 1 n o p q r    a  0 0 0 0 0 0 0 0 0 0 a a a a a a b b b c
b  b b b c e e f g h i k k l m 1 n o p q r    b  0 0 0 0 a a a b b c a a a b b c b b c c
c  c c c c f f f h h i l l l 1 1 n p p q r    c  0 a b c a b c b c c a b c b c c b c c c
d  d d e f d e f g h i j k l m 1 n o p q r    d  0 0 0 0 0 0 0 0 0 0 d d d d d d g g g i
e  e e e f e e f g h i k k l m 1 n o p q r    e  0 0 0 0 a a a b b c d d d e e f g g h i
f  f f f f f f f h h i l l l 1 1 n p p q r    f  0 a b c a b c b c c d e f e f f g h h i
g  g g g h g g h g h i m m 1 m 1 n o p q r    g  0 0 0 0 d d d g g i d d d g g i g g i i
h  h h h h h h h h h i 1 1 1 1 1 n p p q r    h  0 a b c d e f g h i d e f g h i g h i i
i  i i i i i i i i i i n n n n n n q q q r    i  0 d g i d g i g i i d g i g i i g i i i
j  j j k l j k l m 1 n j k l m 1 n o p q r    j  0 0 0 0 0 0 0 0 0 0 j j j j j j o o o r
k  k k k l k k l m 1 n k k l m 1 n o p q r    k  0 0 0 0 a a a b b c j j j k k l o o p r
l  l l l l l l l 1 1 n l l l 1 1 n p p q r    l  0 a b c a b c b c c j k l k l l o p p r
m  m m m 1 m m 1 m 1 n m m 1 m 1 n o p q r    m  0 0 0 0 d d d g g i j j j m m n o o q r
1  1 1 1 1 1 1 1 1 1 n 1 1 1 1 1 n p p q r    1  0 a b c d e f g h i j k l m 1 n o p q r
n  n n n n n n n n n n n n n n n n q q q r    n  0 d g i d g i g i i j m n m n n o q q r
o  o o o p o o p o p q o o p o p q o p q r    o  0 0 0 0 j j j o o r j j j o o r o o r r
p  p p p p p p p p p q p p p p p q p p q r    p  0 a b c j k l o p r j k l o p r o p r r
q  q q q q q q q q q q q q q q q q q q q r    q  0 d g i j m n o q r j m n o q r o q r r
r  r r r r r r r r r r r r r r r r r r r r    r  0 j o r j o r o r r j o r o r r o r r r```

These are in fact the smallest congruence-simple proper semirings, together with another semiring: the zero-multiplication ring of size 2. The next semiring in the row has already 42 elements. Despite of this sparsity of congruence-simple semirings, there are plenty of general semirings, as can be seen in the following table.

```                    all        congruence-simple
size   semirings   rings    semirings rings

2            4      2          4       2
3           22      2          2       2
4          283     11          1       1
5        4'717      2          2       2
6      108'992      4          1       0
7    8'925'672      2          2       2
2...7  9'039'691     23         12       9```

A classification of all finite proper congruence-simple semirings can be given with the help of lattices.

## Lattices and Semirings

A lattice is an ordered set (L,≤) in which every pair of elements has both a supremum and an infimum in L. They can be depicted by order diagrams, which show only the covering pairs (y covers x iff x<y and there is no z with x<z<y).

The supremum operation converts the lattice into a commutative idempotent semigroup, which is in the finite case even a monoid. Conversely, every commutative idempotent monoid (L,+) gives rise to an ordered set (L,≤) by defining x≤y iff x+y=y, which turns out to be a lattice.

Let L be a lattice with supremum operation ∨. Then the endomorphisms End(L,∨) of the monoid (L,∨) is naturally a semiring, and these semirings are congruence-simple. On the other hand, the following statement can be proven (see arXiv:math/0702416):

 Theorem. Let R be a finite proper congruence-simple semiring with nonzero multiplication. Then R is isomorphic to a 'dense' subsemiring S of the endomorphism semiring End(L,∨) of some lattice L. (Here, a subsemiring S⊆End(L,∨) is called 'dense' if every endomorphism f∊End(L,∨) with |Im f|≤2 is contained in S.)

The following table displays the diagrams of the smallest lattices (with at least 2 elements) together with the corresponding congruence-simple semirings, according to the above theorem. We write Rn for a semiring with n elements.

 R2(the Boolean semiring) R6 R20(the 2x2-matrices over R2) R16 R70 R50,a R50,b R43, R42 R50,c, R47, R46,a, R46,b, R46,c R45, R44 (where R46,a,R46,b,R46,c are isomorphic)

One can also prove that a lattice L corresponds to only one congruence-simple semiring (namely its full endomorphism semiring End(L,∨)) if and only if the lattice L is distributive.