# Generation and decidability for periodic $\ell$-pregroups

Nikolaos Galatos<EMAIL_ADDRESS>Isis A. Gallardo<EMAIL_ADDRESS>
###### Abstract

In [11] it is shown that the variety $\mathsf{DLP}$ of distributive
$\ell$-pregroups is generated by a single algebra, the functional algebra
$\mathbf{F}(\mathbb{Z})$ over the integers. Here, we show that $\mathsf{DLP}$
is equal to the join of its subvarieties $\mathsf{LP_{n}}$, for
$n\in\mathbb{Z}^{+}$, consisting of $n$-periodic $\ell$-pregroups. We also
prove that every algebra in $\mathsf{LP_{n}}$ embeds into the subalgebra
$\mathbf{F}_{n}(\mathbf{\Omega})$ of $n$-periodic elements of
$\mathbf{F}(\mathbf{\Omega})$, for some integral chain $\mathbf{\Omega}$; we
use this representation to show that for every $n$, the variety
$\mathsf{LP_{n}}$ is generated by the single algebra
$\mathbf{F}_{n}(\mathbb{Q}\overrightarrow{\times}\mathbb{Z})$, noting that the
chain $\mathbb{Q}\overrightarrow{\times}\mathbb{Z}$ is independent of $n$.

We further establish a second representation theorem: every algebra in
$\mathsf{LP_{n}}$ embeds into the wreath product of an $\ell$-group and
$\mathbf{F}_{n}(\mathbb{Z})$, showcasing the prominent role of the simple
$n$-periodic $\ell$-pregroup $\mathbf{F}_{n}(\mathbb{Z})$. Moreover, we prove
that the join of the varieties $\mathsf{V}(\mathbf{F}_{n}(\mathbb{Z}))$ is
also equal to $\mathsf{DLP}$, hence equal to the join of the varieties
$\mathsf{LP_{n}}$, even though
$\mathsf{V}(\mathbf{F}_{n}(\mathbb{Z}))\not=\mathsf{LP_{n}}$ for every single
$n$. In this sense $\mathsf{DLP}$ has two different well-behaved
approximations.

We further prove that, for every $n$, the equational theory of
$\mathbf{F}_{n}(\mathbb{Z})$ is decidable and, using the wreath product
decomposition, we show that the equational theory of $\mathsf{LP_{n}}$ is
decidable, as well.

###### keywords:

periodic lattice-ordered pregroups, decidability , equational theory , variety
generation , residuated lattices , lattice-ordered groups , diagrams

††journal: Journal of Algebra

[inst1]organization= Department of Mathematics, University of Denver,
addressline=2390 S. York St., city=Denver, postcode=80208, state=CO,
country=USA

##  1 Introduction

A _lattice-ordered pregroup_ (_$\ell$ -pregroup_) is an algebra
$(A,\wedge,\vee,\cdot,^{\ell},^{r},1)$, where $(A,\wedge,\vee)$ is a lattice,
$(A,\cdot,1)$ is a monoid, mutilication preserves the lattice order $\leq$,
and for all $x$,

$x^{\ell}x\leq 1\leq xx^{\ell}\text{ and }xx^{r}\leq 1\leq x^{r}x.$

We often refer to $x^{\ell}$ and to $x^{r}$ as the _left_ and _right inverse_
of $x$, respectively.

The $\ell$-pregroups that satisfy $x^{\ell}=x^{r}$ are exactly the _lattice-
ordered groups_ (_$\ell$ -groups_): algebras
$(A,\wedge,\vee,\cdot,{}^{-1},1)$, where $(A,\wedge,\vee)$ is a lattice
$(A,\cdot,{}^{-1},1)$ is a group, and mutilication preserves the order.
Lattice-ordered groups have been studied extensively ([1], [5], [12], [14])
and they admit a Calyey-style representation theorem due to Holland [13]:
every $\ell$-group can be embedded into the _symmetric_ $\ell$-group of order-
preserving permutations on a totally-ordered set.

_Pregroups_ are defined in a similar way as $\ell$-pregroups, but without the
stipulation that the underlying order yields a lattice. Pregroups were
introduced and studied in the context of mathematical linguistics, both in the
theoretical realm (in connection to context-free grammars and automata) and in
applications (for studying the sentence structure of various natural
languages), see [15], [4], [3]. Pregroups where the order is discrete (or,
equivalently, that satisfy $x^{\ell}=x^{r}$) are exactly groups.

It turns out that $\ell$-pregroups are precisely the _residuated lattices_
that satisfy $(xy)^{\ell}=y^{\ell}x^{\ell}$ and $x^{r\ell}=x=x^{\ell r}$ (see
[10]), hence they can be axiomatized by equations and they form a variety of
algebras which we denote by $\mathsf{LP}$. Since other examples of residuated
lattices include the lattice of ideals of a ring with unit, Boolean algebras,
and the algebra of binary relations over a set among others, $\ell$-pregroups
enjoy common properties with these structures (for example, congruences
correspond to ‘normal’ subalgebras). Furthermore, since residuated lattices
form algebraic semantics for _substructural logics_ [10] (including
intuitionistic, linear, relevance, and many-valued logic), the study of
$\ell$-pregroups relates to the study of these non-classical logical systems,
as well.

An $\ell$-pregroup is called _distributive_ , if its underlying lattice is
distributive. It is shown in [6] that distributive $\ell$-pregroups, like
$\ell$-groups, also enjoy a Cayley/Holland embedding theorem: every
distributive $\ell$-pregroup can be embedded in the _functional/symmetric_
$\ell$-pregroup $\mathbf{F}(\mathbf{\Omega})$ over a chain $\mathbf{\Omega}$.
Here $\mathbf{F}(\mathbf{\Omega})$ consists of all functions on
$\mathbf{\Omega}$ that have _residuals_ and _dual residuals_ of all orders (as
defined in Section 2.1) under composition and pointwise order. In [11] we
showed that this representation theorem can be improved in the sense that the
chain $\mathbf{\Omega}$ can be assumed to be integral; a chain is called
_integral_ if every point is contained in an interval isomorphic to
$\mathbb{Z}$. This tighter representation is used in [11] to show that the
variety of distributive $\ell$-pregroups is generated by a single algebra: the
functional algebra $\mathbf{F}(\mathbb{Z})$. Here, we establish similar
generation results for all periodic varieties of $\ell$-pregroups.

An $\ell$-pregroup is called _$n$ -periodic_, for $n\in\mathbb{Z}^{+}$, if it
satisfies $x^{\ell^{n}}=x^{r^{n}}$; we denote the corresponding variety by
$\mathsf{LP_{n}}$. For example, $2$-periodic $\ell$-pregroups satisfy
$x^{\ell\ell}=x^{rr}$, while $1$-periodic $\ell$-pregroups are precisely the
$\ell$-groups; we say that an $\ell$-pregroup is _periodic_ if it is
$n$-periodic for some $n\in\mathbb{Z}^{+}$. As we mention right below,
periodicity is related to distributivity, so there is hope of using a similar
approach as in [11] to obtain a representation theorem and a generation
result.

In particular, even though it is still an open problem whether every
$\ell$-pregroup is distributive (we only know that the underlying lattice is
semi-distributive by [9]), $\ell$-groups are known to be distributive and in
[7] it is shown that actually all periodic $\ell$-pregroups are distributive,
i.e., $\mathsf{LP_{n}}$ is a subvariety of $\mathsf{DLP}$ for all
$n\in\mathbb{Z}^{+}$.

In Section 2 , we make use of this fact to show that the representation
theorem of [11] for distrubutive $\ell$-pregroups restricts nicely to
$n$-periodic $\ell$-pregroups, for every $n$. In particular, first we observe
that if $\mathbf{\Omega}$ is a chain, then the elements of
$\mathbf{F}(\mathbf{\Omega})$ that satisfy $x^{\ell^{n}}=x^{r^{n}}$ form a
subalgebra $\mathbf{F}_{n}(\mathbf{\Omega})$ of $\mathbf{F}(\mathbf{\Omega})$
and we provide an alternative characterization for these elements; then we
show that every $n$-periodic $\ell$-pregroup embeds in
$\mathbf{F}_{n}(\mathbf{\Omega})$, for some integral chain $\mathbf{\Omega}$
(first representation for $n$-periodic $\ell$-pregroups). In other words the
operator $\mathbf{F}_{n}$ does for $\mathsf{LP_{n}}$ what the operator
$\mathbf{F}$ does for $\mathsf{DLP}$, at least in terms of an embedding
theorem. Moreover, utilizing that every integral chain $\mathbf{\Omega}$ is
locally isomorphic to $\mathbb{Z}$, we show that every function on
$\mathbf{\Omega}$ decomposes into a global component and many local
components, where the latter are elements of $\mathbf{F}_{n}(\mathbb{Z})$.
This shows the important role that $\mathbf{F}_{n}(\mathbb{Z})$ plays; we give
an acessible description of the elements of $\mathbf{F}_{n}(\mathbb{Z})$ and
show that the latter is a simple algebra. Finally, we extend the notion of
wreath product (for groups, monoids, and $\ell$-groups) to $\ell$-pregroups
and prove that every $n$-periodic $\ell$-pregroup embeds into the wreath
product $\mathbf{H}\wr\mathbf{F}_{n}(\mathbb{Z})$ of an $\ell$-group
$\mathbf{H}$ and $\mathbf{F}_{n}(\mathbb{Z})$ (second representation for
$n$-periodic $\ell$-pregroups).

As mentioned earlier, $\ell$-pregroups are involutive residuated lattices and
it turns out that the notion of $n$-periodicity for $\ell$-pregroups is just a
specialization of the one for involutive residuated lattices. In [8] it is
shown that the join of all of the $n$-periodic varieties of involutive
residuated lattices, for $n\in\mathbb{Z}^{+}$, is equal to the whole variety
of involutive residuated lattices; the proof is quite involved using both
algebraic and proof-theoretic arguments. It is natural to ask what is the join
of all of the $\mathsf{LP_{n}}$’s and in particular whether the join is all of
$\mathsf{DLP}$, given that each $\mathsf{LP_{n}}$ is a subvariety of
$\mathsf{DLP}$. Since we do not have an analytic proof-theoretic calculus for
$\ell$-pregroups we cannot use the methods of [8].

In Section 3 we prove that indeed $\mathsf{DLP}$ is equal to the join of all
of the varieties $\mathsf{LP_{n}}$. In more detail, using the method of
diagrams of [11] we show that if an equation fails in $\mathsf{DLP}$, then it
fails in $\mathbf{F}_{n}(\mathbb{Z})$, for some $n$. As a result we obtain
that $\mathsf{DLP}$ is also equal to the join of the varieties
$\mathsf{V}(\mathbf{F}_{n}(\mathbb{Z}))$, thus complementing nicely the
generation result for $\mathsf{DLP}$ given in [11]. With the goal of
converting the representation theorem for $\mathsf{LP_{n}}$, for every $n$,
into a generation result, we search for chains $\mathbf{\Omega}_{n}$ such that
the variety $\mathsf{LP_{n}}$ is generated by
$\mathbf{F}_{n}(\mathbf{\Omega}_{n})$. Since
$\bigvee\mathsf{LP_{n}}=\bigvee\mathsf{V}(\mathbf{F}_{n}(\mathbb{Z}))$, we
investigate whether we can take $\mathbf{\Omega}_{n}=\mathbb{Z}$ for all $n$.
It is easy to see that this cannot work for $n=1$, as
$\mathbf{F}_{n}(\mathbb{Z})$ is isomorphic to the $\ell$-group on the
integers, hence it generates the variety of abelian $\ell$-groups, not the
variety of all $\ell$-groups. We further prove that, unfortunately,
$\mathsf{LP_{n}}\not=\mathsf{V}(\mathbf{F}_{n}(\mathbb{Z}))$ for every single
$n$, contrasting with
$\bigvee\mathsf{LP_{n}}=\bigvee\mathsf{V}(\mathbf{F}_{n}(\mathbb{Z}))$. Since
$\mathbf{F}_{1}(\mathbb{Q})$ ends up being the $\ell$-group or order-
preserving permutations on $\mathbb{Q}$, Holland’s generation theorem shows
that we can take $\mathbf{\Omega}_{1}$ to be $\mathbb{Q}$, i.e.,
$\mathsf{LP_{1}}=\mathsf{V}(\mathbf{F}_{1}(\mathbb{Q}))$. We prove, however,
that $\mathsf{LP_{n}}\not=\mathsf{V}(\mathbf{F}_{n}(\mathbb{Q}))$, for every
$n>1$, leaving unsettled the question of whether there is a choice of
$\mathbf{\Omega}_{n}$ for each $n$; or whether we can select a single/uniform
chain $\mathbf{\Omega}$ that will serve as $\mathbf{\Omega}_{n}$ for all $n$,
i.e., $\mathsf{LP_{n}}=\mathsf{V}(\mathbf{F}_{n}(\mathbf{\Omega}))$. Later, in
Section 5, we prove that such a uniform choice of a chain does exist and can
be taken to be $\mathbb{Q}\overrightarrow{\times}\mathbb{Z}$, i.e.,
$\mathsf{LP_{n}}$ is generated by
$\mathbf{F}_{n}(\mathbb{Q}\overrightarrow{\times}\mathbb{Z})$, for all $n$
(generation theorem for $\mathsf{LP_{n}}$).

It follows from the wreath product representation
$\mathbf{H}\wr\mathbf{F}_{n}(\mathbb{Z})$ that, even though
$\mathbf{F}_{n}(\mathbb{Z})$ does not generate the variety $\mathsf{LP_{n}}$,
it plays an important role for $n$-periodic $\ell$-pregroups. It turns out
that a good understanding of this algebra is needed for the goal of Section 5,
so Section 4 is devoted to $\mathbf{F}_{n}(\mathbb{Z})$ and, among other
things, to proving that its equational theory is decidable. In particular, we
observe that each element $f$ of $\mathbf{F}_{n}(\mathbb{Z})$ admits a useful
decomposition $f=f^{\circ}\circ f^{*}$, where $f^{\circ}$ is an automorphism
of $\mathbb{Z}$ ($f^{\circ}\in F_{1}(\mathbb{Z})$) and $f^{*}$ is a _short_
element of $\mathbf{F}_{n}(\mathbb{Z})$. Furthermore, we consider diagrams (of
[11]) that are $n$-periodic (a new notion) and show that they are suitable for
studying $\mathbf{F}_{n}(\mathbb{Z})$: we can go from a failure of an equation
on $\mathbf{F}_{n}(\mathbb{Z})$ to an $n$-periodic diagram and back. As the
$n$-periodic diagrams obtained in this way can have unbounded _heights_ and a
decision algorithm would need a known bound of this height to terminate, we
focus on controlling the height of the automorphism part $f^{\circ}$ of a
function (the $f^{*}$ part is short by construction). We rephrase the height-
control problem in the language or linear algebra and, working with linear
systems, we prove that such an upper bound can indeed be computed, thus
leading to decidability.

In Section 5 we rely on the wreath product decomposition of the second
representation theorem. In particular, each function in
$\mathbf{F}_{n}(\mathbf{\Omega})$, where $\mathbf{\Omega}$ is an integral
chain, has a global component and many local components, which are elements of
$\mathbf{F}_{n}(\mathbb{Z})$ and thus can be controlled by results in Section
4. Since every integral chain has a lexicographic product structure
$\mathbf{J}\overrightarrow{\times}\mathbb{Z}$, where $\mathbf{J}$ is an
arbitrary chain, we introduce a notion of diagram suited for
$\mathbf{F}_{n}(\mathbf{\Omega})$, called $n$-periodic partition diagram, that
captures the natural partitioning induced by the lexicographic product on the
diagram and has local parts that are $n$-periodic diagrams. We prove that a
failure of an equation in $\mathbf{F}_{n}(\mathbf{\Omega})$ yields a failure
in an $n$-periodic partition diagram, we show that the latter can be taken to
be short per local component, and we further prove that any failure in an
$n$-periodic partition diagram can be materialized in
$\mathbf{F}_{n}(\mathbb{Q}\overrightarrow{\times}\mathbb{Z})$. This way, we
obtain both the generation result
$\mathsf{LP_{n}}=\mathsf{V}(\mathbf{F}_{n}(\mathbb{Q}\overrightarrow{\times}\mathbb{Z}))$
and that the latter has a decidabile equational theory.

##  2 Characterizing the elements of $\mathbf{F}_{n}(\mathbf{\Omega})$.

In this section, for every positive integer $n$, we define the $n$-periodic
$\ell$-pregroup of the form $\mathbf{F}_{n}(\mathbf{\Omega})$ over a given
chain $\mathbf{\Omega}$. These algebras will play an important role in the
representation and generation theorems for $n$-periodic $\ell$-pregroups.

###  2.1 The functional $\ell$-pregroup $\mathbf{F}(\mathbf{\Omega})$.

We first describe the functional/symmetric $\ell$-pregroup
$\mathbf{F}(\mathbf{\Omega})$ over a chain $\mathbf{\Omega}$. Given functions
$f:\mathbf{P}\rightarrow\mathbf{Q}$ and $g:\mathbf{Q}\rightarrow\mathbf{P}$
between posets, we say that $g$ is a _residual_ for $f$, or that $f$ is a
_dual residual_ for $g$, or that $(f,g)$ forms a _residuated pair_ if

$f(a)\leq b\Leftrightarrow a\leq g(b)\text{, for all }a\in P,b\in Q.$

The residual and the dual residual of $f$ are unique when they exists and we
denote them by $f^{r}$ and $f^{\ell}$, respectively; if they exist, they are
given by

$f^{r}(b)=\max\\{a\in P:f(a)\leq b\\}\quad\text{ and }\quad
f^{\ell}(a)=\min\\{b\in Q:a\leq f(b)\\}.$

If $f$ has a residual, i.e., if $f^{r}$ exists, then $f$ is called
_residuated_ and if it has a dual residual, i.e., if $f^{\ell}$ exists, , it
is called _dually residuated_. If the residual of $f^{r}$ exists, we denote it
by $f^{rr}$ or $f^{(-2)}$ and we call it the _second-order residual_ of $f$.
If the dual residual of $f^{\ell}$ exists, we denote it by $f^{\ell\ell}$ or
$f^{(2)}$ and we call it the _second-order dual residual_ of $f$. More
generally, $f^{r^{n}}$ or $f^{(-n)}$ is the _$n$ th-order residual_ of $f$, if
it exists, and $f^{\ell^{n}}$ or $f^{(n)}$ is the _$n$ th-order dual residual_
of $f$, if it exists.

Given a chain $\mathbf{\Omega}$, we denote by $F(\mathbf{\Omega})$ the set all
maps on $\mathbf{\Omega}$ that have residuals and dual residuals of all
orders. This set supports an $\ell$-pregroup $\mathbf{F}(\mathbf{\Omega})$,
under composition, identity, the pointwise order, r and ℓ. Since the elements
are functions with a chain a codomain and the order is pointwise,
$\mathbf{F}(\mathbf{\Omega})$ is a _distributive_ $\ell$-pregroup, i.e., its
underlying lattice is distrubutive; we denote by $\mathsf{DLP}$ the variety of
distrubutive $\ell$-pregroups. In [6] it is shown that every distrubutive
$\ell$-pregroup can be embedded in $\mathbf{F}(\mathbf{\Omega})$ for some
chain $\mathbf{\Omega}$.

We write $a\prec b$, when $a$ is covered by $b$ (i.e., when $b$ is a cover of
$a$) and also $a+1=b$ and $a=b-1$. A chain $\mathbf{\Omega}$ is said to be
_integral_ if it is isomorphic to the lexicographic product
$\mathbf{J}\overrightarrow{\times}\mathbb{Z}$ for some chain $\mathbf{J}$.

In [11] it is shown that every $\mathbf{F}(\mathbf{\Omega})$ embeds in
$\mathbf{F}(\overline{\mathbf{\Omega}})$ for some integral chain
$\overline{\mathbf{\Omega}}$ containing $\mathbf{\Omega}$. This results in an
improved representation theorem for $\mathsf{DLP}$: every distrubutive
$\ell$-pregroup can be embedded in $\mathbf{F}(\mathbf{\Omega})$ for some
integral chain $\mathbf{\Omega}$.

###  2.2 Functions in $\mathbf{F}(\mathbf{\Omega})$, where $\mathbf{\Omega}$
is integral

We now take a closer look at the elements in $\mathbf{F}(\mathbf{\Omega})$,
where $\mathbf{\Omega}$ is integral—in particular on how they behave under the
application of iterated inverses.

######  Lemma 2.1.

[11] If $f$ is an order-preserving map on a chain $\mathbf{\Omega}$ with
residual $f^{r}$ and dual residual $f^{\ell}$, and $a,b\in\Omega$, then:

  1. 1.

$f^{\ell}ff^{\ell}=f^{\ell}$, $f^{r}ff^{r}=f^{r}$, $ff^{\ell}f=f$ and
$ff^{r}f=f$.

  2. 2.

We have $b<f(a)$ iff $f^{r}(b)<a$. Also, $f(b)<a$ iff $b<f^{\ell}(a)$.

It is well known that a function $f:\mathbf{P}\rightarrow\mathbf{Q}$ is
residuated iff it is order-preserving and, for all $b\in Q$, the set $\\{a\in
P:f(a)\leq b\\}$ has a maximum in $\mathbf{Q}$; also, it is dually residuated
iff it is order-preserving and, for all $b\in Q$, the set $\\{b\in P:a\leq
f(b)\\}$ has a minimum. If a function is residuated, then it preserves
existing joins, and if it is dually residuated, it preserves existing meets.

We start by studying the effect of $f\mapsto f^{\ell\ell}$ on functions of
$\mathbf{F}(\mathbf{\Omega})$, where $\mathbf{\Omega}$ is integral; this
process is an $\ell$-pregroup automorphism (see [11], for example).

######  Lemma 2.2.

Assume that $\mathbf{\Omega}$ is an integral chain,
$f:\Omega\rightarrow\Omega$ is an order-preserving map and $x\in\Omega$.

  1. 1.

If $f^{\ell\ell}$ exists, then $f^{\ell\ell}(x)=f(x-1)+1$.

  2. 2.

If $f^{rr}$ exists, then $f^{rr}(x)=f(x+1)-1$.

###### Proof.

