aligntableaux = bottom

# On the first order theory of plactic monoids

Daniel Turaev

###### Abstract

This paper proves that a plactic monoid of any finite rank will have decidable
first order theory. This resolves other open decidability problems about the
finite rank plactic monoids, such as the Diophantine problem and identity
checking. This is achieved by interpreting a plactic monoid of arbitrary rank
in Presburger arithmetic, which is known to have decidable first order theory.
The algorithm generating the interpretations is uniform, which answers
positively the decidability of the Diophantine problem for the infinite rank
plactic monoid. We also show that the plactic monoid of rank 2 is bi-
interpretable with Presburger arithmetic.

###### Contents

  1. 1 Introduction
  2. 2 Background
    1. 2.1 Rewriting systems
    2. 2.2 The plactic monoid
    3. 2.3 Interpretations, theories, and Presburger arithmetic
  3. 3 The case $n=2$
    1. 3.1 Interpreting $P_{2}$ in $(\mathbb{Z},0,1,+,-,\leq)$
    2. 3.2 Bi-interpretability
  4. 4 The general case
    1. 4.1 Multiplication – the idea
    2. 4.2 The formula defining $\mu_{x}$
  5. 5 The Diophantine problem in the infinite case
    1. 5.1 The plactic monoid of all tableaux
    2. 5.2 A plactic monoid on integers
    3. 5.3 Two open questions

##  1 Introduction

The plactic monoid has its origin in the work of Knuth [22], which based
itself on the algorithm developed by Schensted [41]. First studied in depth by
Lascoux and Schützenberger [25, 42, 43], its combinatorial properties were
applied to the theory of symmetric polynomials to prove the Littlewood-
Richardson rule. Due to its origins as a monoid of Young tableaux, it has
proved useful in various aspects of geometry and representation theory [14].
More recently, it has found application in Kashiwara’s crystal basis theory
[19], with analogous plactic monoids being defined for different root systems
associated to crystal bases [27, 28, 29, 30], and used to study Kostka-Foulkes
polynomials [26]. Related, plactic-like monoids have also been defined [1, 12,
16, 35], and used to study the combinatorics and growth properties of the
plactic monoid, which itself has some interesting combinatorial structure.
Cain, Gray, and Malheiro [5] have shown that the plactic monoids are
biautomatic, as are related crystal monoids [4], and related plactic-like
monoids such as the Chinese, Hypoplactic, and Sylvester monoids [6].

Schensted’s multiplication algorithm can be used to decide the word problem
for the plactic monoid. It was shown in 1981 that the plactic monoid has
decidable conjugacy problem [25]. A classic generalisation of both the word
and conjugacy problems is the Diophantine problem, which has received much
attention for free groups [20, 32, 40, 44], where Makanin-Razborov diagrams
were used independently by Sela [44] and Kharlampovich and Myasnikov [21] to
solve the Tarski problems on the first order theory of free groups111For a
survey of these results, see [13]. The Diophantine problem has also been
studied for free monoids [33, 45] and is gaining attention in the study of
other monoids [15, 36]. In the monoid setting, it asks for an algorithm for
deciding whether a given system of equations has a solution in a given monoid.

An active area of research is the question of checking identities in the
plactic monoids and their monoid algebras. Progress has been made in the rank
3 case [23, 24], and the plactic monoid, bicyclic monoid, and related plactic-
like monoids have been shown to admit faithful representations in terms of
matrices over the tropical semiring [3, 8, 10, 18]. This implies that every
plactic monoid of finite rank satisfies a nontrivial semigroup identity. There
is a natural decision problem underpinning this field of study – is it
decidable whether a given identity is satisfied by a plactic monoid.

In this paper, we show that the plactic monoid of every finite rank has
decidable first order theory. This result is a significant generalisation of
both of the above ideas. Both identities and Diophantine equations are
expressible as first order sentences, thus yielding positive results for both
the Diophantine problem and the problem of identity checking. It is not
equivalent to these results – the free semigroup has undecidable theory
despite having decidable Diophantine problem [39]. Nor does this result follow
from the multi-homogeneity of the plactic monoids, as there are multi-
homogeneous monoids with undecidable theory, and even undecidable conjugacy
problem [7].

The argument presented below is by constructing an interpretation of a plactic
monoid in Presburger arithmetic, and could open the door to studying the
theories of plactic-like classes of monoid. It is known that all groups
interpretable in Presburger arithmetic are abelian-by-finite [37]. This result
may also be a starting point for classifying all monoids interpretable in
Presburger arithmetic.

In preparing this paper for publication, the author was made aware in private
communication that Alan Cain and Tara Brough have independently constructed a
proof that the plactic monoids are interpretable in Presburger arithmetic,
which will appear in a forthcoming paper of theirs. This coincides with the
results in section 3.1 and section 4.

### Notation and conventions

Write $[n]$ for the set $\\{1,\dots,n\\}$. Write $A$ for a totally-ordered
alphabet on $n$ letters, which will usually be $[n]$. The free monoid on an
alphabet $A$ will be written with a Kleene star $A^{*}$, and will have
identity $\varepsilon$, the empty word. Given a set of generators $A$ and
relations $R\subset A^{*}\times A^{*}$, the monoid presentation denoted by
$\langle A|R\rangle$ will be the quotient of $A^{*}$ by the congruence
generated by $R$. The set $\mathbb{N}$ of natural numbers will contain 0.

##  2 Background

###  2.1 Rewriting systems

A string rewriting system (henceforth rewriting system) for $A^{*}$ is a set
$R~{}\subset~{}A^{*}\times~{}A^{*}$ of elements $(\ell,r)$, usually written
$\ell\to r$, called _rewrite rules_. See the book [2] for a more detailed
introduction.

For two elements $u,v\in A^{*}$, write $u\to_{R}v$ if $u=x\ell z$, $v=xrz$,
and $(\ell,r)\in R$. The transitive and reflexive closure of $\to_{R}$,
written $\to_{R}^{*}$, is called the reduction relation of $R$. The symmetric
closure of $\to_{R}^{*}$ is a semigroup congruence. The monoid obtained by
taking the quotient of $A^{*}$ by this congruence is the monoid presented by
$\langle A|R\rangle$. Thus every presentation $\langle A|R\rangle$ also
corresponds to a rewriting system, which is written $(A,R)$.

A rewriting system is called _Noetherian_ if it has no infinite descending
chain. That is, there is no sequence $u_{1},u_{2},\dots\ \in A^{*}$ such that
$u_{i}\to_{R}u_{i+1}$ for all $i\in\mathbb{N}$. A rewriting system is called
_confluent_ if it has the property that, whenever $u\in A^{*}$ is such that
$u\to_{R}^{*}u^{\prime}$ and $u\to_{R}^{*}u^{\prime\prime}$, there exists a
$v$ such that $u^{\prime}\to_{R}^{*}v$ and $u^{\prime\prime}\to_{R}^{*}v$. We
call a confluent Noetherian rewriting system _complete_.

Call $u\in(A,R)$ a _reduced word_ if there is no subword $\ell$ of $u$ that
forms the left hand side of a rewrite rule in $R$. By theorem 1.1.12 of [2],
if $(A,R)$ is a complete rewriting system, then for every $u\in A^{*}$ there
is a _unique, reduced_ $v\in A^{*}$ such that $u\to_{R}^{*}v$. This $v$ is
called a _normal form_ for $u$, and forms a cross-section of the monoid
$\langle A|R\rangle$, in the sense that every element of the monoid is equal
to exactly one reduced word. We may therefore identify a monoid admitting a
complete rewriting system with its set of normal forms, and the multiplication
being concatenation followed by reducing to normal form.

###  2.2 The plactic monoid

We follow the French conventions of Young diagrams having longer rows
underneath shorter ones.

######  Definition 2.1.

A _Semistandard Young Tableau_ (henceforth simply tableau) is a Young diagram
with labelled boxes, with labels satisfying the following conditions

  * •

each row weakly increases left to right

  * •

each column strongly decreases top to bottom

######  Example.

3&4
233
11244
is a tableau. 4&5
6 1
123 is not a tableau.

Let $t$ be a tableau with labels taken from $A$. We associate to $t$ a _row
reading_ in $A^{*}$. Suppose $t$ is a tableau of $m$ rows, labelled top to
bottom as $r_{1},\dots,r_{m}$. The labels of the boxes in each row are an
increasing sequence, which can be viewed as a word $r_{i}\in A^{*}$. The row
reading of $t$ is then $w=r_{1}r_{2}\dots r_{m}\in A^{*}$.

We similarly associate a _column reading_ to $t$. Denote the columns of $t$
from left to right by $c_{1},\dots,c_{m}$. Each such column corresponds to a
strictly decreasing sequence $c_{i}\in A^{*}$. The column reading of $t$ is
then $w=c_{1}\dots c_{m}\in A^{*}$.

######  Example.

The tableau $t=$ 3
2 & 3
1 1 2 2 2 has row reading

$32311222=3\ 23\ 11222$

and column reading

$32131222=321\ 31\ 2\ 2\ 2$

We now describe Schensted’s algorithm. Consider $A=[n]$ the totally ordered
alphabet, and $w\in A^{*}$. We may view $w$ as a finite sequence of numbers.
Schensted’s algorithm is used to study the longest increasing and decreasing
subsequences of $w$. The algorithm associates a tableau to $w$ with the
property that the number of columns of $w$ is the length of the longest
_increasing_ sequence, and the number of rows is the length of the longest
_strictly decreasing_ sequence. See [41] or chapter 5 of [31] for more details
on this combinatorial structure.

######  Definition 2.2 (Schensted’s algorithm).

We define $P:A^{*}\to A^{*}$ to be the map sending a word $w$ to the row
reading of a tableau recursively as follows:

Firstly, $P(\varepsilon)=\varepsilon$. Then suppose $w=x_{1}\dots x_{\ell}\in
A^{*}$ and $P(x_{1}\dots x_{\ell-1})=r_{1}\dots r_{m}$ for some rows $r_{i}$
that form the row reading of a tableau. Then we have:

  1. 1.

