# Groups elementary equivalent to finitely generated free metabelian

Olga Kharlampovich111CUNY, Graduate Center and Hunter College , Alexei
Miasnikov222Stevens Institute of Technology

We describe groups elementarily equivalent to a free metabelian group with $n$
generators.

###### Contents

  1. 1 Interpretability and bi-iterpretability
  2. 2 By-interpretation of a free metabelian group with $\mathbb{Z}$
    1. 2.1 Preliminaries for metabelian groups
    2. 2.2 ${\mathbb{Z}}$ is absolutely interpretable in $G$
    3. 2.3 Interpretation of ${\mathbb{Z}}$-exponentiation in $G$
    4. 2.4 Interpretation of ${\mathbb{Z}}\bar{G}$-module $G^{\prime}$ in $G$
    5. 2.5 Proof of Theorem 2
  3. 3 Groups elementarily equivalent to a free  metabelian group
  4. 4 $A$-metabelian groups

##  1 Interpretability and bi-iterpretability

One can use the model-theoretic notion of interpretability and bi-
iterpretability to study structures elementarily equivalent to a given one. In
this paper we are going to do this for free metabelian groups. We remind here
some precise definitions and several known facts that may not be very familiar
to algebraists.

A _language_ (or _a signature_) $L$ is a triple $(Fun,Pr,C)$, where
$Fun=\\{f,\ldots\\}$ is a set of functional symbols $f$ coming together with
their arities $n_{f}\in\mathbb{N}$, $Pr$ is a set of relation (or predicate)
symbols $Pr=\\{P,\ldots\\}$ coming together with their arities
$n_{P}\in\mathbb{N}$, and a set of constant symbols $C=\\{c,\ldots\\}$.
Sometimes we write $f(x_{1},\ldots,x_{n})$ or $P(x_{1},\ldots,x_{n})$ to show
that $n_{f}=n$ or $n_{P}=n$. Usually we denote variables by small letters
$x,y,z,a,b,u,v,\ldots$, while the same symbols with bars
$\bar{x},\bar{y},\ldots$ denote tuples of the corresponding variables, say
$\bar{x}=(x_{1},\ldots,x_{n})$. In this paper we always assume, if not said
otherwise, that the languages we consider are finite. The following languages
appear frequently throughout the text: the language of groups
$\\{\cdot,^{-1},1\\}$, where 1 is the constant symbol for the identity
element, $\cdot$ is the binary multiplication symbol, and -1 is the symbol of
inversion; and the language of rings $\\{+,\cdot,0\\}$ with the standard
symbols for addition, multiplication, and the additive identity $0$. Sometimes
we add the constant $1$ to form the language of unitary rings (a priori, our
rings are not unitary).

A structure in the language $L$ (an $L$-structure) with the base set $A$ is
sometimes denoted by $\mathbb{A}=\langle A;L\rangle$ or simply by
$\mathbb{A}=\langle A;f,\ldots,P,\ldots,c,\ldots\rangle$. For a given
structure $\mathbb{A}$ by $L(\mathbb{A})$ we denote the language of
$\mathbb{A}$. When the language $L$ is clear from the context, we follow the
standard algebraic practice and denote the structure $\mathbb{A}=\langle
A;L\rangle$ simply by $A$. For example, we refer to a field
$\mathbb{F}=\langle F;+,\cdot,0,1\rangle$ simply as $F$, or to a group
$\mathbb{G}=\langle G;\cdot,^{-1},1\rangle$ as $G$, etc. Sometimes we refer to
a first-order formula in a language $L$ as to an $L$-formula and denote by
${\mathcal{F}}_{L}$ the set of all $L$-formulas.

Let $\mathbb{B}=\langle B;L\rangle$ be a structure. A subset $A\subseteq
B^{n}$ is called definable in $\mathbb{B}$ if there is a formula
$\phi(x_{1},\ldots,x_{n})$ (without parameters) in $L(\mathbb{B})$ such that
$A=\\{(b_{1},\ldots,b_{n})\in
B^{n}\mid\mathbb{B}\models\phi(b_{1},\ldots,b_{n})\\}$. In this case we denote
$A$ by $\phi(B^{n})$ or $\phi({\mathbb{B}})$ and say that _$\phi$ defines $A$_
in $\mathbb{B}$. Similarly, an operation $f$ on the subset $A$ is definable in
$\mathbb{B}$ if its graph is definable in $\mathbb{B}$. A constant $c$ is
definable if the relation $x=c$ is definable. An $n$-ary predicate
$P(x_{1},\ldots,x_{n})$ is definable in $\mathbb{B}$ if the set
$\\{(b_{1},\ldots,b_{n})\in\mathbb{B}^{n}|P(b_{1},\ldots,b_{n})\ {\rm is\
true}\\}$ is definable in $\mathbb{B}$.

In the same vein an algebraic structure $\mathbb{A}=\langle
A;f,\ldots,P,\ldots,c,\ldots\rangle$ is definable in $\mathbb{B}$ if there is
a definable subset $A^{*}\subseteq B^{n}$ and operations $f^{*},\ldots,$
predicates $P^{*},\ldots,$ and constants $c^{*},\ldots,$ on $A^{*}$ all
definable in $\mathbb{B}$ such that the structure $\mathbb{A}^{*}=\langle
A^{*};f^{*},\ldots,P^{*},\ldots,c^{*},\ldots,\rangle$ is isomorphic to
$\mathbb{A}$. (Notice, that constants $c,\ldots$ belong to the language of
$\mathbb{A}$, they are not parameters.) For example, if $Z(G)$ is the center
of a group $G$ then it is definable as a group in $G$.

One can do a bit more in terms of definability. In the notation above if
$\sim$ is a definable equivalence relation on a definable subset $A\subseteq
B^{n}$ then we say that the quotient set $A/\sim$ is interpretable in
$\mathbb{B}$. Furthermore, an operation $f$ or a predicate $P$ on the quotient
set $A/\sim$ is interpretable in $\mathbb{B}$ if the full preimage of its
graph in $A$ is definable in $\mathbb{B}$. For example, if $N$ is a normal
definable subgroup of a group $G$, then the equivalence relation $x\sim y$ on
$G$ given by $xN=yN$ is definable in $G$, so the quotient set $G/N$ of all
right cosets of $N$ is interpretable in $G$. It is easy to see that the
multiplication induced from $G$ on $G/N$ is also interpretable in $G$. This
show that the quotient group $G/N$ is interpretable in $G$.

######  Definition 1.

An algebraic structure $\mathbb{A}=\langle
A;f,\ldots,P,\ldots,c,\ldots\rangle$ is absolutely interpretable (or
$0$-interpretable) in a structure $\mathbb{B}$ if there is a subset
$A^{*}\subseteq B^{n}$ definable in $\mathbb{B}$, an equivalence relation
$\sim$ on $A^{*}$ definable in $\mathbb{B}$, operations $f^{*},\ldots,$
predicates $P^{*},\ldots,$ and constants $c^{*},\ldots,$ on the quotient set
$A^{*}/{\sim}$ all interpretable in $\mathbb{B}$ such that the structure
$\mathbb{A}^{*}=\langle
A^{*}/{\sim};f^{*},\ldots,P^{*},\ldots,c^{*},\ldots,\rangle$ is isomorphic to
$\mathbb{A}$.

Now we introduce some notation. An interpretation of ${\mathbb{A}}$ in
${\mathbb{B}}$ is described by the following set of formulas in the language
$L({\mathbb{B}})$

$\Gamma=\\{U_{\Gamma}(\bar{x}),E_{\Gamma}(\bar{x}_{1},\bar{x}_{2}),Q_{\Gamma}(\bar{x}_{1},\ldots,\bar{x}_{t_{Q}})\mid
Q\in L({\mathbb{A}})\\}$

(here $\bar{x}$ and $\bar{x}_{i}$ are $n$-tuples of variables) which interpret
$\mathbb{A}$ in $\mathbb{B}$ (as in the definition 1 above). Namely,
$U_{\Gamma}$ defines in $\mathbb{B}$ a subset
$A_{\Gamma}=U_{\Gamma}(B^{n})\subseteq B^{n}$, $E_{\Gamma}$ defines in
${\mathbb{B}}$ an equivalence relation $\sim_{\Gamma}$ on $A_{\Gamma}$, and
the formulas $Q_{\Gamma}$ define functions $f_{\Gamma}$, predicates
$P_{\Gamma}$, and constants $c_{\Gamma}$ that interpret the corresponding
symbols from $L(\mathbb{A})$ on the quotient set $A_{\Gamma}/\sim_{\Gamma}$ in
such a way that the $L$-structure $\Gamma({\mathbb{B}})=\langle
A_{\Gamma}/\sim_{\Gamma};f_{\Gamma},\ldots,P_{\Gamma},\ldots,c_{\Gamma},\ldots\rangle$
is isomorphic to ${\mathbb{A}}$. Note, that we interpret a constant $c\in
L({\mathbb{A}})$ in the structure $\Gamma({\mathbb{B}})$ by the
$\sim_{\Gamma}$-equivalence class of some tuple $\bar{b}_{c}\in A_{\Gamma}$
defined in ${\mathbb{B}}$ by the formula $Q_{c}$. We write
$\mathbb{A}\simeq\Gamma(\mathbb{B})$ if $\Gamma$ interprets ${\mathbb{A}}$ in
${\mathbb{B}}$ as described above and refer to $\Gamma$ as an interpretation
code or just code. The number $n$ is called the dimension of $\Gamma$, denoted
$n=dim\Gamma$. By $\mu_{\Gamma}$ we denote a a surjective map
$A_{\Gamma}\to{\mathbb{A}}$ (here ${\mathbb{A}}=\langle
A;L({\mathbb{A}})\rangle$) that gives rise to an isomorphism
$\bar{\mu}_{\Gamma}:\Gamma({\mathbb{B}})\to\mathbb{A}$. We refer to this map
$\mu_{\Gamma}$ as the _the coordinate map_ of the interpretation $\Gamma$.
Sometimes we cal the relation $\sim_{\Gamma}$ the _kernel_ of the coordinate
map $\mu_{\Gamma}$ and denote it by $\ker(\mu_{\Gamma})$. Finally, notation
$\mu:{\mathbb{B}}\rightsquigarrow{\mathbb{A}}$ means that ${\mathbb{A}}$ is
interpretable in ${\mathbb{B}}$ with the coordinate map $\mu$. We use this
notation throughout the paper.

More generally, the formulas that interpret $\mathbb{A}$ in $\mathbb{B}$ may
contain elements from $\mathbb{B}$ that are not in the language
$L(\mathbb{B})$, i.e., some parameters, say $p_{1},\ldots,p_{k}\in B$. In this
case we assume that all the formulas from the code $\Gamma$ have a tuple of
extra variables $\bar{y}=(y_{1},\ldots,y_{k})$ for parameters in
${\mathbb{B}}$:

$\Gamma=\\{U_{\Gamma}(\bar{x},\bar{y}),E_{\Gamma}(\bar{x}_{1},\bar{x}_{2},\bar{y}),Q_{\Gamma}(\bar{x}_{1},\ldots,\bar{x}_{t_{Q}},\bar{y})\mid
Q\in L(\mathbb{A})\\}$ (1)

so that after the assignment $y_{1}\to p_{1},\ldots,y_{k}\to p_{k}$ the code
interprets $\mathbb{A}$ in $\mathbb{B}$. In this event we write
$\mathbb{A}\simeq\Gamma(\mathbb{B},\bar{p})$ (here
$\bar{p}=(p_{1},\ldots,p_{k})$), and say that $\mathbb{A}$ is interpretable in
$\mathbb{B}$ by the code $\Gamma$ with parameters $\bar{p}$. In the case when
$\bar{p}=\emptyset$ one gets again the absolute interpretability.

We will say that a subset $D\subseteq A_{\Gamma}/\sim_{\Gamma}$ is definable
in ${\mathbb{B}}$ if its full preimage in $A_{\Gamma}$ is definable in
${\mathbb{B}}$. More generally, a subset
$D\subseteq(A_{\Gamma}/\sim_{\Gamma})^{m}$ is definable in ${\mathbb{B}}$ if
its full preimage in $A_{\Gamma}^{m}$ under the natural projection
$A_{\Gamma}^{m}\to(A_{\Gamma}/\sim_{\Gamma})^{m}$ is definable in
${\mathbb{B}}$.

We say that a structure $\mathbb{A}$ is interpreted in a given structure
$\mathbb{B}$ _uniformly_ with respect to a subset $D\subseteq B^{k}$ if there
is a code $\Gamma$ such that $\mathbb{A}\simeq\Gamma(\mathbb{B},\bar{p})$ for
every tuple of parameters $\bar{p}\in D$. If $\mathbb{A}$ is interpreted in
${\mathbb{B}}$ uniformly with respect to a 0-definable subset $D\subseteq
B^{k}$ then we say that ${\mathbb{A}}$ is _regularly interpretable_ in
${\mathbb{B}}$ and write in this case
${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\phi)$, provided $D$ is defined by
$\phi$ in ${\mathbb{B}}$. Note that the absolute interpretability is a
particular case of the regular interpretability where the set $D$ is empty.

Now we discuss a very strong version of mutual interpretability of two
structures, so-called bi-interpretability.

######  Definition 2.

Two algebraic structures ${\mathbb{A}}$ and ${\mathbb{B}}$ are called bi-
interpretable (with parameters) in each other if the following conditions
hold:

  * 1)

${\mathbb{A}}$ and ${\mathbb{B}}$ are interpretable (with parameters) in each
other, so ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},p)$ and
${\mathbb{B}}\simeq\Delta({\mathbb{A}},q)$ for some codes $\Gamma$ and
$\Delta$ and tuples of parameters $p,q$. By transitivity ${\mathbb{A}}$, as
well as ${\mathbb{B}}$, is interpretable (with parameters) in itself, so
${\mathbb{A}}\simeq(\Gamma\circ\Delta)({\mathbb{A}},p^{\ast})$ and
${\mathbb{B}}\simeq(\Delta\circ\Gamma)({\mathbb{B}},q^{\ast})$, where $\circ$
denotes composition of interpretations and $p^{\ast}$, $q^{\ast}$ the
corresponding parameters.

  * 2)

There is a formula $\theta_{\mathbb{A}}(\bar{u},x,\bar{s})$ in the language
$L({\mathbb{A}})$ such that $\theta_{\mathbb{A}}(\bar{u},x,p^{*})$ defines in
${\mathbb{A}}$ the isomorphism
$\bar{\mu}_{\Gamma\circ\Delta}:(\Gamma\circ\Delta)({\mathbb{A}},p^{\ast})\to{\mathbb{A}}$
(more precisely, it defines the coordinate map
$\mu_{\Gamma\circ\Delta}:A_{\Gamma\circ\Delta}\to A$). Similarly, there is a
formula $\theta_{\mathbb{B}}(\bar{v},x,\bar{t})$ in the language
$L({\mathbb{B}})$ such that $\theta_{\mathbb{B}}(\bar{v},x,q^{*})$ defines in
${\mathbb{B}}$ the isomorphism
$\bar{\mu}_{\Delta\circ\Gamma}:(\Delta\circ\Gamma)({\mathbb{B}},q^{\ast})$
(more precisely, it defines the coordinate map
$\mu_{\Delta\circ\Gamma}:B_{(\Delta\circ\Gamma)}\to B$).

