2
$\begingroup$

A semiring is a structure $(R, +, 0, *)$ such that $(R, +, 0)$ is a commutative monoid, $(R, *, 0)$ is a semigroup with zero, and the distributive laws hold.

I know that there were attempts at computing semigroups of small order, and all semigroups up to order $8$ has been computed. Was there a similar attempt at computing semirings of small orders? If yes, where can I find results of that?

$\endgroup$

2 Answers 2

3
$\begingroup$

Andrej Bauer's program alg exists to calculate these sorts of numbers, it will also output the addition and multiplication tables for finite algberaic structures too. If you look at the file theories/semiring.th there you'll see the axioms it assumes for a semiring

Theory semiring.

Constant 0.
Binary + *.

Axiom: 0 + x = x.
Axiom: x + 0 = x.
Axiom: x + (y + z) = (x + y) + z.
Axiom: x + y = y + x.
Axiom: x * (y * z) = (x * y) * z.
Axiom: (x + y) * z = x * z + y * z.
Axiom: x * (y + z) = x * y + x * z.
Axiom: 0 * x = 0.
Axiom: x * 0 = 0.

I just ran this on my computer up to size six, up to five is fairly quick if you consider the number of structures it is processing, but as you can see the numbers are getting large, and if you consider the number of possible pairs of binary operations on a set of size 7, there are a lot to consider, even if some are easy to see that they fail. Edit: I left it longer overnight and the output is now:

# Statistics

    size | count
    -----|------
       1 | 1
       2 | 4
       3 | 22
       4 | 283
       5 | 4717
       6 | 109010

But this sequence is not in the oeis so I have no idea how to find more terms, except by computing further, seven might take a while!

Edit in response to a further question in comments:

I just installed alg again and using the following theory

# A unital semiring is like a unital ring without subtraction.

Theory unital_semiring.

Constant 0 1.
Binary + *.

Axiom: 0 + x = x.
Axiom: x + 0 = x.
Axiom: x + (y + z) = (x + y) + z.
Axiom: x + y = y + x.

Axiom: 1 * x = x.
Axiom: x * 1 = x.
Axiom: x * (y * z) = (x * y) * z.

Axiom: (x + y) * z = x * z + y * z.
Axiom: x * (y + z) = x * y + x * z.

Axiom: 0 * x = 0.
Axiom: x * 0 = 0.

I get

size | count
-----|------ 
    1 | 0
    2 | 2
    3 | 6
    4 | 40
    5 | 295
       6 | 3246
$\endgroup$
5
  • $\begingroup$ I'm not very computer savvy and this seems pretty difficult to install, especially on Windows. :( $\endgroup$
    – Jakobian
    Dec 31, 2020 at 18:54
  • $\begingroup$ When restricting your definition to the notion of "semiring" which also have a multiplicative identity (a.k.a. "rig"), I also can't google a sequence on oeis. Do you happen to have the program still set up to query the structures for the first four or five cases? $\endgroup$
    – Nikolaj-K
    Jan 14 at 14:43
  • $\begingroup$ @Nikolaj-K I have edited my answer above to include the unital case, its also not on oeis, are the axioms I used the ones you were thinking of? $\endgroup$ Jan 16 at 14:08
  • $\begingroup$ @AlexJBest That's great, thanks a bunch! Really curious that those numbers don't seem to be online somewhere. $\endgroup$
    – Nikolaj-K
    Jan 16 at 21:24
  • 1
    $\begingroup$ @Nikolaj-K Yes indeed the only place I could find them was math.chapman.edu/~jipsen/structures/… (the page sometimes fails to load for me, web.archive.org/web/20230926120523/https://math.chapman.edu/… is an archive link) $\endgroup$ Jan 17 at 17:52
0
$\begingroup$

This is not a complete answer to your question, but I will sketch a method to construct finite semirings (of small orders).

Since you are interested in semirings of small orders, one strategy would be embedded them into some class of universal semirings via some Cayley’s type representation theorem. For examples:

  • if you want to know all groups of order less than some small $n,$ you can do so by looking at subgroups of the symmetric group $S_n.$

  • For semigroups of order less than $n,$ you can look at sub-semigroups of symmetric semigroup of endomorphisms of a set (the set of functions to itself) with $n$ elements. The semigroup (in fact, a monoid) of such transformations is of order $n^n,$ and therefore become extermly large with $n.$

There are similar such theorems for other algebraic structures (such as Boolean algebras, categories, ...) as well. Now lets formulate a representation theorem for semirings.

Given a semiring $R,$ additive semigroup endomorphism of $R$ denoted by $\mathbf{End}(R)$ form a semiring under pointwise addition, composition and zero map. Furthermore, there is an injective semiring homomorphism $\Phi : R\hookrightarrow\mathbf{End}(R)$ given by $\Phi(r)(a)=\varphi_r(a)=ra$ for all $a, r\in R,$ and here $\varphi_r\in\mathbf{End}(R).$

It is not difficult to prove this result. Note that we can construction the semiring $\mathbf{End}(R)$ only using the additive structure of $R.$ In other words, any semiring is isomorphic to a sub-semiring of endomorphisms of a semigroup. Now since you have a classification all semigroups up to order $8,$ you can perform this construction to find some semirings up to there.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .