\section{Introduction}
Given two equivalence relations $R, S$ on the set $\omega$ of natural
numbers, we say that $R$ is \emph{computably reducible to $S$}  (or, simply,
$R$ is \emph{reducible to $S$}; notation: $R \leq S$) if there exists a
computable function $f$ such that, for every $x,y \in \omega$,
\[
x \rel{R} y \Leftrightarrow f(x) \rel{S} f(y).
\]
The first systematic study of this reducibility on equivalence relations is
implicit in  Ershov~\cite{Ershov:NumberingsI, Ershov:NumberingsII}. Recently
this reducibility has been successfully applied to classify natural problems
arising in mathematics and computability theory: see for instance
in~\cite{Coskey-Hamkins-Miller, Fokina-Friedman-Nies, Fokina-et-al-several}.

In classifying objects according to their relative complexity, an important
role is played by objects that are universal, or complete, with respect to
some given class. We are interested in this notion for the case of
equivalence relations on $\omega$.

\begin{defn}
Let $\mathcal{A}$ be a class of equivalence relations. An equivalence
relation $R\in \mathcal A$  is called \emph{$\mathcal{A}$-universal}, (also
sometimes called $\mathcal{A}$-complete) if  $S \leq R$ for every $S \in
\mathcal{A}$.
\end{defn}
For instance, by~Fokina  et al.~\cite{Fokina-et-al-several}  the isomorphism
relation for various familiar classes of computable structures is
$\Sigma^1_1$-universal, and by~Fokina,  Friedman and Nies
\cite{Fokina-Friedman-Nies} the relation of computable isomorphism of c.e.\
sets is $\Sigma^0_3$-universal. Ianovski et al.\
\cite[Theorem~3.5]{Ianovski-et-al} provide a natural example  of a
$\Pi^0_1$-universal equivalence relation, namely equality of unary quadratic
time computable functions. In contrast, they show
\cite[Corollary~3.8]{Ianovski-et-al} that there is no $\Pi^0_n$-universal
equivalence relation for $n>1$.

In this paper we are interested in $\Sigma^{0}_{1}$-universal and in
$\Pi^{0}_{1}$-universal equivalence relations arising from group theory. They
arise naturally via word problems, if we view the word problem of a group as
the  equivalence relation that holds for two terms if they denote the same
group element.

In  Theorem~\ref{thm:main1}  we will build  a finitely presented group  with
a word problem as follows: each pair of distinct equivalence classes is  effectively
inseparable in a uniform way. Since this property for ceers implies
 $\Sigma^0_1$-universality (see \cite{ceers}), it follows that the word problem is
$\Sigma^0_1$-universal.

Finitely generated (f.g.) groups of computable permutations are special cases
of f.g. groups with a co-c.e. set of relators. The word problem of any
finitely generated (f.g.) group of computable permutations is $\Pi^0_1$.
Using the  theory of numberings, Morozov~\cite{morozov2000once} built an
example of a  f.g.\ group with $\Pi^0_1$ word problem  that  is not
isomorphic to  a f.g.\  group of computable permutations. (We conjecture that
future research might provide a natural example of such a group, generated
for instance by finitely many computable isometries of the Urysohn space.) As
our second main result, in Theorem~\ref{thm:main2} we will   build   a f.g.\
group of computable permutations  with a $\Pi^{0}_{1}$-universal word
problem. Thus, within the groups that have a $\Pi^0_1$ word problem, the
maximum complexity of the word problem is already assumed  within the
restricted class of f.g.\ groups of computable permutations. By varying the
methods, in Theorem~\ref{th:truth table} we show that every c.e.\ truth-table
degree contains the word problem of a 3-generated group of computable
permutations.

We include a number of open questions. Is the computably enumerable equivalence
relation of isomorphism among
finitely presented groups recursively isomorphic to equivalence of
sentences under Peano arithmetic?  What is the complexity of embedding and
isomorphism among f.g.\ groups of (primitive) recursive permutations? A
natural guess would be $\Sigma^0_3$ -universality.

\section{Background and preliminaries}
\subsection*{Group theory}
Group theoretic terminology and notations are standard, and can be found for
instance in \cite{Kargapolov-Merzljakov:Book}. Throughout let $F(X)$ be the
free group on $X$, consisting of all reduced words of letters from $X \cup
X^{-1}$, with binary operation induced by concatenation and cancellation of
$x$ with $x^{-1}$, and the empty string as identity; see
\cite[p.89]{Kargapolov-Merzljakov:Book} for notations and details. It is
customary to write $F(x_1, \ldots, x_k)$ if $X=\{x_1, \ldots, x_k\}$ is
finite. The symbol $\cong$ denotes isomorphism of groups, and, for a group
$H$ and a set $S \subseteq H$, by $\Ncl_{H}(S) $ one denotes the normal
closure of $S$ in $H$; if $H$ is clear from the context one writes $\Ncl(S)$.
A~\emph{presentation} of a group $G$ is a pair $\langle X; R\rangle$  with
$R\subseteq F(X)$ such that $G\cong {F(X)}{/\Ncl_{F(X)}(R)}$. It is
legitimate to write $G=\langle X; R\rangle$ since the presentation identifies
$G$ up to group isomorphism. The congruence corresponding to the normal
subgroup $\Ncl_{F(X)}(R)$ will be written as $=_{G}$; the relation $=_{G}$ is
clearly an equivalence relation on $F(X)$, which we will call the \emph{word
problem} of $G=\langle X; R \rangle$; the $=_{G}$-equivalence
class of an element $x$ will be denoted by $[x]_{G}$. If $X$ is a finite set then we can
encode the elements of $F(X)$ by natural numbers, and multiplication becomes
a binary computable function. A group $G=\langle X; R\rangle$ is
\emph{finitely presented} (f.p.) if both $X$ and $R$ are finite. It is easy
to see (under coding) that in this case, $=_{G}$ is a computably enumerable
equivalence relation on $\omega$.

Our terminology is slightly nonstandard because by the word problem of a
f.p.\ group $G=\langle X;  R\rangle$, one usually means the equivalence class
$[1]_{G}$ of the identity element $1$, and the problem of deciding, for a given word $w\in F(X)$, whether
$w \in [1]_{G}$. The difference is minor, though, since $=_{G}$ and the set
$[1]_{G}$ are $m$-equivalent. The $1$-reduction $x \mapsto \langle
x,1\rangle$ shows that $[1]_G \, \le_1 \, =_G$ (where the symbol $\le_{1}$
denotes $1$-reducibility), and the $m$-reduction $\langle x,y\rangle \mapsto
xy^{-1}$ shows that  $=_G \, \le_m \, [1]_G$ (where the symbol $\le_{m}$
denotes $m$-reducibility).

\subsection*{Effective inseparability}
The reader is referred to \cite{Soare:Book} for any unexplained notation and
terminology from computability theory. A partial computable function which
is total  is  simply called   a
computable function. If  $A, B
\subseteq \omega$, one writes  $A\equiv B$ if there exists a computable
permutation $f$ of $\omega$ such that $f(A)=B$;   if $(A,B)$ and $(C,D)$ are
disjoint pairs of subsets of $\omega$, one writes  $(A,B) \equiv (C,D)$, if
there exists a computable permutation $f$ of $\omega$ such that $f(A)=C$ and
$f(B)=D$. We recall that a  disjoint pair of sets $(A,B)$ is called
\emph{recursively inseparable} if there is no recursive set  $X$ such that $A
\subseteq X$ and $B \subseteq X^c$, where $X^{c}$ denotes the complement of
$X$. The following property is stronger: $(A,B)$  is \emph{effectively
inseparable} (\emph{e.i.}) if there is \emph{productive} function, that is, a
partial computable function $\psi(u,v)$ such that
\[
(\forall u,v)[A \subseteq W_u \mathand B \subseteq W_v \mathand W_u \cap W_v =
\emptyset \Rightarrow \psi(u,v)\downarrow \notin W_u \cup W_v].
\]

\begin{rem}\label{stuff-on-ei}
It is well known (see e.g.\ \cite[II.4.13]{Soare:Book}) that if $(A,B)$ and
$(C,D)$ are disjoint pairs of c.e.\ sets then:
\begin{enumerate}
\item[-] $(C,D)$ e.i.\ implies $(A,B) \le_1 (C,D)$;
\item[-] if both pairs are e.i.\ then $(A,B) \equiv (C,D)$;
\item[-] if $(A,B) \le_m (C,D)$ and $(A,B)$ is e.i.\ then $(C,D)$ is e.i.\
    as well;
\item[-] if $A \subseteq C$, $B \subseteq D$ and $(A,B)$ is e.i.\ then
    $(C,D)$ is e.i.\ as well.
\end{enumerate}
 \end{rem}
The following fact  about e.i.\ pairs of c.e.\  sets will be used in the
proof of Theorem~\ref{thm:main1}.

\begin{lem}\label{lem:uei-product}
If $(A,B)$ and $(C,D)$ are e.i.\ pairs of c.e.\ sets, then so is
the pair $(A\times C, B\times D)$. Moreover,   a productive function for
$(A\times C, B\times D)$ can be found uniformly from productive functions for
$(A,B)$ and $(C,D)$.
\end{lem}

\begin{proof}
We prove in fact that if $(A,B)$ is a disjoint pair of c.e.\  sets, and
$(C,D)$ is e.i., then $(A,B) \le_{1} (A\times C, B\times D)$: hence, if
$(A,B)$ is e.i., then $(A\times C, B\times D)$ is e.i.\  as well. Let $g$ be
a computable function such that $g(A)\subseteq C$ and $g(B)\subseteq D$; such
a function exists because $(A,B) \le_{1} (C,D)$.   Clearly the
$1$-$1$ computable function
\[
f(x)=\langle x, g(x)\rangle
\]
provides a $1$-reduction showing that $(A,B) \le_{1} (A\times C, B\times D)$.

The claim about uniformity is straightforward.
\end{proof}

  Although not used in this paper, it is worth noting that a statement
analogous to the   lemma  above holds  when we replace ``effectively
inseparable'' by the weaker notion of being recursively inseparable.

\begin{prop}\label{lem:rec-ins}
If $(A,B)$ and $(C,D)$ are recursively inseparable pairs of c.e.\  sets,
then so is $(A\times C, B\times D)$.
\end{prop}

\begin{proof}
Assume that $R$ is a computable set such that $A\times
C \subseteq R$ and $B\times D \subseteq R^{c}$. For every
$v$, let
\[
R_{v}=\{x: \langle x, v\rangle \in R\}.
\]
We observe that for every $v$ there exists $x \in A$ such that $\langle x,
v\rangle \in R^{c}$, or there exists $x \in B$ such that $\langle x, v
\rangle \in R$;  otherwise $A\subseteq R_{v}$ and $B \subseteq R_{v}^{c}$,
which would contradict the inseparability of $(A,B)$. Let $R_{A} $ and $R_{B}
$ be computable binary relations such that
\begin{align*}
&(\exists x)[x \in A \,\&\,\langle x,v\rangle \in R^{c}] \Leftrightarrow
            (\exists s)R_{A}(v,s),\\
&(\exists x)[x \in B \,\&\,\langle x,v\rangle \in R ] \Leftrightarrow
            (\exists s)R_{B}(v,s),
\end{align*}
and define
\[
U=\{v: (\exists s)[R_{A}(v,s)] \,\&\, (\forall t \le s) \neg R_{B}(v,t)]\}.
\]
The set $U$ is decidable, as we have seen that for every $v$, there exists $x
\in A$ such that $\langle x,v\rangle \in R^{c}$, or there exists $x \in B$
such that $\langle x,v\rangle \in R$. Now $v \in C \cap U$ implies  $(\exists
x)[x \in A \,\&\, \langle x,v\rangle \in R^{c}]$ contrary to $A \times C
\subseteq R$. Similarly, $v \in D \smallsetminus U$ implies $(\exists x)[x
\in B \,\&\,\langle x,v\rangle \in R]$, contrary to  $B \times D \subseteq
R^c$. We conclude  that $C \subseteq U^{c}$ and $D \subseteq U$, which is the
final contradiction.
\end{proof}

\subsection*{C.e.\  equivalence relations and word problems}
Computably enumerable equivalence relations have been  studied extensively;
see for instance \cite{Bernardi-Sorbi:Classifying, Ershov:positive,
Gao-Gerdes}. While they are called \emph{positive} in the Russian literature,
we call such an equivalence relation a \emph{ceer} following Andrews et al.\
\cite{ceers}. $\Sigma^{0}_{1}$-universal ceers arising naturally in formal
logic have been pointed out for instance in~\cite{Bernardi-Montagna:extensional, Montagna:ufp,
Visser:Numerations}.

\begin{defn}[\cite{Bernardi:the-relation-provable}]\label{uei eqrel}
A ceer $E$ is called \emph{uniformly effectively inseparable} (\emph{u.e.i.})
if there is  a computable  binary function $p$ such that, whenever
$a\cancel{\rel{E}} b$, the partial computable function $\psi(u,v)
=\phi_{p(a,b)}(u,v)$ witnesses that the pair of equivalence classes $([a]_E,
[b]_E)$ is e.i.\
\end{defn}
\noindent As already observed in the introduction, it is shown in
\cite{ceers} that every u.e.i.\ ceer is $\Sigma^{0}_{1}$-universal. It is
worth recalling that uniformity plays a crucial role in yielding
universality, as there are non-universal ceers yielding a partition of
$\omega$ into effectively inseparable pairs of distinct classes~\cite{ceers}.

Surprisingly, f.p.\ groups  with a $\Sigma^0_1$-universal word problem
appeared in the literature prior to any explicit study of computable
reducibility among equivalence relations.  Charles F.\
Miller~III~\cite{MillerIII-decision} proved that there exists a f.p.\  group
with $\Sigma^0_1$-universal word problem.  He  shows that  another
interesting equivalence relation is $\Sigma^0_1$-universal:  the isomorphism
relation between finite presentations of groups, which (via encoding of
finite presentations  by numbers)  can be seen as a ceer.  Not knowing  of
this much earlier result, Ianovski, Miller, Ng, and  Nies~\cite[Question
6.1]{Ianovski-et-al} had recently posed this as an open question.

\begin{thm}[\cite{MillerIII-decision}]\label{thm:MillerIII} \mbox{}
\begin{enumerate}
  \item  Given a ceer $E$  one can effectively build a f.p.\ group
      $G_{E}=\langle X; R \rangle$, and a computable sequence of words
      $(w_{i})_{ i \in \omega}$ in $ F(X)$ such that, for every $i,j$,
      \[
i \rel{E} j \Leftrightarrow w_{i}=_{G_{E}} w_{j}.
\]
  \item Given  a finite presentation $\langle X; R \rangle$ of a group $G$
      one  can effectively find a computable family  $(H^G_w )_{w  \in
      F(X)}$ of f.p.\ groups such that, for all $v, w \in F(X)$,
\[
v =_G w \Leftrightarrow H^G_{v} \cong H^G_{w}.
\]
\end{enumerate}
\end{thm}
\begin{proof}
The first item is obtained  in \cite[p~90f]{MillerIII-decision}, used as a
preliminary step to prove Theorem~V.2. The second item is
\cite[Theorem~V.1]{MillerIII-decision}.
\end{proof}

\begin{cor}  \label{cor:Miller} \mbox{}
\begin{enumerate}
\item There exists a f.p.\ group $G$ such that $=_{G}$ is a
    $\Sigma^{0}_{1}$-universal ceer.
\item The isomorphism problem  $\cong_{f.p.}$ between finite presentations
    of groups is a $\Sigma^{0}_{1}$-universal ceer.
\end{enumerate}

\end{cor}

\begin{proof}
Let $E$ be a $\Sigma^{0}_{1}$-universal ceer. Then
\begin{enumerate}
  \item by Theorem~\ref{thm:MillerIII}(1), $E\le \, =_{G_E }$, and thus
      $=_{G_{E}}$ is $\Sigma^{0}_{1}$-universal;
  \item by Theorem~\ref{thm:MillerIII}(2),
\[
i \rel{E} j \Leftrightarrow H^{G_{E}}_{v} \cong H^{G_{E}}_{w}.
\]
This shows that $E \le \, \cong_{f.p.}$, whence $\cong_{f.p.}$ is
$\Sigma^{0}_{1}$-universal.
\end{enumerate}
\end{proof}

We observe   that $\Sigma^0_1$-universality of the word problem  does not
necessarily imply being u.e.i.

\begin{thm}\label{thm:notei}
There exists a f.p.\ group $G$ such that $=_G$ is $\Sigma^0_1$-universal, but
not u.e.i.
\end{thm}

\begin{proof}
We build  a f.p.\ group $G$ such that $=_G$ is $\Sigma^0_1$-universal, but it
does not even yield a partition into recursively  inseparable pairs of
disjoint equivalence classes. To see this, let $H = \langle X; R \rangle$ be
a f.p.\  group such that $=_H$ is $\Sigma^0_1$-universal. Let $v\not \in X$
be a new letter. The free product $G=H \ast F(v)$ (where $F(v)$ is the free
group on $v$) has the finite presentation $\langle X, v; R\rangle$. Since $H$
can be seen as a subgroup of $G$ and the embedding is computable, the group
$G$ has $\Sigma^0_1$-universal word problem. Any word $w \in F(X \cup \{v\})$
can be uniquely written as $w=h_1v^{n_1}h_2\cdots v^{n_r}h_{r+1}$, with $h_j
\in F(X)$ and $n_j \neq 0$, for all $j$. Let
\[
n_v(w)=n_1+ \cdots +n_r
\]
be the exponent sum of $v$ in $w$, and let $S=\{w \in F(X \cup \{v\}):
n_v(w)=0\}$. It is immediate that $[1]_G\subseteq S$ and $[v]_G \subseteq
S^c$, so  the recursive set $S$ separates the pair $([1]_G, [v]_G)$.
\end{proof}

The proof of the previous theorem suggests an additional comment. We observe
that if in a group $G$ the operations are computable, then all
$=_G$-equivalence classes are uniformly computably isomorphic: the function
$w \mapsto wu^{-1}v$ is a computable permutation of the group (uniformly
depending on $u,v$) which maps $[u]_G$ onto $[v]_G$. Thus if an equivalence
class $[u]_G$ is creative, so is any other equivalence class $[v]_G$, and
creativeness holds uniformly, i.e. there is a computable function $p$ such
that, for every $v$, $\phi_{p(v)}$ is productive for the complement of
$[v]_G$. Nothing like this holds for effective inseparability, or for
computable inseparability. Indeed, one can take the group $H$ considered in
the proof of Theorem~\ref{thm:notei} to be such that its word problem yields
at least a pair of effectively inseparable classes (for instance take $H=D$,
where $D$ is the group built in Theorem~\ref{thm:main1} in which all distinct
pairs of equivalence classes are effectively inseparable). Thus the word
problem of the group $G$ of Theorem~\ref{thm:notei} does have effectively
inseparable classes, but not all pairs are so, since there are pairs which
can be computably separated.

\section{A finitely presented group with u.e.i.\ word problem}
We now build   a f.p.\  group  with a  word problem that is a u.e.i.\ ceer.
We first provide   Lemma~\ref{lem:normal-closure}   that if $G$ is a f.p.\
group containing a word $w$ such that $([1]_G, [w]_G)$ is e.i., then all
disjoint pairs $([s]_G, [t]_G)$ with $s, t \in \Ncl_G(w)$ are   e.i.\ in a
uniform way. For the main construction, using a result of Miller III, we take
a computably presented group~$A$ containing a word~$w$ such that the pair
$([1]_A, [w]_A)$ is e.i. By the Higman Embedding Theorem combined with a
construction due to Rabin, we embed $A$ into a f.p.\ group $D$ so that if
$N$ is a non-trivial normal subgroup of $D$, with $w \in N$, then $N=D$.
Taking $N=\Ncl_D(w)$
and observing that the pair $([1]_D, [w]_D)$ is also  e.i., the lemma shows
that $=_D$ is u.e.i.

\begin{lem}\label{lem:normal-closure}
Let $G=\langle X; R\rangle$ be a given f.p.\ group, and let $w$  be an element
of $F(X)$ such that  $([1]_G, [w]_G)$ is e.i. Let $N=\Ncl_G(w)$. For   $s,t
\in N$ such that  $s \ne_G t$, the pair of sets $([s]_G,[t]_G)$ is e.i.\
uniformly in $s,t$.
\end{lem}

\begin{proof}
Since $([s]_G, [t]_G)\equiv ([1]_G, [s^{-1}t]_G)$, it suffices to show that
$([1]_G, [r]_G)$ is uniformly e.i.\ for any $r \in N \smallsetminus [1]_G$.
Note that $N$ consists of the products of conjugates of $w$ and of $w^{-1}$,
so  it is enough to show:
\begin{enumerate}
  \item if $([1]_G, [u]_{G})$ is e.i., then so is $([1]_G, [u^{-1}]_{G})$:
      this follows from the fact that $([1]_{G}, [u]_{G}) \equiv
      ([u^{-1}]_{G}, [1]_{G},)$, via the computable permutation $x \mapsto
      u^{-1} x$;
  \item if $([1]_G, [u]_{G})$ is e.i., then so is $([1]_{G}, [g^{-1}u
      g]_{G})$ for every $g \in G$: the computable permutation $x \mapsto
      g^{-1} x g$ provides an isomorphism $([1]_G, [u]_{G})\equiv
      ([1]_{G}, [g^{-1}u g]_{G}) $;
  \item if $uv \ne_G 1$ and the pairs $([1]_{G}, [u]_{G})$ and $([1]_{G},
      [v]_{G})$ are e.i., then $([1]_{G}, [uv]_{G})$ is e.i.:  \\
      By Lemma~\ref{lem:uei-product} the pair $([1]_G \times [1]_G,
      [u]_G\times [v]_G)$ is e.i. On the other hand, let
      \begin{align*}
       X&=\{\langle w,z\rangle : wz \in [1]_G\},\\
       Y&=\{\langle w,z\rangle : wz \in [uv]_G\}.
      \end{align*}
Then    $[1]_G \times [1]_G \subseteq X$ and $ [u]_G\times [v]_G\subseteq
      Y$, and thus, by Remark~\ref{stuff-on-ei}, $(X, Y)$ is e.i. Since
      $(X,Y)\le_m ([1]_{G}, [uv]_{G})$ via the mapping $\langle w, z\rangle
      \mapsto wz$, it follows that $([1]_{G}, [uv]_{G})$ is e.i., as
      desired.
\end{enumerate}
Each step provides being e.i.\ in a uniform fashion. If $r\in N$ we can
obtain its  representation as a product of conjugates of $w$ and of $w^{-1}$
effectively. Since $[1]_G$ and $N$ are c.e., there is a partial computable
function $p$ such that $\phi_{p(a,r)}$ is productive for $([a]_G, [r]_G)$,
when $a \in [1]_G$ and $r \in N \smallsetminus [1]_G$. So $([1]_G,[r]_G)$ is
e.i.\ uniformly in $r$, whence $([s]_G,[t]_G)$ is e.i.\ uniformly in $s,t$
 as required.
 \end{proof}

\begin{thm}\label{thm:main1}
There exists a f.p.\  group $D$ such that $=_D$ is u.e.i.
\end{thm}

\begin{proof}
For elements $u,t$ of a group, we write $\Cj(u,t)=t^{-1}ut$. Following
\cite{MillerIII-quotients},  take an e.i.\ pair $(Y_0,Y_1)$ of c.e.\ sets.
Let
$F=F(c,d)$ be the free group on two generators $c,d$; for every $i>0$, let
\[
b_{i-1}=\Cj(\Cj(c,d^{-1}),c^{i})\cdot \Cj(\Cj(\Cj(c^{-1},d),c^{i}),d^{-2}).
\]
Next let
\[
R=\Ncl_{F}(\{b_{0}b_{i}^{-1}: i \in Y_0\} \cup \{b_{1}b_{j}^{-1}: j \in Y_1\}),
\]
and let  $A=\langle c,d; R \rangle$.
Note
that $A$ is   a \emph{computably presented}  group, namely $A$ has a
presentation $\langle Z; T\rangle$ where $Z$ is finite and $T$ is c.e. It can
be shown \cite{MillerIII-quotients} that the computable mapping $i \mapsto
b_i$ provides a reduction
\[
(Y_0,Y_1) \le_1 ([b_0]_A, [b_1]_A).
\]
Hence, by the third item in Remark~\ref{stuff-on-ei}, the pair  $([b_0]_A,
[b_1]_A)$ is e.i. We now follow  a line of argument as in the proof of
Theorem~IV.3.5 of \cite{Lyndon-Schupp}, to which the reader is referred to
fill in the details of the present proof;  the only difference between our
proof and that in~\cite{Lyndon-Schupp} is that we first embed $A$ into a
f.p.\ group $L$, aiming at a final f.p.\ group $D$, whereas in the proof of
Theorem~IV.3.5 of \cite{Lyndon-Schupp} the starting group $C$ is first
embedded into a countable simple group $S$, as the goal in that case is to
end up with a finitely generated simple group. (The construction provided by
Theorem~IV.3.5 of \cite{Lyndon-Schupp} is due to Rabin~\cite{Rabin}; the
version presented in \cite{Lyndon-Schupp} is modelled on
Miller~III~\cite{MillerIII-decision}.)

By the Higman Embedding Theorem (\cite{Higman}; see also
\cite[Theorem~IV.7.1]{Lyndon-Schupp}) the computably presented group $A$ can
be embedded into  a f.p.\ group $L$; next embed, using
\cite[Theorem~IV.3.1]{Lyndon-Schupp},  the free product $L \ast F(x)$ (with
$x$ a new generator) in a f.p.\ group $U$, generated by $u_1$ and $u_2$ both
of infinite order.

In order to build the desired f.p.\ group $D$, we are now going to introduce
additional groups, using two well known combinatorial group theoretic
constructions, namely HNN-extension (where HNN stands for
Higman-Neumann-Neumann), and free product with amalgamation. We briefly
recall these two constructions. If $G=\langle T; Z\rangle$ is a group
presentation, and $\phi:H\rightarrow K$ is an isomorphism between subgroups
of $G$, then the \emph{HNN-extension of $G$, relative to $H,K$ and $\phi$},
is the group $\langle T, p; Z \cup \{p^{-1}h p=\phi(h): h \in H\}\rangle$, of
which $G$ is a subgroup, and $p$  (with $p \notin G$) realizes by conjugation
the given isomorphism; $p$ is called the \emph{stable letter}. It is clear
that one can limit oneself to let the added relations vary on a set of
generators of $H$, instead of adding one relation for each $h \in H$.
Moreover, if $G_{1}=\langle T_{1}; Z_{1}\rangle$, $G_{2}=\langle T_{2};
Z_{2}\rangle$ are group presentations of disjoint groups, with two isomorphic
subgroups $H_{1}, H_{2}$, via isomorphism $\phi: H_{1}\rightarrow H_{2}$,
then their \emph{free product amalgamating $H_1$ and $H_2$ by $\phi$} is the
group $\langle T_{1}\cup T_{2}; Z_{1}\cup Z_{2} \cup \{h=\phi(h): h \in
H_{1}\}\rangle$, which is intuitively the ``freest'' overgroup of both $G_{1}$
and $G_{2}$ in which their subgroups are identified. Again,  it is clear that
one can limit oneself to let the added relations vary on a set of generators
of $H_{1}$, instead of adding one relation for each $h \in H_{1}$. For more
on these constructions, see \cite{Lyndon-Schupp}.

Consider the groups
\begin{align*}
J&=\langle U, y_1, y_2; y_1^{-1}u_1 y_1=u_1^2, y_2^{-1}u_2 y_2=u_2^2\rangle,\\
K&= \langle J,z; z^{-1}y_1z=y_1^{2}, z^{-1}y_2z=y_2^{2}\rangle,\\
P&=\langle r,s; s^{-1}rs=r^{2}\rangle,\\
Q&=\langle r,s,t; s^{-1}rs=r^{2}, t^{-1}st=s^{2}\rangle.\\
\end{align*}
The group $J$ is the (double) HNN-extension of $U$ with stable letters
$y_{1}, y_{2}$, where for each $i\in \{1,2\}$, $y_{i}$ realizes by
conjugation the isomorphism induced by $u_{i} \mapsto u_{i}^{2}$, between the
subgroups generated by $u_{i}$, and  by $u_{i}^{2}$, respectively; $K$ is the
HNN-extension of $J$, with stable letter $z$, realizing by conjugation the
isomorphism induced by $y_{1} \mapsto y_{1}^{2}$ and $y_{2} \mapsto
y_{2}^{2}$, between the subgroups generated by $y_{1}, y_{2}$,  and by
$y_{1}^{2}, y_{2}^{2}$, respectively; $P$ is the HNN-extension of $F(r)$,
with stable letter $s$, realizing by conjugation the isomorphism  induced by
$r \mapsto r^{2}$, between the subgroups generated by $r$, and  by $r^{2}$,
respectively; $Q$ is the HNN-extension of $P$, with stable letter $t$,
realizing by conjugation the isomorphism induced by $s \mapsto s^{2}$,
between the subgroups generated by $s$, and by $s^{2}$, respectively. It is
shown in the proof of \cite[Theorem~IV.3.4]{Lyndon-Schupp} that $r,t$ freely
generate a   subgroup of $Q$. Let $w \in L$, with $w \ne_L 1$: since the
commutator $[w,x]$ has infinite order in $U$, an argument similar to the one
used for $r,t$, and $Q$ (see again \cite{Lyndon-Schupp}) shows that $z$ and
$[w,x]$ freely generate a  subgroup of $K$. Thus, one can form the free
product with amalgamation
\[
D=\langle K \ast Q; r=z, t=[w,x]\rangle.
\]
All  groups mentioned are finitely presented except for $A$.
We summarize in the following diagram the chains of embeddings provided by the constructions:
\[
\begin{CD}
A @>>> L @>>> L \ast F(x) @>>> U @>>> J @>>> K\\
   @.           @.                         @.        @.         @.     @VVV\\
   @.          @. F(r)            @>>> P @>>> Q @>>> D.
\end{CD}
\]
As pointed out in the proof of \cite[Theorem~IV.3.4]{Lyndon-Schupp}, if $N
\lhd D$ and $w \in N$, then $w=1$ in the quotient $D/N$. Then $[w,x]=1$ in
this quotient. Using the relators, we conclude that $t=1$, $s=1$, $r=1$,
$z=1$, $y_1=1$, $y_2=1$, $u_1=1$ and $u_2=1$. Therefore the quotient is
trivial, and hence $N=D$.

Keeping track of the images of the generators $c,d$ of $A$ into $D$, under
the chain of embeddings leading from $A$ to $D$, one sees that there is a
computable function $k$ from $F(c,d)$ into $F(X)$, where $X$ is the set of
generators of $D$ in the exhibited presentation of $D$, inducing the embedding
of $A$ into $D$. Let us identify
$k(a)$ with $a$, for all $a \in F(c,d)$. Since, under this identification, $b_{0}\neq_{D}
b_{1}$,  $[b_0]_A \subseteq [b_0]_D, [b_1]_A \subseteq  [b_1]_D$, and $([b_0]_A,
[b_1]_A)$ is e.i.,  it follows that  $([b_0]_D, [b_1]_D)$ is e.i.\ by the
last item in Remark~\ref{stuff-on-ei}. Let $w=b_1^{-1}b_0$: then
$w \ne_D 1$, the pair $([1]_D, [w]_D)$ is e.i., and by
Lemma~\ref{lem:normal-closure} the normal closure $N=\Ncl_D(w)$ satisfies
the property that all pairs $([s]_{D}, [t]_{D})$ of disjoint equivalence
classes of $N$ are e.i., uniformly in $s,t$. Since $w \in N$, it follows that
$N=D$. Therefore $D$ is a f.p.\ group with u.e.i.\ word problem.
\end{proof}

\section{Diagonal functions}
A \emph{diagonal} function for an equivalence relation $E$ is a computable
function $\delta$ such that $a \cancel{\rel{E}} \delta(a)$, for all $a$. In
this section we apply diagonal functions to   ceers arising from group
theory, and pose some related open questions. Following~\cite{Montagna:ufp},
a ceer $E$ is \emph{uniformly finitely precomplete}  if there exists a
computable function $f(D,e,x)$ such that
\[
\phi_e(x)\downarrow \in [D]_E \Rightarrow f(D,e,x) \rel{E} \phi_e(x),
\]
for all $D,e,x$, where $D$ is a finite set and
$[D]_E$ denotes the $E$-closure of $D$.  (Here, and in the following, when given as an input to a computable
function, a finite set will be always identified with its canonical index.) An important example of a uniformly
finitely precomplete ceer is provable equivalence in Peano Arithmetic, i.e.\
the ceer $\sim_{PA}$ defined by $\ulcorner \sigma \urcorner \sim_{PA}
\ulcorner \tau \urcorner$ if and only if $\vdash_{PA} \sigma
\leftrightarrow \tau$.  Here $\sigma, \tau$ are sentences of $PA$, and we
refer to some computable bijection $\ulcorner \mbox{} \urcorner$ of the set
of sentences with $\omega$. A diagonal function is given by $\delta(\sigma) =
\neg \sigma$.

Ceers $E$ and $F$ are  called \emph{computably isomorphic} if there exists a
computable permutation $p$ of $\omega$ such that $p(E) = F$. The notions of a
diagonal function and a uniformly finitely precomplete  ceer play an
important role in the study and classification of $\Sigma^{0}_{1}$-universal
ceers.

\begin{prop}[\cite{Montagna:ufp}]
(i) Every uniformly finitely precomplete ceer is u.e.i.

\noindent (ii) A ceer $E$ is computably isomorphic to $\sim_{PA}$ if and only
if $E$ is uniformly finitely precomplete and $E$ has a diagonal function.
\end{prop}

A  \emph{strong diagonal} function for an equivalence relation $E$ is a
computable function $\delta$ such that $\delta(D) \notin [D]_E$, for every
finite set $D$.  Andrews and Sorbi~\cite{jumpsofceers} have shown   that
every u.e.i.\ ceer with a strong diagonal function is uniformly finitely
precomplete, and therefore computably isomorphic to $\sim_{PA}$.

Suppose a f.p.\ group $G = \langle X; R \rangle$ is nontrivial, say $w\ne_G
1$ for some $w \in F(X)$. Then $=_{G}$ has a diagonal function, namely the
map $\delta(r) = rw$ ($ r \in F(x)$). It would be interesting to prove that
there exists a f.p.\ group $G$ such that $=_G$ is uniformly finitely
precomplete, for this would yield an example of a word problem of a f.p.\
group which is computably isomorphic to $\sim_{PA}$. To show this, one can
try to strengthen Theorem~\ref{thm:main1} to provide a f.p.\ group $G$ such
that  $=_G$ is u.f.p., or, equivalently, to extend its proof in order to
provide  a f.p.\ group $G$ such that $=_G$ is u.e.i.\  and $G$ has a strong
diagonal function. Thereafter one can  use the above-mentioned result of
Andrews and Sorbi~\cite{jumpsofceers}. We do not know at present how to do
carry out this plan.

\begin{prop}
The isomorphism problem  $\cong_{f.p.}$ between finite presentations of
groups has a strong diagonal function.
\end{prop}
\begin{proof}
Uniformly in  a finite presentation $G = \langle x_1, \ldots, x_n ; r_1,
\ldots, r_k\rangle$,  the abelianization $G_{ab}$ has the finite presentation
\[
G_{ab} = \langle x_1, \ldots, x_n ; r_1, \ldots, r_k, [x_i,x_j]:
1 \le i<j \le n \rangle,
\]
where $[u,v]=u^{-1}v^{-1}uv$ is the usual commutator of $u,v$.
Given a finite set $S = \{G_1, \ldots, G_r\}$ of finite presentations, let
$\delta(S)$ be the canonical finite presentation of  the abelian group
$H=\mathds{Z} \times \prod_{1\le u \le r} (G_u)_{ab}$. Then $H \not \cong G_u$
for each $u$. For, if $G_u$ is abelian, then the torsion free rank of $H$
exceeds that of $G_u$.

We note that, via a   less elementary method involving  the Grushko-Neumann
Theorem (see~\cite[p.\ 178]{Lyndon-Schupp}), one could also  simply let  $H$
be the amalgam of $\mathds{Z}$ and all the $G_u$.
\end{proof}
We conjecture that $\cong_{f.p.}$ is uniformly finitely precomplete, and
hence computably isomorphic to $\sim_{PA}$.  In view of the foregoing
proposition it would suffice to show that the ceer $\cong_{f.p.}$ is  u.e.i.
By a result of Rabin~\cite{Rabin},  every equivalence class of $\cong_{f.p.}$ is creative;
see also \cite[p.\ 79]{MillerIII-decision}.