Algebraic structures ${\mathbb{A}}$ and ${\mathbb{B}}$ are called 0-bi-
interpretable or absolulutely by-interpretable in each other if in the
definition above the tuples of parameters $p$ and $q$ are empty.

Unfortunately, 0-bi-interpretability is rather rare. Indeed, the following
result puts quite strong restrictions on such structures.

######  Lemma 1.

[3] If ${\mathbb{A}}$ and ${\mathbb{B}}$ are 0-bi-interpretable in each other
then their groups of automorphisms are isomorphic.

Fortunately, there is a notion of regular bi-interpretability, which is less
restrictive, occurs more often, and which enjoys many properties of 0-bi-
iterpretability.

######  Definition 3.

Two algebraic structures ${\mathbb{A}}$ and ${\mathbb{B}}$ are called
regularly bi-interpretable in each other if the following conditions hold:

  * 1)

${\mathbb{A}}$ and ${\mathbb{B}}$ are regularly interpretable in each other,
so ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\phi)$ and
${\mathbb{B}}\simeq\Delta({\mathbb{A}},\psi)$ for some codes $\Gamma$ and
$\Delta$ and the corresponding formulas $\phi,\psi$ (without parameters). By
transitivity ${\mathbb{A}}$, as well as ${\mathbb{B}}$, is regularly
interpretable in itself, so
${\mathbb{A}}\simeq(\Gamma\circ\Delta)({\mathbb{A}},\phi^{\ast})$ and
${\mathbb{B}}\simeq(\Delta\circ\Gamma)({\mathbb{B}},\psi^{\ast})$, where
$\circ$ denotes composition of interpretations and $\phi^{\ast},\psi^{\ast}$
the corresponding formulas.

  * 2)

There is a formula $\theta(\bar{y},x,\bar{z})$ in the language of
${\mathbb{A}}$ such that for every tuple $p^{\ast}$ satisfying
$\phi^{\ast}(\bar{z})$ in ${\mathbb{A}}$ the formula
$\theta(\bar{y},x,p^{\ast})$ defines in ${\mathbb{A}}$ the isomorphism
$\bar{\mu}_{\Gamma\circ\Delta}:(\Gamma\circ\Delta)({\mathbb{A}},p^{\ast})\to{\mathbb{A}}$
and there is a formula $\sigma(\bar{u},x,\bar{v})$ in the language of
${\mathbb{B}}$ such that for every tuple $q^{\ast}$ satisfying
$\psi^{\ast}(\bar{v})$ in ${\mathbb{B}}$ the formula
$\sigma(\bar{u},x,q^{\ast})$ defines in ${\mathbb{B}}$ the isomorphism
$\bar{\mu}_{\Delta\circ\Gamma}:(\Delta\circ\Gamma)({\mathbb{B}},q^{\ast})\to{\mathbb{B}}$.

######  Definition 4.

Suppose structures ${\mathbb{A}}$ and ${\mathbb{B}}$ are regularly
interpretable in each other, so ${\mathbb{A}}\simeq\Gamma({\mathbb{B}},\phi)$
and ${\mathbb{B}}\simeq\Delta({\mathbb{A}},\psi)$ for some codes $\Gamma$ and
$\Delta$ and the corresponding formulas $\phi,\psi$ without parameters.
Suppose ${\mathbb{A}}\simeq(\Gamma\circ\Delta)({\mathbb{A}},\bar{s})$ for any
tuple $\bar{s}$ such that $A\models\phi^{*}(\bar{s})$. We say that
${\mathbb{A}}$ is invertibly interpretable in ${\mathbb{B}}$ if there is a
formula $\theta(\bar{y},x,\bar{s})$ in the language of ${\mathbb{A}}$ such
that for every tuple $p^{*}$ satisfying $\phi^{*}(\bar{s})$ in ${\mathbb{A}}$
the formula $\theta(\bar{y},x,p^{*})$ defines in ${\mathbb{A}}$ an isomorphism
$\Gamma\circ\Delta({\mathbb{A}},p^{*})\rightarrow{\mathbb{A}}.$

######  Theorem 1.

Let ${\mathbb{A}}$ be invertible interpretable in ${\mathbb{B}}$,
${\mathbb{A}}\simeq\Gamma({\mathbb{B}})$. Then a structure
${\mathbb{A}}^{\prime}$ is elementarily equivalent to ${\mathbb{A}}$ if and
only if there is a structure ${\mathbb{B}}^{\prime}$ elementarily equivalent
to ${\mathbb{B}}$ such that
${\mathbb{A}}^{\prime}\simeq\Gamma({\mathbb{B}}^{\prime}).$

###### Proof.

The ”if” part is [5, Lemma 4.4 (2)]. If
${\mathbb{A}}\equiv{\mathbb{A}}^{\prime},$ then
${\mathbb{B}}^{\prime}\simeq\Delta({\mathbb{A}}^{\prime})\equiv{\mathbb{B}}$
by the ”if” part. By the definition of invertible interpretability,
$\Gamma({\mathbb{B}}^{\prime})\simeq\Gamma\circ\Delta({\mathbb{A}}^{\prime}).$

∎

##  2 By-interpretation of a free metabelian group with $\mathbb{Z}$

We proved in [5] that a free metabelian group with $n$ generators, $n>1$ is
prime, atomic, homogeneous and QFA. This was done by proving the existence of
bi-interpretation with ${\mathbb{Z}}$. Here we will describe a bi-
interpretation from [5] of a free metabelian group $G$ of finite rank $n\geq
2$ with $\mathbb{Z}=(\mathbb{Z},\cdot,^{-1},0,1)$. We will use it in the next
section.

Throughout this section we denote by $G$ a free metabelain group of rank
$n\geq 2$ with basis $X=\\{x_{1},\ldots,x_{n}\\}$.

######  Theorem 2.

Every free metabelian group of finite rank $\geq 2$ is regularly bi-
interpretable with $\mathbb{Z}$.

###  2.1 Preliminaries for metabelian groups

In this section we introduce notation and describe some results that we need
in the sequel.

Some notation: $G^{\prime}=[G,G]$ is the commutant of $G$, $G_{m}$ is the
$m$’th term of the lower central series of $G$, $\langle A\rangle$ is the
subgroup generated by $A\subseteq G$, $C_{G}(A)$ is the centralizer of a
subset $A\subseteq G$, if $x,y\in G$ then $[x,y]=x^{-1}y^{-1}xy$ is the
commutator of $x$ and $y$, and $x^{y}=y^{-1}xy$ is the conjugate of $x$ by
$y$. The maximal root of an element $x\in G$ is an element $x_{0}\in G$ such
that $x_{0}$ is not a proper power in $G$ and $x\in\langle x_{0}\rangle$. We
term an element $x\in G$ a root if it is not a proper in $G$.

In [8] Mal’cev obtained complete description of centralizers of elements in
$G$. Namely, the following holds. Let $x\in G$. Then

  * 1)

if $x\in G^{\prime}$ then $C_{G}(x)=G^{\prime}$

  * 2)

if $x\not\in G^{\prime}$ then $C_{G}(x)=\langle x_{0}\rangle$, where $x_{0}$
is the unique maximal root of $x$, i.e., $x=x_{0}^{k}$ for some
$k\in{\mathbb{N}}$ and $x_{0}$ is not a proper power.

It follows, in particular, that the maximal roots of elements in $G$ exist and
they are unique.

Let $v\in G\smallsetminus G^{\prime}$. Define a map $\lambda_{v}:G^{\prime}\to
G^{\prime}$ such that for $c\in G^{\prime}$ $\lambda_{v}(c)=[v,c]$. Then the
map $\lambda_{v}$ is a homomorphism. Indeed, using the commutator identity

$[x,yz]=[x,z][x,y]^{z},$

which holds for every elements $x,y,z$ of an arbitrary group, one has for
$c_{1},c_{2}\in G^{\prime}$

$[v,c_{1}c_{2}]=[v,c_{2}][v,c_{1}]^{c_{2}}=[v,c_{2}][v,c_{1}]=[v,c_{1}][v,c_{2}],$
(2)

as claimed.

Similarly, in the notation above, the map $\mu_{v}:c\to[c,v]$ is a
homomorphism $\mu_{v}:G^{\prime}\to G^{\prime}$.

Let $v\in G\smallsetminus G^{\prime}$ and $d\in G^{\prime}$. Then for any
$k\in{\mathbb{Z}}$ there exists $c\in G^{\prime}$ such that:

$(vd)^{k}=v^{k}d^{k}[c,v].$

We prove first, by induction on $k$, that

$d^{k}v=vd^{k}[c,v]$

for some $c\in G^{\prime}$. Indeed, for $k=1$ one has the standard equality
$dv=vd[d,v]$. Now

$d^{k+1}v=d^{k}dv=d^{k}vd[d,v]=vd^{k}[c_{1},v]d[d,v]=vd^{k+1}[c_{1},v][d,v]=vd^{k+1}[c_{1}d,v],$

the last equality comes from the property (2), that the map $\mu_{v}$ is a
homomorphism on $G^{\prime}$.

Now one can finish the claim by induction on $k$ as follows (here elements
$c_{i}\in G^{\prime}$ appears as the result of application of the induction
step and the claim above):

$(vd)^{k+1}=(vd)^{k}vd=v^{k}d^{k}[c_{2},v]vd=v^{k}d^{k}v[c_{2},v][[c_{2},v],v]d=$
$=v^{k}vd^{k}[c_{3},v][c_{2},v][[c_{2},v],v]d=v^{k+1}d^{k+1}[c_{3}c_{2}[c_{2},v],v]=v^{k+1}d^{k+1}[c,v]$

where the second to last equality comes again from the property (2), and
$c=c_{3}c_{2}[c_{2},v]$. This proves the claim.

######  Lemma 2.

[5, Lemma 4.23] Let $d\in G^{\prime}$. If for any $v\in G\smallsetminus
G^{\prime}$ there exists $c\in G^{\prime}$ such that $d=[c,v]$, then $d=1$.

The group $G$ acts by conjugation on $G^{\prime}$, which gives an action of
the abelianization $\bar{G}=G/G^{\prime}$ on $G^{\prime}$. This action extends
by linearity to an action of the group ring ${\mathbb{Z}}\bar{G}$ on
$G^{\prime}$ and turns $G^{\prime}$ into a ${\mathbb{Z}}\bar{G}$-module.
Denote by $a_{i}$ the image of $x_{i}$ in $\bar{G}$, $i=1,\ldots,n$. The group
$\bar{G}$ is a free abelian group with basis $a_{1},\ldots,a_{n}$, so the
group ring ${\mathbb{Z}}\bar{G}$ can be viewed as the Laurent polynomial ring
$A={\mathbb{Z}}[a_{1},a_{1}^{-1},\ldots,a_{n},a_{n}^{-1}]$. For the action of
$A$ on $G^{\prime}$ we use the exponential notation, namely, for $u\in
G^{\prime}$ and $a\in A$ we denote by $u^{a}$ the result of the action of $a$
on $u$. Let $Y=\\{[x_{i},x_{j}]\mid 1\leq j<i\leq n\\}$. Then the set of
commutators $Y$ generates $G^{\prime}$ as an $A$-module. Note, that $G$ (as a
metabelian group) satisfies the Jacobi identity, i.e, for every $u,v,w\in G$
the following equality holds

$[u,v,w][v,w,u][w,u,v]=1.$

In particular, for $u=x_{i},v=x_{j},w=x_{k}$ one gets (in the module notation)

$[x_{i},x_{j}]^{a_{k}-1}[x_{j},x_{k}]^{a_{i}-1}[x_{k},x_{i}]^{a_{j}-1}=1.$

It shows also that commutators from $Y$ satisfy the following identity

$[x_{i},x_{j}]^{a_{k}-1}[x_{j},x_{k}]^{a_{i}-1}=[x_{i},x_{k}]^{a_{j}-1},$

so $Y$ is not a free generating set of the module $G^{\prime}$. However, there
are nice normal forms of elements of the module $G^{\prime}$ described, for
example, in [12], [5].

######  Proposition 1.

Every element $u\in G^{\prime}$ can be uniquely presented as the following
product

$u=\Pi_{1\leq j<i\leq n}[x_{i},x_{j}]^{\beta_{ij}(a_{1},\ldots,a_{i})},$

where
$\beta_{ij}(a_{1},\ldots,a_{i})\in{\mathbb{Z}}[a_{1},a_{1}^{-1},\ldots,a_{i},a_{i}^{-1}]\leq{\mathbb{Z}}\bar{G}$.

The following statement follows from normal forms.

######  Proposition 2.

[5, Proposition 4.4] $G^{\prime}$ is a free module over
$\mathbb{Z}[a_{1},a_{1}^{-1},a_{2},a_{2}^{-1}]$ with the basis
$\\{[x_{i},x_{j}]^{a_{3}^{\delta_{3}}\ldots a_{j}^{\delta_{j}}}\\}$ for all
$1\leq i<j\leq n$, $\delta_{3},\ldots,\delta_{j}\in{\mathbb{Z}}^{j-2}.$

Let $F_{n}$ be the free group of rank $n$ with the basis
$\\{z_{1},\ldots,z_{n}\\},$ let $\pi:F_{n}\rightarrow\bar{g}$. A partial Fox
derivative associated with $z_{i}$ is the linear map
$D_{i}:\mathbb{Z}(F_{n})\rightarrow\mathbb{Z}(F_{n})$ satisfying the
conditions

$D_{i}(z_{i})=1,D_{i}(z_{j})=0,i\neq j$

and

$D_{i}(uv)=D_{i}(u)+uD_{i}(v)$

for all $u,v\in F_{n}$. The main identity is
$D_{1}(w)(z_{1}-1)+\ldots+D_{n}(w)(z_{n}-1)=w-1.$ $D_{i}$ induces a linear map
$d_{i}:{\mathbb{Z}}G\rightarrow{\mathbb{Z}}\bar{G}.$ We briefly explain the
details. One can compute

$D_{i}([u^{-1},v^{-1}])=(1-uvu^{-1})D_{i}(u^{-1})+(u-uvu^{-1}v^{-1})D_{i}(v)$

for all $u,v\in F_{n}.$ It follows that for
$\pi^{\prime}:{\mathbb{Z}}F_{n}\rightarrow{\mathbb{Z}}\bar{G}$, for all
$w\in{F_{n}}^{\prime\prime}$, $w\in\ker\pi^{\prime}$. Hence $D_{i}$ induces a
linear map $d_{i}:{\mathbb{Z}}G\rightarrow{\mathbb{Z}}\bar{G}$ (that we will
also call Fox derivative).

From the definition we have

$d_{i}(x_{i})=1,\ d_{i}(x_{j})=0,i\neq j,$ $d_{i}(uv)=d_{i}(u)+(u\pi)d_{i}(v)$

for all $u,v\in G$. The main identity is
$d_{1}(w)(a_{1}-1)+\ldots+d_{n}(w)(a_{n}-1)=w\pi-1,$ where $w$ is an arbitrary
element of $G$.

It can be verified that for $w\in G^{\prime}$ and $a\in\bar{G}$,
$d_{i}(w^{a})=a^{-1}d_{i}(w).$ Also note that for $w\in G^{\prime}$ and $u\in
G$ we have

$d_{i}(wu)=d_{i}(w)+d_{i}(u).$