(1) We first show the claim for the case where $f^{\ell}f(x)=x$. Since
$x=f^{\ell}f(x)=\min\\{b\in\Omega:f(x)\leq f(b)\\}$, we get
$x-1\notin\\{b\in\Omega:f(x)\leq f(b)\\}$, hence $f(x)\nleq f(x-1)$; since
$\mathbf{\Omega}$ is a chain we get $f(x-1)<f(x)$. Therefore,
$f(x-1)<f(x-1)+1\leq f(x)$, which yields $f^{\ell}(f(x-1)+1)=x$, by the
definition of $f^{\ell}$. On the other hand, Lemma 2.1(1) yields
$ff^{\ell}f(x-1)=f(x-1)<f(x-1)+1$, so by Lemma 2.1(2) we get
$f^{\ell}f(x-1)<f^{\ell}(f(x-1)+1)=x$. Therefore, $f^{\ell}(f(x-1))<x$ and
$f^{\ell}(f(x-1)+1)\leq x$; taking into account that $f(x-1)\prec f(x-1)+1$ we
obtain $f^{\ell\ell}(x)=\min\\{b\in\Omega:x\leq f^{\ell}(b)\\}=f(x-1)+1$.

Now, we consider the case $f^{\ell}f(x)\neq x$. Since $f^{\ell}f(x)\leq x$ by
residuation, we get $f^{\ell}f(x)<x$. Also, since $f(x)<f(x)+1$, Lemma 2.1(2)
yields $x<f^{\ell}(f(x)+1)$; so $f^{\ell}f(x)<x<f^{\ell}(f(x)+1)$. Hence, by
the definition of $f^{\ell\ell}$, we have
$f^{\ell\ell}(x)=f(x)+1=f^{\ell\ell}(f^{\ell}(f(x)+1))$. So, for
$y:=f^{\ell}(f(x)+1)$ we have $f^{\ell\ell}(x)=f^{\ell\ell}(y)$. Consequently,
using Lemma 2.1(1) we obtain
$f^{\ell}f(y)=f^{\ell}ff^{\ell}(f(x)+1)=f^{\ell}(f(x)+1)=y$. In particular,
the element $y$ satisfies the conditions of the previous case, so
$f^{\ell\ell}(x)=f^{\ell\ell}(y)=f(y-1)+1$. Below we prove that
$f(y-1)=f(x-1)$, which yields $f^{\ell\ell}(x)=f(y-1)+1=f(x-1)+1$, as desired.

Since $y-1<y=f^{\ell}(f(x)+1)$, Lemma 2.1(2) gives $f(y-1)<f(x)+1$, so
$f(y-1)\leq f(x)$. As mentioned above, we have $f^{\ell}f(x)<x$, hence
$f^{\ell}f(x)\leq x-1$. Therefore, $f(x)=ff^{\ell}f(x)\leq f(x-1)$ by using
Lemma 2.1(1). In summary, we have $f(y-1)\leq f(x)\leq f(x-1)$. Since $x<y$,
we also get the other inequality: $f(x-1)\leq f(y-1)$. Statement (2) is the
dual of (1). ∎

Using induction and Lemma 2.2 we get the following formula.

######  Lemma 2.3.

If $\mathbf{\Omega}$ is an integral chain, $f\in F(\mathbf{\Omega})$ and
$n\in\mathbb{Z}$, then $f^{(2n)}(x)=f(x-n)+n$ for all $x\in\Omega$.

As usual, we denote the inverse image of a set $X\subseteq\Omega$ via a
function $f$ by $f^{-1}[X]$; we write $f^{-1}[a]$ for $f^{-1}[\\{a\\}]$.

######  Lemma 2.4.

[11] Given a chain $\mathbf{\Omega}$, a map $f$ on $\Omega$ is residuated and
dually residuated iff $f$ is order-preserving and for all $a\in\Omega$:

  1. 1.

If $a\in f[\Omega]$, then $f^{-1}[a]=[b,c]$, for some $b\leq c$ in $\Omega$.

  2. 2.

If $a\notin f[\Omega]$, there exists $b,c\in\Omega$ such that, $b\prec c$ and
$a\in(f(b),f(c))$.

In the case (1), $f^{\ell}(a)=b$ and $f^{r}(a)=c$; in the case (2),
$f^{\ell}(a)=c$ and $f^{r}(a)=b$. Moreover, if $\mathbf{\Omega}$ is integral
then this is further equivalent to $f\in F(\mathbf{\Omega})$.

A simple characterization of the elements of $\mathbf{F(\mathbb{Z})}$ is given
by the next lemma.

######  Lemma 2.5.

[11] If $f$ is a function on $\mathbb{Z}$, then $f\in F(\mathbb{Z})$ iff $f$
is order-preserving and $f^{-1}[a]$ is a bounded interval for all $a\in
f[\mathbb{Z}]$ iff $f$ is an order-preserving and $f^{-1}[a]$ is a finite set
for all $a\in f[\mathbb{Z}]$.

###  2.3 The $n$-periodic subalgebra $\mathbf{F}_{n}(\mathbf{\Omega})$ of
$\mathbf{F}(\mathbf{\Omega})$.

In the language of $\ell$-pregroups, we define $x^{(n)}$ for all
$n\in\mathbb{Z}$, by $x^{(0)}:=x$, $x^{(n+1)}:=(x^{(n)})^{\ell}$ if $n>0$ and
$x^{(n-1)}:=(x^{(n)})^{r}$ if $n<0$. Note that this notation agrees with the
notation for $f^{(n)}$, when this function exists. Given $n\in\mathbb{Z}^{+}$,
we say that an element $x$ is $n$-periodic if $x^{\ell^{n}}=x^{r^{n}}$, i.e.,
$x^{(n)}=x^{(-n)}$, or equivalently $x^{(2n)}=x$; an $\ell$-pregroup is _$n$
-periodic_ if all of its elements are, and it is called _periodic_ if it is
$n$-periodic for some $n$. In [7] it is shown that every periodic
$\ell$-pregroup is in fact distributive.

For every chain $\mathbf{\Omega}$, $F_{n}(\mathbf{\Omega})$ denotes the set of
all $n$-periodic elements of $\mathbf{F}(\mathbf{\Omega})$; the following
lemma shows that this set supports a subalgebra
$\mathbf{F}_{n}(\mathbf{\Omega})$ of $\mathbf{F}(\mathbf{\Omega})$.

######  Lemma 2.6.

Let $n$ be a positive integer.

  1. 1.

The $n$-periodic elements of any $\ell$-pregroup form a $n$-periodic
subalgebra.

  2. 2.

For every chain $\mathbf{\Omega}$, $\mathbf{F}_{n}(\mathbf{\Omega})$ is an
$n$-periodic subalgebra of $\mathbf{F}(\mathbf{\Omega})$.

###### Proof.

(1) As mentioned in the introduction, $\ell$-pregroups are involutive
residuated lattices, so they satisfy involutivity $x^{\ell r}=x=x^{r\ell}$,
the De Morgan laws

$(x\vee y)^{\ell}=x^{\ell}\wedge y^{\ell}$, $(x\wedge y)^{\ell}=x^{\ell}\vee
y^{\ell}$, $(x\vee y)^{r}=x^{r}\wedge y^{r}$, $(x\wedge y)^{r}=x^{r}\vee
y^{r}$,

and, since $x+y=xy$, the inverses are monoid antihomomorphisms

$(xy)^{\ell}=y^{\ell}x^{\ell}$, $(xy)^{r}=y^{r}x^{r}$, and $1^{\ell}=1^{r}=1$;

see [7]. Therefore, the map $x\mapsto x^{\ell\ell}$ is an endomorphism of the
$\ell$-pregroup $\mathbf{L}$ (actually an automorphism), hence so are all of
its (positive and negative) powers. In particular, $x\mapsto x^{(2n)}$ is an
endomorphism, hence the set of its fixed points is a subalgebra (for example,
if $x^{(2n)}=x$ and $y^{(2n)}=y$, then $(xy)^{(2n)}=x^{(2n)}y^{(2n)}=xy$).
Clearly, an element of $\mathbf{L}$ is $n$-periodic iff it is a fixed point of
$x\mapsto x^{(2n)}$. As a result, the set of all $n$-periodic elements of
$\mathbf{L}$ forms a subalgebra of $\mathbf{L}$ and all of its elements are
$n$-periodic. (2) follows by applying (1) to $\mathbf{F}(\mathbf{\Omega})$. ∎

We now establish our first representation theorem for $n$-periodic
$\ell$-pregroups, which will be useful in obtaining the generation and
decidability results for $n$-periodic $\ell$-pregroups; the second
representation theorem will be Theorem 2.16.

######  Theorem 2.7.

Given $n\in\mathbb{Z}^{+}$, every $n$-periodic $\ell$-pregroup can be embedded
in $\mathbf{F}_{n}(\mathbf{\Omega})$, for some integral chain
$\mathbf{\Omega}$, i.e., in
$\mathbf{F}_{n}(\mathbf{J}\overrightarrow{\times}\mathbb{Z})$, for some chain
$\mathbf{J}$.

###### Proof.

Let $\mathbf{L}$ be an $n$-periodic $\ell$-pregroup. By [7] $\mathbf{L}$ is a
distributive, so by [11] $\mathbf{L}$ embeds in $\mathbf{F}(\mathbf{\Omega})$,
for some integral chain $\mathbf{\Omega}$. Since $\mathbf{L}$ satisfies the
equation $x^{(2n)}=x$, the image of the embedding also satisfies the equation;
so the image is contained in $\mathbf{F}_{n}(\mathbf{\Omega})$. The last part
of the theorem follows from the fact that every integral chain is isomorphic
to $\mathbf{J}\overrightarrow{\times}\mathbb{Z}$ for some chain $\mathbf{J}$.
∎

We will dedicate the remainder of this subsection to characterizing the
functions in $\mathbf{F}_{n}(\mathbf{\Omega})$, where $\mathbf{\Omega}$ is an
integral chain.

######  Lemma 2.8.

If $\mathbf{\Omega}$ is an integral chain, $f\in F(\mathbf{\Omega})$ and
$n\in\mathbb{Z}^{+}$, each of the following are equivalent to $f\in
F_{n}(\mathbf{\Omega})$:

  1. 1.

For all $x\in\Omega$, $f(x)=f(x-n)+n$.

  2. 2.

For all $x\in\Omega$ and $k\in\mathbb{Z}$, $f(x)=f(x-kn)+kn$.

  3. 3.

For all $x,y\in\Omega$:

    1. (a)

$x\leq y+n\Rightarrow f(x)\leq f(y)+n$ and

    2. (b)

$x+n\leq y\Rightarrow f(x)+n\leq f(y)$.

  4. 4.

For all $x,y\in\Omega$ and $k\in\mathbb{Z}$: $x\leq y+kn\Rightarrow f(x)\leq
f(y)+kn$.

###### Proof.

The equivalence to (1) follows from $n$-periodicity and Lemma 2.3. Also,
$(1)\Rightarrow(2)$ follows by induction and the converse is obvious.
$(4)\Rightarrow(3)$ is obvious, as well.

For $(2)\Rightarrow(4)$, if $x,y\in\Omega$, $k\in\mathbb{Z}$ and $x\leq y+kn$,
then by order preservation and (2) we have $f(x)\leq f(y+kn)=f(y+kn-
kn)+kn=f(y)+kn$.

For $(3)\Rightarrow(1)$, if $x\in\Omega$, then $x\leq(x-n)+n$, so $f(x)\leq
f(x-n)+n$ by (3a). Since $x-n+n\leq x$, (3b) gives $f(x-n)+n\leq f(x)$; so
$f(x-n)+n=f(x)$. ∎

In particular, for $\mathbf{F}_{n}(\mathbb{Z})$ we make use of the
characterization for $\mathbf{F}(\mathbb{Z})$, as well.

######  Lemma 2.9.

For all $f:\mathbb{Z}\rightarrow\mathbb{Z}$, and $n\in\mathbb{Z}^{+}$, we have
$f\in F_{n}(\mathbb{Z})$ iff

  1. 1.

for all $a\in f[\mathbb{Z}]$, $f^{-1}[a]$ is finite (equivalently, a bounded
interval) and,

  2. 2.

for all $x,y,k\in\mathbb{Z}$: $x\leq y+kn\Rightarrow f(x)\leq f(y)+kn$.

###### Proof.

In the forward direction, observe that by Lemma 2.4, we know that for all
$a\in f[\mathbb{Z}]$, there exist $b,c\in\mathbb{Z}$ such that
$f^{-1}[a]=[b,c]$, so $f^{-1}[a]$ is bounded. Also, by Lemma 2.8, for all
$x,y,k\in\mathbb{Z}$, if $x\leq y+kn$, then $f(x)\leq f(y)+kn$.

For the converse direction, if $x,y\in\mathbb{Z}$ and $x\leq y$, by (2) we
have $f(x)\leq f(y)$, so $f$ is order preserving. Since (1) also holds, Lemma
2.5 implies $f\in F(\mathbb{Z})$; by (2) and Lemma 2.8, we get $f\in
F_{n}(\mathbb{Z})$ ∎

######  Lemma 2.10.

For every $n$, the $\ell$-pregroup $\mathbf{F}_{n}(\mathbb{Z})$ is simple.

###### Proof.

The invertible elements of $\mathbf{F}_{n}(\mathbb{Z})$ are the order-
preserving bijections on $\mathbb{Z}$, so they are precisely the translations
$t_{k}:x\mapsto x-k$, for $k\in\mathbb{Z}$. Using the results in [10] about
the correspondence between congruences and convex normal submonoids of the
negative cone, to prove that $\mathbf{F}_{n}(\mathbb{Z})$ is simple it
suffices to prove that: if $M$ is a non-trivial convex normal submonoid of the
negative cone of $\mathbf{F}_{n}(\mathbb{Z})$ then $M$ is the whole negative
cone.

Given a strictly negative $f\in M$, the element $g:=f\wedge
f^{\ell\ell}\wedge\cdots\wedge f^{\ell^{2n-2}}$ is invertible, since $(f\wedge
f^{\ell\ell}\wedge\cdots\wedge f^{\ell^{2n-4}}\wedge
f^{\ell^{2n-2}})^{\ell\ell}=f^{\ell\ell}\wedge f^{\ell^{4}}\wedge\cdots\wedge
f^{\ell^{2n-2}}\wedge f^{\ell^{2n}}=f^{\ell\ell}\wedge
f^{\ell^{4}}\wedge\cdots\wedge f^{\ell^{2n-2}}\wedge f$, and $g\leq f<1$ so
$g$ is a strictly decreasing translation and $M$ contains $g$ and all of its
powers; therefore $M$ contains translations $t_{k}$ for arbitrarily large $k$.
We now argue that every negative element $h$ of $F_{n}(\mathbb{Z})$ is above
some power of $g$ and thus belongs to $M$. Since $h$ is negative, for all
$m\in\mathbb{Z}$ there exists $k_{m}\geq 0$ such that $h(m)=m-k_{m}$. Since
$h$ is $n$-periodic, there are only $n$-many distinct such $k_{m}$’s; let
$k^{\prime}$ be the largest. We have $t_{k}\leq h$ for $k\geq k^{\prime}$, so
$h\in M$. ∎

The following two lemmas provide an even more transparent characterization of
the elements of $\mathbf{F}_{n}(\mathbf{J}\overrightarrow{\times}\mathbb{Z})$
where $\mathbf{J}$ is a chain. Note that if $f\in F_{n}(\mathbf{\Omega})$ then
not only $f^{(2n)}=f$, but moreover $f^{(2kn)}=f$ for all $k\in\mathbb{Z}$.
For $x,y\in J\times\mathbb{Z}$, we write $x\equiv y$ iff they have the same
first coordinate, i.e., if there exists $k\in\mathbb{Z}$ such that $x=y+k$
($x$ and $y$ belong to the same component of the lexicographic product). The
following lemma shows that maps in
$\mathbf{F}_{n}(\mathbf{J}\overrightarrow{\times}\mathbb{Z})$ preserve this
equivalence relation.

######  Lemma 2.11.

If $\mathbf{J}$ is a chain,
$\mathbf{\Omega}=\mathbf{J}\overrightarrow{\times}\mathbb{Z}$,
$n\in\mathbb{Z}$, $f\in F_{n}(\mathbf{\Omega})$, $j,i\in J$ and
$m\in\mathbb{Z}$, then the following hold.

  1. 1.

For all $x,y\in\Omega$, $x\equiv y\Rightarrow f(x)\equiv f(y)$.
In other words, if $f(j,0)=(i,m)$, then for all $r\in\mathbb{Z}$, there exists
$k\in\mathbb{Z}$, such that $f(j,r)=(i,k)$.

  2. 2.

If $x\notin f[\Omega]$, then there exists $b\in\Omega$ such that
$f(b)<x<f(b+1)$.
In other words, if $(i,m)\notin f[\Omega]$, then there exist $b\in\Omega$, and
$r,k\in\mathbb{Z}$ such that $f(b)=(i,r)$, $f(b+1)=(i,k)$ and $m\in(r,k)$.

###### Proof.

(1) Suppose $f(j,0)=(i,m)$ and let $r\leq 0$; the proof for $r>0$ is dual. We
have $f(j,r)=(i^{\prime},k)$, where $i^{\prime}\in J$ and $k\in\mathbb{Z}$; we
will show that $i^{\prime}=i$. Since $(j,r)\leq(j,0)$, we get
$(i^{\prime},k)=f(j,r)\leq f(j,0)=(i,m)$ by the order-preservation of $f$, so
$i^{\prime}\leq i$. Using the order-preservation of $f$, Lemma 2.3 and the
$n$-periodicity of $f$, we get $(i,m)=f(j,0)\leq
f(j,r-rn)=f^{(2rn)}((j,r-rn)+rn)-rn=f^{(2rn)}(j,r)-rn=f(j,r)-rn=(i^{\prime},k)-rn=(i^{\prime},k-rn)$,
which implies $i\leq i^{\prime}$; therefore $i=i^{\prime}$.

(2) If $(i,m)\notin f[\Omega]$ then, since $f\in F(\mathbf{\Omega})$, by Lemma
2.4 there exist $b,c\in\Omega$ with $b\prec c$ such that
$(i,m)\in(f(b),f(c))$. Then, by (1), there exist $j\in J$ and
$r,k\in\mathbb{Z}$ such that $f(b)=(j,r)$ and $f(c)=f(b+1)=(j,k)$; so
$(i,m)\in((j,r),(j,k))$. Therefore, $i=j$ and $m\in(r,k)$. ∎

The following theorem shows that maps in
$\mathbf{F}_{n}(\mathbf{J}\overrightarrow{\times}\mathbb{Z})$ consist of a
global component map on $\mathbf{J}$ and many local component maps, one for
each $j\in J$. The ability to work on the global level and on the local levels
separately will be crucial for the results in the next sections.

######  Theorem 2.12.

Given a chain $\mathbf{J}$, then $f\in
F_{n}(\mathbf{J}\overrightarrow{\times}\mathbb{Z})$ if and only if there
exists an order-preserving bijection $\widetilde{f}:J\rightarrow J$ and maps
$\overline{f}_{j}\in F_{n}(\mathbb{Z})$, for all $j\in J$, such that
$f(j,r)=(\widetilde{f}(j),\overline{f}_{j}(r))$ for all $(j,r)\in
J\times\mathbb{Z}$.

###### Proof.

We first show that if $\widetilde{f}:J\rightarrow J$ is an order-preserving
bijection and $\overline{f}_{j}\in F_{n}(\mathbb{Z})$, for all $j\in J$, then
$f\in F(\mathbf{J}\overrightarrow{\times}\mathbb{Z})$, where
$f(j,r)=(\widetilde{f}(j),\overline{f}_{j}(r))$ for all $(j,r)\in
J\times\mathbb{Z}$, by verifying the conditions of Lemma 2.4; we set
$\mathbf{\Omega}:=\mathbf{J}\overrightarrow{\times}\mathbb{Z}$ for brevity. If
$(j_{1},r_{1})\leq(j_{2},r_{2})$ in $\mathbf{\Omega}$, then $j_{1}<j_{2}$ or
($j_{1}=j_{2}$ and $r_{1}\leq r_{2}$). In the first case, since
$\widetilde{f}$ is an order preserving bijection, we have
$\widetilde{f}(j_{1})<\widetilde{f}(j_{2})$ and in the second case,
$\widetilde{f}(j_{1})=\widetilde{f}(j_{2})$ and
$\overline{f}_{j_{1}}(r_{1})\leq\overline{f}_{j_{1}}(r_{2})=\overline{f}_{j_{2}}(r_{2})$,
since $\overline{f}_{j_{1}}$ is order preserving. Hence, in both cases
$f(j_{1},r_{1})=(\widetilde{f}(j_{1}),\overline{f}_{j_{1}}(r_{1}))\leq(\widetilde{f}(j_{2}),\overline{f}_{j_{2}}(r_{2}))=f(j_{2},r_{2})$,
i.e., $f$ is order-preserving. If $(i,m)\in f[\Omega]$, then
$(i,m)=f(j,\ell)=(\widetilde{f}(j),\overline{f}_{j}(\ell))$, for some
$(j,\ell)\in J\times\mathbb{Z}$. Actually, since $\widetilde{f}$ is a
bijection, $j\in J$ is unique with the property $\widetilde{f}(j)=i$. Also,
since $m\in\overline{f}_{j}[\mathbb{Z}]$ and $\overline{f}_{j}\in
F(\mathbb{Z})$, by Lemma 2.4 there exist $r,k\in\mathbb{Z}$ such that
$(\overline{f}_{j})^{-1}[m]=[r,k]$. Therefore, $f^{-1}[(i,m)]=[(j,r),(j,k)]$.
If $(i,m)\not\in f[\Omega]$, since $\widetilde{f}$ is a bijection, there exist
$j\in J$ such that $\widetilde{f}(j)=i$, hence
$m\not\in(\overline{f}_{j})^{-1}[\mathbb{Z}]$. Since $\overline{f}_{j}\in
F(\mathbb{Z})$, by Lemma 2.4 there exist $r,k\in\mathbb{Z}$ such that $r\prec
k$ and $m\in(\overline{f}_{j}(r),\overline{f}_{j}(k))$. Hence,
$(j,r)\prec(j,k)$ and $(i,m)\in(f(j,r),f(j,k))$. Having shown that $f\in
F(\mathbf{\Omega})$, to prove $f\in F_{n}(\mathbf{\Omega})$ we verify that $f$
is $n$-periodic. For all $(j,r)\in\Omega$, by applying Lemma 2.3 to $f$ and to
$\overline{f}_{j}$ and using $\overline{f}_{j}\in F_{n}(\mathbb{Z})$, we get
$f^{(2n)}(j,r)=f((j,r)-n)+n=f(j,r-n)+n=(\widetilde{f}(j),\overline{f}_{j}(r-n))+n=(\widetilde{f}(j),\overline{f}_{j}(r-n)+n)=(\widetilde{f}(j),\overline{f}_{j}^{(2n)}(r))=(\widetilde{f}(j),\overline{f}_{j}(r))=f(j,r)$.

