plain algproblem  Input: Question:

# Quadratic equations in the lamplighter group

Alexander Ushakov and Chloe Weiers  Department of Mathematical Sciences,
Stevens Institute of Technology, Hoboken NJ 07030
<EMAIL_ADDRESS>
###### Abstract.

In this paper we study complexity of solving quadratic equations in the
lamplighter group. We give a complete classification of cases (depending on
genus and other characteristics of a given equation) when the problem is
${\mathbf{NP}}$-complete or polynomial-time decidable. We notice that the
conjugacy problem can be solved in linear time. Finally, we prove that the
problem belongs to the class ${\mathbf{XP}}$.
Keywords. Diophantine problem, quadratic equations, spherical equations,
conjugacy problem, metabelian groups, lamplighter group, wreath product,
complexity, NP-completeness.

2010 Mathematics Subject Classification. 20F16, 20F10, 68W30.

##  1\. Introduction

Let $F=F(Z)$ denote the free group on countably many generators
$Z=\\{z_{i}\\}_{i=1}^{\infty}$. For a group $G$, an _equation over $G$ with
variables in $Z$_ is an equality of the form $W=1$, where $W\in F*G$. If
$W=z_{i_{1}}g_{1}\cdots z_{i_{k}}g_{k}$, with $z_{i_{j}}\in Z$ and $g_{j}\in
G$, then we refer to $\\{z_{i_{1}},\ldots,z_{i_{k}}\\}$ as the set of
_variables_ and to $\\{g_{1},\ldots,g_{k}\\}$ as the set of _constants_ (or
_coefficients_) of $W$. We occasionally write $W(z_{1},\ldots,z_{k})$ or
$W(z_{1},\ldots,z_{k};g_{1},\ldots,g_{k})$ to indicate that the variables in
$W$ are precisely $z_{1},\ldots,z_{k}$ and (in the latter case) the constants
are precisely $g_{1},\ldots,g_{k}$.

A _solution_ to an equation $W(z_{1},\ldots,z_{k})=1$ over $G$ is a
homomorphism

$\varphi\colon F*G\rightarrow G$

such that $\varphi|_{G}=1_{G}$ and $W\in\ker\varphi$. If $\varphi$ is a
solution of $W=1$ and $g_{i}=\varphi(z_{i})$, then we often say that
$g_{1},\ldots,g_{k}$ is a solution of $W=1$. We also write
$W(g_{1},\ldots,g_{k})$ or $W(\bar{g})$ to denote the image of
$W(z_{1},\ldots,z_{k})$ under the homomorphism $F*G\rightarrow G$ which maps
$z_{i}\mapsto g_{i}$ (and restricts to the identity on $G$). Note that while
some authors allow for solutions in some overgroup $H$ (with an embedding
$G\hookrightarrow H$), in this article we only consider solutions in $G$.

In this paper we assume that $G$ comes equipped with a fixed generating set
$X$ and elements of $G$ are given as products of elements of $X$ and their
inverses. This naturally defines the length (or size) of the equation $W=1$ as
the length of its left-hand side $W$.

######  Definition 1.1.

An equation $W=1$ is called _quadratic_ if each variable appears exactly twice
(as either $z_{i}$ or $z_{i}^{-1}$).

The _Diophantine problem_ in a group $G$ for a class of equations $C$ is an
algorithmic question to decide whether a given equation $W=1$ in $C$ has a
solution. In this paper we study the class of quadratic equations over the
standard lamplighter group $L_{2}$.

###  1.1. Classification of quadratic equations

We say that equations $W=1$ and $V=1$ are _equivalent_ if there is an
automorphism $\phi\in\operatorname{{Aut}}(F\ast G)$ such that $\phi$ is the
identity on $G$ and $\phi(W)=V$. It is a well known consequence of the
classification of compact surfaces that any quadratic equation over $G$ is
equivalent, via an automorphism $\phi$ computable in time $O(|W|^{2})$, to an
equation in exactly one of the following three _standard forms_ (see [6, 9]):

(1) $\displaystyle\prod_{j=1}^{k}z_{j}^{-1}c_{j}z_{j}$ $\displaystyle=1$
$\displaystyle k\geq 1,$ (2)
$\displaystyle\prod_{i=1}^{g}[x_{i},y_{i}]\prod_{j=1}^{k}z_{j}^{-1}c_{j}z_{j}$
$\displaystyle=1$ $\displaystyle g\geq 1,k\geq 0,$ (3)
$\displaystyle\prod_{i=1}^{g}x_{i}^{2}\prod_{j=1}^{k}z_{j}^{-1}c_{j}z_{j}$
$\displaystyle=1$ $\displaystyle g\geq 1,k\geq 0.$

The number $g$ is the _genus_ of the equation, and both $g$ and $k$ (the
number of constants) are invariants. The standard forms are called,
respectively, _spherical_ , _orientable of genus $g$_, and _non-orientable of
genus $g$_.

###  1.2. Previous results

The Diophantine problem for quadratic equations naturally generalizes
fundamental (Dehn) problems of group theory such as the word and conjugacy
problems. Furthermore, there is a deep relationship between quadratic
equations and compact surfaces, which makes quadratic equations an interesting
object of study.

Study of quadratic equations originated with Malcev, who in [20] considered
some particular quadratic equations over free groups, now often referred to as
_Malcev’s equations_. This line of research for free groups was continued:
solution sets were studied in [9], ${\mathbf{NP}}$-completeness was proved in
[7, 14]. Various classes of infinite groups were analyzed: hyperbolic groups
were studied in [10, 15], the first Grigorchuk group was studied in [17] and
[1], free metabelian groups were studied in [18, 19], metabelian
Baumslag–Solitar groups were studied in [21]. The Diophantine problem for
quadratic equations over the lamplighter group $L_{2}$ was recently shown to
be decidable by Kharlampovich, Lopez, and Miasnikov (see [13]).

###  1.3. History of the study of $L_{2}$

The group ${L_{2}}$ was first studied under the name of the lamplighter group
by Kaimanovich and Vershik [12], though it has been an object of study for
much longer as a simple example of a wreath product (see [4] for a compact
history). The standard lamplighter group $L_{2}$ has many different
realizations, including as a dynamical system, an infinite direct sum, and
notably as a self-similar group generated by a $2$-state automaton (see
Grigorchuk and Żuk [11]). The construction and mechanics of the lamplighter
group extend naturally beyond ${L_{2}}$ to the generalized lamplighter group
$L_{n}$; dead-end elements of generalized lamplighter groups were described by
Cleary and Taback in [5], and Bartholdi and Šunik showed that generalized
lamplighter groups are self-similar [2].

Complexity of solving some fundamental problems has also been a topic of study
in lamplighter groups. The conjugacy search problem was explored by Sale for
general wreath products in [22] and in lamplighter groups specifically in
[23]. Siehler explored the conjugacy problem and described conditions for
membership in the derived subgroup of $L_{n}$ in [24]. In this paper we
provide a different but equivalent description of the derived subgroup of
$L_{2}$, which is naturally more compact due to the simplicity of
${\mathbb{Z}}_{2}$.

###  1.4. The $3$-partition problem

For a multiset $S=\\{s_{1},\ldots,s_{3k}\\}$ of $3k$ integers, let

$T_{S}=\frac{1}{k}\sum_{i=1}^{3k}s_{i}.$

The $3$-partition problem (we occasionally use the abbreviation
$\operatorname{3PART}$) is the problem of deciding whether a given
$S=\\{s_{1},\ldots,s_{3k}\\}$ with $T_{S}/4<s_{i}<T_{S}/2$ can be partitioned
into $k$ triples, each of which sums to $T_{S}$. This problem is known to be
_strongly_ ${\mathbf{NP}}$-complete, which means that it remains
${\mathbf{NP}}$-complete even when the integers in $S$ are bounded above by a
polynomial in $m$. In other words, the problem remains
${\mathbf{NP}}$-complete even when the input is represented in unary.111A
thorough treatment of this problem may be found in [8].

The _partition problem_ is a related problem to decide whether a given
multiset $S$ of positive integers can be partitioned into two subsets $S_{1}$
and $S_{2}$ such that the sum of the numbers in $S_{1}$ equals the sum of the
numbers in $S_{2}$. The problem is ${\mathbf{NP}}$-complete if the numbers are
given in binary and polynomial time decidable if the numbers are given in
unary.

