`IsSemiring` is not a semiring?

[markuspf]

In GAP according to the documentation and the code IsSemiring is defined as an additive magma that is also a magma, and multiplication distributes over addition. In particular neither addition, nor multiplication are assumed to be associative.

I wonder whether there is a case to rename this filter and de-capture the notion of semiring. This is of course only possible if we do not break too much code written by other people (a quick grep through installed packages suggests that only the library, Homalg, and one of my (as yet unpublished packages) do.

Otherwise I'll have to invent a different name for semirings, or abuse GAP's filter in some way, both options don't seem very attractive.

[fingolfin]

Indeed, usually in mathematics, a semiring is a ring without the requirement that additive elements have additive inverses. And I think that's precisely the concept we had in mind for use in MatrixObj...

I think we actually have a chance at renaming IsSemiring because (a) it is actually undocumented, and (b) almost nothing uses it. And those few places that uses it (outside of lib/semiring.gd) actually seem to be written under the wrong assumption that IsSemiring corresponds to the usual mathematical concept:

• code in lib/cyclotom.gi for comparing certain sets of cyclotomics, such as PositiveIntegers and NonnegativeIntegers etc.: I wrote that, and I am pretty sure I had the mathematical meaning in mind
• also this:

  lib/integer.gd:43:DeclareCategory( "IsPositiveIntegers", IsSemiringWithOne );
  lib/integer.gd:45:DeclareCategory( "IsNonnegativeIntegers", IsSemiringWithOneAndZero );

• we use IsSemiring in the MatrixObj interface, but as I already mentioned, I think we had the "standard" concept in mind
• the semigroups package has code dealing with matrices over semirings in its semiringmat.gi and mentions tropical rings as example, so I think this also supposes the "usual" meaning
• MatricesForHomalg checks IsSemiringWithOneAndZero in one place. not sure what that's about

CC @ThomasBreuer

[fingolfin]

Note there are slightly differing notions of "semiring" in the literature, depending on whether one requires the existence of units for addition and/or multiplication; and whether one require commutativity for addition or not. Some references:

• https://en.wikipedia.org/wiki/Semiring
• https://encyclopediaofmath.org/wiki/Semi-ring
• https://proofwiki.org/wiki/Definition:Semiring_(Abstract_Algebra)

But all definitions I could find had one thing in common: associativity is required for both + and *, whereas in the GAP definition, this is not the case.

Given the circumstances I described in my previous comment, we might actually be able to get away with changing the definition of IsSemiring (just need to decide to what).

[wilfwilson]

Summary: changing the definition of IsSemiring to require associativity would not affect the Semigroups package (cc @james-d-mitchell).

The Semigroups package allows for the construction of, and computation with, semigroups generated by matrices whose entries 'come from' one of only a few kinds of semirings. These are listed in Chapter 5 of the manual, and in particular all of the semirings are associative. Indeed, I don't think it would make sense to make a semigroup out of matrices over a non-associative semirings.

(Note that the Semigroups package doesn't actually introduce any new semiring objects, as far as I am aware; the actual entries of the matrices are integers or ±infinity; we just additionally tell the matrix how those elements should be interpreted; matrix multiplication then does the appropriate thing.)

The semirings 'in' the Semigroups packages all have additive and multiplicative identities, and are commutative under both operations, so will not be affected if we make a decision in this regard, either. But in general, an element has neither an additive nor a multiplicative inverse.

[wilfwilson]

For the record, note that @markuspf took the first steps towards making a "Semirings" package https://github.com/gap-packages/semirings at the same time as creating this issue.

[wilfwilson]

I was about to comment that I believe that we should make IsSemiring require its operations to be associative, and probably that is as far as we should go.

I would also want to require that the addition be commutative (because addition operations in GAP always seem to be commutative!), and that there is a zero element, but if there seem to be people using semirings that do not have these properties, then we should not require them.

But, from https://www.gap-system.org/Manuals/doc/ref/chap56.html#X80FD843C8221DAC9 (uh oh):

A ring in GAP is an additive group (see IsAdditiveGroup (55.1-6)) that is also a magma (see IsMagma (35.1-1)), such that addition + and multiplication * are distributive, see IsDistributive (56.4-5).

The multiplication need not be associative (see IsAssociative (35.4-7)). For example, a Lie algebra (see 64) is regarded as a ring in GAP.

This was a surprise to me. This means this we wouldn't be able to have the implication IsRing => IsSemiring.

[wilfwilson]

I think we’re all agreed that we can, and should, change IsSemiring, and document it. Additive associativity seems uncontroversial. So the first question after that is: do we require multiplicative associativity too and therefore break consistency withIsRing, or not?