If $a=\alpha_{1}a_{1}+\ldots+\alpha_{k}a_{k}\in{\mathbb{Z}}\bar{G}$ with
$\alpha_{i}\in{\mathbb{Z}},a_{i}\in\bar{G}$, we denote by
$a_{inv}=\alpha_{1}{a_{1}}^{-1}+\ldots+\alpha_{k}{a_{k}}^{-1}.$ Then

$d_{i}(w^{a})=a_{inv}d_{i}(w).$

For $u\in G,\alpha\in{\mathbb{Z}}$,

$d_{i}(u^{\alpha})=\frac{u^{\alpha}-1}{u-1}d_{i}(u).$

###  2.2 ${\mathbb{Z}}$ is absolutely interpretable in $G$

The description in 2.1 of the centralizers of elements in $G$ implies that the
formula

$\phi(x)=\forall y\forall z([x,[y,z]]=1)$

defines the commutant $G^{\prime}$ in $G$. Indeed, $\phi(g)$ holds in $G$ for
an element $g\in G$ if and only if $C_{G}(g)\geq G^{\prime}$, which happens
only if $g\in G^{\prime}$.

The free nilpotent group $G/G_{3}$ of class 2 and rank n is 0-interpretable in
$G$. Indeed, the verbal subgroup $G_{3}$ has finite width in $G$ [13], hence
it is 0-definable in $G$. Therefore the quotient group $G/G_{3}$ is
0-interpretable in $G$.

It was shown in [9] that the ring ${\mathbb{Z}}$ and its action by exponents
on free abelian groups $G/G^{\prime}$ and $G^{\prime}/G_{3}$ are
0-interpretable in $G/G_{3}$, hence, by transitivity of 0-interpretations, it
is 0-interpretable in $G$. We denote this interpretation of ${\mathbb{Z}}$ in
$G$ by ${\mathbb{Z}}^{*}$.

Now, we may use in our formulas expressions of the type $y=x^{m}modG^{\prime}$
for $x,y\in G\smallsetminus G^{\prime}$ and $m\in{\mathbb{Z}}^{*}$ viewing
them as notation for the corresponding formulas of group theory language which
are coming from the interpretations of ${\mathbb{Z}}^{*}$ and its actions on
$G/G^{\prime}$. Similarly, for $G^{\prime}/G_{3}$. More precisely, the
interpretation ${\mathbb{Z}}^{*}$ is given by a definable in $G$ subset
$A\subseteq G^{k}$ together with a definable in $G$ equivalence relation
$\sim$ on $A$ and formulas
$\psi_{+}(\bar{x},\bar{y},\bar{z}),\psi_{\circ}(\bar{x},\bar{y},\bar{z})$ with
$k$-tuples of variables $\bar{x},\bar{y},\bar{z}$, such that the formulas
$\psi_{+}$ and $\psi_{\circ}$ define binary operations on the factor set
$A/\sim$ (denoted by $+$ and $\circ$) and the structure $\langle
A/\sim;+,\circ\rangle$ is a ring isomorphic to ${\mathbb{Z}}$. Furthermore,
the exponentiation by ${\mathbb{Z}}^{*}$ on $G/G^{\prime}$ and on
$G^{\prime}/G_{3}$ is also 0-interpretable, which means that there are
formulas in the group language, say $expnil_{1}(u,v,\bar{x})$ and
$expnil_{2}(u,v,\bar{x})$, such that for $g,h\in G$ and
$m\in{\mathbb{Z}}^{*}$, where $m$ is the equivalence class of some tuple
$\bar{a}\in A$ (we write in this case $m=[\bar{a}]$), one has $g^{m}=h(mod\
G^{\prime})$ if and only if $expnil_{1}(g,h,\bar{a})$ holds in $G$ and also
for elements $p,q\in G^{\prime}$ $p^{m}=q(mod\ G_{3})$ if and only if
$expnil_{2}(p,q,\bar{a})$ holds in $G$.

###  2.3 Interpretation of ${\mathbb{Z}}$-exponentiation in $G$

Now, in the notation above, we construct a formula $exp(u,v,\bar{x})$ of the
group language, where $\bar{x}$ is a $k$-tuple of variables, such that for
$g,h\in G$ and $m\in{\mathbb{Z}}^{*}$, where $m$ is the equivalence class
$[\bar{a}]$ of some $\bar{a}\in A$, the following holds

$g=h^{m}\Longleftrightarrow G\models exp(g,h,\bar{a}),\ (here\ m=[\bar{a}]).$

To construct the formula $exp(u,v,\bar{x})$ we consider several two cases, for
each of them build the corresponding formula $exp_{i}(u,v,\bar{x})$, and then
use them to build $exp(u,v,\bar{x})$.

Case 1. Let $g\in G\smallsetminus G^{\prime}$. In Section 2.2 we described a
formula $expnil_{1}(u,v,\bar{x})$ of group language such that for $g,h\in G$
and $m=[\bar{a}]\in{\mathbb{Z}}^{*}$ one has

$g^{m}=h(mod\ G^{\prime})\Longleftrightarrow G\models\
expnil_{1}(g,h,\bar{a}).$

Now put

$exp_{1}(u,v,\bar{x})=([u,v]=1\wedge expnil_{1}(u,v,\bar{x}).$

Then the formula $exp_{1}(u,v,\bar{x})$ holds in $G$ on elements $g,h\in G$
and $m=[\bar{a}]$ if and only if $h=g^{m}(mod\ G^{\prime})$ and $h\in
C_{G}(g)$. Since the centralizer $C_{G}(g)$ is cyclic there is only one such
$h$ and in this case $h=g^{m}$.

Case 2. Let $g\in G^{\prime}$. Then for any $w\in G\smallsetminus G^{\prime}$
and every $m\in{\mathbb{Z}}$ there exists $c\in G^{\prime}$ such that the
following equality holds

$(wg)^{m}=w^{m}g^{m}[c,w].$

hence the elements $g$ and $g^{m}$ and $m=[\bar{a}]\in Z^{*}$ satisfies the
following formula

$\exp_{2}(u,v,\bar{x})=\forall w(w\in G\smallsetminus G^{\prime}\to\exists
c(c\in G^{\prime}\wedge((wu)^{m}=w^{m}u^{m}[c,w])).$

Here, of course, we use the formula $exp_{2}(u,v,\bar{x})$ to write down the
condition$(wu)^{m}=w^{m}u^{m}[c,w]$.

We claim that for given $g\in G^{\prime}$ and $m=[\bar{a}]\in{\mathbb{Z}}^{*}$
the formula $\exp_{2}(g,v,\bar{a})$ holds in $G$ only one one element -
precisely on $g^{m}$. Indeed, let $h\in G$ be such that for a given
$m\in{\mathbb{Z}}$ for any $w\in G\smallsetminus G^{\prime}$ there exists
$c_{1}\in G^{\prime}$ such that

$(wg)^{m}=w^{m}h[c_{1},w].$

Then $w^{m}g^{m}[c,w]=w^{m}h[c_{1},w]$, so

$h^{-1}g^{m}=[c,w][c_{1},w]^{-1}=[c,w][c_{1}^{-1},w]=[cc_{1}^{-1},w].$

Now by Lemma 2 one gets $h^{-1}g^{m}=1$, so $h=g^{m}$, as claimed. This shows
that the formula $\exp_{2}(u,v,\bar{x})$ defines the exponentiation on
$G^{\prime}$.

Finally, the formula

$\exp(u,v,\bar{x})=(u\notin G^{\prime}\to exp_{1}(u,v,\bar{x}))\wedge(u\in
G^{\prime}\to exp_{2}(u,v,\bar{x}))$

defines ${\mathbb{Z}}$-exponentiation on the whole group $G$.

###  2.4 Interpretation of ${\mathbb{Z}}\bar{G}$-module $G^{\prime}$ in $G$

In this section we interpret in $G$ the action of the ring
${\mathbb{Z}}\bar{G}$ on $G^{\prime}$.

We first show how to interpret the action of
${\mathbb{Z}}[a_{1},\ldots,a_{n}]$ on $G^{\prime}$ and then the action of the
whole ring ${\mathbb{Z}}[a_{1},a_{1}^{-1},\ldots,a_{n},a_{n}^{-1}]$ on
$G^{\prime}$. But first we need two preliminary results.

For a tuple $\bar{\alpha}=(\alpha_{1},\ldots,\alpha_{m})\in{\mathbb{Z}}^{m}$,
$m\leq n$, denote by $\lambda_{\bar{\alpha}}$ the homomorphim
$\lambda_{\bar{\alpha}}:{\mathbb{Z}}[a_{1},\ldots,a_{n}]\to{\mathbb{Z}}[a_{m+1},\ldots,a_{n}]$
such that $a_{i}\to\alpha_{i},i=1,\ldots,m$. The kernel $I_{\bar{\alpha}}$ of
$\lambda_{\bar{\alpha}}$ is the ideal generated in
${\mathbb{Z}}[a_{1},\ldots,a_{n}]$ by
$\\{a_{1}-\alpha_{1},\ldots,a_{m}-\alpha_{m}\\}$. Notice, that for every
polynomial $P=P(a_{1},\ldots,a_{m})\in{\mathbb{Z}}[a_{1},\ldots,a_{n}]$ one
has $\lambda_{\bar{\alpha}}(P)=P(\alpha_{1},\ldots,\alpha_{n})$, so

$P(a_{1},\ldots,a_{m})=P(\alpha_{1},\ldots,\alpha_{m})+\Sigma_{i=1}^{m}(a_{i}-\alpha_{i})f_{i},$

for some $f_{i}\in{\mathbb{Z}}[a_{1},\ldots,a_{n}]$.

Let $A$ and $B$ be rings and $\Lambda$ a set of homomorphisms from $A$ into
$B$. Recall that $A$ is discriminated into $B$ by a set $\Lambda$ if for any
finite subset $A_{0}\subseteq A$ there is a homomorphism $\lambda\in\Lambda$
which is injective on $A_{0}$.

The following result is known, but we need the argument from the proof in the
sequel.

Claim 1. The ring ${\mathbb{Z}}[a_{1},\ldots,a_{n}]$ is discriminated into
${\mathbb{Z}}$ by the set of homomorphisms
$\lambda_{\bar{\alpha}},\bar{\alpha}\in{\mathbb{Z}}^{n}$.

###### Proof.

Since ${\mathbb{Z}}[a_{1},\ldots,a_{n}]$ is an integral domain it suffices to
show $\Lambda$ separates ${\mathbb{Z}}[a_{1},\ldots,a_{n}]$ into
${\mathbb{Z}}$, i.e., for every non-zero polynomial
$Q\in{\mathbb{Z}}[a_{1},\ldots,a_{n}]$ there exists $\lambda\in\Lambda$ such
that $\lambda(Q)\neq 0$. Indeed, let $A_{0}=\\{P_{1},\ldots,P_{t}\\}$ with
$P_{i}\neq P_{j}$ for $1\leq j<i\leq t$. Put $Q_{ij}=P_{i}-P_{j}$ and
$Q=\Pi_{1\leq j<i\leq t}Q_{ij}$. Then $Q\neq 0$. If for some
$\lambda\in\Lambda$ $\lambda(Q)\neq 0$ then $\lambda$ is injective on $A_{0}$.

Now we prove by induction on $n$ that $\Lambda$ separates
${\mathbb{Z}}[a_{1},\ldots,a_{n}]$ into $Z$. If $P\in{\mathbb{Z}}[a_{1}]$ then
$\lambda_{\alpha_{1}}$ for each sufficiently large $\alpha_{1}$ separates $P$
into ${\mathbb{Z}}$. If $P\in{\mathbb{Z}}[a_{1},\ldots,a_{n}]$ then for some
$m\in{\mathbb{N}}$

$P=Q_{m}a_{n}^{m}+Q_{m-1}a_{n}^{m-1}+\ldots+Q_{1}a_{n}+Q_{0},$

where $Q_{i}\in{\mathbb{Z}}[a_{1},\ldots,a_{n-1}]$ and $Q_{m}\neq 0$. By
induction there is
$\bar{\beta}=(\beta_{1},\ldots,\beta_{n-1})\in{\mathbb{Z}}^{n-1}$ such that
the homomorphism $\lambda_{\bar{\beta}}$ discriminates $Q_{m}$ into
${\mathbb{Z}}$. Then

$\lambda_{\bar{\beta}}(Q_{m})a_{n}^{m}+\lambda_{\bar{\beta}}(Q_{m-1})a_{n}^{m-1}+\ldots+\lambda_{\bar{\beta}}(Q_{1})a_{n}+\lambda_{\bar{\beta}}(Q_{0})$

is a non-zero polynomial in ${\mathbb{Z}}[a_{n}]$. Now one can separate this
polynomial into ${\mathbb{Z}}$ by sending $a_{n}$ to a large enough integer
$\alpha_{n}$, as above. This proves the claim.

∎

Denote by $(G^{\prime})^{I_{\bar{\alpha}}}$ the submodule of the module
$G^{\prime}$ obtained from $G^{\prime}$ by the action of the ideal
$I_{\bar{\alpha}}$. $(G^{\prime})^{I_{\bar{\alpha}}}$ is an abelian subgroup
of $G$ generated by the set $\\{g^{Q}\mid g\in G^{\prime},Q\in
I_{\bar{\alpha}}\\}$, hence by the set $\\{g^{a_{i}-\alpha_{i}}\mid g\in
G^{\prime},i=1,\ldots,n\\}$.

Claim 2. For any basis $(x_{1},\ldots,x_{n})$ of $G$ and any tuple
$(\alpha_{1},\ldots,\alpha_{m})\in{\mathbb{Z}}^{m}$ the subgroup
$(G^{\prime})^{I_{\bar{\alpha}}}\leq G^{\prime}$ is definable in $G$ uniformly
in $(x_{1},\ldots,x_{n})$ and $(\alpha_{1},\ldots,\alpha_{m})$. More
precisely, let ${\mathbb{Z}}^{*}$ be 0-interpretation of ${\mathbb{Z}}$ in $G$
from Section 2.2. Then there is a formula
$\phi(y,y_{1},\ldots,y_{n},\bar{z}_{1},\ldots,\bar{z}_{m})$ of group theory
such that for any basis $(x_{1},\ldots,x_{n})$ of $G$ and any tuple
$(\bar{k}_{1},\ldots,\bar{k}_{m})\in({\mathbb{Z}}^{*})^{n}$ the formula
$\phi(y,x_{1},\ldots,x_{n},\bar{k}_{1},\ldots,\bar{k}_{m})$ defines in $G$ the
subgroup $(G^{\prime})^{I_{\bar{\alpha}}}$, where
$\alpha_{i}=\bar{k}_{i}\in{\mathbb{Z}}^{*},i=1,\ldots,m$.

Indeed, let $(x_{1},\ldots,x_{n})$ be a basis of $G$ and
$(\alpha_{1},\ldots,\alpha_{m})\in{\mathbb{Z}}^{m}$. The abelian subgroup
$(G^{\prime})^{I_{\bar{\alpha}}}$ of $G$ is generated by the set
$\\{g^{a_{i}-\alpha_{i}}\mid g\in G^{\prime},i=1,\ldots,m\\}$. It follows that
every element $u\in(G^{\prime})^{I_{\bar{\alpha}}}$ can be presented as a
product

$u=g_{1}^{a_{1}-\alpha_{1}}\ldots g_{m}^{a_{m}-\alpha_{m}},$

for some $g_{1},\ldots,g_{m}\in G^{\prime}$, or , equivalently, in the form

$u=g_{1}^{x_{1}}g_{1}^{-\alpha_{1}}\ldots g_{m}^{x_{m}}g_{m}^{-\alpha_{m}}$
(3)

where $g_{i}^{x_{i}}$ is a conjugation of $g_{i}$ by $x_{i}$, and
$g_{i}^{-\alpha_{i}}$ is the standard exponentiation of $g_{i}$ by the integer
$-\alpha_{i}$, $i=1,\ldots,n$. It was shown that there exists a formula
$\exp_{2}(u,v,\bar{z})$ such that for any $g,h\in G^{\prime}$ and
$\alpha=\bar{m}\in{\mathbb{Z}}^{*}$ the formula $\exp_{2}(g,h,\bar{m})$ holds
in $G$ if and only if $g=h^{\alpha}$. Using formula $\exp_{2}(u,v,\bar{z})$
and definability of the commutant $G^{\prime}$ in $G$ (see Section 2.2) one
can write down the condition (3) by a group theory formula uniformly in
$(x_{1},\ldots,x_{n})$ and $(\alpha_{1},\ldots,\alpha_{m})$, as claimed.

######  Lemma 3.

[5, Lemma 4.24] Let $g,h\in G^{\prime}$ and
$P\in{\mathbb{Z}}[a_{1},\ldots,a_{m}]$, $m\leq n$. Then $g^{P}=h$ if and only
if the following condition holds:

$\forall\alpha_{1},\ldots\alpha_{m}\in{\mathbb{Z}}(g^{P(\alpha_{1},\ldots,\alpha_{m})}=h\
mod\ (G^{\prime})^{I_{\bar{\alpha}}}).$ (4)

Every element $Q\in{\mathbb{Z}}[a_{1},a_{1}^{-1},\ldots,a_{n},a_{n}^{-1}]$ can
be written as

$Q=P(a_{1},...,a_{m})(a_{1}^{k_{1}}\ldots a_{m}^{k_{m}})^{-1}$

for some $k_{1},\ldots,k_{m}\geq 0$. Therefore $g^{Q}=h$ if and only if
$g^{P(a_{1},...,a_{m})}=h^{(a_{1}^{k_{1}}\ldots a_{m}^{k_{m}})}.$ This gives
the interpretation of the action of
${\mathbb{Z}}[a_{1},a_{1}^{-1},\ldots,a_{n},a_{n}^{-1}]$ on $G^{\prime}$.

###  2.5 Proof of Theorem 2

In this section we will prove Theorem 2. Using the Magnus embedding

$x_{i}\rightarrow\begin{pmatrix}a_{i}&0\\\ t_{i}&1\end{pmatrix},$

where $a_{1},\ldots,a_{n}$ are the generators of the free abelian group and
$\\{t_{1},\ldots,t_{n}\\}$ the base of the free $\mathbb{Z}\bar{G}$ module
$T$. Then $G^{\prime}$ has the structure of the the submodule of $T$ generated
by $t_{i}(x_{j}-1)-t_{j}(x_{i}-1),i\neq j.$ Denote this submodule by
$G^{\prime}_{{\mathbb{Z}}\bar{G}}$.

The module $G^{\prime}_{{\mathbb{Z}}\bar{G}}$ is a two sorted structure
$({\mathbb{Z}}\bar{G},G^{\prime},\delta)$ where $\delta$ is the predicate
describing the action of ${\mathbb{Z}}\bar{G}$ on $G^{\prime}$. We will show
that $G^{\prime}_{{\mathbb{Z}}\bar{G}}$ is bi-interpretable with $\mathbb{Z}$.

By the result in [2] every infinite f.g. integral domain is bi-interpretable
with ${\mathbb{Z}}.$ Therefore $\mathbb{Z}\bar{G}$ which is isomorphic to the
ring of Laurent polynomials, is bi-interpretable with $\mathbb{Z}$. A
$0$-interpretation of the ring of Laurent polynomials
$\mathbb{Z}\bar{G}={\mathbb{Z}}[a_{1},a_{1}^{-1},\ldots,a_{n},a_{n}^{-1}]$ in
${\mathbb{Z}}$ is described, for example, in [4, Theorem 3]. The following
result is established in [11].

######  Proposition 3.

The subset ${\mathbb{Z}}$ is regularly definable in $\mathbb{Z}\bar{G}$ and
there is a regular bi-interpretation of ${\mathbb{Z}}$ and
$\mathbb{Z}\bar{G}$.

Every f.g. free $\mathbb{Z}\bar{G}$-module is then regularly bi-interpretable
with ${\mathbb{Z}}\bar{G}$ (with some ${\mathbb{Z}}\bar{G}$-basis as
constants), and, therefore, it is bi-interpretable with $\mathbb{Z}$. Since
${\mathbb{Z}}$ is bi-interpretable with $T$ and with the submodule $B$
generated by $[u_{1},u_{2}]$, we can define a map
$T\rightarrow_{\phi}{\mathbb{Z}}\rightarrow_{\psi}B\leq T$. The graph of the
map $\psi\circ\phi$ is definable in $T$ (with parameters, regularly). The
restriction of the map $\phi$ to $G^{\prime}_{{\mathbb{Z}}\bar{G}}$,
$\phi|_{G^{\prime}_{{\mathbb{Z}}\bar{G}}}$ is the interpretation of
$G^{\prime}_{{\mathbb{Z}}\bar{G}}$ in ${\mathbb{Z}}$ and $\psi$ is the
interpretation of ${\mathbb{Z}}$ in $G^{\prime}_{{\mathbb{Z}}\bar{G}}$. Te
graph of $\psi\circ\phi|_{G^{\prime}_{{\mathbb{Z}}\bar{G}}}$ is definable and
therefore $G^{\prime}_{{\mathbb{Z}}\bar{G}}$ is regularly bi-interpretable
with ${\mathbb{Z}}$. Denote by $\alpha$ the bijection from
$G^{\prime}_{{\mathbb{Z}}\bar{G}}$ to ${\mathbb{Z}}$.

We have the interpretation of $G$ on the set ${\mathbb{Z}}^{m+1}$ and,
therefore, in ${\mathbb{Z}}$ defined by

$\tau(u_{1}^{m_{1}}\ldots u_{n}^{m_{n}}h)=(m_{1},\ldots,m_{n},\alpha(h)).$

We have already shown that the exponentiation and the module structure of
$G^{\prime}_{{\mathbb{Z}}\bar{G}}$ are interpretable in $G$.

Now, given an $n+1$ tuple $(m_{1},...,m_{n},k)$ of integers we reconstruct the
element of the group as $u_{1}^{m_{1}}\ldots u_{n}^{m_{n}}\alpha^{-1}(k).$

So we have a sequence of regular bi-interpretations:

$G\longleftrightarrow(\mathbb{Z}\bar{G},G^{\prime}_{{\mathbb{Z}}\bar{G}})\longleftrightarrow\mathbb{Z}^{m+1},\longleftrightarrow\mathbb{Z}.$

This proves the theorem.

##  3 Groups elementarily equivalent to a free
metabelian group

In this section we will describe groups elementarily equivalent to the free
metabelian group $G$ with $n$ generators (denote them by
$x_{1},\ldots,x_{n}).$

Since $G$ is regularly bi-interpretable in ${\mathbb{Z}}$, we can use Theorem
1 with $G={\mathbb{A}}$ and ${\mathbb{Z}}={\mathbb{B}}.$ Then
$G=\Gamma({\mathbb{Z}}),{\mathbb{Z}}=\Delta(G,\bar{g}).$ If $H\equiv G$, then
the same formulas give the interpretation $H=\Gamma(\tilde{\mathbb{Z}}),$
where $\tilde{\mathbb{Z}}\equiv{\mathbb{Z}}$. We call $\tilde{\mathbb{N}}$, a
structure elementarily equivalent to ${\mathbb{N}}$ a model of arithmetic.
Notice that ${\mathbb{N}}$ and ${\mathbb{Z}}$ are absolutely bi-interprtable.
A ring $\tilde{\mathbb{Z}}$ (resp. $\tilde{\mathbb{N}}$) is called a non-
standard model if it is not isomorphic to ${\mathbb{Z}}$ (resp.
${\mathbb{N}}$), see [7] and [11].

First, we notice that $H$ is a so-called exponential group with exponents in
$\tilde{\mathbb{Z}}$. Let us recall the four axioms of exponential groups from
[10]. Let $A$ be an arbitrary associative ring with identity and $\Gamma$ a
group. Fix an action of the ring $A$ on $\Gamma$, i.e. a map $\Gamma\times
A\rightarrow\Gamma$. The result of the action of $\alpha\in A$ on $g\in\Gamma$
is written as $g^{\alpha}$. Consider the following axioms:

  1. 1.

$g^{1}=g$, $g^{0}=1$, $1^{\alpha}=1$ ;

  2. 2.

$g^{\alpha+\beta}=g^{\alpha}\cdot g^{\beta},\
g^{\alpha\beta}=(g^{\alpha})^{\beta}$;

  3. 3.

$(h^{-1}gh)^{\alpha}=h^{-1}g^{\alpha}h;$

  4. 4.

$[g,h]=1\Longrightarrow(gh)^{\alpha}=g^{\alpha}h^{\alpha}.$

######  Definition 5.

Groups with $A$-actions satisfying axioms 1)–4) are called $A$– exponential
groups.

