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\}$.

  • 3
    $\begingroup$ Take the convolution $1_{a_1}*(1_{a_2}+1_{-a_2})*\cdots*(1_{a_n}+1_{-a_n})$. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.