🔢 mathematics

Finite Presentability of Brin-Higman-Thompson Monoids via Free Jónsson-Tarski Algebras

This paper demonstrates that the Brin-Higman-Thompson monoids and their generalizations are finitely presented by realizing them as endomorphism monoids of higher-dimensional Jónsson-Tarski algebras and interpreting their elements as rewrite rules.

Original authors: Bill de Witt, Luna Elliott

Published 2026-06-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bill de Witt, Luna Elliott

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, infinite library of books. But instead of words, the books are made of patterns of numbers and shapes. In mathematics, there are special groups of rules called "Thompson's groups" that describe how you can shuffle these patterns around without losing any information. They are famous for being complex but perfectly organized.

This paper introduces a new set of rules called monoids. Think of a "group" as a club where every member can undo their moves (like a reversible dance). A "monoid" is a bit more relaxed: it's a club where you can do moves, but you might not be able to undo them (like a dance where you can spin forward, but once you stop, you can't necessarily spin backward to exactly where you started).

The authors, Bill De Witt and Luna Elliott, are looking at a specific, very complex version of these monoids that exist in multiple dimensions (not just left/right, but up/down, forward/back, etc.). They call these Brin-Higman-Thompson monoids.

Here is the core of what they discovered, explained simply:

1. The "Tree" and the "Algebra" Connection

The authors realized that these complex monoids are actually the same thing as the "machines" (mathematicians call them endomorphisms) that run on a specific type of algebraic structure called a Jónsson-Tarski algebra.

The Analogy: Imagine a tree growing in a garden. You can cut branches off, graft new ones on, or rearrange the whole tree.
- The Monoid is the set of all possible ways you can rearrange the tree.
- The Algebra is the tree itself, built from specific rules.
- The authors proved that the set of all possible tree-rearrangements is exactly the same as the set of all machines that can operate on this specific type of algebraic tree. It's like discovering that the instructions for a video game level are identical to the code running the game engine.

2. The "Rewrite Rule" Perspective

To understand these rearrangements, the authors looked at them as rewrite rules.

The Analogy: Think of a "Find and Replace" function in a word processor.
- If you have a pattern like A(B C), a rewrite rule might say, "Change this to A(C B)."
- In their complex, multi-dimensional world, these rules are like swapping entire sections of a 3D puzzle.
- The authors showed that every single move in their monoid can be described as a specific "Find and Replace" instruction on these algebraic trees.

3. The Big Discovery: Finite Presentability

The most important result of the paper is about Finite Presentability.

The Problem: These mathematical objects are infinite. They have an infinite number of possible moves. Usually, to describe an infinite object, you need an infinite list of rules.
The Discovery: The authors proved that you do not need an infinite list. You can describe the entire, infinite complexity of these monoids using a finite list of generators (basic moves) and a finite list of relations (rules about how those moves interact).
The Analogy: Imagine a language with infinite words. Usually, you'd need a dictionary with infinite pages. But these authors proved that for this specific language, you only need a small pocket dictionary (a finite set of words) and a small grammar book (a finite set of rules) to generate every single sentence in the language.

4. How They Did It

They used a clever trick involving "deferments."

The Analogy: Imagine you have a rule that says "Swap the top two shelves of a bookcase." A "deferment" is like saying, "Don't swap the top shelves yet; instead, go down to the bottom shelf, swap the books there, and then apply the top-shelf swap rule."
By breaking down complex moves into these "deferred" steps and showing how they relate to each other, they were able to build a complete, finite blueprint for the entire system.

Summary

In short, this paper takes a very complicated, multi-dimensional mathematical structure (the Brin-Higman-Thompson monoids), shows that it is essentially a machine for rearranging algebraic trees, and proves that despite being infinite, it can be completely described by a short, finite list of rules. They also provided the actual list of rules for a specific 2-dimensional case, which was the original monoid studied by the mathematician Thompson.

What the paper does NOT claim:

