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
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
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
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
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
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
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
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
participants (4)
-
Andrej Bauer -
Josh Nichols-Barrer -
Marco Grandis -
Vaughan Pratt