KNAPSACK PROBLEMS FOR WREATH PRODUCTS

arXiv:1709.09598v2 [] 2 Oct 2017

MOSES GANARDI, DANIEL KÖNIG, MARKUS LOHREY, AND GEORG ZETZSCHE

Abstract. In recent years, knapsack problems for (in general non-commutative) groups
have attracted attention. In this paper, the knapsack problem for wreath products
is studied. It turns out that decidability of knapsack is not preserved under wreath
product. On the other hand, the class of knapsack-semilinear groups, where solutions
sets of knapsack equations are eﬀectively semilinear, is closed under wreath product. As
a consequence, we obtain the decidability of knapsack for free solvable groups. Finally,
it is shown that for every non-trivial abelian group G, knapsack (as well as the related
subset sum problem) for the wreath product G ≀ Z is NP-complete.

1. Introduction
In [23], Myasnikov, Nikolaev, and Ushakov began the investigation of classical discrete
optimization problems, which are formulated over the integers, for arbitrary (possibly noncommutative) groups. The general goal of this line of research is to study to what extent
results from the commutative setting can be transferred to the non-commutative setting.
Among other problems, Myasnikov et al. introduced for a finitely generated group G the
knapsack problem and the subset sum problem. The input for the knapsack problem is a
sequence of group elements g1 , . . . , gk , g ∈ G (specified by finite words over the generators
of G) and it is asked whether there exists a solution (x1 , . . . , xk ) ∈ Nk of the equation
g1x1 · · · gkxk = g. For the subset sum problem one restricts the solution to {0, 1}k . For
the particular case G = Z (where the additive notation x1 · g1 + · · · + xk · gk = g is usually
preferred) these problems are NP-complete (resp., TC0 -complete) if the numbers g1 , . . . , gk , g
are encoded in binary representation [11, 8] (resp., unary notation [3]).
Another motivation is that decidability of knapsack for a group G implies that the membership problem for polycyclic subgroups of G is decidable. This follows from the well-known
fact that every polycyclic group A has a generating set {a1 , . . . , ak } such that every element
of A can be written as an1 1 · · · ank k for n1 , . . . , nk ∈ N, see e.g. [27, Chapter 9].
In [23], Myasnikov et al. encode elements of the finitely generated group G by words
over the group generators and their inverses, which corresponds to the unary encoding of
integers. There is also an encoding of words that corresponds to the binary encoding of
integers, so called straight-line programs, and knapsack problems under this encodings have
been studied in [18]. In this paper, we only consider the case where input words are explicitly
represented. Here is a (non-complete) list of known results concerning knapsack and subset
sum problems:
• Subset sum and knapsack can be solved in polynomial time for every hyperbolic
group [23]. In [4] this result was extended to free products of any number of hyperbolic groups and finitely generated abelian groups.
• For every virtually nilpotent group, subset sum belongs to NL (nondeterministic
logspace) [12]. On the other hand, there are nilpotent groups of class 2 for which
knapsack is undecidable. Concrete examples are direct products of sufficiently many
1991 Mathematics Subject Classification. 20F10.
Key words and phrases. knapsack, wreath products, decision problems in group theory.
The fourth author is supported by a fellowship within the Postdoc-Program of the German Academic
Exchange Service (DAAD) and by Labex DigiCosme, Univ. Paris-Saclay, project VERICONISS..
1

2

M. GANARDI, D. KÖNIG, M. LOHREY, AND G. ZETZSCHE

•

•

•

•

•

copies of the discrete Heisenberg group H3 (Z) [12], and free nilpotent groups of class
2 and sufficiently high rank [22].
Knapsack for the discrete Heisenberg group H3 (Z) is decidable [12]. In particular, together with the previous point it follows that decidability of knapsack is not
preserved under direct products.
For the following groups, subset sum is NP-complete (whereas the word problem can
be solved in polynomial time): free metabelian non-abelian groups of finite rank, the
wreath product Z≀Z, Thompson’s group F , the Baumslag-Solitar group BS(1, 2) [23],
and every polycyclic group that is not virtually nilpotent [26].
Knapsack is decidable for every co-context-free group (a group is co-context-free if
the set of all words over the generators that do not represent the group identity is
a context-free language) [12].
Knapsack belongs to NP for every virtually special group [18]. A group is virtually
special if it is a finite extension of a subgroup of a graph group. For graph groups
(also known as right-angled Artin groups) a complete classification of the complexity
of knapsack was obtained in [19]: If the underlying graph contains an induced path
or cycle on 4 nodes, then knapsack is NP-complete; in all other cases knapsack can
be solved in polynomial time (even in LogCFL).
Decidability of knapsack is preserved under finite extensions, HNN-extensions over
finite associated subgroups and amalgamated free products over finite subgroups
[18].

In this paper, we study the knapsack problem for wreath products. The wreath product
is a fundamental construction in group theory and semigroup theory, see Section 4 for the
definition. An important application of wreath products in group theory is the Magnus
embedding theorem [20], which allows to embed the quotient group Fk /[N, N ] into the
wreath product Zk ≀ (Fk /N ), where Fk is a free group of rank k and N is a normal subgroup
of Fk . From the algorithmic point of view, wreath products have some nice properties: The
word problem for a wreath product G ≀ H is AC0 -reducible to the word problems for the
factors G and H, and the conjugacy problem for G ≀ H is TC0 -reducible to the conjugacy
problems for G and H and the so called power problem for H [21].
As in the case of direct products, it turns out that decidability of knapsack is not preserved
under wreath products: For this we consider direct products of the form H3 (Z) × Zℓ , where
H3 (Z) is the discrete 3-dimensional Heisenberg group. It was shown in [12] that for every
ℓ ≥ 0, knapsack is decidable for H3 (Z) × Zℓ . We prove in Section 6 that for every non-trivial
group G and every sufficiently large ℓ, knapsack for G ≀ (H3 (Z) × Zℓ ) is undecidable.
By the above discussion, we need stronger assumptions on G and H to obtain decidability
of knapsack for G≀H. We exhibit a very weak condition on G and H, knapsack-semilinearity,
which is sufficient for decidability of knapsack for G ≀ H. A finitely generated group G is
knapsack-semilinear if for every knapsack equation, the set of all solutions (a solution can
be seen as an vector of natural numbers) is effectively semilinear.
Clearly, for every knapsack-semilinear group, the knapsack problem is decidable. While
the converse is not true, the class of knapsack-semilinear groups is extraordinarily wide.
The simplest examples are finitely generated abelian groups, but it also includes the rich
class of virtually special groups [18], all hyperbolic groups (see Appendix A), and all cocontext-free groups [12]. Furthermore, it is known to be closed under direct products (an
easy observation), finite extensions, HNN-extensions over finite associated subgroups and
amalgamated free products over finite subgroups (the last three closure properties are simple
extensions of the transfer theorems in [18]). In fact, the only non-knapsack-semilinear groups
with a decidable knapsack problem that we are aware of are the groups H3 (Z) × Zn .
We prove in Section 7 that the class of knapsack-semilinear groups is closed under wreath
products. As a direct consequence of the Magnus embedding, it follows that knapsack is

KNAPSACK PROBLEMS FOR WREATH PRODUCTS

3

decidable for every free solvable group. Recall, that in contrast, knapsack for free nilpotent
groups is in general undecidable [22].
Finally, we consider the complexity of knapsack for wreath products. We prove that
for every non-trivial finitely generated abelian group G, knapsack for G ≀ Z is NP-complete
(the hard part is membership in NP). This result includes important special cases like for
instance the lamplighter group Z2 ≀ Z and Z ≀ Z. Wreath products of the form G ≀ Z with G
abelian turn out to be important in connection with subgroup distortion [1]. Our proof also
shows that for every non-trivial finitely generated abelian group G, the subset sum problem
for G ≀ Z is NP-complete. In [23] this result is only shown for infinite abelian groups G.
2. Preliminaries
We assume standard notions concerning groups. A group G is finitely generated if there
exists a finite subset Σ ⊆ G such that every element g ∈ G can be written as g = a1 a2 · · · an
with a1 , a2 , . . . , an ∈ Σ. We also say that the word a1 a2 · · · an ∈ Σ∗ evaluates to g (or
represents g). The set Σ is called a finite generating set of G. We always assume that Σ
is symmetric in the sense that a ∈ Σ implies a−1 ∈ Σ. An element g ∈ G is called torsion
element if there is an n ≥ 1 with g n = 1. The smallest such n is the order of g and denoted
ord(g). If g is not a torsion element, we set ord(g) = ∞.
A set of vectors A ⊆ Nk is linear if there exist vectors v0 , . . . , vn ∈ Nk such that
A = {v0 + λ1 · v1 + · · · + λn · vn | λ1 , . . . , λn ∈ N}.
The tuple of vectors (v0 , . . . , vn ) is a linear represention of A. A set A ⊆ Nk is semilinear
if it is a finite union of linear sets A1 , . . . , Am . A semilinear representation of A is a list of
linear representations for the linear sets A1 , . . . , Am . It is well-known that the semilinear
subsets of Nk are exactly the sets definable in Presburger arithmetic. These are those sets
that can be defined with a first-order formula ϕ(x1 , . . . , xk ) over the structure (N, 0, +, ≤
) [7]. Moreover, the transformations between such a first-order formula and an equivalent
semilinear representation are effective. In particular, the semilinear sets are effectively closed
under Boolean operations.
3. Knapsack for groups
Let G be a finitely generated group with the finite symmetric generating set Σ. Moreover,
let V be a set of formal variables that take values from N. For a subset U ⊆ V , we use NU to
denote the set of maps ν : U → N, which we call valuations. An exponent expression over G is
a formal expression of the form E = v0 ux1 1 v1 ux2 2 v2 · · · uxk k vk with k ≥ 0 and words ui , vi ∈ Σ∗ .
Here, the variables do not have to be pairwise distinct. If every variable in an exponent
expression occurs at most once, it is called a knapsack expression. Let VE = {x1 , . . . , xk } be
the set of variables that occur in E. For a valuation ν ∈ NU such that VE ⊆ U (in which case
ν(x )
ν(x )
ν(x )
we also say that ν is a valuation for E), we define ν(E) = v0 u1 1 v1 u2 2 v2 · · · uk k vk ∈ Σ∗ .
We say that ν is a solution of the equation E = 1 if ν(E) evaluates to the identity element
1 of G. With Sol(E) we denote the set of all solutions ν ∈ NVE of E. We can view Sol(E)
Pk
as a subset of Nk . The length of E is defined as |E| = |v0 | + i=1 |ui | + |vi |, whereas k is
its depth. If the length of a knapsack expression is not needed, we will write an exponent
expression over G also as E = h0 g1x1 h1 g2x2 h2 · · · gkxk hk where gi , hi ∈ G. We define solvability
of exponent equations over G, ExpEq(G) for short, as the following decision problem:
Input: A finite
Tnlist of exponent expressions E1 , . . . , En over G.
Question: Is i=1 Sol(Ei ) non-empty?

The knapsack problem for G, KP(G) for short, is the following decision problem:
Input: A single knapsack expression E over G.
Question: Is Sol(E) non-empty?

4

M. GANARDI, D. KÖNIG, M. LOHREY, AND G. ZETZSCHE

We also consider the uniform knapsack problem for powers
Gm = G × · · · × G .
|
{z
}
m many

∗

We denote this problem with KP(G ). Formally, it is defined as follows:
Input: A number m ≥ 0 (represented in unary notation) and a knapsack expression E over
the group Gm .
Question: Is Sol(E) non-empty?
It turns out that the problems KP(G∗ ) and ExpEq(G) are interreducible:
Proposition 3.1. For every finitely generated group G, KP(G∗ ) is decidable if and only if
ExpEq(G) is decidable.
Proof. Clearly, every instance of KP(G∗ ) can be translated to an instance of ExpEq(G)
by projecting onto the m factors of a power Gm . For the converse direction, assume that
KP(G∗ ) is decidable. Then in particular, G has a decidable word problem. Let Ej =
xk,j
x
hk,j be an exponent expression over G for every j ∈ [1, m]. By adding
h0,j g1,j1,j h1,j · · · gk,j
dummy powers of the form 1x we may assume that the Ej have the same depth k. We
distinguish two cases.
Case 1. G is a torsion group. Since G has a decidable word problem, we can compute ℓ ∈ N
ℓ
so that gi,j
= 1 for every i ∈ [1, k] and j ∈ [1, m]. Then there is a solution to the exponent
equation system if and only if there is a solution ν with 0 ≤ ν(x) < ℓ for every variable x.
Hence, solvability is clearly decidable.
Case 2. There is some a ∈ G with ord(a) = ∞. We first rename the variables in E1 , . . . , Em
such that every variable occurs at most once in the entire system of expressions. Let
′
be the resulting system of knapsack expressions and let U be the set of variables
E1′ , . . . , Em
′
. We can compute an equivalence relation ∼ ⊆ U × U such that
that occur in E1′ , . . . , Em
′
the system E1 = 1, . . . , Em = 1 has a solution if and only if the system E1′ = 1, . . . , Em
=1
′
′
has a solution ν with ν(x) = ν(x ) for x ∼ x . We can equip U with a linear order ≤ so that
if x occurs left of x′ in some Ej′ , then x < x′ .
Now for each pair (x, x′ ) ∈ U × U with x ∼ x′ and x < x′ , we add the knapsack
′
′
for some ℓ ≥ 0 such
expression ax (a−1 )x . This yields knapsack expressions E1′ , . . . , Em+ℓ
′
′
that E1 = 1, . . . , Em+ℓ = 1 is solvable if and only if E1 = 1, . . . , Em = 1 is solvable.
Moreover, whenever x occurs to the left of x′ in some expression, then x < x′ .
′
By padding the expressions with trivial powers, we turn E1′ , . . . , Em+ℓ
into expressions
′′
that all exhibit the same variables (in the same order). Now, it is easy to turn
E1′′ , . . . , Em+ℓ
′′
into a single knapsack expression over Gm+ℓ .