\section{$\Pi^{0}_{1}$-universality and groups of computable permutations}
We use the following notation: the product $\alpha\beta$ of two permutations
on some set $S$  is the permutation $\alpha\beta(s)=\beta(\alpha(s))$ where
$s \in S$.

\begin{thm}\label{thm:main2}
 There is a f.g.\ group of computable permutations  with a
$\Pi^{0}_{1}$-universal word problem.
\end{thm}

\begin{proof}
Given a $\Pi^0_1$ equivalence relation $E$, by \cite[Prop.\
3.1]{Ianovski-et-al} there is a computable binary function $f$ such
that
\[
x\rel{E}y \Leftrightarrow (\forall n) [f(x,n) = f(y,n)].
\]
The construction of $f$
shows that   $f(x,n)\le x$ for each $x,n$.

Fix now a $\Pi_{1}^{0}$-universal equivalence relation $E$
(for the existence of such an equivalence relation see~\cite{Ianovski-et-al}) and a corresponding function
$f$ as above. Via  a computable bijection  we identify $\mathds{Z} \times \omega$ with
$\omega$. We think of the domain of our computable permutations as a
disjoint union of pairs of ``columns" $$C^i_x = \{ 2x+i\} \times \omega,$$
where $i =0,1$, $x \in \mathds{Z}$ for the rest of this proof.

The first two of the three computable permutations $\sigma, \tau, \alpha$ we
are  about to define do not depend at all on $f$. The permutation $\sigma$
shifts $\C i x $ to $\C i {x+1}$:
\[
\sigma (\la 2x+i, n \ra) = \la 2x+2+i, n \ra.
\]
The permutation $\tau$ exchanges $\C i 0 $ with  $\C {1-i} 0$ and is the
identity elsewhere:
\[
\tau (\la  i, n \ra) = \la  1-i, n \ra.
\]
We now define a computable permutation $\alpha$ coding $f$ in the sense that
there exists a fixed computable sequence $(t_x(\alpha, \sigma,\tau))_{x \in
\omega}$ of words in the free group generated by the symbols $\alpha, \sigma, \tau$, such that
for each $x,y \in \omega$,
\begin{equation} \label{eqn: code}
 \forall n \, f(x,n) = f(y,n)  \Leftrightarrow t_x
= t_y,
\end{equation}
where equality $t_x= t_y$ is in the group
generated by the three permutations.
For each $x, n$, the permutation $\alpha$ has a cycle of length $f(x,n)$ in the
interval $n(x+1), \ldots, (n+1)(x+1) -1$ of $C_{x}^{0}$. Thus, for each $x,n
\in \omega$ and $k \le x$,
\[
\alpha(\la 2x, n(x+1) +k \ra) =
\begin{cases}    \la 2x, n(x+1) + k+1 \ra & \mbox{if} \ k< f(x,n) \\
					  \la 2x, n(x+1)  \ra & \mbox{if} \ k= f(x,n) \\
					  \la 2x, n(x+1) +k  \ra & \mbox{otherwise,}
\end{cases}
\]
and $\alpha$ is the identity on the remaining columns.
We now define the terms $t_x$ for $x \in \omega$. The permutation $t_x
(\alpha, \sigma, \tau)$ will only retain the encoding of the values $f(x,n)$, and
erase all other information. It also moves this information to the pair of
columns $\C 0 0, \C 10$. In this way  we can compare the values $f(x,n)$ and
$f(y,n)$ applying  $t_x$ and $t_y$ to $\alpha, \sigma, \tau$.

Recall that for elements $u,t$ of a group we write $\Cj(u,t)=t^{-1}ut$.
We let
\[
t_x=\Cj(\alpha, \sigma^{-x})\tau \Cj(\alpha^{-1}, \sigma^{-x}).
\]
Let $\alpha_x$   be the permutation    given by $\alpha(\langle 2x,
y\rangle)=\langle 2x, \alpha_x(y)\rangle$. Using that everything cancels
except what $\alpha$ codes on the column $C^0_x$,  we obtain
\[
t_x(\langle u,y\rangle)=
\begin{cases}
\langle u,y \rangle, &\text{if $u\ne 0,1$},\\
\langle 1, \alpha_x(y)\rangle, &\text{if $u=0$},\\
\langle 0, (\alpha_x)^{-1}(y)\rangle, &\text{if $u=1$}.
\end{cases}
\]
By the definition of $\alpha$ it is now clear that (\ref{eqn: code}) is
satisfied, and thus our $\Pi^{0}_{1}$-universal $E$ is reducible to
the word problem of $G$.
\end{proof}
In the area of  computational complexity, one writes input numbers in binary
and considers time bounds compared to their length. A quadratic time variant
$G$ of the function $f$  encoding the equivalence relation $E$ is obtained in
\cite[Theorem~3.5]{Ianovski-et-al}.  Some modifications to the proof above
yield three permutations that are polynomial time computable, as are their
inverses, and they  still  generate a group with $\Pi^0_1$-universal word
problem.

Independently Fridman~\cite{Fridman1962}, Clapham~\cite{clapham1964finitely}
and Boone~\cite{Boone1966a,Boone1966b,Boone1971} proved that each c.e.\
Turing degree contains the word problem of a f.p.\ group. (Here and
throughout next theorem and its proof, ``word problem'' is meant classically
as the equivalence class of the identity element). Later
Collins~\cite{Collins-tt-1971} extended this to c.e.\ truth table degrees. In
contrast, Ziegler~\cite{Ziegler1976}  constructed a bounded truth-table
degree that does not contain the word problem of a f.p.\ group. For f.g.
groups with $\Pi^{0}_{1}$ word problem, Morozov~\cite{morozov2000once} has
shown that there is a two-generator group which is not embeddable into  the
group of computable permutations of $\omega$.

 Using the
methods of the foregoing result, here we obtain an analog of the results by
Fridman, Clapham, Boone and Collins  for f.g.\ groups of computable
permutations. In fact we can choose the permutations of a special kind.

Let us call a permutation $\sigma$ \emph{fully primitive recursive} if both
$\sigma $ and $\sigma^{-1}$ are primitive recursive. Note that the fully
primitive recursive permutations form a group.

\begin{thm} \label{th:truth table}
Given a $\Pi^0_1$ set $S$ we can effectively build   fully primitive recursive
permutations $\beta, \sigma, \tau$ such that the group $G$ generated by them
has word problem in the same truth-table degree as~$S$.
\end{thm}
\begin{proof}
In this proof we   work with  an array of  columns indexed by integers.  Let
$\sigma (\la x, n \ra) = \la x+1, n \ra$  ($x \in \mathds{Z}, n \in \omega$)
be the shift to the next column. Let $\tau$ consist of the 2-cycles  $(\la 0,
3t +1 \ra ,  \la 0, 3t+2 \ra)$ for each $t$: in other words, $\tau(\la 0,
3t +1 \ra) =\la 0, 3t+2 \ra$, $\tau(\la 0,
3t +2 \ra) =\la 0, 3t+1 \ra$ for all $t$, and $\tau$ is the identity elsewhere.

Let $S$ be a given $\Pi^{0}_{1}$ set, and let $S^{c}= \omega \smallsetminus
S$ be the complement of $S$. First we show we may assume that, up to
$m$-equivalence,  $S^{c}$  is the range of a  $1$-$1$ function with graph
effectively given  by an index for a  primitive recursive relation.  We can
uniformly replace $S^{c}$ by $\{2n \colon \, n \in  S^{c}\}  \cup \{2n+1
\colon n \in \omega\}$, so we may assume that $S^{c}$ is infinite. From a
c.e.\ index for $S^{c}$ we may effectively obtain an index $e$  of a Turing
machine  that computes a  $1$-$1$   function $f$ with range $S^{c}$. Thus,
for all $x$ we have $f(x)=U(\mu y. \,T(e,x,y))$, where $U$ and $T$ are
respectively a primitive recursive function and a primitive recursive
predicate as in the Kleene Normal Form Theorem. Consider the primitive
recursive predicate  $P(e,x,y)$, which holds if and only if $T(e,x,y) \,\&\,
\forall z < y \, [\neg T(e,x,z)]$.  Using  the standard primitive recursive
pairing function $\la . \,, . \ra$, let $g (\la x, y \ra) = 2 U(y)$ if
$P(e,x,y)$ holds, and  $g (\la x, y \ra) = 2 \la x, y \ra + 1$ otherwise.
Clearly $g$ is a $1$-$1$ function with primitive recursive graph. The range
of $g$ is $\{2n \colon \, n \in  S^{c}\} \cup \{2 \la x, y \ra + 1\colon \,
\neg P(e,x,y)\}$, which is   $m$-equivalent to $S^{c}$.

Next we code the graph of $g$  into a fully primitive recursive permutation
$\beta$ as follows:  if $g(t) = x$, then $\beta $ has  a 2-cycle $(\la x, 3t
\ra, \la x, 3t+1 \ra)$. Thus, among the three permutations only $\beta$
depends on $S$.  Clearly $\beta $ is fully primitive recursive uniformly in a
c.e.\ index for $S^c$.

Let $G$ be the group of   permutations generated by $\sigma, \tau, \beta$.
For $x \in \omega$, we can picture $\Cj (\beta , \sigma^{-x})$ as the
``shift'' of $\beta$ by $x$ columns to the left. The set $S$  is many-one
below the word problem of $G$ because
\[
x \in S \Leftrightarrow  [\Cj (\beta , \sigma^{-x}), \tau] =1,
\]
where $[u,v]=u^{-1}v^{-1}uv$ is the usual commutator of $u,v$. To see this,
first note that if $y \ne 0$, then $\Cj (\beta , \sigma^{-x})(\langle
y,t\rangle)$ still lies in the $y$-th column, and thus $\Cj (\beta ,
\sigma^{-x}) \tau(\langle y,t\rangle)=\tau \Cj (\beta , \sigma^{-x})(\langle
y,t\rangle$), as $\tau$ is the identity on the $y$-th column. Now, if $x \in
S$, then $\beta$ is the identity on the $x$-th column and thus  $\Cj (\beta ,
\sigma^{-x})$ is the identity on the $0$-th column, giving $[\Cj (\beta ,
\sigma^{-x}), \tau] =1$; if $x \notin S$, and $t$ is such that $g(t)=x$, then
$\Cj (\beta, \sigma^{-x}) \tau(\langle 0 ,i\rangle) \ne \tau\Cj (\beta ,
\sigma^{-x})(\langle 0,i\rangle)$, for every $i \in \{3t,3t+1,3t+2\}$.

It remains to show that  the  word problem of $G$ is truth-table below $S$.
We note that $\tau$ and $\beta$ are involutions. For any  $x \in \mathds{Z}$
we write $\beta_x = \Cj (\beta , \sigma^{-x})$ and $\tau_x= \Cj(\tau,
\sigma^{-x})$.  It is easy to see that  $[\beta_x, \beta_y]=1$ and $[\tau_x,
\tau_y]=1$, for all $x,y$.
Suppose now that a word $w\in F(\beta, \sigma, \tau)$ (the free group on
$\{\beta, \sigma, \tau\}$) is given; we have to decide whether $w=1$ in $G$
by  accessing the oracle $S$ in a truth-table fashion. If the exponent sum of
$\sigma$ in $w$ (i.e. the sum of all exponents of occurrences of $\sigma$ in
$w$) is nonzero then $w \neq 1$ in $G$. Otherwise, using the observations
above, we can effectively replace $w$  by an equivalent word
\begin{equation}\label{eqn:w-replace}
(\prod_{x \in L_1} \beta_x) (\prod_{u \in M_1} \tau_{u}) (\prod_{x \in L_2} \beta_x)
(\prod_{u \in M_2} \tau_{u}) \ldots   (\prod_{x \in L_k} \beta_x) (\prod_{u \in M_k} \tau_{u})
\end{equation}
where the the $L_i$ and $M_i$ are effectively
given  finite sets of distinct integers, which are nonempty except for possibly $L_1$
or $M_k$. Let $L=\bigcup_{i} L_{i}$ and $M=\bigcup_{i} M_{i}$.