These axioms can be written by first-order formulas in $G$ and $H$. This
implies the following lemma.

######  Lemma 4.

$H$ is $\tilde{Z}$-exponential group.

Our main goal now is to describe the structure of $H$. We know that $G$ can be
represented as a pair ${\mathbb{Z}}\bar{G}$ and a module
$G^{\prime}_{{\mathbb{Z}}\bar{G}}$ with the action of ${\mathbb{Z}}\bar{G}$ on
$G^{\prime}_{{\mathbb{Z}}\bar{G}}$ interpretable in $G$ by Section 2.4.

We have $G\rightarrow_{\Gamma}{\mathbb{Z}}\rightarrow_{\Delta}G,$ where the
interpretation $\Gamma({\mathbb{Z}})$ is via normal forms, therefore
$H\rightarrow_{\Gamma}\tilde{\mathbb{Z}}\rightarrow_{\Delta}H.$ The element
$g=x_{1}^{\gamma_{1}}\ldots x_{n}^{\gamma_{n}}u\in G$, where

$u=\Pi_{1\leq j<i\leq n}[x_{i},x_{j}]^{\beta_{ij}(a_{1},\ldots,a_{i})},$

where
$\beta_{ij}(a_{1},\ldots,a_{i})\in{\mathbb{Z}}[a_{1},a_{1}^{-1},\ldots,a_{i},a_{i}^{-1}]\leq{\mathbb{Z}}\bar{G}$,
is interpreted as a tuple of elements in ${\mathbb{Z}}$,
$g\rightarrow(\gamma_{i},\ldots,\gamma_{n},\bar{\beta}_{11},\ldots,\bar{\beta}_{n-1,n}),$
where $\beta_{ij}$ are tuples.

For $H$ instead of ${\mathbb{Z}}\bar{G}$ we will have a non standard Laurent
polynomial ring $\tilde{\mathbb{Z}}\bar{G}_{NS}$ described in [11]. This is a
ring elementarily equivalent to ${\mathbb{Z}}\bar{G}$. More precisely, regular
bi-interpretation of $G$ with ${\mathbb{Z}}$ induces the regular bi-
interpretation of ${\mathbb{Z}}\bar{G}$ with ${\mathbb{Z}}$,
${\mathbb{Z}}\bar{G}=\Gamma_{1}({\mathbb{Z}})$. Then
$\tilde{\mathbb{Z}}\bar{G}_{NS}=\Gamma_{1}(\tilde{\mathbb{Z}}).$ The same
formula as in the standard case says that for $h\in H$,

$h=x_{1}^{\tilde{\gamma}_{1}}\ldots x_{n}^{\tilde{\gamma}_{n}}u,\\\ \ \ \
u=\Pi_{1\leq j<i\leq n}[x_{i},x_{j}]^{\beta_{ij}(a_{1},\ldots,a_{i})},$ (5)

where $\tilde{\gamma}_{i}\in\tilde{\mathbb{Z}},$
$\beta_{ij}(a_{1},\ldots,a_{i})\in\tilde{\mathbb{Z}}\bar{G}_{NS}$. It is
interpreted as a non-standard tuple of tuples of elements in
$\tilde{\mathbb{Z}}$,

$g\rightarrow(\tilde{\gamma}_{i},\ldots,\tilde{\gamma}_{n},\bar{\beta}_{11},\ldots,\bar{\beta}_{n-1,n}).$

There is a formula connecting
$P[a_{1},\ldots,a_{n}]\in\tilde{\mathbb{Z}}\bar{G}_{NS}$ and its evaluation
$P[\alpha_{1},\ldots,\alpha_{n}]$, where
$\alpha_{1},\ldots,\alpha_{n}\in\tilde{\mathbb{Z}}$. Lemma 3 gives the
interpretation of the action of the standard Laurent polynomial ring
${\mathbb{Z}}\bar{G}$ on $G^{\prime}$ and, therefore, the interpretation of
the action of the non-standard Laurent polynomial ring
$\tilde{\mathbb{Z}}\bar{G}_{NS}$ on $H^{\prime}$, where $H^{\prime}$ is the
$\tilde{\mathbb{Z}}\bar{G}_{NS}$ module generated by $\\{[x_{i},x_{j}]\\}$.

Denote by $a$ the image of $x\in H$ in $\tilde{\mathbb{Z}}\bar{G}_{NS}$. The
following three lemmas show how an arbitrary element in $H$ can be written in
the normal form.

######  Lemma 5.

For any $z\in H$ and $\delta\in\tilde{\mathbb{Z}},$

$[z,x^{\delta}]=[z,x]^{(a^{\delta}-1)/(a-1)},$

$(a^{\delta}-1)/(a-1)\in\tilde{\mathbb{Z}}\bar{G}_{NS}$ .

###### Proof.

There is an identity for integer $\delta$: $[z,x^{\delta},x]=[z.x,x^{\delta}]$
that implies

$[z,x^{\delta}]=[z,x]^{(a^{\delta}-1)/(a-1)}.$

Here
$(a^{\delta}-1)/(a-1)\in{\mathbb{Z}}\bar{G}={\mathbb{Z}}[a_{1},a_{1}^{-1},\ldots,a_{n},a_{n}^{-1}]$
in the standard case and, therefore, $(a^{\delta}-1)/(a-1)$ is in
$\tilde{\mathbb{Z}}\bar{G}_{NS}$ in the non-standard case. ∎

Notice that one can rewrite

$[x_{i},x_{j}]^{{a_{k}^{\delta}-1}},$

where $j<i<k,$ using the Jacobi identity as

$[x_{i},{x_{k}}^{\delta}]^{-(a_{j}-1)}[x_{j},{x_{k}}^{\delta}]^{a_{i}-1}.$

######  Lemma 6.

If $x,y\in H-H^{\prime}$ and $b$ is the image of $y$ in
$\tilde{Z}\bar{G}_{NS}$, then we have for the $\delta$-commutator

$y^{-\delta}x^{-\delta}(xy)^{\delta}=[x,y]^{-f(a,b)},$

where $f(a,b)$ is a non-standard polynomial such that