E1′′ , . . . , Em+ℓ
Note that the equation v0 ux1 1 v1 ux2 2 v2 · · · uxk k vk = 1 is equivalent to
−1
· · · v0−1 )xk (v0 · · · vk ) = 1.
(v0 u1 v0−1 )x1 (v0 v1 u2 v1−1 v0−1 )x2 · · · (v0 · · · vk−1 uk vk−1

Hence, it suffices to consider exponent expressions of the form ux1 1 ux2 2 · · · uxk k v.
The group G is called knapsack-semilinear if for every knapsack expression E over G, the
set Sol(E) is a semilinear set of vectors and a semilinear representation can be effectively
computed from E. The following classes of groups only contain knapsack-semilinear groups:
• virtually special groups [17]: these are finite extensions of subgroups of graph groups
(aka right-angled Artin groups). The class of virtually special groups is very rich.
It contains all Coxeter groups, one-relator groups with torsion, fully residually free
groups, and fundamental groups of hyperbolic 3-manifolds.
• hyperbolic groups: see Appendix A
• co-context-free groups [12], i.e., groups where the set of all words over the generators
that do not represent the identity is a context-free language. Lehnert and Schweitzer
[14] have shown that the Higman-Thompson groups are co-context-free.

KNAPSACK PROBLEMS FOR WREATH PRODUCTS

5

Since the emptiness of the intersection of finitely many semilinear sets is decidable, we have:
Lemma 3.2. If G is knapsack-semilinear, then KP(G∗ ) and ExpEq(G) are decidable.
An example of a group G, where KP(G) is decidable but KP(G∗ ) (and hence ExpEq(G))
are undecidable is the Heisenberg group H3 (Z), see [12]. It is the group of all matrices of
the following form, where a, b, c ∈ Z:


1 a c
0 1 b 
0 0 1
In particular, H3 (Z) is not knapsack-semilinear.

4. Wreath products
L
Let G and H be groups. Consider the direct sum K = h∈H Gh , where Gh is a copy of
G. We view K as the set G(H) of all mappings f : H → G such that supp(f ) = {h ∈ H |
f (h) 6= 1} is finite, together with pointwise multiplication as the group operation. The set
supp(f ) ⊆ H is called the support of f . The group H has a natural left action on G(H) given
by hf (a) = f (h−1 a), where f ∈ G(H) and h, a ∈ H. The corresponding semidirect product
G(H) ⋊ H is the wreath product G ≀ H. In other words:
• Elements of G ≀ H are pairs (f, h), where h ∈ H and f ∈ G(H) .
• The multiplication in G ≀ H is defined as follows: Let (f1 , h1 ), (f2 , h2 ) ∈ G ≀ H. Then
(f1 , h1 )(f2 , h2 ) = (f, h1 h2 ), where f (a) = f1 (a)f2 (h−1
1 a).
The following intuition might be helpful: An element (f, h) ∈ G ≀ H can be thought of
as a finite multiset of elements of G \ {1G } that are sitting at certain elements of H (the
mapping f ) together with the distinguished element h ∈ H, which can be thought of as
a cursor moving in H. If we want to compute the product (f1 , h1 )(f2 , h2 ), we do this as
follows: First, we shift the finite collection of G-elements that corresponds to the mapping
f2 by h1 : If the element g ∈ G \ {1G } is sitting at a ∈ H (i.e., f2 (a) = g), then we remove
g from a and put it to the new location h1 a ∈ H. This new collection corresponds to the
mapping f2′ : a 7→ f2 (h−1
1 a). After this shift, we multiply the two collections of G-elements
pointwise: If in a ∈ H the elements g1 and g2 are sitting (i.e., f1 (a) = g1 and f2′ (a) = g2 ),
then we put the product g1 g2 into the location a. Finally, the new distinguished H-element
(the new cursor position) becomes h1 h2 .
By identifying f ∈ G(H) with (f, 1H ) ∈ G ≀ H and h ∈ H with (1G(H) , h), we regard
(H)
G
and H as subgroups of G ≀ H. Hence, for f ∈ G(H) and h ∈ H, we have f h =
(f, 1H )(1G(H) , h) = (f, h). There are two natural projection morphism σG≀H : G ≀ H → H
and τG≀H : G ≀ G(H) with
(1)

σG≀H (f, h) = h,

(2)

τG≀H (f, h) = f.

If G (resp. H) is generated by the set Σ (resp. Γ) with Σ ∩ Γ = ∅, then G ≀ H is generated
by the set {(fa , 1H ) | a ∈ Σ} ∪ {(f1G , b) | b ∈ Γ}, where for g ∈ G, the mapping fg : H → G
is defined by fg (1H ) = g and fg (x) = 1G for x ∈ H \ {1H }. This generating set can be
identified with Σ ⊎ Γ. We will need the following embedding lemma:
Lemma 4.1. Let G, H, K be finitely generated groups where K has a decidable word problem.
Then, given n ∈ N with n ≤ |K|, one can compute an embedding of Gn ≀ H into G ≀ (H × K).
Proof. Let Σ, Γ, and Θ be finite generating sets of G, H, and K, respectively. Suppose
n ∈ N is given. Since K has a decidable word problem and |K| ≥ n, we can compute words
w1 , . . . , wn ∈ Θ∗ that represent pairwise distinct elements k1 , . . . , kn of K.
Let πi : Gn → G be the projection on the i-th coordinate. Since the statement of the
lemma does not depend on the chosen generating sets of Gn ≀ H and G ≀ (H × K), we may

6

M. GANARDI, D. KÖNIG, M. LOHREY, AND G. ZETZSCHE

choose one. The group Gn is generated by the tuples si := (1, . . . , 1, s, 1, . . . , 1) ∈ Gn , for
s ∈ Σ and i ∈ [1, n], where s is at the i-th coordinate. Hence, ∆ = {si | s ∈ Σ, i ∈ [1, n]} ⊎ Γ
is a finite generating set of Gn ≀ H.
The embedding ι : ∆∗ → (Σ ∪ Γ ∪ Θ)∗ is defined by ι(si ) = wi swi−1 for s ∈ Σ, i ∈ [1, n]
and ι(t) = t for t ∈ Γ. It remains to be shown that ι induces an embedding of Gn ≀ H into
G ≀ (H × K).
Consider the injective morphism ϕ : (Gn )(H) → G(H×K) where for ζ ∈ (Gn )(H) , we have
(
πi (ζ(h)) if k = ki
[ϕ(ζ)](h, k) =
1
if k ∈
/ {k1 , . . . , kn }
We claim that ϕ extends to an injective morphism ϕ̂ : (Gn )(H) ⋊ H → G(H×K) ⋊ H where
H acts on G(H×K) by (hζ)(a, k) = ζ(h−1 a, k) for h, a ∈ H, k ∈ K. To show this, it suffices
to establish ϕ(hζ) = hϕ(ζ) for all ζ ∈ (Gn )(H) , h ∈ H, i.e., the action of H commutes with
the morphism ϕ. To see this, note that
[ϕ(hζ)](a, ki ) = πi ((hζ)(a)) = πi (ζ(h−1 a)) = [ϕ(ζ)](h−1 a, ki ) = [hϕ(ζ)](a, ki )
and if k ∈
/ {k1 , . . . , kn }, we have
[ϕ(hζ)](a, k) = 1 = [ϕ(ζ)](h−1 a, k) = [hϕ(ζ)](a, k).
Since the above action of H on G(H×K) is the restriction of the action of H × K on G(H×K) ,
we have G(H×K) ⋊ H ≤ G(H×K) ⋊ (H × K) = G ≀ (H × K). Thus ϕ̂ can be viewed as an
embedding ϕ̂ : Gn ≀ H → G ≀ (H × K).
We complete the proof by showing that ι represents ϕ̂, i.e. ϕ̂(w) = ι(w) for every w ∈ ∆∗ ,
where w denotes the element of (Gn )(H) ⋊H represented by the word w and similarly for ι(w).
It suffices to prove this in the case w ∈ ∆ ⊆ (Gn )(H) ⋊ H. If w = si with s ∈ Σ, i ∈ [1, n], we
observe that ϕ̂(si ) = ki ski−1 = ι(si ). Moreover, for t ∈ Γ ⊆ H we have ϕ̂(t) = t = ι(t). 
5. Main results
In this section, we state the main results of the paper. We begin with a general necessary
condition for knapsack to be decidable for a wreath product. Note that if H is finite, then
G ≀ H is a finite extension of G|H| [16, Proposition 1], meaning that KP(G ≀ H) is decidable
if and only if KP(G|H| ) is decidable [18, Theorem 11]1. Therefore, we are only interested in
the case that H is infinite.
Proposition 5.1. Suppose H is infinite. If KP(G ≀ H) is decidable, then KP(H) and
KP(G∗ ) are decidable.
Proof. As a subgroup of G ≀ H, H inherits decidability of the knapsack problem. According
to Lemma 4.1, given m ∈ N, we can compute an embedding of Gm into G ≀ H and thus solve
knapsack instances over Gm uniformly in m.

Proposition 5.1 shows that KP(H3 (Z) ≀ Z) is undecidable: It was shown in [12] that
KP(H3 (Z)) is decidable, whereas for some m > 1, the problem KP(H3 (Z)m ) is undecidable.
Proposition 5.1 raises the question whether decidability of KP(H) and KP(G∗ ) implies
decidability of KP(G ≀ H). The answer turns out to be negative. Let us first recall the
following result from [12]:
Theorem 5.2 ([12]). For every ℓ ∈ N, KP(H3 (Z) × Zℓ ) is decidable.
Hence, by the following result, which is shown in Section 6, decidability of KP(H) and
KP(G∗ ) does in general not imply decidability of KP(G ≀ H):
1Strictly speaking, only preservation of NP-membership was shown there. However, the proof also yields
preservation of decidability.

KNAPSACK PROBLEMS FOR WREATH PRODUCTS

7

Theorem 5.3. There is an ℓ ∈ N such that for every group G 6= 1, KP(G ≀ (H3 (Z) × Zℓ ))
is undecidable.
We therefore need to strengthen the assumptions on H in order to show decidability of
KP(G ≀ H). By adding the weak assumption of knapsack-semilinearity for H, we obtain a
partial converse to Proposition 5.1. In Section 7 we prove:
Theorem 5.4. Let H be knapsack-semilinear. Then KP(G ≀ H) is decidable if and only if
KP(G∗ ) is decidable.
In fact, in case G is also knapsack-semilinear, our algorithm constructs a semilinear
representation of the solution set. Therefore, we get:
Theorem 5.5. The group G ≀ H is knapsack-semilinear if and only if both G and H are
knapsack-semilinear.
Since every free abelian group is clearly knapsack-semilinear, it follows that the iterated
wreath products G1,r = Zr and Gd+1,r = Zr ≀ Gd,r are knapsack-semilinear. By the wellknown Magnus embedding, the free solvable group Sd,r embeds into Gd,r . Hence, we get:
Corollary 5.6. Every free solvable group is knapsack-semilinear. Hence, solvability of
exponent equations is decidable for free solvable groups.
Finally, we consider the complexity of knapsack for wreath products. We prove NPcompleteness for an important special case:
Theorem 5.7. For every non-trivial finitely generated abelian group G, KP(G ≀ Z) is NPcomplete.
6. Undecidability: Proof of Theorem 5.3
Our proof of Theorem 5.3 employs the undecidability of the knapsack problem for certain
powers of H3 (Z). In fact, we need a slightly stronger version, which states undecidability
already for knapsack instances of bounded depths.
Theorem 6.1 ([12]). There is a fixed constant m and a fixed list of group elements g1 , . . . , gk ∈
Q
H3 (Z)m such that membership in the product ki=1 hgi i is undecidable. In particular, there
are k, m ∈ N such that solvability of knapsack instances of depth k is undecidable for H3 (Z)m .
We prove Theorem 5.3 by showing the following.
Proposition 6.2. There are m, ℓ ∈ N such that for every non-trivial group G, the knapsack
problem for Gm ≀ (H3 (Z) × Zℓ ) is undecidable.
Let k and m be the constants from Theorem 6.1. In order to prove Proposition 6.2,
consider a knapsack expression
E = g1x1 · · · gkxk gk+1

(3)

with g1 , . . . , gk+1 ∈ H3 (Z)m . We can write gi = (gi,1 , . . . , gi,m ) for i ∈ [1, k + 1], which leads
to the expressions
x

x

k,j
gk+1,j .
Ej = g1,j1,j · · · gk,j

(4)

Let ℓ = m·k and let α : H3 (Z)×Zℓ → H3 (Z) and β : H3 (Z)×Zℓ → Zℓ be the projection onto
the left and right component, respectively. For each p ∈ [1, ℓ], let ep ∈ Zℓ be the p-th unit
vector ep = (0, . . . , 0, 1, 0, . . . , 0). For j ∈ [1, m] we define the following knapsack expressions
over H3 (Z) × Zℓ (0 denotes the zero vector of dimension ℓ):
Ej′ =

k
Y

i=1

(gi,j , e(j−1)k+i )xi,j (gk+1,j , 0)

and

Mj =

ℓ
Y

(1, −et )yj,t,0 (1, et )yj,t,1 .

t=1

8

M. GANARDI, D. KÖNIG, M. LOHREY, AND G. ZETZSCHE

Note that the term (j − 1)k + i assumes all numbers 1, . . . , m · k as i ranges over 1, . . . , k
and j ranges over 1, . . . , m.
Since G is non-trivial, there is some a ∈ G \ {1}. For each j ∈ [1, m], let aj =
(1, . . . , 1, a, 1, . . . , 1) ∈ Gm , where the a is in the j-th coordinate. With this, we define

 Y
Y
zi
m
m
m
k Y
Y
−1
′
aj M j .
aj Ej C
and F =
(1, −e(j−1)k+i )
C=
i=1

j=1

j=1

j=1

m

ℓ

m

ℓ

Since G and H3 (Z) × Z are subgroups of G ≀ (H3 (Z) × Z ), we can treat F as a knapsack
expression over Gm ≀ (H3 (Z) × Zℓ ). We will show that Sol(F ) 6= ∅ if and only if Sol(E) 6= ∅.
For this we need another simple lemma:
Lemma 6.3. Let G, H be groups and let a ∈ G \ {1} and f, g, h ∈ H. Regard G and H as
subsets of G ≀ H. Then f aga−1 h = 1 if and only if g = 1 and f h = 1.
Proof. The right-to-left direction is trivial. For the converse, suppose f aga−1 h = 1 and
g 6= 1. By definition of G ≀ H, we can write f aga−1 h = (ζ, p) with ζ ∈ G(H) and p ∈ H,
where ζ(f ) = a 6= 1, ζ(f g) = a−1 6= 1, and p = f gh. This clearly implies f aga−1 h 6= 1, a
contradiction. Hence, f aga−1 h = 1 implies g = 1 and thus f h = 1.

In the proof of the following lemma, we use the simple fact that every morphism ϕ : G →
G′ extends uniquely to a morphism ϕ̂ : G ≀ H → G′ ≀ H such that ϕ̂↾G = ϕ and ϕ̂↾H = idH
(the identity mapping on H).
Lemma 6.4. A valuation ν for F satisfies ν(F ) = 1 if and only if for every i ∈ [1, k],
j ∈ [1, m], t ∈ [1, m − 1], we have
(5)

ν(Ej ) = 1,

(6)

ν(Mt ) =

ν(xi,j ) = ν(zi ),

ν(Et′ ),

ν(M1 · · · Mm ) = 1.

m

Proof. Let πj : G → G be the projection morphism onto the j-th coordinate and let
π̂j : Gm ≀ (H3 (Z) × Zℓ ) → G ≀ (H3 (Z) × Zℓ ) be its extension with π̂j ↾H3 (Z)×Zℓ = idH3 (Z)×Zℓ . Of
course, for g ∈ Gm ≀ (H3 (Z) × Zℓ ), we have g = 1 if and only if π̂j (g) = 1 for every j ∈ [1, m].
Observe that



Y

  r−1
 r−1
m
m
Y
Y  Y
Mj 
Mj a−1
Ej′ C
Ej′ a
π̂r (ν(F )) = ν 
j=1

j=r

j=1

j=r

for every r ∈ [1, m]. Therefore, according to Lemma 6.3, ν(F ) = 1 holds if and only if for
every r ∈ [1, m], we have
(7)

′
ν(E1′ · · · Em
CM1 · · · Mm ) = 1

and

′
ν(Er′ · · · Em
CM1 · · · Mr−1 ) = 1.

We claim that Eq. (7) holds for all r ∈ [1, m] if and only if
(8)

′
ν(E1′ · · · Em
C) = 1,

ν(Et′ ) = ν(Mt )

and

ν(M1 · · · Mm ) = 1

for all t ∈ [1, m − 1]. First assume that Eq. (8) holds for all t ∈ [1, m − 1]. We clearly get
′
′
ν(E1′ · · · Em
CM1 · · · Mm ) = 1 and ν(Er′ · · · Em
CM1 · · · Mr−1 ) = 1 for r = 1. The equations
′
′
′
ν(Er · · · Em CM1 · · · Mr−1 ) = 1 for r ∈ [2, m] are obtained by conjugating ν(E1′ · · · Em
C) = 1
′
′
with ν(E1 ) = ν(M1 ), . . . , ν(Er−1 ) = ν(Mr−1 ). Now assume that Eq. (7) holds for all r ∈
′
[1, m]. Taking r = 1 yields ν(E1′ · · · Em
C) = 1 and hence ν(M1 · · · Mm ) = 1. Moreover, we
′
′
′
′
have ν(E1 · · · Er−1 ) = ν(E1 · · · Em CM1 · · · Mr−1 ) = ν(M1 · · · Mr−1 ) for all r ∈ [1, m], which
implies ν(Et′ ) = ν(Mt ) for all t ∈ [1, m − 1].
Observe that by construction of Ej′ and C, we have
(9)
(10)

α(ν(Ej′ )) = ν(Ej ),
α(ν(C)) = 1,

for every i ∈ [1, k] and j ∈ [1, m].

′
π(j−1)k+i (β(ν(E1′ · · · Em
))) = ν(xi,j ),

π(j−1)k+i (β(ν(C))) = −ν(zi ).

KNAPSACK PROBLEMS FOR WREATH PRODUCTS

9

Note that the equations in Eq. (8) only involve elements of H3 (Z)×Zℓ . Since for elements
g ∈ H3 (Z) × Zℓ , we have g = 1 if and only if α(g) = 1 and β(g) = 1, the equation
′
′
′
ν(E1′ · · · Em
C) = 1 is equivalent to α(ν(E1′ · · · Em
C)) = 1 and β(ν(E1′ · · · Em
C)) = 1. By
Eqs. (9) to (10), this is equivalent to ν(E1 · · · Em ) = 1 and ν(xi,j ) = ν(zi ) for all i ∈ [1, k]
and j ∈ [1, m]. Finally, ν(Et′ ) = ν(Mt ) implies ν(Et ) = α(ν(Et′ )) = α(ν(Mt )) = 1 for all
t ∈ [1, m − 1] and hence also ν(Em ) = 1. Thus, Eq. (8) is equivalent to the conditions in the
lemma.

Lemma 6.5. Sol(F ) 6= ∅ if and only if Sol(E) 6= ∅.
Proof. If ν(F ) = 1, then according to Lemma 6.4, the valuation also satisfies ν(Ej ) = 1 and
ν(xi,j ) = ν(zi ) for i ∈ [1, k] and j ∈ [1, m]. In particular ν(xi,j ) = ν(xi,j ′ ) for j, j ′ ∈ [1, m].
Thus, we have
ν(x )
ν(x )
g1 1,1 · · · gk k,1 gk+1 = 1
and hence Sol(E) 6= ∅.
Suppose now that Sol(E) 6= ∅. Then there is a valuation ν with ν(Ej ) = 1 and ν(xi,j ) =
ν(xi,j ′ ) for i ∈ [1, k] and j, j ′ ∈ [1, m]. We shall prove that we can extend ν so as to satisfy
the conditions of Lemma 6.4.
The left-hand equation in Eq. (5) is fulfilled already. Since ν(xi,j ) = ν(xi,j ′ ), setting
ν(zi ) = ν(xi,1 ) will satisfy the right-hand equation of Eq. (5). Finally, observe that by
assigning suitable values to the variables yj,s,b for j ∈ [1, m], s ∈ [1, ℓ], and b ∈ {0, 1}, we
can enforce any value from {1}×Zℓ for ν(Mj ). Therefore, we can extend ν so that it satisfies
Eq. (6) as well.

This completes the proof of Proposition 6.2, which allows us to prove Theorem 5.3.
Proof of Theorem 5.3. By Proposition 6.2, there are ℓ, m ∈ N such that the knapsack problem is undecidable for Gm ≀(H3 (Z)×Zℓ ). According to Lemma 4.1, the group Gm ≀(H3 (Z)×Zℓ )
is a subgroup of G≀(H3 (Z)×Zℓ+1 ), meaning that the latter also has an undecidable knapsack
problem.

7. Decidability: Proof of Theorem 5.4 and Theorem 5.5
Let us fix a wreath product G ≀ H. Recall the projection homomorphisms σ = σG≀H : G ≀
H → H and τ = τG≀H : G≀H → G(H) from (1). For g ∈ G≀H we write supp(g) for supp(τ (g)).
A knapsack expression E = h0 g1x1 h1 · · · gkxk hk over G ≀ H is called torsion-free if for each
i ∈ [1, k], either σ(gi ) = 1 or σ(gi ) has infinite order. A map ϕ : Na → Nb is called affine if
there is a matrix A ∈ Nb×a and a vector µ ∈ Nb such that ϕ(ν) = Aν + µ for every ν ∈ Na .
Proposition 7.1. Let knapsack be decidable for H. For every knapsack expression E over
G ≀ H, one can S
construct torsion-free expressions E1 , . . . , Er and affine maps ϕ1 , . . . , ϕr such
r
that Sol(E) = i=1 ϕi (Sol(Ei )).

Proof. First of all, note that since knapsack is decidable for H, we can decide for which
i the element σ(gi ) ∈ H has finite or infinite order. For a knapsack expression F =
h0 g1x1 h1 · · · gkxk hk , let t(F ) be the set of indices of i ∈ [1, k] such that σ(gi ) 6= 1 and σ(gi ) has
finite order. We show that if |t(E)| > 0, then one can construct expressions E0 , . . . , Er−1
Sr−1
and affine maps ϕ0 , . . . , ϕr−1 such that |t(Ej )| < |t(E)| and Sol(E) = j=0 ϕj (Sol(Ej )).
This suffices, since the composition of affine maps is again an affine map.
Suppose E = h0 g1x1 h1 · · · gkxk hk and σ(gi ) 6= 1 has finite order r. Note that we can
compute r. For every j ∈ [0, r − 1], let
x

x

i+1
i−1
hi+1 · · · gkxk hk .
Ej = h0 g1x1 h1 · · · gi−1
hi−1 (gir )xi (gij hi )gi+1

Let X = {x1 , . . . , xr }. Moreover, let ϕ : NX → NX be the affine map such that for ν ∈
NX , we have ϕj (ν)(xℓ ) = ν(xℓ ) for ℓ 6= i and ϕj (ν)(xi ) = r · ν(xi ) + j. Note that then

10

M. GANARDI, D. KÖNIG, M. LOHREY, AND G. ZETZSCHE

σ(gir ) = σ(gi )r = 1 and thus t(Ej ) = t(E) \ {i}. Furthermore, we clearly have Sol(E) =
Sr−1

j=0 ϕj (Sol(Ej )).

Since the image of a semilinear set under an affine map is again semilinear, Proposition 7.1
tells us that it suffices to prove Theorems 5.4 and 5.5 for torsion-free knapsack expressions.
For the rest of this section let us fix a torsion-free knapsack expression E over G ≀ H. We
can assume that E = g1x1 g2x2 · · · gkxk gk+1 (note that if g has infinite order than also c−1 gc
has infinite order). We partition the set VE = {x1 , . . . , xk } of variables in E as VE = S ⊎ M ,
where S = {xi ∈ VE | σ(gi ) = 1} and M = {xi ∈ VE | ord(σ(gi )) = ∞}. In this situation,
the following notation will be useful. If U = A ⊎ B for a set of variables U ⊆ V and µ ∈ NA
and κ ∈ NB , then we write µ ⊕ κ ∈ NU for the valuation with (µ ⊕ κ)(x) = µ(x) for x ∈ A
and (µ ⊕ κ)(x) = κ(x) for x ∈ B.
Computing powers. A key observation in our proof is that in order to compute the group
element τ (g m )(h) (in the cursor intuition, this is the element labelling the point h ∈ H in the
wreath product element g m ) for h ∈ H and g ∈ G ≀ H, where σ(g) has infinite order, one only
has to perform at most |supp(g)| many multiplications in G, yielding a bound independent
of m. Let us make this precise. Suppose h ∈ H has infinite order. For h′ , h′′ ∈ H, we
write h′ 4h h′′ if there is an n ≥ 0 with h′ = hn h′′ . Then, 4h is transitive. Moreover,
since h has infinite order, 4h is also anti-symmetric and thus a partial order. Observe that
if knapsack is decidable for H, given h, h′ , h′′ ∈ H, we can decide whether h has infinite
order and whether h′ 4h h′′ . It turns out that for g ∈ G ≀ H, the order 4σ(g) tells us how
to evaluate the mapping τ (g m ) at a certain element of H. Before we make this precise, we
need some notation.
We will sometimes want to multiply all elements ai for i ∈ I such that the order in which
we multiply is specified by some linear order on I. If (I, ≤) is a finite linearly ordered set
Q≤
Qn
with I = {i1 , . . . , in }, i1 < i2 < . . . < in , then we write i∈I ai for j=1 aij . If the order ≤
Q
is clear from the context, we just write i∈I ai .
Lemma 7.2. Let g ∈ G ≀ H such that ord(σ(g)) = ∞ and let h ∈ H, m ∈ N. Moreover let
F = supp(g) ∩ {σ(g)−i h | i ∈ [0, m − 1]}. Then F is linearly ordered by 4σ(g) and
Y4σ(g)
τ (g)(h′ ).
τ (g m )(h) =
h′ ∈F

Proof. By definition of G≀H, we have τ (g1 g2 )(h) = τ (g1 )(h)·τ (g2 )(σ(g1 )−1 h). By induction,
this implies
n
m−1
Y
Y
−i
m
τ (g)(σ(g)−ij h),
τ (g)(σ(g) h) =
τ (g )(h) =
i=0

j=1

where {i1 , . . . , in } = {i ∈ [0, m − 1] | σ(g)−i h ∈ supp(g)} with i1 < · · · < in . Note
that then F = {σ(g)−ij h | j ∈ [1, n]}. Since σ(g)−ij h = σ(g)ij+1 −ij σ(g)−ij+1 h, we have

σ(g)−i1 h 4σ(g) · · · 4σ(g) σ(g)−in h.
Lemma 7.3. Let g ∈ G ≀ H with σ(g) = 1 and h ∈ H. Then τ (g m )(h) = (τ (g)(h))m .

Proof. Recall that for g1 , g2 ∈ G ≀ H, we have τ (g1 g2 )(f ) = τ (g1 )(h) · τ (g2 )(σ(g1 )−1 h).
Qm−1

Therefore, if σ(g) = 1, then τ (g m )(h) = i=0 τ (g)(σ(g)−i h) = (τ (g)(h))m .
Addresses. A central concept in our proof is that of an address. Intuitively, a solution
to the equation E = 1 can be thought of as a sequence of instructions on how to walk
through the Cayley graph of H and place elements of G at those nodes. Here, being a
solution means that in the end, all the nodes contain the identity of G. In order to express
that every node carries 1 in the end, we want to talk about at which points in the product
E = g1x1 g2x2 · · · gkxk gk+1 a particular node is visited. An address is a datum that contains just

KNAPSACK PROBLEMS FOR WREATH PRODUCTS

11

enough information about such a point to determine which element of G has been placed
during that visit.
A pair (i, h) with i ∈ [1, k + 1], and h ∈ H is called an address if h ∈ supp(gi ). The set
of addresses of the expression E is denoted by A. Note that A is finite and computable. To
each address (i, h), we associate the group element γ(i, h) = gi of the expression E.
A linear order on addresses. We will see that if a node is visited more than once, then
(i) each time2 it does so at a different address and (ii) the order of these visits only depends
on the addresses. To S
capture the order of these visits, we define a linear order on addresses.
We partition A = i∈[1,k+1] Ai , where Ai = {(i, h) | h ∈ supp(gi )} for i ∈ [1, k + 1]. Then,
for a ∈ Ai and a′ ∈ Aj , we let a < a′ if and only if i < j. It remains to order addresses
within each Ai . Within Ak+1 , we pick an arbitrary order. If i ∈ [1, k] and σ(gi ) = 1, we also
order Ai arbitrarily. Finally, if i ∈ [1, k] and σ(gi ) has infinite order, then we pick a linear
order ≤ on Ai so that for h, h′ ∈ supp(gi ), h 4σ(gi ) h′ implies (i, h) ≤ (i, h′ ). Note that this
is possible since 4σ(gi ) is a partial order on H.
Cancelling profiles. In order to express that a solution for E yields the identity at every
node of the Cayley graph of H, we need to compute the element of G that is placed after
the various visits at a particular node. We therefore, associate to each address an expression
over G that yields the element placed during a visit at this address a ∈ A. In analogy
to τ (g) for g ∈ G ≀ H, we denote this expression by τ (a). If a = (k + 1, h), then we set
τ (a) = τ (gk+1 )(h). Now, let a = (i, h) for i ∈ [1, k]. If σ(gi ) = 1, then τ (a) = τ (gi )(h)xi .
Finally, if σ(gi ) has infinite order, then τ (a) = τ (gi )(h).
This allows us to express the element of G that is placed at a node h ∈ H if h has
been visited withQa particular set of addresses. To each subset C ⊆ A, we assign the
expression EC = a∈C τ (a), where the order of multiplication is given by the linear order
on A. Observe that only variables in S ⊆ {x1 , . . . , xk } occur in EC . Therefore, given κ ∈ NS ,
we can evaluate κ(EC ) ∈ G. We say that C ⊆ A is κ-cancelling if κ(EC ) = 1.
In order to record which sets of addresses can cancel simultaneously (meaning: for the
same valuation), we use profiles. A profile is a subset of P(A) (the power set of A). A profile
P ⊆ P(A) is said to be κ-cancelling if every C ∈ P is κ-cancelling. A profile is cancelling if
it is κ-cancelling for some κ ∈ NS .
Clusters. We also need to express that there is a node h ∈ H that is visited with a particular
set of addresses. To this end, we associate to each address a ∈ A another expression σ(a).
As opposed to τ (a), the expression σ(a) is over H and variables M ′ = M ∪ {yi | xi ∈ M }.
Let a = (i, h) ∈ A. When we define σ(a), we will also include factors σ(gj )xj and σ(gj )yj
where σ(gj ) = 1. However, since these factors do not affect the evaluation of the expression,
this should be interpreted as leaving out such factors.
(1) If i = k + 1 then σ(a) = σ(g1 )x1 · · · σ(gk )xk h.
(2) If i ∈ [1, k] then σ(a) = σ(g1 )x1 · · · σ(gi−1 )xi−1 σ(gi )yi h.
ν(x )

ν(x )

We now want to express that when multiplying g1 1 · · · gk k gk+1 , there is a node h ∈ H
such that the set of addresses with which one visits h is precisely C ⊆ A. In this case, we
will call C a cluster.
′
Let µ ∈ NM and µ′ ∈ NM . We write µ′ ⊏ µ if µ′ (xi ) = µ(xi ) for xi ∈ M and
µ′ (yi ) ∈ [0, µ(xi ) − 1] for every yi ∈ M ′ . We can now define the set of addresses at which
one visits h ∈ H: For h ∈ H, let
′

Aµ,h = {a ∈ A | µ′ (σ(a)) = h for some µ′ ∈ NM with µ′ ⊏ µ}.
A subset C ⊆ A is called a µ-cluster if C 6= ∅ and there is an h ∈ H such that C = Aµ,h .
2Here, we count two visits inside the same factor g , i ∈ [1, k], with σ(g ) = 1 as one visit.
i
i

12

M. GANARDI, D. KÖNIG, M. LOHREY, AND G. ZETZSCHE

Lemma 7.4. Let ν ∈ NVE with ν = µ ⊕ κ for µ ∈ NM and κ ∈ NS . Moreover, let h ∈ H
and C = Aµ,h . Then τ (ν(E))(h) = κ(EC ).
Proof. Recall that for k1 , k2 ∈ G≀H and h ∈ H, we have τ (k1 k2 )(h) = τ (k1 )(h)·τ (σ(k1 )−1 h).
Therefore, we can calculate τ (ν(E))(h) as
τ (ν(E))(h) =

k


Y


ν(x )
τ gi i
σ(pi−1 )−1 h · τ (gk+1 ) σ(pk )−1 h ,

i=1
ν(x )
g1 1

where pi =
on A, we have
κ(EC ) =

Y

a∈C

ν(x )
· · · gi i

κ(τ (a)) =

for i ∈ [0, k]. On the other hand, by definition of the linear order

Y

!

κ(τ (a)) · · ·

a∈C∩A1

Therefore, it suffices to show that



ν(x )
σ(pi−1 )−1 h =
τ gi i
(11)
(12)


τ (gk+1 ) σ(pk )−1 h =

Y

a∈C∩Ak

Y

!
κ(τ (a)) 

Y

a∈C∩Ak+1



κ(τ (a)) .

κ(τ (a))

a∈C∩Ai

Y

κ(τ (a)),

a∈C∩Ak+1

for i ∈ [1, k].
We begin with Eq. (12). Note that by definition of C = Aµ,h , if a ∈ C ∩ Ak+1 =
′
Aµ,h ∩ Ak+1 with a = (k + 1, t), then there is a µ′ ∈ NM with µ′ ⊏ µ such that µ′ (σ(a)) = h.
Moreover, since a ∈ Ak+1 , σ(a) contains only variables in M and thus µ′ (σ(a)) = µ(σ(a)) =
ν(σ(a)). Note that then
h = µ′ (σ(a)) = ν(σ(a)) = ν(σ(g1 )x1 · · · σ(gk )xk t) = σ(pk )t,
meaning that there is only one such t, namely t = σ(pk )−1 h. Moreover, recall that if
a = (k + 1, t), then τ (a) = τ (gk+1 )(t) ∈ G. Therefore, the right-hand side of Eq. (12) is

κ(τ (a)) = τ (gk+1 )(t) = τ (gk+1 ) σ(pk )−1 h ,

which is the left-hand side of Eq. (12).
It remains to verify Eq. (11). Let us analyze the addresses in C ∩Ai for i ∈ [1, k]. Consider
a ∈ C ∩ Ai = Aµ,h ∩ Ai with a = (i, t). Since a ∈ Aµ,h , there is a µ′ ⊏ µ with µ′ (σ(a)) = h.
Since i ∈ [1, k] we have
(13) h = µ′ (σ(a)) = µ′ (σ(g1 )x1 · · · σ(gi−1 )xi−1 σ(gi )yi t)
′

′

= σ(g1 )ν(x1 ) · · · σ(gi−1 )ν(xi−1 ) σ(gi )µ (yi ) t = σ(pi−1 )σ(gi )µ (yi ) t.
′

Here again, if σ(gj ) = 1, we mean that the factor σ(gj )ν(xj ) (resp., σ(gi )µ (yi ) ) does not
appear. We now distinguish two cases.
Case 1. σ(gi ) = 1. In this case, Eq. (13) tells us that h = σ(pi−1 )t, i.e., t = σ(pi−1 )−1 h.
Thus, C ∩ Ai = {(i, σ(pi−1 )−1 h)}. Moreover, since σ(gi ) = 1, τ (a) is defined as (τ (gi )(t))xi .
Therefore, the right-hand side of Eq. (11) reads



ν(x )
ν(x )
(τ (gi )(t))κ(xi ) = (τ (gi )(t))ν(xi ) = (τ (gi i ))(t) = τ gi i
σ(pi−1 )−1 h ,
where the second equality is due to Lemma 7.3. This is precisely the left-hand side of
Eq. (11).

Case 2. σ(gi ) has infinite order. Let
F = supp(gi ) ∩ {σ(gi )−j σ(pi−1 )−1 h | j ∈ [0, ν(xi ) − 1]}.

KNAPSACK PROBLEMS FOR WREATH PRODUCTS

13

We claim that t ∈ F if and only if (i, t) ∈ C. If (i, t) ∈ C then Equation (13) directly
implies that t ∈ F . Conversely, assume that t ∈ F and let t = σ(gi )−j σ(pi−1 )−1 h for
j ∈ [0, ν(xi ) − 1]. Then, according to Eq. (13), setting µ′ (yi ) := j guarantees µ′ (σ(a)) = h
for a = (i, t), i.e., (i, t) ∈ C.
Observe that F is linearly ordered by 4σ(gi ) : If j < j ′ , then
σ(gi )−j σ(pi−1 )−1 h = σ(gi )j

′

−j

′

σ(gi )−j σ(pi−1 )−1 h.

Therefore, we can compute the right-hand side of Eq. (11) as
Y4σ(gi )
Y
Y
τ (gi )(t).
τ (a) =
κ(τ (a)) =
a∈C∩Ai

a∈C∩Ai

t∈F

According to Lemma 7.2, this equals the left-hand side of Eq. (11).
VE

M


S

Proposition 7.5. Let ν ∈ N with ν = µ ⊕ κ for µ ∈ N and κ ∈ N . Then ν(E) = 1
if and only if σ(ν(E)) = 1 and there is a κ-cancelling profile P such that every µ-cluster is
contained in P .
Proof. Note that ν(E) = 1 if and only if τ (ν(E)) = 1 and σ(ν(E)) = 1. Therefore, we show
that τ (ν(E)) = 1 if and only if there is a κ-cancelling profile P such that every µ-cluster is
contained in P .
First, let suppose that there is a κ-cancelling profile P such that every µ-cluster is contained in P . We need to show that then τ (ν(E)) = 1, meaning τ (ν(E))(h) = 1 for every
h ∈ H. Consider the set C = Aµ,h . If C = ∅, then by definition, we have EC = 1. Thus,
κ(EC ) = 1, which by Lemma 7.4 implies τ (ν(E))(h) = 1. If C 6= ∅, then C is a µ-cluster
and hence κ-cancelling. Therefore, by Lemma 7.4, τ (ν(E))(h) = κ(EC ) = 1. This shows
that τ (ν(E)) = 1.
Now suppose τ (ν(E)) = 1 and let P ⊆ P(A) be the profile consisting of all sets Aµ,h with
h ∈ H. Then P is κ-cancelling, because if C ∈ P with C = Aµ,h , then by Lemma 7.4, we
have κ(EC ) = τ (ν(E))(h) = 1.

Lemma 7.6. Suppose KP(G∗ ) is decidable. Given an instance of knapsack for G ≀ H, we
can compute the set of cancelling profiles. If G is knapsack-semilinear, then for each profile
P , the set of κ such that P is κ-cancelling is semilinear.
Proof. A profile P ⊆ P(A) is κ-cancelling if and only if κ(EC ) = 1 for every C ∈ P .
Together, the expressions EC for C ∈ P constitute an instance of ExpEq(G) (and according
to Proposition 3.1, ExpEq(G) is decidable if KP(G∗ ) is decidable) and this instance is
solvable if and only if P is cancelling. This proves the first statement of the lemma. The
second
statement holds because the set of κ ∈ NS such that P is κ-cancelling is precisely
T
C∈P Sol(EC ) and because the class of semilinear sets is closed under Boolean operations.

Let LP ⊆ NM be the set of all µ ∈ NM such that every µ-cluster belongs to P .

Lemma 7.7. Let H be knapsack-semilinear. For every profile P ⊆ P(A), the set LP is
effectively semilinear.
Proof. We claim that the fact that every µ-cluster belongs to P can be expressed in Presburger arithmetic. This implies the lemma.
In addition to the variables in M ′ , we will use the variables in M ′ = {x | x ∈ M ′ }. For a
z1 −1
−1 −1 zm
knapsack expression F = r0 sz11 r1 · · · szmm rm with variables in M ′ , let F −1 = rm
(sm ) · · · r1−1 (s−1
1 ) r0 .
′
′
Moreover, let F = r0 s1z1 r1 · · · szmm rm . For µ ∈ NM , the valuation µ ∈ NM is defined as
′
′
M′
µ(x) = µ(x) for all x ∈ M . Furthermore, for µ ∈ N , we define the valuation µ ∈ NM by
′
′
µ(x) = µ(x) for x ∈ M ′ . Thus if µ ∈ NM or µ ∈ NM , then µ = µ.
As a first step, for each pair a, b ∈ A, we construct a Presburger formula ηa,b with free
′
′
variables M ′ ∪ M ′ such that for µa ∈ NM and µb ∈ NM , we have µa ⊕ µb |= ηa,b if and

14

M. GANARDI, D. KÖNIG, M. LOHREY, AND G. ZETZSCHE

only if µa (σ(a)) = µb (σ(b)). This is possible because µa (σ(a)) = µb (σ(b)) is equivalent to
(µa ⊕ µb )(σ(a)σ(b)−1 ) = 1 and the solution set of the knapsack expression σ(a)σ(b)−1 is
effectively semilinear by assumption.
Next, for each non-empty subset C ⊆ A, we construct a formula γC with free variables
in M ′ such that µ |= γC if and only if C is a µ-cluster. Since C 6= ∅, we can pick a fixed
a ∈ C and let γC express the following:

^
′
′
∃µ′ ∈ NM : µ′ ⊏ µ ∧
∃µ′′ ∈ NM : µ′′ ⊏ µ ∧ µ′ (σ(a)) = µ′′ (σ(b))
b∈C

(14)

∧

^ 

b∈A\C
′


′
∀µ′′ ∈ NM : µ′′ ⊏ µ → ¬ µ′ (σ(a)) = µ′′ (σ(b)) .

µ′′

Observe that µ ⊏ µ and
⊏ µ are easily expressible in Presburger arithmetic.
Let us show that in fact µ |= γC if and only if C is a µ-cluster. Consider some C ⊆ A and
′
let a ∈ C be the element picked to define γC . If µ |= γC , then there is a µ′ ∈ NM with the
′
properties stated in Eq. (14). We claim that with h := µ (σ(a)), we have C = Aµ,h . The
′
second of the three conjuncts in Eq. (14) states that for every b ∈ C there is a µ′′ ∈ NM
such that µ′′ ⊏ µ and µ′′ (σ(b)) = µ′ (σ(a)) = h. Thus, b ∈ Aµ,h , proving C ⊆ Aµ,h . The
third conjunct states that the opposite is true for every b ∈ A \ C, so that b ∈
/ Aµ,h for all
b ∈ A \ C. In other words, we have Aµ,h ⊆ C and thus Aµ,h = C.
Conversely, suppose C 6= ∅ and C = Aµ,h . Let a ∈ C be the element chosen to define γC .
Since a ∈ Aµ,h , there is a µ′ ⊏ µ with h = µ′ (σ(a)). Moreover, for every b ∈ C, there is a
µ′′ ⊏ µ with µ′′ (σ(b)) = h = µ′ (σ(a)). Hence, the second conjunct is satsfied. Furthermore,
for every b ∈ A\Aµ,h , there is no µ′′ ⊏ µ with µ′′ (σ(b)) = h, meaning that the third conjunct
is satisfied as well. Hence, C = Aµ,h and thus we have µ |= γC if and only if C is a µ-cluster.
Finally, we getVa formula with free variables M that expresses that every µ-cluster belongs
to P by writing C∈P(A)\P, C6=∅ ¬γC .


We are now ready to prove Theorems 5.4 and 5.5. Let H be knapsack-semilinear and let
KP(G∗ ) be decidable. For each profile P ⊆ P(A), let KP ⊆ NS be the set of all κ ∈ NS
such that P is κ-cancelling.
Observe that for ν = µ⊕κ, where µ ∈ NM and κ ∈ NS , the value of σ(ν(E)) only depends
on µ. Moreover, the set T ⊆ NM of all µ such that σ(ν(E)) = 1 is effectively
semilinear
S
because H is knapsack-semilinear. Proposition 7.5 tells us that Sol(E) = P ⊆P(A) KP ⊕
(LP ∩ T ) and Lemma 7.7 states that LP is effectively semilinear. This implies Theorem 5.4:
We can decide solvability of E by checking, for each of the finitely many profiles P , whether
KP 6= ∅ (which is decidable by Lemma 7.6) and whether LP ∩ T 6= ∅. Moreover, if G is
knapsack-semilinear, then Lemma 7.6 tells us that KP and thus Sol(E) is semilinear as well.
This proves Theorem 5.5.
8. Complexity: Proof of Theorem 5.7
Throughout the section we fix a finitely generated group G. The goal of this section is to
show that if G is abelian and non-trivial, then KP(G ≀ Z) is NP-complete.
8.1. Periodic words over groups. In this section we define a countable subgroup of Gω
(the direct product of ℵ0 many copies of G) that consists of all periodic sequences over
G. We show that the membership problem for certain subgroups of this group can be
solved in polynomial time if G is abelian. We believe that this is a result of independent
interest which might have other applications. Therefore, we prove the best possible complexity bound, which is TC0 .3 This is the class of all problems that can be solved with
uniform threshold circuits of polynomial size and constant depth. Here, uniformity means
3Alternatively, the reader can always replace TC0 by polynomial time in the further arguments.

KNAPSACK PROBLEMS FOR WREATH PRODUCTS

15

DLOGTIME-uniformity, see e.g. [10] for more details. Complete problems for TC0 are multiplication and division of binary encoded integers (or, more precisely, the question whether
a certain bit in the output number is 1) [10]. TC0 -complete problems in the context of
group theory are the word problem for any infinite finitely generated solvable linear group
[13], the subgroup membership problem for finitely generated nilpotent groups [25], the conjugacy problem for free solvable groups and wreath products of abelian groups [21], and the
knapsack problem for finitely generated abelian groups [19].
With G+ we denote the set of all tuples (g0 , . . . , gq−1 ) over G of arbitrary length q ≥ 1.
With Gω we denote the set of all mappings f : N → G. Elements of Gω can be seen as
infinite sequences (or words) over the set G. We define the binary operation ◦ on Gω by
pointwise multiplication: (f ◦ g)(n) = f (n)g(n). In fact, Gω together with the multiplication
◦ is the direct product of ℵ0 many copies of G. The identity element is the mapping id with
id(n) = 1 for all n ∈P
N. For f1 , f2 , . . . , fn ∈ Gω we write ni=1 fi for f1 ◦ f2 ◦ · · · ◦ fn . If G
n
is abelian, we write i=1 fi for ni=1 fi . A function f ∈ Gω is periodic with period q ≥ 1 if
f (k) = f (k + q) for all k ≥ 0. Note that in this situation, f might also be periodic with a
smaller period q ′ < q. Of course, a periodic function f with period q can be specified by the
tuple (f (0), . . . , f (q − 1)). Vice versa, a tuple u = (g0 , . . . , gq−1 ) ∈ G+ defines the periodic
function fu ∈ Gω with
fu (n · q + r) = gr for n ≥ 0 and 0 ≤ r < q.
One can view this mapping as the sequence uω obtained by taking infinitely many repetitions
of u. Let Gρ be the set of all periodic functions from Gω . If f1 is periodic with period q1 and
f2 is periodic with period q2 , then f1 ◦ f2 is periodic with period q1 q2 (in fact, lcm(q1 , q2 )).
Hence, Gρ forms a countable subgroup of Gω . Note that Gρ is not finitely generated: The
subgroup generated by elements fi ∈ Gρ with period qi (1 ≤ i ≤ n) contains only functions
with period lcm(q1 , . . . , qn ). Nevertheless, using the representation of periodic functions by
elements of G+ we can define the word problem for Gρ , WP(Gρ ) for short:
Input: Tuples u1 , . . . , un ∈ G+ (elements of G are represented by finite words over Σ).
Question: Does ni=1 fui = id hold?
For n ≥ 0 we define the subgroup Gρn of all f ∈ Gρ with f (k) = 1 for all 0 ≤ k ≤ n − 1.
We also consider the uniform membership problem for subgroups Gρn , Membership(Gρ∗ ) for
short:
Input: Tuples u1 , . . . , un ∈ G+ (elements of G are represented by finite words over Σ) and
a binary encoded number m.
Question: Does ni=1 fui belong to Gρm ?
Lemma 8.1. WP(Gρ ) is TC0 -reducible to Membership(Gρ∗ )
Proof. Let u1 , . . . , un ∈ G+ and let qi be the length of ui . Let m = lcm(q1 , . . . , qn ). We

have ni=1 fui = id if and only ni=1 fui belongs to Gρm .
Theorem 8.2. For every finitely generated abelian group G, Membership(Gρ∗ ) belongs to
TC0 .
Proof. Since the word problem for a finitely generated abelian group belongs to TC0 , it
suffices to show the following claim:
Pn
Claim: Let u1 , . . . , un ∈ G+ and let qi be the length of ui . Let f = Pi=1 fui . If there
n
exists a position m such that f (m) 6= 0, then there exists a position m < i=1 qi such that
f (m) 6= 0.
Pn
Pn
Let m ≥ i=1 qi . We show that if f (j) = 0 for all j with m − i=1 qi ≤ j < m, then also
f (m) = 0, which proves the above claim.
Pn
Hence, let us assume that f (j) = 0 for all j with m − i=1 qi ≤ j < m. Note
P that
fui (j) = fui (j − qi ) for all j ≥ qi and 1 ≤ i ≤ n. For M ⊆ [1, n] let qM =
i∈M qi .

16

M. GANARDI, D. KÖNIG, M. LOHREY, AND G. ZETZSCHE

Moreover, for 1 ≤ k ≤ n let Mk = {M ⊆ [1, n], |M | = k}. For all 1 ≤ k ≤ n − 1 we get
X X
X
X
fui (m − qM ) = −
fui (m − qM )
M∈Mk i∈M

M∈Mk i∈[1,n]\M

=

X

−

X

fui (m − qM − qi )

M∈Mk i∈[1,n]\M

=

=

−

−

n
X

X

fui (m − qM∪{i} )

i=1 M∈Mk ,i∈M
/
n
X
X

fui (m − qM )

i=1 M∈Mk+1 ,i∈M

=

X

−

X

fui (m − qM ).

M∈Mk+1 i∈M

We can write
f (m) =

n
X
i=1

fui (m) =

n
X

X X

fui (m − qi ) =

i=1

fui (m − qM ).

M∈M1 i∈M

From the above identities we get by induction:
X X
f (m) = (−1)n+1
fui (m − qM )
M∈Mn i∈M

n+1

= (−1)

X

fui (m − q[1,n] )

i∈[1,n]

= (−1)n+1 f (m −

n
X

qi ) = 0.

i=1

This proves the claim and hence the theorem.



8.2. Automata for Cayley representations. The goal of this section is to show that if
ExpEq(G) and Membership(Gρ∗ ) both belong to NP, then also KP(G ≀ Z) belongs to NP.
An interval [a, b] ⊆ Z supports an element (f, d) ∈ G ≀ Z if {0, d} ∪ supp(f ) ⊆ [a, b]. If
(f, d) ∈ G ≀ Z is a product of length n over the generators, then the minimal interval [a, b]
which supports (f, d) satisfies b − a ≤ n. A knapsack expression E = v0 ux1 1 v1 · · · uxk k vk is
called rigid if each ui evaluates to an element (fi , 0) ∈ G ≀ Z. Intuitively, the movement of
the cursor is independent from the values of the variables xi up to repetition of loops. In
particular, every variable-free expression is rigid.
In the following we define so called Cayley representations of rigid knapsack expressions.
This is a finite word, where every symbol is a marked knapsack expression over G. A marked
knapsack expression over G is of the form E, E, E, or E, where E is a knapsack expression
over G. We say that E and E (resp., E and E) are top-marked (resp., bottom-marked).
Let E = v0 ux1 1 v1 · · · uxk k vk be a rigid knapsack expression over G ≀ Z. For an assignment
ν let (fν , d) ∈ G ≀ Z be the element to which ν(E) evaluates, i.e. (fν , d) = ν(E). Note that
d does not depend on ν. Because of the rigidity of E, there is an interval [a, b] ⊆ Z that
supports (fν , d) for all assignments ν. For each j ∈ [a, b] let Ej be a knapsack expression
over G with the variables x1 , . . . , xk such that fν (j) = ν(Ej ) for all assignments ν. Then
we call the formal expression


Ea Ea+1 · · · E−1 E0 E1 · · · Ed−1 Ed Ed+1 · · · Eb if d > 0
r = Ea Ea+1 · · · E−1 E0 E1 · · · Eb
if d = 0 .


Ea Ea+1 · · · Ed−1 Ed Ed+1 · · · E−1 E0 E1 · · · Eb if d < 0

KNAPSACK PROBLEMS FOR WREATH PRODUCTS

-1
ax

0
ax
1
b

ax

ax b

1
bx
1
by
a

bx by a

2

3

by
b−1
b

by
a
a

by

b y a2

17

4

5

6

7

8

9

10

11

12

a
b−1
b

a
a

a
b−1
b

a
a

a

a2

a
b−1
b
a

a
a
a2

a
b−1
ab−1

a
a

a
a

a

a2

Figure 1. Cayley representation
a Cayley representation of E (or E is represented by r). Formally, a Cayley representation is
a sequence of marked knapsack expressions. For a Cayley representation r, we denote by |r|
the number of knapsack expressions in the sequence. If necessary, we separate consecutive
marked knapsack expressions in r by commas. For instance, if a1 and a2 are generators of
G, then a1 , a2 a1 , a2 is a Cayley representation of length 3, whereas a1 , a2 , a1 , a2 is a Cayley
representation of length 4. By this definition, r depends on the chosen supporting interval
[a, b]. However, compared to the representation of the minimal supporting interval, any
other Cayley representation differs only by adding 1’s (i.e., trivial knapsack expressions over
G) at the left and right end of r.
A Cayley representation of E records for each point in Z an expression that describes
which element will be placed at that point. Multiplying an element of G ≀ Z always begins
at a particular cursor position; in a Cayley representation, the marker on top specifies
the expression that is placed at the cursor position in the beginning. Moreover, a Cayley
representation describes how the cursor changes when multiplying ν(E): The marker on the
bottom specifies where the cursor is located in the end.
Example 8.3. Let us consider the wreath product F2 ≀Z where F2 is the free group generated
by {a, b} and Z is generated by t. Consider the rigid knapsack expression E = ux1 u2 uy3 u54
where
• u1 = at−1 at2 bt−1 , represented by a a b,
• u2 = t, represented by 1 1,
• u3 = btbtbt−2 , represented by b b b,
• u4 = at−1 bt2 b−1 tatat−1 , represented by b a b−1 a a.
A Cayley representation of ux1 is ax ax b−1 and a Cayley representation of uy3 is by by by . The
diagram in Fig. 1 illustrates how to compute a Cayley representation r of E, which is shown
in the bottom line. Here, we have chosen the supporting interval minimal. Note that if
we replace the exponents 5 in u54 by a larger number, then we only increase the number of
repetitions of the factor a, a2 in the Cayley representation.
Example 8.3 also illustrates the concept of so called consistent tuples, which will be
used later. A tuple (γ1 , . . . , γn ), where every γi is a marked knapsack expression over G
is consistent if, whenever γi is bottom-marked and i < n, then γi+1 is top-marked. Every
column in Fig. 1 is a consistent tuple.
Let E be an arbitrary knapsack expression over G ≀ Z. We can assume that E has the
form ux1 1 · · · uxk k uk+1 . We partition the set of variables X = {x1 , . . . , xk } as X = X0 ∪ X1 ,
where X0 contains all variables xi where ui evaluates to an element (f, 0) ∈ G ≀ Z, and
X1 contains all other variables. For a partial assignment ν : X1 → N we obtain a rigid
knapsack expression Eν by replacing in E every variable xi ∈ X1 by ν(xi ). A set R of
Cayley representations is a set representation of E if
• for each assignment ν : X1 → N there exists r ∈ R such that r represents Eν ,

18

M. GANARDI, D. KÖNIG, M. LOHREY, AND G. ZETZSCHE

• for each r ∈ R there exists an assignment ν : X1 → N such that r represents Eν and
ν(x) ≤ |r| for all x ∈ X1 .
Example 8.4. Let us consider again the wreath product F2 ≀ Z and consider the (nonrigid) knapsack expression E ′ = ux1 u2 uy3 uz4 where u1 , u2 , u3 , u4 are taken from Example 8.3.
We have X0 = {x, y} and X1 = {z}. For z = 5 we obtained in Example 8.3 the Cayley
representation
ax , ax b, bx by a, by , by a2 , a, a2 , a, a2 , a, a2 , ab−1 , a, a.
A set representation R of E ′ consists of the following Cayley representations:
• ax , ax , bx by , by , by for ν(z) = 0,
• ax , ax b, bx by a, by b−1 , by a, a for ν(z) = 1,
• ax , ax b, bx by a, by , by a2 , a, a2 , . . . , a, a2 , ab−1 , a, a for ν(z) ≥ 2.
{z
}
|
ν(z) − 2 times

Only finitely many different marked knapsack expressions appear in this set representation
R, and R is clearly a regular language over the finite alphabet consisting of this finitely
many marked knapsack expressions.

In the following, we will show that for every knapsack expression E = ux1 1 · · · uxk k uk+1
there exists a non-deterministic finite automaton (NFA) that accepts a set representation of
E, whose size is exponential in n = |E|. First, we consider the blocks ux1 1 , . . . , uxk k , uk+1 .
Lemma 8.5. One can compute in polynomial time for each 1 ≤ i ≤ k + 1 an NFA Ai of
size |ui |O(1) that recognizes a set representation of uxi i or uk+1 .
Proof. Let us do a case distinction.
Case 1. Consider an expression uxi i where xi ∈ X0 , i.e. ui evaluates to some element
(f, 0) ∈ G ≀ Z. Let [a, b] be the minimal interval which supports (f, 0). Thus, b − a ≤ |ui |.
Then
ri = f (a)xi · · · f (−1)xi f (0)xi f (1)xi · · · f (b)xi
is a Cayley representation of uxi i where |ri | = b − a + 1 ≤ |ui | + 1. Clearly, {ri } is a set
representation of uxi i , which is recognized by an NFA Ai of size |ri | + 1 ≤ |ui | + 2.
Case 2. Similarly, for the word uk+1 we obtain a Cayley representation rk+1 as above except
that the exponents xi are not present. Again, {rk+1 } is a set representation of uk+1 , which
is recognized by an NFA Ak+1 of size |uk+1 | + 2.
Case 3. Consider an expression uxi i where xi ∈ X1 , i.e., ui evaluates to some element
(f, d) ∈ G ≀ Z where d 6= 0. Let [a, b] be a minimal interval which supports (f, d), hence
b − a ≤ |ui |.
We only consider the case d > 0; at the end we say how to modify the construction for
d < 0. Consider the word
ri = f (a) · · · f (−1)f (0) · · · f (d)f (1) · · · f (b),
which is a Cayley representation of (f, d). We will prove that there is an NFA Ai with εtransitions of size O(|ri |2 ) = O(|ui |2 ) which recognizes a set representation of uxi i . This set
representation has to contain a Cayley representation of every um
i (a variable-free knapsack
expression over G) for m ≥ 0.
First we define an auxiliary automaton B. Example 8.6 shows an example of the following
construction. Let Γ be the alphabet of ri (a set of possibly marked elements of G) and define
g : [a, b] → Γ by


f (0) if c = 0
g(c) = f (d) if c = d


f (c) otherwise.

KNAPSACK PROBLEMS FOR WREATH PRODUCTS

b

a

b
(-1)

a
(0)

b−1
b

1
(1,-1)

a
a

a2
(2,0)

a
b−1
b

a
a

a
(3,1,-1)

a2
(2,0)

a
b−1
b

a
a

a
(3,1,-1)

a2
(2,0)

a
b−1
b
a
(3,1,-1)

19

a
a
a2
(2,0)

a
b−1
ab−1
(3,1)

a
a
(2)

a
a
(3)

Figure 2. A run of the automaton for (at−1 bt2 b−1 tatat−1 )x
The state set of B is the set Q of all decreasing arithmetic progressions (s, s−d, s−2d, . . . , s−
ℓd) in the interval [a, b] where ℓ ≥ 0 together with a unique final state ⊤. It is not hard to
see that |Q| = O(|ri |2 ). For each state (s0 , . . . , sℓ ) ∈ Q we define the marked G-element


f (s ) · · · f (sℓ ) if neither g(s0 ) is top-marked nor g(sℓ ) is bottom-marked

 0
α(s0 , . . . , sℓ ) = f (s0 ) · · · f (sℓ ) if g(s0 ) is top-marked



f (s0 ) · · · f (sℓ ) if g(sℓ ) is bottom-marked
Since d > 0 it cannot happen that g(s0 ) is top-marked and at the same time g(sℓ ) is
bottom-marked. The initial state is the 1-tuple (a). For each state (s0 , . . . , sℓ ) ∈ Q and
γ = α(s0 , . . . , sℓ ) the automaton has the following transitions:
•
•
•
•

ε

(s0 , . . . , sℓ ) −
→ (s0 , . . . , sℓ , a) if sℓ = a + d
γ
(s0 , . . . , sℓ ) −
→ (s0 + 1, . . . , sℓ + 1) if s0 < b
γ
(s0 , . . . , sℓ ) −
→ (s1 + 1, . . . , sℓ + 1) if s0 = b and ℓ ≥ 1
γ
(s0 , . . . , sℓ ) −
→ ⊤ if s0 = b and ℓ = 0

Finally we take the union with another automaton which accepts the singleton {1}. This
yields the desired automaton Ai .
If d < 0 we can consider the group element (f ′ , −d) with f ′ : [−b, −a] → G, f ′ (c) = f (−c)
for −b ≤ c ≤ −a. We then do the above automaton construction for (f ′ , −d). From the
resulting NFA we finally construct an automaton for the reversed language. This proves the
lemma.

Example 8.6. Below is a run of the automaton for (at−1 bt2 b−1 tatat−1 )x on the word
b, a, 1, (a2 , a)3 , a2 , ab−1 , a, a.
Fig. 2 shows how this word is produced from (at−1 bt2 b−1 tatat−1 )5 . The last line shows the
tuple of relative positions in the currently “active” copies of b, a, b−1 , a, a. The positions
are −1, 0, 1, 2, 3. For instance, the tuple (3, 1, −1) means that currently three copies of
b, a, b−1 , a, a are active. The current position in the first copy is 3, the current position in
the second copy is 1, and the current position in the third copy is -1. These tuples are
states in the run below. The only additional states (1) and (3, 1) in the run are origins of
ε-transitions, which add new copies of b, a, b−1 , a, a.
b

a

ε

1

→ (1) −
→ (1, −1) −
→
(−1) −
→ (0) −
a2

ε

a

a2

ε

a

a2

ε

a

a2

ab−1

(2, 0) −→ (3, 1) −
→ (3, 1, −1) −
→
(2, 0) −→ (3, 1) −
→ (3, 1, −1) −
→
(2, 0) −→ (3, 1) −
→ (3, 1, −1) −
→
a

a

→ (3) −
→⊤
(2, 0) −→ (3, 1) −−−→ (2) −

20

M. GANARDI, D. KÖNIG, M. LOHREY, AND G. ZETZSCHE

A language L ⊆ Σ∗ is bounded if there exist words β1 , . . . , βn ∈ Σ∗ such that L ⊆ β1∗ · · · βn∗ .
It will be convenient to use the following characterization. For states p, q of an automaton
B, let Lp,q (B) be the set of all words read on a path from p to q. An NFA B recognizes
a bounded language if and only if for every state q, the language Lq,q (B) is commutative,
meaning that uv = vu for any u, v ∈ Lq,q (B) [5].
Lemma 8.7. Given an NFA B that recognizes a bounded language, one can compute in
polynomial time words β1 , . . . , βn with L(B) ⊆ β1∗ · · · βn∗ .
Proof. For any two states p, q with Lp,q (B) 6= ∅, compute a shortest word wp,q ∈ Lp,q (B)
and let Pq = u∗1 · · · u∗m , where wq,q = u1 · · · um and u1 , . . . , um are letters.
We first prove the lemma for the languages Lp,q = Lp,q (B) if p, q lie in the same strongly
connected component. Any two words in Lp,q have to be comparable in the prefix order:
Otherwise we could construct two distinct words of equal length in Lp,p , contradicting the
∗
commutativity of Lp,p . Since wp,q wq,q
⊆ Lp,q , this means that every word in Lp,q must be
∗
∗
∗
wq,q
Pq .
a prefix of a word in wp,q wq,q . In particular, we have Lp,q ⊆ wp,q
In the general case, we assume that B has only one initial state s. We decompose B into
strongly connected components, yielding a directed acyclic graph Γ with vertices V . For
i ≤ |V |, let Di = {v ∈ V | v has distance i from [s] in Γ}, where [s] denotes the strongly
Q
Q|V | Q
connected component of s. Observe that L(B) ⊆ i=0 v∈Di p,q∈v Lp,q , where the two
innermost products are carried out in an arbitrary order. Since we have established the
lemma in the case of the Lp,q , this tells us how to perform the computation for L(B).

Lemma 8.8. The NFAs Ai from Lemma 8.5 recognize bounded languages.
Proof. The statement is clear for the automata which recognize singleton languages in cases
1. and 2. Consider the constructed automaton B from case 3. It is almost deterministic
in the following sense: Every state in B has at most one outgoing transition labelled by a
symbol from the alphabet and at most one outgoing ε-transition.
We partition its state set as Q = Q0 ⊎ Q1 , where Q0 consists of those states (s0 , . . . , sℓ )
where sℓ ≤ a + d. Since there is no transition from Q1 to Q0 , every strongly connected
component is either entirely within Q0 or entirely within Q1 . If a state q has an outgoing
ε-transition, then q ∈ Q0 and all non-ε-transitions from q lead into Q1 . Therefore, every
state in B has at most one outgoing transition that leads into the same strongly connected
component. Thus, every strongly connected component is a directed cycle, meaning that
Lq,q (B) = w∗ , where w is the word read on that cycle. Hence, B recognizes a bounded
language. Hence also L(Ai ) = L(B) ∪ {1} is bounded.

Qk+1
O(n log n)
Lemma 8.9. There exists an NFA A of size i=1 O(|ui |) ≤ 2
which recognizes a
set representation of E, where n = |E|.
Proof. Reconsider the automata Ai from Lemma 8.5. We first ensure that for all 1 ≤ i ≤ k+1
we have L(Ai ) = 1∗ L(Ai ) 1∗ , which can be achieved using two new states in Ai . Let Ei be
the finite alphabet of marked knapsack expressions that occur as labels in Ai and let E be
the set of consistent tuples in the cartesian product E1 × · · · × Ek+1 .
Let A′ be the following product NFA over the alphabet E. It stores a (k + 1)-tuple of
states (one for each NFA Ai ). On input of a consistent tuple (γ1 , . . . , γk+1 ) ∈ E it reads γi
Qk+1
into Ai . The size of A′ is i=1 O(|ui |) ≤ 2O(n log n) . To obtain the NFA A we project the
transition labels of A′ as follows: Let (γ1 , . . . , γk+1 ) ∈ E and let (χ1 , . . . , χk+1 ) obtained by
removing all markings from the γi . We then replace the transition label (χ1 , . . . , χk+1 ) by
• χ1 · · · χk+1 if neither χ1 is top-marked nor χk+1 is bottom-marked,
• χ1 · · · χk+1 if χ1 is top-marked and χk+1 is not bottom-marked,
• χ1 · · · χk+1 if χ1 is not top-marked and χk+1 is bottom-marked,
• χ1 · · · χk+1 if χ1 is top-marked and χk+1 is bottom-marked.
One can verify that A recognizes a set representation of E.


KNAPSACK PROBLEMS FOR WREATH PRODUCTS

21

Proposition 8.10. Let G be a finitely generated abelian group. If ExpEq(G) ∈ NP and
Membership(Gρ∗ ) ∈ NP, then also KP(G ≀ Z) ∈ NP.
Proof. We first claim that, if E = 1 is solvable, then there exists a solution ν such that ν(x) is
exponentially bounded in n for all x ∈ X1 . Assume that ν is a solution for E = 1. From the
NFA A, we obtain an automaton A′ by replacing each knapsack expression in the alphabet
of A by its value unter ν in G. Then, A′ has the same number of states as A, hence at most
2O(n log n) . Moreover, A′ accepts a Cayley representation of the identity of G ≀ Z (which is
just a sequence of 1’s). Due to the size bound, A′ accepts such a representation of length
2O(n log n) . Since A accepts a set representation of E, this short computation corresponds to
a solution ν ′ . By definition of a set representation, for each x ∈ X1 , A′ makes at least ν ′ (x)
steps. Therefore, ν ′ (x) is bounded exponentially for x ∈ X1 .
Since each Ai accepts a set representation of uxi i , i ∈ [1, k] or of uk+1 , this implies that
solvability of E is witnessed by words α1 , . . . , αk+1 with αi ∈ L(Ai ) for i ∈ [1, k + 1] whose
length is bounded exponentially.
In the following we will encode exponentially long words as follows: A cycle compression
of a word w is a sequence (β1 , ℓ1 , . . . , βm , ℓm ) where each βi is a word and each ℓi ≥ 0 is a
binary encoded integer such that there exists a factorization w = w1 · · · wm and each factor
wi is the prefix of βiω of length ℓi . Each wi is called a cycle factor in w.
We need the following simple observation. Let (β1 , ℓ1 , . . . , βm , ℓm ) be a cycle compression
of a word w with the corresponding factorization w = w1 · · · wm . Given a position p in w
which yields factorizations w = uv, u = w1 · · · wi−1 wi′ , v = wi′′ wi+1 · · · wm and wi = wi′ wi′′ .
Splitting (β1 , ℓ1 , . . . , βm , ℓm ) at position p yields the unique cycle compression of w of the
form
(β1 , ℓ1 , . . . , βi−1 , ℓi−1 , βi′ , ℓ′i , βi′′ , ℓ′′i , . . . , βm , ℓm )
where |wi′ | = ℓ′i and |wi′′ | = ℓ′′i . Clearly, splitting can be performed in polynomial time.
With the help of splitting operations we can also remove a given set of positions from a
cycle compressed word in polynomial time.
This leads us to our NP-algorithm: First we construct the NFAs Ai as above. By
Lemma 8.8 each NFA Ai recognizes a bounded language. Hence for each i ∈ [1, k + 1],
Lemma 8.7 allows us to compute in polynomial time words βi,1 , . . . , βi,mi such that L(Ai ) ⊆
∗
∗
. For each Ai we guess a cycle compression (βi,1 , ℓi,1 , . . . , βi,mi , ℓi,mi ) of a word
βi,1
· · · βi,m
i
αi such that the words α1 , . . . , αk+1 have equal length ℓ. Then, we test in polynomial time
whether αi is accepted by Ai (this is a restricted case of the compressed membership problem
of a regular language [15]). Next we verify in polynomial time whether the markers of the
αi are consistent and whether the position of the origin in α1 coincides with the position of
the cursor in αk+1 . If so, we remove all markers from the words αi .
Finally we reduce to instances of ExpEq(G) and Membership(Gρ∗ ). Denote with P =
{p1 , . . . , pr } ⊆ [1, ℓ] the set of positions p such that there exists a variable xi ∈ X0 occurring
in αi [p], which is the expression at position p in αi . Note that if a variable xi ∈ X0
occurs in αi , then by definition of X0 and set representations, αi contains at most |ui |O(1)
positions with an expression 6= 1. We can therefore compute P in polynomial time and obtain
an instance of ExpEq(G) containing the expression α1 [pj ] · · · αk+1 [pj ] for each j ∈ [1, r].
We then remove the positions in P from the words αi and compute cycle compressions
(βi,1 , ℓi,1 , . . . , βi,mi , ℓi,mi ) of the new words αi in polynomial time.
The remaining words reduce to instances of Membership(Gρ∗ ) as follows: Consider the set
Pk+1
of at most i=1 mi positions at which some cycle factor begins in αi . By splitting all words
αi along these positions we obtain new cycle compressions of the form (βi,1 , ℓ1 , . . . , βi,m , ℓm )
of αi , i.e., the j-th cycle factor has uniform length across all αi . From this representation
one easily obtains m instances of Membership(Gρ∗ ).

Proposition 8.10 yields the NP
Lmupper bound for Theorem 5.7: If G is a finitely generated
abelian group, then G ∼
= Zn ⊕ i=1 (Z/ri Z) for some n, r1 , . . . , rm ∈ N, so that ExpEq(G)

22

M. GANARDI, D. KÖNIG, M. LOHREY, AND G. ZETZSCHE

corresponds to the solvability problem for linear equation systems over the integers, possibly
with modulo-constraints (if m > 0). This is a well known problem in NP. Moreover,
Membership(Gρ∗ ) belongs to TC0 by Theorem 8.2.
It remains to prove the NP-hardness part of Theorem 5.7, which is the content of the
next section.
8.3. NP-hardness.
Theorem 8.11. If G is non-trivial, then KP(G ≀ Z) is NP-hard.
Proof. Since every non-trivial group contains a non-trivial cyclic group, we may assume
that G is non-trivial and abelian. We reduce from 3-dimensional matching, 3DM for short.
In this problem, we have a set of triples T = {e1 , . . . , et } ⊆ [1, q] × [1, q] × [1, q] for some
q ≥ 1, and the question whether there is a subset M ⊆ T such that |M | = q and all pairs
(i, j, k), (i′ , j ′ , k ′ ) ∈ M with (i, j, k) 6= (i′ , j ′ , k ′ ) satisfy i 6= i′ , j 6= j ′ and k 6= k ′ ; such a set
M is called a matching. Since we will write all group operations multiplicatively, we denote
the generator of Z by a.
Let G be a non-trivial group and g ∈ G \ {1}. We reduce 3DM to KP(G ≀ Z) in the
following way: for every el = (i, j, k) ∈ T let
wl

=

ai gaq−i+j gaq−j+k ga−2q−k+(3q+1)l ga−(3q+1)l

=

ai gaq−i+j gaq−j+k ga−2q−k a(3q+1)l ga−(3q+1)l .
|
{z
} |
{z
}
ul

vl

Intuitively, ul is the word that puts g on positions i, q + j and 2q + k, and vl puts g on
position (3q + 1)l and then moves the cursor back to 0. Hence, vl is contained in G(Z) and
thus commutes with every element of G ≀ Z (recall that G is abelian).
We define the knapsack expression
E = w1x1 · · · wtxt (ag −1 )3q a−3q

q
Y

(a(3q+1)yi g −1 ) a−(3q+1)yq+1

i=1

with variables x1 , . . . , xt , y1 , . . . , yq+1 . For all values of these variables, the following equivalences hold.
w1x1

· · · wtxt

(ag

−1 3q −3q

) a

u1x1 · · · uxt t (ag −1 )3q a−3q v1x1 · · · vtxt
ux1 · · · uxt t (ag −1 )3q a−3q = 1 and v1x1 · · · vtxt
|1
{z
}
E1
|

q
Y

(a(3q+1)yi g −1 ) a−(3q+1)yq+1 = 1

i=1
q
Y

(a(3q+1)yi g −1 ) a−(3q+1)yq+1 = 1

i=1
q
Y

⇔
⇔

(a(3q+1)yi g −1 ) a−(3q+1)yq+1 = 1

i=1

{z

E2

}

The second equivalence holds because (i) for all values of the variables, the word E1 only
affects positions from the interval [1, 3q], whereas the word E2 only affects positions that
are multiples of 3q + 1 and (ii) E2 represents a word in G(Z) .
First assume that there is a matching M ⊆ T . We define a valuation ν for E by ν(xi ) = 1
if ei ∈ M and ν(xi ) = 0 if ei ∈
/ M . Let M = {em1 , . . . , emq } such that mi < mj for i < j
and let m0 = 0. Then we set ν(yi ) = mi − mi−1 for 1 ≤ i ≤ q, and ν(yq+1 ) = mq . Since M
is a matching, we have
Y
ν(uxe11 · · · uxett ) =
ul = (ag)3q a−3q
el ∈M

KNAPSACK PROBLEMS FOR WREATH PRODUCTS

23

and thus ν(E1 ) = 1. Furthermore, we have
ν(vex11

· · · vextt )

=

q
Y

i=1

a

(3q+1)mi

ga

−(3q+1)mi

=

q
Y

(a(3q+1)(mi −mi−1 ) g) a−(3q+1)mq

i=1

and thus ν(E2 ) = 1.
Now assume that there is a valuation ν for E with ν(E1 ) = ν(E2 ) = 1. Let ni = ν(xi )
and mi = ν(yi ). For every 1 ≤ l ≤ t, we must have g nl ∈ {1, g}, i.e., nl ≡ 0 mod ord(g) or
nl ≡ 1 mod ord(g). We first show that q ′ :=Q#{l | nl ≡ 1 mod ord(g)} = q. This follows from
ν(E2 ) = 1 and the fact that the effect of qi=1 a(3q+1)mi g −1 is to multiply the G-elements
at exactly q many positions p (p ≡ 0 mod (3q + 1)) with g −1 . Hence, the effect of v1n1 · · · vtnt
must be to multiply the G-elements at exactly q many positions p (p ≡ 0 mod (3q + 1)) with
g. But this means that q ′ = q.
So we can assume that q ′ = q. We finally show that M = {el | nl ≡ 1 mod ord(g)} ⊆ T
is a matching: Assume that there are e = (i, j, k) ∈ M and e′ = (i′ , j ′ , k ′ ) ∈ M with
i = i′ , j = j ′ or k = k ′ . Since q ′ = q this would imply that at most 3q − 1 positions p with
1 ≤ p ≤ 3q can be set to g by the word une11 · · · unett . But then, (ag −1 )3q a−3q would leave
a position with value g −1 , and hence ν(E1 ) 6= 1. Hence, M must be a matching. Notice
that the argumentation of the whole proof still works in the case that we allow the variables
x1 , . . . , xt , y1 , . . . , yq+1 to be integers instead of naturals.

Note that the above NP-hardness proof also works for the subset sum problem, where the
range of the valuation is restricted to {0, 1}. Moreover, if the word problems for two groups
G and H can be solved in polynomial time, then word problem for G ≀ H can be solved in
polynomial time as well [21]. This implies that subset sum for G ≀ H belongs to NP. Thus,
we obtain:
Theorem 8.12. Let G and H be non-trivial finitely generated groups and assume that H
contains an element of infinite order. Then, the subset sum problem for G ≀ H is NP-hard. If
moreover, the word problem for G and H can be solved in polynomial time, then the subset
sum problem for G ≀ H is NP-complete.
9. Open problems
Our results yield decidability of KP(G ≀ H) for almost all groups G and H that are known
to satisfy the necessary conditions. However, we currently have no complete characterization
of those G and H for which KP(G ≀ H) is decidable.
Several interesting open problems concerning the complexity of knapsack for wreath products remain. We are confident that our NP upper bound for KP(G ≀ Z), where G is finitely
generated abelian, can be extended to KP(G≀F ) for a finitely generated free group G as well
as to KP(G ≀ Zk ). Another question is whether the assumption on G being abelian can be
weakened. In particular, we want to investigate whether polynomial time algorithms exist
for Membership(Gρ∗ ) for certain non-abelian groups G.
The complexity of knapsack for free solvable groups is open as well. Our decidability proof
uses the preservation of knapsack-semilinearity under wreath products (Theorem 5.5). Our
construction in the proof of Theorem 5.5 adds for every application of the wreath product a
∀∗ ∃∗ -quantifier prefix in the formula describing the solution set. Since a free solvable group
of class d and rank r is embedded into a d-fold iterated wreath product of Zr , this leads to a
Π2(d−1) -formula (for d = 1, we clearly have a Π0 -formula). The existence of a solution is then
expressed by a Σ2d−1 -formula. Haase [9] has shown that the Σi+1 -fragment of Presburger
arithmetic is complete for the i-th level of the so-called weak EXP hierarchy. In addition
to the complexity resulting from the quantifier alternations in Presburger arithmetic, our
algorithm incurs a doubly exponential increase in the formula size for each application of
the wreath product. This leads to the question whether there is a more efficient algorithm
for knapsack over free solvable groups.

24

M. GANARDI, D. KÖNIG, M. LOHREY, AND G. ZETZSCHE

Finally, we are confident that with our techniques from [18] one can also show preservation
of knapsack-semilinearity under graph products.
References
[1] Tara C. Davis and Alexander Yu. Olshanskii. Subgroup distortion in wreath products of cyclic groups.
Journal of Pure and Applied Algebra, 215(12):2987–3004, 2011.
[2] Samuel Eilenberg and Marcel P. Schützenberger. Rational sets in commutative monoids. Journal of
Algebra, 13:173–191, 1969.
[3] Michael Elberfeld, Andreas Jakoby, and Till Tantau. Algorithmic meta theorems for circuit classes of
constant and logarithmic depth. Electronic Colloquium on Computational Complexity (ECCC), 18:128,
2011.
[4] Elizaveta Frenkel, Andrey Nikolaev, and Alexander Ushakov. Knapsack problems in products of groups.
Journal of Symbolic Computation, 74:96–108, 2016.
[5] Pawel Gawrychowski, Dalia Krieger, and Jeﬀrey Shallit Narad Rampersad. Finding the growth rate of a
regular or context-free language in polynomial time. International Journal of Foundations of Computer
Science, 21(04):597–618, 2010.
[6] Etienne Ghys and Pierre de la Harpe. Sur les groupes hyperboliques d’après Mikhael Gromov. Progress
in mathematics. Birkhäuser, 1990.
[7] Seymour Ginsburg and Edwin H. Spanier. Semigroups, Presburger formulas, and languages. Pacific
Journal of Mathematics, 16(2):285–296, 1966.
[8] Christoph Haase. On the complexity of model checking counter automata. PhD thesis, University of
Oxford, St Catherine’s College, 2011.
[9] Christoph Haase. Subclasses of presburger arithmetic and the weak EXP hierarchy. In Joint Meeting
of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the TwentyNinth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS 2014, pages
47:1–47:10. ACM, 2014.
[10] William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits
for division and iterated multiplication. Journal of Computer and System Sciences, 65:695–716, 2002.
[11] Richard M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher,
editors, Complexity of Computer Computations, pages 85–103. Plenum Press, 1972.
[12] Daniel König, Markus Lohrey, and Georg Zetzsche. Knapsack and subset sum problems in nilpotent,
polycyclic, and co-context-free groups. In Algebra and Computer Science, volume 677 of Contemporary
Mathematics, pages 138–153. American Mathematical Society, 2016.
[13] Daniel König and Markus Lohrey. Evaluation of circuits over nilpotent and polycyclic groups. Algorithmica, 2017.
[14] Jörg Lehnert and Pascal Schweitzer. The co-word problem for the higman-thompson group is contextfree. Bulletin of the London Mathematical Society, 39(2):235–241, 2007.
[15] Markus Lohrey. Algorithmics on SLP-compressed strings: A survey. Groups Complexity Cryptology,
4(2):241–299, 2012.
[16] Markus Lohrey, Benjamin Steinberg, and Georg Zetzsche. Rational subsets and submonoids of wreath
products. Information and Computation, 243:191–204, 2015.
[17] Markus Lohrey and Georg Zetzsche. Knapsack in graph groups, HNN-extensions and amalgamated
products. CoRR, abs/1509.05957, 2015.
[18] Markus Lohrey and Georg Zetzsche. Knapsack in graph groups, HNN-extensions and amalgamated
products. In Nicolas Ollinger and Heribert Vollmer, editors, Proc. of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016), volume 47 of Leibniz International
Proceedings in Informatics (LIPIcs), pages 50:1–50:14, Dagstuhl, Germany, 2016. Schloss Dagstuhl–
Leibniz-Zentrum fuer Informatik.
[19] Markus Lohrey and Georg Zetzsche. The complexity of knapsack in graph groups. In Proceedings of
the 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, volume 66 of LIPIcs,
pages 52:1–52:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
[20] Wilhelm Magnus. On a theorem of Marshall Hall. Annals of Mathematics. Second Series, 40:764–768,
1939.
[21] Alexei Miasnikov, Svetla Vassileva, and Armin Weiß. The conjugacy problem in free solvable groups
and wreath products of abelian groups is in TC0 . In Computer Science – Theory and Applications –
12th International Computer Science Symposium in Russia, CSR 2017, Proceedings, volume 10304 of
Lecture Notes in Computer Science, pages 217–231. Springer, 2017.
[22] Alexei Mishchenko and Alexander Treier. Knapsack problem for nilpotent groups. Groups Complexity
Cryptology, 9(1):87–98, 2017.
[23] Alexei Myasnikov, Andrey Nikolaev, and Alexander Ushakov. Knapsack problems in groups. Mathematics of Computation, 84:987–1016, 2015.

KNAPSACK PROBLEMS FOR WREATH PRODUCTS

25

[24] Alexei Myasnikov and Andrey Nikolaev. Verbal subgroups of hyperbolic groups have inﬁnite width.
Journal of the London Mathematical Society, 90(2):573–591, 2014.
[25] Alexei Myasnikov and Armin Weiß. TC0 circuits for algorithmic problems in nilpotent groups. CoRR,
abs/1702.06616, 2017.
[26] Andrey Nikolaev and Alexander Ushakov. Subset sum problem in polycyclic groups. Journal of Symbolic
Computation, 84:84–94, 2018.
[27] Charles Sims. Computation with finitely presented groups. Cambridge University Press, 1994.

Appendix A. Hyperbolic groups
Let G be a finitely generated group with the finite symmetric generating set Σ. The
Cayley-graph of G (with respect to Σ) is the undirected graph Γ = Γ(G) with node set G
and all edges (g, ga) for g ∈ G and a ∈ Σ. We view Γ as a geodesic metric space, where every
edge (g, ga) is identified with a unit-length interval. It is convenient to label the directed
edge from g to ga with the generator a. The distance between two points p, q is denoted
with dΓ (p, q). For g ∈ G let |g| = dΓ (1, g). For r ≥ 0, let Br (1) = {g ∈ G | dΓ (1, g) ≤ r}.
Given a word w ∈ Σ∗ , one obtains a unique path P [w] that starts in 1 and is labelled
with the word w. This path ends in the group element represented by w. More generally, for
g ∈ G we denote with g · P [w] the path that starts in g and is labelled with w. We will only
consider paths of the form g · P [w]. One views g · P [w] as a continuous mapping from the
real interval [0, |w|] to Γ. Such a path P : [0, n] → Γ is geodesic if dΓ (P (0), P (n)) = n; it is a
(λ, ǫ)-quasigeodesic if for all points p = P (a) and q = P (b) we have |a − b| ≤ λ · dΓ (p, q) + ε.
We say that a path P : [0, n] → Γ is path from P (0) to P (n). A word w ∈ Σ∗ is geodesic if
the path P [w] is geodesic.
A geodesic triangle consists of three points p, q, r, ∈ G and geodesic paths Pp,q , Pp,r , Pq,r
(the three sides of the triangle), where Px,y is a path from x to y. For δ ≥ 0, the group
G is δ-hyperbolic, if for every geodesic triangle, every point p on one of the three sides has
distance at most δ from a point belonging to one of the two sides that are opposite of p.
Finally, G is hyperbolic, if it is δ-hyperbolic for some δ ≥ 0. Finitely generated free groups
are for instance 0-hyperbolic. The property of being hyperbolic is independent of the the
chosen generating set. The word problem for every hyperbolic group is decidable in linear
time. This allows to compute for a given word w an equivalent geodesic word; the best
known algorithm is quadratic.
Let us fix a δ-hyperbolic group G with the finite symmetric generating set Σ for the
further discussion.
Lemma A.1 (c.f. [6, 8.21]). Let g ∈ G be of infinite order and let n ≥ 1. Let u be a
geodesic word representing g. Then the path P [un ] is a (λ, ǫ)-quasigeodesic, where λ = |g|N ,
ǫ = 2|g|2 N 2 + 2|g|N and N = |B2δ (1)|.
Consider two paths P1 : [0, n1 ] → Γ, P1 : [0, n2 ] → Γ and let K be a positive real number.
We say that P1 and P2 asynchronously K-fellow travel if there exist two continuous nondecreasing mappings ϕ1 : [0, 1] → [0, n1 ] and ϕ2 : [0, 1] → [0, n2 ] such that ϕ1 (0) = ϕ2 (0) = 0,
ϕ1 (1) = n1 , ϕ2 (1) = n2 and for all 0 ≤ t ≤ 1, dΓ (P1 (ϕ1 (t)), P2 (ϕ2 (t))) ≤ K. Intuitively, this
means that one can travel along the paths P1 and P2 asynchronously with variable speeds
such that at any time instant the current points have distance at most K.
Lemma A.2 (c.f. [24]). Let P1 and P2 be (λ, ǫ)-quasigeodesic paths in ΓG and assume that
Pi starts in gi and ends in hi . Assume that dΓ (g1 , h1 ), dΓ (g2 , h2 ) ≤ h. Then there exists a
computable bound K = K(δ, λ, ǫ, h) ≥ h such that P1 and P2 asynchronously K-fellow travel.
A.1. Hyperbolic groups are knapsack-semilinear. In this section, we prove the following result:
Theorem A.3. Every hyperbolic group is knapsack-semilinear.
Let us fix a δ-hyperbolic group G and let Σ be a finite symmetric generating set for G.
We first consider knapsack instances of depth 2.

26

M. GANARDI, D. KÖNIG, M. LOHREY, AND G. ZETZSCHE

Lemma A.4. For all g1 , h1 , g2 , h2 ∈ G such that g1 and g2 have infinite order, the set
{(x1 , x2 ) | h1 g1x1 = g2x2 h2 in G} is effectively semilinear.
Proof. The semilinear subsets of Nk are exactly the rational subsets of Nk [2]. A subset
A ⊆ Nk is rational if it is a homomorphic image of a regular set of words. In other words,
there exists a finite automaton with transitions labeled by elements of Nk such that A is
the set of v ∈ Nk that are obtained by summing the transition labels along a path from
the initial state to a final state. We prove that the set {(x1 , x2 ) | h1 g1x1 = g2x2 h2 in G} is
effectively rational.
Let ui be a geodesic word representing gi and let ℓi = |ui |. Assume that n1 , n2 ≥ 1
are such that h1 g1n1 = g2n2 h2 . Let P1 = h1 · P [un1 1 ] and let P2 = P [un2 2 ]. By Lemma A.1,
P1 and P2 are (λ, ǫ)-quasigeodesics, where λ and ǫ only depend on δ, |u1 | and |u2 |. By
Lemma A.2, the paths P1 and P2 asynchronously K-fellow travel, where K is a computable
bound that only depends on δ, λ, ǫ, |g1 |, |h1 |, |g2 |, |h2 |. Let ϕ1 : [0, 1] → [0, n1 · ℓ1 ] and
ϕ2 : [0, 1] → [0, n2 · ℓ2 ] be the corresponding continuous non-decreasing mappings.
Let p1,i = h1 g1i = P1 (i · ℓ1 ) for 0 ≤ i ≤ n1 and p2,j = g2j = P2 (j · ℓ2 ) for 0 ≤ j ≤ n2 . Thus,
p1,i is a point on P1 and p2,j is a point on P2 . We define the binary relation R ⊆ {p1,i | 0 ≤
i ≤ n1 } × {p2,j | 0 ≤ j ≤ n2 } by
R = {(p1,i , p2,j ) | ∃r ∈ [0, 1] : ϕ1 (r) ∈ [i · ℓ1 , (i + 1) · ℓ1 ), ϕ2 (r) ∈ [j · ℓ2 , (j + 1) · ℓ1 )}.
Thus, we take all pairs (P1 (ϕ1 (r)), P2 (ϕ2 (r))), and push the first (resp., second) point in this
pair back along P1 (resp., P2 ) to the next point p1,i (resp., p2,j ). Then R has the following
properties:
• (0, 0), (n1 , n2 ) ∈ R
• If (p1,i , p2,j ) ∈ R and (i, j) 6= (n1 , n2 ) then one of the following pairs also belongs to
R: (p1,i+1 , p2,j ), (p1,i , p2,j+1 ), (p1,i+1 , p2,j+1 ).
• If (p1,i , p2,j ) ∈ R, then dΓ (p1,i , p2,j ) ≤ K + ℓ1 + ℓ2 .
Let r = K + ℓ1 + ℓ2 . We can now construct a finite automaton over N × N that accepts the
set {(x1 , x2 ) | h1 g1x1 = g2x2 h2 in G}. The set of states consists of Br (1). The initial state is
h1 , the final state is h2 . Finally, the transitions are the following:
(0,1)

• p −−−→ q for p, q ∈ Br (1) if p = g2 q
(1,0)

• p −−−→ q for p, q ∈ Br (1) if pg1 = q
(1,1)

• p −−−→ q for p, q ∈ Br (1) if pg1 = g2 q
By the above consideration, it is clear that this automaton accepts the set {(x1 , x2 ) | h1 g1x1 =
g2x2 h2 in G}.

We can now prove Theorem A.3.
Proof of Theorem A.3. Consider a knapsack expression E = v1 ux1 1 v2 ux2 2 v3 · · · uxk k vk+1 . We
want to show that the set of all solutions of E = 1 is a semilinear subset of Nk . For this we
construct a Presburger formula with free variables x1 , . . . , xk that is equivalent to E = 1.
We do this by induction on the depth k. Therefore, we can use in our Presburger formula
also knapsack equations of the form F = 1, where F has depth at most k − 1.
Let gi ∈ G be the group element represented by the word ui . In a hyperbolic group the
order of torsion elements is bounded by a fixed constant that only depends on the group, see
also the proof of [23, Theorem 6.7]). This allows to check for each gi whether it has finite
order, and to compute the order in the positive case. Assume that gi has finite order mi .
We then produce for every number 0 ≤ d ≤ mi − 1 a knapsack instance of depth k − 1 by
replacing uxi i by udi , which by induction can be transformed into an equivalent Presburger
formula. We then take the disjunction of all these Presburger formulae for all 0 ≤ d ≤ mi −1.
A similar argument shows that it suffices to construct a Presburger formula describing all
solutions in Nk+ (where N+ = N \ {0}).