##  2\. Preliminaries: the lamplighter group

Define a set

${\mathbb{Z}_{2}^{\mathbb{Z}}}=\left\\{\,f\colon{\mathbb{Z}}\to{\mathbb{Z}}_{2}\;\middle|\;|\operatorname{{supp}}(f)|<\infty\,\right\\}$

and a binary operation $+$ on ${\mathbb{Z}_{2}^{\mathbb{Z}}}$ which for
$f,g\in{\mathbb{Z}_{2}^{\mathbb{Z}}}$ produces
$f+g\in{\mathbb{Z}_{2}^{\mathbb{Z}}}$ defined by

$(f+g)(x)=f(x)+g(x)\ \mbox{ for }\ x\in{\mathbb{Z}}.$

For $f\in{\mathbb{Z}_{2}^{\mathbb{Z}}}$ and $b\in{\mathbb{Z}}$, define
$f^{b}\in{\mathbb{Z}_{2}^{\mathbb{Z}}}$ by

$f^{b}(x)=f(x+b)\ \mbox{ for }\ x\in{\mathbb{Z}},$

which is a right ${\mathbb{Z}}$-action on ${\mathbb{Z}_{2}^{\mathbb{Z}}}$
because $f^{0}=f$ and
$f^{(b_{1}+b_{2})}(x)=f(x+b_{1}+b_{2})=(f^{b_{1}})^{b_{2}}(x)$. Hence we can
consider a semidirect product
${\mathbb{Z}}\ltimes{\mathbb{Z}_{2}^{\mathbb{Z}}}$ equipped with the operation

$(\delta_{1},f_{1})(\delta_{2},f_{2})=(\delta_{1}+\delta_{2},f_{1}^{\delta_{2}}+f_{2}).$

The group ${\mathbb{Z}}\ltimes{\mathbb{Z}_{2}^{\mathbb{Z}}}$ is called a
_restricted wreath product_ of ${\mathbb{Z}}_{2}$ and ${\mathbb{Z}}$ and is
denoted by ${\mathbb{Z}}_{2}\wr{\mathbb{Z}}$. The group
${\mathbb{Z}}_{2}\wr{\mathbb{Z}}$ is also known as the lamplighter group, as
it can be viewed as an infinite set of lamps (each lamp indexed by an element
of ${\mathbb{Z}}$), with each lamp either on or off, and a lamplighter
positioned at some lamp. Given some element $(\delta,f)\in{L_{2}}$,
$f\in{\mathbb{Z}_{2}^{\mathbb{Z}}}$ represents the configuration of
illuminated lamps and $\delta\in{\mathbb{Z}}$ represents the position of the
lamplighter. Similarly, we can define ${\mathbb{Z}}_{2}\wr{\mathbb{Z}}_{n}$ as
${\mathbb{Z}}_{n}\ltimes{\mathbb{Z}}_{2}^{{\mathbb{Z}}_{n}}$. Henceforth, we
denote ${\mathbb{Z}}_{2}\wr{\mathbb{Z}}$ as $L_{2}$, the generalized
lamplighter group ${\mathbb{Z}}_{n}\wr{\mathbb{Z}}$ as $L_{n}$, and
${\mathbb{Z}}_{2}\wr{\mathbb{Z}}_{n}$ by $L_{2}^{n}$.

###  2.1. Mechanics of ${L_{2}}$

There is a natural isomorphism between ${\mathbb{Z}_{2}^{\mathbb{Z}}}$ and the
ring ${\mathbb{Z}}_{2}[x^{\pm}]$ of _Laurent polynomials_ with coefficients in
${\mathbb{Z}}_{2}$ that maps $f\in{\mathbb{Z}_{2}^{\mathbb{Z}}}$ to
$\sum_{i=-\infty}^{\infty}f(i)x^{i}$. Hence, the group $L_{2}$ can be viewed
as ${\mathbb{Z}}\ltimes{\mathbb{Z}}_{2}[x^{\pm}]$ with the
${\mathbb{Z}}$-action on ${\mathbb{Z}}_{2}[x^{\pm}]$ defined by

$f^{\delta}=f\cdot x^{-\delta}.$

Similarly, we can view ${\mathbb{Z}}_{2}^{{\mathbb{Z}}_{n}}$ as the quotient
ring ${\mathbb{Z}}_{2}[x^{\pm}]/{\left\langle x^{n}-1\right\rangle}$ and
$L_{2}^{n}$ as
${\mathbb{Z}}_{n}\ltimes({\mathbb{Z}}_{2}[x^{\pm}]/{\left\langle
x^{n}-1\right\rangle})$. Throughout this section we use notation for
${\mathbb{Z}_{2}^{\mathbb{Z}}}$ and ${\mathbb{Z}}_{2}[x^{\pm}]$
interchangeably (respectively, ${\mathbb{Z}}_{2}^{{\mathbb{Z}}_{n}}$ and
${\mathbb{Z}}_{2}[x^{\pm}]/{\left\langle x^{n}-1\right\rangle}$), slightly
abusing the notation.

For $b\geq 0$ define a group homomorphism
$\lambda_{b}\colon{\mathbb{Z}}_{2}[x^{\pm}]\to{\mathbb{Z}}_{2}[x^{\pm}]$ by

$\lambda_{b}(f)=(x^{b}-1)\cdot f$

and a ring homomorphism
$\pi_{b}\colon{\mathbb{Z}}_{2}[x^{\pm}]\to{\mathbb{Z}}_{2}[x^{\pm}]/{\left\langle
x^{b}-1\right\rangle}$ by

$[\pi_{b}(f)](x)=\sum_{y\equiv_{b}x}f(y)\mbox{ for }x\in{\mathbb{Z}}_{b}.$

######  Proposition 2.1.

${\mathbb{Z}}_{2}[x^{\pm}]\stackrel{{\scriptstyle\lambda_{b}}}{{\longrightarrow}}{\mathbb{Z}}_{2}[x^{\pm}]\stackrel{{\scriptstyle\pi_{b}}}{{\longrightarrow}}{\mathbb{Z}}_{2}[x^{\pm}]/{\left\langle
x^{b}-1\right\rangle}$ is an exact sequence, i.e.,
$\operatorname{{im}}(\lambda_{b})=\ker(\pi_{b})$.

###### Proof.

The inclusion $\operatorname{{im}}(\lambda_{b})\subseteq\ker(\pi_{b})$ is
obvious, because for every $f\in{\mathbb{Z}_{2}^{\mathbb{Z}}}$,

$\pi_{b}{\left(\lambda_{b}(f)\right)}=\pi_{b}{\left((x^{b}-1)f\right)}=\pi_{b}(x^{b}-1)\pi_{b}(f)=0\cdot\pi_{b}(f)=0.$

Conversely, if $g\in\ker(\pi_{b})$, then $g\in{\left\langle
x^{b}-1\right\rangle}$ and, hence, $g$ is a multiple of $x^{b}-1$. ∎

More generally, for ${\overline{b}}=(b_{1},\ldots,b_{k})\in{\mathbb{Z}}^{k}$,
define a linear function
$\lambda_{{\overline{b}}}\colon({\mathbb{Z}_{2}^{\mathbb{Z}}})^{k}\to{\mathbb{Z}_{2}^{\mathbb{Z}}}$
by

$(f_{1},\ldots,f_{k})\ \
\stackrel{{\scriptstyle\lambda_{{\overline{b}}}}}{{\mapsto}}\ \
(1-x^{b_{1}})\cdot f_{1}+\cdots+(1-x^{b_{k}})\cdot f_{k},$

$b=\gcd(b_{1},\ldots,b_{k})$, and a projection homomorphism
$\pi_{\overline{b}}=\pi_{b}\colon{\mathbb{Z}_{2}^{\mathbb{Z}}}\to{\mathbb{Z}}_{2}^{{\mathbb{Z}}_{b}}$.
Throughout the paper we use the conventions that $\gcd(0,\dots,0)=0$,
${\mathbb{Z}}_{n}$ is the ring of congruence classes modulo $n$ if $n>0$, and
${\mathbb{Z}}_{0}={\mathbb{Z}}$.