Conversely, if $f\in F_{n}(\mathbf{\Omega})$, we define the function
$\widetilde{f}:J\rightarrow J$ by $\widetilde{f}(j)=i$ iff $f(j,0)=(i,m)$ for
some $m\in\mathbb{Z}$; by Lemma 2.11(1) $\widetilde{f}$ is well defined. To
show that $\widetilde{f}$ is one-to-one, we assume that
$\widetilde{f}(j_{1})=\widetilde{f}(j_{2})$ for some $j_{1},j_{2}\in J$; since
$\mathbf{J}$ is a chain, we may further assume that $j_{1}\leq j_{2}$. Then,
there exist $r_{1},r_{2}\in\mathbb{Z}$ such that
$f(j_{1},0)=(\widetilde{f}(j_{1}),r_{1})$ and
$f(j_{2},0)=(\widetilde{f}(j_{1}),r_{2})$; since $j_{1}\leq j_{2}$, by the
order-preservation of $f$ we have $(\widetilde{f}(j_{1}),r_{1})=f(j_{1},0)\leq
f(j_{2},0)=(\widetilde{f}(j_{2}),r_{2})=(\widetilde{f}(j_{1}),r_{2})$, so
$r_{1}\leq r_{2}$. Let $k\in\mathbb{Z}$ be such that $r_{2}<r_{1}+kn$. Using
this fact, Lemma 2.3 and the periodicity of $f$, we have
$f(j_{2},0)=(\widetilde{f}(j_{1}),r_{2})<(\widetilde{f}(j_{1}),r_{1}+kn)=(\widetilde{f}(j_{1}),r_{1})+kn=f(j_{1},0)+kn=f(j_{1},kn-
kn)+kn=f((j_{1},kn)-kn)+kn=f^{(2kn)}(j_{1},kn)=f(j_{1},kn)$; hence
$f(j_{1},kn)\nleq f(j_{2},0)$. By order preservation we get
$(j_{1},kn)\not\leq(j_{2},0)$ and since $\Omega$ is a chain we obtain
$(j_{2},0)<(j_{1},kn)$; thus $j_{2}\leq j_{1}$. In conclusion $j_{1}=j_{2}$.

To show that $\widetilde{f}$ is onto, let $i\in J$ and consider
$(i,0)\in\Omega$. If $(i,0)\in f[\Omega]$, there exists $(j,r)\in\Omega$ such
that $f(j,r)=(i,0)$; by Lemma 2.11(1) we have $f(j,0)=(i,k)$ for some
$k\in\mathbb{Z}$, so $i\in\widetilde{f}[J]$. If $(i,0)\notin f[\Omega]$, by
Lemma 2.11(2) there exist $j\in J$ and $r,m_{1},m_{2}\in\mathbb{Z}$, such that
$f(j,r)=(i,m_{1})$, $f(j,r+1)=(i,m_{2})$, and $0\in(m_{1},m_{2}$); then, by
Lemma 2.11(1), $f(j,0)=(i,m_{3})$ for some $m_{3}\in\mathbb{Z}$, so
$\widetilde{f}(j)=i$, i.e., $i\in\widetilde{f}[J]$.

Now, for $j\in J$, we define
$\overline{f}_{j}:\mathbb{Z}\rightarrow\mathbb{Z}$ where
$\overline{f}_{j}(r)=m$ iff $f(j,r)=(\widetilde{f}(j),m)$ for some
$m\in\mathbb{Z}$; by Lemma 2.11(1) $\overline{f}_{i}$ is well-defined. We will
show that $\overline{f}_{j}\in F(\mathbb{Z})$ by verifying the condition in
Lemma 2.5. If $m\in\overline{f}_{j}[\mathbb{Z}]$, then there exist
$r\in\mathbb{Z}$ such that $\overline{f}_{j}(r)=m$, hence, by the definition
of $\overline{f}_{j}$, there exist $i\in J$ such that $f(j,r)=(i,m)$. Since
$f\in F(\mathbf{\Omega})$, by Lemma 2.4(1) there exist
$(j_{1},r_{1}),(j_{2},r_{2})\in\Omega$ such that
$f^{-1}[(i,m)]=[(j_{1},r_{1}),(j_{2},r_{2})]$. So, by Lemma 2.11(1)
$\widetilde{f}(j_{1})=i=\widetilde{f}(j_{2})$ and since $\widetilde{f}$ is a
bijection, $j_{1}=j_{2}:=j$. Then $f^{-1}[(i,m)]=[(j,r_{1}),(j,r_{2})]$; thus
$\overline{f}_{j}^{-1}[m]=[r_{1},r_{2}]$. Finally, we prove that
$\overline{f}_{j}\in F_{n}(\mathbb{Z})$, by showing that $\overline{f}_{j}$ is
$n$-periodic. For all $j\in J$ and $m\in\mathbb{Z}$, by the $n$-periodicity of
$f$ and Lemma 2.3, we have
$(\widetilde{f}(j),\overline{f}_{j}(m))=f(j,m)=f^{(2n)}(j,m)=f((j,m)-n)+n=f(j,m-n)+n=(\widetilde{f}(j),\overline{f}_{j}(m-n))+n=(\widetilde{f}(j),\overline{f}_{j}(m-n)+n)$;
hence
$\overline{f}_{j}(m)=\overline{f}_{j}(m-n)+n=(\overline{f}_{j})^{(2n)}(m)$, by
Lemma 2.3, we have that $\overline{f}_{j}$ is $n$-periodic. ∎

######  Example 2.13.

In Figure 1 we can see a function $f$ of
$\mathbf{F}_{2}(\mathbb{Q}\overrightarrow{\times}\mathbb{Z})$ and its $0$-th
component $\overline{f}_{0}$ which is an element of
$\mathbf{F}_{2}(\mathbb{Z})$.

$3$$3$$2$$2$$1$$1$$0$$0$$7$$7$$6$$6$$5$$5$$4$$4$$3$$3$$2$$2$$1$$1$$0$$0$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$f$

$7$$7$$6$$6$$5$$5$$4$$4$$3$$3$$2$$2$$1$$1$$0$$0$$\vdots$$\vdots$$\vdots$$\vdots$$\overline{f}_{0}$

Figure 1: An element of
$\mathbf{F}_{n}(\mathbb{Q}\overrightarrow{\times}\mathbb{Z})$ and one of its
components in $\mathbf{F}_{n}(\mathbb{Z})$

###  2.4 Wreath products

In this section we show that
$\mathbf{F}_{n}(\mathbf{J}\overrightarrow{\times}\mathbb{Z})$ is actually a
wreath product and that every $n$-periodic $\ell$-pregroup can be embedded in
the wreath product of an $\ell$-group and an $n$-periodic simple
$\ell$-pregroup (our second representation theorem for $n$-periodic
$\ell$-pregroups).

First recall that if $\mathbf{H}=(H,\overline{\circ},1_{H})$ and
$\mathbf{N}=(N,\odot,1_{N})$ are monoids and $\mathbf{H}$ acts on the monoid
$\mathbf{N}$ on the right via $\otimes:\mathbf{H}\curvearrowright\mathbf{N}$,
(i.e., $n\otimes 1_{H}=n$ $(n\otimes h_{1})\otimes
h_{2}=n\otimes(h_{1}\overline{\circ}h_{2})$, $(n_{1}\odot n_{2})\otimes
h=(n_{1}\otimes h)\odot(n_{2}\otimes h)$ and $1_{N}\otimes h=1_{N}$), then the
_semidirect product_ $\mathbf{H}\ltimes_{\otimes}\mathbf{N}$ is defined by

$(h_{1},n_{1})(h_{2},n_{2})=(h_{1}\overline{\circ}h_{2},(n_{1}\otimes
h_{2})\odot n_{2})$

and it forms a monoid with unit $(1_{H},1_{N})$.

If we take $\mathbf{N}=\mathbf{F}^{J}$, where $J$ is a set and
$\mathbf{F}=(F,\ocirc,1_{F})$ is a monoid, i.e., the operation of $\mathbf{N}$
is $(n_{1}\odot n_{2})(j):=n_{1}(j)\ocirc n_{2}(j)$, and if $\mathbf{H}$ acts
on the set $J$ on the left by $*:\mathbf{H}\curvearrowright J$, then
$\mathbf{H}$ acts on $\mathbf{F}^{J}$ on the right via
$\otimes:\mathbf{H}\curvearrowright\mathbf{F}^{J}$, where

$n\otimes h:=n\circ\lambda_{h}$ and $\lambda_{h}(j):=h*j$,

hence $(n\otimes h)(j)=(n\circ\lambda_{h})(j)=n(\lambda_{h}(j))=n(h*j)$.
Indeed, $\otimes$ is a right action because $((n_{1}\odot n_{2})\otimes
h)(j)=((n_{1}\odot n_{2})\circ\lambda_{h})(j)=(n_{1}\odot
n_{2})(\lambda_{h}(j))=n_{1}(\lambda_{h}(j))\ocirc
n_{2}(\lambda_{h}(j))=n_{1}\circ\lambda_{h}(j)\ocirc
n_{2}\circ\lambda_{h}(j)=(n_{1}\otimes h)(j)\ocirc(n_{2}\otimes
h)(j)=((n_{1}\otimes h)\odot(n_{1}\otimes h))(j)$ and $(1_{N}\otimes
h)(j)=(1_{N}\circ\lambda_{h})(j)=1_{N}(\lambda_{h}(j))=1_{F}=1_{N}(j)$. Also,
for every $h_{1},h_{2}\in H$ and $j\in J$, we have
$(\lambda_{h_{1}}\circ\lambda_{h_{2}})(j)=h_{1}*(h_{2}*j)=(h_{1}\overline{\circ}h_{2})*j=\lambda_{h_{1}\overline{\circ}h_{2}}(j)$,
so $(n\otimes h_{1})\otimes
h_{2}=(n\circ\lambda_{h_{1}}\circ\lambda_{h_{2}})=n\circ\lambda_{h_{1}\overline{\circ}h_{2}}=n\otimes(h_{1}\overline{\circ}h_{2})$.
The semidirect product $\mathbf{H}\ltimes_{\otimes}\mathbf{F}^{J}$ is known as
the _wreath product_ $\mathbf{H}\wr_{J,*}\mathbf{F}$, or simply
$\mathbf{H}\wr\mathbf{F}$ when $\mathbf{H}$ is a submonoid of
$\mathbf{End}(J)$ and $h*j:=h(j)$. One such case is when we take
$\mathbf{H}:=\mathbf{Aut}(\mathbf{J})$ to be the order-preserving
automorphisms of a chain $\mathbf{J}$, resulting in the wreath product
$\mathbf{Aut}(\mathbf{J})\wr\mathbf{F}=\mathbf{Aut}(\mathbf{J})\ltimes\mathbf{F}^{J}$.

Now, we expand the monoid structure of the wreath product
$\mathbf{H}\wr_{J,*}\mathbf{F}$ relative to $J$ and $*$, when $\mathbf{H}$ is
an $\ell$-group, $\mathbf{J}$ is a chain, $\mathbf{F}$ is an $\ell$-pregroup,
and $*:\mathbf{H}\curvearrowright\mathbf{J}$ is a left action of $\mathbf{H}$
on the chain $\mathbf{J}$, by defining an order and inversion operations. We
say that a monoid $\mathbf{H}$ acts on a chain $\mathbf{J}$ via
$*:\mathbf{H}\curvearrowright\mathbf{J}$, if $\mathbf{H}$ acts on the set $J$
and $*$ is monotone on both coordinates.

We define

$(h_{1},n_{1})\leq(h_{2},n_{2})$ by: $h_{1}\leq h_{2}$ and
$h_{1}*j=h_{2}*j\Rightarrow n_{1}(j)\leq n_{2}(j)$, for all $j$.

Also, $(h_{1},n_{1})\vee(h_{2},n_{2})=(h_{1}\vee h_{2},n_{\vee})$ and
$(h_{1},n_{1})\wedge(h_{2},n_{2})=(h_{1}\wedge h_{2},n_{\wedge})$, where for
every $j$,

$n_{\vee}(j)=\begin{cases}n_{2}(j)\\\ n_{1}(j)\\\ n_{1}(j)\vee
n_{2}(j)\end{cases}n_{\wedge}(j)=\begin{cases}n_{1}(j)&\text{ if
}h_{1}*j<h_{2}*j\\\ n_{2}(j)&\text{ if }h_{2}*j<h_{1}*j\\\ n_{1}(j)\wedge
n_{2}(j)&\text{ if }h_{1}*j=h_{2}*j\end{cases}$

Also, we define:

$(h,n)^{\ell}:=(h^{-1},n^{\ell}\otimes h^{-1})$ and
$(h,n)^{r}:=(h^{-1},n^{r}\otimes h^{-1})$ ,

where $n\mapsto n^{\ell}$ and $n\mapsto n^{r}$ are the operations of the
direct product $\mathbf{F}^{J}$. We denote by
$\mathbf{H}\wr_{\mathbf{J},*}\mathbf{F}$ the resulting structure, which we
call the _( $\ell$-pregroup) wreath product_, and we prove that it is an
$\ell$-pregroup.

######  Theorem 2.14.

If $*:\mathbf{H}\curvearrowright\mathbf{J}$ is a left action of the
$\ell$-group $\mathbf{H}$ on the chain $\mathbf{J}$ and $\mathbf{F}$ is an
$\ell$-pregroup, then $\mathbf{H}\wr_{\mathbf{J},*}\mathbf{F}$ is an
$\ell$-pregroup. Furthermore,

  1. 1.

for every $k$, $\mathbf{H}\wr_{\mathbf{J},*}\mathbf{F}$ is $k$-periodic iff
$\mathbf{F}$ is $k$-periodic.

  2. 2.

$\mathbf{H}\wr_{\mathbf{J},*}\mathbf{F}$ is distributive iff $\mathbf{F}$ is
distributive.

###### Proof.

From the above calculations we know that $\mathbf{H}\wr_{J,*}\mathbf{F}$
supports a monoid structure.

We show that $\leq$ is a partial order; it is clearly reflexive. For
transitivity, we assume $(h_{1},n_{1})\leq(h_{2},n_{2})\leq(h_{3},n_{3})$, so
$h_{1}\leq h_{2}\leq h_{3}$; in particular $h_{1}*j\leq h_{2}*j\leq h_{3}*j$
for all $j$, by the monotonicity of $*$ on its left coordinate. So, if
$h_{1}*j=h_{3}*j$, then $h_{1}*j=h_{2}*j=h_{3}*j$, so $n_{1}(j)\leq
n_{2}(j)\leq n_{3}(j)$. For antisymmetry, we assume
$(h_{1},n_{1})\leq(h_{2},n_{2})\leq(h_{1},n_{1})$, so $h_{1}\leq h_{2}\leq
h_{1}$; in particular $h_{1}*j=h_{2}*j$, for all $j$. Therefore, by assumption
we get $n_{1}(j)\leq n_{2}(j)\leq n_{1}(j)$, for all $j$.

We will use the fact that $*$ distributes over joins on its left coordinate,
which we establish now. First note that the map $j\mapsto h*j$ is an order-
preserving bijection: $h*i=h*j\Rightarrow h^{-1}*(h*i)=h^{-1}*(h*j)\Rightarrow
i=j$ and the action is order-preserving on the right coordinate; so, $j\mapsto
h*j$ distributes over joins and meets. Now, to prove $(h_{1}\vee
h_{2})*j=h_{1}*j\vee h_{2}*j$, by order-preservation we only need to check
$(h_{1}\vee h_{2})*j\leq h_{1}*j\vee h_{2}*j$, which is equivalent to
$j\leq(h_{1}\vee h_{2})^{-1}*(h_{1}*j\vee h_{2}*j)$, i.e., to $j\leq(h_{1}\vee
h_{2})^{-1}*(h_{1}*j)\vee(h_{1}\vee h_{2})^{-1}*(h_{2}*j)$, which is
equivalent to $j\leq(1\wedge h_{2}^{-1}\overline{\circ}h_{1})*j\vee(1\wedge
h_{1}^{-1}\overline{\circ}h_{2})*j$, which in turn holds by order preservation
on the left coordinate.

We show that $\leq$ is a lattice-order and that join and meet are given by the
formulas. First note that $(h_{1},n_{1})\leq(h_{1}\vee h_{2},n_{\vee})$,
because $h_{1}\leq h_{1}\vee h_{2}$ and, if $h_{1}*j=(h_{1}\vee h_{2})*j$,
then $h_{2}*j\leq(h_{1}\vee h_{2})*j=h_{1}*j$; by definition, we get that then
$n_{\vee}(j)\in\\{n_{1}(j),n_{1}(j)\vee n_{2}(j)\\}$, thus $n_{1}(j)\leq
n_{\vee}(j)$. Also, if $(h_{1},n_{1})\leq(h,n)$ and $(h_{2},n_{2})\leq(h,n)$,
then $h_{1},h_{2}\leq h$, so $h_{1}\vee h_{2}\leq h$. If $(h_{1}\vee
h_{2})*j=h*j$, for some $j$, then $(h_{1}*j)\vee(h_{2}*j)=h*j$, so because
$\mathbf{J}$ is a chain we get $h*j=h_{1}*j$ or $h*j=h_{2}*j$. In either case,
by the definition of $n_{\vee}$, we get $n_{\vee}(j)=n_{1}(j)\vee n_{2}(j)$.
Therefore, $(h_{1}\vee h_{2},n_{\vee})\leq(h,n)$. Likewise, we show that the
meet is given by the formula.

We will show that multiplication is order-preservating on the right. We assume
that $(h_{1},n_{1})\leq(h_{2},n_{2})$, i.e., $h_{1}\leq h_{2}$ and
$h_{1}*j=h_{2}*j\Rightarrow n_{1}(j)\leq n_{2}(j)$, for all $j$. We will show
that $(h_{1},n_{1})(h,n)\leq(h_{2},n_{2})(h,n)$, i.e., that
$(h_{1}\overline{\circ}h,(n_{1}\otimes h)\odot
n)\leq(h_{2}\overline{\circ}h,(n_{2}\otimes h)\odot n)$. Since $h_{1}\leq
h_{2}$, by monotonicity of $\overline{\circ}$, we get
$h_{1}\overline{\circ}h\leq h_{2}\overline{\circ}h$. For each $j$, if
$(h_{1}\overline{\circ}h)*j=(h_{2}\overline{\circ}h)*j$, then
$h_{1}*(h*j)=h_{2}*(h*j)$, so $n_{1}(h*j)\leq n_{2}(h*j)$, by hypothesis. By
the order-preservation of $\ocirc$ in $\mathbf{F}$, we get $n_{1}(h*j)\ocirc
n(j)\leq n_{2}(h*j)\ocirc n(j)$. Since
$n_{i}(h*j)=(n_{i}\circ\lambda_{h})(j)=(n_{i}\otimes h)(j)$, we get
$(n_{1}\otimes h)(j)\ocirc n(j)\leq(n_{2}\otimes h)(j)\ocirc n(j)$, i.e.,
$((n_{1}\otimes h)\odot n)(j)\leq((n_{2}\otimes h)\odot n)(j)$.

For the left side, we will show that
$(h,n)(h_{1},n_{1})\leq(h,n)(h_{2},n_{2})$, i.e., that
$(h\overline{\circ}h_{1},(n\otimes h_{1})\odot
n_{1})\leq(h\overline{\circ}h_{2},(n\otimes h_{2})\odot n_{2})$. We get
$h\overline{\circ}h_{1}\leq h\overline{\circ}h_{2}$, by the monotonicity of
$\overline{\circ}$. For each $j$, if
$(h\overline{\circ}h_{1})*j=(h\overline{\circ}h_{2})*j$, then
$h*(h_{1}*j)=h*(h_{2}*j)$, so $h^{-1}*(h*(h_{1}*j))=h^{-1}*(h*(h_{2}*j))$.
Since $\mathbf{H}$ is a group we get
$h^{-1}*(h*(i))=(h^{-1}\overline{\circ}h)*i=1_{H}*i=i$, therefore
$h_{1}*j=h_{2}*j$, hence $n_{1}(j)\leq n_{2}(j)$, by hypothesis; also
$n(h_{1}*j)=n(h_{2}*j)$. By the monotonicity of $\ocirc$, we get
$n(h_{2}*j)\ocirc n_{1}(j)\leq n(h_{2}*j)\ocirc n_{2}(j)$. Since
$n(h_{i}*j)=(n\circ\lambda_{h_{i}})(j)=(n\otimes h_{i})(j)$, we get $(n\otimes
h_{1})(j)\ocirc n_{1}(j)\leq(n\otimes h_{2})(j)\ocirc n_{2}(j)$, hence
$((n\otimes h_{1})\odot n_{1})(j)\leq((n\otimes h_{2})\odot n_{2})(j)$.

Now, show that for all $x\in H\times F^{J}$, we have $x^{\ell}x\leq 1$ and
$1\leq x^{r}x$. Using the fact that $f^{\ell}f\leq 1_{F}$ holds for all $f\in
F$, and thus also $n^{\ell}\odot n\leq 1_{N}$ for $n\in F^{J}$, we get
$(h^{-1},n^{\ell}\otimes
h^{-1})(h,n)=(h^{-1}\overline{\circ}h,((n^{\ell}\otimes h^{-1})\otimes h)\odot
n)=(1_{H},(n^{\ell}\otimes(h^{-1}\overline{\circ}h))\odot
n)=(1_{H},(n^{\ell}\otimes 1_{H})\odot n)=(1_{H},n^{\ell}\odot
n)\leq(1_{H},1_{N})$. Also, $(h^{-1},n^{r}\otimes
h^{-1})(h,n)=(h^{-1}\overline{\circ}h,((n^{r}\otimes h^{-1})\otimes h)\odot
n)=(1_{H},(n^{r}\otimes(h^{-1}\overline{\circ}h))\odot n)=(1_{H},(n^{r}\otimes
1_{H})\odot n)=(1_{H},n^{r}\odot n)\geq(1_{H},1_{N})$. Note that we used the
fact that $\mathbf{H}$ acts via $\otimes$ on the set $F^{J}$.

