The n-Category Café

I should probably wait for Ben Steinberg to turn up and say something informed; but in my limited understanding, based on the days when I used to spend more time messing around with the convolution algebras of semigroups, is that rectangular bands can serve as basic building blocks in a structure theory for general bands. (For other readers: a band is a semigroup in which every element is idempotent.) The structure theorem is due to Petrich, and is explained in Section 4.3 of Howie’s An Introduction To Semigroup Theory.

An interesting application, or manifestation, of some of the general theory comes from the analysis of certain random processes as random walks on special kinds of bands. In these settings you want to know about eigenvalues of certain transition matrices, which is apparently helped or clarified by understanding the structure of the convolution algebra of the band; here one interesting feature is that the convolution algebra modulo its Jacobson radical is commutative. Ken Brown (of group cohomology book fame) has written about this, see

• Semigroups, rings, and Markov chains. J. Theoret. Probab. 13 (2000), 871–938.

• Semigroup and ring theoretical methods in probability, Representations of finite dimensional algebras and related topics in Lie theory and geometry, 3–26, Fields Inst. Commun., 40, Amer. Math. Soc., Providence, RI, 2004.

Both available from Brown’s webpage.

My big question now is: what are rectangular bands good for, if anything?

My little question is: what is “rectangular” about rectangular bands? What is that word supposed to connote?

To me, rectangular bands are interesting because they are models of a kind of computation that can read a single binary digit from memory: $xy$ means “read the bit, if it is 0, proceed as $x$, if it is 1, proceed as $y$”.

It’s a simple theory that illustrates the idea of studying computational effects through algebraic theories. (e.g. I started with this in Instances of computational effects.)

Thanks, Yemon! This paper is really exciting to me:

• Ken Brown, Semigroups, rings, and Markov chains. J. Theoret. Probab. 13 (2000), 871–938.

Summarizing just a bit, he considers random walks on semigroups, particularly semigroups that arise from Coxeter complexes and hyperplane arrangements.

One nice thing: he takes a semigroup and defines $x \le y$ if $x y = y$. This gives a partial ordering iff the semigroup is a left regular band, meaning that idempotence

$$x x = x$$

and the graphic identity

$$x y x = x y$$

hold.

He seems to be particularly interested in cases where this semigroup is a monoid, in which case idempotence follows from the graphic identity, so we have what Lawvere called a graphic monoid.

When we have a simplicial complex or more general piecewise-linear cell complex, the faces form a poset ordered by inclusion (where we may need to reverse the ordering for compatibility with what I said above), and apparently these are often associated to semigroups via the above procedure.

There seems to be quite a big interesting story here.

The Wikipedia page claims now that in every semigroup (not necessarily a band), $xyz = xz$ implies $xyx = x$. But if your only rule yields terms with at least two factors, you cannot derive a general equation with right-hand side $x$. I will not edit the Wikipedia page, but this should be corrected.

Rectangular bands are the algebras for the monad on $\mathbf{Set}$ that arises from the familiar duplicate-product adjunction between $\mathbf{Set}$ and $\mathbf{Set}\times\mathbf{Set}$.

In detail: $F:\mathbf{Set}\to\mathbf{Set}\times\mathbf{Set}$ given by $F(A)=(A,A)$ is a left adjoint to $G:\mathbf{Set}\times\mathbf{Set}\to\mathbf{Set}$ given by $G(B_1,B_2)=B_1\times B_2$. This adjunction gives us a monad on $\mathbf{Set}$. The category of rectangular bands is the Eilenberg-Moore category for this monad.

I wonder whether the original duplicate-product adjunction is the Kleisli category for this monad.

Two left regular bands can have isomorphic posets without being isomorphic. The 4 element boolean algebra with meet has the same poset as the left regular band obtained by adding to a 2 element left zero semigroup an identity and a zero.

My colleague Stuart Margolis has a proof that it is NP-hard to determine if a poset comes from a left regular band.

Here is the link to the paper on left regular bands, topology and representation theory:

• Stuart Margolis, Franco Saliola and Benjamin Steinberg, Cell complexes, poset topology and the representation theory of algebras arising in algebraic combinatorics and discrete geometry, arXiv:1508.05446.

Now if somebody can explain the Lawvere Hegelian taco I would be grateful.

However, an isomorphism of semigroups is automatically an isomorphism of monoids; i.e. the functor $U$ is pseudomonic. Some fancy language for that is that an identity element is “property-like structure” on a semigroup — perhaps the simplest nontrivial example of property-like structure.

You can adjoin an element $1$ to your semigroup $S$, along with equations $1x=x=x1$ for each $x \in S$, obtaining a monoid $S[1]$. This is true for the same reason that, given any monoid $M$, you can adjoin elements $m^{-1}$ for each $m \in M$, along with relations $m m^{-1} = 1 = m^{-1}m$ to obtain a group $M[M^{-1}]$. It’s just pure algebraic fiat. And there will be canonical homomorphisms $S \to S[1]$, $M \to M[M{-1}]$.

But I think maybe Rob MacDonald wanted to known whether these homomorphisms are injective, so that we’re really “extending” the gadget we started with. For that, we need to do a bit more work. For example, $M \to M[M^{-1}]$ will be injective only if $M$ is cancellative, satisfying $xy = xz \implies y = z$ (I think this condition is also sufficient?). It isn’t injective when $M$ is, say, the monoid of functions on the 2-element set.

In the case of adjoining a unit, though, $S \to S[1]$ is always injective, because the relations $1x = x = x1$ fully specify a multiplication on the disjoint union $S \amalg \{1\}$ (using the original multiplication on $S$ itself), and a case-by-case check reveals that the multiplication is associative as long as the original multiplication was (for example, check that $1 (x 1) = 1x = x = x1 = (1x)1$ for $x \in S$ and $1(xy) =xy = (1x)y$ for $x,y \in S$, and …).

Is there a slick way to see this that avoids a case-by-case analysis?