######  Lemma 2.2.

If $b_{1},b_{2}>0$ and $b=\gcd(b_{1},b_{2})$, then
$\gcd(x^{b_{1}}-1,x^{b_{2}}-1)=x^{b}-1$.

###### Proof.

The statement follows from the Euclidean lemma. Indeed, if $b_{2}=b_{1}+r$,
then

$(x^{b_{2}}-1)-x^{r}(x^{b_{1}}-1)=x^{r}-1,$

and, hence, $\gcd(x^{b_{1}}-1,x^{b_{2}}-1)=\gcd(x^{b_{1}}-1,x^{r}-1)$. That
allows to define a Euclidean-like process that terminates with $x^{b}-1$. ∎

######  Corollary 2.3.

$\operatorname{{im}}(\lambda_{{\overline{b}}})=\ker(\pi_{{\overline{b}}})$.

###### Proof.

It follows from Lemma 2.2 that $\operatorname{{im}}(\lambda_{{\overline{b}}})$
is a principal ideal generated by $x^{b}-1$ which is the same as
$\ker(\pi_{{\overline{b}}})=\ker(\pi_{b})$. ∎

######  Proposition 2.4.

Let $W=\sum_{i=1}^{k}(1-x^{b_{i}})\cdot f_{i}+W^{\prime}(f_{k+1},\dots)$,
where $b_{i}\in{\mathbb{Z}}\setminus\\{0\\}$ are constants,
$f_{i}\in{\mathbb{Z}_{2}^{\mathbb{Z}}}$ are unknown, and $W^{\prime}$ does not
involve $f_{1},\dots,f_{k}$. Then

$W=0\mbox{ has a solution in }{\mathbb{Z}_{2}^{\mathbb{Z}}}\ \
\Leftrightarrow\ \ W^{\prime}=0\mbox{ has a solution in
}{\mathbb{Z}}_{2}^{{\mathbb{Z}}_{b}},$

where $b=\gcd(b_{1},\dots,b_{k})$.

###### Proof.

“$\Rightarrow$” Suppose that $W=0$ has a solution in
${\mathbb{Z}_{2}^{\mathbb{Z}}}$. Applying a homomorphism $\pi_{\overline{b}}$
we get the equation $\pi_{{\overline{b}}}(W)=0$ in which the term
$\sum_{i=1}^{k}(1-x^{b_{i}})\cdot f_{i}$ vanishes and that has a solution in
${\mathbb{Z}}_{2}^{{\mathbb{Z}}_{b}}$.

“$\Leftarrow$” Suppose that $W^{\prime}=0$ has a solution
$f_{k+1}^{\prime},f_{k+2}^{\prime},\ldots\in{\mathbb{Z}}_{2}^{{\mathbb{Z}}_{b}}$.
Choose any functions
$f_{k+1}^{\ast},f_{k+2}^{\ast},\ldots\in{\mathbb{Z}_{2}^{\mathbb{Z}}}$
satisfying $f_{i}^{\prime}=\pi_{\overline{b}}(f_{i}^{\ast})$. Since
$\pi_{\overline{b}}$ is a homomorphism,

$\pi_{\overline{b}}(W^{\prime}(f_{k+1}^{\ast},f_{k+2}^{\ast},\dots))=W^{\prime}(f_{k+1}^{\prime},f_{k+2}^{\prime},\dots))=0$

and, hence,
$W^{\prime}(f_{k+1}^{\ast},f_{k+2}^{\ast},\dots)\in\ker(\pi_{\overline{b}})\stackrel{{\scriptstyle\ref{cor:sequencemulti}}}{{=}}\operatorname{{im}}(\lambda_{\overline{b}})$.
Therefore, there exist
$f_{1}^{\ast},\dots,f_{k}^{\ast}\in{\mathbb{Z}_{2}^{\mathbb{Z}}}$ satisfying
$\sum_{i=1}^{k}(1-x^{b_{i}})\cdot
f_{i}^{\ast}+W^{\prime}(f_{k+1}^{\ast},f_{k+2}^{\ast},\dots)=0$. ∎

###  2.2. Several useful facts about $L_{2}$

Let $a=(0,\mathbf{1}_{0})$, where
${\mathbf{1}}_{0}\in{\mathbb{Z}}_{2}^{\mathbb{Z}}$ is defined by

${\mathbf{1}}_{0}(x)=\begin{cases}1&\mbox{ if }x=0\\\ 0&\mbox{ if }x\neq 0\\\
\end{cases}$

and $t=(1,0)$, where the $0$ in the second component is the function identical
to $0$. It is easy to see that $L_{2}$ is generated by $a$ and $t$, i.e.,
every element of $L_{2}$ can be defined as a word in the alphabet $\\{a,t\\}$.
It is a well-known fact that $L_{2}$ is not finitely presented, see [3].

Let $\sigma_{a}\colon L_{2}\to{\mathbb{Z}}_{2}$ and $\sigma_{t}\colon
L_{2}\to{\mathbb{Z}}$ be “projection homomorphisms” defined by

$\sigma_{a}(g)=\sum_{i=-\infty}^{\infty}f(i)\ \ \mbox{ and }\ \
\sigma_{t}(g)=\delta$

if $g=(\delta,f)$. Clearly, $\sigma_{a}$ and $\sigma_{t}$ are computable in
linear time for $w=w(a,t)\in L_{2}$.

Finally, let us mention several useful formulae used throughout the paper.

$\displaystyle(\delta,f)^{-1}$
$\displaystyle=(-\delta,-f^{-\delta})=(-\delta,-x^{\delta}f).$
$\displaystyle(\delta,f)^{2}$
$\displaystyle=(2\delta,f^{\delta}+f)=(2\delta,(x^{-\delta}+1)f).$
$\displaystyle(\delta,f)^{-1}(\delta_{1},f_{1})(\delta,f)$
$\displaystyle=(-\delta,-f^{-\delta})(\delta_{1},f_{1})(\delta,f)=(\delta_{1},(1-x^{-\delta_{1}})f+x^{-\delta}f_{1}).$

##  3\. Spherical equations

In this section we prove that the Diophantine problem for spherical equations
defined by (1) over ${L_{2}}$ is ${\mathbf{NP}}$-complete and prove that the
problem for conjugacy equations can be solved in linear time.

######  Proposition 3.1.

A spherical equation (1) with constants $c_{i}=(\delta_{c_{i}},f_{c_{i}})$ has
a solution if and only if the following two conditions are satisfied:

  * (Sp1)

$\sum_{i=1}^{k}\delta_{c_{i}}=0$,

  * (Sp2)

$\sum_{i=1}^{k}f_{c_{i}}^{\delta_{i}}=0$ in
${\mathbb{Z}}_{2}^{{\mathbb{Z}}_{\delta}}$ for some
$\delta_{1},\dots,\delta_{k}\in{\mathbb{Z}}_{\delta}$,

where $\delta=\gcd(\delta_{c_{1}},\ldots,\delta_{c_{m}})$.

###### Proof.

Let $z_{i}=(\delta_{z_{i}},f_{z_{i}})$. Direct computation shows that in
notation of ${\mathbb{Z}}\ltimes{\mathbb{Z}}_{2}^{\mathbb{Z}}$ the equation
(1) has a solution if and only if

${\left(\sum_{i=1}^{k}\delta_{c_{i}},\sum_{i=1}^{k}x^{-\Delta_{i}}\left[{\left(1-x^{-\delta_{c_{i}}}\right)}f_{z_{i}}+x^{-\delta_{z_{i}}}f_{c_{i}}\right]\right)}=(0,0)$

where $\Delta_{i}=\delta_{c_{i+1}}+\dots+\delta_{c_{k}}$ for $i=0,\dots,k$, is
satisfied, which further translates to the conditions
$\sum_{i=1}^{k}\delta_{c_{i}}=0$ (which establishes (Sp1)) and

$\sum_{i=1}^{k}x^{-\Delta_{i}}\left[{\left(1-x^{-\delta_{c_{i}}}\right)}f_{z_{i}}+x^{-\delta_{z_{i}}}f_{c_{i}}\right]=0.$

