The Nyberg-Brodda Monoid Family is FCRS

This is a rough sketch of a proof giving an affirmative answer to a question posed by Carl-Fredrik Nyberg-Brodda¹.

QUOTE

Question 24. Does $\Pi_N$ admit a finite complete rewriting system for all $N \geq 2?$

Proof

Let $M = \langle a,b \mid baa(ba)^n=a \rangle$ where $n \geq 2.$

Define the string rewriting system $R$ by the rules

$$\begin{align*} baa(ba)^n &\longrightarrow a & \\ baa(ba)^ka &\longrightarrow aa(ba)^{n(n-k)}, & 0 \leq k \lt n. \end{align*}$$

Let $P$ be the map sending a word $w \in \{a,b\}^*$ to the vector $(p_1, p_2, \ldots, p_k)$ where each $p_i$ is the index of the earliest occurrence of $aa$ in $w$ after the previous index (or the beginning of $w$, if $i = 1$). Note that we count $aaa$ as having two occurrences of $aa.$

Let $\ell$ be the map $w \mapsto (\left|P(w)\right|, P(w)).$

Observe that both rules, dependig on the surrounding context, either decrease the number of the occurrences of $aa$, or preserve the number of occurrences but trade a later ocurrence for an earlier one, decreasing $P(w)$ lexicographically. Thus, each rewrite reduces $\ell(w)$ and hence $R$ is terminating.

We will now prove that each rule holds in $M.$

Suppose $k = n - 1.$ In that case

$$\begin{align*} baa(ba)^{n - 1}a &= baa(ba)^{n - 1}baa(ba)^{n} \\ &= baa(ba)^{n}a(ba)^{n} \\ &= aa(ba)^n. \end{align*}$$

Now, suppose $2 \leq m \leq n$ and

$$baa(ba)^{n - m + 1}a = aa(ba)^{n(m - 1)}.$$

Then

$$\begin{align*} baa(ba)^{n - m}a &= baa(ba)^{n - m}baa(ba)^{n} \\ &= baa(ba)^{n - m + 1}a(ba)^{n} \\ &= aa(ba)^{n(m - 1)}(ba)^n \\ &= aa(ba)^{nm}. \end{align*}$$

Thus, all rules of $R$ are valid in $M.$

We will now consider overlaps between the rules of $R.$ Let $A_k = baa(ba)^ka$ and let $B = baa(ba)^n.$

First, consider the case where a suffix of $A_k$ is a prefix of $B$. This overlap has the shape

$$aa(ba)^{n(n-k)}(ba)^n \longleftarrow baa(ba)^{k-1}baa(ba)^n \longrightarrow baa(ba)^{k-1}a,$$

and is joined by

$$baa(ba)^{k - 1}a \longrightarrow aa(ba)^{n(n-k+1)}.$$

Now, consider

$$aa(ba)^ka \longleftarrow baa(ba)^{n-1}baa(ba)^ka \longrightarrow baa(ba)^{n-1}aa(ba)^{n(n-k)}.$$

Fisrt, we apply

$$baa(ba)^{n-1}a \longrightarrow aa(ba)^{n}$$

which allows for the two sides to join as follows.

$$\begin{align*} aa(ba)^{n}a(ba)^{n(n-k)} &\longrightarrow aa(ba)^{n-1}baa(ba)^n(ba)^{n(n-k - 1)}\\ &\longrightarrow aa(ba)^{n-1}a(ba)^{n(n-k - 1)} \\ &\longrightarrow aa(ba)^{n-2}baa(ba)^n(ba)^{n(n-k - 2)} \\ &\longrightarrow aa(ba)^{n-2}a(ba)^{n(n-k - 2)} \\ &\longrightarrow \cdots \\ &\longrightarrow aa(ba)^{n - (n - k - 1)}a(ba)^{n(n-k-(n - k - 1))} \\ &\longrightarrow aa(ba)^{k + 1}a(ba)^{n} \\ &\longrightarrow aa(ba)^{k}baa(ba)^{n} \\ &\longrightarrow aa(ba)^{k}a \\ \end{align*}$$

Thus, all overlaps between $A_k$ and $B$ join.

Now consider the self-overlap of $B,$

$$aa(ba)^n \longleftarrow baa(ba)^{n-1}baa(ba)^n \longrightarrow baa(ba)^{n-1}a.$$

The rule $baa(ba)^{n-1}a \longrightarrow aa(ba)^n$ joins this overlap.

Finally, consider the overlap between $A_p$ and $A_q,$

$$aa(ba)^{n(n-p)+q}a \longleftarrow baa(ba)^{p-1}baa(ba)^qa \longrightarrow baa(ba)^{p-1}aa(ba)^{n(n-q)}.$$

Observe that

$$baa(ba)^{p-1}aa(ba)^{n(n-q)} \longrightarrow aa(ba)^{n(n-p+1)} a(ba)^{n(n-q)},$$

making the two sides joinable by the same reasoning as earlier.

Thus, we conclude that $R$ is locally confluent. Since it is terminating, Newman’s lemma upgrades this to confluence. Hence, we can conclude that every monoid presented as

$$\langle a,b \mid baa(ba)^n=a \rangle$$

for $n \geq 2$ has a finite complete rewriting system.

$\blacksquare$

Footnotes

1. Carl-Fredrik Nyberg-Brodda. On the Dehn functions of a class of monadic one-relation monoids. Comptes Rendus. Mathématique, Volume 362 (2024), pp. 713-730. doi: 10.5802/crmath.554 ↩