Semigroup

A semigroup is a set with an associative binary operation, and no requirement of an identity element. Maximum over the integers, the union of bounding boxes, the concatenation of non-empty lists and the operation that keeps its first argument are semigroups that are not monoids. Associativity alone is enough to combine a non-empty sequence in any bracketing, in parallel or in a tree, and to combine $n$ copies of one element in $O (lo g n)$ operations by repeated squaring^[4]. Adjoining a new identity element turns any semigroup into a monoid. Semigroup theory is a branch of algebra in its own right, with applications to automata^[7] and to analysis^[8].

§ 01

Definition

A semigroup is a set $S$ with a binary operation $⋄ : S \times S \to S$ that is associative:

(a ⋄ b) ⋄ c = a ⋄ (b ⋄ c) for all a, b, c \in S

A semigroup with a two-sided identity is a monoid, and a monoid in which every element is invertible is a group^[1]. In a semigroup, the combination of any non-empty finite sequence is well defined without brackets, but the empty sequence has no combination:

sconcat (a_{1}, \dots, a_{n}) = a_{1} ⋄ a_{2} ⋄ \dots ⋄ a_{n} (n \geq 1)

which is why a semigroup-generic fold takes a non-empty collection, as Haskell's sconcat :: NonEmpty a -> a does.

§ 02

Examples

The positive integers under addition form a semigroup without identity, as do the integers under maximum or minimum when there is no least or greatest element. Axis-aligned bounding boxes under union have no identity, since every box has some extent. Non-empty lists under concatenation are the free semigroup: every function from elements into a semigroup extends uniquely to a homomorphism from non-empty lists. The operations $a ⋄ b = a$ ("keep the first") and $a ⋄ b = b$ ("keep the last") are associative on any set and have no identity when the set has more than one element.

Semigroups without identity as OCaml modules, sconcat over a non-empty list, and an identity adjoined with option.

module type SEMIGROUP = sig
  type t
  val ( <+> ) : t -> t -> t
end
 
(* Bounding boxes under union: there is no box that leaves every other
   box unchanged. *)
module Box = struct
  type t = { x0 : int; y0 : int; x1 : int; y1 : int }
  let ( <+> ) a b = { x0 = min a.x0 b.x0; y0 = min a.y0 b.y0; x1 = max a.x1 b.x1; y1 = max a.y1 b.y1 }
  let point x y = { x0 = x; y0 = y; x1 = x; y1 = y }
  let show b = Printf.sprintf "(%d,%d)-(%d,%d)" b.x0 b.y0 b.x1 b.y1
end
 
(* Keep the first value: associative, and no identity. *)
module First = struct type t = string let ( <+> ) a _ = a end
 
(* Combining needs at least one element. *)
let sconcat (type a) (module S : SEMIGROUP with type t = a) (x, xs) = List.fold_left S.( <+> ) x xs
 
(* Adjoining an identity: None is the new unit. *)
module WithUnit (S : SEMIGROUP) = struct
  type t = S.t option
  let empty = None
  let ( <+> ) a b = match (a, b) with None, x | x, None -> x | Some a, Some b -> Some (S.( <+> ) a b)
end

Running it.

bounding box of the points: (-2,-1)-(5,4)
first of [b; a; c]: b
with a unit adjoined, empty list: None;  all points: (-2,-1)-(5,4)

Adjoining an identity

Every semigroup $S$ extends to a monoid $S^{1} = S \cup {1}$ by adding a new element that acts as the identity^[1]:

1 ⋄ a = a = a ⋄ 11 ⋄ 1 = 1

In programming this is the option type: None is the identity, and two Some values are combined with the semigroup operation. It is how maximum on a type with no least element becomes a monoid, and folding the empty collection returns None instead of an arbitrary value.

§ 03

Repeated squaring

Combining $n$ copies of an element $x$ in a semigroup, written $x^{n}$ , takes $n - 1$ operations one at a time. Associativity allows grouping the copies instead:

x^{2 k} = (x ⋄ x)^{k} x^{2 k + 1} = x ⋄ (x ⋄ x)^{k}

which needs at most $2 ⌊ lo g_{2} n ⌋$ operations^[4]. No identity and no inverse is needed, only associativity, so the same function computes integer powers, matrix powers, repeated strings and iterated functions. Haskell's stimes is this operation.