By Proposition 2.4, the latter equation is satisfied if and only if

$\sum_{i=1}^{k}x^{-\Delta_{i}-\delta_{z_{i}}}f_{c_{i}}=0\ \mbox{ in }\
{\mathbb{Z}}_{2}^{{\mathbb{Z}}_{\delta}}$

is satisfied. Replacing $\Delta_{i}+\delta_{z_{i}}$ with $\delta_{i}$ we get
the condition (Sp2). ∎

###  3.1. Complexity lower bound

Let $S=\\{s_{1},\ldots,s_{3k}\\}$ be an instance of $\operatorname{3PART}$ and
$T=\frac{1}{k}\sum s_{i}$ be the anticipated sum for subsets, where
$T/4<s_{i}<T/2$ for each $i$. For $y\in{\mathbb{N}}$ define elements

$c_{y}=\prod_{i=0}^{y-1}t^{i}at^{-i},\ \ \ \
c=\prod_{i=0}^{k-1}t^{(T+1)i}c_{T}t^{-(T+1)i}.$

$0$$1$$\cdots$$y-1$$y$$-1$$y$ lamps

Figure 1. The “lamp-configuration” $f$ for the element $c_{y}=(0,f)$.

$-1$$0$$1$$T$ lamps$\cdots$$T-1$$T$$T+1$$T+2$$T$
lamps$\cdots$$2T$$2T+1$$\cdots$$(T+1)(k-1)-1$$(T+1)(k-1)$$(T+1)(k-1)+1$$\cdots$$T$
lamps$(T+1)(k-1)+(T-1)$$(T+1)(k-1)+T$

Figure 2.  The “lamp-configuration” $f$ for the element $c=(0,f)$ consists of
$k$ clusters of $T$ lit lamps, each cluster separated by a single unlit lamp.

######  Proposition 3.2.

$S=\\{s_{1},\ldots,s_{3k}\\}$ is a positive instance of $\operatorname{3PART}$
if and only if

(4) $\prod_{i=1}^{3k}z_{i}^{-1}c_{s_{i}}z_{i}=c$

has a solution.

###### Proof.

“$\Rightarrow$” If $S$ is a positive instance of $\operatorname{3PART}$, then,
without loss of generality, we may assume that $\sum_{i=1}^{3}s_{3j+i}=T$ for
$j=0,1,\ldots,k-1$. Let

$T_{i}=\begin{cases}0&i=0\\\ (T+1)(i-1)&1\leq i\leq 3k.\end{cases}$

Then clearly $z_{i}=t^{\Delta_{i}}$ for $i=1,\ldots,3k$ is a solution to (4),
where $\Delta_{i}$’s are defined as:

$\displaystyle\Delta_{1}$ $\displaystyle=0$ $\displaystyle\Delta_{2}$
$\displaystyle=-s_{1}$ $\displaystyle\Delta_{3}$ $\displaystyle=-s_{1}-s_{2}$
$\displaystyle\Delta_{4}$ $\displaystyle=-T_{1}$ $\displaystyle\Delta_{5}$
$\displaystyle=-T_{1}-s_{4}$ $\displaystyle\Delta_{6}$
$\displaystyle=-T_{1}-s_{4}-s_{5}$ $\displaystyle\Delta_{7}$
$\displaystyle=-T_{2}$ $\displaystyle\Delta_{8}$ $\displaystyle=-T_{2}-s_{7}$
$\displaystyle\Delta_{9}$ $\displaystyle=-T_{2}-s_{7}-s_{8}$
$\displaystyle\cdots$ $\displaystyle\cdots$ $\displaystyle\cdots$

“$\Leftarrow$” Conversely, assume there is an assignment of $z_{i}$’s
satisfying (4). For each $c_{s_{i}}$, $\operatorname{{supp}}(c_{s_{i}})$ is a
sequence of $s_{i}$ adjacent lamps $0,1,\ldots,s_{i}-1$ on ${\mathbb{Z}}$. The
solution $z_{i}$ shifts the $3k$ sequences of indexed $a$–copies into $k$
groupings of $T$ consecutive copies of $a$. Clearly, then,
$z_{1},\ldots,z_{3k}$ produces a non-overlapping tiling of a subset of
${\mathbb{Z}}$ into $k$ partitions, each of which is the union of three
shifted sets of $c_{s_{i}}$’s. In other words, a solution matches
$\operatorname{{supp}}(c)$ with shifted clusters of
$\operatorname{{supp}}(c_{s_{i}})$. It is obvious, then, that for
$x_{i}=s_{x_{i}}$,

$\sum_{i=1}^{3}c_{x_{3j+i}}=T\ \mbox{ for }\ j=0,1,\ldots k-1.$

Thus $S=\left\\{s_{1},\ldots,s_{3k}\right\\}$ is a positive instance of
$\operatorname{3PART}$. ∎

######  Corollary 3.3.

The Diophantine problem for spherical quadratic equations over ${L_{2}}$ is
${\mathbf{NP}}$-hard.

###### Proof.

The reduction discussed in Proposition 3.2 is a polynomial-time Karp reduction
from $\operatorname{3PART}$ to the Diophantine problem for spherical
equations. ∎

###  3.2. Complexity upper bound

Now we prove that the Diophantine problem for spherical equations (1) over
$L_{2}$ belongs to ${\mathbf{NP}}$. For a nontrivial function
$f\colon{\mathbb{Z}}\to{\mathbb{Z}}_{2}$ define

$\operatorname{{diam}}(f)=\max\left\\{\,x-y\;\middle|\;x,y\in\operatorname{{supp}}(f)\,\right\\},$

and note that $\operatorname{{diam}}(f)$ is invariant under a $\delta$-shift,
i.e.,
$\operatorname{{diam}}(f^{\delta})=\operatorname{{diam}}{\left(f\right)}$ for
every $\delta\in{\mathbb{Z}}$. The next lemma states that the diameter of $f$
cannot exceed the length of a shortest word $w$ describing that function.

######  Lemma 3.4.

For any word $w=w(a,t)$ in generators of $L_{2}$ defining the element
$(\delta,f)$,

$|\delta|\leq|w|\ \mbox{ and }\
\operatorname{{diam}}{\left(f\right)}\leq\left|w\right|.$

Furthermore, $\operatorname{{diam}}{\left(f\right)}\leq\left|w\right|/2$ for
any $w=w(a,t)$ defining $(0,f)$.

######  Theorem 3.5.

The Diophantine problem for spherical equations over ${L_{2}}$ belongs to
${\mathbf{NP}}$.

###### Proof.

Consider a spherical equation $W=1$ of type (1) that has a solution. By
Proposition 3.1, it has a solution if and only if the conditions (Sp1) and
(Sp2) hold. The condition (Sp1) can be verified in linear time. The condition
(Sp2) is an equation for $\delta_{1},\dots,\delta_{k}\in{\mathbb{Z}}$. We
claim that if (Sp2) has a solution, then it has a bounded solution satisfying

$-|W|\leq\min\delta_{i}\leq\max\delta_{i}\leq|W|,$

which gives an efficiently verifiable certificate for (1).

If $\delta\geq 1$, then

(5) $0\leq\delta_{i}<\delta\leq|W|$

and the claim holds. Therefore, we may assume that $\delta=0$. Fix
$\delta_{1},\ldots,\delta_{k}$ satisfying (Sp2). Let $I=\\{1,\ldots,k\\}$ be
the set of indices. Define an equivalence relation $R$ as the transitive
closure of the following binary relation on $I$:

$J=\left\\{\,(i,j)\in I\times
I\;\middle|\;\operatorname{{supp}}(f_{c_{i}}^{\delta_{i}})\cap\operatorname{{supp}}(f_{c_{j}}^{\delta_{j}})\neq\varnothing\,\right\\}.$

A _cluster_ for the sequence of functions $f_{c_{1}},\ldots,f_{c_{k}}$ is an
equivalence class for the relation $R$. We can partition $I$ into a finite
union of some $n$ clusters $C_{i}$, i.e. $I=C_{1}\sqcup\cdots\sqcup C_{n}$.
Note that $\sum_{i\in C}f_{c_{i}}^{\delta_{i}}=0$ for every cluster $C$.
Hence, shifting a cluster independently of other clusters does not change the
sum of its shifted component functions. In other words,