For showing $xx^{r}\leq 1\leq xx^{\ell}$ we will use that $\mathbf{H}$ acts
also on the monoid $\mathbf{F}^{J}$ and the order-preservation of $\otimes$ on
the first coordinate, which we establish first. If $n_{1}\leq n_{2}$, i.e.,
$n_{1}(j)\leq n_{2}(j)$ for all $j$, then for all $h$ we get $n_{1}\otimes
h\leq n_{2}\otimes h$. Indeed, for all $j$, we have $n_{1}(h*j)\leq
n_{1}(h*j)$, so $(n_{1}\otimes h)(j)\leq(n_{2}\otimes h)(j)$. Thus,
$\otimes:\mathbf{H}\curvearrowright\mathbf{F}^{J}$ is order-preserving in the
left coordinate. Now, for $xx^{r}\leq 1\leq xx^{\ell}$, we have
$(h,n)(h^{-1},n^{r}\otimes h^{-1})=(h\overline{\circ}h^{-1},(n\otimes
h^{-1})\odot(n^{r}\otimes h^{-1}))=(1_{H},(n\odot n^{r})\otimes
h^{-1})\leq(1_{H},1_{N}\otimes h^{-1})=(1_{H},1_{N})$ and
$(h,n)(h^{-1},n^{\ell}\otimes h^{-1})=(h\overline{\circ}h^{-1},(n\otimes
h^{-1})\odot(n^{\ell}\otimes h^{-1}))=(1_{H},(n\odot n^{\ell})\otimes
h^{-1})\geq(1_{H},1_{N}\otimes h^{-1})=(1_{H},1_{N})$

(1) We now prove that $(n\otimes h)^{\ell}=n^{\ell}\otimes h$, i.e.,
$(n\otimes h)^{\ell}(j)=(n^{\ell}\otimes h)(j)$, for all $j$. By the
coordinate-wise definition of ℓ on elements of $F^{J}$, this is equivalent to
$((n\otimes h)(j))^{\ell}=(n^{\ell}\otimes h)(j)$, to
$(n(h*j))^{\ell}=n^{\ell}(h*j)$ and to $(n(h*j))^{\ell}=(n(h*j))^{\ell}$,
which holds. Likewise, we have $(n\otimes h)^{r}=n^{r}\otimes h$. We use these
properties to establish the characterization of the periodic case.

Note that $(h,n)^{\ell\ell}=(h^{-1},n^{\ell}\otimes
h^{-1})^{\ell}=((h^{-1})^{-1},(n^{\ell}\otimes
h^{-1})^{\ell}\otimes(h^{-1})^{-1}))=(h,(n^{\ell\ell}\otimes h^{-1})\otimes
h)=(h,n^{\ell\ell}\otimes(h^{-1}\overline{\circ}h))=(h,n^{\ell\ell}\otimes
1_{H})=(h,n^{\ell\ell})$. More generally, we get $(h,n)^{(2k)}=(h,n^{(2k)})$,
for every $k$. Therefore, for each positive integer $k$, we have that
$(h,n)^{(2k)}=(h,n)$ for all $(h,n)\in\mathbf{H}\wr_{\mathbf{J},*}\mathbf{F}$,
iff $(h,n^{(2k)})=(h,n)$ for all
$(h,n)\in\mathbf{H}\wr_{\mathbf{J},*}\mathbf{F}$, iff $n^{(2k)}=n$ for all
$n\in F^{J}$.

(2) We first show that if $\mathbf{F}$ is distributive, then
$\mathbf{H}\wr_{\mathbf{J},*}\mathbf{F}$ is distributive, as well. We will
show that for all
$(h_{1},n_{1}),(h_{2},n_{2}),(h_{3},n_{3})\in\mathbf{H}\wr_{\mathbf{J},*}\mathbf{F}$
we have:

$(h_{1},n_{1})\wedge((h_{2},n_{2})\vee(h_{3},n_{3}))=((h_{1},n_{1})\wedge(h_{2},n_{2}))\vee((h_{1},n_{1})\wedge(h_{3},n_{3}))$

For simplicity, we define $n_{i\wedge j}$ by
$(h_{i},n_{i})\wedge(h_{l},n_{l})=(h_{i}\wedge h_{l},n_{i\wedge j})$, instead
of the generic term $n_{\wedge}$, and similarly for the join. By the
distributivity of $\mathbf{J}$ we get $h_{1}*j\wedge(h_{2}*j\vee
h_{3}*j)=(h_{1}*j\wedge h_{2}*j)\vee(h_{1}*j\wedge h_{3}*j)$ and in
particular, there exists $i\in\\{1,2,3\\}$ such that
$h_{1}*j\wedge(h_{2}*j\vee h_{3}*j)=h_{i}*j$, since $\mathbf{J}$ is a chain.
If $h_{1}*j,h_{2}*j,h_{3}*j$ are all distinct, then $n_{1\wedge(2\vee
3)}(j)=n_{i}(j)=n_{(1\wedge 2)\vee(1\wedge 3)}(j)$

On the other hand, if $h_{1}*j,h_{2}*j,h_{3}*j$ are not all distinct, for
$\\{i,k\\}=\\{2,3\\}$, we have

$\displaystyle n_{1\wedge(2\vee 3)}(j)$
$\displaystyle=\begin{cases}n_{1}(j)\wedge n_{k}(j)&\text{ if
}h_{i}*j<h_{k}*j=h_{1}*j\\\ n_{1}(j)&\text{ if }h_{1}*j=h_{k}*j<h_{i}*j\\\
n_{1}(j)&\text{ if }h_{1}*j<h_{k}*j=h_{i}*j\\\ n_{2}(j)\vee n_{3}(j)&\text{ if
}h_{k}*j=h_{i}*j<h_{1}*j\\\ n_{1}(j)\wedge(n_{2}(j)\vee n_{3}(j))&\text{ if
}h_{1}*j=h_{k}*j=h_{i}*j\end{cases}$

Also, if $h_{1}*j,h_{2}*j,h_{3}*j$ are not all distinct, $n_{(1\wedge
2)\vee(1\wedge 3)}(j)=$

$\displaystyle\begin{cases}n_{1}(j)\wedge n_{k}(j)&\text{ if
}h_{i}*j<h_{k}*j=h_{1}*j\\\ n_{1}(j)&\text{ if }h_{1}*j=h_{k}*j<h_{i}*j\\\
n_{1}(j)&\text{ if }h_{1}*j<h_{k}*j=h_{i}*j\\\ n_{2}(j)\vee n_{3}(j)&\text{ if
}h_{k}*j=h_{i}*j<h_{1}*j\\\ (n_{1}(j)\vee n_{2}(j))\wedge(n_{1}(j)\vee
n_{3}(j))&\text{ if }h_{1}*j=h_{k}*j=h_{i}*j\end{cases}$

By the distributivity of $\mathbf{F}$, we get $n_{1\wedge(2\vee
3)}(j)=n_{(1\wedge 2)\vee(1\wedge 3)}(j)$ for all $j\in J$, and by the
distributivity of $\mathbf{H}$, we have
$(h_{1},n_{1})\wedge((h_{2},n_{2})\vee(h_{3},n_{3}))=((h_{1},n_{1})\wedge(h_{2},n_{2}))\vee((h_{1},n_{1})\wedge(h_{3},n_{3}))$.

On the other hand, if $\mathbf{H}\wr_{\mathbf{J},*}\mathbf{F}$ is
distributive, for all $n_{1},n_{2},n_{3}\in F$ and $h\in H$,
$(h,n_{1})\wedge((h,n_{2})\vee(h,n_{3}))=((h,n_{1})\wedge(h,n_{2}))\vee((h,n_{1})\wedge(h,n_{3}))$,
hence $(h,n_{1}\vee(n_{2}\wedge n_{3}))=(h,(n_{1}\vee n_{2})\wedge(n_{1}\vee
n_{3}))$, so $n_{1}\vee(n_{2}\wedge n_{3})=(n_{1}\vee n_{2})\wedge(n_{1}\vee
n_{3})$. Thus, $\mathbf{F}$ is distributive. ∎

We want to stress that the wreath product construction applies to arbitrary
$\ell$-pregroups, not only to distributive ones.

######  Remark 2.15.

We note that the more general definition where $\mathbf{H}$ is allowed to be
an $\ell$-pregroup, $(h,n)^{\ell}:=(h^{\ell},n^{\ell}\otimes h^{\ell})$ and
$(h,n)^{r}:=(h^{r},n^{\ell}\otimes h^{r})$ fails: $(h,n)^{\ell
r}=(h^{\ell},n^{\ell}\otimes h^{\ell})^{r}=(h^{\ell r},(n^{\ell}\otimes
h^{\ell})^{r}\otimes h^{\ell r})=(h,(n^{\ell r}\otimes h^{\ell})\otimes
h)=(h,n\otimes(h^{\ell}\overline{\circ}h))\leq(h,n\otimes 1_{H})=(h,n)$, but
unless $h\overline{\circ}h^{r}=1_{H}$ (i.e., $h$ is invertible, for arbitrary
$h$), we do not get equality.

It is well known that if the monoid $\mathbf{F}$ acts on the left on a set
$\Omega$, then the monoid wreath product $\mathbf{H}\wr_{J,*}\mathbf{F}$ acts
on $J\times\Omega$. It is not hard to show that if an $\ell$-pregroup
$\mathbf{F}$ acts on a chain $\mathbf{\Omega}$ then the $\ell$-group wreath
product $\mathbf{H}\wr_{J,*}\mathbf{F}$ acts on the lexicographic product
$\mathbf{J}\overrightarrow{\times}\mathbf{\Omega}$, by
$(h,g)(j,a):=(h(j),g(a))$, for $(h,g)\in\mathbf{H}\wr_{J,*}\mathbf{F}$ and
$(j,a)\in{J}\overrightarrow{\times}\Omega$.

As promised we now show that
$\mathbf{F}_{n}(\mathbf{J}\overrightarrow{\times}\mathbb{Z})$ is indeed an
$\ell$-pregroup wreath product and use this fact to get a second
representation theorem for $n$-periodic $\ell$-pregroups.

######  Theorem 2.16.

For every chain $\mathbf{J}$ and $n\in\mathbb{Z}^{+}$,
$\mathbf{F}_{n}(\mathbf{J}\overrightarrow{\times}\mathbb{Z})\cong\mathbf{Aut}(\mathbf{J})\wr\mathbf{F}_{n}(\mathbb{Z})$.
Therefore, every $n$-periodic $\ell$-pregroup can be embedded in the wreath
product of an $\ell$-group and the simple $n$-periodic $\ell$-pregroup
$\mathbf{F}_{n}(\mathbb{Z})$.

###### Proof.

By Theorem 2.12, every $f$ in
$\mathbf{F}_{n}(\mathbf{J}\overrightarrow{\times}\mathbb{Z})$ can be
identified with the pair $(\widetilde{f},\overline{f})$ in
$\mathbf{Aut}(\mathbf{J})\times(\mathbf{F}_{n}(\mathbb{Z}))^{J}$, where
$\overline{f}(j)=\overline{f}_{j}$, i.e.,
$\overline{f}=(\overline{f}_{j})_{j\in J}$. We will verify that composition of
$f$’s corresponds to multiplication of pairs $(\widetilde{f},\overline{f})$ in
the wreath product
$\mathbf{Aut}(\mathbf{J})\wr\mathbf{F}_{n}(\mathbb{Z})=\mathbf{Aut}(\mathbf{J})\ltimes(\mathbf{F}_{n}(\mathbb{Z}))^{J}$
under the identification $f\equiv(\widetilde{f},\overline{f})$. Indeed, for
every $(j,m)\in J\times\mathbb{Z}$ and $f,g$ in
$\mathbf{F}_{n}(\mathbf{J}\overrightarrow{\times}\mathbb{Z})$, we have

$\begin{array}[]{rl}(f\circ
g)(j,m)&=f(g(j,m))=f(\widetilde{g}(j),\overline{g}_{j}(m))=(\widetilde{f}(\widetilde{g}(j)),\overline{f}_{\widetilde{g}(j)}(\overline{g}_{j}(m)))\\\
&=((\widetilde{f}\circ\widetilde{g})(j),(\overline{f}_{\widetilde{g}(j)}\circ\overline{g}_{j})(m))=((\widetilde{f}\circ\widetilde{g})(j),(\overline{f}\otimes\widetilde{g})\odot\overline{g})_{j}(m))\\\
&=(\widetilde{f}\circ\widetilde{g},(\overline{f}\otimes\widetilde{g})\odot\overline{g})(j,m)=((\widetilde{f},\overline{f})(\widetilde{g},\overline{g}))(j,m)\end{array}$

where we used that
$\overline{f}_{\widetilde{g}(j)}\circ\overline{g}_{j}=\overline{f}(\widetilde{g}(j))\circ\overline{g}(j)=(\overline{f}\otimes{\widetilde{g})(j)}\circ\overline{g}(j)=(\overline{f}\otimes\widetilde{g})\odot\overline{g})(j)=(\overline{f}\otimes\widetilde{g})\odot\overline{g})_{j}$
which is, in turn, based on
$\overline{f}(\widetilde{g}(j))=(\overline{f}\otimes{\widetilde{g})(j)}$, a
general fact we already established above as $n(h(j))=(n\otimes h)(j)$.

For the order, note that $f\leq g$ iff
$(\widetilde{f}(j),(\overline{f}_{j}(m))_{j\in
J})\leq(\widetilde{g}(j),(\overline{g}_{j}(m))_{j\in J})$, for all $(j,m)$,
iff $\widetilde{f}\leq\widetilde{g}$ and
$\widetilde{f}(j)=\widetilde{g}(j)\Rightarrow\overline{f}_{j}(m)\leq\overline{g}_{j}(m)$
for all $(j,m)$, iff $\widetilde{f}\leq\widetilde{g}$ and
$\widetilde{f}(j)=\widetilde{g}(j)\Rightarrow\overline{f}_{j}\leq\overline{g}_{j}$.
for all $j$.

Also, we have that if $f$ corresponds to $(\widetilde{f},\overline{f})$, then
$f^{\ell}\equiv(\widetilde{f}^{-1},\overline{f}^{\ell}\otimes\widetilde{f}^{-1})$,
where $\overline{f}^{\ell}(j):=\overline{f}(j)^{\ell}$ is given by the
definition of ℓ to the direct product $\mathbf{F}_{n}(\mathbb{Z})^{J}$.

By Lemma 2.4 for all $(j,n)\in{J}\overrightarrow{\times}\mathbb{Z}$ there
exist $(i,m)\in{J}\overrightarrow{\times}\mathbb{Z}$ such that
$f(i,m-1)<(j,n)\leq f(i,m)$ and $f^{\ell}(j,n)=(i,m)$, so
$(\tilde{f}(i),\overline{f}_{i}(m-1))<(j,n)\leq(\tilde{f}(i),\overline{f}_{i}(m))$.
Then $j=\tilde{f}(i)$ and $\overline{f}_{i}(m-1)<n\leq\overline{f}_{i}(m)$,
therefore $\overline{f}_{i}^{\ell}(n)=m$. So
$f^{\ell}(j,n)=(i,m)=(\tilde{f}^{-1}(j),\overline{f}_{\tilde{f}^{-1}(j)}^{\ell}(n))=(\widetilde{f}^{-1},\overline{f}^{\ell}\otimes\widetilde{f}^{-1})(j,n)$.

That $\mathbf{F}_{n}(\mathbb{Z})$ is simple follows from Lemma 2.10. ∎

######  Remark 2.17.

We mention that in the definition of the monoid $\mathbf{H}$ we denoted the
operation by $\overline{\circ}$ because in our application
$\mathbf{H}=\mathbf{Aut}(\mathbf{J})$ the operation is the usual composition
$\circ$ of functions on $J$. Furthermore, we denoted by $\ocirc$ the operation
of $\mathbf{F}$, as in our case of $\mathbf{F}=\mathbf{F}_{n}(\mathbb{Z})$ it
is composition $\circ$ of functions on $\mathbb{Z}$. Finally, we denoted by
$\odot$ the operation of $\mathbf{N}=\mathbf{F}^{J}$, as it is the extension
of the composition operation of $\mathbf{F}$ to the direct power
$\mathbf{F}^{J}$. Typically, the same symbol is used for the operation in the
direct product, but when this operation is functional composition then
$(n_{1}\odot n_{2})(j)=n_{1}(j)\circ n_{2}(j)$ looks better than $(n_{1}\circ
n_{2})(j)$ which could be easily misinterpreted as $n_{1}(n_{2}(j))$.

##  3 The join of the periodic varieties

In [7] it is shown that each each periodic $\ell$-pregroup is distributive, so
$\mathsf{LP_{n}}\subseteq\mathsf{DLP}$, for all $n$. In this section we show
that the join of all of the varieties $\mathsf{LP_{n}}$, for
$n\in\mathbb{Z}^{+}$, is $\mathsf{DLP}$.

As mentioned earlier, $\ell$-pregroups are exactly the involutive residuated
lattices that satisfy $(xy)^{\ell}=y^{\ell}x^{\ell}$ and $x^{r\ell}=x=x^{\ell
r}$; in the language of residuated lattices this implies $x+y=xy$, $0=1$,
${\sim}x=x^{r}$ and ${-}x=x^{\ell}$. Given $n\in\mathbb{Z}^{+}$, an involutive
residuated lattice is called _$n$ -periodic_ if it satisfies
${\sim}^{n}x={-}^{n}x$; therefore, the notion of $n$-periodicity for
$\ell$-pregroups is a specialization of the one for involutive residuated
lattices. Since $n$-periodicity is defined equationally, the class of all
$n$-periodic involutive residuated lattices is a variety, for each $n$. In [8]
it is proved that the join of all of these $n$-periodic involutive residuated
lattice varieties is equal to the whole variety of involutive residuated
lattices. This proof relies, among other things, on proof-theoretic arguments
on an analytic sequent calculus for the class of involutive residuated
lattices; since an analytic calculus is not known for the class of
distributive $\ell$-pregroups, we cannot use the same methods here, but we
rely on the method of diagrams.

###  3.1 Diagrams and $n$-periodicity

We recall some definitions from [11]. The main idea behind these notions is to
try to capture the failure of an equation in an algebra
$\mathbf{F}(\mathbf{\Omega})$ in a finitistic way: retain only finitely many
points of $\mathbf{\Omega}$ and record the behavior of functions of
$\mathbf{F}(\mathbf{\Omega})$ on these points to still witness the failure. A
_c-chain_ , or _chain with covers_ , is a triple $(\Delta,\leq,\Yleft)$,
consisting of a finite chain $(\Delta,\leq)$ and a subset of the covering
relation, ${\Yleft}\subseteq{\prec}$, i.e., if $a\Yleft b$, then $a$ is
covered by $b$. Given a chain $(\Delta,\leq)$, a partial function $g$ over
$\Delta$ is called _order-preserving_ if, for all $a,b\in Dom(g)$, $a\leq b$
implies $g(a)\leq g(b)$; such a $g$ is intended as the restriction of an
$f\in\mathbf{F}(\mathbf{\Omega})$ to $\mathbf{\Delta}$. A _diagram_
$(\mathbf{\Delta},g_{1},\ldots,g_{l})$ consists of a c-chain $\mathbf{\Delta}$
and order-preserving partial functions $g_{1},\ldots,g_{l}$ on
$(\Delta,\leq)$, where $l\in\mathbb{N}$.

Given a c-chain $(\Delta,\leq,\Yleft)$ and an order-preserving partial
function $g$ on $\Delta$, we define the relation $g^{[\ell]}$ by: for all
$x,b\in\Delta$, $(x,b)\in g^{[\ell]}$ iff $b\in Dom(g)$ and there exists $a\in
Dom(g)$ such that $a\Yleft b$ and $g(a)<x\leq g(b)$. We also define the
relation $g^{[r]}$ by: for all $x,a\in\Delta$, $(x,a)\in g^{[r]}$ iff $a\in
Dom(g)$ and there exists $b\in Dom(g)$, such that $a\Yleft b$ and $g(a)\leq
x<g(b)$. The intention is that $g^{[\ell]}$ will correspond to $f^{\ell}$, for
$f\in\mathbf{F}(\mathbf{\Omega})$, and the covering relation $\Yleft$ is
crucial for this correspondence and for the correct calculation of the two
inverses.

######  Lemma 3.1.

[11] If $\mathbf{\Delta}$ is a c-chain and $g$ is an order-preserving partial
function on $\mathbf{\Delta}$, then $g^{[\ell]}$ and $g^{[r]}$ are order-
preserving partial functions. Therefore, for all $x,b\in\Delta$,
$g^{[\ell]}(x)=b$ iff: $b,b-1\in Dom(g)$, $b-1\Yleft b$ and $g(b-1)<x\leq
g(b)$.

Given a c-chain $\mathbf{\Delta}$ and an order-preserving partial function $g$
on $\mathbf{\Delta}$, we define $g^{[n]}$, for all $n\in\mathbb{N}$,
recursively by: $g^{[0]}=g$ and $g^{[k+1]}:=(g^{[k]})^{[\ell]}$. Also, we
define $g^{[-n]}$, for all $n\in\mathbb{N}$, recursively by
$g^{[-(k+1)]}:=(g^{[k]})^{[r]}$. Lemma 3.1 shows that if $g$ is a partial
function on $\mathbf{\Delta}$, then $g^{[n]}$ is a partial function for all
$n\in\mathbb{Z}$.