KNAPSACK PROBLEMS FOR WREATH PRODUCTS

27

un2 2
un1 1

un3 3

v

un4 4
un5 5

Figure 3. The (k + 1)-gon for k = 5 from the proof of Theorem A.3

By the above discussion, we can assume that all ui represent group elements of infinite
order. The case that k ≤ 2 is covered by Lemma A.4. Hence, we assume that k ≥ 3. By the
above remark, we only need to consider valuations ν such that ν(xi ) > 0 for all i ∈ [1, k].
Moreover, we can assume that E has the form ux1 1 · · · uxk k v, where all ui and v are geodesic
ν(x )
words. By Lemma A.1 for every valuation ν, all words ui i are (λ, ǫ)-quasigeodesics for
certain constants λ and ǫ.
Consider a solution ν and let ni = ν(xi ) for i ∈ [1, k]. Consider the polygon obtained by
traversing the closed path labelled with ux1 1 · · · uxk k v. We partition this path into segements
P1 , . . . , Pk , Q, where Pi is the subpath labelled with uni i and Q is the subpath labelled with
v. We consider these subpaths as the sides of a (k + 1)-gon, see Fig. 3. Since all sides of
this (k + 1)-gon are (λ, ǫ)-quasigeodesics, we can apply [23, Lemma 6.4]: Every side of the
(k+1)-gon is contained in the h-neighborhoods of the other sides, where h = (κ+κ log(k+1))
for a constant κ that only depends on the constants δ, λ, ε.
Let us now consider the side P2 of the quasigeodesic (k+1)-gon. It is labelled with ux2 2 . Its
neighboring sides are P1 and P3 (recall that k ≥ 3) and are labelled with ux1 1 and ux3 3 .4 We
now distinguish the following cases. In each case we cut the (k + 1)-gon into smaller pieces
along paths of length ≤ h, and these smaller pieces will correpsond to knapsack instances of
smaller depth. When we speak of a point on the (k + 1)-gon, we mean a node of the Cayley
graph (i.e., an element of the group G) and not a point in the interior of an edge. Moreover,
when we peak of the successor point of a point p, we refer to the clockwise order on the
(k + 1)-gon, where the sides are traversed in the order P1 , . . . , Pk , Q.
Case 1: There is a point on p ∈ P2 that has distance at most h from a node q ∈ P4 · · · Pk .
Let us assume that q ∈ Pi where i ∈ [4, k]. We now construct two new knapsack instances
Ft and Gt for all words w ∈ Σ∗ of length at most h and all factorizations u2 = u2,1 u2,2 and
ui = ui,1 ui,2 , where t = (i, w, u2,1 , u2,2 , ui,1 , ui,2 ):
x

