Knapsack in Graph Groups

Abstract

It is shown that the knapsack problem, which was introduced by Myasnikov et al. for arbitrary finitely generated groups, can be solved in NP for every graph group. This result even holds if the group elements are represented in a compressed form by so called straight-line programs, which generalizes the classical NP-completeness result of the integer knapsack problem. If group elements are represented explicitly by words over the generators, then knapsack for a graph group belongs to the class LogCFL (a subclass of P) if the graph group can be built up from the trivial group using the operations of free product and direct product with $\mathbb {Z}$. In all other cases, the knapsack problem is NP-complete.

1 Introduction

In their paper [44], Myasnikov, Nikolaev, and Ushakov started the investigation of classical discrete optimization problems, which are formulated over the integers, for arbitrary (possibly non-commutative) 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 g ₁,…,g _k ,g ∈ G (specified by finite words over the generators of G) and it is asked whether there exists a solution $(x_{1}, \ldots , x_{k}) \in \mathbb {N}^{k}$ of the equation $g_{1}^{x_{1}} {\cdots } g_{k}^{x_{k}} = g$. For the subset sum problem one restricts the solution to {0,1}^k.

For the particular case $G = \mathbb {Z}$ (where the additive notation x ₁ ⋅ g ₁ + ⋯ + x _k ⋅ g _k = g is usually preferred) these problems are NP-complete if the numbers g ₁,…,g _k ,g are encoded in binary representation. For subset sum, this is a classical result from Karp’s seminal paper [31] on NP-completeness. Knapsack for integers is usually formulated in a more general form in the literature; NP-completeness of the above form (for binary encoded integers) was shown in [23], where the problem was called multisubset sum.¹ Interestingly, if we consider subset sum for the group $G = \mathbb {Z}$, but encode the input numbers g ₁,…,g _k ,g in unary notation, then the problem is in DLOGTIME-uniform T C ⁰ (a small subclass of polynomial time and even of logarithmic space that captures the complexity of multiplication of binary encoded numbers; see e.g. the book [50] for more details) [17], and the same holds for knapsack (see Theorem 4.29). Related results can be found in [29].

In [44], 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. Among others, the following results were shown in [44]:

• Subset sum and knapsack can be solved in polynomial time for every hyperbolic group.

• Subset sum for a virtually nilpotent group (a finite extension of a nilpotent group) can be solved in polynomial time.

• 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 $\mathbb {Z} \wr \mathbb {Z}$, Thompson’s group F, and the Baumslag-Solitar group BS(1,2).

Further results on knapsack and subset sum have been recently obtained in [33]:

• For a virtually nilpotent group, subset sum belongs to NL (nondeterministic logspace).

• There is a nilpotent group of class 2 (in fact, a direct product of sufficiently many copies of the discrete Heisenberg group $H_{3}(\mathbb {Z})$), for which knapsack is undecidable.

• The knapsack problem for the discrete Heisenberg group $H_{3}(\mathbb {Z})$ is decidable. In particular, together with the previous point it follows that decidability of knapsack is not preserved under direct products.

• There is a polycyclic group with an NP-complete subset sum problem. Recently it has been shown that subset sum is NP-complete for every polycyclic group that is not virtually nilpotent [45].

• The knapsack problem is decidable for every co-context-free group.

In recent years, group-theoretic problems began to be studied in the setting where group elements are encoded in a succinct (or compressed) way. A particularly popular succinct representation are so called straight-line programs (SLP). These are context-free grammars that produce a single word, see [35, 36] for surveys. Over a unary alphabet, one can achieve for every word exponential compression with SLPs: The word a ⁿ can be produced by an SLP of size O(log n). This shows that knapsack and subset sum for the group $\mathbb {Z}$ with SLP-compressed group elements correspond to the classical knapsack and subset sum problem with binary encoded numbers. To distinguish between the two variants, we will speak in this introduction of uncompressed knapsack (resp., subset sum) if the input group elements are given explicitly by words over the generators. On the other hand, if these words are represented by SLPs, we will speak of compressed knapsack (resp., subset sum). In the main part of this paper, the terms “knapsack” and “subset sum” will refer to the uncompressed version.

In this paper we will study the compressed and uncompressed versions of knapsack and subset sum for the class of graph groups. Graph groups are also known as “right-angled Artin groups” or “free partially commutative groups”. A graph group is specified by a finite simple graph. The vertices are the generators of the group, and two generators a and b are allowed to commute if and only if a and b are adjacent. Graph groups can be regarded as interpolating between free groups and free abelian groups and constitute a group counterpart of trace monoids (free partially commutative monoids), which have been used for the specification of concurrent behavior. In combinatorial group theory, graph groups are currently an active area of research, mainly because of their rich subgroup structure (see e.g. [6, 10, 20]).

Since the word problem for a graph group can be solved in polynomial time, it is clear that for each graph group, the subset sum problem belongs to NP. This result carries over to compressed subset sum, since the compressed word problem (the word problem where the input group element is given by an SLP) for a graph product can be solved in polynomial time [37] (see also [36] for more details). Our first main result states that for every graph group, even compressed knapsack belongs to NP and is in fact NP-complete. This generalizes the classical NP-completeness for knapsack (over $\mathbb {Z}$) to a much wider class of groups. To prove this result, we proceed in two steps:

• We show that if an instance $g_{1}^{x_{1}} {\cdots } g_{k}^{x_{k}} = g$, where all group elements g ₁,…,g _k are given succinctly by SLPs, has a solution in a graph group, then it has a solution where every x _i is bounded exponentially in the input length (the total length of all SLPs representing the group elements g ₁,…,g _k ,g).

• We then guess the binary encodings of numbers n ₁,…,n _k that are bounded by the exponential bound from the previous point and verify in polynomial time the identity $g_{1}^{n_{1}} {\cdots } g_{k}^{n_{k}} = g$. The latter problem is an instance of the compressed word problem for a graph group, which can be solved in polynomial time [37].

In fact, our proof yields a stronger result: First, it yields an NP procedure for solving knapsack-like equations $g_{1}^{x_{1}} {\cdots } g_{k}^{x_{k}} = g$ where some of the variables x ₁,…,x _k are allowed to be identical. We call such an equation an exponent equation. Hence, we prove that solvability of exponent equations over a graph group belongs to NP. A by-product of our proof is that the set of all solutions $(x_{1}, \ldots , x_{k}) \in \mathbb {N}^{k}$ of $g_{1}^{x_{1}} {\cdots } g_{k}^{x_{k}} = g$ is semilinear, and a semilinear representation can be produced effectively. This seems to be true for many groups, e.g., for all co-context-free groups [33]. On the other hand, the discrete Heisenberg group $H_{3}(\mathbb {Z})$ is an example of a group for which solvability of exponent equations is decidable, but the set of all solutions of an exponent equation is not semilinear; it is defined by a single quadratic Diophantine equation [33].

The second part of the paper is concerned with with uncompressed knapsack and subset sum for graph groups. In the case of knapsack, we completely determine the complexity and for subset sum, we obtain an almost complete picture. For a finite simple graph Γ, let $\mathbb {G}({\Gamma })$ denote the graph group specified by Γ.

• (i) Uncompressed knapsack and subset sum for $\mathbb {G}({\Gamma })$ are complete for T C ⁰ if Γ is a complete graph (and thus $\mathbb {G}({\Gamma })$ is a free abelian group.)²

• (ii) Uncompressed knapsack and subset sum for $\mathbb {G}({\Gamma })$ are L o g C F L-complete if Γ is not a complete graph and neither contains an induced cycle on four nodes (C 4) nor an induced path on four nodes (P 4).

• (iii) Uncompressed knapsack for $\mathbb {G}({\Gamma })$ is N P-complete if Γ contains an induced C 4 or an induced P 4 (it is not clear whether this also holds for subset sum).

The result (1) is a straightforward extension of the corresponding fact for $\mathbb {Z}$ [17]. The proofs for (1) and (1) are less obvious. Recall that L o g C F L is the closure of the context-free languages under logspace reductions; it is contained in the circuit complexity class N C ².

To show the upper bound in (1), we use the fact that the graph groups $\mathbb {G}({\Gamma })$, where Γ neither contains an induced C 4 nor an induced P 4 (these graphs are the so called transitive forests), are exactly those groups that can be built up from $\mathbb {Z}$ using the operations of free product and direct product with $\mathbb {Z}$. We then construct inductively over these operations a logspace-bounded auxiliary pushdown automaton working in polynomial time (these machines accept exactly the languages in L o g C F L) that checks whether an acyclic finite automaton accepts a word that is trivial in the graph group. In order to apply this result to knapsack, we finally show that every solvable knapsack instance over a graph group $\mathbb {G}({\Gamma })$ with Γ a transitive forest has a solution with polynomially bounded exponents. This is the most difficult result in the second part of this paper and it might be of independent interest.

For the lower bound in (1), it suffices to consider the group F ₂ (the free group on two generators). Our proof is based on the fact that the context-free languages are exactly those languages that can be accepted by valence automata over F ₂. This is a reinterpretation of the classical theorem of Chomsky and Schützenberger. To the authors’ knowledge, the result (1) is the first completeness result for L o g C F L in the area of combinatorial group theory.

Finally, for the result (1) it suffices to show N P-hardness of knapsack for the graph groups $\mathbb {G}(\mathsf {C4})$ (where C 4 is a cycle on four nodes) and $\mathbb {G}(\mathsf {P4})$ (where P 4 is a cycle on four nodes). Our proof for $\mathbb {G}(\mathsf {C4})$ is based on ideas from [44]. For $\mathbb {G}(\mathsf {P4})$, we apply a technique that was first used by Aalbersberg and Hoogeboom [1] to show that the intersection non-emptiness problem for regular trace languages is undecidable for P 4.

This work presents all results with full proofs from the extended abstracts in [39, 40] that concern the knapsack problem and the subset sub problem for graph groups (the paper [39] also contains transfer results on HNN-extensions and free products with amalgamations, which do not appear here).

Related work

Implicitly, the knapsack problem was also studied by Babai et al. [4], where it is shown that knapsack for commutative matrix groups over algebraic number fields can be solved in polynomial time.

The knapsack problem is a special case of the more general rational subset membership problem. A rational subset of a finitely generated monoid M is the homomorphic image in M of a regular language over the generators of M. In the rational subset membership problem for M the input consists of a rational subset L ⊆ M (specified by a finite automaton) and an element m ∈ M and it is asked whether m ∈ L. It was shown in [38] that the rational subset membership problem for a graph group G is decidable if and only if the corresponding graph has (i) no induced cycle on four nodes (C 4) and (ii) no induced path on four nodes (P 4). For the decidable cases, the precise complexity is open.

Knapsack for G can be also viewed as the question, whether a word equation z ₁ z ₂⋯z _n = 1, where z ₁,…,z _n are variables, together with constraints of the form {g ⁿ∣n ≥ 0} for the variables has a solution in G. Such a solution is a mapping φ: {z ₁,…,z _n }→ G such that φ(z ₁ z ₂⋯z _n ) evaluates to 1 in G and all constraints are satisfied. For another class of constraints (so-called normalized rational constraints, which do not cover constraints of the form {g ⁿ∣n ≥ 0}), solvability of general word equations was shown to be decidable (P S P A C E-complete) for graph groups by Diekert and Muscholl [14]. This result was extended in [13] to a transfer theorem for graph products. A graph product is specified by a finite simple graph where every node is labeled with a group. The associated group is obtained from the free product of all vertex groups by allowing elements from adjacent groups to commute. Note that decidability of knapsack is not preserved under graph products: It is not even preserved under direct products (see the above mentioned results from [33]).

2 Basic Concepts

2.1 Complexity Classes

We assume that the reader is familiar with the complexity classes P and N P, see e.g. [3] for details. The class T C ⁰ is a very low circuit complexity class; it is contained for instance in N C ¹ and deterministic logspace. We will use this class only in Section 4.4, and even that part can be understood without the precise definition of T C ⁰. Nevertheless, for completeness we include the formal definition of T C ⁰.

A language L ⊆{0,1}^∗ belongs to T C ⁰ if there exists a family (C _n ) _n≥0 of Boolean circuits with the following properties:

• C _n has n distinguished input gates x ₁,…,x _n and a distinguished output gate o.

• C _n accepts exactly the words from L ∩{0,1}ⁿ, i.e., if the input gate x _i receives the input a _i ∈{0,1}, then the output gate o evaluates to 1 if and only if a ₁ a ₂⋯a _n ∈ L.

• Every circuit C _n is built up from input gates, and-gates, or-gates, and majority-gates, where a majority gate evaluates to 1 if at least half of its input wires carry 1.

• All gates have unbounded fan-in, which means that there is no bound on the number of input wires for a gate.

• There is a polynomial p(n) such that C _n has at most p(n) many gates.

• There is a constant c such that every C _n has depth at most c, where the depth is the length of a longest path from an input gate x _i to the output gate o.

This is in fact the definition of non-uniform T C ⁰. Here “non-uniform” means that the mapping n↦C _n is not restricted in any way. In particular, it can be non-computable. For algorithmic purposes one usually adds some uniformity requirement to the above definition. The most “uniform” version of T C ⁰ is D L O G T I M E-uniform T C ⁰. For this, one encodes the gates of each circuit C _n by bit strings of length O(log n). Then the circuit family (C _n ) _n≥0 is called D L O G T I M E-uniform if (i) there exists a deterministic Turing machine that computes for a given gate u ∈{0,1}^∗ of C _n (|u|∈ O(log n)) in time O(log n) the type (of gate u, where the types are x ₁,…,x _n , and, or, majority) and (ii) there exists a deterministic Turing machine that decides for two given gate u,v ∈{0,1}^∗ of C _n (|u|,|v|∈ O(log n)) in time O(log n) whether there is a wire from gate u to gate v. In the following, we always implicitly refer to D L O G T I M E-uniform T C ⁰.

If the language L in the above definition of T C ⁰ is defined over a non-binary alphabet Σ then one first has to fix a binary encoding of words over Σ. When talking about hardness for T C ⁰, one has to use reductions, whose computational power are below T C ⁰, e.g. A C ⁰-Turing-reductions. The precise definition of these reductions is not important for our purpose. Important problems that are complete for T C ⁰ are:

• The languages {w ∈{0,1}^∗∣|w|₀ ≤|w|₁} and {w ∈{0,1}^∗∣|w|₀ = |w|₁}, where |w| _a denotes the number of occurrences of a in w, see e.g. [50].

• The computation (of a certain bit) of the binary representation of the product of two (or any number of) binary encoded integers [25].

• The computation (of a certain bit) of the binary representation of the integer quotient of two binary encoded integers [25].

• The word problem for every infinite solvable linear group [32].

• The conjugacy problem for the Baumslag-Solitar group B S(1,2) [15].

The class LogCFL consists of all problems that are logspace reducible to a context-free language. The class LogCFL is included in the parallel complexity class N C ² and has several alternative characterizations (see e.g. [48, 50]):

• logspace bounded alternating Turing-machines with polynomial tree size,

• semi-unbounded Boolean circuits of polynomial size and logarithmic depth, and

• logspace bounded auxiliary pushdown automata with polynomial running time.

For our purposes, the last characterization is most suitable. An AuxPDA (for auxiliary pushdown automaton) is a nondeterministic pushdown automaton with a two-way input tape and an additional work tape. Here we only consider AuxPDA with the following two restrictions:

• The length of the work tape is restricted to O(log n) for an input of length n (logspace bounded).

• There is a polynomial p(n), such that every computation path of the AuxPDA on an input of length n has length at most p(n) (polynomially time bounded).

Whenever we speak of an AuxPDA in the following, we implicitly assume that the AuxPDA is logspace bounded and polynomially time bounded. Deterministic AuxPDA are defined in the obvious way. The class of languages that are accepted by AuxPDA is exactly LogCFL, whereas the class of languages accepted by deterministic AuxPDA is L o g D C F L (the closure of the deterministic context-free languages under logspace reductions) [48].

2.2 Finite automata

We will use standard notions from automata theory. We define a nondeterministic finite automaton (NFA) as a tuple $\mathcal {A} = (Q,{\Sigma }, {\Delta }, q_{0}, F)$, where Q is a finite set of states, Σ is the input alphabet, q ₀ ∈ Q is the initial state, F ⊆ Q is the final state, and Δ ⊆ Q ×Σ^∗× Q is a finite set of transitions. Note that such an automaton can read several (including zero) many symbols in a transition. A spelling NFA is an NFA $\mathcal {A} = (Q,{\Sigma }, {\Delta }, q_{0}, F)$, where Δ ⊆ Q × Σ × Q. The language accepted by $\mathcal {A}$ is denoted with $L(\mathcal {A})$. If we allow ε-transitions of the form (q,ε,p), which is the case for general (non-spelling) NFA, then we can assume that the set of final states F consists of a unique state q _f , in which case we write $\mathcal {A} = (Q,{\Sigma }, {\Delta },$ q ₀,q _f ).

An acyclic NFA is a (not necessarily spelling) NFA $\mathcal {A} = (Q,{\Sigma }, {\Delta }, q_{0}, q_{f})$ such that the relation {(p,q)∣∃w ∈Σ^∗ : (p,w,q) ∈ Δ} is acyclic. An acyclic loop NFA is a (not necessarily spelling) NFA $\mathcal {A} = (Q,{\Sigma }, {\Delta }, q_{0}, q_{f})$ such that there exists a linear order ≼ on Δ having the property that for all (p,u,q),(q,v,r) ∈ Δ it holds (p,u,q) ≼ (q,v,r). Thus, an acyclic loop NFA is obtained from an acyclic NFA by attaching to some of the states a unique loop.

2.3 Vectors and Semilinear Sets

Vectors will be column vectors, unless we explicitly speak of row vectors. For a vector $x \in \mathbb {Z}^{k}$ we denote with x ^T the corresponding row vector. Given a vector $x=(x_{1},\ldots ,x_{k})^{T} \in \mathbb {Z}^{k}$, we use three different standard norms:

$$\begin{array}{@{}rcl@{}} \|x\|_{\infty} &=& \max \{|x_{i}| \mid 1 \leq i \leq k\}, \end{array} $$

(1)

$$\begin{array}{@{}rcl@{}} \|x\|_{2} &=& \sqrt{\sum\limits_{1 \leq i \leq k} {x_{i}^{2}}}, \end{array} $$

(2)

$$\begin{array}{@{}rcl@{}} \|x\|_{1} &=& \sum\limits_{i=1}^{m} |x_{i}| . \end{array} $$

(3)

For a subset $T\subseteq \mathbb {N}^{k}$, we write T ^⊕ for the smallest subset of $\mathbb {N}^{k}$ that contains T ∪{0} and is closed under addition. A subset $S\subseteq \mathbb {N}^{k}$ is called linear if there is a vector $x\in \mathbb {N}^{k}$ and a finite set $F\subseteq \mathbb {N}^{k}$ such that S = x + F ^⊕. Note that a set is linear if and only if it can be written as $x+A\mathbb {N}^{t}$ for some $x\in \mathbb {N}^{k}$ and some matrix $A\in \mathbb {N}^{k\times t}$. Here, $A\mathbb {N}^{t}$ denotes the set of all vectors A y for $y\in \mathbb {N}^{t}$. A semilinear set is a finite union of linear sets. If $S=\bigcup _{i=1}^{n} x_{i}+F_{i}^{\oplus }$ for $x_{1},\ldots ,x_{n}\in \mathbb {N}^{k}$ and finite sets $F_{1},\ldots ,F_{n}\subseteq \mathbb {N}^{k}$, then the tuple (x ₁,F ₁,…,x _n ,F _n ) is a semilinear representation of S. Saying that a set S is effectively semilinear means that a semilinear representation for S can be computed from certain input data.

2.4 Words and straight-line programs

For a word w we denote with alph(w) the set of symbols occurring in w. The length of the word w is |w|.

A straight-line program, briefly SLP, is basically a context-free grammar that produces exactly one string. To ensure this, the grammar has to be acyclic and deterministic (every variable has a unique production where it occurs on the left-hand side). Formally, an SLP is a tuple $\mathcal {G} = (V,{\Sigma },\text {rhs},S)$, where V is a finite set of variables (or nonterminals), Σ is the terminal alphabet, S ∈ V is the start variable, and rhs maps every variable to a right-hand side rhs(A) ∈ (V ∪ Σ)^∗. We require that there is a linear order < on V such that B < A whenever B ∈ N ∩alph(rhs(A)). Every variable A ∈ V derives to a unique string $\text {val}_{\mathcal {G}}(A)$ by iteratively replacing variables by the corresponding right-hand sides, starting with A. Finally, the string derived by $\mathcal {G}$ is $\text {val}(\mathcal {G}) = \text {val}_{\mathcal {G}}(S)$.

Let $\mathcal {G} = (V,{\Sigma },\text {rhs},S)$ be an SLP. The size of $\mathcal {G}$ is $|\mathcal {G}| = {\sum }_{A \in V} |\text {rhs}(A)|$, i.e., the total length of all right-hand sides. A simple induction shows that for every SLP $\mathcal {G}$ of size m one has $|\text {val}(\mathcal {G})| \leq \mathcal {O}(3^{m/3}) \subseteq 2^{\mathcal {O}(m)}$ [9, proof of Lemma 1]). On the other hand, it is straightforward to define an SLP $\mathcal {H}$ of size 2n such that $|\text {val}(\mathcal {H})| \geq 2^{n}$. This justifies to see an SLP $\mathcal {G}$ as a compressed representation of the string $\text {val}(\mathcal {G})$, and exponential compression rates can be achieved in this way. More details on SLPs can be found in the survey [35].

2.5 Groups

We assume that the reader has some basic knowledge concerning (finitely generated) groups (see e.g. [41] for further details). Let G be a finitely generated group, and let A be a finite generating set for G. Then, elements of G can be represented by finite words over the alphabet A ^±1 = A ∪ A ⁻¹. The free group generated by A is denoted by F(A) and we also write F _n for F(A) if |A| = n. Elements of F(A) can be identified with irreducible words over A ^±1, i.e., words that do not contain a factor of the form a a ⁻¹ or a ⁻¹ a for a ∈ A. The length |g| of g ∈ F(A) is the the length of the irreducible word corresponding to g.

A group G is finitely presented if there exists a finite alphabet A and a finite set of words R ⊆ (A ^±1)^∗ (which we identify with a subset of F(A)) such that G is isomorphic to F(A)/N, where N is the smallest normal subgroup of F(A) that contains R. The group F(A)/N is usually denoted by 〈A∣R〉 and the pair (A,R) is called a presentation of G. Elements of R are called relators. With 〈A∣u ₁ = v ₁,…,u _k = v _k 〉 we denote the group $\langle A \mid u_{1}v_{1}^{-1}, \ldots , u_{k} v_{k}^{-1} \rangle$.

It is a standard fact that an element g ∈ F(A) represents the identity of G = 〈A∣R〉 if and only if g can be written in F(A) as a product ${\prod }_{i=1}^{n} c_{i}^{-1} r_{i} c_{i}$, where c _i ∈ F(A) and r _i ∈ R ∪ R ⁻¹. The minimal such n is called the area of g (with respect to the presentation (A,R)). The Dehn function of the presentation (A,R) is the function $f \colon \mathbb {N} \to \mathbb {N}$ that maps n to the maximal area of an element g ∈ F(A) such that g = 1 in F(A) and |g|≤ n. We say that a finitely presented group G has a polynomial Dehn function if there exists a presentation for G whose Dehn function is bounded by a polynomial.

2.6 Knapsack and exponent equations

Let G be a finitely generated group, and fix a generating set A for G. An exponent equation over G is an equation of the form

$$\begin{array}{@{}rcl@{}} v_{0} u_{1}^{x_{1}} v_{1} u_{2}^{x_{2}} v_{2} {\cdots} u_{n}^{x_{n}} v_{n} = 1 \end{array} $$

(4)

where u ₁,u ₂,…,u _n ,v ₀,v ₁,…,v _n ∈ G are group elements that are given by finite words over the alphabet A ^±1 and x ₁,x ₂,…,x _n are not necessarily distinct variables. Such an exponent equation is solvable if there exists a mapping $\sigma \colon \{x_{1}, \ldots ,x_{n}\} \to \mathbb {N}$ such that v ₀ u1σ(x ₁)v ₁ u1σ(x ₂)v ₂⋯u n σ(x _n )v _n = 1 in the group G. If there is no danger of confusion, we will simplify notation and not distinguish between variables and solutions. Solvability of exponent equations over G is the following computational problem:

Input: :