We will now define the notion of $n$-periodicity for a partial function $g$ in
a diagram $\mathbf{\Delta}$, which is intended to capture the fact that, when
$\Delta$ is identified with a subset of $\mathbb{Z}$, $g$ is the restriction
to $\Delta$ of an $n$-periodic function of $\mathbb{Z}$, i.e., a function in
$\mathbf{F}_{n}(\mathbb{Z})$. As $\Delta$ might not be convex in $\mathbb{Z}$,
the information of the spacing between elements of $\Delta$ is lost and only
their relative ordering is retained (together with some coverings that are
needed for the correct calculation of iterated inverses $g^{[m]}$). Given
$\mathbf{\Delta}$ and $g$, whether $g$ deserves to be called $n$-periodic
depends on the existence of such a spacing (which is provided by a way of
viewing $\mathbf{\Delta}$ inside $\mathbb{Z}$). This leads to the following
definitions.

A _spacing embedding_ of c-chains is an injection that preserves the order and
the covering relations. Note that such an embedding also reflects the order
(due to the fact that we are working with chains) but may not reflect the
covering relation. Given a spacing embedding
$e:\mathbf{\Delta}_{1}\rightarrow\mathbf{\Delta}_{2}$ and a partial function
$g$ on a c-chain $\mathbf{\Delta}_{1}$, the _counterpart_ of $g$ in
$\mathbf{\Delta}_{2}$ is defined to be the partial map $g^{e}=:e\circ g\circ
e^{-1}$. When $\Delta_{2}=\mathbb{Z}$, spacing embeddings that are shifts of
each other via automorphisms of $\mathbb{Z}$ are essentially equivalent for
our purposes. So we will consider only spacing embeddings where the least
element of their image is $0$. The _height_ of a spacing embedding
$e:\mathbf{\Delta}\rightarrow(\mathbb{Z},\leq_{\mathbb{Z}},\Yleft_{\mathbb{Z}})$
is then defined to be $\max(e[\Delta])$, i.e., the size of the convexification
of the image $e[\Delta]$ in $\mathbb{Z}$ (minus 1). The following definition
of $n$-periodicity is inspired by the equivalences in Lemma 2.8.

A partial function $g$ on a c-chain $\mathbf{\Delta}$ is called _$n$
-periodic_ with respect to a spacing embedding
$e:\mathbf{\Delta}\rightarrow(\mathbb{Z},\leq_{\mathbb{Z}},\Yleft_{\mathbb{Z}})$,
where $n\in\mathbb{Z}^{+}$, if ($\min(e[\Delta])=0$ and) for all $x,y\in
Dom(g^{e})$ and $k\in\mathbb{Z}$,

$x\leq_{\mathbb{Z}}y+kn\Rightarrow g^{e}(x)\leq_{\mathbb{Z}}g^{e}(y)+kn.$

or equivalently, because $\mathbb{Z}$ is a chain, and by setting $k:=-k$,

$g^{e}(y)<_{\mathbb{Z}}g^{e}(x)+kn\Rightarrow y<_{\mathbb{Z}}x+kn.$

Therefore, $g$ is $n$-periodic with respect to $e$ iff $g^{e}$ is $n$-periodic
with respect to the identity map on $\mathbb{Z}$. Observe that given that $e$
preserves and reflects the order, $n$-periodic partial functions are also
order preserving.

A main issue with this definition is that it provides no insight on whether it
is possible to consider only finitely-many spacing embeddings or, given such
an embedding, whether it suffices to consider only finitely-many $k$’s in the
$n$-periodicity condition. Actually, Lemma 3.3 below shows that this
definition merely translates, into a more palatable form, the demand that
there exists a counterpart of $g$ that extends to an $n$-periodic function of
$\mathbb{Z}$. In Lemma 3.2 we show that checking finitely-many $k$’s suffices.
In order to obtain decidability results, we later also prove that finitely-
many spacing embeddings suffice.

######  Lemma 3.2.

If $\mathbf{\Delta}$ is a c-chain, $g$ is a partial function on
$\mathbf{\Delta}$ and $e:\mathbf{\Delta}\rightarrow\mathbb{Z}$ is a spacing
embedding of height $d$, then $g$ is $n$-periodic with respect to $e$ iff for
all $x,y\in Dom(g^{e})$ and $|k|\leq\lceil d/n\rceil$ we have $x\leq
y+kn\Rightarrow g^{e}(x)\leq g^{e}(y)+kn$.

###### Proof.

For the non-trivial (backward) direction, we assume that $x\leq y+kn$, $x,y\in
Dom(g^{e})$, and $k\in\mathbb{Z}$ with $k>\lceil d/n\rceil$. Since, $x\leq
y+d\leq y+\lceil d/n\rceil n\leq y+kn$, we get $g^{e}(x)\leq g^{e}(y)+\lceil
d/n\rceil n\leq g^{e}(y)+kn$, by the $n$-periodicity of $g$ for the value
$\lceil d/n\rceil$. If $k<-\lceil d/n\rceil$ and $x,y\in Dom(g^{e})$, then
$-d\leq x-y$, so $y+kn<y-\lceil d/n\rceil n\leq y-d\leq x$; hence the
condition is holds vacuously. ∎

For convenience, for a fixed $n\in\mathbb{Z}^{+}$, for every $x\in\mathbb{Z}$
we denote by $Rx$ the remainder and by $Qx$ the quotient of dividing $x$ by
$n$. So, $x-Rx=Qx\cdot n$ and we denote this value by $Sx$.

######  Lemma 3.3.

If $\mathbf{\Delta}$ is a c-chain, $g$ is a partial function on $\Delta$ and
$e$ is a spacing embedding $e$ on $\mathbf{\Delta}$, then $g$ is $n$-periodic
with respect to $e$ iff its counterpart $g^{e}$ can be extended to a function
in $F_{n}(\mathbb{Z})$.

###### Proof.

First note that the backward direction holds by Lemma 2.8. Note that the empty
partial function is vacuously $n$-periodic, so we will assume that the partial
functions are non-empty. For the forward direction, we note that $h:=g^{e}$ is
an $n$-periodic partial function on $\mathbb{Z}$ with respect to the identity
spacing embedding. We define the partial function $\hat{h}$ on $\mathbb{Z}$ by
$\hat{h}(Rx)=h(x)-Sx$ for all $x\in Dom(h)$, hence that
$Dom(\hat{h})\subseteq[0,n)_{\mathbb{Z}}$; we will show that $\hat{h}$ is
well-defined (single-valued) and $n$-periodic at the same time. If $x,y\in
Dom(h)$, $k\in\mathbb{Z}$ and $Rx\leq Ry+kn$, then $Rx+Sx\leq Ry+Sy+(Sx-
Sy)+kn$, so $x\leq y+kn+(Sx-Sy)$; since $Sx$ and $Sy$ are multiples of $n$,
the periodicity of $h$ yields $h(x)\leq h(y)+kn+(Sx-Sy)$, so
$(h(x)-Sx)\leq(h(y)-Sy)+kn$. By applying this for $k=0$ (and for two
inequalities simultaneously) we get $Rx=Ry\Rightarrow(h(x)-Sx)=(h(y)-Sy)$. By
applying this for arbitrary $k$ we get $Rx\leq
Ry+kn\Rightarrow\hat{h}(Rx)\leq\hat{h}(Ry)+kn$.

We extend $\hat{h}$ to a function $f:[0,n)_{\mathbb{Z}}\rightarrow\mathbb{Z}$
on the whole period, given by $f(x)=\hat{h}(a_{x})$, where $a_{x}$ is the
smallest $a\in Dom(\hat{h})$ with $x\leq a$, if such an $a$ exists, and
$a_{x}$ is the biggest $a\in Dom(\hat{h})$, otherwise. To verify that $f$ is
$n$-periodic with respect to the identity, by Lemma 3.2 it is enough to check
the $n$-periodicity condition for $k\in\\{-1,0,1\\}$; since $x\nleq y-n$ for
all $x,y\in[0,n)_{\mathbb{Z}}$, we consider only $k\in\\{0,1\\}$. If
$x,y\in[0,n)_{\mathbb{Z}}$ and $x\leq y+n$, since $a_{x},a_{y}\in[0,n)$ we
have $a_{x}\leq a_{y}+n$, so $\hat{h}(a_{x})\leq\hat{h}(a_{y})+n$ by the
$n$-periodicity of $\hat{h}$, hence $f(x)\leq f(y)+n$. Also, for all
$x,y\in[0,n)_{\mathbb{Z}}$, if $x\leq y+0$, then $a_{x}\leq a_{y}$, so
$\hat{h}(a_{x})\leq\hat{h}(a_{y})$, hence $f(x)\leq f(y)$. Therefore $f$ is a
partial function on $\mathbb{Z}$ that is $n$-periodic with respect to the
identity.

Finally, we extend $f$ to a total function $\hat{f}$ on $\mathbb{Z}$, by
$\hat{f}(x)=f(Rx)+Sx$ for all $x\in\mathbb{Z}$; note that $\hat{f}$ extends
$f$, since $Rx=x$ and $Sx=0$, for all $x\in[0,n)_{\mathbb{Z}}$. To show that
$\hat{f}\in F_{n}(\mathbb{Z})$, we will verify the conditions of Lemma 2.9.
For condition (2), if $x,y,k\in\mathbb{Z}$ and $x\leq y+kn$, then $Rx\leq
Ry+Sy-Sx+kn$, so by the $n$-periodicity of $f$ we have $f(Rx)\leq f(Ry)+Sy-
Sx+kn$, so $f(Rx)+Sx\leq f(Ry)+Sy+kn$, i.e., $\hat{f}(x)\leq\hat{f}(y)+kn$. In
particular, $\hat{f}$ is order preserving. For condition (1), if
$b\in\mathbb{Z}$ and $x\in\hat{f}^{-1}[\hat{f}(b)]$, then
$\hat{f}(x)=\hat{f}(b)$, so $\hat{f}(b)-n<\hat{f}(x)<\hat{f}(b)+n$. Also,
$\hat{f}(b\pm n)=f(R(b\pm n))+S(b\pm n)=f(Rb)+Sb\pm n=\hat{f}(b)\pm n$, so
$\hat{f}(b-n)<\hat{f}(x)<\hat{f}(b+n)$, and by order preservation $b-n<x<b+n$.
Therefore, $\hat{f}^{-1}[\hat{f}(b)]\subseteq[b-n,b+n]$. Consequently,
$\hat{f}\in F_{n}(\mathbb{Z})$.

To see that $\hat{f}$ extends $h$, note that if $x\in Dom(h)$ then $Rx\in
Dom(\hat{h})$ and $\hat{h}(Rx)=h(x)-Sx$. By definition of $\hat{f}$ and given
that $f$ extends $\hat{h}$, we have
$\hat{f}(x)=f(Rx)+S(x)=\hat{h}(Rx)+Sx=h(x)-Sx+Sx=h(x)$. ∎

The next lemma shows that [ℓ] and [r] keep us within the setting of
$n$-periodicity.

######  Lemma 3.4.

If $\mathbf{\Delta}$ is a c-chain and $g$ is partial function on
$\mathbf{\Delta}$ that is $n$-periodic with respect to a spacing embedding
$e$, then the partial functions $g^{[\ell]}$ and $g^{[r]}$ are $n$-periodic on
$\mathbf{\Delta}$ with respect to $e$. Moreover,
$(g^{[\ell]})^{e}\subseteq(g^{e})^{[\ell]}$ and
$(g^{[r]})^{e}\subseteq(g^{e})^{[r]}$.

###### Proof.

By Lemma 3.1 we know that $g^{[\ell]}$ and $g^{[r]}$ are partial functions
over $\mathbf{\Delta}$. Let $h:=g^{e}$ be the counterpart of $g$ with respect
to a spacing embedding $e$ witnessing the $n$-periodicity of $g$; then $h$ is
$n$-periodic with respect to $id_{\mathbb{Z}}$.

Let $x,y\in Dom(h^{[\ell]})$, and set $a:=h^{[\ell]}(x)$ and
$b:=h^{[\ell]}(y)$. Then, by definition, $a,a-1,b,b-1\in Dom(h)$,
$h(a-1)<x\leq h(a)$ and $h(b-1)<y\leq h(b)$. If $x\leq y+kn$ for some
$k\in\mathbb{Z}$, then $h(a-1)<x\leq y+kn\leq h(b)+kn$, so by the
$n$-periodicity of $h$, we get $a-1<b+kn$. Consequently, $h^{[\ell]}(x)=a\leq
b+kn=h^{[\ell]}(y)+kn$. So $h^{[\ell]}$ is an $n$-periodic partial function
with respect to $id_{\mathbb{Z}}$; in particular, any restriction of it is
also $n$-periodic.

To show that $(g^{[\ell]})^{e}=h^{[\ell]}|_{Dom((g^{[\ell]})^{e})}$, note that
if $x\in Dom((g^{[\ell]})^{e})$, then $e^{-1}(x)\in Dom(g^{[\ell]})$, so there
exist $a,a-1\in Dom(g)$, such that $g(a-1)<e^{-1}(x)\leq g(a)$ and
$g^{[\ell]}(e^{-1}(x))=a$. Hence, $ege^{-1}(e(a)-1)=ege^{-1}(e(a-1))<x\leq
ege^{-1}(e(a))$, i.e., $h(e(a)-1)<x\leq h(e(a))$, thus
$h^{[\ell]}(x)=e(a)=eg^{[\ell]}(e^{-1}(x))=(g^{[\ell]})^{e}(x)$. Similarly, we
can show that $(g^{[r]})^{e}\subseteq(g^{e})^{[r]}$. ∎

###  3.2 The join

By [7], for every $n$, the variety $\mathsf{LP_{n}}$ of $n$-periodic
$\ell$-pregroups is a subvariety of $\mathsf{DLP}$. Here we prove that the
join of all of the $\mathsf{LP_{n}}$’s is precisely the whole variety
$\mathsf{DLP}$; in other words the class of periodic $\ell$-pregroups
generates the variety of all distributive $\ell$-pregroups.

It is shown in [11] that every equation in the language of $\ell$-pregroups is
equivalent to one of the form $1\leq w_{1}\vee\ldots\vee w_{k}$ where
$m\in\mathbb{Z}^{+}$ and the $w_{i}$’s are _intensional terms_ , i.e., terms
of the form

$x_{1}^{(m_{1})}x_{2}^{(m_{2})}\ldots x_{l}^{(m_{l})},$

where $x_{1},\ldots,x_{l}$ are not necessarily distinct variables,
$l\in\mathbb{N}$, and $m_{1},\ldots,m_{l}\in\mathbb{Z}$. Therefore, we may
consider equations in such _intensional_ form.

Recall that a failure of an equation $1\leq w_{1}\vee\ldots\vee w_{k}$ in
$\mathbf{F}(\mathbf{\Omega})$ consists of a homomorphism
$\varphi:\mathbf{Tm}\rightarrow\mathbf{F}(\mathbf{\Omega})$, from the algebra
$\mathbf{Tm}$ of all terms in the language of $\ell$-pregroups, such that
$\varphi(1)(p)>\varphi(w_{1})(p),\ldots,\varphi(w_{k})(p)$, for some
$p\in\Omega$.

The failure of an equation in a diagram is formulated relative to an
_intensional algebra_ —an algebra over the language
$(\cdot,1,^{\ell},^{r})$—playing the role of $\mathbf{F}(\mathbf{\Omega})$.
Given a c-chain $\mathbf{\Delta}$, we define the algebra
$\mathbf{Pf}(\mathbf{\Delta})=(Pf(\mathbf{\Delta}),{\circ},^{[\ell]},^{[r]},i_{\Delta})$,
where $Pf(\mathbf{\Delta})$ is the set of all the order-preserving partial
functions over $\mathbf{\Delta}$, $\circ$ is the composition of partial
functions, $i_{\Delta}$ is the identity function on $\Delta$, and $g\mapsto
g^{[\ell]}$ and $g\mapsto g^{[r]}$ are the two inversion operations as defined
on $\mathbf{\Delta}$.

The following lemma follows from the definition of counterparts and by
iterations of Lemma 3.4.

######  Lemma 3.5.

If $\mathbf{\Delta}$ is an c-chain and $g,f$ are partial functions on
$\mathbf{\Delta}$ that are $n$-periodic with respect to a spacing embedding
$e$, then

  1. 1.

$(f\circ g)^{e}=f^{e}\circ g^{e}$ and

  2. 2.

for all $m\in\mathbb{Z}$, $(g^{[m]})^{e}\subseteq(g^{e})^{[m]}$.

Moreover, for every $u\in\mathbf{Ti}$ with $l$-many variables and
$g_{1},\ldots,g_{l}$ partial functions on $\mathbf{\Delta}$, $n$-periodic with
respect to $e$, then $(u^{\mathbf{Pf}(\mathbf{\Delta})}(g_{1},\ldots
g_{l}))^{e}\subseteq u^{\mathbf{Pf}(\mathbb{Z})}(g_{1}^{e},,g_{l}^{e})$.

###### Proof.