$(a-1)f(a,b)=$
$(a^{\delta}b^{\delta}-1)/(ab-1)+(1-b^{\delta})/(b-1)=b^{\delta-1}(a^{\delta-1}-1)+b^{\delta-2}(a^{\delta-2}-1)+\ldots+b(a-1).$

###### Proof.

We can write that $y^{-\delta}x^{-\delta}(xy)^{\delta}$ is in the module
generated by the commutator $[x,y]$, and we wish to see what is the non-
standard polynomial $f(a,b).$

We have $[x,y^{-\delta}x^{-\delta}(xy)^{\delta}]=[x,y]^{f(a,b)(a-1)}.$ At the
same time

$[x,y^{-\delta}x^{-\delta}(xy)^{\delta}]=[x,(xy)^{\delta}][x,y^{-\delta}x^{-\delta}]^{(ab)^{\delta}}=[x,xy]^{((ab)^{\delta}-1)/(ab-1))}[x,y^{-\delta}]^{a^{-\delta}(ab)^{\delta}}=$
$[x,y]^{(a^{\delta}b^{\delta}-1)/(ab-1)+(1-b^{\delta})/(b-1)}.$

Polynomial

$(a^{\delta}b^{\delta}-1)/(ab-1)+(1-b^{\delta})/(b-1)=b^{\delta-1}(a^{\delta-1}-1)+b^{\delta-2}(a^{\delta-2}-1)+\ldots+b(a-1)$

is divisible by $(a-1)$ in the standard ring of Laurent polynomials, therefore
it is divisible by $(a-1)$ in the non-standard ring. Since the rings are
integral domains, $f(a,b)$ is the result of this division. ∎

The following lemma is immediate.

######  Lemma 7.

$x_{1}^{\gamma_{1}}\ldots x_{n}^{\gamma_{n}}x_{1}^{\delta_{1}}\ldots
x_{n}^{\delta_{n}}=x_{1}^{\gamma_{1}+\delta_{1}}\ldots
x_{n}^{\gamma_{n}+\delta_{n}}\overline{\Pi},$ where $\overline{\Pi}\in
H^{\prime}$.

We summarise this now.

######  Theorem 3.

If $H$ is a group elementarily equivalent to $G$. Then is has the following
structure.

  1. 1.

Elements $h\in H$ have the normal form

$h=x_{1}^{\tilde{\gamma}_{1}}\ldots x_{n}^{\tilde{\gamma}_{n}}u,\\\ \ \ \
u=\Pi_{1\leq j<i\leq n}[x_{i},x_{j}]^{\beta_{ij}(a_{1},\ldots,a_{i})},$

where $\tilde{\gamma}_{i}\in\tilde{\mathbb{Z}},$
$\beta_{ij}(a_{1},\ldots,a_{i})\in\tilde{\mathbb{Z}}\bar{G}_{NS}$.

  2. 2.

$H^{\prime}$ is a module over $\tilde{\mathbb{Z}}\bar{G}_{NS}$ with generators
$\\{[x_{i},x_{j}]\\}.$

  3. 3.

Multiplication in $H$ is defined as

$x_{1}^{\gamma_{1}}\ldots x_{n}^{\gamma_{n}}\Pi_{1\leq j<i\leq
n}[x_{i},x_{j}]^{\beta_{ij}(a_{1},\ldots,a_{i})}x_{1}^{\delta_{1}}\ldots
x_{n}^{\delta_{n}}\Pi_{1\leq j<i\leq
n}[x_{i},x_{j}]^{\nu_{ij}(a_{1},\ldots,a_{i})}=$
$x_{1}^{\gamma_{1}+\delta_{1}}\ldots
x_{n}^{\gamma_{n}+\delta_{n}}{\overline{\Pi}}\ \Pi_{1\leq j<i\leq
n}[x_{i},x_{j}]^{a_{1}^{\delta_{1}}\ldots
a_{n}^{\delta_{n}}\beta_{ij}(a_{1},\ldots,a_{i})+\nu_{ij}(a_{1},\ldots,a_{i})},$

where $\bar{\Pi}$ is defined in Lemma 7.

##  4 $A$-metabelian groups

The question about varieties of exponential groups was discussed in [1]. Let
$\Gamma$ be an arbitrary exponential group with exponents in $A$. We set

$(\Gamma,\Gamma)_{A}=\langle(g,h)_{\alpha}=h^{-\alpha}g^{-\alpha}(gh)^{\alpha},g,h\in\Gamma,\alpha\in
A\rangle_{A}.$

The $A$-subgroup $(\Gamma,\Gamma)_{A}$ is called the $A$-commutant of the
group $\Gamma$. By [1, Theorem 3.4], a free abelian $A$-group with base $X$ is
a free $A$-module and is $A$-isomorphic to the factor-group of the free
$A$-group with base $X$ by its $A$-commutant. The $A$-commutant is called the
first $A$ commutant and denoted by $\Gamma^{(1,A)}$. The $A$-commutant of
$\Gamma^{(1,A)}$ is the second $A$ commutant $\Gamma^{(2,A)}.$ Then $\Gamma$
is called in [1] $n$-step $A$-solvable group if $\Gamma^{(n,A)}=1.$ Clearly
$n$-step $A$-solvable group is $n$-solvable $A$-group. If $\Gamma^{(2,A)}=1$
we call $\Gamma$ an $A$-metabelian group. Notice, that $H$ that is
elementarily equivalent to a free metabelian group is
$\tilde{\mathbb{Z}}$-metabelian because $\alpha$-commutators belong to
$H^{\prime}$ and commute in $H$.

A discretely ordered ring is an ordered ring in which there is no element
between 0 and 1. Let $A$ be a discretely ordered ring and $K$ be a
multiplicative $A$-module with generators $a_{1},\ldots,a_{n}$. Consider a
group algebra $A(K)$. Let $R$ be the $A$ algebra generated by $A(K)$ and for
all positive $\delta\in A$, by series
$(a^{\delta}-1)/(a-1)=\Sigma_{0\leq\alpha<\delta}a^{\alpha},$ and
$\Sigma_{0\leq\alpha<\delta}b^{\alpha}\frac{a^{\alpha}-1}{a-1},$ where $a,b\in
K.$

We define an $A$-metabelian exponential group $M$ with generators
$x_{1},\ldots,x_{n}$ by the following axioms:

1) $M$ is an $A$-exponential group.

Let $M^{\prime}$ consist of elements that commute with any
$\alpha$-commutator.

2) For any $\delta\in A$, $y,x\in M$, $y^{-\delta}x^{-\delta}(xy)^{\delta}$ is
in $M^{\prime}$. Moreover, $M^{(2,A)}=1$ (therefore $M$ is $A$-metabelian in
the Amaglobeli’s definition above).

3) For any $[z_{1},z_{2}]$ and any $\sigma\in R$ there is
$[z_{1},z_{2}]^{\sigma}$.

4) For any $z,x\in M$ and $\delta\in A,$
$[z,x^{\delta}]=[z,x]^{(a^{\delta}-1)/(a-1)}.$

and $y^{-\delta}x^{-\delta}(xy)^{\delta}=[x,y]^{f(a,b)},$ where

$f(a,b)=[(a^{\delta}b^{\delta}-1)/(ab-1)+(1-b^{\delta})/(b-1)]/(1-a)\in R.$

Therefore $A$-commutant is an $R$-module.

Let now $M$ be a free group with generators $x_{1},\ldots,x_{n}$ in the
category of $A$-metabelian exponential groups.

######  Lemma 8.

$M^{\prime}$ is an $R$-module generated by elements $[x_{i},x_{j}]$. If $u$
belongs to $M^{\prime}$, then it can be uniquely written as

$u=\Pi_{1\leq j<i\leq n}[x_{i},x_{j}]^{\beta_{ij}(a_{1},\ldots,a_{i})},$

where $\beta_{ij}(a_{1},\ldots,a_{i})\in R$.

###### Proof.

Consider a $\delta$-commutator $y^{-\delta}x^{-\delta}(xy)^{\delta}$. We have,
using identities 1) and 2),

$[x,y^{-\delta}x^{-\delta}(xy)^{\delta}]=[x,(xy)^{\delta}][x,y^{-\delta}x^{-\delta}]^{(ab)^{\delta}}=[x,xy]^{((ab)^{\delta}-1)/(ab-1))}[x,y^{-\delta}]^{a^{-\delta}(ab)^{\delta}}=$
$[x,y]^{(a^{\delta}b^{\delta}-1)/(ab-1)+(1-b^{\delta})/(b-1)}.$

Every commutator can be represented as $[x_{i}^{\beta},(x_{i_{1}}\ldots
x_{i_{t}})^{\alpha},x_{j_{1}}^{\alpha_{1}},\ldots,x_{j_{k}}^{\alpha_{k}}]$. We
can assume that $i\geq j_{1}\geq j_{2}\ldots\geq j_{k}$ otherwise use the
Jacobi identity. If $i$ is greater than or equal to all $i_{1},\ldots,i_{t}$,
then the representation from Lemma 5 gives elements $[x_{i},x_{i_{1}}\ldots
x_{i_{t}}]^{f(a_{i_{1}},\ldots,a_{i_{t}})}$. Bringing the commutator
$[x_{i},x_{i_{1}}\ldots x_{i_{t}}]$ to normal form and acting by
$f(a_{i_{1}},\ldots,a_{i_{t}})$ gives elements in normal form.

Suppose now some of $i_{1},\ldots,i_{t}$ is greater than $i$. Consider a
general example

$[x_{1},(x_{2}x_{3})^{\delta}]=[x_{1},(x_{2}x_{3})]^{((a_{2}a_{3})^{\delta}-1)/(a_{2}a_{3}-1)}=[x_{1},x_{2}x_{3}]^{\delta}\Pi_{0\leq\alpha<\delta}[x_{1},x_{2}x_{3},(x_{2}x_{3})^{\alpha}]=$
$[x_{1},x_{2}x_{3}]^{\delta}\Pi_{0\leq\alpha<\delta}[x_{1},x_{2}x_{3},x_{3}^{\alpha}]^{x_{2}^{\alpha}}\Pi_{0\leq\alpha<\delta}[x_{1},x_{2}x_{3},x_{2}^{\alpha}]=$
$[x_{1},x_{2}x_{3}]^{\delta}[x_{1},x_{2}x_{3},x_{3}]^{\Sigma_{0\leq\alpha<\delta}a_{2}^{\alpha}(a_{3}^{\alpha}-1)/(a_{3}-1)}[x_{1},x_{2}x_{3},x_{2}]^{\Sigma_{0\leq\alpha<\delta}(a_{2}^{\alpha}-1)/(a_{2}-1)}.$

Using the Jacobi identity we rewrite
$[x_{1},x_{2}x_{3},x_{3}]=[x_{3},x_{2}x_{3}]^{a_{1}-1}[x_{3},x_{1}]^{-a_{2}a_{3}}.$
This finally gives a representation of the commutator
$[x_{1},(x_{2}x_{3})^{\delta}]$ in the normal form. A general case can be
treated similarly.

To prove uniqueness of normal forms we need the analogue of Fox derivatives
from $A(M)$ to $R$. We define a partial Fox derivative as a linear mapping
$d_{i}:A(M)\rightarrow R$ satisfying the properties of $d_{i}$ from Section
2.1 and

$d_{i}(g^{\delta})=\frac{g^{\delta}-1}{g-1}d_{i}(g)=d_{i}(g)\Sigma_{0\leq\alpha<\delta}g^{\alpha}.$
(6)

A consequence of these is an equality:

$Dg^{-\delta}=-g^{-\delta}Dg^{\delta}.$

One can also compute for $f(a,b)\in R$

$d_{i}([x,y]^{f(a,b)})=f(a,b)_{inv}d_{i}([x,y]).$ (7)

The uniqueness of the normal form can be proved by using Fox derivatives and
the homomorphisms $\varepsilon_{I},$ where $I\subseteq\\{1,\ldots,n\\}$ and
$x_{i}\varepsilon_{j}=x_{i}$ if $i\in I$ and $x_{i}\varepsilon_{j}=1$ if
$i\not\in I$ (as it is done in [12] for normal forms in a free metabelian
group). For example, we have
$u\varepsilon_{\\{1,2\\}}=[x_{2},x_{1}]^{\beta_{12}(a_{1},a_{2})},$ hence
${\beta_{12}(a_{2},a_{1})}$ is defined uniquely. Multiply $u$ by
$[x_{2},x_{1}]^{-\beta_{21}(a_{1},a_{2})}$ to get $u^{\prime}$.

Then
$u^{\prime}\varepsilon_{\\{1,2,3\\}}=[x_{3},x_{1}]^{\beta_{31}(a_{1},a_{2},a_{3})}[x_{3},x_{2}]^{\beta_{32}(a_{1},a_{2},a_{3})}.$

Then
$d_{1}(u^{\prime}\varepsilon_{\\{1,2,3\\}})=\beta_{31(inv)}(a_{1},a_{2},a_{3})(a_{3}-1)a_{1}^{-1}a_{3}^{-1},$
$d_{2}(u^{\prime}\varepsilon_{\\{1,2,3\\}})=\beta_{32(inv)}(a_{1},a_{2},a_{3})(a_{3}-1)a_{2}^{-1}a_{3}^{-1}.$

This allows to compute uniquely $\beta_{31}(a_{1},a_{2},a_{3})$ and
$\beta_{32}(a_{1},a_{2},a_{3}),$ respectively, and so on.

∎

######  Theorem 4.

If $H\equiv G$, where $G$ is a free metabelian group, then $H$ contains a free
$\tilde{\mathbb{Z}}$-metabelian exponential group as a subgroup.

###### Proof.

We know that $H$ is $\tilde{\mathbb{Z}}$-exponential group for some
$\tilde{\mathbb{Z}}\equiv{\mathbb{Z}}.$. And $H^{\prime}$ is a
$\tilde{\mathbb{Z}}\bar{G}_{NS}$-module. Let $M$ be a free
$\tilde{\mathbb{Z}}$-metabelian exponential group defined above. Then normal
forms of elements in $M$ are exactly normal forms (5) of elements in $H$,
therefore $M$ is a subgroup of $H.$ ∎

## References

  * [1] M.G. Amaglobeli, Power groups, Journal of Mathematical Sciences, Vol. 186, No. 6, November, 2012.
  * [2] M. Aschenbrenner, A. Khelif, E. Naziazeno, T. Scanlon, The logical complexity of finitely generated commutative rings. Int. Math. Res. Not. IMRN 2020, no. 1, 112-166.
  * [3] W. Hodges, Model theory, Cambridge University Press, 1993.
  * [4] O. Kharlampovich, A. Myasnikov, What does a group algebra of a free group “know” about the group?, Annals of Pure and Applied Logic, 169 (2018) 523-547.
  * [5] O. Kharlampovich, A. Myasnikov, M. Sohrabi, Rich groups, weak second order logic and applications, De Gruyter, Groups and Model Theory, GAGTA book 2, 2021, 127-193.
  * [6] A. Khelif, Bi-interpretabilité et structures QFA: étude des groupes résolubles et des anneaux commutatifs, C. R. Acad. Sci. Paris, Ser. I 345 (2007) 59-61; and Preuves (unpublished).
  * [7] R. Kaye, Models of Peano arithmetic, Clarendon Press, 1991.
  * [8] A. Malcev, On free solvable groups, Soviet Math. Doklady 1 (1960), 65-68.
  * [9] A. G. Myasnikov, M. Sohrabi, Groups elementarily equivalent to a free 2-nilpotent group of finite rank, Algebra and Logic, Vol. 48, No. 2, March 2009.
  * [10] A. G. Myasnikov, V.N. Remeslennikov, Exponential groups, I. Foundations of the theory and tensor completions, Sib. Mat. Zh., 35, No. 5, (1994) 1106-1118.
  * [11] A. Miasnikov, A. Nikolaev, Nonstandard polynomials: algebraic properties and elementary equivalence, 2023, preprint.
  * [12] A. Myasnikov, V. Romankov Diophantine cryptography in free metabelian groups: Theoretical base, Groups Complex. Cryptol. 2014; 6 (2):103-120
  * [13] V. Romankov, On the width of verbal subgroups of solvable groups, Algebra and Logic, 1982, v. 21, no 1, 60-72.