Repeated squaring for any associative operation, with a count of operations.

(* x <+> x <+> ... <+> x (n >= 1 copies) in O(log n) operations, by
   repeated squaring. Only associativity is needed. *)
let times op n x =
  let count = ref 0 in
  let op a b = incr count; op a b in
  let rec go n x = if n = 1 then x else
    let h = go (n / 2) (op x x) in
    if n mod 2 = 0 then h else op x h in
  let r = go n x in
  (r, !count)
 
(* 2x2 integer matrices under multiplication: [[1;1];[1;0]]^n holds
   Fibonacci numbers. *)
let mul (a, b, c, d) (e, f, g, h) = (a * e + b * g, a * f + b * h, c * e + d * g, c * f + d * h)

Running it.

fib 10  = 55                    4 matrix products (naively 9)
fib 50  = 12586269025           7 matrix products (naively 49)
fib 90  = 2880067194370816120   9 matrix products (naively 89)
13 copies of "ab": ababababababababababababab  (5 concatenations)
x -> 3x+1 mod p composed 10^6 times, applied to 1: 333334  (25 compositions)

The Fibonacci numbers are entries of powers of a $2 \times 2$ matrix,

(1110)^{n} = (F_{n + 1} F_{n} F_{n} F_{n - 1})

so $F_{90}$ takes 9 matrix products. Applied to functions under composition, the method composes a function with itself a million times in 25 compositions; applying the result still performs a million applications, but the same idea applied to functions with a compact representation, such as affine maps modulo $p$ or matrices, makes the whole computation logarithmic.

§ 04

Special classes

A semigroup is commutative if $a ⋄ b = b ⋄ a$ , and a band if every element is idempotent, $a ⋄ a = a$ . A commutative band is a semilattice: defining $a \leq b ⟺ a ⋄ b = b$ gives a partial order in which $a ⋄ b$ is the least upper bound. Maximum, set union and logical disjunction are semilattices.

Semilattices are the algebra behind conflict-free replicated data types^[5]. Replicas of a data structure that merge their states with a semilattice operation reach the same state once they have exchanged all updates, whatever the order and however often a message is repeated, since the operation is associative, commutative and idempotent:

A grow-only counter: one slot per replica, merged by pointwise maximum.

(* A commutative, idempotent semigroup: pointwise maximum of counters, one
   slot per replica. Replicas that exchange states in any order, any
   number of times, end up equal. *)
module IMap = Map.Make (Int)
 
let merge a b = IMap.union (fun _ x y -> Some (max x y)) a b
let incr_at r c = IMap.update r (function None -> Some 1 | Some n -> Some (n + 1)) c
let value c = IMap.fold (fun _ n acc -> n + acc) c 0

Running it.

local counts: 10, 7, 8
after gossip and a final exchange: 25, 25, 25
merge idempotent: true   commutative: true

§ 05

Semigroup theory

The structure of semigroups is richer than that of groups, since elements need not be invertible. Green's relations classify the elements of a semigroup by the ideals they generate^[6], and are the starting point of the structure theory of Clifford and Preston^[2]. Every finite semigroup acts on itself, and a finite automaton defines one: the transformations of its states induced by input words, under composition. The Krohn–Rhodes theorem decomposes every finite semigroup, and so every finite automaton, into simple groups and a few basic semigroups combined by wreath products^[7]. In analysis, one-parameter semigroups of operators $T (s + t) = T (s) T (t)$ describe the solutions of evolution equations such as the heat equation, where time runs only forward^[8].

§ 06

In programming languages

Haskell has had a Semigroup class with <> and sconcat, and since 2018 it has been a superclass of Monoid, so every monoid is declared a semigroup first^[9]. Scala's Cats and PureScript have the same hierarchy. In languages without type classes, as in OCaml, a semigroup is a module with a type and an associative operation, and generic code takes it as a functor argument or a first-class module.

§ 07

History

De Séguier introduced the term semi-groupe in 1904 for a set with an associative operation^[3]. The subject developed from the 1920s onwards, with Suschkewitsch's work on finite semigroups, Green's relations in 1951^[6], and the monograph of Clifford and Preston in 1961^[2]. Hille and Phillips developed operator semigroups in functional analysis^[8], and Krohn and Rhodes connected finite semigroups to automata in 1965^[7].