Ft

i+1
= ux1 1 uy22 (u2,1 wui,2 )uzi i ui+1
· · · uxk k v and

Gt

i−1 yi
= u2,2 uz22 ux3 3 · · · ui−1
ui (ui,1 w−1 )

x

Here y2 , z2 , yi , zi are new variables. The situation looks as follows, where the case i = k = 5
is shown:

4We take the side P since Q is not a neighboring side of P . This avoids some additional cases in the
2
2
following case distinction.

28

M. GANARDI, D. KÖNIG, M. LOHREY, AND G. ZETZSCHE

uy22

u2,1 u2,2

uz22

ux1 1

ux3 3
w
ux4 4

v

uz55

u5,2 u5,1

uy55

Note that Ft and Gt have depth at most k−1. Lets say that a tuple t = (i, w, u2,1 , u2,2 , ui,1 , ui,2 )
is valid for case 1 if i ∈ [4, k], w ∈ Σ∗ , |w| ≤ h, u2 = u2,1 u2,2 and ui = ui,1 ui,2 . Moreover,
let A1 be the following formula, where t ranges over all tuples that are valid for case 1, and
i is the first component of the tuple t:
_
A1 =
∃y2 , z2 , yi , zi : x2 = y2 + 1 + z2 ∧ xi = yi + 1 + zi ∧ Ft = 1 ∧ Gt = 1
t