# Do-Operation Guided Causal Representation Learning with Reduced Supervision
Strength

Jiageng Zhu1,2,3 Hanchen Xie2,3 Wael AbdAlmageed1,2,3
1 USC Ming Hsieh Department of Electrical and Computer Engineering
2 USC Information Sciences Institute
3 Visual Intelligence and Multimedia Analytics Laboratory
{jiagengz, hanchenx<EMAIL_ADDRESS>
###### Abstract

Causal representation learning has been proposed to encode relationships
between factors presented in the high dimensional data. However, existing
methods suffer from merely using a large amount of labeled data and ignore the
fact that samples generated by the same causal mechanism follow the same
causal relationships. In this paper, we seek to explore such information by
leveraging _do-operation_ for reducing supervision strength. We propose a
framework which implements _do-operation_ by swapping latent cause and effect
factors encoded from a pair of inputs. Moreover, we also identify the
inadequacy of existing causal representation metrics empirically and
theoretically and introduce new metrics for better evaluation. Experiments
conducted on both synthetic and real datasets demonstrate the superiorities of
our method compared with state-of-the-art methods.

##  1 Introduction

Figure 1:  _Do-operation_ to cause and effect factors. Light position (L) and
pendulum angle (A) are the cause of shadow position (SP) and shadow length
(SL). Applying _do-operation_ to cause factors will change the effect factors
accordingly. Oppositely, applying _do-operation_ to the effect factors will
not affect the cause factors, and the original causal relationships from L and
A to SP and SL are removed. Thus, a counterfactual sample will be created.

Causal representation learning [14] has been proposed to extract causal
relations from high dimension observations. To this end, CausalVAE [16]
contains a causal layer and a mask layer as parts of deep neural network (DNN)
architecture, and uses labels of generative factors to learn the causal
relationship between different latent factors.

However, training CausalVAE requires labels of all generative factors, which
may still pose a strong assumption. For instance, all semantic causal factors
need to be carefully annotated, which is either costly or hard to be
identified in the first place. Further, since it relies on full supervision,
CausalVAE limits the dimensionality of the latent representation to be the
same as the number of generative factors and leaves no space for other
_unknown_ confounding factors which can be entangled with semantically
meaningful latent factors and harm the performance. Moreover, CausalVAE
incorporates ground-truth generative factors so that causal layer of CausalVAE
can be trained separately from VAE. Thus, rather than extracting causal
relations from high dimension observations, causal representation in CausalVAE
is merely obtained through ground-truth generative factors, which is also used
as a part of inputs during training.

To avoid the constraint of using fully supervised training, we utilize the
_do-operation_ , illustrated in Figure 1, to learn causal representation with
reduced supervision. _Do-operation_ [13] defines an intervention that remove
certain relationships in the causal graph and replace a factor with a
constant. According to Pearl _et al._ [13], the causal effects can only
propagate from cause factors to effect factors and not inversely. Thus, when
_do-operation_ is applied to cause factors, a new and factual sample will be
generated. Conversely, when _do-operation_ is applied to effect factors, the
cause factors should be unaffected. Further, since _do-operation_ changes the
values of effect factors to constants, the newly generated sample can be
counterfactual. When training the model, since the supervision strength is
reduced to limited or even no labels, we use two latent representations
encoded from a pair of inputs and apply _do-operation_ via exchanging their
latent factors with each other. By comparing the new reconstructions after
_do-operation_ with the original inputs, a supervision signal can be
introduced.

CausalVAE [16] uses MIC and TIC [8] to evaluate the performance of causal
representation learning. However, MIC and TIC only calculate mutual
information between the latent representation and its corresponding ground
truth generative factors. We argue, therefore, that MIC and TIC can only
reflect the correctness of the marginal distribution of each factor itself,
whereas no causal relationship between factors can be measured. Therefore, we
propose new metrics for better evaluation.

Figure 2: Model structure. The input $x$ is encoded to exogenous variable
$\varepsilon$, which can be further splits into latent causal factors
$\varepsilon_{c}$ and unknown nuisance factors $\varepsilon_{u}$.
$\varepsilon_{c}$ is then mapped to endogenous variable $z$. The causal
relationships are discovered and calculated through causal discovery layer.
The unknown nuisance factors $\varepsilon_{u}$ and causal representation
$\hat{z}$ is then concatenated as the inputs of a decoder. A pair of inputs
are used to introduce supervision signal. Two encoders and two decoders in
model share same weights respectively.

Related work: Disentangled representation learning aims at attaining mutual
independent latent factors [1] and Variational Autoencoder (VAE) [7] is the
basic framework of most disentanglement methods, where the loss function is
$L_{VAE}(x,z)=-\mathbb{E}_{q_{\phi}(z|x)}[logp_{\theta}(x|z)]+D_{KL}(q_{\phi}(z|x)||p(z))$.
Other unsupervised VAEs including $\beta$-VAE [5] AnnealedVAE [2], LadderVAE
[9] and $\beta$-TCVAE [3] are proposed by modifying $L_{VAE}$. Causal
representation learning is the extension of disentangled representation
learning. To achieve causal representation, CausalVAE [16], built upon iVAE
[6], removes the requirement of prior knowledge of true causal graph by
introducing the causal layer and mask layer into the model. However, all
generative factor labels are required to train CausalVAE.

##  2 Method

Model architecture: We propose a new architecture, shown in Figure 2, as well
as a training algorithm that greatly reduces the supervision strength via a
_do-operation_ module. We use $x$ denotes an input image,
$\varepsilon=[\varepsilon_{c},\varepsilon_{u}]$ denotes exogenous latent
factors which is further split into causal and unknown nuisance exogenous
factors, $z$ denotes latent causal factors, $\hat{z}$ denotes latent causal
factors after causal discovery and $\hat{x}$ denotes reconstructed images.

In contrast with CausalVAE, our framework uses $\varepsilon_{u}$ to encode
unknown nuisance factors. Meanwhile, similar to CausalVAE, the exogenous
factors $\varepsilon_{c}$ are first transformed to endogenous latent factors
$z$, and a causal discovery layer (CDL) propagates causal effects from parent
factors to their child factors. We use a graph autoencoder (GAE) [12] as CDL,
which learns nonlinear causal relationships and thus generalizes over NOTEARS
[17] used in CausalVAE. The unknown nuisance latent factors $\varepsilon_{u}$
are concatenated with the latent causal factors $\hat{z}$ as the input of a
decoder. As discussed in [10], unsupervised learning can not identify expected
latent representations so that supervision is necessary. To reduce supervision
strength in CausalVAE and inspired by [11], we use a pair of inputs and
implement _do-operation_ during training to utilize a weak supervision signal.
The CDL, that applies causal effect from parent factors to child factors, is
the key to implement _do-operation_ , descried in Section 2, in order to
decrease supervision strength. By using this new training strategy, we show in
Section 4 that no label is needed during training on synthetic datasets and
only a small amount of labels is needed on real datasets.

Figure 3: _Do-operation_ on cause factors encourage model to learn correct
causal relationships, while _do-operation_ on effect factors prevent model
learning wrong causal relationship.

Do-operation illustrates causal relationship: _Do-operation_ [13] defines an
intervention that deletes a specific relationship in the causal graph and
replaces factors with constants. As shown in Figure 1, if _do-operation_ is
applied to cause factors, since the original causal graph stays unchanged, the
effect factors will be affected according to their parent factors. Conversely,
when _do-operation_ is applied to effect factors, cause factors will not
affect the value of effect factors. This process can be shown in Equations 1
and 2.

$\displaystyle
do(z_{c}^{(l)}):=z_{c}^{(m)};~{}~{}~{}f([do(z_{c}^{(l)}),z_{e}^{(l)}])=[z_{c}^{(m)},z_{e}^{(m)}];\hfill$
(1) $\displaystyle
do(z_{e}^{(l)}):=z_{e}^{(m)};~{}~{}~{}f([z_{c}^{(l)},do(z_{e}^{(l)})])=[z_{c}^{(l)},~{}~{}z_{e}^{(m)}];$
(2)

where $f$ is the causal relationship function, and generative factors $z$ are
split into cause factors $z_{c}$ and effect factors $z_{e}$. By assigning
previous cause factors $z_{c}^{(l)}$ with new value $z_{c}^{(m)}$, effect
factors $z_{e}$ will change accordingly. Oppositely, if _do-operation_ is
applied to effect factors $z_{e}^{(l)}$ whose value is replaced by
$z_{e}^{(m)}$, cause factors $z_{c}$ should stay unchanged. Besides, The
output of causal function $f$ can be counterfactual since the original causal
relationship has changed.

Do-operation on cause factors (Do-Cause): As shown in the Equation 1, if we
apply _do-operation_ to cause factors $z_{c}$, since $z_{c}$ have no parent
factors, the causal graph is unchanged and the value of effect factors $z_{e}$
should change accordingly. To train our model, since no label or limited
labels of generative factors are available, we use pairs of images as a weak
supervision signal to encourage the model to learn causal representation. As
illustrated in Figure 3a, except the regular propagation of inputs, after two
endogenous latent factors $z_{1}$ and $z_{2}$ are encoded from a pair of
inputs $x_{1}$ and $x_{2}$, we exchange the cause factors of two latent
representations with each other to create two new latent representation
$z_{1}^{\prime}=[do(z_{1c}),z_{1e}]$ and $z_{2}^{\prime}=[do(z_{2c}),z_{2e}]$,
where a latent factor is cause or effect is determined by the learnable causal
matrix $A$ in CDL. As shown in Equation 3, two new representations
$z_{1}^{\prime}$ and $z_{2}^{\prime}$ are fed into the CDL and then
concatenated with their corresponding unknown nuisance factors
$\varepsilon_{u_{1}}$ and $\varepsilon_{u_{2}}$ as inputs of the decoder.

$\begin{split}z_{1}^{\prime}:=[do(z_{c_{1}}),z_{e_{1}}]&=[z_{c_{2}},z_{e_{1}}];~{}~{}~{}\hat{z}_{1}^{\prime}=f(z_{1}^{\prime});~{}~{}~{}\hat{x}_{1}^{\prime}=Dec(\hat{z}_{1}^{\prime},\varepsilon_{u_{2}})\\\
z_{2}^{\prime}:=[do(z_{c_{2}}),z_{e_{2}}]&=[z_{c_{1}},z_{e_{2}}];~{}~{}~{}\hat{z}_{2}^{\prime}=f(z_{2}^{\prime});~{}~{}~{}\hat{x}_{2}^{\prime}=Dec(\hat{z}_{2}^{\prime},\varepsilon_{u_{1}})\\\
\end{split}$ (3)

Recall that from Equation 1, the new outputs of CDL should be same with the
original outputs of CDL, where $\hat{z}_{1}^{\prime}=\hat{z}_{2}$ and
$\hat{z}_{2}^{\prime}=\hat{z}_{1}$, since _do-operation_ on cause factors does
not change causal graph, and the unchanged causal graph propagates causal
relationships from cause factors to effect factors. Since the new latent
causal representation $\hat{z}_{2}^{\prime}$ and $\hat{z}_{1}^{\prime}$ should
be same with the original latent causal representation $z_{1}$ and $z_{2}$,
their corresponding reconstructions $\hat{x}_{1}^{\prime}$ and
$\hat{x}_{2}^{\prime}$ after the decoder should also be same with the the
original inputs $x_{2}$, $x_{1}$. As shown in Equation 4, by comparing new
reconstructions with the original inputs, the model is encouraged to learn the
correct causal relationships, where $d$ is distance function, such as binary
cross entropy or mean square error.

$L_{cause}=d(\hat{x}_{1}^{\prime},x_{2})+d(\hat{x}_{2}^{\prime},x_{1})$ (4)

Do-operation on effect factors (Do-Effect): Compared with _do-operation_ on
the cause factors, since the causal graph will change when applying _do-
operation_ to the effect factors, the latent effect factors should be
exchanged after the CDL in order to remove the effect of cause factors. The
whole process of _do-operation_ on the effect factors can be shown in Equation
5.

$\begin{split}\hat{z}_{1}=f(z_{1});~{}~{}~{}\hat{z}_{1}^{\prime\prime}:=[\hat{z}_{c_{1}},do(\hat{z}_{e_{1}})]&=[\hat{z}_{c_{1}},\hat{z}_{e_{2}}];~{}~{}~{}\hat{x}_{1}^{\prime\prime}=Dec(\hat{z}_{1}^{\prime\prime},\varepsilon_{u_{1}})\\\
\hat{z}_{2}=f(z_{2});~{}~{}~{}\hat{z}_{2}^{\prime\prime}:=[\hat{z}_{c_{2}},do(\hat{z}_{e_{2}})]&=[\hat{z}_{c_{2}},\hat{z}_{e_{1}}];~{}~{}~{}\hat{x}_{2}^{\prime\prime}=Dec(\hat{z}_{2}^{\prime\prime},\varepsilon_{u_{2}})\\\
\end{split}$ (5)

Since _do-effect_ changes the existing causal graph, the new latent
representations $\hat{z}_{1}^{\prime\prime}$ and $\hat{z}_{2}^{\prime\prime}$
are not consistent with their corresponding latent representations $z_{1}$ and
$z_{2}$. Thus, after decoder, the new reconstructions
$\hat{x}_{1}^{\prime\prime}$ and $\hat{x}_{2}^{\prime\prime}$ will be
different from their original inputs $x_{1}$ and $x_{2}$. Further, the new
reconstructions are are actually counterfactual images as illustrated in
Figure 1b. In practice, using MSE or BCE may lead to degenerated solution
where $\hat{x}^{\prime\prime}$ are random noise. To solve this issue, we use a
classifier $C_{w}$ to distinguish factual images, including $x_{i}$,
$\hat{x}_{i}$ and $\hat{x}_{i}^{\prime}$, with counterfactual images
$\hat{x}_{i}^{\prime\prime}$, where classifier and VAE are trained
alternatively. The losses of training classifier and _do-operation_ on the
effect factors are shown in Equations 6 and 7 respectively.

$\displaystyle
L_{cla}=\mathbf{BCE}(C_{w}(x_{i}),\mathbf{1})+\mathbf{BCE}(C_{w}(\hat{x}_{i}),\mathbf{1})+\mathbf{BCE}(C_{w}(\hat{x}_{i}^{\prime}),\mathbf{1})+\mathbf{BCE}(C_{w}(\hat{x}_{i}^{\prime\prime}),\mathbf{0})\hfill$
(6) $\displaystyle
L_{effect}=\mathbf{BCE}(C_{w}(\hat{x}_{1}^{\prime\prime}),\mathbf{0})+\mathbf{BCE}(C_{w}(\hat{x}_{2}^{\prime\prime}),\mathbf{0})$
(7)

Training model with reduced supervision strength: As discussed in Section 1
and empirically proven in Section 4, our method only requires a small amount
of supervision to train. For synthetic datasets, where actually no label are
needed, the loss function is shown in Equation 8, where $L_{VAE}$ is same with
$L_{VAE}$ shown in Section 1.

$L_{no-label}=L_{VAE}(x,z)+\alpha L_{cause}+\beta
L_{effect}+\gamma||\hat{z}-z||^{2}_{2}+h(A)$ (8)

where $\alpha$, $\beta$ and $\gamma$ are hyperparameters for regularizations.
$||\hat{z}_{i}-z_{i}||^{2}_{2}$ is added to the loss since the outputs of CDL
should align with their inputs. $h(A)$ is an acyclicity constraint for the
causal graph $A$. In our implementation, we use $h(A)=tr(e^{A\odot A})-d$ as
proposed in [17].

If some labels of generative factors are available, similar to CausalVAE [16],
we utilize them by adding label constrains to Equation 8 which leads to
Equation 9, where $f$ is CDL.

$L_{semi}=L_{no-label}+||u-f(u)||_{2}^{2}+D_{KL}(q_{\phi}(z|x,u)||p(z|u))$ (9)

##  3 Evaluation Metrics For Causal Representation Learning

Maximum Information Coefficient (MIC) and Total Information Coefficient (TIC)
[8] have originally been proposed as general purpose metrics to measure
correlation between two random variables. Both metrics range from $0$ to $1$
and the higher value indicates better performance.

Figure 4: One simple example of calculating new metrics.

CausalVAE [16] suggested using MIC and TIC for evaluating causal
representation learning, despite the following inadequacy. In CausalVAE, MIC
and TIC first calculate the information relevance between every ground truth
labels and their corresponding learned latent factors. Then, the means of MIC
and TIC for every factors are used as the final metrics values. However, MIC
and TIC only measure correlations between a latent factor and its
corresponding generative factor, and can not evaluate the correctness of
relationships between cause and effect factors. Therefore, we argue that MIC
and TIC are not suitable for evaluating causal representation learning where
the goal is to learn the correct causal relationships between cause and effect
factors. An intuitive example for illustrating the deficiency of MIC and TIC
can be found in Appendix.

To address this issue, we propose four new metrics: PosMIC, PosTIC, NegMIC and
NegTIC. PosMIC and PosTIC are used to evaluate the causal relation correctness
between latent factors, where higher value are expected. NegMIC and NegTIC are
used to evaluate the falseness of causal relation discovery among latent
factors, where lower value are expected. Additionally, to fully characterize
the performance of causal representation learning using a single metric, we
propose using the harmonic mean of the new metrics, i.e. $F_{1}^{MIC}$ and
$F_{1}^{TIC}$. We will first describe how the proposed new metrics are
calculated and then discuss their adequacy over the metrics used in CausalVAE.

Calculating PosMIC, PosTIC, NegMIC and NegTIC: As illustrated in Figure 4, to
calculate PosMIC and PosTIC, given ground truth causal graph $G$, we first set
the latent effect factors ($z_{3}$ and $z_{4}$ in Figure 4) to $0$. If the
causal layer learns the correct relationship between the latent cause factors
and the latent effect factors, $z_{3}$ and $z_{4}$ values are determined by
the cause factors $z_{1}$ and $z_{2}$. Then, we separately calculate the
MIC/TIC values of the latent effect factors and their corresponding generative
factors. Finally, the means of the MIC/TIC of all latent effect factors values
are taken to be the PosMIC and PosTIC values. NegMIC and NegTIC are calculated
in the opposite way, where the latent cause factors are set to $0$, and the
final MIC/TIC values are calculated between the latent cause factors after the
causal layer and their corresponding generative factors. Ideally, the causal
relationship should unidirectionally propagates from cause to effect, not in
the opposite direction. Thus, the lower NegMIC and NegTIC indicate better
performance of causal representation learning. To better compare different
models and fully characterize the performance of causal representation
learning, we consider Pos and Neg metrics together by calculating the harmonic
mean: $F_{1}^{MIC}=2*\frac{PosMIC\cdot(1-NegMIC)}{PosMIC+(1-NegMIC)}$.
$F_{1}^{TIC}$ of PosTIC and NegTIC is calculated similarly.

Figure 5: Correlation of different metrics on Pendulum dataset. MIC and TIC
show low correlation with rubrics for causal discovery. Contrarily, our
proposed metrics shows high and expected correlation with those rubrics.

Adequacy of proposed metrics: By conducting experiments on the Pendulum
dataset, introduced in Section 4, we empirically show the advantage of the new
metrics by proving that MIC and TIC fail to distinguish between models with
correct and wrong causal graphs. We initialize causal graphs $A$ of the
CausalVAEs with different causal graphs and stop the gradient of elements if
they are initialized with zero, such that CausalVAEs are created with various
correctness levels of the causal graphs. If a causal graph $A$ is initialized
identical to the correct causal graph, the performance of that CausalVAE is
expected to be optimal since the correct causal relationship is obtained by
initialization. Conversely, the performance of wrong causal graph initialized
CausalVAE is expected to be poor. After training, we calculate correlations
among metrics used for causal representation learning and rubrics used in the
causal discovery research area: True Positive Rate (TPR), False Discovery Rate
(FDR), and Structural Hamming Distance (SHD). TPR and FDR calculate the rate
of discovering correct and wrong causal relations, respectively. SHD is the
minimum number of modifications to correct a causal graph. As shown in Figure
5, MIC and TIC have a low correlation with TPR, FDR, and SHD. In contrast, our
proposed new metrics PosMIC, PosTIC, NegMIC, and NegTIC have significant
higher correlation with three rubrics used in causal inference. PosMIC and
PosTIC are more positively correlated with TPR, and NegMIC and NegTIC are
positively correlated with FDR and SHD.

##  4 Experimental Evaluation

Table 1: Causal representation metrics tested on Pendulum and Flow.

3 Models Pendulum Flow MIC $\mathbf{\uparrow}$ TIC $\mathbf{\uparrow}$ PosMIC
$\mathbf{\uparrow}$ PosTIC $\mathbf{\uparrow}$ NegMIC $\mathbf{\downarrow}$
NegTIC $\mathbf{\downarrow}$ $F_{1}^{MIC}$ $\mathbf{\uparrow}$ $F_{1}^{TIC}$
$\mathbf{\uparrow}$ MIC $\mathbf{\uparrow}$ TIC $\mathbf{\uparrow}$ PosMIC
$\mathbf{\uparrow}$ PosTIC $\mathbf{\uparrow}$ NegMIC $\mathbf{\downarrow}$
NegTIC $\mathbf{\downarrow}$ $F_{1}^{MIC}$ $\mathbf{\uparrow}$ $F_{1}^{TIC}$
$\mathbf{\uparrow}$ Fully Supervised learning methods (all labels are used)
CausalVAE 95.1$\pm$2.1 81.6$\pm$1.9 53.0$\pm$4.5 43.4$\pm$3.7 46.6$\pm$3.9
37.0$\pm$4.2 53.2$\pm$3.6 51.4$\pm$3.2 72.1 $\pm$1.3 56.4 $\pm$1.6 45.1
$\pm$4.8 36.7 $\pm$4.2 43.3 $\pm$5.1 33.7 $\pm$3.2 50.2 $\pm$4.4 47.3 $\pm$3.7
ConditionVAE 93.8$\pm$3.3 80.5$\pm$1.4 36.5$\pm$3.0 27.8$\pm$3.2 34.6$\pm$4.2
25.7 $\pm$3.6 46.9 $\pm$4.7 40.5 $\pm$3.5 75.5 $\pm$2.3 56.5 $\pm$1.8 28.6
$\pm$3.2 21.3 $\pm$3.1 27.2 $\pm$2.8 20.6 $\pm$2.7 41.1 $\pm$5.1 33.6 $\pm$4.0
Unsupervised Learning methods (no label is used) CausalVAE(unsup) 21.2
$\pm$1.4 12.0 $\pm$1.0 20.5 $\pm$2.6 11.8 $\pm$2.7 23.3 $\pm$3.2 14.7 $\pm$1.9
32.4 $\pm$3.4 20.7 $\pm$3.1 20.5 $\pm$4.7 11.8 $\pm$2.6 22.8 $\pm$2.7 12.5
$\pm$1.4 21.5 $\pm$2.4 12.0 $\pm$1.9 35.3 $\pm$5.6 21.9 $\pm$4.7 BetaVAE 22.6
$\pm$4.6 12.5 $\pm$2.2 21.2 $\pm$2.7 12.7 $\pm$2.9 23.7 $\pm$3.1 12.6 $\pm$1.9
33.2 $\pm$3.3 22.2 $\pm$2.7 23.6 $\pm$3.2 12.5 $\pm$0.6 23.6 $\pm$3.6 12.5
$\pm$1.9 22.1 $\pm$2.5 11.4 $\pm$1.9 36.2 $\pm$4.9 21.9 $\pm$4.2 LadderVAE
22.4 $\pm$3.1 12.8 $\pm$1.2 15.2 $\pm$1.9 8.6 $\pm$1.0 14.2 $\pm$1.7 7.9
$\pm$0.9 25.8 $\pm$3.0 15.7 $\pm$2.8 34.3 $\pm$4.3 24.4 $\pm$1.5 16.2 $\pm$1.8
10.5 $\pm$1.0 13.3 $\pm$1.2 6.9 $\pm$0.6 27.3 $\pm$ 3.2 18.9 $\pm$2.8 Reduced
supervision method (no label is used; supervision source is image pairing )
Our method 86.6 $\pm$7.9 74.5 $\pm$5.1 54.1 $\pm$4.5 44.0 $\pm$4.2 40.2
$\pm$3.9 31.6 $\pm$3.2 56.8 $\pm$5.2 53.6 $\pm$4.3 65.5 $\pm$6.6 56.7 $\pm$4.9
50.7 $\pm$4.7 41.3 $\pm$4.2 36.8 $\pm$3.8 27.2 $\pm$3.0 56.3 $\pm$5.9 52.7
$\pm$4.9 3

Datasets: Following [16], we use two synthetic datasets and two real world
datasets. Pendulum focuses on pendulum angle, light angle, shadow location and
shadow length, and Flow focuses on ball size, water height, hole and water
flow. CelebA(SMILE) focuses on gender, smile, eyes open and mouth open, and
CelebA(BEARD) focuses on age, gender and beardedness and baldness. We refer
readers to [16] and Appendix for more details. Besides using MIC and TIC as
evaluation metrics, we also use our new metrics for better evaluating causal
representation learning.

###  4.1 Comparisons with State-Of-The-Art (SOTA)

Synthetic datasets: Our method achieves comparable results on MIC and TIC
compared with the fully supervised learning methods CausalVAE [16] and
ConditionVAE [15], and outperform other unsupervised learning methods. As
shown in Section 4, comparing to CausalVAE and ConditionVAE, our method can
achieve slightly better performance on PosMIC, PosTIC, NegMIC and NegTIC.
Unsupervised methods achieve low value on NegMIC and NegTIC due to barely
learning semantic information. Further, the result of using a few labels to
train our method is included in Appendix.

(a)  MIC $\mathbf{\uparrow}$.

(b) PosMIC $\mathbf{\uparrow}$.

(c) NegMIC $\mathbf{\downarrow}$.

(d) $F_{1}^{MIC}$ $\mathbf{\uparrow}$.

(e)  TIC $\mathbf{\uparrow}$.

(f) PosTIC $\mathbf{\uparrow}$.

(g) NegTIC $\mathbf{\downarrow}$.

(h) $F_{1}^{TIC}$ $\mathbf{\uparrow}$.

Figure 6: Box plots of metrics tested on CelebA(BEARD). Our method outperforms
CausalVAE under various supervision strengths, where the advantage of our
method is better revealed with weaker supervision strength. All experiments
results are reproduced by us, except the blue star is the mean value reported
in [16].

Real datasets: Compared with synthetic datasets, there are $40$ generative
factors in CelebA dataset. If no label is available during training CelebA
datasets, the search space for the model becomes intractable as there are
$2^{40}$ different binary causal graphs for $40$ factors. To decrease the
difficulty, label information is needed to control the semantic factors which
are encoded in each dimension of latent space [4]. For comprehensive
comparison, our model and baselines are trained with
$\\{20\%,40\%,60\%,80\%,100\%\\}$ of labeled data, and the remaining samples
are unlabelled. As shown in Figures 6 and 7, our method consistently and
significantly outperforms CausalVAE. Furthermore, with fewer labels, our
method outperforms CausalVAE more appreciably.

(a)  MIC $\mathbf{\uparrow}$.

(b)  PosMIC $\mathbf{\uparrow}$.

(c)  NegMIC $\mathbf{\downarrow}$.

(d) $F_{1}^{MIC}$ $\mathbf{\uparrow}$.

(e)  TIC $\mathbf{\uparrow}$.

(f)  PosTIC $\mathbf{\uparrow}$.

(g) NegTIC $\mathbf{\downarrow}$.

(h) $F_{1}^{TIC}$ $\mathbf{\uparrow}$.

Figure 7: Box plots of metrics tested on CelebA(SMILE). Our method outperforms
CausalVAE under various supervision strengths, where the advantage of our
method is better revealed with weaker supervision strength. All experiments
results are reproduced by us, except the blue star is the mean value reported
in [16].

##  5 Conclusion

In this work, we propose a novel architecture for causal representation
learning with reduced supervision strength, exploiting the _do-operation_ . We
use a pair of images and apply _do-operation_ to both latent cause and effect
factors for new reconstructions. By comparing the new reconstructions after
_do-operation_ and the original inputs, the supervision strength is reduced.
Furthermore, to better evaluate causal representation learning, we propose new
metrics to address adequacy of existing metrics. We empirically demonstrate
the advantages of our method on both synthetic and real datasets.

Acknowledgement: This material is based on research sponsored by Air Force
Research Laboratory under agreement number FA8750-19-1-1000. The U.S.
Government is authorized to reproduce and distribute reprints for Governmental
purposes notwithstanding any copyright notation thereon.

## References

  * [1] Yoshua Bengio, Aaron Courville, and Pascal Vincent.  Representation learning: A review and new perspectives.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8):1798–1828, 2013.
  * [2] Christopher P. Burgess, Irina Higgins, Arka Pal, Loic Matthey, Nick Watters, Guillaume Desjardins, and Alexander Lerchner.  Understanding disentangling in $\beta$-vae, 2018.
  * [3] Ricky T. Q. Chen, Xuechen Li, Roger Grosse, and David Duvenaud.  Isolating sources of disentanglement in variational autoencoders, 2019\.
  * [4] Zunlei Feng, Xinchao Wang, Chenglong Ke, An-Xiang Zeng, Dacheng Tao, and Mingli Song.  Dual swap disentangling.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * [5] Irina Higgins, Loïc Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner.  beta-vae: Learning basic visual concepts with a constrained variational framework.  In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
  * [6] Ilyes Khemakhem, Diederik Kingma, Ricardo Monti, and Aapo Hyvarinen.  Variational autoencoders and nonlinear ica: A unifying framework.  In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 2207–2217. PMLR, 26–28 Aug 2020.
  * [7] Diederik P. Kingma and Max Welling.  Auto-encoding variational bayes.  In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
  * [8] Justin B. Kinney and Gurinder S. Atwal.  Equitability, mutual information, and the maximal information coefficient.  Proceedings of the National Academy of Sciences, 111(9):3354–3359, 2014.
  * [9] Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors.  Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, 2016.
  * [10] Francesco Locatello, Stefan Bauer, Mario Lucic, Gunnar Rätsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem.  Challenging common assumptions in the unsupervised learning of disentangled representations, 2019.
  * [11] Francesco Locatello, Michael Tschannen, Stefan Bauer, Gunnar Rätsch, Bernhard Schölkopf, and Olivier Bachem.  Disentangling factors of variations using few labels.  In International Conference on Learning Representations, 2020.
  * [12] Ignavier Ng, Shengyu Zhu, Zhitang Chen, and Zhuangyan Fang.  A graph autoencoder approach to causal structure learning.  arXiv preprint arXiv:1911.07420, 2019.
  * [13] Judea Pearl.  Causality: Models, Reasoning and Inference.  Cambridge University Press, 2nd edition, 2009.
  * [14] Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio.  Toward causal representation learning.  Proceedings of the IEEE, 109(5):612–634, 2021.
  * [15] Kihyuk Sohn, Honglak Lee, and Xinchen Yan.  Learning structured output representation using deep conditional generative models.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
  * [16] Mengyue Yang, Furui Liu, Zhitang Chen, Xinwei Shen, Jianye Hao, and Jun Wang.  Causalvae: Disentangled representation learning via neural structural causal models.  In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021, pages 9593–9602. Computer Vision Foundation / IEEE, 2021.
  * [17] Xun Zheng, Bryon Aragam, Pradeep Ravikumar, and Eric P. Xing.  DAGs with NO TEARS: Continuous Optimization for Structure Learning.  In Advances in Neural Information Processing Systems, 2018.