$\sum_{i\notin C}f_{c_{i}}^{\delta_{i}}+\sum_{i\in
C}f_{c_{i}}^{\delta_{i}+\Delta}=0,$

for any cluster $C$ and any $\Delta\in{\mathbb{Z}}$. Define the support of a
cluster $C$ as

$\operatorname{{supp}}(C)=\bigcup_{i\in
C}\operatorname{{supp}}{\left(f_{c_{i}}^{\delta_{i}}\right)}$

(note that $\operatorname{{supp}}(C)\subseteq{\mathbb{Z}}$ because $\delta=0$)
and its diameter as

$\operatorname{{diam}}(C)=\max\left\\{\,x-y\;\middle|\;x,y\in\operatorname{{supp}}(C)\,\right\\}.$

It follows from the definition of a cluster that the diameter of a cluster $C$
cannot exceed the sum of the diameters of its component functions, so

$\operatorname{{diam}}(C)\leq\sum_{i\in
C}\operatorname{{diam}}{\left(f_{c_{i}}^{\delta_{i}}\right)}=\sum_{i\in
C}\operatorname{{diam}}{\left(f_{c_{i}}\right)}\stackrel{{\scriptstyle\ref{le:inv2}}}{{\leq}}\sum_{i\in
C}\left|c_{i}\right|/2\leq|W|/2.$

Thus, the diameter of a single cluster is bounded by the lengths of the words
describing its component functions.

For each cluster $C_{j}$ choose a “midpoint” for its support

$p_{j}=\left\lfloor\tfrac{1}{2}{\left(\min\left\\{\,x\;\middle|\;x\in\operatorname{{supp}}(C_{j})\,\right\\}+\max\left\\{\,x\;\middle|\;x\in\operatorname{{supp}}(C_{j})\,\right\\}\right)}\right\rfloor$

and for $i=1,\dots,k$ define

$\delta_{i}^{\prime}=\delta_{i}-p_{j}\ \mbox{ if }\ i\in C_{j}.$

Since $\delta_{i}$ from the same cluster are shifted the same way, we have
that $\delta_{1}^{\prime},\dots,\delta_{k}^{\prime}$ satisfies (Sp2).
Furthermore, this transformation “centers” cluster supports and, in
particular, for every $i\in C_{j}$ we have that

(6) $\operatorname{{supp}}\big{(}f_{c_{i}}^{\delta_{i}^{\prime}}\big{)}\
\subseteq\ \operatorname{{supp}}(C_{j})\ \subseteq\
\left[-|W|/4,|W|/4\right].$

Therefore, $|\delta_{i}^{\prime}|$ is bounded by $|W|$ as claimed. ∎

######  Theorem 3.6.

The Diophantine problem for spherical equations over ${L_{2}}$ is
${\mathbf{NP}}$-complete.

######  Corollary 3.7.

There is an algorithm that, for a given spherical equation (1), decides if it
has a solution or not in time $O(|W|^{k})$.

###### Proof.

By Proposition 3.1, (1) has a solution if and only if (Sp1) and (Sp2) are
satisfied. (Sp1) can be checked in linear time. Below, we discuss (Sp2) for
two cases $\delta=0$ and $\delta\neq 0$.

Suppose that $\delta=0$. In the proof of Theorem 3.5 we showed that if (Sp2)
is satisfied by $\delta_{1},\dots,\delta_{k}\in{\mathbb{Z}}$, then it is
satisfied by $\delta_{1}^{\prime},\dots,\delta_{k}^{\prime}\in{\mathbb{Z}}$
satisfying (6), i.e.,

$\operatorname{{supp}}\big{(}f_{c_{i}}^{\delta_{i}^{\prime}}\big{)}\subseteq\left[-|W|/4,|W|/4\right],$

which gives at most $|W|/2$ distinct values for $\delta_{i}^{\prime}$. That
gives $O(|W|^{k-1})$ potential combinations for
$\delta_{1}^{\prime},\dots,\delta_{k-1}^{\prime}$. The value of
$\delta_{k}^{\prime}$ is uniquely defined by
$\delta_{1}^{\prime},\dots,\delta_{k-1}^{\prime}$ and does not need to be
enumerated. Each combination can be checked in linear time. Hence the claimed
bound.

If $\delta\neq 0$, then (as in Theorem 3.5) an equation has a solution
$0\leq\delta\leq|W|$ and each $\delta_{i}$ can take at most $|W|$ distinct
values. Clearly, we may assume that $\delta_{1}=0$. Hence, the same complexity
bound holds. ∎

###  3.3. The conjugacy problem over $L_{2}$

In [23], Sale showed that the conjugacy search problem can be solved in
quadratic time over $L_{n}$. Below we show that it can be solved in linear
time over $L_{2}$. (In fact, the same approach works for $L_{n}$.)

######  Proposition 3.8.

The conjugacy problem over $L_{2}$ is decidable in linear time.

###### Proof.

First, observe that a spherical equation with two conjugates

$z_{1}^{-1}c_{1}z_{1}z_{2}^{-1}c_{2}z_{2}=1\ \ \Rightarrow\ \
z_{1}^{-1}c_{1}z_{1}=z_{2}^{-1}c_{2}^{-1}z_{2}$

is an instance of the conjugacy problem with elements $c_{1}$ and
$c_{2}^{-1}$. Let $c_{1}=(\delta_{c_{1}},f_{c_{1}})$ and
$c_{2}^{-1}=(\delta_{c_{2}},f_{c_{2}})$ for notational convenience. For such
an equation to have a solution, clearly $\delta_{c_{1}}=\delta_{c_{2}}$ must
be satisfied. The problem thus splits into two cases, depending on whether
$\delta$’s are trivial. In both cases, we exclude the trivial support case,
where one or both functions satisfy
$\operatorname{{supp}}(f_{c_{i}})=\varnothing$.

The first case is where $\delta_{c_{1}}=\delta_{c_{2}}=0$. By Proposition 3.1,
(Sp1) and (Sp2) must be satisfied. The condition (Sp1) is satisfied by
assumption. In this case, $\gcd(\delta_{c_{1}},\delta_{c_{2}})=0$, so (Sp2)
simplifies to deciding whether there exists an element $\Delta\in{\mathbb{Z}}$
such that $f_{c_{1}}=f_{c_{2}}^{\Delta}$ in ${\mathbb{Z}_{2}^{\mathbb{Z}}}$.
Define $b_{1},d_{1},b_{2},d_{2}\in{\mathbb{Z}}$ as

$b_{i}=\displaystyle{\min_{x\in\operatorname{{supp}}(f_{c_{i}})}x},\ \ \
d_{i}=\displaystyle{\max_{x\in\operatorname{{supp}}(f_{c_{i}})}x}.$

Without loss of generality, assume that $b_{1}\leq b_{2}$. Let
$\Delta=b_{2}-b_{1}$. It can be determined whether
$f_{c_{1}}=f_{c_{2}}^{\Delta}$ by scanning pairs of elements starting from
$b_{1}$ to $\max(d_{1},d_{2})$. Clearly, this can be done in linear time.

$f_{c_{2}}$$f_{c_{1}}$$b_{1}$$b_{2}$$d_{1}$$d_{2}$$\Delta$ Figure 3. An
example of an instance where $f_{c_{1}}=f_{c_{2}}^{\Delta}$.

The second case is where $\delta_{c_{1}}=\delta_{c_{2}}\neq 0$. Let
$\delta=\delta_{c_{1}}$. Here the equation simplifies to
${\left(1-x^{-\delta}\right)}{\left(f_{z_{1}}-f_{z_{2}}\right)}=f_{c_{2}}^{\delta_{z_{2}}}-f_{c_{1}}^{\delta_{z_{1}}}$,
which has a solution if and only if there exists $\Delta\in{\mathbb{Z}}$ such
that $\pi_{\delta}(f_{c_{1}})=\pi_{\delta}(f_{c_{2}})^{\Delta}$ in
${\mathbb{Z}}_{2}^{{\mathbb{Z}}_{\delta}}$.