An exponent equation E over G (where elements of G are specified by words over the alphabet A ^±1.)

Question: :

Is E solvable?

It suffices to consider exponent equations of the form $u_{1}^{x_{1}} u_{2}^{x_{2}} {\cdots } u_{n}^{x_{n}} v_{n} = 1$: using conjugation, we can replace an equation $v_{0} u_{1}^{x_{1}} v_{1} u_{2}^{x_{2}} v_{2} {\cdots } u_{n}^{x_{n}} v = 1$ by $(v_{0} u_{1} v_{0}^{-1})^{x_{1}} (v_{0}v_{1}) u_{2}^{x_{2}} v_{2} {\cdots } u_{n}^{x_{n}} v_{n} = 1$ and then continue in this way. On the other hand, in some of our proof it is convenient to allow the group elements v ₀,v ₁,…,v _n−1 in (4).

The knapsack problem for the group G is the restriction of solvability of exponent equations over G to exponent equations of the form $u_{1}^{x_{1}} u_{2}^{x_{2}} {\cdots } u_{n}^{x_{n}} u^{-1} = 1$ or, equivalently, $u_{1}^{x_{1}} u_{2}^{x_{2}} {\cdots } u_{n}^{x_{n}} = u$ where the exponent variables x ₁,…,x _n have to be pairwise different.

We will also study a compressed version of exponent equations over G, where elements of G are given by SLPs over A ^±1. A compressed exponent equation is an exponent equation $v_{0} u_{1}^{x_{1}} v_{1} u_{2}^{x_{2}} v_{2} {\cdots } u_{n}^{x_{n}} v_{n} = 1$ where the group elements u ₁,u ₂,…,u _n ,v ₀,v ₁,…,v _n ∈ G are given by SLPs over the terminal alphabet A ^±1. The sum of the sizes of these SLPs is the size of the compressed exponent equation.

Let us define solvability of compressed exponent equations over G as the following computational problem:

Input: :

A compressed exponent equation E over G.

Question: :

Is E solvable?

The compressed knapsack problem for G is defined analogously. Note that with this terminology, the classical knapsack problem for binary encoded integers is the compressed knapsack problem for the group $\mathbb {Z}$. The binary encoding of an integer can be easily transformed into an SLP over the alphabet {a,a ⁻¹} (where a is a generator of $\mathbb {Z}$) and vice versa. Here, the number of bits in the binary encoding and the size of the SLP are linearly related.

Remark 2.1

Let us comment on the difference between the knapsack problem and solvability of exponent equations. The main concern of this work is the knapsack problem, where all variables are distinct. However, the methods we use in Section 3 for obtaining the N P upper bound apply to general (even compressed) exponent equations. Our proof of the LogCFL upper bound in Section 4, on the other hand, only works for the knapsack problem.

Nevertheless, all our (complexity) lower bounds are with respect to the knapsack problem.

It is a simple observation that the decidability and complexity of solvability of (compressed) exponent equations over G as well as the (compressed) knapsack problem for G does not depend on the chosen finite generating set for the group G. Therefore, we do not have to mention the generating set explicitly in these problems.

Remark 2.2

Since we are dealing with a group, one might also allow solution mappings $\sigma \colon \{x_{1}, \ldots ,x_{n}\} \to \mathbb {Z}$ to the integers. But this variant of solvability of (compressed) exponent equations (knapsack, respectively) can be reduced to the above version, where σ maps to $\mathbb {N}$, by simply replacing a power $u_{i}^{x_{i}}$ by $u_{i}^{x_{i}} (u^{-1}_{i})^{y_{i}}$, where y _i is a fresh variable.

This work is concerned with decidability and complexity of solvability of exponent equations for so-called graph groups, which will be introduced in the next section.

2.7 Traces and graph groups

Let (A,I) be a finite simple graph. In other words, the edge relation I ⊆ A × A is irreflexive and symmetric. It is also called the independence relation, and (A,I) is called an independence alphabet. The relation D = (A × A) ∖ I is also called the associated dependence relation and (A,D) is called the associated dependence alphabet. We consider the monoid $\mathbb {M}(A, I) = A^{*}/\!\!\equiv _{I}$, where ≡ _I is the smallest congruence relation on the free monoid A ^∗ that contains all pairs (a b,b a) with a,b ∈ A and (a,b) ∈ I. This monoid is called a trace monoid or partially commutative free monoid; it is cancellative, i.e., x y = x z or y x = z x implies y = z. Elements of $\mathbb {M}(A, I)$ are called Mazurkiewicz traces or simply traces. The trace represented by the word u is denoted by [u] _I , or simply u if no confusion can arise. For a language L ⊆ A ^∗ we denote with [L] _I = {u ∈ A ^∗∣∃v ∈ L : u≡ _I v} its partially commutative closure. The length of the trace [u] _I is |[u] _I | = |u| and its alphabet is alph([u] _I ) = alph(u). It is easy to see that these definitions do not depend on the concrete word that represents the trace [u] _I . For subsets B,C ⊆ A we write B I C for B × C ⊆ I. If B = {a} we simply write a I C. For traces s,t we write s I t for alph(s)I alph(t). The empty trace [ε] _I is the identity element of the monoid $\mathbb {M}(A,I)$ and is denoted by 1. A trace t is connected if we cannot factorize t as t = u v with u ≠ 1≠v and u I v.

A trace $t \in \mathbb {M}(A,I)$ can be visualized by its dependence graph D _t . To define D _t , choose an arbitrary word w = a ₁ a ₂⋯a _n , a _i ∈ A, with t = [w] _I and define D _t = ({1,…,n},E,λ), where E = {(i,j)∣i < j,(a _i ,a _j ) ∈ D} and λ(i) = a _i . If we identify isomorphic dependence graphs, then this definition is independent of the chosen word representing t. Moreover, the mapping t↦D _t is injective. As a consequence of the representation of traces by dependence graphs, one obtains Levi’s lemma for traces (see e.g. [16, p. 74]), which is one of the fundamental facts in trace theory. The formal statement is as follows.

Lemma 2.3 (Levi’s lemma)

Let $u_{1}, \ldots , u_{m}, v_{1}, \ldots , v_{n} \in \mathbb {M}(A,I)$ . Then

$$u_{1}u_{2} {\cdots} u_{m} = v_{1} v_{2} {\cdots} v_{n}$$

if and only ifthere exist $w_{i,j} \in \mathbb {M}(A,I) (1 \leq i \leq m$, 1 ≤ j ≤ n)suchthat

• u _i = w _i,1 w _i,2⋯w _i,n for every 1 ≤ i ≤ m,

• v _j = w _1,j w _2,j ⋯w _m,j for every 1 ≤ j ≤ n,and

• w _i,j I w _k,ℓ if 1 ≤ i < k ≤ m and n ≥ j > ℓ ≥ 1.

The situation in the lemma will be visualized by a diagram of the following kind. The i–th column corresponds to u _i , the j–th row corresponds to v _j , and the intersection of the i–th column and the j–th row represents w _i,j . Furthermore w _i,j and w _k,ℓ are independent if one of them is left-above the other one.

A consequence of Levi’s Lemma is that trace monoids are cancellative, i.e., u s v = u t v implies s = t for all traces $s,t,u,v\in \mathbb {M}(A,I)$.

Let $s,t \in \mathbb {M}(A,I)$ be traces. We say that s is a prefix of t if there is a trace $r\in \mathbb {M}(A,I)$ with s r = t. Moreover, we define ρ(t) as the number of prefixes of t. We will use the following statement from [5].

Lemma 2.4

Let $t \in \mathbb {M}(A,I)$ be a trace of length n. Then $\rho (t) \in \mathcal {O}(n^{\alpha })$ , where α is the size of a largest clique of the associated dependence alphabet (A,D).

With an independence alphabet (A,I) we associate the finitely presented group

$$\mathbb{G}(A,I) = \langle A \mid ab=ba \ ((a,b) \in I) \rangle. $$

Such a group is called a graph group, or right-angled Artin group,³ or free partially commutative group. Here, we use the term graph group. Graph groups received a lot of attention in group theory during the last few years, mainly due to their rich subgroup structure [6, 10, 20], and their relationship to low dimensional topology (via so-called virtually special groups) [2, 24, 51]. We represent elements of $\mathbb {G}(A,I)$ by traces over an extended independence alphabet. For this, let A ⁻¹ = {a ⁻¹∣a ∈ A} be a disjoint copy of the alphabet A, and let A ^±1 = A ∪ A ⁻¹. We define (a ⁻¹)⁻¹ = a and for a word w = a ₁ a ₂⋯a _n with a _i ∈ A ^±1 we define $w^{-1} = a^{-1}_{n} {\cdots } a^{-1}_{2} a^{-1}_{1}$. This defines an involution (without fixed points) on (A ^±1)^∗. We extend the independence relation I to A ^±1 by (a ^x,b ^y) ∈ I for all (a,b) ∈ I and x,y ∈{−1,1}. Then, there is a canonical surjective morphism $h \colon \mathbb {M}(A^{\pm 1},I) \to \mathbb {G}(A,I)$ that maps every symbol a ∈ A ^±1 to the corresponding group element. Of course, h is not injective, but we can easily define a subset $\text {IRR}(A^{\pm 1},I) \subseteq \mathbb {M}(A^{\pm 1}, I)$ of irreducible traces such that h restricted to IRR(A ^±1,I) is bijective. The set IRR(A ^±1,I) consists of all traces $t \in \mathbb {M}(A^{\pm 1},I)$ such that t does not contain a factor [a a ⁻¹] _I with a ∈ A ^±1, i.e., there do not exist $u, v \in \mathbb {M}(A^{\pm 1}, I)$ and a ∈ A ^±1 such that in $\mathbb {M}(A^{\pm 1}, I)$ we have a factorization t = u[a a ⁻¹] _I v. For every trace t there exists a corresponding irreducible normal form that is obtained by removing from t factors [a a ⁻¹] _I with a ∈ A ^±1 as long as possible. It can be shown that this reduction process is terminating (which is trivial since it reduces the length) and confluent (in [34] a more general confluence lemma for graph products of monoids is shown). Hence, the irreducible normal form of t does not depend on the concrete order of reduction steps. For a group element $g \in \mathbb {G}(A,I)$ we denote with |g| the length of the unique trace t ∈IRR(A ^±1,I) such that h(t) = g.

For a trace t = [u] _I (u ∈ (A ^±1)^∗) we can define t ⁻¹ = [u ⁻¹] _I . This is well-defined, since u≡ _I v implies u ⁻¹≡ _I v ⁻¹. The following lemma will be important; see also [14, Lemma 23]).

Lemma 2.5

Let s,t ∈IRR(A ^±1,I). Then there exist unique factorizations s = u p and t = p ⁻¹ v in $\mathbb {M}(A^{\pm 1},I)$ such that u v ∈IRR(A ^±1,I). Hence, uv is the irreducible normal form of st.

3 Compressed knapsack and exponent equations

The goal of this section is to show the following result:

Theorem 3.1

Let (A,I) be a fixed independence alphabet. Solvability of compressed exponent equations over the graph group $\mathbb {G}(A,I)$ is in NP.

As a byproduct, we will prove that the set of solutions of an exponent equation over a fixed graph group is semilinear.

In Section 3.1 we will analyze the possible factorizations of a power u ^x, where u is a connected trace and x is a natural number, into a product y ₁ y ₂⋯y _m of traces. In Section 3.2 we will describe the set of solution of a trace equation p u ^x s = q v ^y t, where u and v are connected traces and $x,y \in \mathbb {N}$ are variables. In Section 3.3 we state an auxiliary result on linear diophantine equations that follows easily from a result of [19]. In Section 3.4 we prove the key lemma that allows us to reduce an exponent equations over a graph group to a system of trace equations. Finally, in Section 3.5 we prove Theorem 3.1. Section 3.6 deals with the compressed solvability of exponent equations in a graph group that is also part of the input (and given by the defining independence alphabet).

3.1 Factorizations of Powers

Based on Levi’s lemma we prove in this section a factorization result for powers of a connected trace. We start with the case that we factorize such a power into two factors.

Lemma 3.2

Let $u \in \mathbb {M}(A,I) \setminus \{1\}$ be a connected trace. Then, for all $x \in \mathbb {N}$ and all traces y ₁,y ₂ the following two statements are equivalent:

• (i) u ^x = y ₁ y ₂

• (ii) There exist $l,k,c \in \mathbb {N}$ and traces s,p such that: y ₁ = u ^l s , y ₂ = p u ^k , s p = u ^c , l + k + c = x , and c ≤|A|.

Proof

That (ii) implies (i) is clear. It remains to prove that (i) implies (ii). Assume that u ^x = y ₁ y ₂ holds. The case that x ≤|A| is trivial. Hence, assume that x ≥|A| + 1. We apply Levi’s lemma (Lemma 2.3) to the identity u ^x = y ₁ y ₂:

Let A _i = alph(u _1,2⋯u _i,2). Then A _i ⊆ A _i+1. If A ₁ = ∅ then u _1,2 = 1 and we can go to Case 2 below. Otherwise, assume that A ₁≠∅. In that case there must exist 1 ≤ i ≤|A| such that A _i = A _i+1, which implies alph(u _i+1,2) ⊆ A _i . Since u _i+1,1 I(u _1,2⋯u _i,2) we also have u _i+1,1 I u _i+1,2. Since u is connected, we have u _i+1,1 = 1 or u _i+1,2 = 1. We can therefore distinguish the following two cases:

Case 1. There exists 1 ≤ i ≤|A| + 1 such that u _i,1 = 1. Then u _i,2 = u, which implies u _j,1 = 1 for all j > i (since u _i,2 I u _j,1):

Let s = u _1,1 u _2,1⋯u _i−1,1 and p = u _1,2 u _2,2⋯u _i−1,2. Thus, y ₁ = u ⁰ s, y ₂ = p u ^x−i+1 and s p = u ⁱ⁻¹ with i − 1 ≤|A|, and the conclusion of the lemma holds.

Case 2. There exists 1 ≤ i ≤|A| + 1 such that u _i,2 = 1. Then, u _j,2 = 1 for all j < i (since u _i,1 = u and u _j,2 I u _i,1):

Let $y^{\prime }_{1} = u_{i+1,1} {\cdots } u_{x,1}$. Hence, $u^{x-i} = y^{\prime }_{1} y_{2}$. We can use induction to get factorizations $y^{\prime }_{1} = u^{l} s$, y ₂ = p u ^k, and s p = u ^c with c ≤|A| and k + l + c = x − i. Finally, we have $y_{1} = u^{i} y^{\prime }_{1} = u^{i+l} s$, which shows the conclusion of the lemma. □

Now we lift Lemma 3.2 to an arbitrary number of factors.

Lemma 3.3

Let $u \in \mathbb {M}(A,I) \setminus \{1\}$ be a connected trace and $m \in \mathbb {N}$ , m ≥ 2. Then, for all $x \in \mathbb {N}$ and traces y ₁,…,y _m the following two statements are equivalent:

• (i) u ^x = y ₁ y ₂⋯y _m .

• (ii) There exist traces p _i,j (1 ≤ j < i ≤ m), s _i (1 ≤ i ≤ m)and numbers $x_{i}, c_{j} \in \mathbb {N} (1 \leq i \leq m$ , 1 ≤ j ≤ m − 1)such that:

  • $y_{i} = ({\prod }_{j=1}^{i-1} p_{i,j}) u^{x_{i}} s_{i}$ for all 1 ≤ i ≤ m ,

  • p _i,j I p _k,l if j < l < k < i and $p_{i,j} I (u^{x_{k}} s_{k})$ if j < k < i , ⁴

  • s _m = 1and for all 1 ≤ j < m,$s_{j} {\prod }_{i=j+1}^{m} p_{i,j} = u^{c_{j}}$,

  • c _j ≤|A|for all 1 ≤ j ≤ m − 1,

  • $x = {\sum }_{i=1}^{m} x_{i} + {\sum }_{i=1}^{m-1} c_{i}$.

Proof

Let us first show that (ii) implies (i). Assume that (ii) holds. Then we get

$$y_{1} y_{2} {\cdots} y_{m} = \prod\limits_{i=1}^{m} \left((\prod\limits_{j=1}^{i-1} p_{i,j}) u^{x_{i}} s_{i} \right). $$

The independencies p _i,j I p _k,l for j < l < k < i and $p_{i,j} I (u^{x_{k}} s_{k})$ for j < k < i yield

$$\begin{array}{@{}rcl@{}} && \prod\limits_{i=1}^{m} \left(\left(\prod\limits_{j=1}^{i-1} p_{i,j}\right) u^{x_{i}} s_{i} \right) \\ &=& u^{x_{1}} s_{1} p_{2,1} {\cdots} p_{m,1} u^{x_{2}} s_{2} p_{3,2} {\cdots} p_{m,2} u^{x_{3}} s_{3} {\cdots} u^{x_{m-1}} s_{m-1} p_{m,m-1} u^{x_{m}} s_{m} \\ &=& u^{x_{1}} u^{c_{1}} u^{x_{2}} u^{c_{2}} u^{x_{3}} {\cdots} u^{c_{m-1}} u^{x_{m}} = u^{x} . \end{array} $$

We now prove that (i) implies (ii) by induction on m. So, assume that u ^x = y ₁ y ₂⋯y _m . The case m = 2 follows directly from Lemma 3.2. Now assume that m ≥ 3. By Lemma 3.2 there exist factorizations $y_{1} = u^{x_{1}} s_{1}$, $y_{2} {\cdots } y_{m} = p_{1} u^{x^{\prime }}$, and $s_{1}p_{1} = u^{c_{1}}$ with c ₁ ≤|A| and x ₁ + x ^′ + c ₁ = x. Levi’s lemma applied to $y_{2} {\cdots } y_{m} = p_{1} u^{x^{\prime }}$ gives the following diagram:

There exist $y^{\prime }_{i}$ with $y_{i} = p_{i,1} y^{\prime }_{i}$ (2 ≤ i ≤ m), $y^{\prime }_{2} {\cdots } y^{\prime }_{m} = u^{x^{\prime }}$, and $y^{\prime }_{j} I p_{i,1}$ for j < i. By induction on m we get factorizations

$$y^{\prime}_{i} = \prod\limits_{j=2}^{i-1} p_{i,j} u^{x_{i}} s_{i}$$

for 2 ≤ i ≤ m such that for all 2 ≤ j < i ≤ m:

• p _i,j I p _k,l if j < l < k < i and $p_{i,j} I (u^{x_{k}} s_{k})$ if j < k < i,

• s _m = 1 and for all 2 ≤ j < m, $s_{j} {\prod }_{i=j+1}^{m} p_{i,j} = u^{c_{j}}$ for some c _j ≤|A|,

• $x^{\prime } = {\sum }_{i=2}^{m} x_{i} + {\sum }_{i=2}^{m-1} c_{i}$.

Since $y^{\prime }_{j} I p_{i,1}$ for j < i we get p _i,1 I p _j,k for 1 < k < j < i and $p_{i,1} I u^{x_{j}} s_{j}$ for 1 < j < i. Finally, we have

$$s_{1} \prod\limits_{i=2}^{m} p_{i,1} = s_{1} p_{1} = u^{c_{1}} \\</p><p class="noindent">$$

and

$$x = x_{1} + c_{1} + x^{\prime} = x_{1} + c_{1} + \sum\limits_{i=2}^{m} x_{i} + {\sum}_{i=2}^{m-1} c_{i} = \sum\limits_{i=1}^{m} x_{i} + \sum\limits_{i=1}^{m-1} c_{i} .</p><p class="noindent">$$

This proves the lemma. □

Remark 3.4

In Section 3.5 we will apply Lemma 3.3 in order to replace an equation u ^x = y ₁ y ₂⋯y _m (where x,y ₁,…,y _m are variables and u is a concrete connected trace) by an equivalent disjunction. Note that the length of all factors p _i,j and s _i above is bounded by |A|⋅|u|. Hence, one can guess these traces as well as the numbers c _j ≤|A| (the guess results in a disjunction). We can also guess which of the numbers x _i are zero and which are greater than zero. After these guesses we can verify the independencies p _i,j I p _k,l (j < l < k < i) and $p_{i,j} I (u^{x_{k}} s_{k})$ (j < k < i), and the identities s _m = 1, $s_{j} {\prod }_{i=j+1}^{m} p_{i,j} = u^{c_{j}}$ (1 ≤ j < m). If one of them does not hold, the specific guess does not contribute to the disjunction. In this way, we can replace the equation u ^x = y ₁ y ₂⋯y _m by a disjunction of formulas of the form

$$\exists x_{i} > 0 \; (i \in K): x = \sum\limits_{i\in K} x_{i} + c \wedge \bigwedge\limits_{i \in K} y_{i} = p_{i} u^{x_{i}} s_{i} \wedge \bigwedge\limits_{i \in [1,m] \setminus K} y_{i} = p_{i} s_{i} , $$

where K ⊆ [1,m], c ≤|A|⋅ (m − 1) and the p _i ,s _i are concrete traces of length at most |A|⋅ (m − 1) ⋅|u|. The number of disjuncts in the disjunction will not be important for our purpose.

3.2 Automata for partially commutative closures

In this section, we present several automata constructions that are well-known from the theory of recognizable trace languages [11, Chapter 2]). For our purpose we need upper bounds on the size (the size of an automaton is its number of states) of the constructed automata. In our specific situation we can obtain better bounds than those obtained from the known constructions. Therefore, we present the constructions in detail.

Let us fix an independence alphabet (A,I) and let $\mathcal {A} = (Q, A, {\Delta }, q_{0}, F)$ be an NFA over the alphabet A. Then, $\mathcal {A}$ is an I-diamond NFA if for all (a,b) ∈ I and all transitions (p,a,q),(q,b,r) ∈ Δ there exists a state q ^′ such that (p,b,q ^′),(q ^′,a,r) ∈ Δ. For an I-diamond automaton we have $L(\mathcal {A}) = [L(\mathcal {A})]_{I}$. The NFA $\mathcal {A}$ is memorizing if (i) every state is accessible from the initial state q ₀ and (ii) there is a mapping α: Q → 2^A such that for every word w ∈ A ^∗, if $q_{0} \stackrel {w}{\longrightarrow }_{\mathcal {A}} q$, then α(q) = alph(w).

Lemma 3.5

Let $\mathcal {A}_{1}$ and $\mathcal {A}_{2}$ be I-diamond NFA and let n _i be the number of states of $\mathcal {A}_{i}$ . Assume that $\mathcal {A}_{2}$ is memorizing. Then there exists an I-diamond NFA for $[L(\mathcal {A}_{1}) L(\mathcal {A}_{2})]_{I}$ with n ₁ ⋅ n ₂ many states.

Proof

Let $\mathcal {A}_{i} = (Q_{i}, A, {\Delta }_{i}, q_{0,i}, F_{i})$ for i ∈{1,2}. Let α ₂: Q ₂ → 2^A be the map witnessing the fact that $\mathcal {A}_{2}$ is memorizing. Then, let

$$\mathcal{A} = (Q_{1} \times Q_{2}, A, {\Delta}, \langle q_{0,1}, q_{0,2}\rangle, F_{1} \times F_{2}), $$

where

$$\begin{array}{@{}rcl@{}} {\Delta} & = & \{ (\langle p_{1}, p_{2}\rangle, a, \langle q_{1}, p_{2}\rangle) \mid (p_{1}, a, q_{1}) \in {\Delta}_{1}, a I \alpha_{2}(p_{2}) \} \cup \\ & & \{ (\langle p_{1}, p_{2}\rangle, a, \langle p_{1}, q_{2}\rangle) \mid (p_{2}, a, q_{2}) \in {\Delta}_{2}\} . \end{array} $$

Claim 1. $\mathcal {A}$ is an I-diamond NFA.

To show this claim, let us consider two consecutive transitions in $\mathcal {A}$ labeled with independent letters. The following four cases can be distinguished, where we assume (a,b) ∈ I in all four cases:

Case 1. $\langle p_{1}, p_{2}\rangle \stackrel {a}{\longrightarrow }_{\mathcal {A}} \langle q_{1}, p_{2}\rangle \stackrel {b}{\longrightarrow }_{\mathcal {A}} \langle r_{1}, p_{2}\rangle$, where $p_{1} \stackrel {a}{\longrightarrow }_{\mathcal {A}_{1}} q_{1} \stackrel {b}{\longrightarrow }_{\mathcal {A}_{1}} r_{1}$ and a I α ₂(p ₂), b I α ₂(q ₂). Since $\mathcal {A}_{1}$ is an I-diamond NFA, there exists a state $q^{\prime }_{1} \in Q_{1}$ such that $p_{1} \stackrel {b}{\longrightarrow }_{\mathcal {A}_{1}} q^{\prime }_{1} \stackrel {a}{\longrightarrow }_{\mathcal {A}_{1}} r_{1}$. We get $\langle p_{1}, p_{2}\rangle \stackrel {b}{\longrightarrow }_{\mathcal {A}} \langle q^{\prime }_{1}, p_{2}\rangle \stackrel {a}{\longrightarrow }_{\mathcal {A}} \langle r_{1}, p_{2}\rangle$.

Case 2. $\langle p_{1}, p_{2}\rangle \stackrel {a}{\longrightarrow }_{\mathcal {A}} \langle p_{1}, q_{2}\rangle \stackrel {b}{\longrightarrow }_{\mathcal {A}} \langle p_{1}, r_{2}\rangle$, where $p_{2} \stackrel {a}{\longrightarrow }_{\mathcal {A}_{2}} q_{2} \stackrel {b}{\longrightarrow }_{\mathcal {A}_{2}} r_{2}$. We can conclude as in Case 1 using the fact that $\mathcal {A}_{2}$ is an I-diamond NFA.

Case 3. $\langle p_{1}, p_{2}\rangle \stackrel {a}{\longrightarrow }_{\mathcal {A}} \langle q_{1}, p_{2}\rangle \stackrel {b}{\longrightarrow }_{\mathcal {A}} \langle q_{1}, q_{2}\rangle$, where $p_{1} \stackrel {a}{\longrightarrow }_{\mathcal {A}_{1}} q_{1}$, $p_{2} \stackrel {b}{\longrightarrow }_{\mathcal {A}_{2}} q_{2}$, and a I α ₂(p ₂). Since α ₂(q ₂) = α ₂(p ₂) ∪{b} and (a,b) ∈ I we have a I α ₂(q ₂). We get $\langle p_{1}, p_{2}\rangle \stackrel {b}{\longrightarrow }_{\mathcal {A}} \langle p_{1}, q_{2}\rangle \stackrel {a}{\longrightarrow }_{\mathcal {A}} \langle q_{1}, q_{2}\rangle$.

Case 4. $\langle p_{1}, p_{2}\rangle \stackrel {a}{\longrightarrow }_{\mathcal {A}} \langle p_{1}, q_{2}\rangle \stackrel {b}{\longrightarrow }_{\mathcal {A}} \langle q_{1}, q_{2}\rangle$, where $p_{2} \stackrel {a}{\longrightarrow }_{\mathcal {A}_{2}} q_{2}$, $p_{1} \stackrel {b}{\longrightarrow }_{\mathcal {A}_{1}} q_{1}$, and b I α ₂(q ₂). Since α ₂(q ₂) = α ₂(p ₂) ∪{a}, we also have b I α ₂(p ₂). This implies $\langle p_{1}, p_{2}\rangle \stackrel {b}{\longrightarrow }_{\mathcal {A}} \langle q_{1}, p_{2}\rangle \stackrel {a}{\longrightarrow }_{\mathcal {A}} \langle q_{1}, q_{2}\rangle$.

This concludes the proof of Claim 1. To show that $L(\mathcal {A}) = [L(\mathcal {A}_{1}) L(\mathcal {A}_{2})]_{I}$ it suffices to show the following claim:

Claim 2. For all w ∈ A ^∗, p ₁ ∈ Q ₁, and p ₂ ∈ Q ₂, the following two statements are equivalent :

• (i) $\langle q_{0,1}, q_{0,2}\rangle \stackrel {w}{\longrightarrow }_{\mathcal {A}} \langle p_{1}, p_{2}\rangle$

• (ii) There are w ₁,w ₂ ∈ A ^∗ such that w≡ _I w ₁ w ₂, $q_{0,1} \stackrel {w_{1}}{\longrightarrow }_{\mathcal {A}_{1}} p_{1}$, and $q_{0,2} \stackrel {w_{2}}{\longrightarrow }_{\mathcal {A}_{2}} p_{2}$.

Let us first prove that (i) implies (ii). The case w = ε is clear. Hence, let w = w ^′ a. Then there exist $p^{\prime }_{1} \in Q_{1}$, $p^{\prime }_{2} \in Q_{2}$ such that

$$\langle q_{0,1}, q_{0,2}\rangle \stackrel{w^{\prime}}{\longrightarrow}_{\mathcal{A}} \langle p^{\prime}_{1}, p^{\prime}_{2}\rangle</p><p class="noindent">\stackrel{a}{\longrightarrow}_{\mathcal{A}} \langle p_{1}, p_{2}\rangle . $$

By induction, there exists a factorization $w^{\prime } \equiv _{I} w^{\prime }_{1} w^{\prime }_{2}$ such that $q_{0,1} \stackrel {w^{\prime }_{1}}{\longrightarrow }_{\mathcal {A}_{1}} p^{\prime }_{1}$ and $q_{0,2} \stackrel {w^{\prime }_{2}}{\longrightarrow }_{\mathcal {A}_{2}} p^{\prime }_{2}$. Note that $\text {alph}(w^{\prime }_{2}) = \alpha _{2}(p^{\prime }_{2})$. There are two cases:

Case 1. $p^{\prime }_{1} \stackrel {a}{\longrightarrow }_{\mathcal {A}_{1}} p_{1}$, $p_{2} = p^{\prime }_{2}$, and $a I \alpha _{2}(p^{\prime }_{2})$. Thus, $a I w^{\prime }_{2}$. We get $w = w^{\prime }a \equiv _{I} w^{\prime }_{1} w^{\prime }_{2} a \equiv _{I} (w^{\prime }_{1} a) w^{\prime }_{2}$. Let $w_{1} = w^{\prime }_{1} a$ and $w_{2} = w^{\prime }_{2}$. We get $q_{0,1} \stackrel {w_{1}}{\longrightarrow }_{\mathcal {A}_{1}} p_{1}$ and $q_{0,2} \stackrel {w_{2}}{\longrightarrow }_{\mathcal {A}_{2}} p_{2}$.

Case 2. $p^{\prime }_{2} \stackrel {a}{\longrightarrow }_{\mathcal {A}_{2}} p_{2}$ and $p_{1} = p^{\prime }_{1}$. Let $w_{1} = w^{\prime }_{1}$ and $w_{2} = w^{\prime }_{2} a$. Thus, $w = w^{\prime }a \equiv _{I} w^{\prime }_{1} w^{\prime }_{2} a = w_{1} w_{2}$. Moreover, we have $q_{0,1} \stackrel {w_{1}}{\longrightarrow }_{\mathcal {A}_{1}} p_{1}$ and $q_{0,2} \stackrel {w_{2}}{\longrightarrow }_{\mathcal {A}_{2}} p_{2}$.

Let us now prove that (ii) implies (i). Assume that w≡ _I w ₁ w ₂, $q_{0,1} \stackrel {w_{1}}{\longrightarrow }_{\mathcal {A}_{1}} p_{1}$, and $q_{0,2} \stackrel {w_{2}}{\longrightarrow }_{\mathcal {A}_{2}} p_{2}$. We have to show that $\langle q_{0,1}, q_{0,2}\rangle \stackrel {w}{\longrightarrow }_{\mathcal {A}} \langle p_{1}, p_{2}\rangle$. But since $\mathcal {A}$ is an I-diamond NFA, it suffices to show that $\langle q_{0,1}, q_{0,2}\rangle \stackrel {w_{1} w_{2}}{\longrightarrow }_{\mathcal {A}} \langle p_{1}, p_{2}\rangle$, which follows directly from the assumption and the definition of $\mathcal {A}$ (note that α ₂(q _0,2) = ∅). This concludes the proof of Claim 2 and hence the proof of the lemma. □

In general, for a regular language L ⊆ A ^∗, the partially commutative closure [L] _I is not regular. For instance, if A = {a,b} and a I b, then [(a b)^∗] _I consists of all words with the same number of a’s as b’s. On the other hand, it is well known that if [v] _I is a connected trace, then [v ^∗] _I is regular (in fact, there is a more general result, known as Ochmanski’s theorem [11, Section 2.3]). For our purpose we need an upper on the size of an I-diamond NFA for [v ^∗] _I (with [v] _I connected). Recall that ρ(u) is the number of different prefixes of the trace u.

Lemma 3.6

Let u ∈ A ^∗∖{ε}such that the trace [u] _I is connected. There is a memorizing I-diamond NFA for [u ^∗] _I of size 2 ⋅ ρ([u] _I )^|A| .

Proof

The following construction can be found in [43, Proposition 5]) for the more general case of the partially commutative closure of a so-called loop-connected automaton. We present the construction in our simplified situation, since the NFA gets slightly smaller.

In the following, we identify u with the trace [u] _I . We first define a non-memorizing I-diamond NFA $\mathcal {A}$ for [u ^∗] _I of size ρ(u)^|A|. Then, we show that by adding an additional bit to all states, we can get a memorizing I-diamond NFA $\mathcal {A}$ for [u ^∗] _I of size 2 ⋅ ρ(u)^|A|. The idea for the construction of $\mathcal {A}$ is implicitly contained in the proof of Lemma 3.2: Assume that the automaton wants to read a word w ∈ [u ^∗] _I and a prefix y ₁ of w is already read. Then [y ₁] _I must be of the form u ^k s, where s is a prefix of u ^c for some c ≤|A|. Moreover, by choosing k maximal, we can assume that u is not a prefix of the trace s.

We define $\mathcal {A} = (Q, A, {\Delta }, q_{0}, F)$, where Q is the set of all prefixes s of some trace in u ^∗ such that u is not a prefix of s.

Let us estimate |Q|. Observe that if s ∈ Q, then Lemma 3.2 tells us that s = u ^k s ^′, where s ^′ is a prefix of u ^c with c ≤|A|. Since u is not a prefix of s, we have k = 0 and hence s = s ^′ is a prefix of u ^c. According to Levi’s lemma, s is of the form u ₁ u ₂⋯u _c such that every trace u _i is a non-empty prefix of u. Hence |Q|≤ ρ(u)^|A|.

Note that Q is prefix closed. Moreover, if |u| = 1, then 1 is the only state. The initial state as well as the final state is the empty trace 1. The set of transition tuples is

$${\Delta} = \{ (s, a, sa) \mid s, sa \in Q, a \in A \} \cup \{ (s,a,t) \mid s,t \in Q, sa = ut \text{ in} \mathbb{M}(A,I) \} . $$

Claim 1. $\mathcal {A}$ is an I-diamond NFA.We can distinguish the following four cases, where (a,b) ∈ I in all four cases:Case 1. (s,a,s a),(s a,b,s a b) ∈ Δ. Since s a b = s b a ∈ Q, we must have s b ∈ Q. Hence, we have (s,b,s b),(s b,a,s b a) ∈ Δ.Case 2. (s,a,t),(t,b,v) ∈ Δ, where s a = u t and t b = u v. From s a = u t and the fact that u is not a prefix of s we obtain with Levi’s lemma the factorizations s = u ^′ t and u = u ^′ a with a I t. From a I t and (a,b) ∈ I we get a I t b, in contradiction to t b = u v = u ^′ a v. Hence, Case 2 cannot occur.Case 3. (s,a,t),(t,b,t b) ∈ Δ, where s a = u t. As above, we get factorizations s = u ^′ t and u = u ^′ a with a I t. We claim that s b ∈ Q. First, u is not a prefix of sb: If s b = u v for some trace v, then u ^′ t b = s b = u v = u ^′ a v. Hence t b = a v, in contradiction to a I t b.

It remains to show that sb is a prefix of a trace in u ^∗. Since t b ∈ Q there exists a trace x such that t b x ∈ u ^∗. Hence, s b a x = s a b x = u t b x ∈ u ^∗, i.e., sb is a prefix of a trace in u ^∗. Thus, s b ∈ Q and hence (s,b,s b) ∈ Δ. Moreover s b a = s a b = u t b. Thus, (s b,a,t b) ∈ Δ.Case 4. (s,a,s a),(s a,b,t) ∈ Δ, where s a b = u t. We get s a = u ^′ t, u = u ^′ b and b I t for some trace u ^′. We distinguish two subcases. First assume that u is not a prefix of sb. We claim that s b ∈ Q. Since t ∈ Q, there exist a trace x with t x ∈ u ^∗. Hence, s b a x = s a b x = u t x ∈ u ^∗. Thus, sb is a prefix of a trace in u ^∗ and does not have u as a prefix. Hence s b ∈ Q and (s,b,s b) ∈ Δ. Moreover, s b a = s a b = u t, and thus (s b,a,t) ∈ Δ.

Now assume that u is a prefix of sb. Let s b = u v. Since u is not a prefix of s ∈ Q, we get s = u ^″ v, u = u ^″ b and b I v for some trace u ^″. Hence, u ^″ b = u = u ^′ b, i.e., u ^″ = u ^′ and s = u ^′ v. Thus, u ^′ t = s a = u ^′ v a, which implies t = v a. Since t ∈ Q, we have v ∈ Q. We get (s,b,v),(v,a,t) ∈ Δ. This concludes the proof of Claim 1.The following claim shows that $L(\mathcal {A}) = [u^{*}]_{I}$:Claim 2. For every state s ∈ Q and every w ∈ A ^∗ the following two statements are equivalent:

• (i) $1 \stackrel {w}{\longrightarrow }_{\mathcal {A}} s$

• (ii) [w] _I = u ^k s for some k ≥ 0

Let us first show by induction on |w| that (i) implies (ii). The case w = ε is clear. So, assume that w = w ^′ a. There must exist a state s ^′∈ Q such that

$$1 \stackrel{w^{\prime}}{\longrightarrow}_{\mathcal{A}} s^{\prime} \stackrel{a}{\longrightarrow}_{\mathcal{A}} s.</p><p class="noindent">$$

By induction, we get [w ^′] _I = u ^ℓ s ^′ for some ℓ ≥ 0. The definition of the transitions of $\mathcal {A}$ implies that [w] _I = [w ^′ a] _I = u ^ℓ s ^′ a = u ^k s, where k ∈{ℓ,ℓ + 1}.

For the direction from (ii) to (i) assume that [w] _I = u ^k s for some k ≥ 0. We have to show that $1 \stackrel {w}{\longrightarrow }_{\mathcal {A}} s$. Let s ^′∈ A ^∗ such that s = [s ^′] _I . Hence, w≡ _I u ^k s ^′. Since $\mathcal {A}$ is an I-diamond NFA, it suffices to show that . But this follows directly from the definition of $\mathcal {A}$.

To make $\mathcal {A}$ memorizing, we first keep only those states that are accessible from the initial state 1. Then, we add an extra bit to every state that indicates whether we have already seen a completed occurrence of u. Thus, the new set of states is Q ×{0,1}, the initial state is the pair (1,0), and the final states are (1,0) and (1,1). The new set of transitions is

$$\{ ((s,i), a, (t,i)) \mid (s,a,t) \in {\Delta} \} \cup \{ ((s,i),a,(t,1)) \mid s,t \in Q, sa = ut, i \in \{0,1\} \} . $$

Then, we can define the α-mapping by α(s,i) = alph(u ⁱ s). The resulting NFA is still an I-diamond NFA. □

A direct consequence of Lemma 3.5 and 3.6 is:

Lemma 3.7

Let p,u,s ∈ A ^∗ with u≠ε and [u] _I connected. There is an NFA for [p u ^∗ s] _I of size 2 ⋅ ρ([p] _I ) ⋅ ρ([s] _I ) ⋅ ρ([u] _I )^|A| .

Proof

We first construct an I-diamond NFA for [p] _I (which is identified here with the set of words {w ∈ A ^∗∣w≡ _I p}) with ρ([p] _I ) many states by taking the set of all prefixes of [p] _I as states. Then, we construct a memorizing I-diamond NFA for [u ^∗] _I with 2 ⋅ ρ([u] _I )^|A| states using Lemma 3.6. By Lemma 3.5 we get an I-diamond automaton for [p u ^∗] _I with 2 ⋅ ρ([p] _I ) ⋅ ρ([u] _I )^|A| many states. Finally, we construct an I-diamond NFA for [s] _I with ρ([s] _I ) many states by taking the set of all prefixes of [s] _I as states. This NFA is also memorizing. Hence, we can apply Lemma 3.5 to get an NFA for [p u ^∗ s] _I with 2 ⋅ ρ([p] _I ) ⋅ ρ([s] _I ) ⋅ ρ([u] _I )^|A| many states. □

The main lemma from this section that will be needed later is:

Lemma 3.8

Let $p,q,u,v,s,t \in \mathbb {M}(A,I)$ with u ≠ 1and v ≠ 1connected. Let m = max{ρ(p),ρ(q),ρ(s),ρ(t)}and n = max{ρ(u),ρ(v)}. Then the set

$$L(p,u,s,q,v,t) := \{ (x,y) \in \mathbb{N} \times \mathbb{N} \mid p u^{x} s = q v^{y} t \}$$

is semilinear andis a union of $\mathcal {O}(m^{8} \cdot n^{4 |A|})$manylinear sets of the form $\{ (a+bz, c+dz) \mid z \in \mathbb {N} \}$with $a,b,c,d \in \mathcal {O}(m^{8} \cdot n^{4 |A|})$.

Proof

We identify the traces p,q,u,v,s,t with words representing these traces. By Lemma 3.6 there exists an NFA for [p u ^∗ s] _I of size

$$k = 2 \cdot \rho(p) \cdot \rho(s) \cdot \rho(u)^{|A|} \leq 2 \cdot m^{2} \cdot n^{|A|} $$

and an NFA for [q v ^∗ t] _I of size

$$\ell = 2 \cdot \rho(q) \cdot \rho(t) \cdot \rho(v)^{|A|} \leq 2 \cdot m^{2} \cdot n^{|A|}. $$

Then, we obtain an NFA $\mathcal {A}$ for L = [p u ^∗ s] _I ∩ [q v ^∗ t] _I with k ⋅ ℓ states. We are only interested in the length of words from L. Hence, we replace in $\mathcal {A}$ every transition label by the symbol a. The resulting NFA $\mathcal {B}$ is defined over a unary alphabet. Let $P = \{ n \mid a^{n} \in L(\mathcal {B}) \}$. By [49, Theorem 1]), the set P can be written as a union

$$P = \bigcup\limits_{i=1}^{r} \{ b_{i} + c_{i} \cdot z \mid z \in \mathbb{N} \} $$

with $r \in \mathcal {O}(k^{2} \ell ^{2}) \subseteq \mathcal {O}(m^{8} \cdot n^{4 |A|})$ and $b_{i}, c_{i} \in \mathcal {O}(k^{2} \ell ^{2})\subseteq \mathcal {O}(m^{8} \cdot n^{4 |A|})$. For every 1 ≤ i ≤ r and $z \in \mathbb {N}$ there must exist a pair $(x,y) \in \mathbb {N} \times \mathbb {N}$ such that

$$b_{i} + c_{i} \cdot z = |ps| + |u| \cdot x = |qt| + |v| \cdot y. $$

In particular, b _i ≥|p s|, b _i ≥|q t|, |u| divides b _i −|p s| and c _i , and |v| divides b _i −|q t| and c _i . We get:

$$L(p,u,s,q,v,t) = \bigcup\limits_{i=1}^{r} \left\{ \left(\frac{b_{i}-|ps|}{|u|} + \frac{c_{i}}{|u|} \cdot z, \frac{b_{i}-|qt|}{|v|} + \frac{c_{i}}{|v|} \cdot z \right) \; \left|\; z \right. \in \mathbb{N}\right\} $$

This shows the lemma. □

3.3 Linear Diophantine Equations

We will also need a bound on the norm of a smallest vector in a certain kind of semilinear sets. We will easily obtain this bound from a result from [19].

Lemma 3.9

Let $A \in \mathbb {Z}^{n \times m}$ , $\overline {a} \in \mathbb {Z}^{n}$ , $C \in \mathbb {N}^{k \times m}$ , $\overline {c} \in \mathbb {N}^{k}$ . Let β be an upper bound for the absolute value of all entries in A, $\overline {a}$ , C, $\overline {c}$ . The set

$$ L = \{ C \overline{z} + \overline{c} \mid \overline{z} \in \mathbb{N}^{m}, A \overline{z} = \overline{a} \} \subseteq \mathbb{N}^{k} $$

(5)

is semilinear. Moreover, if L≠∅ then there is y ∈ L with

$$\|y||_{\infty} \leq \beta + (\sqrt{m})^{n} \cdot m \cdot (m+1) \cdot \beta^{n+1}. $$

Proof

Semilinearity of L is clear since the set is Presburger-definable. For the size bound, we use a result from [19] to bound the size of a smallest positive solution of the system $A \overline {z} = \overline {a}$. Let $A \in \mathbb {Z}^{n \times m}$, $B \in \mathbb {Z}^{p \times m}$, $\overline {a} \in \mathbb {Z}^{n \times 1}$, $\overline {b} \in \mathbb {Z}^{p \times 1}$. Let r = rank(A), and $s = \text {rank}\left (\begin {array}{ll} A \\ B \end {array}\right )$. Let M be an upper bound on the absolute values of all (s − 1) × (s − 1)- or (s × s)-subdeterminants of the (n + p) × (m + 1)-matrix $\left (\begin {array}{lll} A & \overline {a} \\ B & \overline {b} \end {array}\right )$, which are formed with at least r rows from the matrix $(A \;\, \overline {a})$. Then by the main result of [19], the system $A \overline {z} = \overline {a}$, $B \overline {z} \geq \overline {b}$ has an integer solution if and only if it has an integer solution $\overline {z}$ such that the absolute value of every entry of $\overline {z}$ is bounded by (m + 1)M.

In our situation, we set p = m, B is the m-dimensional identity matrix, and $\overline {b}$ is the vector with all entries equal to zero (then $B \overline {z} \geq \overline {b}$ expresses that all entries of z are positive). Since $\left (\begin {array}{l} A \\ B \end {array}\right )$ is an (n + m) × m-matrix we get $s = \text {rank}\left (\begin {array}{l} A \\ B \end {array}\right ) \leq m$. We claim that the absolute values of all (s × s)-subdeterminants (and also all (s − 1) × (s − 1)-subdeterminants) of the matrix $\left (\begin {array}{ll} A & \overline {a} \\ B & \overline {b} \end {array}\right )$ are bounded by $(\sqrt {m})^{n} \cdot \beta ^{n}$. To see this, select s rows and s columns from $\left (\begin {array}{ll} A & \overline {a} \\ B & \overline {b} \end {array}\right )$ and consider the resulting submatrix D.

Let d ₁,…,d _s be the row vectors of D. By Hadamard’s inequality we have

$$\det (D) \leq \prod\limits_{i=1}^{s} \|d_{i}\|_{2} . $$

Assume that the row vectors $d_{1}, \ldots , d_{s^{\prime }}$ (s ^′≤ n) of D are from the n × (m + 1)-submatrix $(A, \overline {a})$. The remaining row vectors $d_{s^{\prime }+1}, \ldots , d_{s}$ of D are from $(B, \overline {b})$. Then, every d _i (s ^′ + 1 ≤ i ≤ s) is a zero vector or a unit vector and hence has Euklidean norm 0 or 1. We therefore have

$$\det (D) \leq \prod\limits_{i=1}^{s} \|d_{i}\|_{2} \leq \prod\limits_{i=1}^{s^{\prime}} \|d_{i}\|_{2} \leq (\sqrt{m})^{n} \cdot \beta^{n} . $$

It follows that if $A \overline {z} = \overline {a}$ has a positive solution, then it has a positive solution where every entry is bounded by $(m+1) \cdot (\sqrt {m})^{n} \cdot \beta ^{n}$.

By substituting every entry of $\overline {z}$ by $(\sqrt {m})^{n} \cdot \beta ^{n}$ in $C \overline {z} + \overline {c}$, it follows that if the set L in (5) is non-empty, then it contains a vector with all entries bounded by $\beta + (\sqrt {m})^{n} \cdot m \cdot (m+1) \cdot \beta ^{n+1}$. □

3.4 Reduction from graph groups to trace monoids

As usual, we fix an independence alphabet (A,I). In the following we will consider reduction rules on sequences of traces. For better readability we separate the consecutive traces in such a sequence by commas. Let u ₁,u ₂,…,u _n ∈IRR(A ^±1,I) be irreducible traces. The sequence u ₁,u ₂,…,u _n is I-freely reducible if the sequence u ₁,u ₂,…,u _n can be reduced to the empty sequence ε by the following rules:

• u _i ,u _j → u _j ,u _i if u _i I u _j

• u _i ,u _j → ε if $u_{i} = u_{j}^{-1}$ in $\mathbb {M}(A^{\pm 1},I)$

• u _i → ε if u _i = ε.

A concrete sequence of these rewrite steps leading to the empty sequence is a reduction of the sequence u ₁,u ₂,…,u _n . Such a reduction can be seen as a witness for the fact that u ₁ u ₂⋯u _n = 1 in $\mathbb {G}(A,I)$. On the other hand, u ₁ u ₂⋯u _n = 1 does not necessarily imply that u ₁,u ₂,…,u _n has a reduction. For instance, the sequence a ⁻¹,a b,b ⁻¹ has no reduction. But we can show that every sequence which multiplies to 1 in $\mathbb {G}(A,I)$ can be refined (by factorizing the elements of the sequence) such that the resulting refined sequence has a reduction. For getting an NP-algorithm, it is important to bound the length of the refined sequence exponentially in the length of the initial sequence.

Lemma 3.10

Let n ≥ 2and u ₁,u ₂,…,u _n ∈IRR(A ^±1,I). If u ₁ u ₂⋯u _n = 1in $\mathbb {G}(A,I)$ , then there exist factorizations $u_{i} = u_{i,1} {\cdots } u_{i,k_{i}}$ in $\mathbb {M}(A^{\pm 1},I)$ such that the sequence

$$u_{1,1}, \ldots, u_{1,k_{1}}, \; u_{2,1}, \ldots, u_{2,k_{2}}, \; \ldots, u_{n,1}, \ldots, u_{n,k_{n}} $$

is I-freely reducible.Moreover, ${\sum }_{i=1}^{n} k_{i} \leq 2^{n} - 2$.

Proof

We prove the lemma by induction on n. The case n = 2 is trivial (we must have $u_{2} = u_{1}^{-1}$). If n ≥ 3 then by Lemma 2.5 we can factorize u ₁ and u ₂ as u ₁ = p s and u ₂ = s ⁻¹ t in $\mathbb {M}(A^{\pm 1},I)$ such that v := p t is irreducible. Hence, v u ₃⋯u _n = 1 in $\mathbb {G}(A,I)$. By induction, we obtain factorizations p t = v = v ₁⋯v _k and $u_{i} = v_{i,1} {\cdots } v_{i,k_{i}}$ (3 ≤ i ≤ n) in $\mathbb {M}(A^{\pm 1},I)$ such that the sequence

$$ v_{1}, \ldots, v_{k}, \; v_{3,1}, \ldots, v_{3,k_{3}}, \ldots, v_{n,1}, \ldots, v_{n,k_{n}} $$

(6)

is I-freely reducible. Moreover,

$$k + \sum\limits_{i=3}^{n} k_{i} \leq 2^{n-1} - 2 . $$

By applying Levi’s lemma to the trace identity p t = v ₁ v ₂⋯v _k , we obtain factorizations v _i = u _i,1 u _i,2 in $\mathbb {M}(A^{\pm 1},I)$ such that p = u _1,1⋯u _k,1, t = u _1,2⋯u _k,2, and u _i,2 I u _j,1 for 1 ≤ i < j ≤ k.

Fix a concrete reduction of the sequence (6). We now consider the following sequence

$$ u_{1,1}, \ldots, u_{k,1}, s, \; s^{-1}, u_{1,2}, \ldots, u_{k,2}, \; \tilde{v}_{3,1}, \ldots, \tilde{v}_{3,k_{3}}, \ldots, \tilde{v}_{n,1}, \ldots, \tilde{v}_{n,k_{n}}, $$

(7)

where the subsequence $\tilde {v}_{i,j}$ is $u_{l,2}^{-1}, u_{l,1}^{-1}$ if v _i,j cancels against v _l in our fixed reduction of (6) (which, in particular, implies that $v_{i,j} = v_{l}^{-1} = u_{l,2}^{-1} u_{l,1}^{-1}$ in $\mathbb {M}(A^{\pm 1},I)$). Otherwise (i.e., if v _i,j does not cancel against any v _l in our fixed reduction), we set $\tilde {v}_{i,j} = v_{i,j}$.

Note that u _1,1⋯u _k,1 s = p s = u ₁, s ⁻¹ u _1,2⋯u _k,2 = s ⁻¹ t = u ₂ and the concatenation of all traces in $\tilde {v}_{i,1}, \ldots , \tilde {v}_{i,k_{i}}$ is u _i for 3 ≤ i ≤ n. Hence, it remains to show that the sequence (7) is I-freely reducible. First of all, u _1,1,…,u _k,1,s,s ⁻¹,u _1,2,…,u _k,2 reduces to u _1,1,…,u _k,1,u _1,2,…,u _k,2, which can be rearranged to u _1,1,u _1,2,u _2,1,u _2,2,…,u _k,1,u _k,2 using the fact that u _i,2 I u _j,1 for 1 ≤ i < j ≤ k. Finally, the sequence

$$u_{1,1} u_{1,2}, u_{2,1} u_{2,2}, \ldots, u_{k,1} u_{k,2}, \tilde{v}_{3,1}, \ldots, \tilde{v}_{3,k_{3}}, \ldots, \tilde{v}_{n,1}, \ldots, \tilde{v}_{n,k_{n}} $$

is I-freely reducible. The definition of $\tilde {v}_{i,j}$ allows to basically apply the fixed reduction of (6) to this sequence.

The number of traces in the sequence (7) can be estimated as

$$2 k + 2 + 2 \cdot \sum\limits_{i=3}^{n} k_{i} \leq 2 \cdot (2^{n-1} - 2) + 2 = 2^{n}-2. $$

This concludes the proof of the lemma. □

3.5 Semilinearity, exponential bounds, and N P-membership

We now come to the main technical result of Section 3. Let α ≤|A| be the size of a largest clique of the dependence alphabet (A,D) corresponding to (A,I).

Theorem 3.11

Let $u_{1}, u_{2}, \ldots , u_{n} \in \mathbb {G}(A,I) \setminus \{1\}$ , $v_{0}, v_{1}, \ldots , v_{n} \in \mathbb {G}(A,I)$ and let x ₁,…,x _n be variables (we may have x _i = x _j for i≠j ) ranging over $\mathbb {N}$ . Then, the set of solutions of the exponent equation

$$v_{0} u_{1}^{x_{1}} v_{1} u_{2}^{x_{2}} v_{2} {\cdots} u_{n}^{x_{n}} v_{n} = 1$$

iseffectively semilinear. Moreover, if there is a solution, then there is a solution with$x_{i} \in \mathcal {O}(2^{3 (\alpha n)^{2} + 7 \alpha n} \cdot \mu ^{8\alpha (n+1)} \cdot \nu ^{8 \alpha |A| (n+1)})$,where

• $\mu \in \mathcal {O}(|A|^{\alpha } \cdot 2^{2 \alpha ^{2} n} \cdot \lambda ^{\alpha })$,

• $\nu \in \mathcal {O}(\lambda ^{\alpha })$,and

• λ = max{|u ₁|,|u ₂|,…,|u _n |,|v ₀|,|v ₁|,…,|v _n |}.

Proof

Let us choose irreducible traces for u ₁,u ₂,…,u _n ,v ₀,v ₁,…,v _n ; we denote these traces with the same letters as the group elements. A trace u is called cyclically reduced if there do not exist a ∈ A ^±1 and v such that u = a v a ⁻¹. For every trace u there exist unique traces p,w such that u = p w p ⁻¹ and w is cyclically reduced (since the reduction relation a ⁻¹ x a → x is terminating and confluent [12, Lemma 16]). These traces p and w can be computed in polynomial time. Note that for a cyclically reduced irreducible trace w, every power w ⁿ is irreducible. Let $u_{i} = p_{i} w_{i} p_{i}^{-1}$ with w _i cyclically reduced. Note that w _i cannot be the empty trace since u _i ≠1 in $\mathbb {G}(A,I)$. By replacing every $u_{i}^{x_{i}}$ by $p_{i} w_{i}^{x_{i}} p_{i}^{-1}$, we can assume that all u _i are cyclically reduced, irreducible, and non-empty. In case one of the traces u _i is not connected, we can write u _i as u _i = u _i,1 u _i,2 with u _i,1 I u _i,2 and u _i,1≠1≠u _i,2. Thus, we can replace the power $u_{i}^{x_{i}}$ by $u_{i,1}^{x_{i}} u_{i,2}^{x_{i}}$. Note that u _i,1 and u _i,2 are still irreducible and cyclically reduced. By doing this, the number n from the theorem multiplies by at most α (which is the maximal number of pairwise independent letters). In order to keep the notation simple we still use the letter n for the number of u _i , but at the end of the proof we have to multiply n by α in the derived bound. Hence, for the further proof we can assume that all u _i are connected, irreducible and cyclically reduced. Let λ be the maximal length of one of the traces u ₁,u ₂,…,u _n ,v ₀,v ₁,…,v _n , which does not increase by the above preprocessing.

We now apply Lemma 3.10 to the equation

$$ v_{0} u_{1}^{x_{1}} v_{1} u_{2}^{x_{2}} v_{2} {\cdots} u_{n}^{x_{n}} v_{n} = 1, $$

(8)

where every $u_{i}^{x_{i}}$ is viewed as a single factor. Note that by our preprocessing, all factors $u_{1}^{x_{1}}, u_{2}^{x_{2}}, \ldots , u_{n}^{x_{n}}, v_{0}, \ldots , v_{n}$ are irreducible (for all choices of the x _i ). By taking a disjunction over (i) all possible factorizations of the 2n + 1 factors $u_{1}^{x_{1}}, u_{2}^{x_{2}}, \ldots , u_{n}^{x_{n}}, v_{0}, \ldots , v_{n}$ into totally at most 2²ⁿ⁺¹ − 2 factors and (ii) all possible reductions of the resulting refined factorization of $v_{0} u_{1}^{x_{1}} v_{1} u_{2}^{x_{2}} v_{2} {\cdots } u_{n}^{x_{n}} v_{n}$, it follows that (8) is equivalent to a disjunction of statements of the following form: There exist traces $y_{i,1}, \ldots , y_{i,k_{i}}$ (1 ≤ i ≤ n) and $z_{i,1}, \ldots , z_{i,l_{i}}$ (0 ≤ i ≤ n) such that in $\mathbb {M}(A^{\pm 1},I)$ the following hold:

• (a) $u_{i}^{x_{i}} = y_{i,1} {\cdots } y_{i,k_{i}}$ (1 ≤ i ≤ n)

• (b) $v_{i} = z_{i,1} {\cdots } z_{i,l_{i}}$ (0 ≤ i ≤ n)

• (c) y _i,j I y _k,l for all (i,j,k,l) ∈ J ₁

• (d) y _i,j I z _k,l for all (i,j,k,l) ∈ J ₂

• (e) z _i,j I z _k,l for all (i,j,k,l) ∈ J ₃

• (f) $y_{i,j} = y_{k,l}^{-1}$ for all (i,j,k,l) ∈ M ₁

• (g) $y_{i,j} = z_{k,l}^{-1}$ for all (i,j,k,l) ∈ M ₂

• (h) $z_{i,j} = z_{k,l}^{-1}$ for all (i,j,k,l) ∈ M ₃

Here, the numbers k _i and l _i sum up to at most 2²ⁿ⁺¹ − 2 (hence, some k _i can be exponentially large, whereas l _i can be bound by the length of v _i , which is at most λ). The tuple sets J ₁,J ₂,J ₃ collect all independencies between the factors y _i,j , z _k,l that are necessary to carry out the chosen reduction of the refined left-hand side in (8). Similarly, the tuple sets M ₁,M ₂,M ₃ tell us which of the factors y _i,j , z _k,l cancels against which of the factors y _i,j , z _k,l in our chosen reduction of the refined left-hand side in (8). Note that every factor y _i,j (resp., z _k,l ) appears in exactly one of the identities (f), (g), (h) (since in the reduction every factor cancels against another unique factor). Let us also remark that in the rest of proof we no longer work in the graph group $\mathbb {G}(A,I)$. All statements refer to the trace monoid $\mathbb {M}(A^{\pm 1},I)$.

Next, we simplify our statements. Since the v _i are concrete traces (of length at most λ), we can take a disjunction over all possible factorizations $v_{i} = v_{i,1} {\cdots } v_{i,l_{i}}$ (1 ≤ i ≤ n + 1) such that v _i,j I v _k,l for all (i,j,k,l) ∈ J ₃ and $v_{i,j} = v_{k,l}^{-1}$ for all (i,j,k,l) ∈ M ₃. This allows to replace every variable z _i,j by a concrete trace v _i,j . Statements of the form v _i,j I v _k,l and $v_{i,j} = v_{k,l}^{-1}$ can, of course, be eliminated. Moreover, if there is an identity $y_{i,j} = v_{k,l}^{-1}$ then we can replace the variable y _i,j by the concrete trace $v_{k,l}^{-1}$ (of length at most λ).

In the next step, we eliminate trace equations of the form $u_{i}^{x_{i}} = y_{i,1} {\cdots } y_{i,k_{i}}$ (1 ≤ i ≤ n). Note that some of the variables y _i,j might have been replaced by concrete traces of length at most λ. We apply to each of these trace equations Lemma 3.3, or better Remark 3.4. This allows us to replace every equation $u_{i}^{x_{i}} = y_{i,1} {\cdots } y_{i,k_{i}}$ (1 ≤ i ≤ n) by a disjunction of statements of the following form: There exist numbers x _i,j > 0 (1 ≤ i ≤ n, j ∈ K _i ) such that

• $x_{i} = c_{i} + {\sum }_{j \in K_{i}} x_{i,j}$ for all 1 ≤ i ≤ n,

• $y_{i,j} = p_{i,j} u_{i}^{x_{i,j}} s_{i,j}$ for all 1 ≤ i ≤ n, j ∈ K _i ,

• y _i,j = p _i,j s _i,j for all 1 ≤ i ≤ n, j ∈ [1,k _i ] ∖ K _i .

Here, K _i ⊆ [1,k _i ], the c _i are concrete numbers with c _i ≤|A|⋅ (k _i − 1), and the p _i,j ,s _i,j are concrete traces of length at most |A|⋅ (k _i − 1) ⋅|u _i |≤|A|⋅ (2²ⁿ⁺¹ − 3) ⋅ λ. Hence, the lengths of these traces can be exponential in n.

Note that since x _i > 0, we know the alphabet of $y_{i,j} = p_{i,j} u_{i}^{x_{i,j}} s_{i,j}$ (resp., y _i,j = p _i,j s _i,j ). This allows us to replace all independencies of the form y _i,j I y _k,l for (i,j,k,l) ∈ J ₁ (see (c)) and y _i,j I z _k,l for (i,j,k,l) ∈ J ₂ (see (d)) by concrete truth values. Note that all variables z _k,l have already been replaced by concrete traces. If y _i,j was already replaced by a concrete trace, then we can determine from an equation $y_{i,j} = p_{i,j} u_{i}^{x_{i,j}} s_{i,j}$ the exponent x _i,j . Since y _i,j was replaced by a trace of length at most λ (a small number), we get x _i,j ≤ λ, and we can replace x _i,j in $x_{i} = {\sum }_{j \in K_{i}} x_{i,j} + c_{i}$ by a concrete number of size at most λ. Finally, if y _i,j was replaced by a concrete trace, and we have an equation of the form y _i,j = p _i,j s _i,j , then the resulting identity is either true or false and can be eliminated.

After this step, we obtain a disjunction of statements of the following form: There exist numbers x _i,j > 0 (1 ≤ i ≤ n, $j \in K^{\prime }_{i}$) such that

• (a’) $x_{i} = c_{i}+ {\sum }_{j \in K^{\prime }_{i}} x_{i,j}$ for all 1 ≤ i ≤ n, and

• (b’) $p_{i,j} u_{i}^{x_{i,j}} s_{i,j} = s_{k,l}^{-1} (u^{-1}_{k})^{x_{k,l}} p_{k,l}^{-1}$ for all (i,j,k,l) ∈ M.

Here, $K^{\prime }_{i} \subseteq K_{i}$ is a set of size at most k _i ≤ 2²ⁿ⁺¹ − 2, c _i ≤|A|⋅ (k _i − 1) + λ ⋅ k _i < (|A| + λ) ⋅ (2²ⁿ⁺¹ − 2), and the p _i,j ,s _i,j are concrete traces of length at most |A|⋅ (2²ⁿ⁺¹ − 3) ⋅ λ. The set M specifies a matching in the sense that for every exponent x _a,b (1 ≤ a ≤ n, $b \in K^{\prime }_{i}$) there is a unique (i,j,k,l) ∈ M such that (i,j) = (a,b) or (k,l) = (a,b).

We now apply Lemma 3.8 to the trace identities

$$p_{i,j} u_{i}^{x_{i,j}} s_{i,j} = s_{k,l}^{-1} (u^{-1}_{k})^{x_{k,l}} p_{k,l}^{-1}.$$

Each such identity can be replaced by a disjunction of constraints

$$(x_{i,j}, x_{k,l}) \in \{ (a_{i,j,k,l} + b_{i,j,k,l} \cdot z_{i,j,k,l}, c_{i,j,k,l} + d_{i,j,k,l} \cdot z_{i,j,k,l}) \mid z_{i,j,k,l} \in \mathbb{N} \}. $$

For the numbers a _i,j,k,l ,b _i,j,k,l ,c _i,j,k,l ,d _i,j,k,l we obtain the bound

$$a_{i,j,k,l}, b_{i,j,k,l}, c_{i,j,k,l}, d_{i,j,k,l} \in \mathcal{O}(\mu^{8} \cdot \nu^{8 |A|}) $$

(the alphabet of the traces is A ^±1 which has size 2|A|, therefore, we have to multiply in Lemma 3.8 |A| by 2), where, by Lemma 2.4,

$$ \mu = \max\{ \rho(p_{i,j}), \rho(p_{k,l}), \rho(s_{i,j}), \rho(s_{k,l})\} \in \mathcal{O}(|A|^{\alpha} \cdot 2^{2 \alpha n} \cdot \lambda^{\alpha}) $$

(9)

and

$$ \nu = \max\{ \rho(u_{i}), \rho(u_{k}) \} \in \mathcal{O}(\lambda^{\alpha}). $$

(10)

Note that ρ(t) = ρ(t ⁻¹) for every trace t. The above condition (a’) for x _i can be now written as

$$x_{i} = c_{i}+ \sum\limits_{(i,j,k,l) \in M} (a_{i,j,k,l} + b_{i,j,k,l} \cdot z_{i,j,k,l}) + \sum\limits_{(k,l,i,j) \in M} (c_{k,l,i,j} + d_{k,l,i,j} \cdot z_{k,l,i,j}) . $$

Note that the two sums in this equation contain in total $|K^{\prime }_{i}| \leq 2^{2n+1}$ many summands (since for every $j \in K^{\prime }_{i}$ there is a unique pair (k,l) with (i,j,k,l) ∈ M or (k,l,i,j) ∈ M).

Hence, after a renaming of symbols, the initial (8) becomes equivalent to a finite disjunction of statements of the form: There exist $z_{1}, \ldots , z_{m} \in \mathbb {N}$ (these z _i are the above z _i,j,k,l and $m = \max _{i} |K^{\prime }_{i}|$) such that

$$ x_{i} = a_{i} + \sum\limits_{j=1}^{m} a_{i,j} z_{j} \text{ for all} 1 \leq i \leq n . $$

(11)

Moreover, we have the following size bounds:

• $m = \max _{i} |K^{\prime }_{i}| \leq 2^{2n+1}$,

• $a_{i} \in \mathcal {O}(c_{i} + |K^{\prime }_{i}| \cdot \mu ^{8} \cdot \nu ^{8 |A|}) \subseteq \mathcal {O}(2^{2n} (|A|+\lambda + \mu ^{8} \cdot \nu ^{8 |A|})) \subseteq \mathcal {O}(2^{2n} \cdot \mu ^{8} \cdot \nu ^{8 |A|})$

• $a_{i,j} \in \mathcal {O}(\mu ^{8} \cdot \nu ^{8 |A|})$

Recall that some of the variables x _i can be identical. W.l.o.g. assume that x ₁,…,x _k are pairwise different and for all k + 1 ≤ i ≤ n, x _i = x _f(i), where f : [k + 1,n] → [1,k]. Then, the system of (11) is equivalent to

$$\begin{array}{cc} x_{i} = a_{i} + \sum\limits_{j=1}^{m} a_{i,j} z_{j} \text{ for all\ } 1 \leq i \leq k \\ a_{i} - a_{f(i)} = \sum\limits_{j=1}^{m} (a_{f(i),j}-a_{i,j}) z_{j} \text{ for all\ } k+1 \leq i \leq n . \end{array} $$

The set of all $(x_{1}, \ldots , x_{k}) \in \mathbb {N}^{k}$ for which there exist $z_{1}, \ldots , z_{m} \in \mathbb {N}$ satisfying these equations is semilinear by Lemma 3.9, and if it is non-empty then it contains a vector $(x_{1}, \ldots , x_{k}) \in \mathbb {N}^{k}$ such that (note that $(\sqrt {m})^{n} \in \mathcal {O}(2^{n^{2}+n})$)

$$\begin{array}{@{}rcl@{}} x_{i} & \in & \mathcal{O}((\sqrt{m})^{n} \cdot m^{2} \cdot 2^{2n(n+1)} \cdot \mu^{8(n+1)} \cdot \nu^{8 |A| (n+1)}) \end{array} $$

(12)

$$\begin{array}{@{}rcl@{}} & \subseteq & \mathcal{O}(2^{3n^{2} + 7n} \cdot \mu^{8(n+1)} \cdot \nu^{8 |A| (n+1)}). \end{array} $$

(13)

Recall that in this bound we have to replace n by α ⋅ n due to the initial preprocessing. This proves the theorem. □

Proof

of Theorem 3.1. Consider a compressed exponent equation

$$E = (v_{0} u_{1}^{x_{1}} v_{1} u_{2}^{x_{2}} v_{2} {\cdots} u_{n}^{x_{n}} v_{n} = 1), $$

where $u_{i} = \text {val}(\mathcal {G}_{i})$ and $v_{i} = \text {val}(\mathcal {H}_{i})$ for given SLPs $\mathcal {G}_{1}, \ldots , \mathcal {G}_{n}, \mathcal {H}_{0}, \ldots , \mathcal {H}_{n}$. Let $m = \max \{ |\mathcal {G}_{1}|, \ldots , |\mathcal {G}_{n}|, |\mathcal {H}_{0}|, \ldots , |\mathcal {H}_{n}| \}$. By Theorem 3.11 we know that if there exists a solution for E then there exists a solution (x ₁,…,x _n ) with $x_{i} \in \mathcal {O}(2^{3 (\alpha n)^{2} + 7 \alpha n} \cdot \mu ^{8\alpha (n+1)} \cdot \nu ^{8 \alpha |A| (n+1)})$, where

• $\mu \in \mathcal {O}(|A|^{\alpha } \cdot 2^{2 \alpha ^{2} n} \cdot \lambda ^{\alpha })$,

• $\nu \in \mathcal {O}(\lambda ^{\alpha })$,

• $\lambda = \max \{ |u_{1}|, |u_{2}|, \ldots , |u_{n}|, |v_{0}|, |v_{1}|, \ldots , |v_{n}|\} \in 2^{\mathcal {O}(m)}$, and

• α ≤|A|.

Note that the bound on the x _i is exponential in the input length (the sum of the sizes of all $\mathcal {G}_{i}$ and $\mathcal {H}_{i}$). Hence, we can guess in polynomial time the binary encodings of numbers $k_{i} \in \mathcal {O}(2^{3 (\alpha n)^{2} + 7 \alpha n} \cdot \mu ^{8\alpha (n+1)} \cdot \nu ^{8 \alpha |A| (n+1)})$ (where k _i = k _j if x _i = x _j ). Then, we have to verify whether

$$\text{val}(\mathcal{H}_{0}) \text{val}(\mathcal{G}_{1})^{k_{1}} \text{val}(\mathcal{H}_{1}) \text{val}(\mathcal{G}_{2})^{k_{2}} \text{val}(\mathcal{H}_{2}) {\cdots} \text{val}(\mathcal{G}_{n})^{k_{n}} \text{val}(\mathcal{H}_{n}) = 1$$