##  Appendix A Appendix

###  A.1 Importance of the _do-operation_

To prove the importance of the different _do-operation_ modules used in our
method, we evaluate our model by removing different _do-operation_ modules in
the architecture. As shown in Table A1, by removing Do-Cause, the model loses
the ability of finding causal relationship. Removing Do-effect will lead to
performance decrease on NegMIC and NegTIC.

Therefore, the performance on MIC, TIC, PosMIC and PosTIC degrades similar to
unsupervised CausalVAE. By removing Do-effect and keeping Do-Cause, the
performance on MIC, TIC, PosMIC and PosTIC significantly improves, while the
performance on NegMIC and NegTIC is worse than full model where both cause and
effect _do-operation_ modules are used.

Table A1: Causal representation metrics of model with different _do-operation_
module applied

3 Do-Cause Do-Effect MIC $\uparrow$ TIC $\uparrow$ PosMIC $\uparrow$ PosTIC
$\uparrow$ NegMIC $\downarrow$ NegTIC $\downarrow$ $F_{1}^{MIC}$ $\uparrow$
$F_{1}^{TIC}$ $\uparrow$ - ✓ 30.6 25.9 23.6 17.2 19.2 11.6 36.5 28.8 ✓ - 84.2
72.3 52.6 42.1 46.3 37.9 53.1 50.2 ✓ ✓ 86.6 74.5 54.1 44.0 40.2 31.6 56.8 53.6
3