$f_{c_{2}}$$f_{c_{1}}$$0$$\pi_{\delta}(f_{c_{1}})$$\pi_{\delta}(f_{c_{2}})$$0$$\delta=5$
Figure 4. An example of an instance where
$\pi_{\delta}(f_{c_{1}})=\pi_{\delta}(f_{c_{2}})^{\Delta}$. Here, $\delta=5$
and $\Delta=3$.

In other words, the equation has a solution if and only if the images of
$f_{c_{1}}$ and $f_{c_{2}}$ are cyclic permutations of each other in the
quotient space defined by the $\delta$-component of the functions. Let
$\Sigma=\\{0,1\\}$. Denote by $s_{1},s_{2}\in\Sigma^{\delta}$ the bitstring
representations of the words $w_{1}$ and $w_{2}$ representing
$\pi_{\delta}(f_{c_{1}})$ and $\pi_{\delta}(f_{c_{2}})$ respectively. We know
that $s_{1}$ and $s_{2}$ are cyclic permutations of each other if and only if
$s_{1}$ appears somewhere in $s_{2}^{2}$. This can be checked in linear time
using the pattern-matching algorithm from [16]. ∎

######  Lemma 3.9.

For any $g=(\delta,f)$ where $\delta>0$ there is a conjugator $c$ of linear
length such that $c^{-1}gc=(\delta,f^{\prime})$ with
$\operatorname{{supp}}(f^{\prime})\subseteq\\{0,\dots,\delta-1\\}$.

###### Proof.

Define $c$ as a product $c=p_{0}\cdots p_{\delta-1}n_{0}\cdots n_{\delta-1}$,
where $p_{i}$’s collapse certain positive support points to the left and
$n_{i}$’s collapse certain negative support points to the right. For
$i=0,\ldots,\delta-1$, define
$S_{i}=\left\\{\,x\in\operatorname{{supp}}(f)\;\middle|\;x\equiv_{\delta}i\,\right\\}$,
and find

$b_{i}^{+}=\max\left\\{\,x\in S_{i}\;\middle|\;x\geq\delta\,\right\\},\ \ \ \
b_{i}^{-}=\min\left\\{\,x\in S_{i}\;\middle|\;x<0\,\right\\}.$

If $b_{i}^{+}$ is undefined, then set $p_{i}=1$, and if $b_{i}^{-}$ is
undefined, set $n_{i}=1$. Otherwise, $b_{i}^{+}=i+\delta m$ for some $m\geq 1$
and $b_{i}^{-}=i+\delta n$ for some $n<0$. For $j=1,\ldots,m$ and
$k=1,\ldots,|n|$, define accumulation functions $g_{i,j}^{+}$ and
$g_{i,k}^{-}$ as

$g_{i,j}^{+}=\sum_{\ell=j}^{m}f(i+\delta\ell),\ \ \ \
g_{i,k}^{-}=\sum_{\ell=n}^{k}f(i+\delta\ell)$

and elements $p_{i}$ and $n_{i}$ as

$\displaystyle p_{i}$
$\displaystyle=\prod_{r=1}^{m}t^{i+\delta(m-r)}g^{+}_{i,r-1}t^{-(i+\delta(m-r))}$
$\displaystyle n_{i}$
$\displaystyle=\prod_{r=1}^{|n|}t^{-(i-\delta(|n|-r))}g^{-}_{i,r-1}t^{i-\delta(|n|-r)}.$

Observe that, within the conjugator $c$ defined above, subwords of the form
$t^{i}a^{\varepsilon}t^{-i}$, where $\varepsilon\in\\{0,1\\}$, commute. This
allows to reduce $p_{0}\cdots p_{\delta-1}$ and $n_{0}\cdots n_{\delta-1}$
through cancellation such that $c$ is of the form

$c=t^{\alpha}at^{-b_{1}}at^{-b_{2}}\cdots t^{-b_{q}}at^{\beta},$

where
$\alpha=\max\left\\{\,x\;\middle|\;x\in\operatorname{{supp}}(f)\,\right\\}$,
$\beta=\min\left\\{\,x\;\middle|\;x\in\operatorname{{supp}}(f)\,\right\\}$,
and $b_{i}>0$. Then

$|c|\leq 4|w|,$

where $|w|$ is the length of the word describing $g$. ∎

######  Corollary 3.10.

The conjugacy search problem over $L_{2}$ can be solved in linear time.

###### Proof.

This follows from Lemma 3.9. First, find $\Delta$ satisfying
$\pi_{\delta}(f_{c_{1}})=\pi_{\delta}(f_{c_{2}})^{\Delta}$. Then apply 3.9 to
$(\delta,f_{c_{1}})$ and $(\delta,f_{c_{2}}^{\Delta})$. ∎

##  4\. Orientable equations

Here we study quadratic equations defined by (2) over ${L_{2}}$. Recall that
the _derived subgroup_ $[G,G]$ of a group $G$ is defined as

$[G,G]={\left\langle[x,y]\mid x,y\in G\right\rangle}.$

The _commutator width_ of $G$ is the the least
$k\in{\mathbb{N}}\cup\\{\infty\\}$ such that every $g\in[G,G]$ can be
expressed as a product of at most $k$ commutators.

######  Lemma 4.1.

The following hold:

  * (a)

$[{L_{2}},{L_{2}}]=\ker(\sigma_{a})\cap\ker(\sigma_{t})$.

  * (b)

The commutator width of ${L_{2}}$ is one.

###### Proof.

(a) It is easy to check that every product of commutators belongs to
$\ker(\sigma_{a})\cap\ker(\sigma_{t})$.

(b) If $(\delta,f)\in\ker(\sigma_{a})\cap\ker(\sigma_{t})$, then $\delta=0$
and $\sum_{i=-\infty}^{\infty}f(i)=0$. Define
$g\colon{\mathbb{Z}}\to{\mathbb{Z}}_{2}$ by

$g(j)=\sum_{i\leq j}f(i)\ \mbox{ for }\ j\in{\mathbb{Z}}.$

Notice that $g$ has finite support because $\sum_{i=-\infty}^{\infty}f(i)=0$
and satisfies $g\cdot(1-x)=f$ since

$[g-g\cdot x](j)=g(j)-[g\cdot x](j)=g(j)-g(j-1)=f(j).$

Therefore, $(0,f)=(0,g-g\cdot x)=(0,g)(1,0)(0,g)^{-1}(1,0)^{-1}$ is a
commutator. ∎

######  Proposition 4.2.

The Diophantine problem for orientable quadratic equations over ${L_{2}}$ is
decidable in polynomial time.

###### Proof.

By Lemma 4.1(b), equation (2) has a solution if and only if
$\prod_{j=1}^{k}z_{j}^{-1}c_{j}z_{j}\in[{L_{2}},{L_{2}}]$ for some
$z_{1},\dots,z_{k}$. By Lemma 4.1(a), that holds if and only if
$\sigma_{a}(c_{1}\cdots c_{k})=0$ and $\sigma_{t}(c_{1}\cdots c_{k})=0$. The
latter conditions can be checked in linear time. ∎

##  5\. Non-orientable equations

In this section we analyze non-orientable equations in the lamplighter group
$L_{2}$. We say that $g\in G$ is a _square_ if $g=h^{2}$ for some $h\in G$.

######  Lemma 5.1.

$c=(\delta,f)\in G$ is a square if and only if

  * (a)

$c=1$, or

  * (b)

$\delta=2b\neq 0$ is even and $\pi_{b}(f)=0$.

###### Proof.

“$\Leftarrow$” $c=1=1^{2}$ is a square. If $\delta=2b\neq 0$ is even and
$\pi_{b}(f)=0$, then we have

$\displaystyle\pi_{b}(f)=0$ $\displaystyle\ \Rightarrow\
f\in\ker(\pi_{b})=\operatorname{{im}}(\lambda_{b})$ (Proposition 2.1)
$\displaystyle\ \Rightarrow\ f=(x^{b}-1)\cdot g$ (for some
$g\in{\mathbb{Z}_{2}^{\mathbb{Z}}}$) $\displaystyle\ \Rightarrow\
f=(x^{b}+1)\cdot g=(1+x^{-b})\cdot(x^{b}\cdot g)$ (characteristic $2$).

