# valuation from $\mathbb{Z}^n$ into $\mathbb{Z}$. Easy way?

Let $\mathcal{F}:=\{f_a\}_{a\in\mathbb{Z}}$ be a set of symbols indexed by the integers and satisfying the rules: $$f_a=f_{-a} \qquad \text{and} \qquad f_af_b=f_{a+b}+f_{a-b}.$$ Define a linear operator $\mathcal{L}$ on $\mathcal{F}$ according to $$\mathcal{L}f_a=\begin{cases} 1 \qquad \text{if a=0} \\ 0 \qquad \text{otherwise}. \end{cases}$$

Question 1. If $a_i\in\mathbb{Z}$, then is there a nice formula or an efficient algorithm to compute $$\mathcal{L}(f_{a_1}f_{a_2}\cdots f_{a_k}) \,\,?$$

For example, $\mathcal{L}f_af_b=\mathcal{L}f_{a+b}+\mathcal{L}f_{a-b}$.

Question 2. Fix $k\geq1$. What is the range of values for $\mathcal{L}(f_{a_1}f_{a_2}\cdots f_{a_k})$ if $(a_1,\dots,a_k)\in\mathbb{Z}^k$ runs through all possible $k$-tuples?

For example, when $k=1$ the answer is $\{0,1\}$; when $k=2$ the answer is $\{0,1,2,4\}$.

• Take the convolution $1_{a_1}*(1_{a_2}+1_{-a_2})*\cdots*(1_{a_n}+1_{-a_n})$. – Fan Zheng Feb 21 '17 at 1:37

Suppose we have a knapsack of size $K = 10$, and items of size $x_1=4; x_2 = 5; x_3 = 6$. Clearly there is an exact solution to the decision version of the 0/1 knapsack problem: $K - x_1 - x_3 = 0$. If we set $A = 2K - x_1 - x_2 - x_3$, this solution gives us $A - x_1 + x_2 - x_3 = 0$.
If $K$ is the size of a knapsack and $x_i$ is the weight of the $i$th item, then set $a_1 = 2K - \sum_{i} x_i$ and $a_i = x_{i-1}$. If you can determine if the expression $a_1 \pm a_2 \pm a_3 \pm \ldots$ is ever 0 you can solve the knapsack problem. Therefore I expect there is no efficient solution.