in the graph group $\mathbb {G}(A,I)$. This is an instance of the so-called compressed word problem for $\mathbb {G}(A,I)$, where the input consists of an SLP $\mathcal {G}$ over the alphabet A ^±1 and it is asked whether $\text {val}(\mathcal {G}) =1$ in $\mathbb {G}(A,I)$. Note that the powers $\text {val}(\mathcal {G}_{i})^{k_{i}}$ can be produced with the productions of $\mathcal {G}_{i}$ and additional ⌈log k _i ⌉ many productions (using iterated squaring). Since the compressed word problem for a graph group can be solved in deterministic polynomial time [36, 37] (NP would suffice), the theorem follows. For the last step, it is important that (A,I) is fixed. □

3.6 Solvability of compressed exponent equation for a variable graph group

For the proof of Theorem 3.1 we assumed that the graph group $\mathbb {G}(A,I)$ is fixed. In this section we briefly consider the case, where the independence alphabet (A,I) is part of the input as well. Let uniform solvability of compressed exponent equations over graph groups be the following computational problem.

Input: :

An independence alphabet (A,I) and a compressed exponent equation E over $\mathbb {G}(A,I)$.

Question: :

Is E solvable?

Note that the bound on the exponents x _i in the proof of Theorem 3.1 is still exponential in the input length if the independence alphabet (A,I) is part of the input as well. The problem is that we do not know whether the uniform compressed word problem for graph groups (where the input is an independence alphabet (A,I) together with an SLP over the terminal alphabet A ^±1) can be solved in polynomial time or at least in NP. The latter would suffice to get an NP-algorithm for uniform solvability of compressed exponent equations over a graph groups. On the other hand, we can show that the uniform compressed word problem for graph groups belongs to the complexity class coRP. A language L ∈Σ^∗ belongs to the class coRP if there exists a set P ⊆Σ^∗×{0,1}^∗ and a polynomial p(n) such that P can be decided in deterministic polynomial time and for all x ∈Σ^∗ with |x| = n the following holds:

• If x ∈ L then (x,y) ∈ P for all y ∈{0,1}^p(n).

• If x∉L then (x,y) ∈ P for at most 1/3 ⋅ 2^p(n) many y ∈{0,1}^p(n).

Theorem 3.12

The uniform compressed word problem for graph groups belongs to coRP.

Proof

We make use of a well known embedding of a graph group $\mathbb {G}(A,I)$ with n = |A| into the linear matrix group $\mathsf {GL}_{2n}(\mathbb {Z})$. This embedding is obtained by first embedding $\mathbb {G}(A,I)$ into a so called right-angled Coxeter group followed by a linear embedding for the latter group. A right-angled Coxeter group is obtained by adding to a graph group $\mathbb {G}(A,I)$ all relations a ² = 1 for all generators a ∈ A. Let us denote with $\mathbb {C}(A,I)$ this right-angled Coxeter group.

The following embedding of a graph group $\mathbb {G}(A,I)$ into a right-angled Coxeter group goes back to [26]: Take a disjoint copy A ^′ = {a ^′∣a ∈ A} of A and consider the right-angled Coxeter group $\mathbb {C}(A \cup A^{\prime }, J)$ with

$$J = \{ (a,b), (a^{\prime},b), (a,b^{\prime}), (a^{\prime},b^{\prime}) \mid (a,b) \in I \}. $$

Then the morphism $g \colon \mathbb {G}(A,I) \to \mathbb {C}(A \cup A^{\prime }, J)$ with g(a) = a a ^′ for a ∈ A is injective.

Next, a right-angled Coxeter group $\mathbb {C}(A,I)$ with |A| = n can be embedded into $\mathsf {GL}_{n}(\mathbb {Z})$ by mapping the generator a ∈ A to the linear map $\sigma _{a} \colon \mathbb {Z}^{A} \to \mathbb {Z}^{A}$ defined by