Hence, $c=(2b,f)=(b,x^{b}\cdot g)^{2}$ is a square.

“$\Rightarrow$” Suppose that $(\delta,f)=(b,g)^{2}$. Then $\delta=2b$ and
$f=g+g^{b}$. If $b=0$, then $\delta=0$, $f=g+g=0$, and (a) is satisfied. If
$b\neq 0$, then $\delta=2b\neq 0$ is even and

$g=f+f^{b}=(1+x^{-b})\cdot f=(1-x^{-b})\cdot f=(x^{b}-1)\cdot(x^{-b}f)$

that belongs to $\ker(\pi_{b})$ and, hence, (b) holds. ∎

Let $V$ be the verbal subgroup of $L_{2}$ generated by all squares, i.e.,
$V={\left\langle g^{2}\mid g\in L_{2}\right\rangle}$. It is a common knowledge
that $V$ is a normal subgroup of $L_{2}$ containing the derived subgroup
$[L_{2},L_{2}]$.

######  Lemma 5.2.

The following holds:

  * (a)

$\sigma_{t}(g)=0\ \wedge\ \sigma_{a}(g)=0\ \ \Rightarrow\ \
g\in\operatorname{{ncl}}(atat^{-1})$;

  * (b)

$V=\operatorname{{ncl}}(tt,atat)$;

  * (c)

$g\in V\ \ \Leftrightarrow\ \ \sigma_{t}(g)\mbox{ is even}\ \wedge\
\sigma_{a}(g)=0$.

###### Proof.

(a) Consider an arbitrary $g=(\delta,f)$ satisfying $\sigma_{t}(g)=0$ and
$\sigma_{a}(g)=0$. If $\operatorname{{supp}}(f)=\emptyset$, then $g$ is
trivial and the statement holds. Otherwise define

$m(f)=\min_{f(x)\neq 0}x\ \ \mbox{ and }\ \ M(f)=\max_{f(x)\neq 0}x,$

and notice that either $m(f)<0$ or $M(f)>0$ holds. Without loss of generality
we may assume that $M(f)>0$. Then $(\delta^{\prime},f^{\prime})=g\cdot
t^{M(f)-1}atat^{-1}t^{-M(f)+1}$ is another element satisfying the same
conditions with

$\operatorname{{supp}}(f^{\prime})=\emptyset\mbox{ or
}M(f^{\prime})-m(f^{\prime})<M(f)-m(f),$

which allows to use induction on $M(f)-m(f)$ and establishes (a).

(b) Obviously, $V\supseteq\operatorname{{ncl}}(tt,atat)$. Conversely,

$\displaystyle g\in V$ $\displaystyle\ \ \Rightarrow\ \ \sigma_{t}(g)=2b\mbox{
for some }b\in{\mathbb{Z}}$ $\displaystyle\ \ \Rightarrow\ \
\sigma_{t}(g^{\prime})=0\mbox{ and }\sigma_{a}(g^{\prime})=0\ \ \mbox{ for
}g^{\prime}=g\cdot(tt)^{-b}$ $\displaystyle\ \
\stackrel{{\scriptstyle(a)}}{{\Rightarrow}}\ \
g^{\prime}\in\operatorname{{ncl}}(atat^{-1})\ \ \Rightarrow\ \
g=g^{\prime}\cdot(tt)^{b}\in\operatorname{{ncl}}(tt,atat).$

(c) follows from the discussion above. ∎

By definition, the _verbal width_ of $V$ is the least
$k\in{\mathbb{N}}\cup\\{\infty\\}$ such that if $g\in V$, then $g$ is a
product of at most $k$ squares.

######  Proposition 5.3.

The verbal width of the subgroup $V$ is $2$.

###### Proof.

By Lemma 5.2, $atat^{3}\in V$ and by Lemma 5.1, $atat^{3}$ is not a square.
Hence, the verbal width of $V$ is greater than $1$.

Now, suppose that $(\delta,f)\in V$. Then $\delta=2(1+k)$ for some
$k\in{\mathbb{Z}}$. Define $g:{\mathbb{Z}}\to{\mathbb{Z}}_{2}$ by

$g(j)=\sum_{i=-\infty}^{j}f(i)\ \ \mbox{ for }x\in{\mathbb{Z}}.$

It is easy to check that

$(\delta,f)=(1,g)^{2}+(k,0)^{2}.$

Hence, every $(\delta,f)\in V$ can be expressed as a product of two squares
and the verbal width of $V$ is $2$. ∎

Proposition 5.3 implies that there are exactly two cases for non-orientable
equations over the lamplighter group: genus one and genus two (same as genus
more than one). The latter case is easy because $V$ is normal. Consider a non-
orientable equation of genus two

(7) $x^{2}y^{2}\prod z_{i}^{-1}c_{i}z_{i}=1.$

######  Proposition 5.4.

The Diophantine problem for equations (7) is decidable in linear time.

###### Proof.

By Proposition 5.3, (7) has a solution if and only if $\prod
z_{i}^{-1}c_{i}z_{i}\in V$ for some $z_{1},\dots,z_{k}\in L_{2}$ if and only
if $\sigma_{t}(c_{1}\cdots c_{k})$ is even and $\sigma_{a}(c_{1}\cdots
c_{k})=0$. The obtained condition can be checked in linear time. ∎

Consider a non-orientable equation of genus one

(8) $x^{2}\prod z_{i}^{-1}c_{i}z_{i}=1.$

Clearly, if the equation has a solution, then
$2\sigma_{t}(x)=-\sum\sigma_{t}(c_{i})$, i.e., $\sigma_{t}(x)$ is uniquely
defined by the equation.

######  Lemma 5.5.

If $c_{1}\cdots c_{k}=(0,f)$, then

$\underbrace{x^{2}\prod z_{i}^{-1}c_{i}z_{i}=1}_{W}\mbox{ has a solution }\
\Leftrightarrow\ \underbrace{\prod z_{i}^{-1}c_{i}z_{i}=1}_{W^{\prime}}\mbox{
has a solution.}$

###### Proof.

Name the genus one equation $W$ and the spherical equation $W^{\prime}$. If
$W^{\prime}$ has a solution, then the same assignment for $z_{1},\dots,z_{k}$
and $x=1$ gives a solution for $W$. Conversely, if $W$ has a solution with
$x=(\delta,f)$, then $\delta=0$. Notice that $(0,f)^{2}=1$ in $L_{2}$ for
every $f\colon{\mathbb{Z}}\to{\mathbb{Z}}_{2}$. Hence, we may assume that
$f=0$ and, $W$ has a solution. ∎

######  Proposition 5.6.

The Diophantine problem for equations (8) in ${\mathbf{NP}}$-hard.

###### Proof.

We can use the reduction discussed in Proposition 3.2.

$\\{s_{1},\ldots,s_{3k}\\}$ is a positive instance of $\operatorname{3PART}$
$\displaystyle\ \ \stackrel{{\scriptstyle\ref{pr:tpart}}}{{\Leftrightarrow}}\
\ \mbox{$\displaystyle\prod_{i=1}^{3k}z_{i}^{-1}c_{s_{i}}z_{i}=c$ has a
solution}$ $\displaystyle\ \ \stackrel{{\scriptstyle\ref{le:dropping-
genus}}}{{\Leftrightarrow}}\ \ \mbox{$\displaystyle
x^{2}\prod_{i=1}^{3k}z_{i}^{-1}c_{s_{i}}z_{i}=c$ has a solution.}$

Notice that Lemma 5.5 is applicable because, by design,
$\sigma_{t}(c_{s_{i}})=\sigma_{t}(c)=0$ for each $i=1,\dots,3k$. Thus, the
problem is ${\mathbf{NP}}$-hard. ∎

######  Theorem 5.7.

The Diophantine problem for equations (8) belongs to ${\mathbf{NP}}$.

###### Proof.

Consider an equation $W=1$ of type (8) with constants
$c_{i}=(\delta_{c_{i}},f_{c_{i}})$, that has a solution
$x=(\delta_{x},f_{x}),z_{1}=(\delta_{1},f_{1}),\dots,z_{k}=(\delta_{k},f_{k})$.
First, notice that