Case 2: There is a point on p ∈ P2 that has distance at most h from a node q ∈ Q. We
construct two new knapsack instances Ft and Gt for all words w ∈ Σ∗ of length at most h
and all factorizations u2 = u2,1 u2,2 and v = v1 v2 , where t = (w, u2,1 , u2,2 , v1 , v2 ):
Ft

=

ux1 1 uy22 (u2,1 wv2 ) and

Gt

=

u2,2 uz22 ux3 3 · · · uxk k (v1 w−1 )

As in case 1, y2 , z2 are new variables and Ft and Gt have depth at most k − 1. The situation
looks as follows:
uy22

u2,1 u2,2

ux1 1

uz22

ux3 3
w

v2

ux4 4
v1
ux5 5

We say that a tuple t = (w, u2,1 , u2,2 , v1 , v2 ) is valid for case 2 if w ∈ Σ∗ , |w| ≤ h, u2 =
u2,1 u2,2 and v = v1 v2 . Moreover, let A2 be the following formula, where t ranges over all
tuples that are valid for case 2:
_
A2 =
∃y2 , z2 : x2 = y2 + 1 + z2 ∧ Ft = 1 ∧ Gt = 1
t

Case 3: Every point p ∈ P2 has distance at most h from a point on P1 . Let q be the
unique point in P2 ∩ P3 and let p ∈ P1 be a point with dΓ (p, q) ≤ h. We construct two new

