January 11, 2024

Weak and Strong Algebraic Structures

Weak and Strong Algebraic Structures

Hillel Wayne's recent newsletter on monoids got me thinking again about an old question of mine: why are some algebraic structures more useful than others in software applications?

A bit counter-intuitively, a monoid is one of my examples of an algebraic structure that is not all that useful. A monoid is one of the simplest examples of an algebraic structure that programmers have a reason to talk about. In the context of implementing fold, aka reduce, in functional programming languages, if you recognize your input type as a monoid, then you can use a pre-existing reduce operator, and be confident it will work. One less for loop to write.

Sadly, for monoids the story seems to end there. And this is where my curiosity comes in. If, by contrast, you recognized your data forms a vector space with a dot product (or you model it as one), then you open the door to a wealth of algorithms, data analysis techniques, and interpretations that you can bring to bear on a problem. You can compute various bases to represent your data efficiently, make sparse decompositions, project onto subspaces, compute distances, and study eigenvalues and eigenvectors.

Where are the useful algorithms for monoids? Where are the structure theorems? Surely there are some; an entire subfield of mathematics is devoted to monoid theory. But I haven't seen anything resembling a novel theorem about monoids used in a practical setting (please tell me if you know of one!).¹

My opinion on this has two parts. First, very few things are just monoids. Second, a monoid is just too weak of a structure to do anything really novel with.

For the first, consider the list of examples of monoids on Wikipedia. Out of these 19, there are only two examples that I'd consider "proper" monoids in that they have monoid structure but nothing more: the set of all finite strings over a given alphabet, and the set of all functions from a set to itself. The set of strings is a "free" monoid, meaning it is the unique monoid with the least possible extra structure.

All the others are either non-examples (constructing a new monoid from an existing monoid) or describe sets that have more structure. E.g.,

• Every group/ring/field is a monoid
• The subsets of a set form a monoid, but they have the stronger structure of a lattice
• Functions into a structured set form a monoid, but usually more when the target of the function has more structure (e.g., the set of functions X -> R is a ring when R is a ring).
• The natural numbers (which form a monoid with zero as the additive identity) are usually better studied as integers, or modular integers, both of which form a ring.
• Sets with set union/intersection/complements are more structured than a monoid: they form a structure called a boolean algebra.

While they are monoids, most of these objects are not interesting for their monoid structure alone. The useful things about modular integers come from their group/ring/field-theoretic aspects, not their monoid structure.

For the second point, that a monoid is too weak, let me explain a bit about what I mean by "weak" and "strong."² A "strong" structure admits constructive characterization theorems, and efficient algorithms to convert objects into various canonical forms. For example:

• Linear algebra: Gaussian elimination, the Jordan canonical form, QR decompositions, etc., which convert a matrix into a form that allows useful information to be trivially read from the canonical form (e.g., invertibility dimension, eigenvalues/eigenvectors, explicit dependences between rows).
• Graph theory: search algorithms, component decomposition, tree balancing, subgraph isomorphism (commonly used in computational chemistr; I'm working on a chapter of Practical Math on this very topic).
• Ring theory: residue number systems, the Euclidean algorithm, etc.
• Groups: the classification theorem of finite Abelian groups, algorithms on permutation groups.

These types of structures are useful because they give you new constructive things to latch an application on to. A graph, for example, has local structure in terms of node degree and subgraphs, along with global structure in terms of its component structure, degree distribution, and eigenvalue spectrum. Fields/rings let you factor things, compute inverses and GCDs, etc.

But what can you do with a monoid? Saying "you can reduce it!" is saying little more than, "it is a monoid." When you reduce it, you don't actually use the monoid for anything more than its axiomatic definition, i.e., it's API. This is what I mean by "weak."

Another good example of a weak algebraic structure is a semilattice. Dataflow analysis in a compiler represents the data flowing through a program as a join-semilattice, where the join operation represents how to combine two static estimates of a variable's value at a point where two branches of control flow join together. E.g., if you're estimating the possible range of an integer, you'd take a union of the two estimated ranges. It's a really neat idea, but if you look at the actual implementations of data flow analysis algorithms, they don't analyze the lattice in any meaningful way, they process a worklist of program points that need updating, and join lattice elements greedily. Like reduce for monoids, it uses the algebraic "structure" not for any true structure, but for its API and local guarantees about it.

And this makes sense because it's not the lattice structure of the type that admits useful optimizations. Its the structure of the program being analyzed, like its particular combinations of control flow and branching, that matter. Similarly, a generic algorithm that processes lists isn't going to use any nontrivial monoid structure of its input types, but rather the special structure of the list instance given to it, such as known-to-be-sorted, or known-to-be-uniqued etc. That's not to say that having a generic reduce isn't nice; it is! It's just nice in its cleanliness, rather than allowing you to do something you couldn't do before.

Even groups, which I implied above are "strong," are really too weak to be useful in the same sense as linear algebra and rings/fields. Groups are mostly³ useful in computer science because they're weak enough that you can't easily crack cryptography based on them, but strong enough that you can define efficient encryption/decryption algorithms for them. If you set up a cryptosystem using the wrong group or the wrong public parameters, then the group has too much structure, becomes too easy to analyze, and the underlying security problem can be cracked.

Groups of numbers (or symmetries, or points on an elliptic curve) also have this nice property that they are compact. In a monoid like a string or a list, when you combine two elements z = xy, you explicitly preserve the underlying elements x and y (though the dividing line is lost). This isn't forced by the definition of a monoid, but I find it curious that the "nontrivial" examples of monoids-but-not-more are not compact in the same way as rings of numbers. Maybe monoids are weak because common monoids (that aren't spiritually more structured) are necessarily explicit, and hence the structure is already present in any representation as data, so there's no "new" structure to discover by an analogous kind of "change of basis" that you would find in linear algebra.

Other "weak" algebraic structures that I've never seen novel uses of: magma, groupoid, quandle (a sort of "group" that only has conjugation), and basically every structure listed in this diagram before "group."