If $r_{m}x_{\ell}$ is a row, then we set $P(r_{1}\dots
r_{m}x_{\ell})=r_{1}\dots r_{m}x_{\ell}$

  2. 2.

If not, then we can write $r_{m}=r_{\alpha}yr_{\beta}$, with $y$ being the
leftmost letter such that $x_{\ell}<y$, as this will break the weakly
increasing property required of a row. But then $r_{\alpha}x_{\ell}r_{\beta}$
will be a row. So we set

$P(r_{1}\dots r_{m}x_{\ell})=P(r_{1}\dots
r_{m-1}y)r_{\alpha}x_{\ell}r_{\beta}$

.

We call the process in point (2) ‘bumping the letter $y$’. If $t$ has row
reading $r_{1}\dots r_{m}$ and column reading $c_{1}\dots c_{k}$, then it is
straightforward to show that

$P(r_{1}\dots r_{m})=P(c_{1}\dots c_{k})=r_{1}\dots r_{m}$

######  Definition 2.3 (The plactic monoid).

The relation $\sim$ on $A^{*}$ given by

$u\sim v\iff P(u)=P(v)$

is a semigroup congruence, and the monoid $A^{*}/\sim$ with multiplication
given by $u\cdot v=P(uv)$ is called the _plactic monoid of rank $n$_. Denote
this monoid by $P_{n}$.

Knuth [22] exhibited a set of defining relations $K$ for the plactic monoids
of the form $xzy=zxy$ and $yxz=yzx$ for $x<y<z,\ x,y,z\in A$ and $xyx=yxx$ and
$yyx=yxy$ for $x<y,\ x,y\in A$. That is, we have

$K=\\{xzy=zxy,\ x\leq y<z\\}\cup\\{yxz=yzx,\ x<y\leq z\\}$

with $P_{n}=\langle A|K\rangle$. For each finite rank, it follows that $P_{n}$
will be finitely presented.

It was shown by Cain, Gray, and Malheiro in [5] that the plactic monoid admits
a finite complete rewriting system, which we describe here.

We consider two columns $\alpha,\beta$ as words in $A^{*}$. We say that
$\alpha$ and $\beta$ are _compatible_ , written $\alpha\succeq\beta$, if
$\alpha\beta$ is the column reading of a tableau. Then each pair
$\alpha,\beta$ with $\alpha\nsucceq\beta$ yields a rewrite rule. Consider the
tableau associated to $P(\alpha\beta)$. Since the number of columns in
$P(\alpha\beta)$ is the length of the longest increasing sequence, and
$\alpha,\beta$ are columns, it follows that $P(\alpha\beta)$ will be a tableau
with at most two columns. Therefore this tableau will have column reading
$\gamma\delta$, for some columns $\gamma,\delta$ with $\gamma\succeq\delta$,
and potentially $\delta=\varepsilon$.

Now consider $\mathcal{C}=\\{c_{\alpha}\ |\ \alpha\in A^{*},\alpha\text{ is a
column}\\}$ to be a set of symbols corresponding to columns in $A^{*}$. Since
$A$ is finite and columns are strictly decreasing sequences, $\mathcal{C}$ is
also finite. Then define $R$ to be the set of all rewrite rules detailed above

$R=\\{c_{\alpha}c_{\beta}\to c_{\gamma}c_{\delta}|\ \alpha,\beta\in A^{*}\
\alpha\nsucceq\beta\\}$

It is shown in [5] that

######  Lemma 2.4.

$(\mathcal{C},R)$ is a complete rewriting system for $P_{n}$.

It follows from this that $P_{n}$ admits normal forms as reduced words in
$\mathcal{C}^{*}$. By the definition of $\succeq$, this normal form will be in
the form of column readings $c_{\alpha_{1}}\dots c_{\alpha_{m}}$ with each
$\alpha_{i}\succeq\alpha_{i+1}$.

Note that if $\alpha=\alpha_{m}\dots\alpha_{1}$ and
$\beta=\beta_{n}\dots\beta_{1}$, $\alpha_{i},\beta_{i}\in A$, appear in the
column reading of the same tableau (not necessarily adjacent) with $\alpha$
further left than $\beta$, then $\alpha\succeq\beta$. Indeed, since $\alpha$
and $\beta$ are columns of the same tableau, then by the structure of a
tableau we have that $m\geq n$. Furthermore, each pair $\alpha_{i},\beta_{i}$
will be in the same row of the tableau, with $\alpha_{i}$ appearing earlier
than $\beta_{i}$. This will imply that $\alpha_{i}\leq\beta_{i}$. But these
two conditions imply that $\alpha\succeq\beta$. Thus $\succeq$ is a partial
order.

We introduce a length-decreasing-lexicographic order on $\mathcal{C}$
extending $\succeq$. For $c_{\alpha},c_{\beta}\in\mathcal{C}$, define:

$c_{\alpha}\sqsubseteq
c_{\beta}\iff\left(|\alpha|>|\beta|\right)\lor\left(|\alpha|=|\beta|\wedge\left(\exists
j:\ i<j\implies\alpha_{i}=\beta_{i}\wedge\ \alpha_{j}<\beta_{j}\right)\right)$

With $j$ taken as $n+1$ when $c_{\alpha}=c_{\beta}$. Note that
$c_{\alpha}\succeq c_{\beta}\implies c_{\alpha}\sqsubseteq c_{\beta}$.
Furthermore, this is clearly a total order. We can therefore enumerate the set
$\mathcal{C}$ as $\\{c_{1},\dots c_{k}\\}$, with $k=|\mathcal{C}|=2^{n}-1$,
such that $i\leq j\implies c_{i}\sqsubseteq c_{j}$. Then, since
$c_{\alpha}\succeq c_{\beta}\implies c_{\alpha}\sqsubseteq c_{\beta}$, we have
that the normal forms of $P_{n}$ will have the form

$c_{1}^{w_{1}}\dots c_{k}^{w_{k}}$

with $w_{i}\in\mathbb{N}$ for each $i$, and for any pair $c_{i},c_{j}$ with
$i<j\land c_{i}\nsucceq c_{j}$, either $w_{i}=0$ or $w_{j}=0$. Call two
columns $c_{i}$ and $c_{j}$ _incompatible_ if $i<j\land c_{i}\nsucceq c_{j}$.

######  Example.

$P_{3}$ has seven columns:

3
2
1 , 2
1 , 3
1 , 3
2 , 1 , 2 , 3

listed here in length-decreasing-lexicographic order. This list corresponds to
symbols $c_{1},\dots,c_{7}\in\mathcal{C}$. Note that $c_{4}$ and $c_{5}$ are
incompatible. $P_{3}$ is the lowest rank plactic monoid with an incompatible
pair.

###  2.3 Interpretations, theories, and Presburger arithmetic

We assume familiarity with basic first order logic, and refer the reader to
[17] or [34] for a more detailed introduction to model theory. We will be
following the conventions of [34]

######  Definition 2.5.

Let $L$ be the language of first order formulas for a given signature. Then
the first order theory of an $L$-structure $\mathcal{M}$ is the set of all
sentences in $L$ that hold in $\mathcal{M}$.

The question of deciding a first order theory asks for an algorithm which,
given a first order sentence $\phi$, determines whether $\phi$ is true or
false in $\mathcal{M}$ in finite time.

The language of interest in this paper is the language of monoids, whose
signature is $(\circ,\varepsilon)$. To speak of the first order theory of a
given monoid, one classically allows atomic formulas of the form $u=v$ for
each $u,v\in\mathcal{M}$. In the finitely generated case (with generating set
$A=\\{a_{1},\dots,a_{n}\\}$, say) this is equivalent to adding constants
$a_{1},\dots,a_{n}$ to the signature, and considering the first order theory
with constants of $(\mathcal{M},\circ,\varepsilon,a_{1},\dots,a_{n})$.

In our case, we refer to the first order theory of a plactic monoid of rank
$n$, which will have constants $1,\dots,n$ added to the language of monoids.
Write $FOTh(P_{n})$ as shorthand for the first order theory of $P_{n}$ with
constants.

We aim in the following sections to build an interpretation of $P_{n}$ in
Presburger arithmetic, which will allow $\varphi\in FOTh(P_{n})$ to be reduced
to a sentence $\tilde{\varphi}$ of Presburger arithmetic. A _reduction_ of a
decision problem $D_{1}$ to another decision problem $D_{2}$ is a Turing
machine which, given finitely many queries to an oracle for $D_{2}$, will
yield an algorithm for deciding $D_{1}$. Importantly, this means that
decidability of $D_{2}$ will imply decidability of $D_{1}$, as such an oracle
machine will exist and halt in finite time on each query.

Presburger arithmetic is named after Mojżesz Presburger, who in 1929 was
tasked with studying the decidability of the integers under addition. In his
master’s thesis [38], he used quantifier elimination and reasoning about
arithmetic congruences to prove that the first order theory of
$(\mathbb{N},0,1,+)$ is consistent, complete, and decidable. Note that we can
add a comparison symbol $\leq$ to the signature of Presburger arithmetic
without trouble, since $x\leq y$ is equivalent to the statement $\exists
z:y=x+z$. This yields the following lemma:

######  Lemma 2.6.

$FOTh(\mathbb{N},0,1,+,\leq)$ is decidable.

This result will form the bedrock of the following argument. For an English
translation of Presburger’s work, see [46].

For the definition of an interpretation, we proceed as in section 1.3 of [34]

######  Definition 2.7.

Let $\mathcal{M}$ be an $L$-structure. A set $S\subseteq\mathcal{M}^{n}$ is
called _definable in $\mathcal{M}$_ if there is a first order formula
$\phi(x_{1},\dots,x_{n},y_{1},\dots,y_{m})\in L$ with free variables
$x_{1},\dots,x_{n},y_{1}\dots,y_{m}$ such that there exists
$(w_{1},\dots,w_{m})\in\mathcal{M}^{m}$ with the property that
$\phi(x_{1},\dots,x_{n},w_{1},\dots,w_{m})$ holds if and only if
$(x_{1},\dots,x_{n})\in S$. i.e. $S$ is the set