KNAPSACK PROBLEMS FOR WREATH PRODUCTS

29

knapsack instances Ft and Gt for all words w ∈ Σ∗ of length at most h and all factorizations
u1 = u1,1 u1,2 , where t = (w, u1,1 , u1,2 ):
Ft

= uy11 (u1,1 w)ux3 3 · · · uxk k v and

Gt

= u1,2 uz11 ux2 2 w−1

Since k ≥ 3, Ft and Gt have depth at most k − 1. The situation looks as follows:

uz11
u1,2
u1,1

un2 2
w

ux3 3

uy11

ux4 4

v

ux5 5

We say that a triple t = (w, u1,1 , u1,2 ) is valid for case 3 if w ∈ Σ∗ , |w| ≤ h and u1 = u1,1 u1,2 .
Moreover, let A3 be the following formula, where t ranges over all tuples that are valid for
case 3:
A3 =

_

∃y1 , z1 : x1 = y1 + 1 + z1 ∧ Ft = 1 ∧ Gt = 1

t

Case 4: Every point p ∈ P2 has distance at most h from a point on P3 . This case is of course
completely analogous to case 3 and yields a corresponding formula A4 .
Case 5: Every point p ∈ P2 has distance at most h from a point on P1 ∪ P3 but P2 is neither
contained in the h-neighborhood of P1 nor in the h-neighborhood of P3 . Hence there exists
points p1 , p3 ∈ P2 which are connected by an edge and such that p1 has distance at most h
from P1 and p3 has distance at most h from P3 . Therefore, p1 has distance at most h+1 from
P1 as well as distance at most h + 1 from P3 . We construct three new knapsack instances Ft ,
Gt , Ht for all words w1 , w2 ∈ Σ∗ with |w1 |, |w2 | ≤ h + 1 and all factorizations u1 = u1,1 u1,2 ,
u2 = u2,1 u2,2 , and u3 = u3,1 u3,2 , where t = (w1 , w2 , u1,1 , u1,2 , u2,1 , u2,2 , u3,1 , u3,2 ):
Ft