It does not claim these rules apply to computer science, physics, or biology (though the authors mention a Python package used for testing, they don't claim the math solves real-world problems).
It does not claim to solve the "partial" versions of these monoids (where some moves are missing), though it suggests their methods might be adaptable for that in the future.
It does not claim to have found a new physical law or a medical cure. It is purely a discovery about the structure of abstract mathematical objects.

Technical Summary: Finite Presentability of Brin-Higman-Thompson Monoids via Free Multidimensional Jónsson-Tarski Algebras

Problem Statement
The paper addresses the structural properties of the monoids $tot \, {}_n M_{k,r}$ , which are non-partial generalizations of the Brin-Higman-Thompson groups ${}_n G_{k,r}$ . Introduced by Birget, these monoids extend the classical Thompson's group $V$ (and its monoid version $tot \, M_{2,1}$ ) to higher dimensions and involve partial maps on prefix codes that are not necessarily injective. While the finite presentability of Thompson's group $V$ and its higher-dimensional analogues ${}_n G_{k,r}$ is well-established, the finite presentability of the associated monoids $tot \, {}_n M_{k,r}$ had not been proven. The authors aim to establish that these monoids are finitely presented for all $n, r \ge 1$ and $k \ge 2$ .

Methodology
The authors employ a dual approach combining algebraic geometry (via Jónsson-Tarski varieties) and combinatorial rewriting systems.

Algebraic Realization via Jónsson-Tarski Algebras:
The authors first establish an isomorphism between the monoid $tot \, {}_n M_{k,r}$ and the endomorphism monoid of a free algebra in the $n$ -dimensional $k$ -ary Jónsson-Tarski variety, denoted $End(F_{n,k,r})$ .
- They define the variety ${}_n J_k$ using $n$ $k$ -ary operations ( $\lambda_i$ ) and $nk$ unary operations ( $\alpha_{i,j}$ ) satisfying specific inverse and commutation relations.
- They construct a mapping between the "shrubberies" (elements of the space ${}_n T_{k,r}$ representing prefix codes) and the free generators of $F_{n,k,r}$ .
- Using the concept of "expansions" (analogous to tree expansions in Thompson groups), they prove that complete prefix codes in the topological space correspond bijectively to free generating sets of the algebra. This allows them to represent elements of the monoid as endomorphisms acting on these generating sets.
The Rewrite Perspective:
To prove finite presentability, the authors shift to an anti-isomorphic monoid, ${}_n Rel_{k,r}$ , whose elements are viewed as "rewrite rules" acting on labeled free generating sets.
- They introduce "labeled free generating sets" where generators are assigned labels from an infinite set.
- Elements of the monoid are defined by how they map one labeled set to another, preserving labels. This framework allows the authors to treat monoid elements as transformations of expressions (analogous to bracketed expressions in Thompson's group $V$ ).
- They define "deferments," which allow the action of a map to be shifted to specific root systems, facilitating the manipulation of generators.
Construction of the Presentation:
The proof of finite presentability proceeds by:
- Demonstrating that the monoid is finitely generated by its group of units (automorphisms) and two specific non-invertible elements ( $U$ and $\pi$ ).
- Defining a submonoid ${}_n P_{k,1}$ isomorphic to a free monoid product, which serves as a tool to detect equality between elements.
- Constructing an explicit finite presentation $\langle \Sigma | R \rangle$ . The relations include those defining the group of units, relations governing the interaction between units and the non-invertible generators, and specific relations derived from the "deferment" mechanism and the structure of the free algebra.

Key Contributions and Results

Theorem 1.1 (Isomorphism): For $r, n \ge 1$ and $k \ge 2$ , the monoid $tot \, {}_n M_{k,r}$ is isomorphic to the endomorphism monoid of the $r$ -generated free algebra in the $n$ -dimensional $k$ -ary Jónsson-Tarski variety. This provides a concrete algebraic model for these monoids.
Theorem 1.2 (Finite Presentability): The monoid $tot \, {}_n M_{k,r}$ is finitely presented.
Explicit Presentation: The authors provide an explicit, albeit complex, finite presentation for the specific case of $tot \, M_{2,1}$ (Thompson's original monoid). This presentation involves generators $u, v, \pi_L, U$ and 82 relations, derived from the general construction.
Generalization of Thompson's Proof: The methodology adapts Thompson's original proof for the finite presentability of his monoid to the multidimensional setting, utilizing the structure of Jónsson-Tarski algebras to handle the higher-dimensional prefix codes.

Significance
The paper resolves the open question of whether the non-partial Brin-Higman-Thompson monoids are finitely presented. By realizing these monoids as endomorphism monoids of free algebras in a specific variety, the authors bridge the gap between the topological/combinatorial definitions of these monoids and abstract algebraic structures. This realization allows for the application of algebraic techniques (specifically those related to free objects and varieties) to solve problems regarding the monoids' presentations.

The authors note that while their methods successfully address the non-partial monoids $tot \, {}_n M_{k,r}$ , the question of finite presentability for the partial monoids ${}_n M_{k,r}$ (which include non-injective maps with incomparable image sets) remains open. They suggest that their techniques might be modifiable to address these partial structures, but do not claim to have solved that specific case. The work also highlights the utility of Jónsson-Tarski algebras in understanding the structure of Higman-Thompson type groups and monoids.

1. The "Tree" and the "Algebra" Connection

2. The "Rewrite Rule" Perspective

3. The Big Discovery: Finite Presentability

4. How They Did It

Summary

More like this