(1) is easy to see and (2) follows from Lemma 3.4. We will prove the remaining
inclusion by induction on the structure of terms. For the induction step, let
$u$ be a term of the form $u=x^{(m)}v$ where $m\in\mathbb{Z}$, $v$ is a term
in $\mathbf{Ti}$ over variables $x_{1},\ldots,x_{l}$, and
$x\in\\{x_{1},\ldots,x_{l}\\}$. Also, let $g_{1},\ldots,g_{l}$ be partial
functions on $\mathbf{\Delta}$ that are $n$-periodic with respect to the same
spacing embedding $e$ such that
$(v^{\mathbf{Pf}(\mathbf{\Delta})}(g_{1},\ldots g_{l}))^{e}\subseteq
v^{\mathbf{Pf}(\mathbb{Z})}(g_{1}^{e},\ldots,g_{l}^{e})$; we will write $g$
for the partial function corresponding to $x$. If $a\in
Dom((u^{\mathbf{Pf}(\mathbf{\Delta})}(g_{1},\ldots g_{l}))^{e})$, then $a\in
Dom((g^{(m)})^{e}(v^{\mathbf{Pf}(\mathbf{\Delta})}(g_{1},\ldots g_{l}))^{e})$
by (1), so $a\in Dom((v^{\mathbf{Pf}(\mathbf{\Delta})}(g_{1},\ldots
g_{l}))^{e})$, in particular. So, $e^{-1}a\in
Dom(v^{\mathbf{Pf}(\mathbf{\Delta})}(g_{1},\ldots g_{l}))$ and
$v^{\mathbf{Pf}(\mathbf{\Delta})}(g_{1},\ldots g_{l})(e^{-1}a)\in
Dom(g^{[m]})$. So, by (1), $(u^{\mathbf{Pf}(\mathbf{\Delta})}(g_{1},\ldots
g_{l}))^{e}(a)=(g^{[m]})^{e}(v^{\mathbf{Pf}(\mathbf{\Delta})}(g_{1},\ldots
g_{l}))^{e}(a)$ and by hypothesis
$(g^{[m]})^{e}(v^{\mathbf{Pf}(\mathbf{\Delta})}(g_{1},\ldots
g_{l}))^{e}(a)=(g^{[m]})^{e}(v^{\mathbf{Pf}(\mathbb{Z})}(g_{1}^{e},\ldots
g_{l}^{e}))(a)$. By (2),
$(g^{[m]})^{e}(v^{\mathbf{Pf}(\mathbb{Z}}(g_{1}^{e},\ldots
g_{l}^{e}))(a)=(g^{e})^{[m]}(v^{\mathbf{Pf}(\mathbb{Z})}(g_{1}^{e},\ldots
g_{l}^{e}))(a)$, therefore, $(u^{\mathbf{Pf}(\mathbf{\Delta})}(g_{1},\ldots
g_{l}))^{e}(a)=u^{\mathbf{Pf}(\mathbb{Z})}(g_{1}^{e},\ldots,g_{l}^{e})(a)$. ∎

For $n\in\mathbb{Z}^{+}$, a diagram is called _$n$ -periodic_ with respect to
some spacing embedding if all of its partial functions are $n$-periodic with
with respect to that embedding. A diagram is called _$n$ -periodic_ if it is
$n$-periodic with respect to some spacing embedding.

We say that the equation $1\leq w_{1}\vee\ldots\vee w_{k}$ in intensional form
over variables $x_{1},\ldots,x_{l}$ _fails_ in a diagram
$(\mathbf{\Delta},f_{1},\ldots,f_{l})$ if there is an intensional homomorphism
$\varphi:\mathbf{Ti}\rightarrow\mathbf{Pf}(\mathbf{\Delta})$, from the algebra
$\mathbf{Ti}$ of all intensional terms, and a point $p\in\Delta$ such that
$\varphi(1)(p)>\varphi(w_{1})(p),\ldots,\varphi(w_{k})(p)$ and
$\varphi(x_{i})=f_{i}$ for all $1\leq i\leq l$.

In the following, we denote the lenght of an equation $\varepsilon$ by
$|\varepsilon|$.

######  Lemma 3.6.

If an equation $\varepsilon$ fails in a diagram, then it fails in an
$n$-periodic diagram, where $n=2^{|\varepsilon|}|\varepsilon|^{4}$.

###### Proof.

In the proof of Corollary 4.4 of [11] it is shown that if an equation
$\varepsilon$ fails in a diagram, then it also fails in a diagram where the
c-chain has size $n=2^{|\varepsilon|}|\varepsilon|^{4}$.

Note that every diagram based on a c-chain $\mathbf{\Delta}$ is $n$-periodic
for $n\geq|\Delta|$, as follows. For every partial function $g$ of the
diagram, we consider the (unique) spacing embedding
$e:\Delta\rightarrow\mathbb{Z}$ where $e[\Delta]=\mathbb{N}_{d}$ and
$d=|\Delta|$. Then the partial function $g^{e}$ is defined on the convex
subset $\mathbb{N}_{d}$ of $\mathbb{Z}$, so it can be extended to a partial
function with domain $\mathbb{N}_{n}$ (in any order-preserving way) since
$d\leq n$. This order-preserving partial function is vacuously $n$-periodic,
so it can be further extended periodically to an $n$-periodic function on
$\mathbb{Z}$ by Lemma 3.3. Thus, every partial function of the diagram is
$n$-periodic, hence the equation fails in an $n$-periodic diagram. ∎

The following lemma will help us show that if an equation $\varepsilon$ fails
in a distributive $\ell$-pregroup, then it fails in a periodic one.

######  Lemma 3.7.

If an equation fails in an $n$-periodic diagram, then it fails in
$\mathbf{F}_{n}(\mathbb{Z})$.

###### Proof.

Suppose that an equation $1\leq w_{1}\vee\ldots\vee w_{t}$, in intensional
form, fails in a diagram $(\mathbf{\Delta},g_{1},\ldots,g_{l})$ that is
$n$-periodic with respect to a spacing embedding
$e:\mathbf{\Delta}\rightarrow(\mathbb{Z},\leq_{\mathbb{Z}},\Yleft_{\mathbb{Z}})$,
where $\min(e[\Delta])=0$. This means that there exist $p\in\Delta$ and an
intentional homomorphism
$\varphi:\mathbf{Ti}\rightarrow\mathbf{Pf}(\mathbf{\Delta})$ where
$\varphi(x_{i})=g_{i}$ for all $1\leq i\leq l$, satisfying
$\varphi(1)(p)>\varphi(w_{1})(p),\ldots,\varphi(w_{t})(p)$. For each
$i\in\\{1,\ldots,l\\}$, by Lemma 3.3 the counterpart of each $g_{i}$ by $e$
can be extended to a function $f_{i}\in F_{n}(\mathbb{Z})$.

We extend the assignment $\hat{\varphi}(x_{i})=g^{e}_{i}$ to an intentional
homomorphism
$\hat{\varphi}:\mathbf{Ti}\rightarrow\mathbf{Pf}(e[\mathbf{\Delta}])$; by
Lemma 3.5 have $\varphi(u)^{e}e(p)=\hat{\varphi}(u)e(p)$, for all $u\in FS$.
It follows from the last paragraphs of Theorem 4.1 in [11] that there is a
homomorphism ${\psi}:\mathbf{Ti}\rightarrow\mathbf{F}(\mathbb{Z})$ extending
the assignment $\psi(x_{i})=f_{i}$ and satisfying
$\psi(u)(e(p))=\hat{\varphi}(u)(e(p))$ for all $u\in FS$. Since the extensions
$f_{1},\ldots,f_{l}$ are in $F_{n}(\mathbb{Z})$, the range of $\psi$ is in
$\mathbf{F}_{n}(\mathbb{Z})$. Also $\varepsilon$ fails in
$\mathbf{F}_{n}(\mathbb{Z})$ since for all $i\in\\{1,\ldots,k\\}$, we have
$\psi(w_{i})(e(p))=e\varphi(w_{i})(p)<\psi(1)(e(p))=e\varphi(1)(p)$. ∎

######  Theorem 3.8.

An equation $\varepsilon$ fails in $\mathsf{DLP}$ iff it fails in
$\mathbf{F}_{n}(\mathbb{Z})$, where $n=2^{|\varepsilon|}|\varepsilon|^{4}$.

###### Proof.

If an equation fails in $\mathsf{DLP}$, then by [11] it fails in a diagram. By
Lemma 3.6, the equation fails in an $n$-periodic diagram, where
$n=2^{|\varepsilon|}|\varepsilon|^{4}$. By Lemma 3.7, the equation fails in
$\mathbf{F}_{n}(\mathbb{Z})$. On the other hand, if $\varepsilon$ fails in
$\mathbf{F}_{n}(\mathbb{Z})$, then $\varepsilon$ fails in $\mathsf{DLP}$,
since $\mathbf{F}_{n}(\mathbb{Z})\in\mathsf{DLP}$. ∎

This reduces the decidability of the equational theory of $\mathsf{DLP}$ to
the decidability of all of the $\mathbf{F}_{n}(\mathbb{Z})$’s: given an
equation to check, we know which $\mathbf{F}_{n}(\mathbb{Z})$ to test it in.
In Section 4 we will prove that $\mathbf{F}_{n}(\mathbb{Z})$ is decidable, for
each $n$.

The following theorem shows that $\mathsf{DLP}$ can be expressed as a join in
two different ways.

######  Theorem 3.9.

$\mathsf{DLP}=\bigvee\mathsf{LP_{n}}=\bigvee\mathsf{V}(\\{\mathbf{F}_{n}(\mathbb{Z})\\})=\mathsf{V}(\\{\mathbf{F}_{n}(\mathbb{Z}):n\in\mathbb{Z}^{+}\\})$.

###### Proof.

By Lemma 3.8, we have
$\mathsf{DLP}\subseteq\mathsf{V}(\\{\mathbf{F}_{n}(\mathbb{Z}):n\in\mathbb{Z}^{+}\\})$.
Furthermore, by general facts we have
$\mathsf{V}(\\{\mathbf{F}_{n}(\mathbb{Z}):n\in\mathbb{Z}^{+}\\})=\bigvee\mathsf{V}(\\{\mathbf{F}_{n}(\mathbb{Z})\\})$.
Since each algebra $\mathbf{F}_{n}(\mathbb{Z})$ is $n$-periodic, we get
$\mathsf{V}(\\{\mathbf{F}_{n}(\mathbb{Z})\\})\subseteq\mathsf{LP_{n}}$, so
$\bigvee\mathsf{V}(\\{\mathbf{F}_{n}(\mathbb{Z})\\})\subseteq\bigvee\mathsf{LP_{n}}$.
Finally, by [7], for every $n$, $\mathsf{LP_{n}}\subseteq\mathsf{DLP}$, so
$\bigvee\mathsf{LP_{n}}\subseteq\mathsf{DLP}$. ∎

This complements nicely the result of [11] that $\mathsf{DLP}$ is generated by
$\mathbf{F}(\mathbb{Z})$.

###  3.3 From the join down to the varieties?

It follows from Theorem 3.9 that
$\bigvee\mathsf{LP_{n}}=\bigvee\mathsf{V}(\mathbf{F}_{n}(\mathbb{Z}))$. For
each $n$, we want to find a generating algebra for $\mathsf{LP_{n}}$, so it is
tempting to conjecture that
$\mathsf{LP_{n}}=\mathsf{V}(\mathbf{F}_{n}(\mathbb{Z}))$, for all (or at least
some) $n$. This fails for $n=1$, since $\mathsf{LP}_{1}$ is the variety of
$\ell$-groups while $\mathbf{F}_{1}(\mathbb{Z})$ is isomorphic the
$\ell$-pregroup on the integers (it consists of only the translations on the
integers) and $\mathsf{V}(\mathbf{F}_{1}(\mathbb{Z}))$ is the variety of
abelian $\ell$-groups. Corollary 3.11 below shows that this actually fails for
every single $n$, i.e., for all $n$, the algebra $\mathbf{F}_{n}(\mathbb{Z})$
generates a proper subvariety of $\mathsf{LP_{n}}$.

In other words, it will follow that if an equation fails in a distributive
$\ell$-pregroup, then it fails in $\mathsf{LP_{n}}$ and it fails in
$\mathsf{V}(\mathbf{F}_{m}(\mathbb{Z}))$ for some $m,n$ (which can be then
taken to be minimal such), and also that $n\leq m$ (since
$\mathsf{V}(\mathbf{F}_{k}(\mathbb{Z}))\subseteq\mathsf{LP}_{k}$, for all
$k$), but we necessarily have $n<m$.

The combination of
$\mathsf{V}(\mathbf{F}_{n}(\mathbb{Z}))\not=\mathsf{LP_{n}}$, for all $n$, and
$\bigvee\mathsf{V}(\mathbf{F}_{n}(\mathbb{Z}))=\bigvee\mathsf{LP_{n}}$ is
quite interesting and surprising. This means that for each $n$, the algebra
$\mathbf{F}_{n}(\mathbb{Z})$ satisfies a special equation, but there is no
special equation that is satisfied by all of the
$\mathbf{F}_{n}(\mathbb{Z})$’s. We prove that
$\mathsf{V}(\mathbf{F}_{n}(\mathbb{Z}))\not=\mathsf{LP_{n}}$, for each $n$, by
providing such an equation tailored to each $n$.

The equation states that all invertible elements commute. Clearly, the
invertible elements in an $\ell$-pregroup are the $1$-periodic elements and,
by Lemma 2.6, they form a subalgebra, which is therefore an $\ell$-group; this
is the maximal subalgebra that is an $\ell$-group and we call it the the
_maximal $\ell$-subgroup_ of the $\ell$-pregroup. Therefore, in an
$\ell$-pregroup the inverible elements commute iff its maximal $\ell$-subgroup
is abelian. It is easy to see that an element $g$ is invertible iff
$g^{\ell}=g^{r}$. Therefore, the the property that all invertibles commute can
be captured by the quasiequation

$(x^{\ell}=x^{r}\;\&\;y^{\ell}=y^{r})\Rightarrow xy=yx.$

The lemma below entails that this quasiequation is not equivalent to any
equation. However, when restricted to $n$-periodic $\ell$-pregroups, for a
fixed $n$, this can be captured by the equation

$(x\vee x^{\ell\ell}\vee\cdots\vee x^{\ell^{2n-2}})(y\vee
y^{\ell\ell}\vee\cdots\vee y^{\ell^{2n-2}})=(y\vee\cdots\vee
y^{\ell^{2n-2}})(x\vee\cdots\vee x^{\ell^{2n-2}})$

For convenience, for all $n$, we define the term $i_{n}(x):=x\vee
x^{\ell\ell}\vee\cdots\vee x^{\ell^{2n-2}}$.

######  Lemma 3.10.

For every $n$, and $n$-periodic $\ell$-pregroup $\mathbf{A}$, the following
hold.

  1. 1.

The invertible elements of the algebra $\mathbf{A}$ are exactly the ones of
the form $i_{n}(a)=a\vee a^{\ell\ell}\vee\cdots\vee a^{\ell^{2n-2}}$, where
$a\in A$.

  2. 2.

The invertible elements of the algebra $\mathbf{A}$ commute iff $\mathbf{A}$
satisfies the equation $i_{n}(x)i_{n}(y)=i_{n}(y)i_{n}(x)$.

  3. 3.

The equation $i_{n}(x)i_{n}(y)=i_{n}(y)i_{n}(x)$ holds in
$\mathbf{F}_{n}(\mathbb{Z})$ but fails in $\mathsf{LP_{n}}$.

###### Proof.

(1) Since $\mathbf{A}$ is $n$-periodic, it satisfies $x^{\ell^{2n}}=x$, so for
all $a\in A$, we have $(a\vee a^{\ell\ell}\vee\cdots\vee a^{\ell^{2n-4}}\vee
a^{\ell^{2n-2}})^{\ell\ell}=a^{\ell\ell}\vee a^{\ell^{4}}\vee\cdots\vee
a^{\ell^{2n-2}}\vee a^{\ell^{2n}}=a^{\ell\ell}\vee a^{\ell^{4}}\vee\cdots\vee
a^{\ell^{2n-2}}\vee a$. Therefore, $a\vee a^{\ell\ell}\vee\cdots\vee
a^{\ell^{2n}}$ is invertible. Conversely, if $a$ is invertible, then $a\vee
a^{\ell\ell}\vee\cdots\vee a^{\ell^{2n}}=a$, so it is of this form. (2)
follows from (1).

(3) The only invertible elements of $\mathbf{F}_{n}(\mathbb{Z})$ are the
translations, so they commute with each other; thus
$\mathbf{F}_{n}(\mathbb{Z})$ satisfies the equation. However, there exist non-
commutative $\ell$-groups, such as the group $\mathbf{F}_{1}(\mathbb{Q})$ of
all order-preserving permutations on $\mathbb{Q}$. All $\ell$-pregroups are
$1$-periodic, hence also $n$-periodic. Thus, $\mathbf{F}_{1}(\mathbb{Q})$ is
in $\mathsf{LP_{n}}$, but not all of its invertible elements commute, since
all of its elements are invertible. ∎

Actually, even though by the following corollary $\mathbf{F}_{n}(\mathbb{Z})$
fails to generate $\mathsf{LP_{n}}$, our second representation theorem
(Theorem 2.16) that every $n$-periodic $\ell$-pregroup can be embedded into a
wreath product $\mathbf{H}\wr\mathbf{F}_{n}(\mathbb{Z})$, where $\mathbf{H}$
is an $\ell$-group, showcases the importance of the algebra
$\mathbf{F}_{n}(\mathbb{Z})$ in studying $\mathsf{LP_{n}}$. In that respect,
Lemma 3.7 (which shows that failures in $n$-periodic diagrams can be embedded
in $\mathbf{F}_{n}(\mathbb{Z})$) will turn out to be very useful in the next
sections.

######  Corollary 3.11.

$\mathsf{LP_{n}}\not=\mathsf{V}(\mathbf{F}_{n}(\mathbb{Z}))$, for all $n$.

For each $n$, we want to find a chain $\mathbf{\Omega}_{n}$ such that
$\mathsf{LP_{n}}=\mathsf{V}(\mathbf{F}_{n}(\mathbf{\Omega}_{n}))$. Corollary
3.11 shows that we cannot take $\mathbf{\Omega}_{n}=\mathbb{Z}$ for any $n$.
At this moment it is not clear that such an $\mathbf{\Omega}_{n}$ exists for
any $n$ other than $n=1$: we can take $\mathbf{\Omega}_{1}=\mathbb{Q}$ because
the variety of $\ell$-groups is generated by $\mathbf{F}_{1}(\mathbb{Q})$.
Actually, the next result shows that we cannot take
$\mathbf{\Omega}_{n}=\mathbb{Q}$ for any $n>1$.

Recall that an element of a chain is called a _limit point_ if it is the join
of all of the elements strictly below it or the meet of all of the elements
strictly above it.

######  Lemma 3.12.

If $\mathbf{\Omega}$ is a chain where every point is a limit point, then we
get $\mathbf{F}_{n}(\mathbf{\Omega})=\mathbf{F}_{1}(\mathbf{\Omega})$, for all
$n$. In particilar, $\mathbf{F}_{n}(\mathbb{Q})=\mathbf{F}_{1}(\mathbb{Q})$,
for all $n$. Therefore,
$\mathsf{LP_{n}}\not=\mathsf{V}(\mathbf{F}_{n}(\mathbb{Q}))$ for each $n>1$.

###### Proof.

By Lemma 2.7 of [11], for $f\in F_{n}(\mathbf{\Omega})$ if the preimage of an
element under $f$ has more than one element, then the element is not a limit
point, a contradiction; so every preimage must have at most one element, i.e.,
$f$ is one-to-one. To show that it is onto, assume an element $a$ is not in
the image. By Lemma 2.4 there exists a covering pair $b\prec c$ such that
$a\in(f(b),f(c))$, contradicting the fact that there are no covering pairs in
$\mathbf{\Omega}$. ∎

In Section 5 we prove that for each $n$ there exists indeed a
$\mathbf{\Omega}_{n}$ such that
$\mathsf{LP_{n}}=\mathsf{V}(\mathbf{F}_{n}(\mathbf{\Omega}_{n}))$. Actually,
we do better than that: we identify a single chain $\mathbf{\Omega}$ such that
$\mathsf{LP_{n}}=\mathsf{V}(\mathbf{F}_{n}(\mathbf{\Omega}))$ for all $n$.
This single/uniform chain is
$\mathbf{\Omega}=\mathbb{Q}\overrightarrow{\times}\mathbb{Z}$. Due to the
wreath-product decomposition $\mathbf{H}\wr\mathbf{F}_{n}(\mathbb{Z})$ of
$\mathbf{F}_{n}(\mathbf{\Omega})$, where $\mathbf{\Omega}$ is integral, the
analysis in Section 5 will benefit from the study of the algebra
$\mathbf{F}_{n}(\mathbb{Z})$, so the next section is devoted to that.

##  4 Decidability for $F_{n}(\mathbb{Z})$

The wreath product decomposition for $\mathbf{F}_{n}(\mathbf{\Omega})$ of
Theorem 2.16 brings to the forefront the role of $\mathbf{F}_{n}(\mathbb{Z})$
in understanding $n$-preriodic $\ell$-pregroups. In particular, it turns out
that a lot of the notions (such as $n$-periodicity in a diagram) that will be
needed for the generation result for $\mathsf{LP_{n}}$ already show up when
studying the structure of $\mathbf{F}_{n}(\mathbb{Z})$. In this section we
study this structure and actually prove that the equational theory of
$\mathbf{F}_{n}(\mathbb{Z})$ is decidable. The results of this section will
also be the main driving force for proving that the equational theory of
$n$-preriodic $\ell$-pregroups is decidable in Section 5.

###  4.1 Failures in compatible surjections

Given an equation $\varepsilon$ in intensional form $1\leq w_{1}\vee\ldots\vee
w_{k}$ we will define a set $\Delta_{\varepsilon}$ of terms in an expansion of
the intensional language. First we define the set of _final subwords_ of
$\varepsilon$, $FS_{\varepsilon}:=\\{u:w_{1}=vu\text{ or }...\text{ or
}w_{k}=vu,\text{ for some }v\\}$.

We actually take $\mathbf{Ti}$ to satisfy the equalities $v\cdot 1=v=1\cdot
v$, so strictly speaking we take it to be a quotient of the absolutely free
algebra, so $FS_{\varepsilon}$ contains $1$. The particular syntactic
expressions below, serving as names for the points in $\Delta_{\varepsilon}$,
will not be important for our results, since the work done in [11] (which we
will be citing when appropriate) ensures that $\Delta_{\varepsilon}$ has
enough points for the iterated inverses $g^{[m]}$ to be calculated correctly;
we include the definition for completeness.

In the following the notation $-a$ and $+a$ will be interpreted by the lower
and upper cover of $a$ and $0a=a$, when evaluating the terms. For a variable
$x$ among the variables $x_{1},\ldots,x_{n}$ of $\varepsilon$,
$m\in\mathbb{N}$ and $v\in FS_{\varepsilon}$ we define

$\displaystyle\Delta_{x,m}^{v}$
$\displaystyle:=\\{v\\}\cup\bigcup_{j=0}^{m}\\{\sigma_{j}x^{(j)}\ldots\sigma_{m}x^{(m)}v:\,\sigma_{j},\ldots,\sigma_{m}\in\\{-,0\\},\sigma_{0}=0\\}$
$\displaystyle\Delta_{x,-m}^{v}$
$\displaystyle:=\\{v\\}\cup\bigcup_{j=0}^{m}\\{\sigma_{j}x^{(-j)}\ldots\sigma_{m}x^{(-m)}v:\,\sigma_{j},\ldots,\sigma_{m}\in\\{+,0\\},\sigma_{0}=0\\}$
$\displaystyle S_{\varepsilon}$
$\displaystyle:=\\{(i,m,v):i\in\\{1,\ldots,n\\},m\in\mathbb{Z},v\in
FS_{\varepsilon}\text{ and }x_{i}^{(m)}v\in FS_{\varepsilon}\\}$
$\displaystyle\Delta_{\varepsilon}$
$\displaystyle:=\\{1\\}\cup\underset{(i,m,v)\in
S_{\varepsilon}}{\bigcup}\Delta_{x_{i},m}^{v}$

It is easy to see that $\Delta_{\varepsilon}$ is finite and that it contains
$FS_{\varepsilon}$.

The notion of a compatible surjection that we now define, is a sister notion
to that of a diagram that allows for tighter control in falures of equations.
The underlying set of a diagram can be arbitrary and the partial functions
need to be explicitly given, but for compatible surjections (which are tight
to a given equation $\varepsilon$) the undrerlying set has labels inhereted
from $\Delta_{\varepsilon}$ and this is enough infortation to construct the
partial functions. Given an equation $\varepsilon(x_{1},\ldots,x_{l})$ in
intensional form, a _compatible surjection_ for $\varepsilon$ is an onto map
$\varphi:\Delta_{\varepsilon}\rightarrow\mathbb{N}_{q}$, where
$\mathbb{N}_{q}=\\{1,\ldots,q\\}$ has its the natural order (and
$q\leq|\Delta_{\varepsilon}|$), such that:

  * (i)

The relation $g_{i}:=\\{(\varphi(u),\varphi(x_{i}u))\mid
u,x_{i}u\in\Delta_{\varepsilon}\\}$ on $\mathbb{N}_{q}$ is an order-preserving
partial function for all $i\in\\{1,\ldots,l\\}$.

  * (ii)

The relation ${\Yleft}:=\\{(\varphi(v),\varphi(+v))\mid
v,+v\in\Delta_{\varepsilon}\\}\cup\\{(\varphi(-v),\varphi(v))\mid
v,-v\in\Delta_{\varepsilon}\\}$ on $\mathbb{N}_{q}$ is contained in the
covering relation $\prec$ of $\mathbb{N}_{q}$.

  * (iii)

$\varphi(x_{i}^{(m)}u)=g_{i}^{[m]}(\varphi(u))$, when $i\in\\{1,\ldots,l\\}$,
$m\in\mathbb{Z}$ and $u,x_{i}^{(m)}u\in\Delta_{\varepsilon}$.

Note that the first two conditions ensure that
$\mathbf{D}_{\varepsilon,\varphi}:=(\mathbb{N}_{q},{\leq},{\Yleft},g_{1},\ldots,g_{l})$
is a diagram; in (iii), $g_{i}^{[m]}$ is calculated in this diagram. Also, it
follows that the relation $\Yleft$ is an order-preserving partial function. We
say that $\varphi$ is _$n$ -periodic_ with respect to a spacing embedding, if
all $g_{i}$’s are $n$-periodic with respect to that embedding; this is
equivalent to $\mathbf{D}_{\varepsilon,\varphi}$ being $n$-periodic with
respect to that embedding. We say that $\varphi$ is _$n$ -periodic_ if it is
$n$-periodic with respect to some spacing embedding.

We say that the equation $1\leq w_{1}\vee\ldots\vee w_{k}$ in intensional form
_fails_ in a compatible surjection $\varphi$, if
$\varphi(w_{1}),\ldots,\varphi(w_{k})<\varphi(1)$.

We denote by $\mathbf{Pf}(\mathbf{\Delta})^{\pm}$ the expansion of the algebra
$\mathbf{Pf}(\mathbf{\Delta})$ with two distinguished elements $+$ and $-$,
where $+(a)=b$ iff $a\Yleft b$ and $-(a)=b$ iff $b\Yleft a$. Also, every
intensional homomorphism
$\varphi:\mathbf{Ti}\rightarrow\mathbf{Pf}(\mathbf{\Delta})$ extends to a
homomorphism
$\varphi^{\pm}:\mathbf{Ti}^{\pm}\rightarrow\mathbf{Pf}(\mathbf{\Delta})^{\pm}$,
where $\mathbf{Ti}^{\pm}$ is the expansion with the two constants. Likewise,
when $\mathbf{\Omega}$ is an integral chain, we can consider homomorphisms
$\varphi^{\pm}:\mathbf{Ti}^{\pm}\rightarrow\mathbf{F}(\mathbf{\Omega})^{\pm}$,
where $\mathbf{F}(\mathbf{\Omega})^{\pm}$ denotes the expansion of
$\mathbf{F}(\mathbf{\Omega})$ with the functions $+$ and $-$ that give the
upper cover and the lower cover of an element.

######  Theorem 4.1.

If an equation $\varepsilon$ fails in $\mathbf{F}_{n}(\mathbb{Z})$, then it
also fails in some $n$-periodic compatible surjection for $\varepsilon$.

###### Proof.

If $\varepsilon=\varepsilon(x_{1},\ldots,x_{l})$ is an equation in intentional
form $1\leq w_{1}\vee\ldots\vee w_{k}$ that fails in
$\mathbf{F}_{n}(\mathbb{Z})$, then there exists a list
$f=(f_{1},\ldots,f_{l})$ of elements of $\mathbf{F}_{n}(\mathbb{Z})$ and
$p\in\mathbb{Z}$ such that
$w_{1}^{\mathbf{F}_{n}(\mathbb{Z})}(f)(p),\ldots,w_{k}^{\mathbf{F}_{n}(\mathbb{Z})}(f)(p)>p$;
here $f_{i}=\psi(x_{i})$ where
$\psi:\mathbf{Ti}\mathbin{\rightarrow}\mathbf{F}_{n}(\mathbb{Z})$ is the
homomorphism witnessing the failure of $\varepsilon$. We denote by
$\psi^{\pm}:\mathbf{Ti}^{\pm}\mathbin{\rightarrow}\mathbf{F}_{n}(\mathbb{Z})^{\pm}$
the extension of $\psi$. In Theorem 3.6 of [11] it is shown that
$\psi_{p}:\Delta_{\varepsilon}\rightarrow\psi_{p}[\Delta_{\varepsilon}]$ is a
compatible surjection, where the order on $\psi_{p}[\Delta_{\varepsilon}]$ is
inherited from $\mathbb{Z}$ and

$\psi_{p}(u):=\psi^{\pm}(u)(p)=u^{\mathbf{F}_{n}(\mathbb{Z})^{\pm}}(f)(p)$

for $u\in\Delta_{\varepsilon}$. (In [11] the compatible surjection is actually
taken to be the composition of $\psi_{p}$ with the (unique) isomorphism of the
chain $\psi_{p}[\Delta_{\varepsilon}]$ with the initial segment
$\mathbb{N}_{q}$ of $\mathbb{Z}^{+}$, where
$q=|\psi_{p}[\Delta_{\varepsilon}]|$, but we do not need to do that.) To
simplify the notation, we write $u_{fp}$ for
$u^{\mathbf{F}_{n}(\mathbb{Z})^{\pm}}(f)(p)$. Also, in the same theorem of
[11] it is shown that $\varepsilon$ fails in $\psi_{p}$.

We will show that $\psi_{p}$ is $n$-periodic. Suppose
$\psi_{p}(u)\leq\psi_{p}(v)+kn$ for some $u,v\in\Delta_{\varepsilon}$ and
$k\in\mathbb{Z}$, i.e., $u_{f,p}\leq v_{f,p}+kn$. Given that $f_{i}\in
F_{n}(\mathbb{Z})$, we have
$\psi_{p}(x_{i}u)=(x_{i}u)_{f,p}=f_{i}(u_{f,p})\leq
f_{i}(v_{f,p})+kn=(x_{i}v)_{f,p}+kn=\psi_{p}(x_{i}v)$. This shows that all the
partial functions are $n$-periodic with respect to the identity spacing
embedding on $\mathbb{Z}$. ∎

###  4.2 Controlling the automorphisms of $\mathbb{Z}$.

As mentioned before, a key issue with the definition of $n$-periodicity in a
diagram is that it does not provide any control of the spacing embeddings in
$\mathbb{Z}$. The spacing has to do with the fact that some functions $f$ in
$\mathbf{F}_{n}(\mathbb{Z})$ have a big numerical difference $f(m)-m$ between
their input and output values and thus may span multiple periods (this can be
thought of as the _height_ of $f$ as measured at $m$). The lack of control of
these differences translates into lack of control of the spacing embedding $e$
(when moving from a partial function on a diagram to a function of
$\mathbf{F}_{n}(\mathbb{Z})$). Put differently, the problem is not the
numerical size of the set $\Delta$ on which a diagram is based, nor of its
bijective set $e[\Delta]$ in $\mathbb{Z}$, but rather the size of the
convexification of $e[\Delta]$ in $\mathbb{Z}$. We will show that every
function $f$ in $\mathbf{F}_{n}(\mathbb{Z})$ naturally decomposes of into an
automorphism $f^{\circ}\in F_{1}(\mathbb{Z})$ and a _short_ function $f^{*}\in
F_{n}(\mathbb{Z})$, i.e., a function whose height at every point is bounded by
$2n$. In that sense, the height problem is now focused only on the $f^{\circ}$
component of $f$; in this section, we prove results that control the height of
$f^{\circ}$.

The following definition characterizes all the spacing embeddings that
interact well with a c-chain. Given a finite sub c-chain $\mathbf{\Delta}$ of
$\mathbb{Z}$, a spacing embedding
$e:\mathbf{\Delta}\rightarrow(\mathbb{Z},\leq_{\mathbb{Z}},\Yleft_{\mathbb{Z}})$
is said to _transfer $n$-periodicity_ if for every $f\in F_{n}(\mathbb{Z})$,
$(f|_{\Delta\times\Delta})^{e}$, when non-empty, can be extended to an element
of $F_{n}(\mathbb{Z})$; here $f|_{\Delta\times\Delta}$ is the partial function
obtained by restricting both domain and range to $\Delta$ and
$(f|_{\Delta\times\Delta})^{e}$ is its counterpart in $e[\Delta]$. Below we
show that these spacing embeddings, for $n=1$, can be found by solving a
linear system.

A finite subset $\Delta=\\{p_{0},\ldots,p_{l}\\}$ of $\mathbb{Z}$, where
$p_{0}<p_{1}<\ldots<p_{l}$, is called a _solution_ to a system of equations,
if the vector $y_{\Delta}:=(p_{1}-p_{0},\ldots,p_{l}-p_{l-1})$ of spaces
between the points of $\Delta$ is a solution. Also, we say that a spacing
embedding is a _solution_ to a system, if its image is a solution.

######  Lemma 4.2.

If $\Delta=\\{p_{0},\ldots,p_{l}\\}$ is a finite subset of $\mathbb{Z}$, where
$p_{0}<p_{1}<\ldots<p_{l}$, and
$y_{\Delta}:=(p_{1}-p_{0},\ldots,p_{l}-p_{l-1})$, then for every
$j,z,j^{\prime},z^{\prime}\in\\{0,\ldots,l\\}$ with $z\leq j$ and
$z^{\prime}\leq j^{\prime}$, we have
$p_{j}-p_{z}=p_{j^{\prime}}-p_{z^{\prime}}$ iff

$\sum_{k=z+1}^{j}y_{k}-\sum_{k=z^{\prime}+1}^{j^{\prime}}y_{k}=(j^{\prime}-z^{\prime})-(j-z).$

###### Proof.

Note that for $z\leq j$, we have

$p_{j}-p_{z}=\sum_{k=z+1}^{j}(p_{k}-p_{k-1})=\sum_{k=z+1}^{j}(y_{k}+1)=\sum_{k=z+1}^{j}y_{k}+(j-z).$

Therefore, for $z\leq j$ and $z^{\prime}\leq j^{\prime}$ we have:
$p_{j}-p_{z}=p_{j^{\prime}}-p_{z^{\prime}}$ iff

$\displaystyle\sum_{k=z+1}^{j}y_{k}+j-z=$
$\displaystyle\sum_{k=z^{\prime}+1}^{j^{\prime}}y_{k}+j^{\prime}-z^{\prime}\qquad\text{
iff }$
$\displaystyle\sum_{k=z+1}^{j}y_{k}-\sum_{k=z^{\prime}+1}^{j^{\prime}}y_{k}=$
$\displaystyle(j^{\prime}-z^{\prime})-(j-z)\qed$

A system of equations $AY=b$, where $A$ is an $L\times l$ matrix and $Y$ and
$b$ column vectors of size $l$, is said to be _$\Delta$ -bounded_ if $\Delta$
is a solution to the system, $l\leq|\Delta|$, the entries in $b$ are integers
in $[-2|{\Delta}|,2|{\Delta}|]$ and the entries of $A$ are integers in
$\\{-1,0,1\\}$.

The next lemma states that finding all the spacing embedddings that transfer
$1$-periodicity amounts to solving a linear system. We stress that sub
c-chains of $\mathbb{Z}$ are not assumed to be convex.

######  Lemma 4.3.

If $\mathbf{\Delta}$ is a finite sub c-chain of $\mathbb{Z}$, then there
exists a $\Delta$-bounded system of equations such that a spacing embedding
with domain $\mathbf{\Delta}$ is a solution iff it transfers 1-periodicity.

###### Proof.

First consider all the possible non-empty intersections of automorphisms of
$\mathbb{Z}$ with $\Delta\times\Delta$, and note that there are finitely-many
such intersections, say $s$-many; let $f_{1},\dots,f_{s}\in F_{1}(\mathbb{Z})$
be functions realizing these intersections. Since the intersections are
subsets of $\Delta\times\Delta$, we get $s\leq
2^{|\Delta\times\Delta|}=2^{|\Delta|^{2}}$. If
$\Delta=\\{p_{0},\ldots,p_{l}\\}$, where $p_{0}<p_{1}<\ldots<p_{l}$, we set
$y_{j}:=p_{j}-p_{j-1}-1$, for $j\in\\{1,\ldots,,l\\}$ and
$y_{\Delta}:=(y_{1},\ldots,y_{l})$; in particular, if $p_{j-1}\Yleft p_{j}$ we
have $y_{j}=0$. For $z<j$ and for all $i$, if $p_{z^{\prime}}:=f_{i}(p_{z})$
and $p_{j^{\prime}}:=f_{i}(p_{j})$ are in $\Delta$, then
$p_{j}-p_{z}=p_{j^{\prime}}-p_{z^{\prime}}$ since $f_{i}$ is a translation, so
by Lemma 4.2 we get that $(y_{n})$ satisfies the equation:

$\displaystyle\sum_{k=z+1}^{j}Y_{k}-\sum_{k=z^{\prime}+1}^{j^{\prime}}Y_{k}$
$\displaystyle=(j^{\prime}-z^{\prime})-(j-z)$ ($i,z,j$)

We also consider the equations $Y_{k}=0$ for all $k\in\\{1,\ldots,l\\}$ where
$p_{k-1}\Yleft p_{k}$ (capturing the fact that $y_{k}=0$ for these $k$’s). The
resulting finite system, of all $(i,z,j)$-equations and all the $Y_{k}=0$
equations, can be written as $AY=b$, for an $L\times l$ matrix $A$, and column
vectors $Y$ and $b$ of size $l$, where the entries of $A$ are in
$\\{-1,0,1\\}$, the entries of $b$ have absolute value at most $2|\Delta|$,
since they all have the form $(j^{\prime}-z^{\prime})-(j-z)$, and $\Delta$ is
a solution of the system. Therefore, the system is $\Delta$-bounded. Let
$\overline{\cdot}:\Delta\rightarrow{\mathbb{Z}}$ be a spacing embedding.

If $\overline{\Delta}$ is a solution of the system $AY=b$, for each
$i\in\\{1,\ldots,s\\}$, we define the function
$g_{i}:\mathbb{Z}\rightarrow\mathbb{Z}$ by
$g_{i}(x)=x+(\overline{f_{i}(c_{i})}-\overline{c_{i}})$ for all
$x\in\mathbb{Z}$, where $c_{i},f_{i}(c_{i})\in\Delta$; thus $g_{i}\in
F_{1}(\mathbb{Z})$. Note that $g_{i}$ does not depend on the choice of
$c_{i}$: If $k,f_{i}(k)\in\Delta$, then there exist
$j,z,j^{\prime},z^{\prime}\in\\{1,\ldots,l\\}$ such that
$\overline{c_{i}}=\overline{p_{j}}$, $\overline{k}=\overline{p_{z}}$,
$\overline{f_{i}(c_{i})}=\overline{p_{j^{\prime}}}$, and
$\overline{f_{i}(k)}=\overline{p_{z^{\prime}}}$; since $\bar{\Delta}$ is a
solution, $y_{\Delta}$ it satisfies the equation
$(i,\min\\{j,z\\},\max\\{j,z\\})$, which by Lemma 4.2 is equivalent
$\overline{f_{i}(k)}-\overline{f_{i}(c_{i})}=\overline{k}-\overline{c_{i}}$.
Hence,
$g_{i}(\overline{k})=\overline{k}+(\overline{f_{i}(c_{i})}-\overline{c_{i}})=\overline{f_{i}(k)}$,
for all $k$ such that $k,f_{i}(k)\in\Delta$. As a result, the restriction of
$g_{i}$ to $\overline{\Delta}$ is equal to the counterpart of
$f_{i}|_{\Delta\times\Delta}$ in $\overline{\Delta}$.

Conversely, if $\overline{\cdot}:\Delta\rightarrow{\mathbb{Z}}$ transfers
1-periodicity, for every $i\in\\{1,\dots,s\\}$ the counterpart of
${f_{i}}|_{\Delta\times\Delta}$ by $\overline{\cdot}$ can be extended to a
function in $F_{1}(\mathbb{Z})$, i.e., for all $p_{j},p_{z}\in\Delta$ such
that $p_{j^{\prime}}:=f_{i}(p_{j}),p_{z^{\prime}}:=f_{i}(p_{z})\in\Delta$, we
have that
$\overline{p_{j}}-\overline{p_{z}}=\overline{f_{i}(p_{j})}-\overline{f_{i}(p_{z})}$.
Hence,
$\sum_{k=z+1}^{j}\overline{y_{k}}-\sum_{k=z^{\prime}+1}^{j^{\prime}}\overline{y_{k}}=(j^{\prime}-z^{\prime})-(j-z)$
by Lemma 4.2, so if $z<j$, then $\overline{\Delta}$ satisfies the equation
$(i,z,j)$. Since this is true for all $i\in\\{1,\ldots,s\\}$,
$\overline{\cdot}$ preserves coverings and $j,z\in
Dom({f_{i}}|_{\Delta\times\Delta})$, we have that $\overline{\Delta}$
satisfies $Ax=b$. ∎

The following theorems will help us guarantee the existence of small solutions
for $\Delta$-bounded systems of equations.

######  Theorem 4.4.

[2] Let $Ay=b$ be a system of $M\times l$ linear equations with integer
coefficients. Assume the rows of $A$ are linearly independent (hence $M\leq
l$) and denote by $\gamma^{\prime}$ (respectively $\gamma$) the maximum of the
absolute values of the $M\times M$ minors of the matrix $A$ (the augmented
matrix $(A|b)$). If the system has a solution in non-negative integers, then
the system has a solution $(y_{k})$ in the non-negative integers with
$y_{k}\leq\gamma^{\prime}$ for $l-M$ variables and $y_{i}\leq(l-M+1)\gamma$
for $M$ variables.

Given that $l-M+1\geq 1$ and $\gamma^{\prime}\leq\gamma$ we obtain the
following corollary.

######  Corollary 4.5.

Let $Ay=b$ be a system of $M\times l$ linear equations with integer
coefficients. Assume the rows of $A$ are linearly independent, and denote by
$\gamma$ the maximum of the absolute values of the $M\times M$ minors of the
augmented matrix $(A|b)$. If the system has a solution in non-negative
integers, then the system has a solution $(y_{k})$ in non-negative integers
with $y_{k}\leq(l-M+1)\gamma$ for all $k$.

Using these corollaries and Lemma 4.3, we will prove that for every sub
c-chain of $\mathbb{Z}$, there exists a spacing embedding of bounded height
that transfers 1-periodicity. For convenience, we define
$\rho(a):=2a^{3}a!+a+1$, for $a\in\mathbb{Z}^{+}$.

######  Lemma 4.6.

Given a finite sub c-chain $\mathbf{\Delta}$ of $\mathbb{Z}$, there exists a
spacing embedding with domain $\Delta$ that transfers 1-periodicity and that
has height at most $\rho(|\Delta|)$.

###### Proof.

By Lemma 4.3, there exists a $\Delta$-bounded system of equations $AY=b$
satisfying the conditions of the lemma. Since the system $Ay=b$ is
$\Delta$-bounded, $\Delta$ is a solution for it, hence the system is
consistent. It follows, say by Theorem 2.38 of [16], that $rank(A)=rank(A|b)$.
So we can select a maximal collection of linearly independent rows of $(A|b)$
to obtain an equivalent (sub)system $A^{\prime}y=b^{\prime}$ where
$rank(A|b)=rank(A^{\prime}|b^{\prime})=rank(A^{\prime})$, hence all the rows
are linearly independent. Therefore, $A^{\prime}$ has dimensions $M\times l$
where $M\leq l$. Also, since $y_{\Delta}$ is a solution (in the non-negative
integers) of $Ay=b$, it is also a solution of the equivalent system
$A^{\prime}y=b^{\prime}$.

Observe that if $C=(c_{i,j})$ is an $M\times M$ submatrix of
$(A^{\prime}|b^{\prime})$, then

$|det(C)|=|\sum_{\sigma\in S_{M}}sgn(\sigma)c_{\sigma(1),1}\cdot\ldots\cdot
c_{\sigma(M),M}|\leq\sum_{\sigma\in
S_{M}}|c_{\sigma(1),1}|\cdot\ldots\cdot|c_{\sigma(M),M}|$

Since $Ax=b$ is $\Delta$-bounded, all columns of $(A^{\prime},b^{\prime})$,
aside from the last column which equals $b^{\prime}$, have entries among
$-1,0,1$. Therefore, for all $\sigma\in S_{M}$, we have $|c_{\sigma(i),i}|\leq
1$ for $i\neq M$ and $|c_{\sigma(M),M}|\leq 2|{\Delta}|$, since the entries of
$b$ are integers in $[-2|{\Delta}|,2|{\Delta}|]$ (again because of
$\Delta$-boundedness). So

$|det(C)|\leq\sum_{\sigma\in
S_{M}}|c_{\sigma(1),1}|\cdot\ldots\cdot|c_{\sigma(M),M}|\leq\sum_{\sigma\in
S_{M}}|c_{\sigma(M),M}|\leq M!\cdot 2|\Delta|$

Therefore, if $\gamma$ is the maximum of the absolute values of the $M\times
M$ minors of the augmented matrix $(A^{\prime}|b^{\prime})$, then $\gamma\leq
M!\cdot 2|\Delta|\leq l!\cdot 2|\Delta|\leq(|\Delta|)!\cdot 2|\Delta|$, where
we used that $l\leq|\Delta|$ due to $\Delta$-boundedness. Also $l-M+1\leq
l\leq|\Delta|$. So, by Corollary 4.5, there exists a solution $(y_{k})$ in the
non-negative integers with $y_{k}\leq(|\Delta|)!\cdot 2|\Delta|^{2}$ for all
$k$.

Using the solution $(y_{k})$, we define the map
$\overline{\cdot}:\Delta\rightarrow\mathbb{Z}$ by setting $\overline{p_{0}}=0$
and $\overline{p_{i}}:=i+\sum^{i}_{j=1}y_{j}$, for all $i\in\\{1,\ldots,l\\}$;
so $\overline{\Delta}=\\{\overline{p_{0}},\ldots,\overline{p_{l}}\\}$. The map
$\overline{\cdot}$ is order preserving, because the solution $(y_{k})$ has
non-negative entries, and it preserves $\Yleft$, since every zero entry in
$y_{\Delta}$ implies that the same entry is zero in $y_{\bar{\Delta}}$. Also,
observe that $y_{\bar{\Delta}}=(y_{k})$, hence $\overline{\cdot}$ is a
solution of $A^{\prime}x=b^{\prime}$, thus also of $Ax=b$. Therefore,
$\overline{\cdot}$ is a spacing embedding that is a solution of $Ax=b$. Since
we took $Ax=b$ to be the system given by Lemma 4.3, by that lemma it follows
that $\overline{\cdot}$ transfers $1$-periodicity.

Since $y_{k}\leq(|\Delta|)!\cdot 2|\Delta|^{2}$ for all $k$, the height of
$\overline{\cdot}$ is $1+\overline{p_{i}}=1+l+\sum^{i}_{j=1}y_{j}\leq
1+l+l((|\Delta|)!\cdot 2|\Delta|^{2})\leq 1+|\Delta|+|\Delta|((|\Delta|)!\cdot
2|\Delta|^{2})=1+|\Delta|+(|\Delta|)!\cdot 2|\Delta|^{3}$, hence the height is
bounded by $\rho(|\Delta|)$. ∎

###  4.3 From $\mathbf{F}_{n}(\mathbb{Z})$ to a short $n$-periodic compatible
surjection.

We will describe the decomposition of functions
$f\in\mathbf{F}_{n}(\mathbb{Z})$ into functions of
$\mathbf{F}_{1}(\mathbb{Z})$ and short functions of
$\mathbf{F}_{n}(\mathbb{Z})$, and combine it with the results of the previous
section to ensure that for any $n$-periodic diagram there is a short spacing
embedding witnessing the $n$-periodicity.

A spacing embedding $e:\mathbf{\Delta}\rightarrow\mathbb{Z}$ over a c-chain
$\mathbf{\Delta}$ is called _$n$ -short_ if its height is at most
$\nu(|\Delta|)$, where $\nu(a)=(\rho(3a)+1)n$ for all $a\in\mathbb{Z}^{+}$.
(As always we assume that images of spacing embeddings are non-negative and
include $0$). Recall that for a fixed $n\in\mathbb{Z}^{+}$, for every
$x\in\mathbb{Z}$, $Rx$ denotes the remainder and $Qx$ the quotient of dividing
$x$ by $n$, while $Sx:=x-Rx=nQx$.

Given $g\in F_{1}(\mathbb{Z})$ and $h\in F_{n}(\mathbb{Z})$, we have $g,h\in
F_{n}(\mathbb{Z})$ so $g\circ h\in F_{n}(\mathbb{Z})$. Conversely, for $f\in
F_{n}(\mathbb{Z})$, we define $f^{\circ}(x):=x+Sf(0)$ and
$f^{*}(x):=f(x)-Sf(0)$, for all $x\in\mathbb{Z}$. In the following lemmas we
will make use of the fact that for all $g\in F_{1}(\mathbb{Z})$ and
$x\in\mathbb{Z}$, we have $g(x)=g(x-k)+k$ for all $k\in\mathbb{Z}$, and in
particular $g(x)=x+g(0)$.

######  Lemma 4.7.

The maps $f\mapsto(f^{\circ},f^{*})$ and $(f^{\circ},f^{*})\mapsto
f^{\circ}\circ f^{*}$ define a bijection between $F_{n}(\mathbb{Z})$ and the
set of pairs $f^{\circ}\in F_{1}(\mathbb{Z})$ and $f^{*}\in F_{n}(\mathbb{Z})$
with $Sf^{\circ}(0)=f^{\circ}(0)$ and $0\leq f^{*}(0)<n$.

###### Proof.

For $f\in F_{n}(\mathbb{Z})$, we have $f^{\circ}(x):=x+Sf(0)$ and
$f^{*}(x):=f(x)-Sf(0)$ for all $x\in\mathbb{Z}$, so $f^{\circ}\in
F_{1}(\mathbb{Z})$, $f^{*}\in F_{n}(\mathbb{Z})$,
$Sf^{\circ}(0)=S(Sf(0))=Sf(0)=f^{\circ}(0)$ and $0\leq f^{*}(0)=f(0)-Sf(0)<n$.
So the map $f\mapsto(f^{\circ},f^{*})$ indeed maps to suitable pairs.

Given $f\in F_{n}(\mathbb{Z})$, we have $(f^{\circ}\circ
f^{*})(x)=f^{\circ}(f(x)-Sf(0))=f(x)-Sf(0)+Sf(0)=f(x)$. So, the two maps
compose to the identity, one way.

Conversely, if $g\in F_{1}(\mathbb{Z})$, $h\in F_{n}(\mathbb{Z})$,
$Sg(0)=g(0)$, and $0\leq h(0)<n$, then
$S(gh(0))=S(h(0)+g(0))=S(h(0)+Sg(0))=S(g(0))=g(0)$. Therefore, $(g\circ
h)^{\circ}(x)=x+S(gh(0))=x+g(0)=g(x)$ and $(g\circ
h)^{*}(x)=gh(x)-S(gh(0))=h(x)+g(0)-g(0)=h(x)$. ∎

Lemma 4.6 provides spacing embeddings (of controlled height) that transfer
$1$-periodicity. Using that result and the decomposition of Lemma 4.7, we will
construct spacing embeddings (of controlled height) that transfer
$n$-periodicity, for any given $n$.

######  Example 4.8.

We will demonstrate the idea of how, given a sub c-chain of $\mathbb{Z}$ based
on $\Delta=\\{0,4\\}$, we can obtain a spacing embedding $e$ with domain
$\Delta$ that transfers $n$-periodicity. In other words, we will construct $e$
such that given any function $f$ of $F_{n}(\mathbb{Z})$, the partial function
$(f|_{\Delta\times\Delta})^{e}$ is extendable to an $n$-periodic function on
$\mathbb{Z}$.

We first decompose $f$ as $f=f^{\circ}\circ f^{*}$, where $f^{\circ}\in
F_{1}(\mathbb{Z})$ and $f^{*}\in F_{n}(\mathbb{Z})$ with
$Sf^{\circ}(0)=f^{\circ}(0)$ and $0\leq f^{*}(0)<n$, according to Lemma 4.7;
Figure 2 shows an example of that. We will keep $f^{*}$ as it is, but we will
obtain an improved version of $f^{\circ}$ and compose it back with $f^{*}$.

We will first view $f^{\circ}$ as providing us information about only the
multiples of $n$—i.e., only about the subset $n\mathbb{Z}$ of $\mathbb{Z}$—and
we will scale $n\mathbb{Z}$ into a copy of $\mathbb{Z}$. Since
$f^{\circ}(0)=Sf^{\circ}(0)$, we have $f^{\circ}(0)=kn$ for some
$k\in\mathbb{Z}$, hence $f^{\circ}(x)=x+kn$, for all $x\in\mathbb{Z}$; i.e.,
$f^{\circ}$ is the translation by $kn$. By dividing $kn$ by $n$, we consider
the function $f^{\circ}\div n$ that translates by $k$, i.e., $f^{\circ}\div
n:\mathbb{Z}\rightarrow\mathbb{Z}$ is given by $(f^{\circ}\div n)(x)=x+k$ for
all $x\in\mathbb{Z}$; we set $g:=f^{\circ}\div n$ for brevity. The function
$f^{\circ}\div n$ captures the behavior of $f^{\circ}$ on the first elements
of the periods (the multiples of $n$), and it scales $n\mathbb{Z}$ into a copy
of $\mathbb{Z}$. We will apply Lemma 4.6 to this scaled function.

We define the set $\widetilde{\Delta}=\\{Qx:x\in\Delta\\}=\\{0,2\\}$ and
recall that Lemma 4.6 produces a spacing embedding
$d:\tilde{\Delta}\rightarrow\mathbb{Z}$ that transfers 1-periodicity and has
bounded height. So, $(g|_{\tilde{\Delta}\times\tilde{\Delta}})^{d}$ can be
extended to a function $g_{\tilde{\Delta},d}:\mathbb{Z}\rightarrow\mathbb{Z}$
that is $1$-periodic; say $g_{\tilde{\Delta},d}(x)=x+\ell$ for all
$x\in\mathbb{Z}$, for some $\ell\in\mathbb{Z}$. By Lemma 4.6, the height is
controlled in terms of the convexification of $d[\tilde{\Delta}]$.

We now scale this improved function $g_{\tilde{\Delta},d}$ back: we view the
domain $\mathbb{Z}$ of $g_{\tilde{\Delta},d}$ as a copy of the multiples of
$n$, and we move from this subset $n\mathbb{Z}$ to all of $\mathbb{Z}$. We
define the function $g_{\tilde{\Delta},d}\times
n:\mathbb{Z}\rightarrow\mathbb{Z}$ by $(g_{\widetilde{\Delta},d}\times
n)(x)=x+n\ell$ for all $x\in\mathbb{Z}$.

By composing $g_{\tilde{\Delta},d}\times n$ with $f^{*}$, we obtain a shorter
version of $f$. We claim that $e(x)=d(Qx)n+Rx$, for all $x\in\Delta$, defines
the desired spacing embedding and that
$f_{\Delta,e}:=(g_{\tilde{\Delta},d}\times n)\circ f^{*}$ is an $n$-periodic
function extending $(f|_{\Delta\times\Delta})^{e}$; see Figure 2. This is the
general process we follow in the proof of the next lemma; for technical
reasons the c-chain $\widetilde{\Delta}$ will need to be suitably larger, as
we will see in the argument.

$7$$7$$6$$6$$5$$5$$4$$4$$3$$3$$2$$2$$1$$1$$0$$0$$\vdots$$\vdots$$\vdots$$\vdots$$f$

$7$$7$$6$$6$$5$$5$$4$$4$$3$$3$$2$$2$$1$$1$$0$$0$$\vdots$$\vdots$$\vdots$$\vdots$$f^{*}$

$7$$7$$6$$6$$5$$5$$4$$4$$3$$3$$2$$2$$1$$1$$0$$0$$\vdots$$\vdots$$\vdots$$\vdots$$f^{\circ}$

$3$$3$$2$$2$$1$$1$$0$$0$$\vdots$$\vdots$$\vdots$$\vdots$$f^{\circ}\div n$

$3$$3$$2$$2$$1$$1$$0$$0$$\vdots$$\vdots$$\vdots$$\vdots$$g_{\tilde{\Delta},d}$

$7$$7$$6$$6$$5$$5$$4$$4$$3$$3$$2$$2$$1$$1$$0$$0$$\vdots$$\vdots$$\vdots$$\vdots$$g_{\tilde{\Delta},d}\times
n$

$7$$7$$6$$6$$5$$5$$4$$4$$3$$3$$2$$2$$1$$1$$0$$0$$\vdots$$\vdots$$\vdots$$\vdots$$f_{\Delta,e}$

Figure 2:  Shortening an element of $\mathbf{F}_{n}(\mathbb{Z})$

######  Lemma 4.9.

Given a finite sub c-chain $\mathbf{\Delta}$ of $\mathbb{Z}$, there exists an
$n$-short spacing embedding with domain $\mathbf{\Delta}$ that transfers
$n$-periodicity.

###### Proof.

For
$\widetilde{\Delta}:=\\{Qx:x\in\Delta\\}\cup\\{Qx+1:x\in\Delta\\}\cup\\{Qx-1:x\in\Delta\\}$
we have $|\widetilde{\Delta}|\leq 3|\Delta|$; let
$\widetilde{\mathbf{\Delta}}$ be the sub-chain of $\mathbb{Z}$ with base set
$\widetilde{\Delta}$. By Lemma 4.6, there exists a spacing embedding
$\overline{\cdot}:\widetilde{\Delta}\rightarrow\mathbb{Z}$ that transfers
$1$-periodicity and has height at most $\rho(|\widetilde{\Delta}|)$. Let
$e:\Delta\rightarrow\mathbb{Z}$ be given by $e(x)=\overline{Qx}n+Rx$, for all
$x\in\Delta$. Observe that
$\max(e[\Delta])\leq(\rho(|\widetilde{\Delta}|)+1)n\leq(\rho(3|{\Delta}|)+1)n=\nu(|{\Delta}|)$;
hence $e$ is $n$-short. We will show that $e$ transfers $n$-periodicity.

If $f\in F_{n}(\mathbb{Z})$ and $f|_{\Delta\times\Delta}$ is non-empty, by
Lemma 4.7 there exist $f^{\circ}\in F_{1}(\mathbb{Z})$ and $f^{*}\in
F_{n}(\mathbb{Z})$ with $0<f^{*}(0)\leq n$, $Sf^{\circ}(0)=f^{\circ}(0)$, and
$f=f^{\circ}\circ f^{*}$. Using the $n$-periodicity of $f^{*}$ and that
$f^{\circ}(a)=f^{\circ}(0)+a$, for all $a$, we obtain $f(x)=(f^{\circ}\circ
f^{*})(Sx+Rx)=f^{\circ}(0)+f^{*}(Sx+Rx)=f^{\circ}(0)+Sx+f^{*}(Rx)=f^{\circ}(Sx)+f^{*}(Rx)$.
Since
$f^{\circ}(Sx)=Sx+f^{\circ}(0)=Sx+Sf^{\circ}(0)=S(x+f^{\circ}(0))=Sf^{\circ}(Sx)$,
we get that $f^{\circ}(Sx)$ is a multiple of $n$, so $Sf(x)=f^{\circ}(Sx)$ or
$Sf(x)=f^{\circ}(Sx)+n$, depending on whether $f^{*}(Rx)$ is smaller or bigger
than $n$; note that indeed $f^{*}(Rx)\in[0,2n)_{\mathbb{Z}}$, since $0\leq
Rx<0+n$ implies $0\leq f^{*}(0)\leq f^{*}(Rx)<f^{*}(0)+n<n+n=2n$, by
$n$-periodicity. Therefore, $f^{\circ}(Sx)=Sf(x)=n\cdot Qf(x)$ or
$f^{\circ}(Sx)=Sf(x)-n=n\cdot Qf(x)-n$; hence $Qf^{\circ}(Sx)=Qf(x)$ or
$Qf^{\circ}(Sx)=Qf(x)-1$. In either case, if $x,f(x)\in\Delta$, then
$Qx,Qf^{\circ}(Sx)\in\widetilde{\Delta}$.

We define the function $g$ on $\mathbb{Z}$, by $g(a)=Qf^{\circ}(an)$, for all
$a\in\mathbb{Z}$; note that $g(Qx)=Qf^{\circ}(Sx)$, for all $x\in\mathbb{Z}$
(denoted by $f^{\circ}\div n$ in the Example 4.8). Observe that if
$x,f(x)\in\Delta$, then $Qx,g(Qx)\in\widetilde{\Delta}$; hence, since
$f|_{\Delta\times\Delta}$ is non-empty so is
$g|_{\widetilde{\Delta}\times\widetilde{\Delta}}$. Since
$\overline{\cdot}:\widetilde{\Delta}\rightarrow\mathbb{Z}$ transfers
$1$-periodicity, the counterpart of
$g|_{\widetilde{\Delta}\times\widetilde{\Delta}}$ by $\overline{\cdot}$ can be
extended to some $h\in F_{1}(\mathbb{Z})$. We further define the function
$k\in F_{1}(\mathbb{Z})$ given by $k(x)=h(0)n+x$ (denoted by $h\times n$ in
the Example 4.8).

Note that $k\circ f^{*}\in F_{n}(\mathbb{Z})$; we will show now that $k\circ
f^{*}$ extends the counterpart of $f|_{\Delta\times\Delta}$ by $e$. Assume
that we have $x,f(x)\in\Delta$. We first show that
$ef(x)=\overline{Qf^{\circ}(Sx)}n+f^{*}(Rx)$, i.e.,
$e(f^{\circ}(Sx)+f^{*}(Rx))=\overline{Qf^{\circ}(Sx)}n+f^{*}(Rx)$. When $0\leq
f^{*}(Rx)<n$, then $R(f^{\circ}(Sx)+f^{*}(Rx))=Rf^{*}(Rx)=f^{*}(Rx)$ and
$Q(f^{\circ}(Sx)+f^{*}(Rx))=Qf^{\circ}(Sx)$, so the equation holds. If $n\leq
f^{*}(Rx)<2n$, then $0\leq f^{*}(Rx)-n<n$, so
$R(f^{\circ}(Sx)+f^{*}(Rx))=f^{*}(Rx)-n$ and
$\overline{Q(f^{\circ}(Sx)+f^{*}(Rx))}=\overline{Qf^{\circ}(Sx)+1}=\overline{Qf^{\circ}(Sx)}+1$,
since $\overline{\cdot}$ preseves coverings, so the equation holds in this
case, as well. Therefore,
$e{f(x)}=e(f^{\circ}(Sx)+f^{*}(Rx))=\overline{Q{f^{\circ}(Sx)}}n+f^{*}(Rx)=\overline{g(Qx)}n+f^{*}(Rx)=h(\overline{Qx})n+f^{*}(Rx)=h(0)n+\overline{Qx}n+f^{*}(Rx)=k(0)+\overline{Qx}n+f^{*}(Rx)=k(\overline{Qx}n+f^{*}(Rx))=kf^{*}(\overline{Qx}n+Rx)=kf^{*}(ex)$.
∎

######  Lemma 4.10.

Every $n$-periodic compatible surjection (with respect to some spacing
embedding) is $n$-periodic with respect to an $n$-short spacing embedding.

###### Proof.

If $\varphi:\Delta_{\varepsilon}\rightarrow\mathbb{N}_{d}$ is an $n$-periodic
compatible surjection for some equation $\varepsilon(x_{1},\ldots,x_{l})$,
there exists a spacing embedding $e:\mathbb{N}_{d}\rightarrow\mathbb{Z}$ such
that the partial functions $g_{1},\ldots,g_{l}$ given by $\varphi$ are
$n$-periodic respect to $e$. Hence, each counterpart $g_{i}^{e}$ is a partial
function on $e[\mathbb{N}_{d}]\subseteq\mathbb{Z}$ that is $n$-periodic with
respect to $id_{\mathbb{Z}}$, and by Lemma 3.3 can be extended to a function
in $F_{n}(\mathbb{Z})$. By Lemma 4.9, there exists an $n$-short spacing
embedding $e^{\prime}:e[\mathbb{N}_{d}]\rightarrow\mathbb{Z}$ that transfers
$n$-periodicity, so $e^{\prime}\circ e:\mathbb{N}_{d}\rightarrow\mathbb{Z}$ is
an $n$-short spacing embedding (since it has the same image as $e^{\prime}$,
which is $n$-short) and each $g_{i}$ has an $n$-periodic counterpart by
$e^{\prime}\circ e$ (since $e^{\prime}$ transfers $n$-periodicity). Hence,
$\varphi$ is $n$-periodic with respect to the $n$-short spacing embedding
$e^{\prime}\circ e$. ∎

###  4.4 Decidability.

Finally, we are ready obtain decidability results for
$\mathsf{V}(\mathbf{F}_{n}(\mathbb{Z}))$ and $\mathsf{DLP}$.

######  Lemma 4.11.

An equation fails in $\mathbf{F}_{n}(\mathbb{Z})$ iff it fails in an
$n$-short, $n$-periodic compatible surjection.

###### Proof.

Suppose than an equation $\varepsilon$ fails in $\mathbf{F}_{n}(\mathbb{Z})$,
then by Theorem 4.1, there exists an $n$-periodic compatible surjection
$\varphi$ in which $\varepsilon$ fails. By Lemma 4.10, there exists an
$n$-short spacing embedding with respect to which $\varphi$ is also
$n$-periodic. Hence $\varepsilon$ fails in an $n$-short, $n$-periodic
compatible surjection. The converse follows from Lemma 3.7. ∎

######  Theorem 4.12.

The equational theory of the variety $\mathsf{V}(\mathbf{F}_{n}(\mathbb{Z}))$
is decidable.

###### Proof.

An equation $\varepsilon$ fails in $\mathsf{V}(\mathbf{F}_{n}(\mathbb{Z}))$
iff it fails in $\mathbf{F}_{n}(\mathbb{Z})$ iff (by Theorem 4.11)
$\varepsilon$ fails in an $n$-short, $n$-periodic compatible surjection. There
exist finitely many compatible surjections with domain $\Delta_{\varepsilon}$
(since all of them have a range of the form $\mathbb{N}_{q}$, where
$q\leq|\Delta_{\varepsilon}|$). Also, for each such compatible surjection,
there are finitely many $n$-short spacing embeddings under which the
compatible surjection is $n$-periodic, as the image of each $n$-short spacing
embedding is contained in $\mathbb{N}_{d}$, where $d\leq\nu(q)$. Therefore, by
checking all of these finitely-many situations we obtain an algorithm that
decides every equation. ∎

Theorem 4.12 and Theorem 3.8 yield the following result, which provides a
proof of the decidability of $\mathsf{DLP}$ that is different to the one given
in [11].

######  Corollary 4.13.

The equational theory of the variety $\mathsf{DLP}$ is decidable.

##  5 Generation and decidability for $\mathsf{LP_{n}}$.

In this section we will prove that, for all $n$,
$\mathsf{LP_{n}}=\mathsf{V}(\mathbf{F}_{n}(\mathbb{Q}\overrightarrow{\times}\mathbb{Z}))$
and that the equational theory of $\mathsf{LP_{n}}$ is decidable. A lot of the
detailed work we did in the previous sections will come in handy.

As the failure of an equation in an ($n$-periodic) diagram corresponds to the
failure in $\mathbf{F}_{n}(\mathbb{Z})$ and the latter does not generate
$\mathsf{LP_{n}}$, a new notion of diagram is required for
$\mathbf{F}_{n}(\mathbf{J}\overrightarrow{\times}\mathbb{Z})$, capturing the
natural partiction induced by the lexicographic product ordering on the chain.
For $\Delta\subseteq J\times\mathbb{Z}$, where $J$ is a set, we define the
equivalence relation $\equiv$ on $\Delta$ by $(i_{1},x)\equiv(i_{2},y)$ iff
$i_{1}=i_{2}$; note that generalizes to subsets the equivalence relation we
defined on $J\times\mathbb{Z}$ in Section 2.3.

A _partition diagram_ consists of a diagram of the form
$(\mathbf{J\overrightarrow{\times}\Delta},\Yleft,g_{1},\ldots,g_{s})$, where
$\mathbf{J}$ is a chain and $\mathbf{\Delta}$ is a finite subchain of
$\mathbb{Z}$ such that $x\Yleft y\Rightarrow x\equiv y$ and $x\equiv y$ iff
$g_{i}(x)\equiv g_{i}(y)$, for all $i\in\\{1,\ldots,s\\}$ and $x,y\in
Dom(g_{i})$, together with the exact partition induced by $\mathbf{J}$ and
$\mathbf{\Delta}$; so if $\mathbf{J\overrightarrow{\times}\Delta}$ is
partitioned differently then we get a different partition diagram. For each
partial function $g$ of the diagram we define the partial function
$\widetilde{g}:J\rightarrow J$ where $\widetilde{g}(j)=k$ iff there exist
$x,y\in\mathbb{Z}$ such that $(j,x)\in Dom(g)$ and $g(j,x)=(k,y)$. Note that
that $\widetilde{g}$ is well-defined because if $g(j,x_{1})=(k_{1},y_{1})$ and
$g(j,x_{2})=(k_{2},y_{2})$, then $(j,x_{1})\equiv(j,x_{2})$ implies
$(k_{1},y_{1})=g(j,x_{1})\equiv g(j,x_{2})=(k_{2},y_{2})$, hence
$k_{1}=k_{2}$; moreover, $\widetilde{g}$ is one-to-one. We also define
$\overline{g_{j}}:\Delta\rightarrow\\{j\\}\times\Delta\stackrel{{\scriptstyle
g}}{{\rightarrow}}\\{\tilde{g}(j)\\}\times\Delta\rightarrow\Delta$, for every
$j\in J$, where the first and last maps are the obvious bijections. We say
that an equation _fails_ in a partition diagram, if it fails in the underlying
diagram.

A partition diagram
$(\mathbf{J}\overrightarrow{\times}\mathbf{\Delta},\Yleft,g_{1},\ldots,g_{s})$
is said to be _$n$ -periodic_ if there exists a spacing embedding $e$ on
$\mathbf{\Delta}$ such that $\overline{g}_{j}$ is $n$-periodic with respect to
$e$, for all $j\in J$ and $g\in\\{g_{1},\ldots,g_{s}\\}$. A $n$-periodic
partition diagram is said to be _$n$ -short_ if the spacing embedding