Notice that a product $\beta_x \tau_u$ produces a $3$-cycle in column $-u$
precisely when $x -u\in  S^c$, otherwise  $\beta_x \tau_u$ coincides on
$C_{-u}$ with $\tau_u$. For every $x,u$ let $w(x,u)$ be the word obtained
from (\ref{eqn:w-replace}) by deleting all elements different from $\beta_x,
\tau_u$, and cancelling all occurrences of subwords $\beta_x \beta_x$ and
$\tau_u\tau_u$. Since $g$ is $1$-$1$, we have that the cycles of $\beta_x$
and $\beta_y$ are disjoint for any $x \neq y$: therefore the permutations
corresponding to $w(x,u)$ and $w$ coincide in the interval  $\{\langle -u, 3t
\rangle, \langle -u, 3t+1 \rangle, \langle -u, 3t+2 \rangle\}$ of the column
$C_{-u}$, where $g(t)=x$.

To decide whether the word in (\ref{eqn:w-replace}) is equal to $1$ in $G$,
we give a procedure to decide whether the permutation corresponding to $w$ is
the identity on each column $C_{-u}$.
 First notice that $w$ fixes all columns $C_{-u}$ with $u \notin M$
if and only, for all $x \in L$, the number of occurrences of $\beta_x$ in
(\ref{eqn:w-replace}) is even. Indeed, if $u \notin M$ and $x \in L$, then
$w(x,u)$ is a word consisting of only occurrences of $\beta_x$, which by
cancellation is either empty (if the number of occurrences is even) or equal
to $\beta_x$: if the former case happens for every $x \in L$, then every
column $C_{-u}$ with $u\notin M$ remains fixed; if $x\in L$ satisfies the
latter case, and $u \notin M$ is such that $x-u\in S^c$, then $w$ does not
fix $C_{-u}$, in which case we output $w \ne 1$ in $G$.

If we have already ascertained that all columns $C_{-u}$ remain fixed for all
$u \notin M$, then take any $u \in M$, and for every $x \in L$, perform the
following check querying the oracle:
\begin{enumerate}
\item if $x-u \notin S^c$ then on the column $C_{-u}$ the permutation
    corresponding to $w(x,u)$  coincides with the one corresponding to the word
    obtained from it by cancelling all occurrences of $\beta_x$; in this
    case, state that $C_{-u}$ is \emph{$x$-fixed} if and only if the length
    of the resulting word is even;
\item if $x-u \in S^c$ and the number of occurrences in $w(x,u)$ of the
    subword $\beta_x \tau_u$ is a not a multiple of $3$, then the
    $3$-cycles produced by $\beta_{x}$ and $\tau_{u}$ do not cancel each
    other: state in this case that $C_{-u}$ is \emph{not $x$-fixed};
    otherwise, cancel from $w(x,u)$ all occurrences of $\beta_x\tau_u$, and
    state that $C_{-u}$ is \emph{$x$-fixed} if and only if the resulting word
    is empty.
\end{enumerate}
If for all $x\in L$ we have stated that $C_{-u}$ is $x$-fixed, then we conclude that
$C_{-u}$ is fixed under the permutation corresponding to $w$.

If for all $u \in M$, we have concluded that $C_{-u}$ is fixed, then we
output that $w=1$ in $G$; otherwise we output $w \neq 1$ in $G$. An output
will be  achieved no matter what the oracle is, so the reduction is
truth-table.
\end{proof}

It would be interesting to determine the complexity of isomorphism and
embedding for f.g.\ groups of recursive permutations. Totality of a function
described  by a recursive index is already $\Pi^0_2$ complete, so  it might
be  more natural to restrict oneself to   fully primitive recursive
permutations as defined above.  It    is a $\Pi^0_1$ condition of an index
consisting of a   pair of indices  $(e,i)$ for primitive recursive functions
(one for the potential permutation, one for its potential inverse) whether it
describes such a permutation.

In both settings, isomorphism and embedding are  $\Sigma^0_3$ relations
between finitely generated groups given by finite sets of indices for the
generators.  For an example where the isomorphism relation has an
intermediate complexity, suppose the domain is $\mathds Z$, and consider the
subgroup $G$ of the group of computable permutations generated by the shift.
The problem whether a   group generated by finitely many fully primitive
recursive permutations is isomorphic to  $G$ is $\Pi^0_2$-hard. To see this,
note that   infinity of a c.e.\ set $W_e$  is $\Pi^0_2$-complete.  Build a
fully primitive recursive permutation  $p_e$ by adding a cycle of length $n$
involving large numbers when  $n $ enters $ W_e$. Then the subgroup generated
by $p_e$ is isomorphic to $G$ if and only if $p_e$  has infinite order, if and
only if  $W_e$ is infinite.


\section{Introduction}
The so-called "Emergent Gravity Paradigm" \cite{egp1,egp2,egp3,egp4} developed by T. Padmanabhan and his collaborators suggest that gravity is an emergent phenomenon, and its field equations have the same status as the equations of elasticity or fluid mechanics. An important result is that the evolution of geometry can be interpreted in
thermodynamic terms \cite{padholo1,padholo2}
\begin{equation}\label{1}
    \int_V \frac{d^3 x}{8\pi G}\sqrt{h}u_a g^{ij} L_\xi N^a_{ij}=\frac{1}{2} T_{avg}(N_{sur}-N_{bulk}),
\end{equation}
where
\begin{equation}\label{2}
    N_{sur}=\int_{\partial V}\frac{\sqrt{\sigma}d^2 x}{G};\quad N_{bulk}=\frac{E}{(1/2) T_{avg}};\quad T_{avg}=\frac{1}{A_{sur}}\int_{\partial V} \sqrt{\sigma}d^2 x \frac{N a}{2\pi}
\end{equation}
are the degrees of freedom in the surface and bulk of a 3-dimensional region $V$ and
$T_{avg}$ is the average Davies-Unruh temperature \cite{dut1,dut2} of the boundary. The $h_{ab}$ is
the induced metric on the $t = constant$ surface, $N^a_{ij}=-\Gamma^a_{ij}+\frac{1}{2}(\delta^a_i \Gamma^d_{dj}+\delta^a_j \Gamma^d_{id})$, and $\xi_a = N u_a$ is the proper-time evolution vector corresponding to observers moving
with four-velocity $u_a=-N (dt)_a$, and $E$ is the Komar energy \cite{komar1,komar2}.  The time evolution of the metric in a region
(described by the left hand side), arises because $N_{sur}\neq N_{bulk}$ . In any static spacetime, on the
other hand, $L_\xi(\cdots)=0$, leading to "holographic equipartition" \cite{padholo3,padholo4,padholo5}: $N_{sur}=N_{bulk}$.

In this paper, we will derive the similar expression from the first order formulism, that is the Palatini action. The basic variables are the connection and co-tetrad form fields. This action is closely related to loop quantum gravity \cite{loop1,loop2,loop3,loop4}. Another advantage is that, when considering a black hole, the boundary degrees of freedom can be described by a SO$(1,1)$ BF theory \cite{wmz,wh1,wh2,whl,wh3}. In the following section we set $8\pi G=1$.
\section{The holographic equipartition from first order formulism}
Our starting point is the first order Palatini action coupled with matters,
\begin{equation}\label{3}\begin{split}
    S[e,A]=-\frac{1}{4}\int_{\mathcal{M}} \varepsilon_{IJKL} e^I\wedge e^J \wedge F(A)^{KL}+\frac{1}{2}\int_{\mathcal{M}} e^I \wedge T_I\\
    = -\frac{1}{2}\int_{\mathcal{M}} \Sigma_{IJ} \wedge F(A)^{KL}+\frac{1}{2}\int_{\mathcal{M}} e^I \wedge T_I,
\end{split}\end{equation}
where $e^I$ are covielbein 1-form fields,
\begin{equation}\label{4}
    \Sigma_{IJ}=\frac{1}{2}\varepsilon_{IJKL}e^K \wedge e^L
\end{equation}
 2-form fields, $A^{IJ}$ the $SO(3,1)$ connection 1-form, $F_{IJ}$ the curvature 2-form
of $A^{IJ}$, $T_I$ the energy-momentum 3-form and $I,J$ indices of the Lie algebra of $\frak{so}(3,1)$.
From the above action one can get the field equations,
\begin{equation}\label{5}
\varepsilon_{IJKL}e^J\wedge F(A)^{KL}=T_I,\quad {\rm d}_A \Sigma_{IJ}:={\rm d}\Sigma_{IJ}-A_I^{\ K}\wedge\Sigma_{KJ}-A_J^{\ K}\wedge\Sigma_{IK}=0.
\end{equation}

The dynamical variables can be chosen as the connection $A^{IJ}$ and its conjugate momentum $\Sigma_{IJ}$. Similar to Eq.(\ref{1}), we want to calculate the following expression for the first order formula
\[ \int_V \Sigma_{IJ} \wedge L_\xi A^{IJ}.\]
Due to the Cartan formula $L_\xi={\rm d} i_\xi+i_\xi {\rm d}$, where $i_X$ is the interior product, we get
\begin{equation}\label{6}\begin{split}
  \int_V \Sigma_{IJ} \wedge L_\xi A^{IJ}=\int_V \Sigma_{IJ} \wedge [ {\rm d}(i_\xi A^{IJ})+i_\xi {\rm d}A^{IJ}]\\
  =\int_V {\rm d}(\Sigma_{IJ} \wedge i_\xi A^{IJ})-{\rm d}\Sigma_{IJ} \wedge i_\xi A^{IJ}+\Sigma_{IJ} \wedge i_\xi {\rm d}A^{IJ}\\
   =\int_V \Sigma_{IJ} \wedge i_\xi {\rm d}A^{IJ}-{\rm d}\Sigma_{IJ} \wedge i_\xi A^{IJ}+\int_{\partial V} \Sigma_{IJ} \wedge i_\xi A^{IJ}.
\end{split}\end{equation}

\subsection{The bulk term}
First let us consider the bulk term. We choose the time gauge as
\begin{equation}\label{7}
    e^0_a=u_a=N\xi_a=-N(dt)_a\Rightarrow e_0^a=-u^a=-\xi^a/N,
\end{equation}
so on the hypersurface $V:t=constant$, we have
\begin{equation}\label{8}
    e^0\triangleq 0.
\end{equation}
(We denote equalities on $V$ by the symbol $\triangleq$.) Due to the definition (\ref{4}), the only non-zero $\Sigma$ are $\Sigma_{0i} (i=1,2,3)$. The bulk term is \begin{equation}\label{9}\begin{split}
     2 \int_V \Sigma_{0i} \wedge i_\xi {\rm d}A^{0i}-{\rm d}\Sigma_{0i} \wedge i_\xi A^{0i}=2 \int_V \Sigma_{0i} \wedge i_\xi (F^{0i}-A^0_{\ k} \wedge A^{ki})-i_\xi A^{0i} (A^k_{\ i}\wedge \Sigma_{0k}) \\
     =2 \int_V \Sigma_{0i} \wedge i_\xi F^{0i}+i_\xi A^{ki} (A_{\ k}^0\wedge \Sigma_{0i}),
\end{split}\end{equation}
where the field equations (\ref{5}) are used.

Since $\xi^a=-N e_0^a$,
\begin{equation}\label{10}\begin{split}
   2 \int_V \Sigma_{0i} \wedge i_\xi F^{0i}=2 \int_V i_\xi (\Sigma_{0i}\wedge F^{0i})= 2 \int_V i_\xi \frac{1}{2}(e^i \wedge T_i-e^0 \wedge T_0)\\
   =\int_V N (T_0 -e^i \wedge <e_0,T_i>),
\end{split}\end{equation}
where $<e_0,T_i>=i_{e_0} T_i$.

The second term can be written as
\begin{equation}\label{11}\begin{split}
         2 \int_V i_\xi A^{ki} (A_{\ k}^0\wedge \Sigma_{0i})=2 \int_V <-Ne_0, A^{ki}><e_i, A_{\ k}^0> e^1\wedge e^2\wedge e^3\\
         =\int_V -N <e_0, A^{ki}>(<e_i, A_{\ k}^0>-<e_k, A_{\ i}^0>) e^1\wedge e^2\wedge e^3.
\end{split}\end{equation}
Since the connection 1-form fields are given by
\begin{equation}\label{11a}
    A_I^{\ J}=e_I^c \nabla_a e^J_c dx^a,