$\\{\underline{x}\in\mathcal{M}^{n}|\
\mathcal{M}\models\phi(\underline{x},w_{1},\dots,w_{m})\\}$

######  Example.

The set of elements that commutes with a given $m\in\mathcal{M}$ is definable
by the formula $xm=mx$. The centre of $\mathcal{M}$ is definable by the
formula

$\forall m:xm=mx$

If $\mathcal{M}$ is finitely generated by $\\{m_{1},\dots m_{k}\\}$, then the
formula

$xm_{1}=m_{1}x\land xm_{2}=m_{2}x\land\dots\land xm_{k}=m_{k}x$

defines the centre of $\mathcal{M}$. This has the property of being a
_positive existential_ formula, which is useful in the study of Diophantine
equations222See, for example, [9]

######  Definition 2.8.

A function $f:\mathcal{M}^{m}\to\mathcal{M}^{n}$ is definable in $\mathcal{M}$
if its graph is definable as a subset of $\mathcal{M}^{m+n}$.

Note that the composition of definable functions is definable.

######  Definition 2.9.

Let $\mathcal{M}$ be an $L_{1}$-structure, and $\mathcal{N}$ be an
$L_{2}$-structure. Then we call $\mathcal{N}$ _interpretable_ in $\mathcal{M}$
if there exist some $n\in\mathbb{N}$, some set $S\subseteq\mathcal{M}^{n}$,
and a bijection $\phi:S\to\mathcal{N}$ such that

  1. 1.

$S$ is definable in $\mathcal{M}$

  2. 2.

For every $\sigma$ in the signature of $L_{2}$, including the equality
relation, the preimage by $\phi$ of the graph of $\sigma$ is definable in
$\mathcal{M}$

Since we will only be dealing with the case of a monoid, point 2 reduces to
checking the preimages of equality $\phi^{-1}(=)$ and multiplication
$\phi^{-1}(\cdot)$, with the latter being the set of triples $(a,b,c)\in
S^{3}$ such that $\phi(a)\cdot\phi(b)=\phi(c)$.

Note that in the above definition we insisted the map $\phi$ be a bijection,
as in section 1.3 of [34]. The interpretation we will build will be a
bijection. However, the most general theory of interpretations works with
surjections from $S$ onto $\mathcal{N}$. See section 5 of [17] for more
information.

The following result will prove fundamental, and is a consequence of theorem
5.3.2 and its remarks in [17]:

######  Proposition 2.10.

Suppose $L_{1}$ and $L_{2}$ are languages, with $M_{1}$ and $M_{2}$ being
$L_{1}$\- and $L_{2}$-structures, respectively. Suppose $M_{1}$ is
interpretable in $M_{2}$. Then the problem of deciding $FOTh(M_{1})$ is
reducible to the problem of deciding $FOTh(M_{2})$.

Next we define the notion of bi-interpretability, which will be the subject of
section 3.2. By the definition of interpretations, it is straightforward to
see that interpretations are transitive: if $M_{1}$ is interpretable in
$M_{2}$, and $M_{2}$ is interpretable in $M_{3}$, then $M_{1}$ is
interpretable in $M_{3}$. This implies that if two structures are _mutually
interpretable_ , i.e. $M_{1}$ and $M_{2}$ are each interpretable in the other,
then we obtain an interpretation of $M_{1}$ in itself, and likewise an
interpretation of $M_{2}$ in itself.

######  Definition 2.11.

Given $M_{1}$ an $L_{1}$-structure, and $M_{2}$ an $L_{2}$-structure, we say
$M_{1}$ and $M_{2}$ are _bi-interpretable_ if $M_{1}$ and $M_{2}$ mutually
interpretable, and the map $\phi_{i}$ interpreting $M_{i}$ in itself is
definable in $M_{i}$, for $i=1,2$.

######  Example.

Presburger arithmetic is commonly expressed as $(\mathbb{N},0,1,+,\leq)$ and
$(\mathbb{Z},0,1,+,-,\leq)$. These two models are bi-interpretable.

The identity map $\phi$ on $\mathbb{N}\subset\mathbb{Z}$ definable by $0\leq
x$ interprets $(\mathbb{N},0,1,+,\leq)$ in $(\mathbb{Z},0,1,+,-,\leq)$, and
the map $\psi:\mathbb{N}^{2}\to\mathbb{Z}$ with $\psi(a,b)=a-b$ interprets as
a surjection $(\mathbb{Z},0,1,+,-,\leq)$ in $(\mathbb{N},0,1,+,\leq)$. We then
obtain $\phi\psi:S\to\mathbb{N}$ from the definable set $S=\\{(a,b)\ |\ a\geq
b\\}\subset\mathbb{N}^{2}$, with graph

$\\{(a,b,c)\ |\ a\geq b\land c+b=a\\}$

definable in $(\mathbb{N},0,1,+,\leq)$. We also obtain
$\psi\phi^{2}:T\to\mathbb{Z}$ with $T=\mathbb{N}^{2}$ definable in
$\mathbb{Z}^{2}$ by $0\leq x\land 0\leq y$, whose graph

$\\{(a,b,c)|\ 0\leq a\land 0\leq b\land c=a-b\\}$

definable in $(\mathbb{Z},0,1,+,-,\leq)$.

We will use these two notions of Presburger arithmetic interchangeably.

##  3 The case $n=2$

###  3.1 Interpreting $P_{2}$ in $(\mathbb{Z},0,1,+,-,\leq)$

First, we will explicitly treat the case $n=2$ of tableaux on two letters.
Such tableaux have three possible columns:

2
1 , 1 , 2 .

Denote by $t$ the word $21$ in $A^{*}$. Then by abuse of notation
$\mathcal{C}^{*}=\\{t,1,2\\}^{*}$, and our rewriting system becomes:

$R=\\{21\to t\ ,\ 2t\to t2\ ,\ 1t\to t1\\}$

By the two commutativity rules, and the fact that any factor $21$ would not
appear in a reduced word, we can write any reduced word $w\in(\mathcal{C},R)$
as some $t^{w_{1}}1^{w_{2}}2^{w_{3}}$. Thus, by completeness of the rewriting
system, each element of $P_{2}$ corresponds to a triple
$(w_{1},w_{2},w_{3})\in\mathbb{N}^{3}$, associated to a normal form
$t^{w_{1}}1^{w_{2}}2^{w_{3}}$. Likewise, each such triple corresponds to a
tableau, hence an element of $P_{2}$.

Consider the map $\phi:S\to P_{2}$, where
$S=\mathbb{N}^{3}\subset\mathbb{Z}^{3}$ is definable by the formula

$(0\leq x_{1})\land(0\leq x_{2})\land(0\leq x_{3})$

and $\phi(x_{1},x_{2},x_{3})=t^{x_{1}}1^{x_{2}}2^{x_{3}}$. This is a bijection
from a definable set in $(\mathbb{Z},0,1,+,-,\leq)$, and the inverse graph of
equality will be

$\displaystyle\phi^{-1}(=)$
$\displaystyle=\left\\{(a_{1},a_{2},a_{3},b_{1},b_{2},b_{3})\in\mathbb{N}^{6}\
|\ t^{a_{1}}1^{a_{2}}2^{a_{3}}=t^{b_{1}}1^{b_{2}}2^{b_{3}}\right\\}$
$\displaystyle=\left\\{(a_{1},a_{2},a_{3},b_{1},b_{2},b_{3})\in\mathbb{N}^{6}\
|\ a_{1}=b_{1},\ a_{2}=b_{2},\ a_{3}=b_{3}\right\\}\subset\mathbb{Z}^{6}$

Which is definable by the formula $(\underline{a}\in S)\land(\underline{b}\in
S)\land\bigwedge\limits_{i\in[3]}(a_{i}~{}=~{}b_{i})$

We check the preimage of the graph of multiplication

$\displaystyle\phi^{-1}(\circ)=\left\\{(\underline{a},\underline{b},\underline{c})\in
S^{3}\ |\
t^{a_{1}}1^{a_{2}}2^{a_{3}}t^{b_{1}}1^{b_{2}}2^{b_{3}}=t^{c_{1}}1^{c_{2}}2^{c_{3}}\right\\}$

Explicitly checking the multiplication yields

$\displaystyle t^{a_{1}}1^{a_{2}}2^{a_{3}}t^{b_{1}}1^{b_{2}}2^{b_{3}}$
$\displaystyle=t^{a_{1}+b_{1}}1^{a_{2}}2^{a_{3}}1^{b_{2}}2^{b_{3}}$
$\displaystyle=\begin{cases}t^{a_{1}+b_{1}+a_{3}}1^{a_{2}+b_{2}-a_{3}}2^{b_{3}},\
a_{3}\leq b_{2}\\\ t^{a_{1}+b_{1}+b_{2}}1^{a_{2}}2^{b_{3}+a_{3}-b_{2}},\
b_{2}\leq a_{3}\end{cases}$

Thus we get the following formula for $\phi^{-1}(\circ)$

$\displaystyle(\underline{a}\in S)\land(\underline{b}\in
S)\land(\underline{c}\in S)\land$ $\displaystyle[(a_{3}\leq b_{2}\land
c_{1}=a_{1}+b_{1}+a_{3}\land c_{2}=a_{2}+b_{2}-a_{3}\land c_{3}=b_{3})$
$\displaystyle\lor$ $\displaystyle(b_{2}\leq a_{3}\land
c_{1}=a_{1}+b_{1}+b_{2}\land c_{2}=a_{2}\land c_{3}=b_{3}+a_{3}-b_{2})]$

It follows then that $\phi$ is an interpretation of $P_{2}$ in Presburger
arithmetic. This yields the following result.

######  Theorem 1.

