Hardness for \(\mathsf {TC}^0\)  follows from the fact that the word problem for
\(\mathbb {Z}\)  is \(\mathsf {TC}^0\) -complete: this is exactly the problem of checking
whether for a given word \(w \in \lbrace 0,1\rbrace ^*\) , \(|w|_0 = |w|_1\)  holds.
Let us now show that knapsack for \(\mathbb {Z}^m\)  belongs to
\(\mathsf {TC}^0\) . Let \(A = \lbrace a_1,\ldots , a_m\rbrace \)  be the generating set for
\(\mathbb {Z}^m\) . Given a word \(w \in (A \cup A^{-1})^*\)  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 \(\mathsf {TC}^0\)  (counting the number
of occurrences of a symbol in a string and subtraction can be done in
\(\mathsf {TC}^0\) ). Hence, we can transform in \(\mathsf {TC}^0\)  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 (ma)^{2m+1}\) ,
where \(a\)  is the maximal absolute value of an entry in \((A\mid b)\) . By
[1]} the system \(Ax=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 \(\mathsf {TC}^0\) 
(iterated multiplication can be done in \(\mathsf {TC}^0\) ). However, the question whether
the system \(Ax=b\)  has a solution from \([0, t]^n\)  is an instance of the
\(m\) -integer-linear-programming problem from [2]}, which was
shown to be in \(\mathsf {TC}^0\)  in [2]}. For subset sum
for \(\mathbb {Z}^m\)  one can use the same argument with \(t=1\) .