\end{equation}
one can get
 \begin{equation}\label{12}\begin{split}
   <e_i, A_{\ k}^0>-<e_k, A_{\ i}^0>=-(e^a_i e^c_k \nabla_a e^0_c-e^a_k e^c_i \nabla_a e^0_c)=-(e^a_i e^c_k \nabla_a e^0_c-e^c_k e^a_i \nabla_c e^0_a)\\
   =-e^a_i e^c_k (\nabla_a e^0_c-\nabla_c e^0_a)=-e^a_i e^c_k ({\rm d} e^0)_{ac},
\end{split}\end{equation}
since $e^0_a=-N (dt)_a$, one can get $d e^0=-d N\wedge dt, e_i^0=0$, so this term is 0.

The bulk term can be written as
\begin{equation}\label{13}\begin{split}
  \int_V \Sigma_{IJ} \wedge i_\xi {\rm d}A^{IJ}-{\rm d}\Sigma_{IJ} \wedge i_\xi A^{IJ}=\int_V N (T_0 -e^i \wedge <e^0,T_i>)\equiv E,
\end{split}\end{equation}
where $E$ can be considered as the energy of the system.
\subsection{The boundary term}
Next we consider the boundary term. We choose the boundary $\partial V$ to be $N=constant$ surface within $t=constant$ surface \cite{padholo1}.
Define the acceleration vector $a^c=u^b \nabla_b u^c$, which satisfy $a^b u_b=0$, so we can choose $e_c^1=\frac{a_c}{\sqrt{\|a^c a_c\|}}=\frac{a_c}{a}$.
On the other hand,
\begin{equation}\label{15}
    a_c=h_c^b \nabla_b N/N \circeq 0,
\end{equation}
where $\circeq$ means the equalities on $\partial V$, so we have
\begin{equation}\label{16}
    e^1 \circeq 0.
\end{equation}
Thus the no zero covielbein on $\partial V$ are $e^2,e^3$. The boundary term is
\begin{equation}\label{14}\begin{split}
    \int_{\partial V} \Sigma_{IJ} \wedge i_\xi A^{IJ}=2\int_{\partial V} \Sigma_{01} \wedge i_\xi A^{01}
    =2\int_{\partial V} <-N e_0, A^{01}> e^2 \wedge e^3\\
    =2\int_{\partial V} -N (e^a_0 e^c_1 \nabla_a e^0_c) e^2 \wedge e^3=2\int_{\partial V} -N \sqrt{\|a^c a_c\|} e^2 \wedge e^3
    =2\int_{\partial V} -N a e^2 \wedge e^3=-2\int_{\partial V} N a \sqrt{\sigma}d^2 x.
\end{split}\end{equation}

So the final result is
\begin{equation}\label{15}\begin{split}
  \int_V \Sigma_{IJ} \wedge L_\xi A^{IJ}=\int_{\partial V} -2 N a \sqrt{\sigma}d^2 x+\int_V N (T_0 -e^i \wedge <e^0,T_i>).
\end{split}\end{equation}

Define the surface and bulk degrees of freedom,
\begin{equation}\label{16}
    N_{sur}=\int_{\partial V}\frac{\sqrt{\sigma}d^2 x}{G}=8\pi\int_{\partial V}\sqrt{\sigma}d^2 x;\quad N_{bulk}=\frac{E}{(1/2) T_{avg}},
\end{equation}
then the time evolution of spacetime can be written as
\begin{equation}\label{17}\begin{split}
  -\int_V \Sigma_{IJ} \wedge L_\xi A^{IJ}=\frac{1}{2} T_{avg} (N_{sur}-N_{bulk}),
\end{split}\end{equation}similar to Eq.(\ref{1}).
\section{Conclusion}
In this paper, the main result is the Eq.(\ref{17}), which states that the time evolution of the spacetime is driven by the departure from the holographic equipartition. It has the similar structure as that from the metric formulism. In all static spacetime, the time evolution is frozen, so maintain the holographic equipartition.

\acknowledgments
The author would like to thank Dr. Yu Han and Dr. Molin Liu for many help.


\section*{Results}
\subsection*{Multiplex network construction and analysis}

\begin{figure*}[ht]
\centering
\includegraphics[width=17cm]{Fig1}
\caption{(a) Visualisation of part of the multiplex network representing a toddler's lexicon. (b) Visualisation of an example of the MLN as an edge coloured network. Both (a) and (b) include only 24 of the 529 nodes/words in the whole MLN. (c) Degree correlations across layers quantified by the Kendall Tau. (d) Multiplexity or edge overlap among different layers relative to expectations from configuration models. (e) Reducibility dendrogram for the MLN. The MLN is irreducible: its layers are so different from each other that aggregating any of them would lead to a loss of information about topological patterns.}
\label{fig:visua}
\end{figure*}

We first construct a multiplex lexical network composed of four layers capturing i) free associations from the South Florida association norms \cite{nelson2004university}, (ii) feature sharing from the McRae et al. dataset \cite{mcrae2005semantic}, (iii) co-occurrence in child-directed speech from  the CHILDES dataset \cite{macwhinney2000childes}, and (iv) phonological similarities from WordNet 3.0 \cite{vitevitch2008} (cf. Methods and SI Sect. 2). Hence the resulting MLN properties emerge from the assembly of independent measures rather than from a multiplex network design. Figures~\ref{fig:visua} (a) and (b)  provide a visualisation of the links in each of the four MLN layers. Panel (a) treats each layer as separate whereas panel (b) describes the multiplex as an edge-coloured graph \cite{wasserman1994social}, in which different colours denote different relationships. As evident from (a) and (b), even if words might be disconnected on one layer, they could be connected on the  MLN structure.

We report single-layer summary statistics and comparison to configuration models (i.e. random graphs preserving the degrees of an empirical network \cite{newman2010}) in Table~\ref{tab:1}. We focus on network features already analysed in previous works \cite{motter2002,sigman2002,stey2005large,vitevitch2008}: degree, clustering, degree mixing, connectivity ratio and mean shortest path length. For instance, the degree of a node counts its connections \cite{newman2010} and on the phonological layer, it coincides with the size of its phonological neighbourhood \cite{vitevitch2008,vitevitch2012}. See Methods and SI Sect. S3 for precise definitions and interpretations.

Tab.~\ref{tab:1} shows that the phonological layer has a smaller mean degree compared to other layers. Furthermore, apart from the association layer all other layers are highly fragmented. Their largest connected components include between 24.2\% and 62.4\% of the 529 words. These percentages quantify how many words could be reached from each other by navigating through links on individual layers. In contrast, the \textit{multiplex network} is connected \cite{dedomenico2014navigability} -- every pair of words is connected by a path that potentially exploits different relationship types. Compared to configuration models, except for the co-occurrence layer all other layers display higher clustering, non-zero assortativity and slightly larger path length in their largest connected component. In agreement with previous work \cite{gravino2012complex,sigman2002,vitevitch2014,beckage2015cognition} these patterns suggest that the MLN layers display a core-periphery structure. From a cognitive perspective this feature might possibly facilitate navigation from word to word within cores (see SI Sect. S3 for further discussion).  Layers also differ in their degree distributions, see SI Fig. S2: they are exponential-like for the synonym and phonological layers but much more heavy-tailed for the co-occurrence and association layers. Heavy tails indicate the presence of network hubs, i.e. words which are significantly more connected than average. These hub words play a central role for navigation through concept space \cite{sigman2002,motter2002,gravino2012complex} and could therefore be good candidates for earlier acquisition.

Is it appropriate to represent the ML in terms of four separate layers or
can we get the same type of topological information with fewer layers? Structural reducibility analysis \cite{de2015structural} can test if multiplex layers can be aggregated without losing information (see SI for details). Results reported in Fig.~\ref{fig:visua} (e) show that aggregation cannot be performed without information loss, demonstrating that the chosen 4-layer representation is in fact \textit{irreducible} \cite{de2015structural}. This is not to say that each layer plays a role in language acquisition, just that the information encoded in each layer is different from all other layers.

Before turning to modeling word acquisition, we investigate the MLN structure in more detail. Specifically, Fig.~\ref{fig:visua} (c) analyses the similarity between degrees of a word on different layers. We find that words in the feature and co-occurrence layers tend to have negative degree correlations (Kendall Tau $\kappa \approx -0.16, p<0.0001$), indicating that hubs in one layer tend to have lower degrees in the other layers. This may suggest a type of semantic differentiation \cite{stey2005large} in English in which words that have similar features tend to not be used in close proximity of each other, at least when speaking to
young children. In contrast, the co-occurrence and phonological layers display positive degree correlations (Kendall Tau $\kappa \approx 0.27, p<0.0001$): in the children's lexicon, words having many co-occurrences also have larger phonological neighbourhoods, further supporting the idea that phonological similarities and co-occurrences in child directed speech
influence each other \cite{macwhinney2000childes,wiethan2014early}.

Another question of interest is to what extent links overlap across layers. This can be quantified by edge overlap (or multiplexity
\cite{gemmetto2015multiplexity}). Results are reported in
Fig.~\ref{fig:visua} (d). As expected, we find some overlap between
connections in the feature, co-occurrence and association layers; these layers capture semantic aspects of the ML. Beyond the overlap between these layers,
links tend not to overlap significantly more than one would expect in configuration model across the other layers. This suggests that different MLN layers tend to capture
different relational aspects of the ML, again emphasising that the MLN is a more complete model than single network representations. We now explore the importance of individual layers and of the MLN  as a whole in explaining acquisition trajectories.

\begin{table*}
\footnotesize
\caption{Metrics for the MLN layers with $N=529$ nodes, listing mean degree $\left\langle k \right\rangle$, mean clustering coefficient $CC$, assortativity coefficient $a$, percentage of nodes in the largest connected component $Conn.$, and mean shortest path length of the largest connected component $\left\langle
d\right\rangle$. The quantities are measured for the layers of the MLN and for randomized equivalents with the same degree sequences (denoted with CM). Error bars represent standard deviations and are reported in brackets behind the last significant digit.}
\label{tab:1}
\begin{tabular}{p{3cm}p{0.5cm}p{0.5cm}p{0.8cm}p{0.8cm}p{0.8cm}|p{0.9cm}p{1.1cm}p{1.4cm}p{1.1cm}}
\hline\noalign{\smallskip}
Empirical Network & $\left\langle k \right\rangle$ & $CC$ & $a$ & $Conn.$ & $\left\langle d\right\rangle$ & $CC\,(CM)$ & $a\,(CM)$ & \textit{Conn.} (CM) & $\left\langle d\right\rangle \,(CM)$\\
\hline\noalign{\smallskip}
\rule{0pt}{1em}Associations (Asso.) & 9.3  & 0.20  & -0.1 & 99.6\% & 3.2 &  0.03(1) &  $-0.01(6)$ &  99.6\% & 3.00(1)\\
\rule{0pt}{1em}Feature Norms (Feat.)    & 9.0 & 0.63 & -0.01 & 24.2\% & 1.8 &  0.38(2) & $-0.07(6)$  &  24.2\% & 1.72(1) \\
\rule{0pt}{1em}Co-occurrences (Co-occ.) & 8.1 & 0.69 & -0.44 & 62.4\% & 2.2 & 0.75(3)&  $-0.40(2)$ & 62.4\% & 2.19(1) \\
\rule{0pt}{1em}Phonological Sim (Phon.) & 1.31 & 0.37  &  0.48 & 33.1\% & 7.7 & 0.02(1) & $0.03(2)$ & 45.5\%(8) & 5.31(7) \\
\rule{0pt}{1em}Multiplex Aggregate      & 26.5 & 0.33 & -0.07 & 100\% & 2.4 & 0.18(5) &  $-0.10(8)$ & 100\% & 2.25(1) \\
\noalign{\smallskip}\hline\noalign{\smallskip}
\end{tabular}
\end{table*}

\subsection*{Multiplex Orderings: Results and Discussion}

Here we explore the process of word learning through the MLN assuming a
preferential acquisition scenario \cite{hills2009longitudinal},
where words are learned earlier if they are central in the
language environment. We assume that relevance of the language environment
can be summarised by connectivity in a language network \cite{sigman2002,motter2002,baronchelli2013,beckage2015cognition} rather than making assumptions on the statistics of relationships to infer relevance, as is more standard in a Bayesian approach \cite{xu2007word,frank2009using}.

We generate a word acquisition ordering $\tau$ by ranking words according to measures computed on the MLN. We assume that if one ranking is predictive, it would indicate that the feature generating it is relevant to early language learning. We compare MLN-based orderings to those based on non-relational, word-specific information such as word frequency and word length. For consistency with the literature, we investigated features previously considered in linguistic networks such as word degree \cite{stey2005large,beckage2011,vitevitch2014}, closeness \cite{motter2002,sigman2002}, betweenness \cite{borge2010,motter2002,sigman2002} and PageRank \cite{griffiths2007google}. For more details see Methods and SI Sect. S6.