$P_{2}$ has decidable first order theory

###### Proof.

Since $\phi$ above is an interpretation of $P_{2}$ in
$(\mathbb{Z},0,1,+,-,\leq)$, every first order formula of $P_{2}$ is
interpreted as a first order formula of Presburger arithmetic, which is
decidable by 2.6. ∎

Note that this argument is closely related to the proof that the bicyclic
monoid $B=\langle a,b\ |\ ba=\varepsilon\rangle$ has decidable first order
theory (see section 2.4 of [11]). Indeed, the map $\psi:P_{2}\to B$ sending 1
to $a$, 2 to $b$, and $t$ to $\varepsilon$ is a monoid homomorphism, and
$\psi\circ\phi:S\to B$ is an interpretation of the bicyclic monoid in
Presburger arithmetic.

###  3.2 Bi-interpretability

The centre of $P_{2}$, $Z(P_{2})=\\{t^{n}|\ n\in\mathbb{N}\\}$ is a subset of
$P_{2}$ which is isomorphic to $(\mathbb{N},0,1,+,\leq)$, with $a\leq b$ in
$\mathbb{N}$ corresponding to $\exists y:t^{a}y=t^{b}$, and addition
corresponding to monoid multiplication. The centre is definable in $P_{2}$ via
the formula $x1=1x\land x2=2x$, since $P_{2}$ is finitely generated. We can
therefore take $\psi:Z(P_{2})\to\mathbb{N}$ to be an interpreting map of
$(\mathbb{N},0,1,+,\leq)$ in $P_{2}$.

######  Proposition 3.1.

$P_{2}$ and Presburger arithmetic are bi-interpretable.

###### Proof.

Firstly, note that $\phi:\mathbb{N}^{3}\to P_{2}$ defined as above is also an
interpreting map of $P_{2}$ into $(\mathbb{N},0,1,+,\leq)$, by replacing any
subtraction formulas $a=b-c$ with $a+c=b$. Let $\psi:Z(P_{2})\to\mathbb{N}$ be
the interpretation described above. Then $\psi\phi:S\to\mathbb{N}$, where $S$
is the definable subset $\\{(n,0,0)\ |\
n\in\mathbb{N}\\}\subset\mathbb{N}^{3}$, is the isomorphism sending $(n,0,0)$
to $n$, which is clearly definable.

Consider $\phi\psi:Z(P_{2})^{3}\to P_{2}$, sending $(t^{a},t^{b},t^{c})$ to
$w=t^{a}1^{b}2^{c}$. We have that the sets $S_{1}=\\{1^{n}|\
n\in\mathbb{N}\\}$ and $S_{2}=\\{2^{n}|\ n\in\mathbb{N}\\}$ are definable in
$P_{2}$ as follows:

First, let $C_{1}=\\{t^{a}1^{b}|\ a,b\in\mathbb{N}\\}\subset P_{2}$ be the set
of elements satisfying

$\exists y:yx\in Z(P_{2})$

then $S_{1}$ will be the set of elements satisfying

$x\in C_{1}\land\forall y\forall z:y\in Z(P_{2})\land x=yz\implies
y=\varepsilon$

Likewise, for $C_{2}=\\{t^{a}2^{b}|\ a,b\in\mathbb{N}\\}\subset P_{2}$ defined
by $\exists y:xy\in Z(P_{2})$, we have that the following formula defines
$S_{2}$:

$x\in C_{2}\land\forall y\forall z:y\in Z(P_{2})\land x=yz\implies
y=\varepsilon$

These formulas state that if we can write $x$ as $t^{a}1^{b}$ (respectively
$t^{a}2^{b}$) then we must have $a=0$, meaning $x$ must belong to $S_{1}$
(respectively $S_{2}$).

Given $t^{b}$ we can define $x=1^{b}$ by

$\exists z:x\in S_{1}\land z\in S_{2}\land zx=t^{b}$

Likewise we can define $y=2^{c}$ by

$\exists z:z\in S_{1}\land y\in S_{2}\land yz=t^{b}$

Then we have that $\phi\psi(t^{a},t^{b},t^{c})=t^{a}xy$, which is definable. ∎

##  4 The general case

Throughout this section, let $k=|\mathcal{C}|=2^{n}-1$. Index $\mathcal{C}$ by
$i\in[k]$ with $i~{}<~{}j~{}\iff~{}c_{i}~{}\sqsubset~{}c_{j}$

Let $S\subseteq\mathbb{N}^{k}$ be the set of all $(v_{1},\dots,v_{k})$ such
that $c_{1}^{v_{1}}\dots c_{k}^{v_{k}}$ is the normal form of a tableau, and
let $\phi:S\to P_{n}$ be the natural bijection. The normal form of any tableau
will obey compatibility conditions: for each pair $(a,b)\in[k]\times[k]$ such
that $a<b$ and $c_{a}\nsucceq c_{b}$, we have that either $v_{a}=0$ or
$v_{b}=0$. Let $I\subset[k]\times[k]$ be the set of all such pairs. Then
$S\subset\mathbb{Z}^{k}$ is defined by the formula

$\bigwedge\limits_{i\in[k]}(0\leq x_{i})\land\bigwedge\limits_{(a,b)\in
I}\left[(x_{a}=0)\lor(x_{b}=0)\right]$

We claim that $\phi$ is an interpreting map of $P_{n}$ in Presburger
arithmetic. Again, we check the diagonal:

$\displaystyle\phi^{-1}(=)=\\{(\underline{a},\underline{b})\in S^{2}\ |\
\phi(\underline{a})=\phi(\underline{b})\\}$

Which is definable by $(\underline{a}\in S)\land(\underline{b}\in
S)\land\bigwedge\limits_{i\in[k]}(a_{i}=b_{i})$ as in the $n=2$ case. It
remains to check whether the preimage of the multiplication graph

$\phi^{-1}(\circ)=\left\\{(\underline{a},\underline{b},\underline{c})\in
S^{3}\ |\
\phi(\underline{a})\phi(\underline{b})=\phi(\underline{c})\right\\}\subset\mathbb{Z}^{3k}$

is definable.

###  4.1 Multiplication – the idea

Using the previous section as a base case, we will proceed with the induction
hypothesis that, for each $2\leq i\leq n-1$, we have a formula $\eta_{i}$ in
Presburger arithmetic defining multiplication in $P_{i}$.

We first consider the structure of multiplication in $P_{n}$. The recursive
nature of Schensted’s algorithm yields a characterisation of multiplication in
$P_{n}$ via bottom rows and top tableaux.

######  Definition 4.1.

We call a tableau $t\in P_{n}$ a _top tableau_ if its row reading is a word
over $\\{2,\dots,n\\}^{*}$. i.e. there are no 1’s appearing in the tableau
word representing $t$.

Note that each $u\in P_{n}$ will have an associated top tableau – if
$u=r_{1}\dots r_{l}$, then $r_{1}\dots r_{l-1}$ will be a top tableau.

For $u,v\in P_{n}$, the product $uv$ will be computed by first running an
insertion algorithm into the bottom row of $u$, and then inserting any bumped
letters into the top tableau associated to $u$. We will make this idea more
precise.

######  Definition 4.2.

Define the following maps:

  1. 1.

The top map $T:P_{n}\to P_{n}$ maps an element $w$ with row form $r_{1}\dots
r_{l}$ in $A^{*}$ to its corresponding top tableau $T(w)=r_{1}\dots r_{l-1}$

  2. 2.

The bottom map $B:P_{n}\to P_{n}$ maps an element $w$ as above to its bottom
row $B(w)=r_{l}$

######  Example.

Let $t=$ 3&4
233
11244
. Then $T(t)=34\ 233$ and $B(t)=11244$

For $u,v\in P_{n}$, by the structure of Schensted’s algorithm, the product
$uv$ will run an insertion algorithm first into $B(u)$, followed by any
letters that are bumped being inserted into $T(u)$. This yields the following
characterisation of the top and bottom of the product:

$\displaystyle T(uv)$ $\displaystyle=T(u)T(B(u)v)$ $\displaystyle B(uv)$
$\displaystyle=B(B(u)v)$

Where equality is taken to mean equality in $P_{n}$, not equality of words.
Note that the set of top tableaux, which is equivalently the image of $T$, is
a submonoid isomorphic to $P_{n-1}$ over the alphabet $\\{2,\dots,n\\}$. Thus
the product of top tableaux will be definable via $\eta_{i-1}$. Therefore, if
we can define the row $B(uv)$, and a way of stitching $T(uv)$ and $B(uv)$ into
one tableau $uv$, we will obtain $\eta_{i}$ a formula defining multiplication
in $P_{n}$

######  Definition 4.3.

The stitch map $\Sigma:P_{n}\times P_{n}\to P_{n}$ is defined as follows. For
$u\in P_{n}$ a top tableau with row reading $r_{1}\dots r_{n}\in A^{*}$ and
$v$ a row with row reading $r_{v}\in A^{*}$, $\Sigma(u,v)=uv$ if $r_{1}\dots
r_{n}r_{v}$ is the row reading of a tableau. Otherwise,
$\Sigma(u,v)=\varepsilon$.

If $\Sigma$ has nontrivial output, we call $u$ and $v$ _compatible_ , and $uv$
the “stitched” tableau.

######  Example.

Suppose $u=43322234$ and $v=11113$. Then $\Sigma(u,v)=uv$, with corresponding
tableau

4
3&3
22234
11113

Note that $\Sigma(T(u),B(u))=u$. We can thus characterise multiplication via
the above maps as follows

$\displaystyle uv$ $\displaystyle=\Sigma(T(uv),B(uv))$
$\displaystyle=\Sigma(T(u)T(B(u)v),B(B(u)v))$