###  A.2 GAE comparison with NOTEARS

As we mentioned in Section 3, our method incorporate a graph autoencoder (GAE)
[17] as causal discovery layer. GAE can learn nonlinear structural causal
relationships thus generalizing over NOTEARS [29] which can only learn linear
mapping. As shown in Table A2, if we replace GAE with NOTEARS for causal
discovery layer, the performance of our model will be harmed since the causal
relationships between latent factors can be nonlinear in many cases.

Table A2: Causal representation metrics tested on Pendulum and Flow. Higher
MIC, TIC, PosMIC and PosTIC value mean better performance. Lower NegMIC and
NegTIC value mean better performance. Our methods are trained using only
$10\%$ of label.

3 Models Pendulum MIC $\uparrow$ TIC $\uparrow$ PosMIC $\uparrow$ PosTIC
$\uparrow$ NegMIC $\downarrow$ NegTIC $\downarrow$ $F_{1}^{MIC}$ $\uparrow$
$F_{1}^{TIC}$ $\uparrow$ NOTEARS 40.3 30.9 27.3 17.3 26.2 16.2 39.6 28.7 Our
method 86.6 74.5 54.1 44.0 40.2 31.6 56.8 53.6 3

###  A.3 Synthetic datasets experiments of using a few labels

In Section 4, we demonstrate our method can outperform other methods which do
not use the label, and our method can achieve comparable performance compared
with CausalVAE evaluated by PosMIC, PosTIC, NegMIC, and NegTIC. To test our
method more comprehensively on synthetic datasets, we conduct experiments of
our method, CausalVAE and ConditionVAE using only $10\%$ of labels. As shown
in Section A.3, trained under only $10\%$ of labeled data, CausalVAE and
ConditionVAE are difficult to learn either good semantic meaning latent
factors which is reflected by MIC and TIC, or attain true causal relationship
between cause factors and effect factors, which is shown by PosMIC and PosTIC.
As we discussed in Section 4, since CausalVAE fails to encode useful enough
semantic factors information, it achieves a low value on NegMIC and NegTIC.
ConditionVAE achieves low NegMIC and NegTIC because it aims at learning
disentangled latent representation, where each latent factor is enforced to be
independent of each other. Thus no causal relationship, correct or wrong, will
be learned.

Table A3: Causal representation metrics tested on Pendulum and Flow. Higher
MIC, TIC, PosMIC and PosTIC value mean better performance. Lower NegMIC and
NegTIC value mean better performance. Our methods are trained using only
$10\%$ of label.

3 Models Pendulum Flow MIC TIC PosMIC PosTIC NegMIC NegTIC $F_{1}^{MIC}$
$F_{1}^{TIC}$ MIC TIC PosMIC PosTIC NegMIC NegTIC $F_{1}^{MIC}$ $F_{1}^{TIC}$
All labels used CausalVAE [26] 95.1 81.6 53.0 43.4 46.6 37.0 53.2 51.4 72.1
56.4 45.1 36.7 43.3 33.7 47.3 33.6 ConditionVAE [22] 93.8 79.6 36.5 27.8 34.6
25.7 46.9 40.5 75.5 56.5 28.6 21.3 27.2 20.6 41.1 33.6 10% labels used
CausalVAE [26] 64.7 55.9 39.4 30.7 37.6 28.2 48.3 43.0 53.2 46.7 30.6 22.5
30.3 21.7 42.5 35.0 ConditionVAE [22] 63.2 52.1 30.5 21.3 29.4 24.6 42.6 33.2
55.7 48.1 29.6 20.8 26.7 20.1 42.1 33.0 Our method 94.6 80.7 70.2 59.5 41.2
30.4 63.9 63.9 75.7 56.1 60.3 51.8 37.8 29.6 61.2 59.7 3

###  A.4 Experiments detail

The true causal graph of each datasets are shown in Figure A1.

Figure A1: Ground truth Causal graph of four datasets.

We use one NVIDIA 1080 Ti GPU as our training and inference device. Following
CausalVAE [26] architecture, we show the VAE architecture of synthetic
datasets in Section A.4 and VAE architecture of CelebA dataset in Section A.4.
For latent representation, we also follow the setting of CausalVAE where
latent space $z$ is extanded to matrix $z\in R^{n\times k}$ and $n$ is the
number of concept and $k$ is latent dimension of each concept. $k$ is set to
$4$ for VAE used in synthetic datasets and $k$ is set to $32$ for VAE used in
CelebA dataset.

As described in Section 3, our loss function for no label training is shown in
Equation 10 and the loss for label training is shown in Equation 11. The
hyperparameters $(\alpha,\beta,\gamma)$ are grid search among
$\\{1e^{-3},1e^{-2},1e^{-1},1.0\\}$. For training with label, the
hyperparameter of $l_{u}$ is always set to $1$.

Table A4: Synthetic datasets model architecture

3 encoder | decoder
---|---
4*96*96*900 fc. 1ELU | concepts*(4*300 fc. 1ELU)
900*300 fc. 1ELU | concepts*(300*300 fc. 1ELU)
300*2*concepts*k fc. | concepts*(300*1024 fc. 1ELU)
- | concepts*(1024*4*96*96 fc.)
3 |

Table A5: CelebA datasets model architecture

3 encoder | decoder
---|---
- | 1*1 conv. 128 1LReLU(0.2), stride 1
4*4 conv. 32 1LReLU (0.2), stride 2 | 4*4 convtranspose. 64 1LReLU(0.2), stride 1
4*4 conv. 64 1LReLU (0.2), stride 2 | 4*4 convtranspose. 64 1LReLU(0.2), stride 1
4*4 conv. 64 1LReLU (0.2), stride 2 | 4*4 convtranspose. 32 1LReLU(0.2), stride 1
4*4 conv. 64 1LReLU (0.2), stride 2 | 4*4 convtranspose. 32 1LReLU(0.2), stride 1
4*4 conv. 256 1LReLU (0.2), stride 2 | 4*4 convtranspose. 32 1LReLU(0.2), stride 1
1*1 conv. 3, stride1 | 4*4 convtranpose. 3, stride 2
3 |

###  A.5 Do-operation implementation detail

As we described in section 3, we apply _do-operation_ to both latent cause and
effect factors. To better show the implementation of _do-operation_ in our
work, we describe the process in Figure A2. As illustrated in Figure A2, the
cause and effect factors in the latent space are decided by learned causal
matrix $A$ which is identical to causal matrix used in causal discovery layer.
After deciding the cause and effect factors, we separately apply _do-
operation_ on cause and effect factors. Applying _do-operation_ to cause
factors is straightforward since cause factors have no parent factors and the
causal graph stays unchanged. Oppositely, applying _do-operation_ to effect
factors will both fix the value of effect factors and remove affects from
cause factors. Thus, if we swap the effect factors before causal discovery
layer, the original causal relationships from cause factors to effect factors
still hold. To eliminate the original causal relationships, the swapping
operation on effect factors should be applied after causal discovery layer.

According to [18], _do-operation_ replace factors with constants and remove
all causal relationships towards the factors. If the label information is
available, the _do-operation_ is straightforward since the latent factors
value can be easily fixed with the label value. However, if the label
information is missing, even though the latent factor value can be replaced by
some random values, such random values do not guarantee to be meaningful. To
obtain the proper constants which replace latent factors, another sample is
needed since the reconstruction task force the latent representation encoded
from the input are meaningful and can be used as source for _do-operation_.

Figure A2: _Do-operation_ is applied to both cause factors and effect factors.
_Do-operation_ on cause factors encourage model to learn correct causal
relationships and _do-operation_ on effect factors prevent model learning
wrong causal relationships.

###  A.6 Counter example to prove the weakness of MIC and TIC

Assuming we have four independent gaussian variables $A$, $B$, $C$ and $D$,
where $A\sim\mathcal{N}(\mu_{a},\sigma_{a}^{2})$,
$B\sim\mathcal{N}(\mu_{b},\sigma_{b}^{2})$,
$C\sim\mathcal{N}(\mu_{c},\sigma_{c}^{2})$ and
$D\sim\mathcal{N}(\mu_{d},\sigma_{d}^{2})$. We can create other four gaussian
variables $A^{\prime}$, $B^{\prime}$, $C^{\prime}$ and $D^{\prime}$ where
$A^{\prime}\sim\mathcal{N}(\mu_{a},\sigma_{a}^{2})$,
$B^{\prime}=\frac{\mu_{b}}{\mu_{a}}\cdot
A^{\prime}+(\sigma_{b}-\frac{\mu_{b}}{\mu_{a}}\sigma_{a})\cdot\mathcal{N}(0,1)$,
$C^{\prime}=\frac{\mu_{c}}{\mu_{a}}\cdot
A^{\prime}+(\sigma_{c}-\frac{\mu_{c}}{\mu_{a}}\sigma_{a})\cdot\mathcal{N}(0,1)$
and $D^{\prime}=\frac{\mu_{d}}{\mu_{a}}\cdot
A^{\prime}+(\sigma_{d}-\frac{\mu_{d}}{\mu_{a}}\sigma_{a})\cdot\mathcal{N}(0,1)$.
By creating new variables like this, it is easy to see that $A^{\prime}$ has
same distribution with $A$, $B^{\prime}$ has same distribution with $B$,
$C^{\prime}$ has the same distribution with $C$ and $D^{\prime}$ has the same
distribution with $D$. Since MIC and TIC only evaluate the marginal
distribution of each variable separately, they can not distinguish $A$ from
$A^{\prime}$, $B$ from $B^{\prime}$, $C$ from $C^{\prime}$ and $D$ from
$D^{\prime}$. However, $(A,B,C,D)$ have totally different joint distribution
from $(A^{\prime},B^{\prime},C^{\prime},D^{\prime})$.

###  A.7 Metrics implement details

The superiorities of the proposed new metrics and a simple example has been
discussed in Section 4. More details about those new metrics will be discussed
in this section. For fully supervised learning or semi-supervised learning
method, the metrics calculation are straightforward since every latent
elements is controlled by their corresponding label information [5]. For
unsupervised methods and our reduced supervision method without using label,
we have to first determine the correspondence between each latent factor and
each label. We use MIC to choose which latent element represent the label
information. As we described in Section 4, MIC can be used to measure the
information relevance between a latent factor and a generative label. For each
generative factor label, we choose the latent element which achieve maximum
MIC value evaluated with that generative factor. After choosing the
correspondence between each latent factor with all generative factors label,
we can apply Pos/Neg metrics according to the true causal graph provided by
the datasets.

###  A.8 Reconstruction results

We include the image reconstruction results in this section. Shown in figs. A3
to A6, when changing the cause factors, the effect factors shown in
reconstructions are changed corresponding. On the contrary, when changing the
effect factors, the reconstructions can be counterfactual images and the cause
factors stay unchanged.

Figure A3: Traversal reconstruction of pendulum dataset. For each rows, we
only change one latent factor value and fix all other latent factors. By
changing cause factor (light position or angle), we observe corresponding
change in effect factors (shadow position and shadow length). Oppositely, by
changing effect factor (shadow location and shadow length), the
reconstructions can become counterfactual images and the cause factors (light
position and angle) stay unchanged. Figure A4: Traversal reconstruction of
flow dataset. For each rows, we only change one latent factor value and fix
all other latent factors. By changing cause factor (ball size or hole), we
observe corresponding change in effect factors (water height and flow).
Oppositely, by changing effect factor (water height or flow), the
reconstructions can become counterfactual images and the cause factors (ball
size and hole) stay unchanged. Figure A5: Traversal reconstruction of
CelebA(Beard) dataset. For each rows, we only change one latent factor value
and fix all other latent factors. By changing cause factor (age or gender), we
observe corresponding change in effect factors (bald and beard). Oppositely,
by changing effect factor (beard and bald), the reconstructions can become
counterfactual images and the cause factors stay unchanged. Figure A6:
Traversal reconstruction of pendulum CelebA(Smile) dataset. For each rows, we
only change one latent factor value and fix all other latent factors. By
changing cause factor (gender and smile), we observe corresponding change in
effect factors (eyes open). Oppositely, by changing effect factor (shadow eyes
open), the reconstructions can become counterfactual images and the cause
factors stay unchanged.