$$\sigma_{a}(b) = \left\{\begin{array}{ll} -b & \text{if\ } b=a, \\ b & \text{if\ } (a,b) \in I, \\ b+2a & \text{if\ } a \neq b \text{ and} \ (a,b) \not\in I \end{array}\right. $$

This is an instance of the standard linear embedding for general Coxeter groups, see e.g. the textbook [8] for more details.

Let us fix a graph group $\mathbb {G}(A,I)$ with n = |A| and let $h \colon \mathbb {G}(A,I) \to \mathsf {GL}_{2n}(\mathbb {Z})$ be the linear embedding that results from the above construction. Note that for a given graph (A,I) we can compute in polynomial time for every generator a ∈ A the corresponding matrix $h(a) \in \mathsf {GL}_{2n}(\mathbb {Z})$.

Let $\mathcal {G} = (V,{\Sigma },\text {rhs},S)$ be an SLP over the terminal alphabet A ∪ A ⁻¹. Without loss of generality, one can assume that for every variable X ∈ V, the right-hand side rhs(X) belongs to A ∪ A ⁻¹ ∪ V V, see e.g. [36](@var1@Proposition 3.8@var1@). We now construct an arithmetic circuit⁵ that evaluates to 1 if and only if $\text {val}(\mathcal {G}) = 1$ in the graph group $\mathbb {G}(A,I)$. The construction is the same as in [36](@var1@Theorem 4.15@var1@). For every nonterminal X ∈ V we introduce 4n ² many + -labeled gates X _i,j (1 ≤ i,j ≤ 2n). The idea is that X _i,j evaluates to the entry at position (i,j) in the matrix $h(\text {val}_{\mathcal {G}}(X))$. The wires between the gates are defined such that they implement matrix multiplication. If rhs(X) = Y Z, then we add an auxiliary ×-labeled gate X _i,j,k together with the wires (Y _i,j ,X _i,j,k ), (Z _j,k ,X _i,j,k ), and (X _i,j,k ,X _i,k ) for all 1 ≤ i,j,k ≤ 2n. If rhs(X) = a ∈ A ∪ A ⁻¹, then we set the value of X _i,j to the entry at position (i,j) of the matrix h(a).

Assume that the gate S _i,j of the constructed arithmetic circuit evaluates to the integer s _i,j . Then, the matrix (s _i,j )_1≤i,j≤n is $h(\text {val}(\mathcal {G}))$. Thus, we have to check, whether this matrix is the identity matrix. For this,we add an additional gate X (which will be the output gate of the circuit) together with some auxiliary gates to the circuit such that gate X evaluates to the integer ${\sum }_{i=1}^{n} (s_{i,i}-1)^{2} + {\sum }_{i \neq j} s_{i,j}^{2}$. Then, (s _i,j )_1≤i,j≤n is the identity matrix if and only if gate X evaluates to zero, We can conclude the proof by using the following well-known result, see e.g. [27]: Whether a given arithmetic circuit evaluates to zero can be decided in coRP. □

There is some evidence in complexity theory for R P = c o R P = P. Impagliazzo and Wigderson [28] proved that if there exists a language in $\mathsf {DTIME}(2^{\mathcal {O}(n)})$ that has circuit complexity 2^Ω(n) (which seems to be plausible) then R P = c o R P = P (in fact, B P P = P).

A language L ∈Σ^∗ belongs to the class MA (for Merlin-Arthur protocol) if there exists a set P ⊆Σ^∗×{0,1}^∗×{0,1}^∗ and polynomials p(n),q(n) such that P can be decided in deterministic polynomial time and for all x ∈Σ^∗ with |x| = n the following holds:

• If x ∈ L then there exists y ∈{0,1}^p(n) such that (x,y,z) ∈ P for all z ∈{0,1}^q(n).

• If x∉L then for all y ∈{0,1}^p(n) there exist at most 1/3 ⋅ 2^p(n) many z ∈{0,1}^q(n) such that (x,y,z) ∈ P.

The same (unproven) circuit complexity lower bounds that allow to derandomize R P [28] also imply M A = N P.

Corollary 3.13

Uniform solvability of compressed exponent equations over graph groups belongs to MA.

Proof

We follow to arguments from the proof of Theorem 3.1. As remarked above, the bound on the exponents x _i in the proof of Theorem 3.1 is still exponential in the input length if the independence alphabet (A,I) is part of the input as well. After guessing the values for the x _i in binary representation (this corresponds to the existential quantifier in the definition of MA), we are left with the solution of an instance of the uniform compressed word problem for graph groups, which belongs to coRP by Theorem 3.12. This yields an MA-protocol for uniform solvability of compressed exponent equations over graph groups. □

4 Uncompressed Knapsack and Subset Sum

Since knapsack and subset sum for binary encoded integers is NP-complete, it follows that compressed knapsack and subset sum are NP-hard for every finitely generated group that contains an element of infinite order. In the rest of the paper, we will study the computational complexity of uncompressed knapsack and subset sum for graph groups. In the rest of the paper, the terms “knapsack” and “subset sum” will always refer to the uncompressed variant of the problem.

In Section 4.1, we present a class of graph groups for which knapsack is NP-complete. In Section 4.2, we will show that for all other graph groups, knapsack belongs to LogCFL, which is a subclass of P. In fact, we will show that knapsack is LogCFL- complete for these graph groups, unless they are abelian. Finally, in Section 4.4, we prove T C ⁰-completeness in the case of abelian graph groups (i.e. free abelian groups). For subset sum, we are not able to exactly locate the border between P-membership and NP-completeness.

4.1 N P-completeness

Figure 1 shows two important independence alphabets that we denote with P 4 (path on four nodes) and C 4 (cycle on four nodes). Note that $\mathbb {M}(\mathsf {C4}) = \{a,c\}^{*} \times \{b,d\}^{*}$ and $\mathbb {G}(\mathsf {C4}) \cong F_{2} \times F_{2}$, where F ₂ the free group of rank 2.

Fig. 1

P 4 and C 4

A transitive forest is an independence that can be inductively obtained as follows:

• ({a},∅) is a transitive forest.

• If (A ₁,I ₁) and (A ₂,I ₂) are transitive forests, then also (A ₁ ∪ A ₂,I ₁ ∪ I ₂) is a transitive forest.

• If (A,I) is a transitive forest and a∉I, then (A ∪{a},I ∪{a}× A ∪ A ×{a}) is a transitive forest.

The name “transitive forest” comes from the fact that these graphs are obtained by taking the transitive closure of a disjoint union of rooted directed trees (a forest) and then forgetting the direction of edges. From the above definition of transitive forests, it is clear that the graph groups $\mathbb {G}(A,I)$ with (A,I) a transitive forest is the smallest class of groups that contains $\mathbb {Z}$ and is closed under free products and direct products with $\mathbb {Z}$. We will use the following alternative characterization of transitive forests by Wolk [52]: (A,I) is a transitive forest if and only if (A,I) neither contains an induced P 4 nor and induced C 4.

In the rest of Section 4.1, we will prove the following theorem:

Theorem 4.1

If (A,I)is not a transitive forest, then knapsack is NP -complete for $\mathbb {G}(A,I)$.

By the above mentioned result of Wolk, it suffices to show that knapsack is NP-hard for $\mathbb {G}(\mathsf {C4})$ (Section 4.1.1) and $\mathbb {G}(\mathsf {P4})$ (Section 4.1.2). Note that if (A ^′,I ^′) is an induced subgraph of (A,I), then $\mathbb {G}(A^{\prime },I^{\prime })$ is a subgroup of $\mathbb {G}(A,I)$.

4.1.1 Knapsack and subset sum for $\mathbb {G}(\mathsf {C4})$

In this section, we prove that knapsack and subset sum are NP-complete for $\mathbb {G}(\mathsf {C4})$, i.e., for a direct product of two free groups of rank two. This solves an open problem from [18].

Recall that F(Σ) denotes the free group generated by the set Σ and F ₂ = F({a,b}).

Lemma 4.2

The subset sum problem and the knapsack problem are NP-complete for F ₂ × F ₂. For knapsack, NP -hardness already holds for the variant where the exponent variables are allowed to take values from $\mathbb {Z}$ (see Remark 2.2).

Proof

In [44] it was shown that there exists a fixed set D ⊆ F ₂ × F ₂ such that the following problem (called the bounded submonoid problem) is NP-complete:

Input: :

A unary encoded number n (i.e., n is given by the string a ⁿ) and an element g ∈ F ₂ × F ₂

Question: :

Do there exist g ₁,…g _n ∈ D (not necessarily distinct) such that g = g ₁ g ₂⋯g _n in F ₂ × F ₂?

Let us briefly explain the NP-hardness proof, since we will reuse it.

Recall the notion of the Dehn function defined in Section 2.5. We start with a finitely presented group 〈Σ∣R〉 having an NP-complete word problem and a polynomial Dehn function. Such a group was constructed in [7]. To this group, the following classical construction by Mihaı̆lova [42] is applied: Let

$$D = \{ (r^{\epsilon},1) \mid r \in R, \epsilon \in \{-1,1\} \} \cup \{ (a,a) \mid a \in {\Sigma}^{\pm 1} \}, $$

which is viewed as a subset of F(Σ) × F(Σ). Note that D is closed under taking inverses. Let 〈D〉≤ F(Σ) × F(Σ) be the subgroup generated by D. Mihaı̆lova proved that for every word w ∈ (Σ^±1)^∗ the following equivalence holds:

$$w = 1 \text{ in\ } \langle {\Sigma}, R \rangle \ \Longleftrightarrow \ (w,1) \in \langle D \rangle \text{ in\ } F({\Sigma}) \times F({\Sigma}) . $$

Moreover, based on the fact that 〈Σ,R〉 has a polynomial Dehn function p(n), the following equivalence was shown in [44], where q(n) = p(n) + 8(c ⋅ p(n) + n), c is the maximal length of a relator in R, and D ⁿ is the set of all products of n elements from D:

$$w = 1 \text{ in\ } \langle {\Sigma}, R \rangle \ \Longleftrightarrow \ \exists n \leq q(|w|) : (w,1) \in D^{n} \text{ in} \ F({\Sigma}) \times F({\Sigma}) . $$

From these two equivalences it follows directly that the following three statements are equivalent for all words w ∈ (Σ^±1)^∗, where D = {g ₁,g ₂,…,g _k }:

• w = 1 in 〈Σ,R〉

• $(w,1) = {\prod }_{i=1}^{q(|w|)} (g_{1}^{a_{1,i}} g_{2}^{a_{2,i}} {\cdots } g_{k}^{a_{k,i}})$ in F(Σ) × F(Σ) for a _j,i ∈{0,1}

• $(w,1) = {\prod }_{i=1}^{q(|w|)} (g_{1}^{a_{1,i}} g_{2}^{a_{2,i}} {\cdots } g_{k}^{a_{k,i}})$ in F(Σ) × F(Σ) for $a_{j,i} \in \mathbb {Z}$

This shows that the subset sum problem and the knapsack problem are NP-hard for the group F(Σ) × F(Σ), where for knapsack we allow integer exponents. To get the same results for F ₂ × F ₂, we use the fact that F ₂ contains a copy of F(Σ). □

4.1.2 Knapsack for $\mathbb {G}(\mathsf {P4})$

In this section, we show that knapsack is NP-complete for the graph group $\mathbb {G}(\mathsf {P4})$. Let us fix the copy ({a,b,c,d},I) of P 4 shown in Fig. 1.

As a first step, we will prove NP-completeness of a certain automata theoretic problem, that will be reduced to knapsack for $\mathbb {G}(\mathsf {P4})$ in a second step. For a trace monoid $\mathbb {M}(A,I)$, the intersection nonemptiness problem for acyclic loop NFA is the following computational problem:

Input: :

Two acyclic loop NFA $\mathcal {A}_{1}$, $\mathcal {A}_{2}$ over the input alphabet A (as defined in Section 2.2).

Question: :

Does $[L(\mathcal {A}_{1})]_{I} \cap [L(\mathcal {A}_{2})]_{I} \neq \emptyset$ hold?

Aalbersberg and Hoogeboom [1] proved that for the trace monoid $\mathbb {M}(\mathsf {P4})$ the intersection nonemptiness problem for arbitrary NFA is undecidable. We use their technique to show:

Lemma 4.3

For $\mathbb {M}(\mathsf {P4})$, intersection nonemptiness for acyclic loop NFA is NP-hard.

Proof

We give a reduction from 3SAT. Let $\varphi = \bigwedge _{i=1}^{m} C_{i}$ where for every i ∈ [1,m], C _i = (L _i,1 ∨ L _i,2 ∨ L _i,3) is a clause consisting of three literals. Let x ₁,…,x _n be the boolean variables that occur in φ. In particular, every literal L _i,j belongs to the set {x ₁,…,x _n ,¬x ₁,…,¬x _n }.

Let p ₁,p ₂,…,p _n be a list of the first n prime numbers. So, for each boolean variable x _i we have the corresponding prime number p _i . We encode a valuation β: {x ₁,…,x _n }→{0,1} by any natural number N such that N ≡ 0 mod p _i if and only if β(x _i ) = 1. For a positive literal x _i let $S(x_{i}) = \{ p_{i} \cdot n \mid n \in \mathbb {N}\}$ and for a negative literal ¬x _i let $S(\neg x_{i}) = \{ p_{i} \cdot n + r \mid n \in \mathbb {N}, r\in [1,p_{i}-1]\}$. Moreover, for every i ∈ [1,m] let S _i = S(L _i,1) ∪ S(L _i,2) ∪ S(L _i,3). Thus, S _i is the set of all numbers that encode a valuation, which makes the clause C _i true. Hence, the set $S = \bigcap _{i=1}^{n} S_{i}$ encodes the set of all valuations that make φ true.

We first construct an acyclic loop NFA $\mathcal {A}_{1}$ with

$$L(\mathcal{A}_{1}) = \prod\limits_{i=1}^{m} \{ a (bc)^{N_{i}} d \mid N_{i} \in S_{i} \} . $$

Note that φ is satisfiable iff $[L(\mathcal {A}_{1})]_{I}$ contains a trace from $[\{ (a (bc)^{N} d)^{m} \mid N \in \mathbb {N}\}]_{I}$. We will ensure this property with a second acyclic loop NFA $\mathcal {A}_{2}$ that satisfies the equality $L(\mathcal {A}_{2}) = b^{*} (ad (bc)^{*})^{m-1} ad c^{*} .$

We claim that $[L(\mathcal {A}_{1})]_{I} \cap [L(\mathcal {A}_{2})]_{I} = [\{ (a (bc)^{N} d)^{m} \mid N \in S\}]_{I}$. First assume that w≡ _I (a(b c)^N d)^m for some N ∈ S. We have

$$w \equiv_{I} (a (bc)^{N} d)^{m} \equiv_{I} b^{N} (ad (bc)^{N})^{m-1} ad c^{N} $$

and thus $[w]_{I} \in [L(\mathcal {A}_{2})]_{I}$. Moreover, since N ∈ S we get $[w]_{I} \in [L(\mathcal {A}_{1})]_{I}$. For the other direction, let $[w]_{I} \in [L(\mathcal {A}_{1})]_{I} \cap [L(\mathcal {A}_{2})]_{I}$. Thus

$$w \equiv_{I} \prod\limits_{i=1}^{m} (a (bc)^{N_{i}} d) \equiv b^{N_{1}} \left(\prod\limits_{i=1}^{m-1} (ad c^{N_{i}} b^{N_{i+1}}) \right) ad c^{N_{m}} , $$

where N _i ∈ S _i for i ∈ [1,m]. Moreover, the fact that $[w]_{I} \in [L(\mathcal {A}_{2})]_{I}$ means hat there are k ₀,k ₁,…,k _m−1,k _m ≥ 0 with

$$\begin{array}{@{}rcl@{}} b^{N_{1}} \left(\prod\limits_{i=1}^{m-1} (ad c^{N_{i}} b^{N_{i+1}}) \right) ad c^{N_{m}} & \equiv_{I} b^{k_{0}} \left(\prod\limits_{i=1}^{m-1} (ad (bc)^{k_{i}}) \right) ad c^{k_{m}} \\ &\equiv_{I} b^{k_{0}} \left(\prod\limits_{i=1}^{m-1} (ad b^{k_{i}} c^{k_{i}}) \right) ad c^{k_{m}} . \end{array} $$

Since every symbol is dependent from a or d, this identity implies N _i = N _i+1 for i ∈ [1,m − 1]. Thus, [w] _I ∈ [{(a(b c)^N d)^m∣N ∈ S}] _I . □

For a graph group $\mathbb {G}(A,I)$ the membership problem for acyclic loop NFA is the following computational problem:

Input: :

An acyclic loop NFA $\mathcal {A}$ over the input alphabet A ∪ A ⁻¹.

Question: :

Is there a word $w \in L(\mathcal {A})$ such that w = 1 in $\mathbb {G}(A,I)$?

It is straightforward to reduce the intersection nonemptiness problem for acyclic loop NFA over $\mathbb {M}(A,I)$ to the membership problem for acyclic loop NFA over $\mathbb {G}(A,I)$. For the rest of this section let Σ = {a,b,c,d,a ⁻¹,b ⁻¹,c ⁻¹,d ⁻¹} and let $\theta \colon {\Sigma }^{*} \to \mathbb {G}(P_{4})$ be the canonical homomorphism that maps a word over Σ to the corresponding group element.

Lemma 4.4

For $\mathbb {G}(\mathsf {P4})$, the membership problem for acyclic loop NFA is NP-hard.

Proof

The lemma follows easily from Lemma 4.3. Note that $[L(\mathcal {A}_{1})]_{I} \cap [L(\mathcal {A}_{2})]_{I} \neq \emptyset$ if and only if $1 \in \theta (L(\mathcal {A}_{1}) L(\mathcal {A}_{2})^{-1})$ in the graph group $\mathbb {G}(\mathsf {P4})$. Moreover, it is straightforward to construct from acyclic loop NFA $\mathcal {A}_{1}$ and $\mathcal {A}_{2}$ an acyclic loop NFA for $L(\mathcal {A}_{1}) L(\mathcal {A}_{2})^{-1}$. We only have to replace every transition label w in $\mathcal {A}_{2}$ by w ⁻¹, then reverse all transitions in $\mathcal {A}_{2}$ and concatenate the resulting NFA with $\mathcal {A}_{1}$ on the left. □

We can now use a construction from [38] to reduce membership for acyclic loop NFA to knapsack.

Lemma 4.5

Knapsack for the graph group $\mathbb {G}(\mathsf {P4})$ is NP-hard.

Proof

By Lemma 4.4 it suffices to reduce for $\mathbb {G}(\mathsf {P4})$ the membership problem for acyclic loop NFA to knapsack. Let $\mathcal {A} = (Q, {\Sigma },{\Delta }, q_{0}, q_{f})$ be an acyclic loop NFA with transitions Δ ⊆ Q ×Σ^∗× Q. W.l.o.g. assume that Q = {1,…,n}.

We reuse a construction from [38], where the rational subset membership problem for $\mathbb {G}(\mathsf {P4})$ was reduced to the submonoid membership problem for $\mathbb {G}(\mathsf {P4})$. For a state q ∈ Q let $\widetilde {q} = (ada)^{q} d (ada)^{-q} \in {\Sigma }^{*}$. Let us fix the morphism φ:Σ^∗→Σ^∗ with φ(x) = x x for x ∈ Σ. For a transition t = (p,w,q) ∈ Δ let $\tilde {t} = \widetilde {p} \,\varphi (w)\, \widetilde {q}^{-1}$ and define $S=\{ \tilde {t} \mid t \in {\Delta } \}^{*}$. In [38] it was shown that $1 \in \theta (L(\mathcal {A}))$ if and only if $\theta (\widetilde {q_{0}} \, \widetilde {q_{f}}^{-1}) \in \theta (S)$.

We construct in polynomial time a knapsack instance over $\mathbb {G}(P_{4})$ from the NFA $\mathcal {A}$ as follows: Let us choose an enumeration t ₁,t ₂,…,t _m of the transitions of $\mathcal {A}$ such that the following holds, where t _i = (p _i ,w _i ,q _i ): If q _j = p _k then j ≤ k. Since $\mathcal {A}$ is an acyclic loop NFA, such an enumeration exists. The following claim proves the theorem.

Claim: $1 \in \theta (L(\mathcal {A}))$ if and only if $\theta (\widetilde {q_{0}}\, \widetilde {q_{f}}^{-1}) \in \theta (\tilde {t}_{1}^{*}\, \tilde {t}_{2}^{*} {\cdots } \tilde {t}_{m}^{*})$.

One direction is clear: If $\theta (\widetilde {q_{0}}\, \widetilde {q_{f}}^{-1}) \in \theta (\tilde {t}_{1}^{*}\, \tilde {t}_{2}^{*} {\cdots } \tilde {t}_{m}^{*})$, then $\theta (\widetilde {q_{0}} \,\widetilde {q_{f}}^{-1}) \in \theta (S)$. Hence, by [38] we have $1 \in \theta (L(\mathcal {A}))$. On the other hand, if $1 \in \theta (L(\mathcal {A}))$, then there exists a path in $\mathcal {A}$ of the form

such that 𝜃(a ₁ a ₂⋯a _k ) = 1. Let $(s_{j-1},a_{j},s_{j}) = t_{i_{j}}$, where we refer to the above enumeration of all transitions. Then, we must have i ₁ ≤ i ₂ ≤⋯ ≤ i _k . Moreover, we have

$$\theta(\widetilde{q_{0}}\, \widetilde{q_{f}}^{-1}) = \theta(\widetilde{q_{0}} \, a_{1} a_{2} {\cdots} a_{k} \, \widetilde{q_{f}}^{-1}) = \theta(\tilde{t}_{i_{1}} \tilde{t}_{i_{2}} {\cdots} \tilde{t}_{i_{k}}) \in \theta(\tilde{t}_{1}^{*}\, \tilde{t}_{2}^{*} {\cdots} \tilde{t}_{m}^{*}).$$

This proves the claim and hence the theorem. □

We are now ready to prove Theorem 4.1.

Proof

Theorem 4.1 If (A,I) is not a transitive forest, then P 4 or C 4 is an induced subgraph of (A,I) [52]. Thus, $\mathbb {G}(\mathsf {P4})$ or $\mathbb {G}(\mathsf {C4}) \cong F_{2} \times F_{2}$ is a subgroup of $\mathbb {G}(A,I)$. Hence, NP-hardness of knapsack for $\mathbb {G}(A,I)$ follows from Lemma 4.2 or Lemma 4.5. □

4.2 Membership in LogCFL

In this section, we show that if (A,I) is a transitive forest, then knapsack and subset sum belong to LogCFL, which is a subclass of P; see Section 2.1.

Theorem 4.6

If (A,I)is a transitive forest, then knapsack and subset sum for $\mathbb {G}(A,I)$ belong to LogCFL.

4.2.1 Membership for acyclic NFA

In the proof of Theorem 4.6 we employ the membership problem for acyclic NFA (see Section 2.2), which has already been studied in connection with the knapsack and subset sum problem [18, 33]. For a graph group $\mathbb {G}(A,I)$ the membership problem for acyclic NFA is the following computational problem:

Input: :

An acyclic automaton $\mathcal {A}$ over the input alphabet A ∪ A ⁻¹.

Question: :

Is there a word $w \in L(\mathcal {A})$ such that w = 1 in $\mathbb {G}(A,I)$?

In order to show Theorem 4.6, we reduce knapsack for $\mathbb {G}(A,I)$ with (A,I) a transitive forest to the membership problem for acyclic NFA for $\mathbb {G}(A,I)$ (note that for subset sum this reduction is obvious). Then, we apply the following Proposition 4.7. From work of Frenkel, Nikolaev, and Ushakov [18], it follows that the membership problem for acyclic NFA is in P. We strengthen this to LogCFL:

Proposition 4.7

If (A,I)is a transitive forest, then the membership problem for acyclic NFA over $\mathbb {G}(A,I)$ is in LogCFL.

The proof of Proposition 4.7 uses the following lemma:

Lemma 4.8

For every transitive forest (A,I)with the associated graph group $G = \mathbb {G}(A,I)$ there is a deterministic AuxPDA $\mathcal {P}(G)$ with input alphabet A ^±1 and the following properties:

• In each step, the input head for $\mathcal {P}(G)$ either does not move, or moves one step to the right.

• If the input word is equal to 1 in G, then $\mathcal {P}(G)$ terminates in the distinguished state q ₁ with empty stack. Let us call this state the 1-state of $\mathcal {P}(G)$ .

• If the input word is not equal to 1 in G, then $\mathcal {P}(G)$ terminates in a state different from q ₁ (and the stack is not necessarily empty).

Proof

We construct the AuxPDA $\mathcal {P}(G)$ by induction over the structure of the group G. For this, we consider the three cases that G = 1, G = G ₁ ∗ G ₂, and $G = \mathbb {Z} \times G^{\prime }$. The case that G = 1 is of course trivial.

Case $G = \mathbb {Z} \times G^{\prime }$. We have already constructed the AuxPDA $\mathcal {P}(G^{\prime })$. The AuxPDA $\mathcal {P}(G)$ simulates the AuxPDA $\mathcal {P}(G^{\prime })$ on the generators of G ^′. Moreover, it stores the current value of the $\mathbb {Z}$-component in binary notation on the work tape. If the input word has length n, then O(log n) bits are sufficient for this. At the end, $\mathcal {P}(G)$ goes into its 1-state if and only if $\mathcal {P}(G^{\prime })$ is in its 1-state (which implies that the stack will be empty) and the $\mathbb {Z}$-component is zero.

Case G = G ₁ ∗ G ₂. For i ∈{1,2}, we have already constructed the AuxPDA $\mathcal {P}_{i} = \mathcal {P}(G_{i})$. Let $A_{i}^{\pm 1}$ be its input alphabet, which is a monoid generating set for G _i . Consider now an input word $w \in (A_{1}^{\pm 1} \cup A_{2}^{\pm 1})^{*}$. Let us assume that w = u ₁ v ₁ u ₂ v ₂⋯u _k v _k with $u_{i} \in (A_{1}^{\pm 1})^{+}$ and $v_{i} \in (A_{2}^{\pm 1})^{+}$ (other cases can be treated analogously). The AuxPDA $\mathcal {P}(G)$ starts with empty stack and simulates the AuxPDA $\mathcal {P}_{1}$ on the prefix u ₁. If it turns out that u ₁ = 1 in G ₁ (which means that $\mathcal {P}_{1}$ is in its 1-state) then the stack will be empty and the AuxPDA $\mathcal {P}(G)$ continues with simulating $\mathcal {P}_{2}$ on v ₁. On the other hand, if u ₁≠1 in G ₁, then $\mathcal {P}(G)$ pushes the state together with the work tape content of $\mathcal {P}_{1}$ reached after reading u ₁ on the stack (on top of the final stack content of $\mathcal {P}_{1}$). This allows $\mathcal {P}(G)$ to resume the computation of $\mathcal {P}_{1}$ later. Then $\mathcal {P}(G)$ continues with simulating $\mathcal {P}_{2}$ on v ₁.

The computation of $\mathcal {P}(G)$ will continue in this way. More precisely, if after reading u _i (resp. v _i with i < k) the AuxPDA $\mathcal {P}_{1}$ (resp. $\mathcal {P}_{2}$) is in its 1-state then either

• (i) the stack is empty or

• (ii) the top part of the stack is of the form s q t (t is the top), where s is a stack content of $\mathcal {P}_{2}$ (resp. $\mathcal {P}_{1}$), q is a state of $\mathcal {P}_{2}$ (resp. $\mathcal {P}_{1}$) and t is a work tape content of $\mathcal {P}_{2}$ (resp. $\mathcal {P}_{1}$).

In case (i), $\mathcal {P}(G)$ continues with the simulation of $\mathcal {P}_{2}$ (resp. $\mathcal {P}_{1}$) on the word v _i (resp. u _i+1) in the initial configuration. In case (ii), $\mathcal {P}(G)$ continues with the simulation of $\mathcal {P}_{2}$ (resp. $\mathcal {P}_{1}$) on the word v _i (resp. u _i+1), where the simulation is started with stack content s, state q, and work tape content t. On the other hand, if after reading u _i (resp. v _i with i < k) the AuxPDA $\mathcal {P}_{1}$ (resp. $\mathcal {P}_{2}$) is not in its 1-state then $\mathcal {P}(G)$ pushes on the stack the state and work tape content of $\mathcal {P}_{1}$ reached after its simulation on u _i . This concludes the description of the AuxPDA $\mathcal {P}(G)$. It is clear that $\mathcal {P}(G)$ has the properties stated in the lemma. □

We can now prove Proposition 4.7:

Proof

of Proposition 4.7. Fix the graph group $G = \mathbb {G}(A,I)$, where (A,I) is a transitive forest. An AuxPDA for the membership problem for acyclic NFA guesses a path in the input NFA $\mathcal {A}$ and thereby simulates the AuxPDA $\mathcal {P}(G)$ from Lemma 4.8. If the final state of the input NFA $\mathcal {A}$ is reached while the AuxPDA $\mathcal {P}(G)$ is in the accepting state q ₁, then the overall AuxPDA accepts. It is important that the AuxPDA $\mathcal {P}(G)$ works one-way since the guessed path in $\mathcal {A}$ cannot be stored in logspace. This implies that the AuxPDA cannot re-access the input symbols that already have been processed. Also note that the AuxPDA is logspace bounded and polynomially time bounded since $\mathcal {A}$ is acyclic. □

4.2.2 Bounds on knapsack solutions in transitive forests

As mentioned above, we reduce for graph groups $\mathbb {G}(A,I)$ with (A,I) a transitive forest the knapsack problem to the membership problem for acyclic NFA. To this end, we show that every positive knapsack instance has a polynomially bounded solution. The latter is the most involved proof in our paper.

Frenkel, Nikolaev, and Ushakov [18] call groups with this property polynomially bounded knapsack groups and show that this class is closed under taking free products. However, it is not clear if direct products with $\mathbb {Z}$ also inherit this property and we leave this question open.

Hence, we are looking for a property that yields polynomial-size solutions and is passed on to free products and to direct products with $\mathbb {Z}$. It is known that the solution sets are always semilinear. If (A,I) is a transitive forest, this follows from a more general semilinearity property of rational sets [38] and for arbitrary graph groups, this was shown in Theorem 3.11.

Note that it is not true that the solution sets always have polynomial-size semilinear representations. This already fails in the case of $\mathbb {Z}$: The equation x ₁ + ⋯ + x _k = k has $\binom {2k-1}{k}\ge 2^{k}$ solutions. We therefore need a weaker property: We will show here that the solution sets have semilinear representations where every occurring number is bounded by a polynomial.

For a semilinear representation (x ₁,F ₁,…,x _n ,F _n ) of the semilinear set $S=\bigcup _{i=1}^{n} x_{i}+F_{i}^{\oplus }$, the magnitude of this representation is defined as the maximum of ∥y∥ _∞ , where y ranges over all vectors of $\bigcup _{i=1}^{n} \{x_{i}\}\cup F_{i}$. The magnitude of a semilinear set S is the smallest magnitude of a semilinear representation for S.

Definition 4.9

A group G is called knapsack tame if there is a polynomial p such that for every exponent equation $h_{0} g_{1}^{x_{1}}h_{1}g_{2}^{x_{2}}h_{2}{\cdots } g_{n}^{x_{k}}h_{k}=1$ of size n with pairwise distinct variables x ₁,…,x _k , the set $S\subseteq \mathbb {N}^{k}$ of solutions is semilinear of magnitude at most p(n).

Note that here, we only consider exponent equations where each variable occurs at most once. This corresponds to the definition of the knapsack problem as introduced by Myasnikov et. al. [44]. This is in contrast to Section 3, where the methods we used to obtain N P membership work for general exponent equations. In the case of the LogCFL membership proof, however, our techniques only apply to the original version of the knapsack problem. See also Remark 2.1.

Observe that although the size of an exponent equation may depend on the chosen generating set of G, changing the generating set increases the size only by a constant factor. Thus, whether or not a group is knapsack tame is independent of the chosen generating set.

Theorem 4.10

If (A,I)is a transitive forest, then $\mathbb {G}(A,I)$ is knapsack tame.

Note that Theorem 4.10 implies in particular that every solvable exponent equation with pairwise distinct variables has a polynomially bounded solution. Theorem 4.10 and Proposition 4.7 easily imply Theorem 4.6.

We prove Theorem 4.10 by showing that knapsack tameness transfers from groups G to $G\times \mathbb {Z}$ (Proposition 4.11) and from G and H to G ∗ H (Proposition 4.17). Since the trivial group is obviously knapsack tame, the inductive characterization of groups $\mathbb {G}(A,I)$ for transitive forests (A,I) immediately yields Theorem 4.10.

4.2.3 Tameness of direct products with $\mathbb {Z}$

In this section, we show the following.

Proposition 4.11

If G is knapsack tame, then so is $G\times \mathbb {Z}$ .

Linear Diophantine equations

We employ a result of Pottier [47], which bounds the norm of minimal non-negative solutions to a linear Diophantine equation. Recall the definition of the vector norms ∥x∥ _∞ and ∥x∥₁ from Section 2.3. Let $A\in \mathbb {Z}^{k\times m}$ be an integer matrix where a _{i j} is the entry of A at row i and column j. We will use the following matrix norms:

$$\begin{array}{@{}rcl@{}} \|A\|_{1,\infty} &=& \max_{i\in[1,k]}\left(\sum\limits_{j\in[1,m]} |a_{ij}|\right), \\ \|A\|_{\infty,1} &=& \max_{j\in[1,m]} \left(\sum\limits_{i\in[1,k]} |a_{ij}|\right), \\ \|A\|_{\infty} &=& \max_{i\in [1,k], j\in[1,m]} |a_{ij}| . \end{array} $$

A non-trivial solution $x\in \mathbb {N}^{m}\setminus \{0\}$ to the equation A x = 0 is minimal if there is no $y\in \mathbb {N}^{m}\setminus \{0\}$ with A y = 0 and y ≤ x, y≠x. Here y ≤ x means that y _i ≤ x _i for all i ∈ [1,m]. The set of all solutions clearly forms a submonoid of $\mathbb {N}^{m}$. Let r be the rank of A.

Theorem 4.12 (Pottier 47)

Each non-trivial minimal solution $x \in \mathbb {N}^{m}$ to A x = 0satisfies ∥x∥₁ ≤ (1 + ∥A∥_1,∞ )^r .

We only need Theorem 4.12 for the case that A is a row vector u ^T for $u \in \mathbb {Z}^{k}$.

Corollary 4.13

Let $u \in \mathbb {Z}^{k}$ . Each non-trivial minimal solution $x \in \mathbb {N}^{k}$ to u ^T x = 0satisfies ∥x∥₁ ≤ 1 + ∥u∥₁ .

By applying Theorem 4.12 to the row vector (u ^T,−b) for $b \in \mathbb {Z}$, it is easy to deduce that for each $x\in \mathbb {N}^{k}$ with u ^T x = b, there is a $y\in \mathbb {N}^{k}$ with u ^T y = b, y ≤ x, and $\|y\|_{1}\le 1+\| \binom {u}{b}\|_{1} = 1+ \|u\|_{1} + |b|$. We reformulate Corollary 4.13 as follows.

Lemma 4.14

Let $u \in \mathbb {Z}^{k}$ and $b \in \mathbb {Z}$ . Then the set $\{x\in \mathbb {N}^{k} \mid u^{T} x=b\}$ admits a decomposition $\{ x\in \mathbb {N}^{k} \mid u^{T} x=b \} = \bigcup _{i=1}^{s} c_{i} + C\mathbb {N}^{t}$ , where $c_{i}\in \mathbb {N}^{k}$ and $C\in \mathbb {N}^{k\times t}$ with ∥c _i ∥₁ and ∥C∥ _∞,1 bounded by 1 + ∥u∥₁ + |b|.

Proof

Let {c ₁,…,c _s } be the set of minimal solutions of u ^T x = b. Then, as explained above, Corollary 4.13 yields ∥c _i ∥₁ ≤ 1 + ∥u∥₁ + |b|. Moreover, let $C\in \mathbb {N}^{k\times t}$ be the matrix whose columns are the non-trivial minimal solutions of u ^T x = 0. Then we have ∥C∥ _∞,1 ≤ 1 + ∥u∥₁. This clearly yields the desired decomposition. □

The problem is that we want to apply Lemma 4.14 in a situation where we have no bound on ∥u∥₁, but only one on ∥u∥ _∞ . The following lemma yields such a bound.

Lemma 4.15

If $u\in \mathbb {Z}^{k}$ and $b\in \mathbb {Z}$ with ∥u∥ _∞ ,|b|≤ M , then we have a decomposition $\{x\in \mathbb {N}^{k} \mid u^{T}x=b \} = \bigcup _{i=1}^{s} c_{i} + C\mathbb {N}^{t} \label {sol-decomp-onedim-final}$ where ∥c _i ∥₁,∥C∥ _∞,1 ≤ 1 + (M + 2)M .

Proof

Write u ^T = (b ₁,…,b _k ) and consider the row vector $v^{T} = (b^{\prime }_{1},\ldots ,b^{\prime }_{2M+1})$, $v \in \mathbb {Z}^{2M+1}$, with entries $b^{\prime }_{i} = i-(M+1)$. Thus, we have

$$v^{T} = (b^{\prime}_{1},\ldots,b^{\prime}_{2M+1})=(-M,-M+1,\ldots,-1,0,1,\ldots,M) .$$

Moreover, define the matrix $S = (s_{ij}) \in \mathbb {N}^{(2M+1)\times k}$ with

$$s_{ij} = \left\{\begin{array}{ll} 1 & \text{if}~ b_{j}=b^{\prime}_{i}, \\ 0 & \text{otherwise.} \end{array}\right. $$

Then clearly u = v ^T S and ∥v∥₁ = (M + 1)M. Furthermore, observe that we have ∥S x∥₁ = ∥x∥₁ for every $x\in \mathbb {N}^{k}$ and that for each $y\in \mathbb {N}^{2M+1}$ the set

$$T_{y} = \{ x\in\mathbb{N}^{k} \mid Sx=y\} $$

is finite.

According to Lemma 4.14, we can write

$$ \{x\in\mathbb{N}^{2M+1} \mid v^{T} x=b \} = \bigcup\limits_{i=1}^{s^{\prime}} c^{\prime}_{i}+C^{\prime}\mathbb{N}^{t^{\prime}} $$

(14)

where $\|c^{\prime }_{i}\|_{1}, \|C^{\prime }\|_{\infty ,1} \leq 1+ (M+1)M + M = 1+(M+2)M$. Let {c ₁,…,c _s } be the union of all sets $T_{c^{\prime }_{i}}$ for i ∈ [1,s ^′] and let $C\in \mathbb {N}^{k\times t}$ be the matrix whose columns comprise all T _v where $v\in \mathbb {N}^{2M+1}$ is a column of C ^′. Since we have ∥S x∥₁ = ∥x∥₁ for $x\in \mathbb {N}^{k}$, the vectors c _i obey the same bound as the vectors $c^{\prime }_{i}$, meaning ∥c _i ∥₁ ≤ 1 + (M + 2)M. By the same argument, we have ∥C∥ _∞,1 ≤∥C ^′∥ _∞,1 ≤ 1 + (M + 2)M. It remains to be shown that the equality from Lemma 4.15 holds.

Suppose u ^T x = b. Then v ^T S x = b and hence $Sx=c^{\prime }_{i}+C^{\prime }y$ for some $y\in \mathbb {N}^{t^{\prime }}$. Observe that every column of S is either zero or a unit vector. This implies that if S z = p + q for $p,q \in \mathbb {N}^{2M+1}$, then z decomposes as z = p ^′ + q ^′, $p^{\prime },q^{\prime } \in \mathbb {N}^{k}$, so that S p ^′ = p and S q ^′ = q. Therefore, we can write x = x ₀ + ⋯ + x _n with $Sx_{0}=c^{\prime }_{i}$ and S x _j is some column of C ^′ for each j ∈ [1,n]. Hence, x ₀ = c _r for some r ∈ [1,s] and for each j ∈ [1,n], x _j is a column of C. This proves $x\in c_{r} + C\mathbb {N}^{t}$.

On the other hand, the definition of c ₁,…,c _s and C implies that for each column v of C, S v is a column of C ^′. Moreover, for each i ∈ [1,s], there is a j ∈ [1,s ^′] with $Sc_{i}=c^{\prime }_{j}$ and thus $Sc_{i}+SC\mathbb {N}^{t}\subseteq c^{\prime }_{j}+C^{\prime }\mathbb {N}^{t^{\prime }}$. Therefore

$$u^{T}(c_{i}+C\mathbb{N}^{t}) =v^{T}S(c_{i}+C\mathbb{N}^{t})\subseteq v^{T}(c^{\prime}_{j}+C^{\prime}\mathbb{N}^{t^{\prime}}) $$

and the latter set contains only b because of (14). □

Lemma 4.16

Let $S\subseteq \mathbb {N}^{k}$ be a semilinear set of magnitude M and $u\in \mathbb {Z}^{k}$ , $b\in \mathbb {Z}$ with ∥u∥ _∞ ,|b|≤ m . Then {x ∈ S∣u ^T x = b}is a semilinear set of magnitude at most 10(k m M)³ .

Proof

Let $T=\{x\in \mathbb {N}^{k} \mid u^{T}x=b\}$. We may assume that S is linear of magnitude M, because if S = L ₁ ∪⋯ ∪ L _n , then S ∩ T = (L ₁ ∩ T) ∪⋯ ∪ (L _n ∩ T).

Write $S=a+A\mathbb {N}^{n}$ with $a\in \mathbb {N}^{k}$ and $A\in \mathbb {N}^{k\times n}$, where ∥a∥ _∞ ≤ M and ∥A∥ _∞ ≤ M. Consider the set $U=\{x\in \mathbb {N}^{n} \mid u^{T} Ax=b-u^{T} a\}$. Note that $u^{T} A\in \mathbb {Z}^{1\times n}$ and

$$\|u^{T}A\|_{\infty} \le k\cdot \|u\|_{\infty} \cdot \|A\|_{\infty} \le kmM, $$

$$|b-u^{T}a| \le m+k\cdot \|u\|_{\infty} \cdot \|a\|_{\infty}\le m+kmM. $$

According to Lemma 4.15, we can write $U=\bigcup _{i=1}^{s} c_{i}+C\mathbb {N}^{t}$ where ∥c _i ∥₁ and ∥C∥ _∞,1 are at most 1 + (m + k m M)(m + k m M + 2) ≤ 9(k m M)². Observe that

$$a+AU = \bigcup\limits_{i=1}^{s} a+Ac_{i}+AC\mathbb{N}^{t} $$

and

$$\|a+Ac_{i}\|_{\infty}\le \|a\|_{\infty} + \|A\|_{\infty}\cdot \|c_{i}\|_{1} \le M+M\cdot 9(kmM)^{2}\le 10(kmM)^{3} , $$

$$\| AC \|_{\infty} \le \|A\|_{\infty} \cdot \|C\|_{\infty,1} \le M\cdot 9(kmM)^{2} \le 10(kmM)^{3}. $$

Finally, note that S ∩ T = a + A U. □

We are now ready to prove Proposition 4.11.

Proof

of Proposition 4.11. Suppose G is knapsack tame with polynomial $\bar {p}$. Let

$$ h_{0}g_{1}^{x_{1}}h_{1}g_{2}^{x_{2}}h_{2}{\cdots} g_{k}^{x_{k}}h_{k}=1 $$

(15)

be an exponent equation of size n with pairwise distinct variables x ₁,…,x _k and with $h_{0},g_{1},h_{1},\ldots ,g_{k},h_{k}\in G\times \mathbb {Z}$. Let $h_{i}=(\bar {h}_{i},y_{i})$ for i ∈ [0,k] and $g_{i}=(\bar {g}_{i},z_{i})$ for i ∈ [1,k].

The exponent equation $\bar {h}_{0}\bar {g}_{1}^{x_{1}}\bar {h}_{1}\bar {g}_{2}^{x_{2}}\bar {h}_{2}\cdots \bar {g}_{k}^{x_{k}}\bar {h}_{k}=1$ has a semilinear solution set $\bar {S}\subseteq \mathbb {N}^{k}$ of magnitude at most $\bar {p}(n)$. The solution set of (15) is

$$S=\{ (x_{1},\ldots,x_{k})\in\bar{S} \mid z_{1}x_{1}+\cdots +z_{k}x_{k}=y \}, $$

where y = −(y ₀ + ⋯ + y _k ). Note that |z _i |≤ n and |y|≤ n. By Lemma 4.16, S is semilinear of magnitude $10(n^{2}\bar {p}(n))^{3}$ (recall that k ≤ n). □

4.2.4 Tameness of free products

This section is devoted to the proof of the following proposition.

Proposition 4.17

If G ₀ and G ₁ are knapsack tame, then so is G ₀ ∗ G ₁ .

Let G = G ₀ ∗ G ₁. Suppose that for i ∈{0,1}, the group G _i is generated by A _i , where w.l.o.g. $A_{i}^{-1}=A_{i}$ and let A = A ₀ ⊎ A ₁, which generates G. Recall that every g ∈ G can be written uniquely as g = g ₁⋯g _n where n ≥ 0, g _i ∈ (G ₀ ∖{1}) ∪ (G ₁ ∖{1}) for each i ∈ [1,n] and where g _j ∈ G _t iff g _j+1 ∈ G _1−t for j ∈ [1,n − 1]. We call g cyclically reduced if for some t ∈{0,1}, either g ₁ ∈ G _t and g _n ∈ G _1−t or g ₁,g _n ∈ G _t and g _n g ₁≠1. Consider an exponent equation

$$ h_{0}g_{1}^{x_{1}}h_{1}{\cdots} g_{k}^{x_{k}}h_{k}=1, $$

(16)

of size n, where g _i is represented by u _i ∈ A ^∗ for i ∈ [1,k] and h _i is represented by v _i ∈ A ^∗ for i ∈ [0,k]. Then clearly ${\sum }_{i=0}^{k} |v_{i}|+{\sum }_{i=1}^{k} |u_{i}|\le n$. Let $S\subseteq \mathbb {N}^{k}$ be the set of all solutions to (16). Every word w ∈ A ^∗ has a (possibly empty) unique factorization into maximal factors from $A_{0}^{+}\cup A_{1}^{+}$, which we call syllables. By ∥w∥, we denote the number of syllables of w. The word w is reduced if none of its syllables represents 1 (in G ₀ resp. G ₁). We define the maps λ,ρ: A ⁺ → A ⁺ (”rotate left/right”), where for each word w ∈ A ⁺ with its factorization w = w ₁⋯w _m into syllables, we set λ(w) = w ₂⋯w _m w ₁ and ρ(w) = w _m w ₁ w ₂⋯w _m−1.

Consider a word w ∈ A ^∗ and suppose w = w ₁⋯w _m , m ≥ 0, where for each i ∈ [1,m], we have $w_{i}\in A_{j}^{+}$ for some j ∈{0,1} (we allow that $w_{i}, w_{i+1} \in A_{j}^{+}$). A cancelation is a subset C ⊆ 2^[1,m] that is

• a partition: $\bigcup _{I\in C} I=[1,m]$ and I ∩ J = ∅ for any I,J ∈ C with I≠J.

• consistent: for each I ∈ C, there is an i ∈{0,1} such that $w_{j}\in A_{i}^{+}$ for all j ∈ I.

• canceling: if {i ₁,…,i _ℓ }∈ C with i ₁ < ⋯ < i _ℓ , then $w_{i_{1}}{\cdots } w_{i_{\ell }}$ represents 1 in G.

• well-nested: there are no I,J ∈ C with i ₁,i ₂ ∈ I and j ₁,j ₂ ∈ J such that i ₁ < j ₁ < i ₂ < j ₂.

• maximal: if $w_{i}, w_{i+1} \in A_{j}^{+}$ for j ∈{0,1} then there is an I ∈ C with i,i + 1 ∈ I.

Since C can be regarded as a hypergraph on [1,m], the elements of C will be called edges. We have the following simple fact:

Lemma 4.18

Let w = w ₁⋯w _m , m ≥ 0, where for each i ∈ [1,m], we have $w_{i}\in A_{j}^{+}$ for some j ∈{0,1}. Then w admits a cancelation if and only if it represents 1 in G.

Proof

Assume that w represents 1 in the free product G. The case w = ε is clear; hence assume that w≠ε. Then there must exist a factor w _i w _i+1⋯w _j representing 1 in G such that (i) $w_{i} w_{i+1} {\cdots } w_{j} \in A_{k}^{+}$ for some k ∈{0,1}, (ii) either i = 1 or $w_{i-1} \in A_{1-k}^{+}$, and (iii) either j = m or $w_{j+1} \in A_{1-k}^{+}$. The word w ^′ = w ₁⋯w _i−1 w _j+1⋯w _m also represents 1 in G. By induction, w ^′ admits a cancelation C ^′. Let C ^″ be obtained from C ^′ by replacing every occurrence of an index k ≥ i in C ^′ by k + j − i + 1. Then C = C ^″∪{[i,j]} is a cancelation for w.

For the other direction let us call a partition C ⊆ 2^[1,m] a weak cancelation if it is consistent, canceling and well-nested (but not necessarily maximal). Then we show by induction that w represents 1, if it has a weak cancelation. So, let C be a weak cancelation of w≠ε. Then there must exist an interval [i,j] ∈ C (otherwise C would be not well-nested). Then w _i w _i+1⋯w _j represents 1 in G. Consider the word w ^′ = w ₁⋯w _i−1 w _j+1⋯w _m . Let C ^′ be obtained from C ∖{[i,j]} by replacing every occurrence of an index k ≥ j + 1 in C ∖{[i,j]} by k − j + i − 1. Then C ^′ is a weak cancelation for w ^′. Hence, w ^′ represents 1, which implies that w represents 1. □

Of course, when showing that the solution set of (16) has a polynomial magnitude, we may assume that g _i ≠1 for any i ∈ [1,k]. Moreover, we lose no generality by assuming that all words u _i , i ∈ [1,k] and v _i , i ∈ [0,k] are reduced. Furthermore, we may assume that each g _i is cyclically reduced. Indeed, if some g _i is not cyclically reduced, we can write g _i = f ⁻¹ g f for some cyclically reduced g and replace h _i−1, g _i , and h _i by h _i−1 f ⁻¹, g = f g _i f ⁻¹, and f h _i , respectively. This does not change the solution set because

$$h_{i-1}f^{-1}(fg_{i}f^{-1})^{x_{i}}fh_{i}=h_{i-1}g_{i}^{x_{i}}h_{i}. $$

Moreover, if we do this replacement for each g _i that is not cyclically reduced, we increase the size of the instance by at most 2|g ₁| + ⋯ + 2|g _k |≤ 2n (note that |g| = |g _i |). Applying this argument again, we may even assume that

$$ u_{i}\in A_{0}^{+}\cup A_{1}^{+}\cup A_{0}^{+}A^{*}A_{1}^{+} \cup A_{1}^{+}A^{*}A_{0}^{+} $$

(17)

for every i ∈ [1,k]. Note that λ and ρ are bijections on words of this form.

Consider a solution (x ₁,…,x _k ) to (16). Then the word

$$ w=v_{0}u_{1}^{x_{1}}v_{1}{\cdots} u_{k}^{x_{k}}v_{k} $$

(18)

represents 1 in G. We factorize each v _i , i ∈ [0,k], and each u _i , i ∈ [1,k], into its syllables. These factorizations define a factorization w = w ₁⋯w _m and we call this the block factorization of w. This is the coarsest refinement of the factorization $w=v_{0}u_{1}^{x_{1}}v_{1}{\cdots } u_{k}^{x_{k}}v_{k}$ and of w’s factorization into syllables. The numbers 1,2,…,m are the blocks of w. We fix this factorization w = w ₁⋯w _m for the rest of this section.

Cycles and certified solutions

In the representation v ₀ u1x ₁ v ₁⋯u k x _k v _k = 1 of (16), the words u ₁,…,u _k are called the cycles. If $u_{i}\in A_{0}^{+}\cup A_{1}^{+}$, the cycle u _i is said to be simple and otherwise mixed (note that u _i = ε cannot happen because g _i ≠1). Let p be a block of w. If w _p is contained in some $u_{i}^{x_{i}}$ for a cycle u _i , then p is a u _i -blocks or block from u _i . If w _p is contained in some v _i , then p is a v _i -block or a block from v _i . A certified solution is a pair (x,C), where x is a solution to (16) and C is a cancelation of the word w as in (18).

Observe that if C ⊆ 2^[1,m] is a cancelation for w = w ₁⋯w _m then by maximality, for each simple cycle u _i , all u _i -blocks are contained in the same edge of C. We will also need the following two auxiliary lemmas.

Lemma 4.19

Let C be a cancelation. If i,j are two distinct blocks from the same mixed cycle, then there is no edge I ∈ C with i,j ∈ I .

Proof

Suppose there is such an I ∈ C. Furthermore, assume that i and j are chosen so that |i − j| is minimal and i < j. Since i,j ∈ I, we have $w_{i}w_{j}\in A_{0}^{+}\cup A_{1}^{+}$ by consistency of C. Hence, i and j cannot be neighbors. Therefore there is an ℓ ∈ [1,m] with i < ℓ < j. This means there is a J ∈ C with ℓ ∈ J. By well-nestedness, J ⊆ [i,j]. Since every edge in C must contain at least two elements, we have |J|≥ 2 and thus a contradiction to the minimality of |i − j|. □

An edge I ∈ C is called standard if |I| = 2 and the two blocks in I are from mixed cycles. Intuitively, the following lemma tells us that in a cancelation, most edges are standard.

Lemma 4.20

Let C be a cancelation and u _i be a mixed cycle. Then there are at most n + 3k + 1non-standard edges I ∈ C containing a u _i -block.

Proof

Let N ⊆ C be the set of all non-standard edges I ∈ C that contain a u _i -block. Then, each edge I ∈ N satisfies one of the following.

• (i) I contains a block from some simple cycle. There are at most k such I.

• (ii) I contains a block from some v _j , j ∈ [0,k]. Since ∥v ₀∥ + ⋯ + ∥v _k ∥≤ n, there are at most n such I.

• (iii) I contains only blocks from mixed cycles and |I| > 2.

Let M ⊆ C be the set of edges of type (4.2.4). If we can show that |M|≤ 2k + 1, then the lemma is proven. Consider the sets

$$\begin{array}{@{}rcl@{}} M_{-} &=& \{ I\in M \mid I \ \text{contains a block from a mixed cycle}\ u_{j}, j<i \}, \\ M_{+} &=& \{ I\in M \mid I\ \text{contains a block from a mixed cycle} \ u_{j}, j>i \}. \end{array} $$

We shall prove that |M ₋∩ M ₊|≤ 1 and that |M ₊ ∖ M ₋|≤ k. By symmetry, this also means |M ₋∖ M ₊|≤ k and thus |M| = |M ₋∪ M ₊|≤ 2k + 1.

Suppose I ₁,I ₂ ∈ M ₋∩ M ₊, I ₁≠I ₂. Let r ∈ I ₁ and s ∈ I ₂ such that r and s are blocks from u _i , say with r < s. Since I ₁ ∈ M ₊, I ₁ contains a block r ^′ from a mixed cycle u _j , j > i. This means in particular s < r ^′. By well-nestedness, this implies I ₂ ⊆ [r,r ^′], so that I ₂ cannot contain a block from a mixed cycle u _ℓ with ℓ < i, contradicting I ₂ ∈ M ₋. Thus, |M ₋∩ M ₊|≤ 1.

In order to prove |M ₊ ∖ M ₋|≤ k, we need another concept. For each I ∈ M ₊, there is a maximal j ∈ [1,k] such that u _j is a mixed cycle and I contains a block from u _j . Let μ(I) = j. We will show μ(I ₁)≠μ(I ₂) for all I ₁,I ₂ ∈ M ₊ ∖ M ₋, I ₁≠I ₂. This clearly implies |M ₊ ∖ M ₋|≤ k.

Suppose I ₁,I ₂ ∈ M ₊ ∖ M ₋, I ₁≠I ₂, with μ(I ₁) = μ(I ₂). Let j = μ(I ₁) = μ(I ₂). Let r be a block from u _i contained in I ₁ and let r ^′ be a block from u _i contained in I ₂. (Recall that those exist because I ₁,I ₂ ∈ M.) Without loss of generality, assume r < r ^′. Moreover, let s be a block from u _j contained in I ₁ and let s ^′ be a block from u _j contained in I ₂. Thus, we have r < r ^′ < s ^′.

However, we have |I ₁| > 2, meaning I ₁ contains a block p other than r and s. Since an edge cannot contain two blocks of one mixed cycle (Lemma 4.19), p has to belong to a mixed cycle u _t other than u _i and u _j . By the maximality of j, we have i < t < j. This implies, however, r < r ^′ < p < s ^′, which contradicts well-nestedness. □

Mixed periods

From now on, for each i ∈ [1,k], we use e _i to denote the i-th unit vector in $\mathbb {N}^{k}$, i.e. the vector with 1 in the i-th coordinate and 0 otherwise. A mixed period is a vector $\pi \in \mathbb {N}^{k}$ of the form ∥u _j ∥⋅ e _i + ∥u _i ∥⋅ e _j , where u _i and u _j are mixed cycles. Let $\mathbb {P}\subseteq \mathbb {N}^{k}$ be the set of mixed periods. Note that $|\mathbb {P}|\le k^{2}$.

We will need a condition that guarantees that a given period $\pi \in \mathbb {P}$ can be added to a solution x to obtain another solution. Suppose we have two blocks p and q for which we know that if we insert a string f ₁ to the left of w _p and a string f ₂ to the right of w _q and f ₁ f ₂ cancels to 1 in G, then the whole word cancels to 1. Which string would we insert to the left of w _p and to the right of w _q if we build the solution x + π?

Suppose p is a u _i -block and q is a u _j -block. Moreover, let r be the first (left-most) u _i -block and let s be the last (right-most) u _j -block. If we add ∥u _j ∥⋅ e _i to x, this inserts $\lambda ^{p-r}(u_{i}^{\|u_{j}\|})$ to the left of w _p : Indeed, in the case p = r, we insert $u_{i}^{\|u_{j}\|}$; and when p moves one position to the right, the inserted string is rotated once to the left. Similarly, if we add ∥u _i ∥⋅ e _j to x, we insert $\rho ^{s-q}(u_{j}^{\|u_{i}\|})$ to the right of w _q : This is clear for q = s and decrementing q means rotating the inserted string to the right. This motivates the following definition.

Let (x,C) be a certified solution and let u _i and u _j be mixed cycles with i < j. Moreover, let r ∈ [1,m] be the left-most u _i -block and let s ∈ [1,m] be the right-most u _j -block. Then the mixed period π = ∥u _j ∥⋅ e _i + ∥u _i ∥⋅ e _j is compatible with (x,C) if there are a u _i -block p and a u _j -block q such that

$$ \{p,q\}\in C ~\text{and}~ \lambda^{p-r}(u_{i}^{\|u_{j}\|})\rho^{s-q}(u_{j}^{\|u_{i}\|})~ \text{represents 1 in}~ G. $$

(19)

With $\mathbb {P}(x,C)$, we denote the set of mixed periods that are compatible with (x,C). One might wonder why we require an edge {p,q}∈ C. In order to guarantee that $\lambda ^{p-r}(u_{i}^{\|u_{j}\|})$ and $\rho ^{s-q}(u_{j}^{\|u_{i}\|})$ can cancel, it would be sufficient to merely forbid edges I ∈ C that intersect [p,q] and contain a block outside of [p − 1,q + 1]. However, this weaker condition can become false when we insert other mixed periods. Our stronger condition is preserved, which implies:

Lemma 4.21

Let (x,C)be a certified solution. Then every $x^{\prime }\in x+\mathbb {P}(x,C)^{\oplus }$ is a solution.

Proof

It suffices to show that if (x,C) is a certified solution and $\pi \in \mathbb {P}(x,C)$, then there is a certified solution (x ^′,C ^′) such that x ^′ = x + π and $\mathbb {P}(x,C)\subseteq \mathbb {P}(x^{\prime },C^{\prime })$. Suppose $\pi =\|u_{j}\|\cdot e_{i} + \|u_{i}\|\cdot e_{j} \in \mathbb {P}(x,C)$. Without loss of generality, assume i < j. Let r ∈ [1,m] be the left-most u _i -block and s ∈ [1,m] be the right-most u _j -block in w. Since $\pi \in \mathbb {P}(x,C)$, there is a u _i -block p and a u _j -block q such that (19) holds. As explained above, we can insert $\lambda ^{p-r}(u_{i}^{\|u_{j}\|})$ on the left of w _p and $\rho ^{s-q}(u_{j}^{\|u_{i}\|})$ on the right of w _q and thus obtain a word w ^′ that corresponds to the vector x ^′ = x + π.

Both inserted words consist of ∥u _j ∥⋅∥u _i ∥ many blocks and they cancel to 1, which means we can construct a cancelation C ^′ from C as follows. Between the two sequences of inserted blocks, we add two-element edges so that the left-most inserted u _i -block is connected to the right-most inserted u _j -block, and so forth. The blocks that existed before are connected by edges as in C. It is clear that then, C ^′ is a partition that is consistent, canceling and maximal. Moreover, since there is an edge {p,q}, the new edges between the inserted blocks do not violate well-nestedness: If there were a crossing edge, then there would have been one that crosses {p,q}.

It remains to verify $\mathbb {P}(x,C)\subseteq \mathbb {P}(x^{\prime },C^{\prime })$. A mixed period $\pi ^{\prime } \in \mathbb {P}(x,C) \setminus \{\pi \}$ is clearly contained in $\mathbb {P}(x^{\prime },C^{\prime })$ too. Hence, it remains to show $\pi \in \mathbb {P}(x^{\prime },C^{\prime })$. This, however, follows from the fact that instead of the edge {p,q} that witnesses compatibility of π with (x,C), we can use its counterpart in C ^′; let us call this edge {p ^′,q ^′}: If r ^′ is the left-most u _i -block in w ^′ and s ^′ is the right-most u _j -block in w ^′, then p ^′− r ^′ = p − r + ∥u _i ∥⋅∥u _j ∥ and s ^′− q ^′ = s − q + ∥u _i ∥⋅∥u _j ∥. This implies $\lambda ^{p-r}(u_{i}^{\|u_{j}\|})=\lambda ^{p^{\prime }-r^{\prime }}(u_{i}^{\|u_{j}\|})$ and $\rho ^{s-q}(u_{j}^{\|u_{i}\|})=\rho ^{s^{\prime }-q^{\prime }}(u_{j}^{\|u_{i}\|})$ which implies that (19) holds for the edge {p ^′,q ^′}. This completes the proof of the lemma. □

We shall need another auxiliary lemma.

Lemma 4.22

Let C be a cancelation for w. Let u _i and u _j be distinct mixed cycles. Let D ⊆ C be the set of standard edges I ∈ C that contain one block from u _i and one block from u _j . Then the set

$$B = \{ p \in [1,m] \mid p \text{ is a \(u_{i}\)-block and \(p\in I\) for some \(I\in D\)}\} $$

is aninterval.

Proof

We prove the case i < j, the other follows by symmetry. Suppose there are r ₁,r ₂ ∈ B such that r ₁ < r ₂ and there is no t ∈ B with r ₁ < t < r ₂.

Toward a contradiction, suppose r ₂ − r ₁ > 1. Since r ₁,r ₂ ∈ B, there are I ₁,I ₂ ∈ D with r ₁ ∈ I ₁ and r ₂ ∈ I ₂. Let I ₁ = {r ₁,s ₁} and I ₂ = {r ₂,s ₂}. Then s ₁ and s ₂ are u _j -blocks and by well-nestedness, we have r ₁ < r ₂ < s ₂ < s ₁. Since r ₂ − r ₁ > 1, there is a t with r ₁ < t < r ₂ and therefore some J ∈ C with t ∈ J. Since |J|≥ 2, there has to be a t ^′∈ J, t ^′≠t. However, well-nestedness dictates that t ^′∈ [r ₁,s ₁] ∖ [r ₂,s ₂]. Since J cannot contain another block from u _i (Lemma 4.19), we cannot have t ^′∈ [r ₁,r ₂], which only leaves t ^′∈ [s ₂,s ₁]. Hence, t ^′ is from u _j . By the same argument, any block t ^″∈ J ∖{t,t ^′} must be from u _i or u _j , contradicting Lemma 4.19. This means |J| = 2 and thus t ∈ B, in contradiction to the choice of r ₁ and r ₂. □

Let M ⊆ [1,k] be the set of i ∈ [1,k] such that u _i is a mixed cycle. We define a new norm on vectors $x\in \mathbb {N}^{k}$ by setting ∥x∥ _M = maxi∈M x _i .

Lemma 4.23

There is a polynomial q such that the following holds. For every certified solution (x,C)with ∥x∥ _M > q(n), there exists a mixed period $\pi \in \mathbb {P}(x,C)$ and a certified solution (x ^′,C ^′)such that x ^′ = x − π and $\mathbb {P}(x,C)\subseteq \mathbb {P}(x^{\prime },C^{\prime })$ .

Proof

We show that the lemma holds if q(n) ≥ (n + 3k + 1) + k n ². (Recall that k ≤ n.) Let (x,C) be a certified solution with ∥x∥ _M > q(n). Then there is a mixed cycle u _i such that x _i > q(n) and hence $u_{i}^{x_{i}}$ consists of more than q(n) blocks. Let D ⊆ C be the set of all edges I ∈ C that contain a block from u _i . Since an edge can contain at most one block per mixed cycle (Lemma 4.19), we have |D| > q(n). Hence, Lemma 4.20 tells us that D contains more than k n ² standard edges. Hence, there exists a mixed cycle u _j such that the set E ⊆ D of standard edges I ∈ D that consist of one block from u _i and one block from u _j satisfies |E| > n ². If B _i (resp., B _j ) denotes the set of blocks from u _i (resp., u _j ) contained in some edge I ∈ E, then each of the sets B _i and B _j has to be an interval (Lemma 4.22) of size more than n ².

We only deal with the case i < j, the case i > j can be done similarly. Let us take a subinterval [p ^′,p] of B _i such that p − p ^′ = ∥u _i ∥⋅∥u _j ∥≤ n ². By well-nestedness and since B _j is an interval, the neighbors (with respect to the edges from E) of [p ^′,p] form an interval [q,q ^′] ⊆ B _j as well, and we have p − p ^′ = q ^′− q = ∥u _i ∥⋅∥u _j ∥. Moreover, we have an edge {p − ℓ,q + ℓ}∈ E for each ℓ ∈ [0,p − p ^′]. In particular, $w_{p^{\prime }}w_{p^{\prime }+1}{\cdots } w_{p-1}w_{q+1}{\cdots } w_{q^{\prime }}$ represents 1 in G.

Let r be the left-most u _i -block and let s be the right-most u _j -block. Then, as shown before the definition of compatibility (p. 44), we have

$$\begin{array}{llll}\lambda^{p-r}(u_{i}^{\|u_{j}\|}) = w_{p^{\prime}}w_{p^{\prime}+1}{\cdots} w_{p-1}, && \qquad\quad\rho^{s-q}(u_{j}^{\|u_{i}\|}) = w_{q+1}w_{q+1}{\cdots} w_{q^{\prime}}. \end{array} $$

Therefore, $\lambda ^{p-r}(u_{i}^{\|u_{j}\|})\rho ^{s-q}(u_{j}^{\|u_{i}\|})$ represents 1 in G and {p,q} witnesses compatibility of π = ∥u _j ∥⋅ e _i + ∥u _i ∥⋅ e _j with (x,C). Hence, $\pi \in \mathbb {P}(x,C)$.

Let x ^′ = x − π. We remove the factors $w_{p^{\prime }} {\cdots } w_{p-1}$ and $w_{q+1}{\cdots } w_{q^{\prime }}$ from w. Then, the remaining blocks spell $w^{\prime }=v_{0}u_{1}^{x^{\prime }_{1}}v_{1}{\cdots } u_{k}^{x^{\prime }_{k}}v_{k}$. Indeed, recall that removing from a word y ^t any factor of length ℓ ⋅|y| will result in the word y ^t−ℓ. Moreover, let C ^′ be the set of edges that agree with C on the remaining blocks. By the choice of the removed blocks, it is clear that C ^′ is a cancelation for w ^′. Hence, (x ^′,C ^′) is a certified solution.

It remains to verify $\mathbb {P}(x,C)\subseteq \mathbb {P}(x^{\prime },C^{\prime })$. First note that for every mixed cycle u _ℓ , all u _ℓ -blocks that remain in w ^′ change their position relative to the left-most and the right-most u _ℓ -block by a difference that is divisible by ∥u _ℓ ∥ (if i≠ℓ≠j then these relative positions do not change at all). Note that the expression $\lambda ^{p-r}(u_{i}^{\|u_{j}\|})$ is not altered when p − r changes by a difference divisible by ∥u _i ∥, and an analogous fact holds for $\rho ^{s-q}(u_{j}^{\|u_{i}\|})$. Hence, the edge in C ^′ that corresponds to the C-edge {p,q} is a witness for $\pi \in \mathbb {P}(x^{\prime },C^{\prime })$. Moreover, for all other mixed periods $\pi ^{\prime } \in \mathbb {P}(x,C) \setminus \{\pi \}$ that are witnessed by an edge {t,u}∈ C, the blocks t and u do not belong to [p ^′,p − 1] ∪ [q + 1,q ^′]. Therefore, the corresponding edge in C ^′ exists and serves as a witness for $\pi ^{\prime } \in \mathbb {P}(x^{\prime },C^{\prime })$. □

Lemma 4.24

There exists a polynomial q such that the following holds. For every solution $x\in \mathbb {N}^{k}$ , there exists a certified solution (x ^′,C ^′)such that ∥x ^′∥ _M ≤ q(n)and $x\in x^{\prime }+\mathbb {P}(x^{\prime },C^{\prime })^{\oplus }$ .

Proof

Let q be the polynomial provided by Lemma 4.23. Since x is a solution, there is a certified solution (x,C). Repeated application of Lemma 4.23 yields certified solutions (x ₀,C ₀),…,(x _m ,C _m ) and mixed periods π ₁,…,π _m such that (x ₀,C ₀) = (x,C), $\pi _{i}\in \mathbb {P}(x_{i-1},C_{i-1}) \subseteq \mathbb {P}(x_{i},C_{i})$, x _i = x _i−1 − π _i , and ∥x _m ∥ _M ≤ q(n). In particular, $\mathbb {P}(x_{m},C_{m})$ contains each π _i and hence

$$x=x_{m}+\pi_{1}+\cdots+\pi_{m}\in x_{m}+\mathbb{P}(x_{m},C_{m})^{\oplus}. $$

Thus, (x ^′,C ^′) = (x _m ,C _m ) is the desired certified solution. □

We are now ready to prove Proposition 4.17 and thus Theorem 4.10.

Proof

of Proposition 4.17. Suppose that p ₀ and p ₁ are the polynomials guaranteed by the knapsack tameness of G ₀ and G ₁, respectively. Recall that $S\subseteq \mathbb {N}^{k}$ is the set of solutions to (16). We prove that there exists a polynomial p such that for every x ∈ S there is a semilinear set $S^{\prime }\subseteq \mathbb {N}^{k}$ of magnitude at most p(n) such that x ∈ S ^′⊆ S. This clearly implies that S has magnitude at most p(n). First, we apply Lemma 4.24. It yields a polynomial q and a certified solution (x ^′,C ^′) with ∥x ^′∥ _M ≤ q(n) such that $x\in x^{\prime }+\mathbb {P}(x^{\prime },C^{\prime })^{\oplus }$. Let $w^{\prime } = v_{0}u_{1}^{x^{\prime }_{1}}v_{1}{\cdots } u_{k}^{x^{\prime }_{k}}v_{k}$ and consider w ^′ decomposed into blocks as we did above with w.

Let us briefly describe the idea of the remaining steps to construct S ^′. The semilinear set $x^{\prime }+\mathbb {P}(x^{\prime },C^{\prime })$ already satisfies $x\in x^{\prime }+\mathbb {P}(x^{\prime },C^{\prime })\subseteq S$. The only entries in the semilinear representation for $x^{\prime }+\mathbb {P}(x^{\prime },C^{\prime })$ that are not polynomially bounded yet are the coordinates of x ^′ that correspond to simple cycles. Therefore, we consider the set T ⊆ [1,k] of all i ∈ [1,k] for which the cycle u _i is simple. In order to reduce the entries at these coordinates as well, we partition T according to which edge of C ^′ the blocks from a cycle u _i , i ∈ T, belong to. (Recall that by maximality of C ^′, all the blocks of a simple cycle belong to the same edge.) Then, all blocks that belong to the same edge (i) belong to G _s for some s ∈{0,1} and (ii) yield 1 in G _s . Therefore, these blocks form a solution to a knapsack instance over G _s , to which we can apply knapsack tameness of G _s .

Let us make this idea precise. Since C ^′ is maximal, for each i ∈ T, all u _i -blocks are contained in one edge I _i ∈ C ^′. Note that it is allowed that one edge contains the blocks of multiple simple cycles. We partition T into sets T = T ₁ ⊎⋯ ⊎ T _t so that i ∈ T and j ∈ T belong to the same part if and only if the u _i -blocks and the u _j -blocks belong to the same edge of C, i.e. I _i = I _j .

For a moment, let us fix an ℓ ∈ [1,t] and let I ∈ C ^′ be the edge containing all u _i -blocks for all the i ∈ T _ℓ . Moreover, let T _ℓ = {i ₁,…,i _r }. The words $\bar {v}_{j}$ for j ∈ [0,r] will collect those blocks that belong to I but are not $u_{i_{s}}$-blocks for any s ∈ [1,r]. Formally:

• 1. $\bar {v}_{0}$ consists of all blocks that belong to I that are to the left of all $u_{i_{1}}$-blocks.

• 2. Similarly, $\bar {v}_{r}$ is the concatenation of all blocks belonging to I that are to the right of all $u_{i_{r}}$-blocks.

• 3. Finally, for j ∈ [1,r − 1], $\bar {v}_{j}$ consists of all blocks that belong to I and are to the right of all $u_{i_{j}}$-blocks and to the left of all $u_{i_{j+1}}$-blocks.

By consistency of C ^′, for some s ∈{0,1}, all the words $\bar {v}_{j}$ for j ∈ [0,r] and the words $u_{i_{j}}$ for j ∈ [1,r] belong to $A_{s}^{*}$ and thus represent elements of G _s . Since G _s is knapsack tame, the set

$$S_{\ell}=\{ z\in\mathbb{N}^{k} \mid \bar{v}_{0} u_{i_{1}}^{z_{i_{1}}} \bar{v}_{1} u_{i_{2}}^{z_{i_{2}}} \bar{v}_{2}{\cdots} u_{i_{r}}^{z_{i_{r}}}\bar{v}_{r} \text{\ represents 1 in \(G_{s}\), \(z_{j}=0\) for \(j\notin T_{\ell}\)}\}$$

has magnitude at most p _s (n). Consider the vector $y\in \mathbb {N}^{k}$ with y _i = 0 for i ∈ T and $y_{i}=x^{\prime }_{i}$ for i ∈ [1,k] ∖ T (i.e. when u _i is a mixed cycle). We claim that $S^{\prime } = y + S_{1} + {\cdots } S_{t} + \mathbb {P}(x^{\prime },C^{\prime })^{\oplus }$ has magnitude at most q(n) + p ₀(n) + p ₁(n) + n and satisfies x ∈ S ^′⊆ S.

First, since y and the members of S ₁,…,S _t are non-zero on pairwise disjoint coordinates, the magnitude of y + S ₁ + ⋯ + S _t is the maximum of ∥y∥ _∞ and the maximal magnitude of S ₁,…,S _t . Hence, it is bounded by q(n) + p ₀(n) + p ₁(n). The summand $\mathbb {P}(x^{\prime },C^{\prime })^{\oplus }$ contributes only periods, and their magnitude is bounded by n (recall that they are mixed periods). Thus, the magnitude of S ^′ is at most p(n) = q(n) + p ₀(n) + p ₁(n) + n.

The canceling property of (x ^′,C ^′) tells us that x ^′− y is contained in the sum S ₁ + ⋯ + S _t . By the choice of (x ^′,C ^′), we have $x\in x^{\prime }+\mathbb {P}(x^{\prime },C^{\prime })^{\oplus }$. Together, this means x ∈ S ^′. Hence, it remains to show S ^′⊆ S. To this end, consider a vector x ^″∈ y + S ₁ + ⋯ + S _t . It differs from x ^′ only in the exponents at simple cycles. Therefore, we can apply essentially the same cancelation to x ^″ as to x ^′: we just need to adjust the edges containing the blocks of simple cycles. It is therefore clear that the resulting cancelation C ^″ has the same compatible mixed periods as C ^′: $\mathbb {P}(x^{\prime \prime },C^{\prime \prime })=\mathbb {P}(x^{\prime },C^{\prime })$. Thus, by Lemma 4.21, we have $x^{\prime \prime }+\mathbb {P}(x^{\prime },C^{\prime })^{\oplus } \subseteq S$. This proves $S^{\prime } = y+S_{1}+\cdots +S_{t}+\mathbb {P}(x^{\prime },C^{\prime })^{\oplus }\subseteq S$ and hence Proposition 4.17. □

4.2.5 Proof of Theorem 4.6

Let us first consider knapsack. According to Proposition 4.7, it suffices to provide a logspace reduction from the knapsack problem over G to the membership problem for acyclic NFA over G. Suppose we have an instance

$$h_{0}g_{1}^{x_{1}}h_{1}{\cdots} g_{k}^{x_{k}} h_{k}=1 $$

of the knapsack problem over G of size n. Moreover, let h _i be represented by v _i ∈ A ^∗ for each i ∈ [0,k] and let g _i be represented by u _i ∈ A ^∗ for i ∈ [1,k].

By Theorem 4.1, there is a polynomial p such that the above instance has a solution if and only if it has a solution $x\in \mathbb {N}^{k}$ with ∥x∥ _∞ ≤ p(n). We construct an acyclic NFA $\mathcal {A}=(Q,A,{\Delta },q_{0},q_{f})$ as follows. It has the state set Q = [0,k + 1] × [0,p(n)] and the following transitions. From (0,0), there is one transition labeled v ₀ to (1,0). For each i ∈ [1,k] and j ∈ [0,p(n) − 1], there are two transitions from (i,j) to (i,j + 1); one labeled by u _i and one labeled by ε. Furthermore, there is a transition from (i,p(n)) to (i + 1,0) labeled v _i for each i ∈ [1,k]. The initial state is q ₀ = (0,0) and the final state is q _f = (k + 1,0).

It is clear that $\mathcal {A}$ accepts a word that represents 1 if and only if the exponent equation has a solution. Finally, the reduction can clearly be carried out in logarithmic space.

For subset sum the same reduction as above works but the polynomial bound on solutions is for free.

4.3 LogCFL-completeness

In this section we complement Theorem 4.6 with a lower bound.

Theorem 4.25

If (A,I)is a transitive forest and not a complete graph, then knapsack and subset sum for $\mathbb {G}(A,I)$ are LogCFL-complete.

By Theorem 4.6 it suffices to show that knapsack and subset sum for $\mathbb {G}(A,I)$ are LogCFL-hard if (A,I) is not a complete graph. If (A,I) is not complete, then (A,I) contains two non-adjacent vertices and thus $\mathbb {G}(A,I)$ contains an isomorphic copy of F ₂, the free group of rank two. Hence, we will show that knapsack and subset sum for F ₂ are LogCFL-hard:

Proposition 4.26

For F ₂, knapsack and subset sum are LogCFL-hard.

Let {a,b} be a generating set for F ₂. Let 𝜃: {a,b,a ⁻¹,b ⁻¹}^∗→ F ₂ be the morphism that maps a word w to the group element represented by w.

A valence automaton over a group G is a tuple $\mathcal {A}=(Q,{\Sigma },{\Delta },q_{0},q_{f})$ where Q, Σ, q ₀, q _f are as in a finite automaton and Δ is a finite subset of Q ×Σ^∗× G × Q. The language accepted by $\mathcal {A}$ is denoted $L(\mathcal {A})$ and consists of all words w ₁⋯w _n such that there is a computation

such that (p _i−1,w _i ,g _i ,p _i ) ∈ Δ for i ∈ [1,n], p ₀ = q ₀, p _n = q _f , and g ₁⋯g _n = 1 in G. We call this computation also an accepting run of $\mathcal {A}$ for w (of length n). Note that we allow ε-transitions of the form (p,ε,g,q) ∈ Δ. This implies that an accepting run for a word w can be of length greater than |w|.

An analysis of a proof (in this case [30]) of the Chomsky-Schützenberger theorem yields:

Lemma 4.27

For every language L ⊆Σ^∗ the following statements are equivalent:

• (i) L is context-free.

• (ii) There is a valence automaton $\mathcal {A}$ over F ₂ such that $L = L(\mathcal {A})$ .

• (iii) There is a valence automaton $\mathcal {A}$ over F ₂ and a constant $c \in \mathbb {N}$ such that $L = L(\mathcal {A})$ and for every w ∈ L there exists an accepting run of $\mathcal {A}$ for w of length at most c ⋅|w|.

Proof

The equivalence of (i) and (ii) is well known (see [30]) and the implication from (iii) to (ii) is trivial. We show that (i) implies (iii). For this, we shall use the concept of rational transductions. If Σ and Γ are alphabets, subsets T ⊆Γ^∗×Σ^∗ are called transductions. Given a language L ⊆Σ^∗ and a transduction T ⊆Γ^∗×Σ^∗, we define

$$TL=\{u\in {\Gamma}^{*} \mid \text{\((u,v)\in T\) for some \(v\in L\)} \}. $$

A finite-state transducer is a tuple $\mathcal {A}=(Q,{\Sigma },{\Gamma },{\Delta },q_{0},q_{f})$, where Q is a finite set of states, Σ is its input alphabet, Γ is its output alphabet, Δ is a finite subset of Q ×Γ^∗×Σ^∗× Q, q ₀ ∈ Q is its initial state, and q _f ∈ Q is its final state. The elements of Δ are called transitions. We say that a pair (u,v) ∈Γ^∗×Σ^∗ is accepted by $\mathcal {A}$ if there is a sequence

$$(p_{0},u_{1},v_{1},p_{1}),(p_{1},u_{2},v_{2},p_{2}),\ldots,(p_{n-1},u_{n},v_{n},p_{n}) $$

of transitions where n ≥ 1, p ₀ = q ₀, p _n = q _f , u = u ₁⋯u _n , and v = v ₁⋯v _n . The set of all pairs (u,v) ∈Γ^∗×Σ^∗ that are accepted by $\mathcal {A}$ is denoted by $T(\mathcal {A})$. A transduction T ⊆Γ^∗×Σ^∗ is called rational if there is a finite-state transducer $\mathcal {A}$ with $T(\mathcal {A})=T$.

Let W ₂ ⊆{a,b,a ⁻¹,b ⁻¹}^∗ be the word problem of F ₂, i.e.

$$W_{2}=\{w\in \{a,b,a^{-1},b^{-1}\}^{*} \mid \theta(w)=1\}. $$

For languages K ⊆Γ^∗ and L ⊆Σ^∗, we write K ⇝ L if there is a rational transduction T ⊆Γ^∗×Σ^∗ and a constant c such that K = T L and for each u ∈ K, there is a v ∈ L with |v|≤ c|u| and (u,v) ∈ T. Observe that the relation ⇝ is transitive, meaning that it suffices to show L ⇝ W ₂ for every context-free language L.

Let D ₂ be the one-sided Dyck language over two pairs of parentheses, in other words: D ₂ is the smallest language $D_{2}\subseteq \{x,\bar {x},y,\bar {y}\}^{*}$ such that ε ∈ D ₂ and whenever u v ∈ D ₂, we also have u w v ∈ D ₂ for $w\in \{x\bar {x}, y\bar {y}\}$.

It is easy to see that L ⇝ D ₂ for every context-free language L. Indeed, an ε-free pushdown automaton (which exists for every context-free language [22]) for L can be converted into a transducer witnessing L ⇝ D ₂. Therefore, it remains to show that D ₂ ⇝ W ₂.

Let F ₃ be the free group of rank 3 and let {a,b,#} be a free generating set for F ₃. As above, let

$$W_{3}=\{w\in \{a,b,\#,a^{-1},b^{-1},\#^{-1}\}^{*} \mid \text{\textit{w} represents 1 in \(F_{3}\)}\} $$

be the word problem of F ₃. Since F ₃ can be embedded into F ₂ [41](@var1@Proposition 3.1@var1@), we clearly have W ₃ ⇝ W ₂. It therefore suffices to show D ₂ ⇝ W ₃.

For this, we use a construction of Kambites [30]. He proves that if $\mathcal {A}$ is the transducer in Fig. 2 and $T=T(\mathcal {A})$, then D ₂ = T W ₃. Thus, for every u ∈ D ₂, we have (u,v) ∈ T for some v ∈ W ₃. An inspection of $\mathcal {A}$ yields that $|v|=2|u|+|v|_{\#^{-1}}$ and |v| _# = |u|. Since v ∈ W ₃, we have $|v|_{\#^{-1}}=|v|_{\#}$ and thus |v| = 3|u|. Hence, the transduction T witnesses D ₂ ⇝ W ₃. We have thus shown L ⇝ D ₂ ⇝ W ₃ ⇝ W ₂ and hence the lemma. □

Fig. 2

Transducer used in the proof of Lemma 4.27

Given w, it is easy to convert the valence automaton $\mathcal {A}$ from Lemma 4.27 into an acyclic automaton that exhausts all computations of $\mathcal {A}$ of length c ⋅|w|. This yields the following.

Proposition 4.28

For F ₂ , the membership problem for acyclic NFA is LogCFL -hard.

Proof

Fix a context-free language L ⊆Σ^∗ with a LogCFL-complete membership problem; such languages exist [21]. Fix a valence automaton $\mathcal {A}=(Q,{\Sigma },{\Delta },q_{0},q_{f})$ over F ₂ and a constant $c \in \mathbb {N}$ such that the statement of Lemma 4.27(iii) holds for L, $\mathcal {A}$, and c. Consider a word w ∈Σ^∗. From w we construct an acyclic automaton $\mathcal {B}$ over the input alphabet {a,b,a ⁻¹,b ⁻¹} such that $1 \in \theta (L(\mathcal {B}))$ if and only if w ∈ L. Let m = |w|, w = a ₁ a ₂⋯a _m and n = c ⋅ m. The set of states of $\mathcal {B}$ is [0,m] × [0,n] × Q. The transitions of $\mathcal {B}$ are defined as follows:

• ∈ Δ for all i ∈ [1,m], j ∈ [1,n], and x ∈{a,b,a ⁻¹,b ⁻¹}^∗

• ∈ Δ for all i ∈ [0,m], j ∈ [1,n], and x ∈{a,b,a ⁻¹,b ⁻¹}^∗

The initial state of $\mathcal {B}$ is (0,0,q ₀) and all states (m,j,q _f ) with j ∈ [0,n] are final in $\mathcal {B}$. It is then straightforward to show that $1 \in \theta (L(\mathcal {B}))$ if and only if w ∈ L. The intuitive idea is that in a state of $\mathcal {B}$ we store in the first component the current position in the word w. In this way we enforce the simulation of a run of $\mathcal {A}$ on input w. In the second component of the state we store the total number of simulated $\mathcal {A}$-transitions. In this way we make $\mathcal {B}$ acyclic. Finally, the third state component of $\mathcal {B}$ stores the current $\mathcal {A}$-state. □

Proof

of Proposition 4.26. Let $\mathcal {A} = (Q,\{a,b,a^{-1},b^{-1}\}, {\Delta }, q_{0}, q_{f})$ be an acyclic automaton. We construct words w,w ₁,…,w _m ∈{a,b,a ⁻¹,b ⁻¹} such that the following three statements are equivalent:

• (i) $1 \in \theta (L(\mathcal {A}))$.

• (ii) $\theta (w) \in \theta (w_{1}^{*} w_{2}^{*} {\cdots } w_{m}^{*})$.

• (iii) $\theta (w) \in \theta (w_{1}^{e_{1}} w_{2}^{e_{2}} {\cdots } w_{m}^{e_{m}})$ for some e ₁,e ₂,…,e _m ∈{0,1}.

W.l.o.g. assume that Q = {1,…,n}, where 1 is the initial state and n is the unique final state of $\mathcal {A}$.

Let α _i = a ⁱ b a ⁻ⁱ for i ∈ [1,n + 2]. It is well known that the α _i generate a free subgroup of rank n + 2 in F ₂ [41](@var1@Proposition 3.1@var1@). Define the embedding φ: F ₂ → F ₂ by φ(a) = α _n+1 and φ(b) = α _n+2. For a transition t = (p,w,q) ∈ Δ let $\tilde {t} = \alpha _{p} \varphi (w) \alpha _{q}^{-1}$. Let Δ = {t ₁,…,t _m } such that t _i = (p,a,q) and t _j = (q,b,r) implies i < j. Since $\mathcal {A}$ is acyclic, such an enumeration must exist. Together with the fact that the α _i generate a free group, it follows that the following three statements are equivalent:

• (i) $1 \in \theta (L(\mathcal {A}))$.

• (ii) $\theta (\alpha _{1} \alpha _{n}^{-1}) \in \theta (\tilde {t}_{1}^{*} \, \tilde {t}_{2}^{*} {\cdots } \tilde {t}_{m}^{*})$.

• (iii) $\theta (\alpha _{1} \alpha _{n}^{-1}) \in \theta (\tilde {t}_{1}^{e_{1}} \,\tilde {t}_{2}^{e_{2}} {\cdots } \tilde {t}_{m}^{e_{m}})$ for some e ₁,e ₂,…,e _m ∈{0,1}.

This shows the proposition. □

4.4 T C ⁰-completeness

We finally show that subset sum and knapsack for free abelian groups $\mathbb {Z}^{m}$ are complete for the circuit complexity class T C ⁰. Note that $\mathbb {Z}^{m}$ is isomorphic to the graph group $\mathbb {G}(A,I)$ where (A,I) is the complete graph on m nodes. The proof of the following result is a simple combination of known results from [17, 46].

Theorem 4.29

For every fixed m ≥ 1, knapsack and subset sum for the free abelian group $\mathbb {Z}^{m}$ are complete for T C ⁰ . Hence, knapsack and subset sum for $\mathbb {G}(A,I)$ are complete for T C ⁰ if (A,I)is a non-empty complete graph.

Proof

Hardness for T C ⁰ follows from the well-known fact that the word problem for $\mathbb {Z}$ is T C ⁰-complete: The word problem for $\mathbb {Z}$ is exactly the membership problem for the language Eq = {w ∈{a,b}^∗∣|w| _a = |w| _b } (take b = a ⁻¹). The canonical T C ⁰-complete language is Maj = {w ∈{a,b}^∗∣|w| _a ≥|w| _b } [50], which is equivalent (with respect to A C ⁰-Turing reductions) to Eq: (i) w ∈Eq if and only if w ∈Maj and w ^′∈Maj, where w ^′ is obtained by swapping the letters a and b in w, and (ii) w ∈Maj if and only if $\bigwedge _{i=0}^{|w|} wb^{i} \in \text {Eq}$.

Let us now show that knapsack for $\mathbb {Z}^{m}$ belongs to T C ⁰. Let A = {a ₁,…,a _m } be the generating set for $\mathbb {Z}^{m}$. Given a word w ∈ (A ∪ A ⁻¹)^∗ we can compute the vector $(b_{1}, \ldots , b_{m}) \in \mathbb {Z}^{m}$ with $b_{i} := |w|_{a_{i}} - |w|_{a_{i}^{-1}}$ represented in unary notation in T C ⁰ (counting the number of occurrences of a symbol in a string and subtraction can be done in T C ⁰). Hence, we can transform in T C ⁰ an instance of knapsack for $\mathbb {Z}^{m}$ into a system of equations A x = b, where $A \in \mathbb {Z}^{m \times n}$ is an integer matrix with unary encoded entries, $b \in \mathbb {Z}^{m}$ is an integer vector with unary encoded entries, and x is a vector of n variables ranging over $\mathbb {N}$. Let t = n(m a)^2m+1, where a is the maximal absolute value of an entry in (A∣b). By [46] the system A x = b has a solution if and only if it has a solution with all entries of x from the interval [0,t]. Since m is a constant, the unary encoding of the number t can be computed in T C ⁰ (iterated multiplication can be done in T C ⁰). However, the question whether the system A x = b has a solution from [0,t]ⁿ is an instance of the m-integer-linear-programming problem from [17], which was shown to be in T C ⁰ in [17]. For subset sum for $\mathbb {Z}^{m}$ one can use the same argument with t = 1. □

5 Open Problems

The following two open problems were mentioned earlier:

• Is the subset sum problem for the graph group $\mathbb {G}(\mathsf {P4}) \mathsf {NP}$-hard? The problem belongs to N P.

• Is the class of polynomially bounded knapsack groups (i.e. those where every solvable knapsack instance has a solution where all components are bounded polynomially in the size of the knapsack instance) closed under direct products with $\mathbb {Z}$? See the remarks at the beginning of Section 4.2.2.

An important class of groups with open decidability status of the knapsack problem is that of braid groups.

In [33], it is shown that knapsack is decidable for every co-context-free group. A group is co-context-free if the set of all words that do not represent the group identity is a context-free language. The algorithm from [33] has an exponential running time and it is open whether for every co-context-free group the knapsack problem belongs to N P.