We compare our orderings against an ensemble of empirical age of acquisition orderings, obtained from a probabilistic interpretation of the normative age of acquisition of words based on the MacArthur-Bates Communicative Development Inventory\cite{macwhinney2000childes} (CDI) and over a population of roughly 1000 toddlers (see Methods). The comparison is performed by computing the average word overlap $O(\tau,t)$ of ordering $\tau$ with normative orderings, namely how many words $\tau$ correctly predicts as learned until the inventory includes $t$ words. Word \textit{gains} are then obtained by subtracting $O(\tau,t)$ from the expected number of correctly predicted words by random guessing (see Methods and SI Sect. S6). Word gains are normalised by the inventory size $t$ and their Z-scores relative to statistics from random guesses are estimated. Positive \textit{vocabulary normalised word gain} indicates better than random performance of ordering $\tau$ and negative values indicate performance inferior to random guessing.

Fig.~\ref{fig:orde} reports normalised word gains (a) and their Z-scores (b) for the best performing orderings from our analysis. No ordering always outperforms the others: we notice shifts in which word features are the most relevant for different periods of word learning. This agrees with the idea that the progression of acquisition changes over the course of development: children learn some initial words and then tend to generalise those words based on network connectivity later, i.e. preferential acquisition \cite{hills2009longitudinal}. This cognitive interpretation of the observed shifts at different acquisition stages allow us to distinguish at least three distinct learning phases. In a first stage, comprising months 19 and 20, which we call the \textit{very early learning stage} (VELS), we are trying to predict the first 40 learned words (grey overlays in Fig.~\ref{fig:orde}). Direct sampling \cite{grimmett2001probability} for this period indicates that our results are below the 2.5\% threshold for statistical significance -- the network appears to contain little information relevant for predicting acquisition.
This phase is followed by an
\textit{early learning stage} (ELS) covering an age range between 20 and 23 months. This phase is characterised by \textit{closeness centrality outmatching} every other ordering (see also SI Sect. S6). Last we discriminate a \textit{late learning stage} (LLS) comprising ages between 23 and 28 months. During this stage the dominant hub words have already been learned and more localized structure is likely affecting learning. LLS is characterised by degrees in the association layer and frequency performing equally to or slightly better than closeness and other word features (cf. SI Sect. S6).

Interestingly, while previous work has found frequency to be a good predictor for normative age of acquisition \cite{kuperman2012age}, results in Fig.~\ref{fig:orde} suggest that word length and some topological network information are more predictive of early acquisition ordering. Good performance is achieved by word length in ELS, possibly because of a \textit{least effort effect} \cite{icancho2003} that suggests that short words are easier to memorise and learn. This hypothesis is also supported by the observation that word length loses its predictive
power at later learning stages (word gain Z-scores are compatible with random fluctuations after 300 words have been learned). We interpret this happens when more sophisticated learning
strategies are being used. One of them might be mediated by degree orderings. Among the four layers, ordering words according to their degree in the association layer gives the best performance and it can be up to 100\% more predictive than random guessing (cf. SI Fig. S7). This confirms previous results suggesting that association norms are generally good predictive models for early language learning \cite{hills2009longitudinal,stey2005large,beckage2015modeling}. We
conjecture associations perform well in our case because they are strongly related with semantic memory
\cite{nelson2004university,zock2015words,dedeyne2008network}.

Previous work has pointed out that in early learning, during VELS and ELS, it is very difficult to outperform random guessing because children may not have a clear strategy for learning new words early in language acquisition \cite{beckage2015modeling}. Instead here we find that better than random prediction is possible even in very early learning stages, at least for normative acquisition. Using the multiplex closeness of words it is possible to predict up to 160\% words more than at random (cf. SI Fig. S7) and up to 25\% more than by using degrees in the association layer (cf. SI Fig. S8). As reported in SI Sect. S6, we checked that multiplex closeness consistently outperforms every single-layer orderings during early learning stages. This is a promising result in that multiplex approaches may allow us to quantify learning strategies in toddlers. Also other multiplex measures such as versatile PageRank \cite{dedomenico2015ranking} perform up to 10\% better than degrees in the association layer (cf. SI Fig. S8). The enhanced prediction ability of multiplex features indicates that the multiplex representation of the ML captures meaningful influences of multiple types of feature representations. Altogether, we can conclude that early learning is strongly related to the multiplex structure, specifically the closeness of words considering \emph{all} layers that form the MLN.

Results for the LLS show a reversal of trends. Here we find
that a single layer based on association degree ordering gives best predictability. Global and local multiplex measures, as well as word specific features such as word frequency, perform similarly or slightly worse until 400 words have been learned (see Fig~\ref{fig:orde} and SI Fig. S8). This indicates that preferential acquisition is very important, but at this point in development the dominant
relevant relationships are those captured by the association layer. This is
compatible with the observed emergence of semantic learning in children
\cite{wiethan2014early}. However it has to be noticed that statistical significance deteriorates markedly during later stages of learning  making comparisons of performance in the LLS difficult.

\begin{figure*}[ht]
\centering
\includegraphics[height=4.9cm]{Fig2}
\caption{Left: Vocabulary normalised word gains for different orderings: shorter words first (Short Len.), words with higher degree in the association layer first (Deg. Asso.), closer words on the whole MLN first (Clos. Multiplex), more frequent words first (Freq. Child.) and higher multiplex Page Rank first (PageR. Multiplex). A normalised word gain of $0.20$ means that 20\% of words in the vocabulary have been predicted by the ordering strategy on top of expectations from random guessing. Higher word gains indicate better predictability. Right: Statistical significance indicated by word gain Z-score of the respective orderings. The distribution of the random overlaps can be approximated by a Gaussian after 60 words have been acquired (see SI Sect. S5). In this range, represented by the black dashed line, a score $Z\geq 1.96$ denotes word acquisition patterns that are different from random fluctuations with a 2.5\% significance level.
In both plots, error bars are the same size as the dots. Best performing orderings are
highlighted with different overlays, which identify different learning
stages: VELS (in grey), ELS (in light purple) and LLS (in white). Direct sampling was used in VELS for testing the statistical significance of results.}
\label{fig:orde}
\end{figure*}

So far, we evaluated orderings based on single network layers and the combined
multiplex, showing that prediction performance can benefit from taking
account of information from multiple layers. In this analysis we assumed that each layer plays an equal role. In the next section we evaluate the changing
influence of layers during the evolution of the lexicon.

\subsection*{Optimisation of layer influences}

\begin{figure*}[ht!]
\centering

\includegraphics[width=14.8cm]{Fig3}
\caption{Top (a-d): Optimisation results for the original MLN. (a,b): Vocabulary normalised word gains corresponding to the optimal layer influences at the end of VELS (black), middle of ELS (blue), and middle of LLS (pink) for degree optimisation (a) and closeness optimisation (b). Error margins represent standard deviations over randomised ensembles. In (b) no optimisation of degree outperforms multiplex closeness during ELS. (c,d): Average optimal layer weights indicating the influence or importance of layers over different learning stages obtained from Monte Carlo experiments with degree (c) and closeness (d) optimisation. The phonological layer resulted in influences around $10^-3$. The same optimisation trends were obtained when the phonological layer was excluded from the optimisation. Bottom (e,f): For comparison, optimal layer weights for the MLN where rather than the phonological layer with 529 words an extended one with 30,000 words is used, instead. Considering the extended phonological layer leads to word gains at least 6\% better than (a) and (b) (cf. SI Table 3).}
\label{fig:dego}
\end{figure*}

To explore the influence of different layers on word acquisition, we consider linear combinations of word features on each layer in order to obtain weighted multiplex measures (cf. Methods section). For a given network metric, we optimise the coefficients of the linear combinations to maximise vocabulary normalised word gains. The resulting layer weights, that maximise predictability, indicate the influence of the respective layers on word acquisition. We explored several types of optimisation, based on degree, closeness, betweenness and local clustering (cf. SI Sect. S7 and SI Tab. S3). We focus on the two best performing quantities from the ordering experiments, namely degree and closeness.

In order to avoid over-fitting, we perform a Monte Carlo robustness analysis: we optimise over subsets of word trajectories sampled uniformly at random, consisting of  only 80\% of the original words. Averages are computed over these trajectories and over different realisations of the age of acquisition trajectories from the normative age of acquisition ordering. We also confirmed that the improvement in performance of optimised multiplex parameters is strongly dependent on the structure and overlap of layers, as experiments on randomised multiplex networks result in far smaller word gains (see SI Sect. S8).

Optimisation results (cf. Fig. \ref{fig:dego}) indicated negligible contribution of the phonological layer, with weights ($\approx ~ 10^{-3}$). Degree and closeness orderings based only on the phonological layer perform poorly as well, yielding word gains compatible with random fluctuations at a 5\% significance level (see SI Sect. S6.1 and SI Fig. S5). We retrieved the same optimisation results for the other layers when the phonological layer was excluded. In addition, we considered phonological word scores coming from an "extended" phonological layer for adults, already analysed by Stella and Brede \cite{stella2015phonological} and including 30000 words (see also SI Sect. S6.1.1). Assessing the influence of adults' phonology over word acquisition in toddlers matches previous approaches in the relevant literature \cite{carlson2014children} and we present results in our MLN framework in Fig. \ref{fig:dego} but also in SI Sect. S7.

Optimal layer influences are displayed as a function of age for the MLN layers in Fig. \ref{fig:dego} (c) and (d). Similar patterns of layer influence are found for rankings based on both degree and closeness. We see a clear distinction between different learning stages. When degree is considered, cf. Fig. \ref{fig:dego} (c), in VELS the main layer
contributions stem from the association and the feature norm layers. Instead, when optimising closeness, cf. Fig. \ref{fig:dego} (d), in VELS all layers are found to contribute equally. In both cases the ELS, the next learning stage, marks  a transition region between the VELS (before) and the LLS (after) in which only the association layer dominates. This transition is what motivated our choice of distinguishing between VELS and ELS. For degree-based optimisations, contributions from the co-occurrence layer become very small in the LLS, while associations contribute 80\% of weight. An analogous transition is observed in the ELS phase when closeness is optimised and after that associations make up 80\% of the total layer influence. The dominant influence of associations in later stages of learning is indicative of the emergence of preferential acquisition \cite{hills2009longitudinal} that we already observed in ordering experiments.

When extended phonology is considered, in Fig. \ref{fig:dego} (e) and (f), the influences of semantic layers remain consistent, however, phonology has a higher impact when phonological neighbourhood size/degree is considered rather than closeness. In VELS the extended phonology has importances similar to co-occurrences but the influence of both approaches 0 later in development.

In Fig. \ref{fig:dego} (a) and (b) we compare vocabulary normalised word gains of trajectories based on optimal layer influences against our ordering experiments (cf. SI Fig. S9 for the respective Z-scores and previous section). On the one hand, when predicting only words learned in VELS, the optimal influence orderings outmatch both degree in the association layer and multiplex closeness during VELS but perform worse at later stages. Direct sampling indicates that these results are significant with a p-value of $0.01$. Optimal influences up to the middle of ELS and LLS provide similar word gains, which are both up to 25\% higher than the optimal word gains from VELS. This suggests that the \textit{same learning strategies} may be adopted \textit{after} VELS, starting in ELS and lasting throughout LLS. On the other hand, results in Fig.~\ref{fig:orde} (a) highlight the
importance of closeness centrality for predicting word acquisition at early
stages. In fact, in ELS even the optimal linear combination of degrees results in \textit{smaller word gains} compared to the unweighted multiplex closeness centrality. Optimal linear combinations of closeness perform even better than the unweighted multiplex closeness, see Fig.~\ref{fig:orde} (b). Notice that closeness is a \textit{global} network feature, accounting for the position of a node relative to all other nodes. This is distinct from \textit{local} features, such as degree, which only measure a node's relationship to its first neighbours. Our findings give support to the hypothesis that, particularly in the early learning stages, word learning is influenced by the global structure of the multiplex lexical network. This global multiplex structure is able to capture some important word patterns that influence early lexicon development.

\section*{Conclusions and future work}