Let us consider the structure of $w\in P_{n}$ as a word in normal form in
$\mathcal{C}^{*}$. We have that $w=c_{1}^{w_{1}}c_{2}^{w_{2}}\dots
c_{k}^{w_{k}}$ for some $w_{i}\in\mathbb{N}$ for each $i$, satisfying some
compatibility conditions. But consider now each block $c_{i}^{m}$ for some
$m\in\mathbb{N}$ as a tableau word in row form in the presentation $\langle
A|K\rangle$. Then for $c_{i}=x_{1}x_{2}\dots x_{r}$ in row form in $A^{*}$, we
have that $c_{i}^{m}=x_{1}^{m}x_{2}^{m}\dots x_{r}^{m}$ in row form in
$A^{*}$. For each $c_{i}$, this row form is unique, since each column
corresponds to a unique decreasing sequence in $A^{*}$.

Define $\alpha$ to be the finite sequence of letters in $A$ which first
outputs in order the letters in the row form of $c_{1}$, then the letters of
the row form of $c_{2}$, and so on. We also define $\beta$ to be the finite
sequence, taking values in $[k]$, with $\beta_{i}=j$ when $\alpha_{i}$ is a
letter from column $c_{j}$.

######  Example.

The seven columns of $P_{3}$:

3
2
1 , 2
1 , 3
1 , 3
2 , 1 , 2 , 3 , yield

$\displaystyle\alpha$ $\displaystyle=3,2,1,2,1,3,1,3,2,1,2,3$
$\displaystyle\beta$ $\displaystyle=1,1,1,2,2,3,3,4,4,5,6,7$

Denote the length of $\alpha$ and $\beta$ by $\ell$, which is fixed for any
choice of $n$. Then we can write
$w=\alpha_{1}^{w_{\beta_{1}}}\dots\alpha_{\ell}^{w_{\beta_{\ell}}}$, where
$w_{\beta_{i}}$ is the coefficient of column $c_{\beta_{i}}$ in the normal
form of $w$.

######  Lemma 4.4.

Consider $u,v,w\in P_{n}$. Suppose $v$ has normal form $c_{1}^{v_{1}}\dots
c_{k}^{v_{k}}$. Then $w=uv$ is equivalent to the following:

There exist $u_{0},u_{1},\dots u_{\ell}\in P_{n}$ such that $u_{0}=u$,
$u_{\ell}=w$, and we have a recursive formula for $u_{i}$

$u_{i}=u_{i-1}\alpha_{i}^{v_{\beta_{i}}}$

This result is immediate from the structure of the insertion algorithm and the
fact $v=\alpha_{1}^{v_{\beta_{1}}}\dots\alpha_{\ell}^{v_{\beta_{\ell}}}$

######  Corollary 4.5.

$\phi^{-1}(\circ)$ is definable if the maps $\mu_{x}:\mathbb{N}\times S\to S$
such that $\phi(\mu_{x}(m,\underline{a}))=\phi(\underline{a})x^{m}$ are
definable for each $x\in A$.

###### Proof.

By lemma 4.4, given $\underline{a},\underline{b}\in S$, we have that
$\phi(\underline{c})=\phi(\underline{a})\phi(\underline{b})$ if and only if
there is some $\underline{c}^{0},\dots,\underline{c}^{\ell}$ such that
$\underline{c}^{0}=\underline{a},\ \underline{c}=\underline{c}^{\ell}$, and

$\underline{c}^{i}=\mu_{\alpha_{i}}(b_{\beta_{i}},\underline{c}^{i-1})$

so the preimage of the graph of multiplication is a composition of finitely
many applications of $\mu_{x}$, which will be definable if each $\mu_{x}$ is
definable. ∎

###  4.2 The formula defining $\mu_{x}$

Henceforth, $x$ is a fixed letter in $A$.

Recall that if $\underline{b}=\mu_{x}(m,\underline{a})$, then

$\displaystyle\phi(\underline{b})$ $\displaystyle=\phi(\underline{a})x^{m}$
$\displaystyle=\Sigma(T(\phi(\underline{a}))T(B(\phi(\underline{a}))x^{m}),B(B(\phi(\underline{a}))x^{m})).$

So we wish to obtain a formula of Presburger arithmetic describing

$\underline{b}=\phi^{-1}\Sigma(T(\phi(\underline{a}))T(B(\phi(\underline{a}))x^{m}),B(B(\phi(\underline{a}))x^{m}))$

We can break this down into a composition of several maps. First, define
$\underline{a}^{1}$ and $\underline{a}^{2}$ such that

$\displaystyle\underline{a}^{1}$ $\displaystyle=\phi^{-1}T\phi(\underline{a})$
$\displaystyle\underline{a}^{2}$ $\displaystyle=\phi^{-1}B\phi(\underline{a})$

Next, considering $R\subset P_{n}$ the set of row words, we define two maps
$\rho_{1},\rho_{2}:R~{}\to~{}S$ such that, for $r\in R$,
$\phi(\rho_{1}(r))=T(rx^{m})$ and $\phi(\rho_{2}(r))=B(rx^{m})$. Then since
$\phi(\underline{a}^{2})$ is a row, we can define $\underline{a}^{3}$ and
$\underline{a}^{4}$ to be such that

$\displaystyle\underline{a}^{3}=\rho_{1}(\phi(\underline{a}^{2}))$
$\displaystyle\underline{a}^{4}=\rho_{2}(\phi(\underline{a}^{2}))$

That is, $\phi(\underline{a}^{3})=T(B(\phi(\underline{a}))x^{m})$ and
$\phi(\underline{a}^{4})=B(B(\phi(\underline{a}))x^{m})$.

Next, define $\underline{a}^{5}$ to be such that

$\phi(\underline{a}^{5})=T(\phi(\underline{a}))T(B(\phi(\underline{a}))x^{m})=\phi(\underline{a}^{1})\phi(\underline{a}^{3})$

By our induction hypothesis, this will be definable, as the set of top
tableaux is generated by a known subset of columns. Thus the coefficients in
$\underline{a}^{5}$ will either be calculated by the formula $\eta_{n-1}$, or
will equal zero.

Finally, we have that

$\underline{b}=\phi^{-1}\Sigma(\phi(\underline{a}^{5}),\phi(\underline{a}^{4}))$

Since the composition of definable maps is definable, we have that $\mu_{x}$
is definable precisely when
$\phi^{-1}T\phi(\underline{a}),\phi^{-1}B\phi(\underline{a}),\rho_{1},\rho_{2},$
and $\phi^{-1}\Sigma(\phi(\ ),\phi(\ ))$ are definable. This will be the
subject of the following three lemmas.

######  Lemma 4.6.

The following maps are definable:

  1. i

$\phi^{-1}B\phi:S\to S$

  2. ii

$\phi^{-1}T\phi:S\to S$

###### Proof.

$(i)$ Define the finite sets $B_{a}$ for each $a\in A$ by

$B_{a}=\\{j\in[k]\ |\ c_{j}=x_{m}\dots x_{1}\land x_{1}=a\\}$

