Given a semiring $S$, we get a monoid $M(S)$ as follows:

  • The underlying set of $S$ is $S^2$
  • The identity element is $(0,1)$
  • The law of composition is given by $$(a,A)(b,B) = (Ba+b,AB),$$ where $a,A,b$ and $B$ range over the semiring $S$.

Let's refer to the $M(S)$ as the semidirect monoid of $S$. (See below for motivation.)

Question. Where can I learn more about these monoids? Are they studied anywhere?

Motivation 0. I originally "invented" the above formula due to its connection with positional notation for numbers. Here's an example computation that should hopefully illustrate the idea: $$\begin{align*}(3,10)(6,10)(5,10) &= (30+6,100)(5,10) \\ &= (300+60+5,1000) \\ &= (365,1000) \end{align*} $$

So the number $365$ can be obtained by first taking the numbers $3$, $6$ and $5$, putting them in place of the $\Box$ symbol in the expression $(\Box,10)$ to obtain $(3,10),(6,10)$ and $(5,10)$, then multiplying these pairs in the monoid $M(\mathbb{N})$ and discarding the second entry.

This works for any base, even negative ones, and gives convenient notation for those situations where the base needs to change from one column to the next.

Motivation 1.

The operation also appears naturally when thinking about expanding out products of disjoint unions of sets. Suppose we expand out the product $$(X_0+X_1)(Y_0+Y_1) \cong X_0(Y_0+Y_1)+X_1(Y_0+Y_1) \cong X_0Y_0 + X_0Y_1 + X_1Y_0 + X_1Y_1.$$

We end up with four terms. Let's label them with the elements of the set $\{0,1,2,3\}.$ For example, $X_0Y_0$ would be in position $0$.

Now let's ask the question, in which position does $X_1Y_0$ wind up? Well, just compute: $$(1,2)(0,2) = (2+0,4) = (2,4).$$

So it should end up in position $2$, which it does.

In a similar vein: if we have a list of length $A$, the entries of which are lists of length $B$, the entries of which are lists of length $C$, then to work out where the item at location $(a,b,c)$ will end up once we flatten the list, we just compute $$(a,A)(b,B)(c,C).$$

Motivation 2.

A few hours ago, I noticed (essentially) the same formula appear on the page about the Poincare group.

This got me a bit excited. Here's the key observation:

Given monoids $P$ and $Q$ and a homomorphism $\varphi : P \rightarrow \mathrm{End}(Q),$ we can define that the outer semidirect product of $P$ and $Q$ across $\varphi$ to be the following monoid:

  • The underlying set is $Q \times P$
  • The identity element is $(1,1)$
  • The law of composition is given by $$(a,A)(b,B) = (\varphi(B)(a)b,AB),$$ where $a,A,b$ and $B$ range over the semiring $S$.

(Note that I've changed the definition slightly from the standard group-theoretic one to get the opposite monoid from the one that would be obtained had the definition just been copied and pasted. This is to make semidirect products fit more cleanly with what I wrote above.)

Given a semiring $S$, the important observation is that the monoid $M(S)$ is the semidirect product of $(S,+,0)$ and $(S,\times,1)$ across the function $\varphi : (S,\times,1) \rightarrow \mathrm{End}(S,+,0)$ given by $\varphi(B) = (a \mapsto Ba).$

  • 2
    $\begingroup$ This is semidirect product of the additive and multiplicative reducts is pretty standard. In the case of a ring this is just the monoid of mappings x goes to ax+b. This mapping representation is not faithful necessarily for semirings. $\endgroup$ – Benjamin Steinberg Dec 25 '18 at 11:20
  • $\begingroup$ @BenjaminSteinberg, I don't quite understand your first sentence. Can you elaborate? $\endgroup$ – goblin Dec 25 '18 at 13:08
  • $\begingroup$ @BenjaminSteinberg, your $ax+b$ comment seems very interesting by the way. Write $f;g$ for $g \circ f$. Then on the basis of your comment, if we have an $A$-long list of $B$-long lists of $C$-long lists, then to find the index of the item $(a,b,c)$ after we flatten the whole thing, we can just compute the composite $(A\Box+a);(B\Box+b);(C\Box+c).$ $\endgroup$ – goblin Dec 25 '18 at 13:51
  • $\begingroup$ Your multiplicative monoid acts on the additive monoid and you are forming the semidirect product. This is a standard construction. If the additive part of the semiring is cancellative this is isomorphic to the ax+b monoid but if, for example. The additive monoid has an absorbing element $\infty$ then $ax+\infty$ acts the same as $bx+\infty$ but the corresponding elements of your semidirect product are different. $\endgroup$ – Benjamin Steinberg Dec 25 '18 at 15:00
  • $\begingroup$ @BenjaminSteinberg, yeah, I got that. I was just a bit confused by the structure of your first sentence, but I think I get it now (just a typo). Btw we can make this representation faithful by using formal polynomials instead of literal endofunction, though I guess technically it's no longer a representation at this point. I guess my next question is, do you know anywhere I can learn about this construction? Especially in light of my specific interests, such as non-standard positional number systems and/or finding useful names for locations. $\endgroup$ – goblin Dec 26 '18 at 8:22

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.