$\delta_{x}=\sigma_{t}(x)=-\tfrac{1}{2}(\delta_{c_{1}}+\dots+\delta_{c_{k}})\in{\mathbb{Z}}.$

If $\delta_{x}=0$, then, by Lemma 5.5, the equation has a solution if and only
if the spherical equation obtained by dropping $x^{2}$ has a solution. By
Theorem 3.5, spherical equations have ${\mathbf{NP}}$-certificates.

If $\delta_{x}\neq 0$, then $\delta_{c_{i}}\neq 0$ for some $i$, and

$0<\gcd(\delta_{x},\delta_{c_{1}},\dots,\delta_{c_{k}})=d\leq|W|.$

The second component of the equation $W=1$ (as an element of
${\mathbb{Z}}\ltimes{\mathbb{Z}}_{2}^{\mathbb{Z}}$) is of the form

(9)
$(1+x^{-\delta_{x}})x^{-\Delta_{0}}f_{x}+\sum_{i=1}^{k}x^{-\Delta_{i}}\left[(1-x^{-\delta_{c_{i}}})f_{i}+x^{-\delta_{i}}f_{c_{i}}\right]=0,$

where $\Delta_{i}=\delta_{c_{i+1}}+\dots+\delta_{c_{k}}$ for $i=0,\dots,k$,
and unknowns $f_{x},f_{1},\dots,f_{k}\in{\mathbb{Z}}_{2}^{\mathbb{Z}}$ and
$\delta_{1},\dots,\delta_{k}\in{\mathbb{Z}}$. By Proposition 2.4, (9) has a
solution if and only if the following equation:

(10)
$x^{\delta_{1}^{\prime}}f_{c_{1}}+\dots+x^{\delta_{k}^{\prime}}f_{c_{k}}=0$

has a solution in ${\mathbb{Z}}_{2}^{{\mathbb{Z}}_{d}}$ with
$\delta_{1}^{\prime},\dots,\delta_{k}^{\prime}\in{\mathbb{Z}}_{d}$. Notice
that the term $(1+x^{-\delta_{x}})x^{-\Delta_{0}}f_{x}$ vanishes because of
characteristic $2$. A solution of (10) establishes an
${\mathbf{NP}}$-certificate in this case. ∎

######  Corollary 5.8.

There is an algorithm that for a given non-orientable equation (8), decides if
it has a solution or not in time $O(|W|^{k})$.

###### Proof.

We can reuse parts of the proof of Theorem 5.7. If $\delta_{x}=0$, then the
problem reduces to a spherical equation that, by Corollary 3.7, can be solved
in time $O(|W|^{k})$.

If $\delta_{x}\neq 0$, then enumerate all tuples
$\delta_{2}^{\prime},\dots,\delta_{k}^{\prime}\in{\mathbb{Z}}_{d}$ and test if
$(0,\delta_{2}^{\prime},\dots,\delta_{k}^{\prime})$ satisfy (10). This can be
done in $O(|W|^{k})$ time. ∎

##  6\. Parametric complexity

In this section, we summarize some of our previous results and state that the
Diophantine problem for quadratic equations (of all three types (1), (2), and
(3)) over $L_{2}$ can be solved in polynomial time for any fixed bound on the
number of variables $k$, i.e., the Diophantine problem belongs to the
complexity class ${\mathbf{XP}}$ (“slicewise” polynomial time).

######  Corollary 6.1.

There is an algorithm that solves the Diophantine problem for quadratic
equations $W=1$ of type (1), (2), (3) over the lamplighter group $L_{2}$ in
time $O(|W|^{k})$.

###### Proof.

Follows from Corollary 3.7, Proposition 4.2, and Corollary 5.8. ∎

######  Corollary 6.2.

Fix $K\in{\mathbb{N}}$. The Diophantine problem for the class of quadratic
equations with $k\leq K$ is decidable in polynomial time. The Diophantine
problem for quadratic equations over the lamplighter group $L_{2}$ belongs to
${\mathbf{XP}}$.

## References

  * [1] L. Bartholdi, T. Groth, and I. Lysenok.  Commutator width in the first Grigorchuk group.  Groups Geom. Dyn., 16:493–522, 2022.
  * [2] L. Bartholdi and Z. Šunik.  Some solvable automaton groups, 2006.
  * [3] G. Baumslag.  Wreath products and finitely presented groups.  Math. Z., 75:22–28, 1961.
  * [4] M. Bonanome, M. Dean, and J. Dean.  The lamplighter group ${L_{2}}$.  In A sampling of remarkable groups: Thompson’s, self-similar, Lamplighter, and Baumslag-Solitar, pages 105–132. Birkhauser, 2018.
  * [5] S. Cleary and J. Taback.  Dead end words in lamplighter groups and other wreath products.  Quart. J. Math. Oxford, 56:165–178, 2005.
  * [6] L. Comerford and C. Edmunds.  Quadratic equations over free groups and free products.  J. Algebra, 68:276–297, 1981.
  * [7] V. Diekert and J. Robson.  Quadratic word equations, pages 314–326.  Springer Berlin Heidelberg, Berlin, Heidelberg, 1999.
  * [8] M. Garey and J. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman, 1979.
  * [9] R. Grigorchuk and P. Kurchanov.  On quadratic equations in free groups.  In Proc. Int. Conf. on Algebra Dedicated to the Memory of A. I. Malcev, volume 131 of Contemporary Mathematics, pages 159–171. American Mathematical Society, 1992.
  * [10] R. Grigorchuk and I. Lysenok.  A description of solutions of quadratic equations in hyperbolic groups.  International Journal of Algebra and Computation, 2(3):237–274, 1992.
  * [11] R. Grigorchuk and A. Żuk.  The lamplighter group as a group generated by a $2$-state automaton, and its spectrum.  Geometriae Dedicata, 87:209–244, 2001.
  * [12] V. Kaimanovich and A. Vershik.  Random walks on discrete groups: Boundary and entropy.  Ann. Probab., 11:457–490, 1983.
  * [13] O. Kharlampovich, L. Lopez, and A. Miasnikov.  Diophantine Problem in Some Metabelian Groups.  Mathematics of Computation, 89:2507, 2020.
  * [14] O. Kharlampovich, I. Lysenok, A. Miasnikov, and N. Touikan.  The solvability problem for quadratic equations over free groups is NP-complete.  Theor. Comput. Syst., 47:250–258, 2010.
  * [15] O. Kharlampovich, A. Mohajeri, A. Taam, and A. Vdovina.  Quadratic equations in hyperbolic groups are NP-complete.  Transactions of the American Mathematical Society, 369(9):6207–6238, 2017.
  * [16] D. Knuth, J. H. Morris, and V. Pratt.  Fast pattern matching in strings.  SIAM J. Comput., 6:323–350, 1977.
  * [17] I. Lysenok, A. Miasnikov, and A. Ushakov.  Quadratic equations in the Grigorchuk group.  Groups, Geometry, and Dynamics, 10:201–239, 2016.
  * [18] I. Lysenok and A. Ushakov.  Spherical quadratic equations in free metabelian groups.  Proc. Amer. Math. Soc., 144:1383–1390, 2016.
  * [19] I. Lysenok and A. Ushakov.  Orientable quadratic equations in free metabelian groups.  Journal of Algebra, 581:303–326, 2021.
  * [20] A. Malcev.  On equation $zxyx^{-1}y^{-1}z^{-1}=aba^{-1}b^{-1}$ in a free group.  Algebra i Logika, 5:45–50, 1962.
  * [21] R. Mandel and A. Ushakov.  Quadratic equations in metabelian Baumslag-Solitar groups.  Int. J. Algebra Comput., 33(6):1195–1216, 2023.
  * [22] A. Sale.  The geometry of the conjugacy problem in wreath products and free solvable groups.  preprint. Available at http://arxiv.org/abs/1307.6812.
  * [23] A. Sale.  The geometry of the conjugacy problem in lamplighter groups.  In Algebra and Computer Science, volume 677 of Contemporary Mathematics, pages 171–183. American Mathematical Society, 2016\.
  * [24] J. Siehler.  The finite lamplighter groups: a guided tour.  The College Mathematics Journal, 43(3):203–211, 2012.