which are nonempty for each $a$. Then we get that
$\underline{b}=\phi^{-1}(B(\phi(\underline{a}))$ if and only if the following
formula holds:

$\bigwedge\limits_{i\in[k-n]}(b_{i}=0)\land\bigwedge\limits_{i\in[n]}\left(b_{k-n+i}=\sum_{j\in
B_{i}}a_{j}\right)$

The first part of the formula denoting the coefficient of each column of size
$\geq 2$ being zero, and the second part denoting the fact that each column
$x_{m}\dots x_{1}$ in $\phi(\underline{a})$ contributes to the coefficient of
the $x_{1}$ letter in the bottom row.

$(ii)$ Define the similar sets $T_{i}$ for each $i\in[k]$ by

$T_{i}=\\{j\in[k]\ |\ c_{j}=x_{m}\dots x_{1}\land x_{m}\dots x_{2}=c_{i}\\}$

Note that if $i\in B_{1}$, then $T_{i}=\emptyset$. Now, we have that
$\underline{b}=\phi^{-1}(T(\underline{a}))$ if and only if the following
formula holds:

$\bigwedge\limits_{i\in[k]}\left(b_{i}=\sum_{j\in T_{i}}a_{j}\right)$

Where we take the sum over an empty indexing set to be 0. ∎

Note that the sets $T_{i}$ and $B_{a}$ can be constructed algorithmically for
any given $n$. Given the set of columns as decreasing sequences, we can check
membership in each $B_{a}$ by considering the minimal element of a column, and
we can check membership in each $T_{i}$ by considering the column without its
minimal element. Note also that the set $B_{a}$ and $T_{j}$ partition $[k]$.

Next, we move on to defining the maps $\phi^{-1}T(rx^{m})$ and
$\phi^{-1}B(rx^{m})$.

######  Lemma 4.7.

The following maps are definable:

  1. i

$\rho_{1}\phi:S\to S$

  2. ii

$\rho_{2}\phi:S\to S$

###### Proof.

Consider $S_{R}\subset S$ to be the subset of normal forms corresponding to
rows (i.e. $S_{R}$ is the preimage of $R\subset P_{n}$). Then $S_{R}$ is a
subset definable by

$\bigwedge_{i\in[k-n]}x_{i}=0$

and $\rho_{1}\phi,\ \rho_{2}\phi$ will be maps from $S_{R}$ to $S_{R}$.
Indeed, by [41], the number of rows after running Schensted’s algorithm on any
$w\in A^{*}$ is equal to the length of the longest strictly decreasing
subsequence of $w$. Now, since we map a row $r$ to $rx^{m}\in A^{*}$, and
since $r$ is non-decreasing as a sequence in $A^{*}$, the longest strictly
decreasing subsequence of $w=rx^{m}$ can have length at most 2.

Now, write $\underline{r}=(0,\dots,0,r_{1},r_{2},\dots,r_{n})$. We will
describe explicitly $\underline{c}=(0,\dots,0,c_{1},\dots,c_{n})$ and
$\underline{d}~{}=~{}(0,\dots,d_{1},\dots,d_{n})$ such that
$\phi(\underline{c})=T(w)$ and $\phi(\underline{d})=B(w)$.

First, consider $B(w)$. In the setting $\langle A|K\rangle$, we will have
$x^{m}$ inserted into

$r=1^{r_{1}}2^{r_{2}}\dots(x+1)^{r_{x+1}}(x+2)^{r_{x+2}}\dots n^{r_{n}}$

It will bump $m$ letters from this row, starting at $x+1$. This means that
$d_{i}=r_{i}$ for $i<x$ and $d_{x}=r_{x}+m$. We will now consider the later
entries of $\underline{d}$:

In the first case, suppose $m\leq r_{x+1}$. Then we will bump $m$ letters
$x+1$ and replace them with letters $x$. This yields the effect that
$d_{x+1}=r_{x+1}-m$ and $d_{i}=r_{i}$ for all $i>x+1$.

Now, suppose $r_{x+1}\leq m\leq r_{x+1}+r_{x+2}$. Then all letters $x+1$ are
bumped, as are $m-r_{x+1}$ letters $x+2$. Thus we have that $d_{x+1}=0,\
d_{x+2}=r_{x+2}+r_{x+1}-m$, and $d_{i}=r_{i}$ for all $i>x+2$.

Continuing in this pattern, case $i$ then becomes

$\displaystyle\sum_{j=1}^{i-1}r_{x+j}\leq m\leq\sum_{j=1}^{i}r_{x+j}$

And in this case, $d_{x+j}=0$ for each $0<j<i$. Also,
$d_{x+i}=\sum_{j=1}^{i}r_{x+j}-m$, and all later entries remain unchanged.

Suppose we are now in the case

$\displaystyle\sum_{j=1}^{n-x}r_{x+j}\leq m$

Then we have $d_{x+j}=0$ for all $j$.

Each case yields a formula in terms of $\leq$, addition, and subtraction. Then
the disjunction of the above cases, which will be a finite formula, will
define $\underline{d}$ such that $\phi(\underline{d})=B(w)$.

Let us now consider $T(w)$. This will be the row of bumped letters, which will
mean that $c_{i}=0$ for any $i\leq x$. Now, suppose we are in case $i$ as
above. Then

$\displaystyle\sum_{j=1}^{i-1}r_{x+j}\leq m\leq\sum_{j=1}^{i}r_{x+j}$

and we will bump all letters $x+1,\dots,x+i-1$, as well as some letters $x+i$.
Therefore $c_{x+j}=r_{x+j}$ for $0<j<i$, and
$c_{x+i}=m-\sum_{j=1}^{i-1}r_{x+j}$. Note that the length of $r_{1}$ is always
exactly $m$ in this case.

Now suppose we are in the case

$\displaystyle\sum_{j=1}^{n-x}r_{x+j}\leq m$

Then we will have that $c_{x+j}=r_{x+j}$ for each $j$.

Again, as above, the disjunction of all the cases yields a formula defining
the graph of $\phi^{-1}T(rx^{m})$. ∎

We will now show the definability of the stitch map

######  Lemma 4.8.

The map $\phi^{-1}\Sigma(\phi(\ ),\phi(\ )):S^{2}\to S$ is definable.

###### Proof.

The condition for $\Sigma$ to have nontrivial action is definable via the
following formula:

Suppose $\underline{a}\ ,\ \underline{b}\in S$. Consider the set
$B_{1}=\\{i~{}\in~{}[k]\ |\ c_{i}~{}=~{}x_{m}\dots x_{1}\wedge x_{1}=a\\}$ as
in lemma 4.6. Then $\phi(\underline{a})$ being a top tableau is definable by
$\left(\bigwedge\limits_{i\in B_{1}}a_{i}=0\right)$. Also,
$\phi(\underline{b})$ being a row is definable by the formula
$\left(\bigwedge\limits_{i\in[k-n]}b_{i}=0\right)$

Now, let $e_{a}=\sum_{i\in B_{a}}a_{i}$. In order for it to be possible to
stitch two inputs, we need $e_{2}\leq b_{k-n+1}$, $e_{3}\leq
b_{k-n+2}+b_{k-n+1}-e_{2}$, and so on. We can rearrange this to get the
following compatibility condition:

$\underline{a}\in S\wedge\underline{b}\in S\wedge\left(\bigwedge\limits_{i\in
B_{1}}a_{i}=0\right)\wedge\bigwedge\limits_{i\in[k-n]}(b_{i}=0)\wedge\bigwedge\limits_{i\in[n]}\left(\sum_{j=1}^{i}e_{i}\leq\sum_{j=0}^{i-1}b_{k-n+j}\right)$

Where we take empty sums to be 0. Note that all sums used are finite, so we
obtain a valid formula in Presburger arithmetic. Denote this compatibility
formula $\gamma(\underline{a},\underline{b})$

If $\gamma$ is satisfied, we will define the stitch recursively. We wish to
construct
$\underline{d}=\phi^{-1}\Sigma(\phi(\underline{a}),\phi(\underline{b}))$.

When a top tableau $t$ is multiplied by a compatible bottom row, by the
bumping property of Schensted’s algorithm, columns of $t$ will be bumped from
left to right. Therefore, we must construct each coefficient
$d_{1},\dots,d_{k}$ in order, with columns of $\underline{a}$ and
$\underline{b}$ being ’used up’ in a sense.

Suppose we have calculated the coefficients $d_{1},\dots,d_{i-1}$, and have
obtained modified elements $\underline{a}^{i-1}$ and $\underline{b}^{i-1}$
representing all columns that have not yet been used up in a stitch. We
calculate the coefficient $d_{i}$ as follows:

$d_{i}$ is the coefficient of $c_{i}\in\mathcal{C}$, which we can write as
$c_{i}=x_{m}\dots x_{1}\in A^{*}$. Then $x_{m}\dots x_{2}$ and $x_{1}$ are two
columns, which we denote respectively by $c_{i_{T}}$ and $c_{i_{B}}$ in
$\mathcal{C}$. By the structure of Schensted’s algorithm it is straightforward
to see that $d_{i}=\min(a_{i_{T}}^{i-1},b_{i_{B}}^{i-1})$, which is definable
in Presburger arithmetic by

$\displaystyle(a^{i-1}_{i_{T}}\leq b^{i-1}_{i_{B}}\land
d_{i}=a^{i-1}_{i_{T}})\lor(b^{i-1}_{i_{B}}\leq a^{i-1}_{i_{T}}\land
d_{i}=b^{i-1}_{i_{B}})$

Now define $a^{i}_{j}=a^{i-1}_{j}$ for $j\neq i_{T}$, and
$a^{i}_{i_{T}}=a^{i-1}_{i_{T}}-d_{i}$. Likewise, define
$b^{i}_{j}=b^{i-1}_{j}$ for $j\neq i_{B}$ and
$b^{i}_{i_{B}}=b^{i-1}_{i_{B}}-d_{i}$. This corresponds to the fact that these
columns have now been used up in a stitch. Note that we will always get one of
these coefficients being set to zero. This is clearly definable in Presburger
arithmetic, and we will denote the formula for obtaining $\underline{a}^{i}$
and $\underline{b}^{i}$ from $\underline{a}^{i-1}$ and $\underline{b}^{i-1}$
by $\delta_{i}$, taking $\underline{a}^{0}=\underline{a}$ and
$\underline{b}^{0}=\underline{b}$. This also allows us to calculate $d_{1}$ in
terms of $\underline{a}^{0}$ and $\underline{b}^{0}$

Now we get that $\phi^{-1}\Sigma(\phi(\ ),\phi(\ ))$ has graph
$\\{\underline{a},\underline{b},\underline{d}\\}$ satisfying:

$\displaystyle\gamma(\underline{a},\underline{b})\land\exists\underline{a}^{0}\dots\exists\underline{a}^{k}\exists\underline{b}^{0}\dots\exists\underline{b}^{k}:(\underline{a}^{0}=\underline{a})\land(\underline{b}^{0}=\underline{b})\land\left(\bigwedge_{i\in[k]}d_{i}=\min(a^{i-1}_{i_{T}},b^{i-1}_{i_{B}})\land\delta_{i}\right)$

∎

With the above lemmas in hand, we can now prove the following result.

######  Proposition 4.9.

For any $x\in A$, the map $\mu_{x}$ is definable.

###### Proof.

By the discussion before lemma 4.6, $\mu_{x}$ is a composition of the maps
$\phi^{-1}B\phi,\ \phi^{-1}T\phi,\ \rho_{1}\phi,\ \rho_{2}\phi,\
\phi^{-1}\Sigma(\phi(\ ),\phi(\ ))$, and multiplication of top tableaux. By
lemmas 4.6, 4.7, and 4.8, all five required maps are definable.

To define
$\underline{a}^{5}=\phi^{-1}(T(\phi(\underline{a}))T(B(\phi(\underline{a}))x^{m}))$,
first note that since $\underline{a}^{5}$ denotes a top tableau, we have that
$a^{5}_{i}=0$ for each $i\in B_{1}$ as defined in lemma 4.6. Furthermore, for
each $i\notin B_{1}$, we have that $a^{5}_{i}$ is determined by the formula
$\eta_{n-1}$ applied to $\phi^{-1}(T(\phi(\underline{a})))$ and
$\phi^{-1}(T(B(\phi(\underline{a}))x^{m}))$. This determines $\eta_{n}$ by
induction, with base case $\eta_{2}$ as detailed in section 3.1. This
completes the proof. ∎

######  Theorem 2.

For any $n$, the first order theory of $P_{n}$ decidable

###### Proof.

By proposition 4.9 and corollary 4.5, $\phi^{-1}(\circ)$ is definable. Thus
$\phi:S\to P_{n}$ is an interpretation of $P_{n}$ in Presburger arithmetic.
This reduces $FOTh(P_{n})$ to $FOTh\left(\mathbb{Z},0,1,+,-,\leq\right)$,
which is decidable by lemma 2.6. ∎

By transitivity of interpretations, we have the following corollary.

######  Corollary 4.10.

For any $n\in\mathbb{N},\ P_{n}$ is PE interpretable in $P_{2}$

######  Corollary 4.11.

The diophantine problem (via the positive existential theory) and the problem
of checking if a given identity holds (via the positive universal theory) are
decidable in $P_{n}$

##  5 The Diophantine problem in the infinite case

We note that the above interpretations were constructed algorithmically in a
uniform way. That is to say, there will exist an effective procedure which,
given $n$, will construct the interpreting map for $P_{n}$. The procedure runs
as follows:

  1. 1.

Generate the interpretation for $P_{n-1}$

  2. 2.

Given $n$, generate the power set of $[n]$ except the empty set.

  3. 3.

Enumerate this set by the order $\sqsubseteq$ on columns. Since each column is
a decreasing sequence of elements in $[n]$, each column corresponds to a
unique element of the power set.

  4. 4.

Run Schensted’s algorithm on each pair of columns. If the output of running
Schensted’s algorithm on $c_{i}c_{j}$ is not $c_{i}c_{j}$, then $(i,j)$ is an
incompatible pair.

  5. 5.

Generate the formula defining $S$ by conjuncting with $x_{i}=0\lor x_{j}=0$
for each incompatible pair discovered in step 3.

  6. 6.

Generate the formula defining equality in terms of the formula defining $S$.

  7. 7.

Generate the formula for $\mu_{x}$ in terms of the interpretation for
$P_{n-1}$

  8. 8.

Generate the sequences $\alpha$ and $\beta$ from lemma 4.4. Steps 7 and 8
yield a formula defining multiplication.

Step 1 will repeat recursively until we reach $P_{2}$, which can be written
explicitly as in section 3.

###  5.1 The plactic monoid of all tableaux

We consider $A=\mathbb{N}\setminus\\{0\\}$ with $K_{\mathbb{N}}$ the set of
Knuth relations for all triples $(x,y,z)~{}\in~{}\mathbb{N}^{3}$. Then the
associated plactic monoid $P(\mathbb{N})$ is the monoid of _all_ semistandard
Young tableaux. Despite the work in this paper, the question of deciding the
theory of $P(\mathbb{N})$ remains open. However, we present an algorithm, by
uniformity, for deciding the Diophantine problem for $P(\mathbb{N})$.

######  Lemma 5.1.

For any $n\in\mathbb{N}$ the map $\phi:P(\mathbb{N})\to P_{n}$, defined on
generators as $\phi(k)=k$ if $k\leq n$ and $\phi(k)=\varepsilon$ if $k>n$ and
extended to words in the natural way, is a homomorphism.

###### Proof.

Considered as a map from $\mathbb{N}^{*}$ to $[n]^{*}$, $\phi$ is clearly a
homomorphism. It only remains to show that $\phi$ is well defined as a map
from $P(\mathbb{N})$ to $P_{n}$. We will show this by proving that each Knuth
relation in $K_{\mathbb{N}}$ will map to a relation that holds in $P_{n}$.

Suppose $u=xzy$ and $v=zxy$, for $x\leq y<z$. If $z\leq n$ then $\phi(u)=u,\
\phi(v)=v,$ and $u=v$ in $P_{n}$ so there is nothing to prove. If $z>n$ then
$\phi(u)=\phi(x)\phi(y)=\phi(v)$, as $\phi(z)=\varepsilon$. Thus
$\phi(u)=\phi(v)$ will always hold in $P_{n}$. An analogous argument shows
$\phi(u)=\phi(v)$ for $u=yxz$ and $v=yzx$ with $x<y\leq z$. ∎

######  Theorem 3.

The Diophantine problem for $P(\mathbb{N})$ is decidable.

###### Proof.

Suppose we are given some equation $u_{1}X_{1}\dots
X_{n}u_{n+1}=v_{1}Y_{1}\dots Y_{m}v_{m+1}$. Denote this equation by $\varphi$.
We define the support of $\varphi$ to be all letters appearing in the supports
of $u_{i}$ and $v_{i}$

$supp(\varphi)=\bigcup_{i\leq n+1}supp(u_{i})\cup\bigcup_{j\leq
m+1}supp(v_{j})$

Let $k=\max(supp(\varphi))$. Then by the above proposition there exists a
homomorphism $\phi:P(\mathbb{N})\to P_{k}$. Since each $u_{i}$ and $v_{j}$ is
an element of $P_{k}$, $\phi(u_{i})=u_{i}$ and $\phi(v_{j})=v_{j}$.

Suppose $\varphi$ has a solution $(x_{1},\dots,x_{n},y_{1},\dots,y_{m})\in
P(\mathbb{N})^{m+n}$.

Then $(\phi(x_{1}),\dots\phi(x_{n}),\phi(y_{1}),\dots,\phi(y_{m}))\in
P_{k}^{n+m}$ will also be a solution to $\varphi$. Thus $\varphi$ has a
solution in $P(\mathbb{N})$ if and only if it has a solution in $P_{k}$.

Now, since there is a uniform algorithm for deciding first order sentences in
$P_{k}$ for any $k$, we obtain the following procedure for solving Diophantine
problems in $P(\mathbb{N})$:

  1. 1.

Given $\varphi$ as input, calculate $k=\max(supp(\varphi))$.

  2. 2.

Generate the interpretation of $P_{k}$ into Presburger arithmetic

  3. 3.

Interpret the sentence

$\exists X_{1}\dots\exists X_{n}\exists Y_{1}\dots\exists
Y_{m}:u_{1}X_{1}\dots X_{n}u_{n+1}=v_{1}Y_{1}\dots Y_{m}v_{m+1}$

in Presburger arithmetic using the interpretation of $P_{k}$, and check
whether it holds.

∎

###  5.2 A plactic monoid on integers

We need not restrict ourselves to plactic monoids generated by $\mathbb{N}$.

Let’s consider instead tableaux with labels taken from $\mathbb{Z}$. By the
total order on $\mathbb{Z}$ we obtain a set $K_{\mathbb{Z}}$ of Knuth
relations on triples $(x,y,z)\in\mathbb{Z}^{3}$. Define the plactic monoid on
integers to be $P(\mathbb{Z})=\langle\mathbb{Z}\ |\ K_{\mathbb{Z}}\rangle$.
This is an infintely generated plactic monoid, but note that $P(\mathbb{N})$
and $P(\mathbb{Z})$ are not isomorphic.

Indeed, suppose $\psi:P(\mathbb{Z})\to P(\mathbb{N})$ were an isomorphism.
Then for some $y\in P(\mathbb{Z})$ we have $\psi(y)=1$. Since 1 is
irreducible, we must have $y\in\mathbb{Z}$. Consider $x<y<z,\
x,y,z\in\mathbb{Z}$. Then by irreducibility, $\psi(x),\psi(z)\in\mathbb{N}$.
Thus we have some $a,b\in\mathbb{N}$ such that $1ab=1ba$. Such an equality
cannot hold in $P(\mathbb{N})$.

Given $\varphi$ a Diophantine equation in $P(\mathbb{Z})$, we will have
$supp(\varphi)$ a finite totally ordered set. This set will have some smallest
element $a\in\mathbb{Z}$ and some largest element $b\in\mathbb{Z}$. Then the
interval $[a,b]\subset\mathbb{Z}$ has size $k=b-a+1$, and we can define an
order preserving injective map from $supp(\varphi)$ to $[k]$. We will extend
this map to a homomorphism.

######  Lemma 5.2.

Let $\\{z_{1}<z_{2}<\dots<z_{n}\\}$ be a finite set of integers with their
standard order. Then the map $\phi:P(\mathbb{Z})\to P_{k}$, with
$k=z_{n}-z_{1}+1$ defined on generators by

$\phi(z)=\begin{cases}\varepsilon,\ z<z_{1}\\\ z-z_{1}+1,\
z\in[z_{1},z_{n}]\\\ \varepsilon,\ z>z_{n}\end{cases}$

and extended to words in the natural way, is a homomorphism

###### Proof.

As in lemma 5.1, consider $u=xzy$ and $v=zxy$, for $x\leq yz$. If more than
one letter in $\\{x,y,z\\}$ is mapped to $\varepsilon$, there is nothing to
prove. Likewise if no letters are mapped to $\varepsilon$. If only one letter
is mapped to $\varepsilon$, then this is either $x$, yielding
$\phi(u)=\phi(z)\phi(y)=\phi(v)$, or this letter is $z$, yielding
$\phi(u)=\phi(x)\phi(y)=\phi(v)$. An analogous argument holds for all other
Knuth relations. ∎

Thus, as in the case above, any Diophantine equation $\varphi$ is solvable in
$P(\mathbb{Z})$ if and only if it has a solution in a fixed finite rank
plactic monoid. Therefore, by uniformity of the above algorithm, the
Diophantine problem for $P(\mathbb{Z})$ is also decidable.

###  5.3 Two open questions

  1. 1.

Is the first order theory of $P(\mathbb{N})$ decidable? It is known that this
monoid satisfies no identities [18], and the above proof shows it has
decidable Diophantine problem. Can this be extended to the whole theory? What
about in the $P(\mathbb{Z})$ case?

  2. 2.

Do infinite rank plactic monoids defined on other generating sets have
decidable Diophantine problem? For example, does
$P(\mathbb{Q})=\langle\mathbb{Q}\ |\ K_{\mathbb{Q}}\rangle$ have decidable
Diophantine problem? What about $P(L)$ for an arbitrary recursive total order?

## Acknowledgements

This research was conducted during my master’s study at the University of East
Anglia, and will form part of my thesis. I thank Robert Gray for his support
and feedback as supervisor, and Lorna Gregory for her feedback and useful
discussion of the model theoretic background. I also thank the PhD student
community at the UEA for their support.

## References

  * [1] Antoine Abram and Christophe Reutenauer  “The Stylic Monoid”  arXiv, 2021  DOI: 10.48550/ARXIV.2106.06556
  * [2] Ronald V Book and Friedrich Otto  “String-rewriting systems”  Springer, 1993
  * [3] Alan J Cain et al.  “A note on identities in plactic monoids and monoids of upper-triangular tropical matrices”  In _arXiv:1705.04596_ , 2017
  * [4] Alan J. Cain, Robert D. Gray and António Malheiro  “Crystal monoids & crystal bases: Rewriting systems and biautomatic structures for plactic monoids of types An, Bn, Cn, Dn, and G2”  In _Journal of Combinatorial Theory, Series A_ 162, 2019, pp. 406–466  DOI: https://doi.org/10.1016/j.jcta.2018.11.010
  * [5] Alan J. Cain, Robert D. Gray and António Malheiro  “Finite Gröbner–Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids”  In _Journal of Algebra_ 423, 2015, pp. 37–53  DOI: https://doi.org/10.1016/j.jalgebra.2014.09.037
  * [6] Alan J. Cain, Robert D. Gray and António Malheiro  “Rewriting systems and biautomatic structures for Chinese, hypoplactic, and sylvester monoids”  In _International Journal of Algebra and Computation_ 25.01n02 World Scientific Pub Co Pte Lt, 2015, pp. 51–80  DOI: https://doi.org/10.1142%2Fs0218196715400044
  * [7] Alan J. Cain and António Malheiro  “Deciding conjugacy in sylvester monoids and other homogeneous monoids”  In _International Journal of Algebra and Computation_ 25.05 World Scientific Pub Co Pte Lt, 2015, pp. 899–915  DOI: https://doi.org/10.1142%2Fs0218196715500241
  * [8] Alan J. Cain, Marianne Johnson, Mark Kambites and António Malheiro  “Representations and identities of plactic-like monoids”  In _Journal of Algebra_ 606, 2022, pp. 819–850  DOI: https://doi.org/10.1016/j.jalgebra.2022.04.033
  * [9] Laura Ciobanu and Albert Garreta  “Group equations with abelian predicates”, 2022  arXiv:2204.13946 [math.GR]
  * [10] Laure Daviaud, Marianne Johnson and Mark Kambites  “Identities in upper triangular tropical matrix semigroups and the bicyclic monoid”  In _Journal of Algebra_ 501 Elsevier BV, 2018, pp. 503–525  DOI: https://doi.org/10.1016%2Fj.jalgebra.2017.12.032
  * [11] Volker Diekert and Markus Lohrey  “Word equations over graph products”  In _International Journal of Algebra and Computation_ 18.03 World Scientific, 2008, pp. 493–533
  * [12] Gérard Duchamp and Daniel Krob  “Plactic-Growth-Like Monoids”  In _Words, Languages And Combinatorics Ii: Proceedings Of The International Conference_ , 1994, pp. 124  World Scientific
  * [13] Benjamin Fine, Anthony Gaglione, Gerhard Rosenberger and Dennis Spellman  “The Tarski Problems and Their Solutions”  In _Advances in Pure Mathematics_ 5.04 Scientific Research Publishing, 2015, pp. 212
  * [14] William Fulton  “Young Tableaux: With Applications to Representation Theory and Geometry”, London Mathematical Society Student Texts  Cambridge University Press, 1996  DOI: 10.1017/CBO9780511626241
  * [15] Albert Garreta and Robert D. Gray  “On equations and first-order theory of one-relator monoids”  In _Information and Computation_ 281, 2021, pp. 104745  DOI: https://doi.org/10.1016/j.ic.2021.104745
  * [16] Florent Hivert, Jean-Christophe Novelli and Jean-Yves Thibon  “An analogue of the plactic monoid for binary search trees”  arXiv, 2002  DOI: 10.48550/ARXIV.MATH/0206246
  * [17] Wilfrid Hodges  “Model theory”  Cambridge University Press, 1993
  * [18] Marianne Johnson and Mark Kambites  “Tropical representations and identities of plactic monoids”  In _Transactions of the American Mathematical Society_ 374.6, 2021, pp. 4423–4447
  * [19] M. Kashiwara  “On crystal bases of the $Q$-analogue of universal enveloping algebras”  In _Duke Mathematical Journal_ 63.2 Duke University Press, 1991, pp. 465–516  DOI: 10.1215/S0012-7094-91-06321-0
  * [20] Olga Kharlampovich and Alexei Myasnikov  “Irreducible affine varieties over a free group. I. Irreducibility of quadratic equations and Nullstellensatz”  In _Journal of Algebra_ 200.2 New York: Academic Press,[1964-, 1998, pp. 472–516
  * [21] Olga Kharlampovich and Alexei Myasnikov  “Tarski’s problem about the elementary theory of free groups has a positive solution”  In _Electronic Research Announcements of the American Mathematical Society_ 4.14, 1998, pp. 101–108
  * [22] Donald Knuth  “Permutations, matrices, and generalized Young tableaux”  In _Pacific journal of mathematics_ 34.3 Mathematical Sciences Publishers, 1970, pp. 709–727
  * [23] Łukasz Kubat and Jan Okniński  “Identities of the plactic monoid”  In _Semigroup Forum_ 90.1, 2015, pp. 100–112  Springer
  * [24] Łukasz Kubat and Jan Okniński  “Plactic algebra of rank 3”  In _Semigroup Forum_ 84.2, 2012, pp. 241–266  Springer
  * [25] Alain Lascoux and Marcel-P Schützenberger  “Le monoıde plaxique”  In _Noncommutative structures in algebra and geometric combinatorics (Naples, 1978)_ 109, 1981, pp. 129–156
  * [26] Cédric Lecouvey  “Combinatorics of crystal graphs and Kostka–Foulkes polynomials for the root systems Bn,Cn and Dn”  In _European Journal of Combinatorics_ 27.4, 2006, pp. 526–557  DOI: https://doi.org/10.1016/j.ejc.2005.01.006
  * [27] Cédric Lecouvey  “Schensted-Type Correspondence, Plactic Monoid, and Jeu de Taquin for Type Cn”  In _Journal of Algebra_ 247.2, 2002, pp. 295–331  DOI: https://doi.org/10.1006/jabr.2001.8905
  * [28] Cedric Lecouvey  “Schensted type correspondence for type $G_{2}$ and computation of the canonical basis of a finite dimensional $U_{q}(G_{2})$-module”  arXiv, 2002  DOI: 10.48550/ARXIV.MATH/0211443
  * [29] Cedric lecouvey  “Schensted-type correspondences and plactic monoids for types $B_{n}$ and $D_{n}$”  arXiv, 2002  DOI: 10.48550/ARXIV.MATH/0211444
  * [30] Peter Littelmann  “A plactic algebra for semisimple Lie algebras”  Citeseer, 1995
  * [31] M. Lothaire  “Algebraic Combinatorics on Words”, Encyclopedia of Mathematics and its Applications  Cambridge University Press, 2002  DOI: 10.1017/CBO9781107326019
  * [32] Gennadiy Semenovich Makanin  “Equations in a free group”  In _Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya_ 46.6 Russian Academy of Sciences, Steklov Mathematical Institute of Russian …, 1982, pp. 1199–1273
  * [33] Gennady S Makanin  “The problem of solvability of equations in a free semigroup”  In _Mathematics of the USSR-Sbornik_ 32.2 IOP Publishing, 1977, pp. 129
  * [34] D. Marker  “Model Theory : An Introduction”, Graduate Texts in Mathematics  Springer New York, 2013
  * [35] Jean-Christophe Novelli  “On the hypoplactic monoid”  In _Discrete Mathematics_ 217.1, 2000, pp. 315–336  DOI: https://doi.org/10.1016/S0012-365X(99)00270-8
  * [36] Carl-Fredrik Nyberg-Brodda  “A word-hyperbolic special monoid with undecidable Diophantine problem”  arXiv, 2022  DOI: 10.48550/ARXIV.2205.01056
  * [37] Alf Onshuus and Mariana Vicaría  “Definable groups in models of Presburger Arithmetic”  In _Annals of Pure and Applied Logic_ 171.6, 2020, pp. 102795  DOI: https://doi.org/10.1016/j.apal.2020.102795
  * [38] M. Presburger  “Uber die Vollstandigkeiteines gewissen Systems der Arithmetik ganzer Zahlen, in welchen die Addition als einzige Operation hervortritt”  In _Comptes-Rendus du ler Congres des Mathematiciens des Pays Slavs_ , 1929  URL: https://cir.nii.ac.jp/crid/1571698599431503232
  * [39] W.. Quine  “Concatenation as a Basis for Arithmetic”  In _Journal of Symbolic Logic_ 11.4 Association for Symbolic Logic, 1946, pp. 105–114  DOI: 10.2307/2268308
  * [40] Alexander A Razborov  “On systems of equations in a free group”  In _Mathematics of the USSR-Izvestiya_ 25.1 IOP Publishing, 1985, pp. 115
  * [41] C. Schensted  “Longest Increasing and Decreasing Subsequences”  In _Canadian Journal of Mathematics_ 13 Cambridge University Press, 1961, pp. 179–191  DOI: 10.4153/CJM-1961-015-3
  * [42] M-P Schützenberger  “La correspondance de Robinson”  In _Combinatoire et représentation du groupe symétrique_ Springer, 1977, pp. 59–113
  * [43] Marcel P Schützenberger  “Sur une construction de Gilbert de B. Robinson”  In _Séminaire Dubreil. Algèbre et théorie des nombres_ 25.1, 1971, pp. 1–4
  * [44] Zlil Sela  “Diophantine geometry over groups I : Makanin-Razborov diagrams”  In _Publications Mathématiques de l’IHÉS_ 93 Institut des Hautes Études Scientifiques, 2001, pp. 31–105  URL: http://www.numdam.org/item/PMIHES_2001__93__31_0/
  * [45] Zlil Sela  “Word Equations I: Pairs and their Makanin-Razborov Diagrams”  arXiv, 2016  DOI: 10.48550/ARXIV.1607.05431
  * [46] Ryan Stansifer  “Presburger’s Article on Integer Airthmetic: Remarks and Translation”, 1984