Introducing the framework of \textit{multiplex lexical networks} (MLN), we have described and analysed normative word acquisition patterns of children between the ages of 19 and 28 months. Our approach considers semantic, phonological and syntactic contexts and captures more linguistic information than separate analysis of any single layer network previously could \cite{beckage2011,beckage2015modeling,dedeyne2008network,hills2009longitudinal}. We go beyond a purely topological description by exploiting network
properties to predict the order of normative word learning in children.
Interestingly, we find that the best topological feature in predicting word learning changes through the course of development. This allows us to use network information to distinguish three stages of learning: (i) a very early learning stage where all but the phonological layer contribute substantially to prediction, (ii) an early
learning stage which marks a transition period, and (iii) a late learning
stage in which contribution from word associations dominates word learning. We believe the last point is due to free associations serving as a much better proxy for detecting superordinate words compared to other network features (cf. SI Sect. 6.3 for a quantitative discussion). Further assessment of the extent to which the taxonomic organization serves as a mediator variable influencing word prediction is an interesting direction for future work.

Comparing the predictive power of various MLN features over time
confirms: (i) the superiority of some multiplex network characteristics
relative to single layer networks and word specific measures such as frequency or word length, and (ii) the special role closeness centrality might play in early word learning. This is emphasised in two ways: (i) strong performance of multiplex closeness, outperforming all combinations of
local network features in the early learning phase, and (ii) the best overall predictions of the order words are learned is related to a weighted multiplex version of single-layer closeness centralities. We thus find strong indications that, particularly at early stages of learning, word acquisition in children is  driven by minimising relational distances of learned words relative to other words in both the semantic and syntactic space of the mental lexicon.

With the MLN, we explored questions about normative lexical acquisition,
uncovering developmental learning stages and quantifying the influence of
certain types of linguistic information on early acquisition. Nevertheless, our MLN is limited in important ways. It is important to bear in mind that the MLN
representation is only a projection of an individual child's full ML. Additionally, the results presented in this paper consider normative lexical acquisition. That is to say, a specific child may not learn words in the same order as the normative orderings. Instead normative order is obtained by averaging over roughly 1000 productive vocabulary reports. We attempt to address this shortcoming by sampling multiple orders probabilistically from these norms. Extending the model and testing the universality of the learning strategies in VELS and ELS on longitudinal data for individual children would be an interesting future research direction \cite{aitchison2012}.

Another limitation is the use of a relatively small vocabulary. While the CDI is a commonly used check list of words a child produces, there are many words that a child may know which are not on the CDI. By expanding our model to the full vocabulary of a child, and for longer periods of development, we can further increase our understanding of word learning.

While the present study focuses on word learning in English, results should be corroborated by considering word learning in different languages. Future work can extend our analysis by considering correlations in word learning across other cognitive and linguistic domains to build an even richer picture of language organisation and learning than presented here. A stream of work in psycholinguistics has explored detailed mechanisms of word learning \cite{xu2007word}. Such work typically explores how words are memorised when clues are presented in different order and focuses on the underlying mechanisms of inferring meaning-object mappings, pointing out that learning is strongly dependent on context. Integrating context-dependent information in our MLN framework would surely be an exciting future research direction for investigating individual children's learning trajectories.

The marginal influence of the original phonological layer found in this study can be reconciled with previous findings. Dautriche \textit{et al.}\cite{dautriche2015learning} showed that 18 months old toddlers failed to learn an object label when it was a phonological neighbour of a noun they already knew. In our dataset 80\% of words learned by toddlers within the first two months are nouns. This noun-richness is in opposition with orderings extracted from phonological degree and closeness, which identify mainly non-noun words, verbs in particular, as learned initially. This trend is not surprising, as having learned a verb earlier makes it easier for toddlers to learn its phonological neighbours \cite{dautriche2015learning}. However, this contrast in noun-richness at early development stages reflects in the poor performance of the original phonological layer in predicting normative acquisition ordering. Nonetheless, we show that phonology influences word acquisition by considering a phonological network extended to the adults' lexicon, like in \cite{carlson2014children}. This extended layer identifies nouns as early candidates for learning and provides significant prediction results. This interplay between phonology and acquisition is in agreement with previous findings in the relevant literature \cite{carlson2014children,stamer2012,vitevitch2012,vitevitch2014}.

We have shown strong evidence that multiplex lexical networks
capture a richer picture of the mental lexicon than previous works using only single-layer networks, in spite of the above limitations. More importantly, this work provides novel formalised methods for exploring and explaining the influence of linguistic features on early acquisition.

\section*{Methods}
\subsubsection*{Age of acquisition dataset}

Age of acquisition orderings are constructed based on the MacArthur-Bates
Communicative Development Inventory (CDI) norms \cite{Dale1996}. The CDI,
based on parent report of the productive vocabulary of children aged between
16 and 30 months, has been shown to be related to future language ability
in young children \cite{Dale1996,Fenson1994}. The norms are averaged over
more than 1000 vocabulary reports and indicate the percentage of children,
at a given age, that reportedly produce (and understand) a specific word.
From these norms, we sample orderings of word learning. For example, "mommy" and "ball"
are reported as produced by 93\% and 64\% of children by 16 months, respectively; these words are (usually) learned earlier than "chair" which is produced by only
14\% of 16 month olds. We assume a word is known once 50\% of children in a
given month produce that word. We then sample an order of words learned within a month assuming that higher rates of production probabilistically indicate earlier learning. Starting from position one of the ranking, we: (i) sample a learned word with probability proportional to the percentage of children which are able to produce it, conditioned on the overall production rate being over 50\%, (ii) erase it from the list of candidate words to be learned at later positions and (iii) proceed one position down in the ranking and start from (i). The sampling starts from month 16 and it stops when every word has been sampled. Note that a non-probabilistic version of this ordering has been used in other developmental modelling contexts \cite{hills2009longitudinal,beckage2015modeling}.

\subsubsection*{Construction of the multiplex network}

The four layers of the MLN were selected because of their use in previous single-layer
network studies investigating word learning of young children
\cite{beckage2011,beckage2015cognition,hills2009longitudinal,borge2010}. The
four layers we consider here are (i) a semantic layer based on the Florida
Free Association Norms \cite{nelson2004university} where a link exists from
word A to word B if word B is a free associate of the cue word A; (ii) a layer capturing feature similarity based on the McRae Feature Norms \cite{mcrae2005semantic} where
words A and B are connected if they share at least one semantic feature;
(iii) a layer based on word co-occurrences (measured in child-directed
speech \cite{macwhinney2000childes}) where words A and B are connected if
they co-occur more than 45 times, where the threshold 45 was chosen
approximately to match the link density of the other semantic layers; and a
(iv) layer capturing phonological similarities (based on IPA transcription
from  WordNet 3.0 \cite{miller1995wordnet}) where words A and B are connected if they have
IPA transcriptions with edit distance one. We treat the association
layer as undirected and edge weights in layers (i) to (iii) are ignored. The
resulting MLN is composed of 529 words which represent the intersection
between the CDI data and the set of words which have at
least one connection on any layer (see SI).

\subsubsection*{Cognitive interpretation of network metrics}

We investigate the same local and global features of words/nodes that were
investigated in previous works about network representations of
language: degree, closeness, betweenness and PageRank (see SI). In a given network, the degree of a node is the number of its links \cite{newman2010}. In our MLN, a word is characterised by one degree measure per layer. For instance, on the association layer a word with degree $k^{(Asso.)}$ has $k^{(Asso.)}$ associates. On the phonological layer the degree of a word coincides with its phonological neighbourhood size \cite{vitevitch2014}: a word with degree $k^{(Phon.)}$ has $k^{(Phon.)}$ similar sounding words. Higher degree words in semantic networks were found to have lower age of
acquisition norms \cite{stey2005large}, while degree on the phonological
layer correlated positively with word confusability \cite{vitevitch2012}. On the whole MLN, we can associate each word to its multidegree, namely the sum of its degrees on all the layers \cite{dedomenico2013math}. Fundamentally, the usefulness of measures such as degree would suggest that words with multiple associates, multiple phonological neighbors and multiple
shared features are those words that are learned earliest. The mechanisms
behind this phenomenon could be that words with many associates and shared
features are those words that are important in the language environment
because they play a central role or because they are important to the
parent or child. We remain agnostic as to the exact reason behind the
increased `importance' of a word, but suggest that it can be summarized by the degree.
Closeness relates to how fast information spreads from a node to others \cite{newman2010}. It is interesting for cognitive science since previous work showed that words closer on semantic topologies tend to be processed together in shorter time
\cite{collins1969retrieval,collins1975spreading,motter2002}. Betweenness captures the extent to which a node falls on the shortest path between pairs of words \cite{newman2010}. It captures centrality of words through a hypothetical navigation on the ML \cite{sigman2002,motter2002,borge2010} (cf. SI Sect. S6). PageRank identifies the likelihood of reaching a given node by a random walk in a network. High PageRank words on semantic networks were found easier to retrieve in fluency tasks \cite{griffiths2007google}. Closeness, betweenness and PageRank on multiplex networks exploit jumps through layers (cf. SI Sect. S6).

\subsubsection*{Overlap measures and word ranking}

A word trajectory is an ordered list $\tau=(w_1,w_2, ...,w_N)$ indicating
the exact order in which words are learned. We define ${\tau_{aoa}}$ to be the ensemble of
rankings derived from the CDI norms. We
sample each specific ordering $\tau_{aoa}$ based on the probability of production as reported in the age of acquisition norms.

Predicted word orderings are generated as follows. First, each word is
ranked according to a word score, $s_i$, which is derived from network
specific or extrinsic word features (e.g. frequency or word length). Words are
then ordered according to word score, starting with the largest score. Words
receive a position in the predicted trajectory according to their position
in the ordering of word scores. Ties in word orderings $s_i$ are taken into
account by averaging over all resolutions. For example, one might wish to
consider orderings based on degree in the association layer and would obtain
the following word scores $s_{food}=62$, $s_{water}=45$, $s_{eat}=20$. The
corresponding predicted acquisition trajectory would be
$\tau=(food,water,eat)$. Apart from the features mention in the main text of
the paper, we also considered many others (cf. SI Sect. 6).

To evaluate predictive performance of a word score, we first measure the
overlap $O(\tau,t)$ between the predicted learning trajectory
$\tau$ and the empirically known trajectory $\tau_{aoa}$ at time $t$ by
counting the number of words that co-occur in $\tau$ and $\tau_{aoa}$ up to
time $t$ and averaging over different $\tau_{aoa}$. We define the word gain $g(\tau,t)$ as the overlap minus random fluctuations, i.e.
\begin{equation}
\centering
g(\tau,t)=O(\tau,t) - \langle O(\tau_{ran},t) \rangle.
\end{equation}

The vocabulary size normalised word gains are computed as $G(\tau,t)=g(\tau,t)/t$ while the word gain Z-Scores consider deviations of overlaps from random guessing in terms of standard deviations $\sigma$, as $Z=g(\tau,t)/\sigma(O(\tau_{ran},t))$.

\subsubsection*{Calculating optimal combinations of layers}

To allow for varying influences of layers within the multiplex we construct word scores as convex
combinations of individual layer influence, i.e. a word score $s_w$ for
word $w$ is obtained as:
\begin{equation}
\centering
s_{w}=\alpha s_{w}^{(Asso)}+\beta s_{w}^{(Feat)}+ \gamma s_{w}^{(Co-occ)} + (1-\alpha-\beta-\gamma)s_{w}^{(Phon)},
\end{equation}
where $s_w^{(Asso)}$, $s_w^{(Feat)}$, $s_w^{(Co-occ)}$, and $s_w^{(Phon)}$
are word scores obtained from the respective single layer metrics
and the coefficients $\alpha$, $\beta$, $\gamma$ give the
influence of each layer on the overall word score $s_w$. This linear combination of
single-layer features is similar in spirit to previous decompositions of
multiplex centrality, see \cite{sola2013eigenvector}
and discussions in \cite{de2015structural}. The optimisation finds the influences $\alpha,\beta,\gamma$ that maximise vocabulary normalised word gain (either over the entire time period or over specific learning phases) after removing 20\% of the words
at random. 20$\%$ was chosen in order not to
remove too many words particularly in the very early word learning stages. Performance is evaluated on all words. Optimisation was performed using a differential evolution method \cite{price2006differential}. Averages are calculated over 50 configurations of left out words for 30 normative age of acquisition orderings.