=

uy11 (u1,1 w1 w2 u3,2 )uz33 ux4 4 · · · uxk k v,

Gt

=

u1,2 uz11 uy22 u2,1 w1−1 ,

Ht

=

u2,2 uz22 uy33 u3,1 w2−1

Since k ≥ 3, Ft , Gt and Ht have depth at most k − 1. The situation looks as follows:

30

M. GANARDI, D. KÖNIG, M. LOHREY, AND G. ZETZSCHE

uz11
u1,2

uy22

u2,1 u2,2

w1

uz22

uy33

w2

u3,1

u1,1
uy11

u3,2
uz33

ux4 4

v

ux5 5
We say that a tuple t = (w1 , w2 , u1,1 , u1,2 , u2,1 , u2,2 , u3,1 , u3,2 ) is valid for case 5 if w1 , w2 ∈
Σ∗ , |w1 |, |w2 | ≤ h + 1, u1 = u1,1 u1,2 , u2 = u2,1 u2,2 , and u3 = u3,1 u3,2 . Moreover, let A5 be
the following formula, where t ranges over all tuples that are valid for case 5:
_
A5 =
∃y1 , z1 , y2 , z2 , y3 , z3 : x1 = y1 + 1 + z1 ∧ x2 = y2 + 1 + z2 ∧ x3 = y3 + 1 + z3 ∧
t

Ft = 1 ∧ Gt = 1 ∧ Ht = 1.

Our final formula is A1 ∨A2 ∨A3 ∨A4 ∨A5 . It is easy to check that a valuation ν : {x1 , . . . , xk }
satisfies ν(E) = 1 if and only if ν makes A1 ∨ A2 ∨ A3 ∨ A4 ∨ A5 true. If ν(E) = 1 holds,
then one of the above five cases holds, in which case ν makes the corresponding formula Ai
true. Vice versa, if ν makes one of the formulas Ai true then ν(E) = 1 holds.

Universität Siegen, Germany, {ganardi,koenig,lohrey}@eti.uni-siegen.de
LSV, CNRS & ENS Paris-Saclay, France, zetzsche@lsv.fr

