Suppose $$N = \sum_{i=1}^{k} \sum_{j=1}^{k} x_i \cdot y_j\cdot F_{c_i}^2 \cdot F_{c_j}^2 ; (x_i, y_j, c_i, c_j \in \mathbb{Z}, c_i, c_j \ge 1) \tag{1}$$ and $F_k$ is the $k$-th Fibonacci number. The Fibonacci numbers $F_{c_i}, F_{c_j}$ in $(1)$ are known constants.
The $x_i \ge 0, y_j \ge 0$ are unknown. We know upper bound constraints: i.e. $x_i \le x_{max}, y_i \le y_{max}$ and the product $x_iy_i \le \pi_{max}$. Also, $F_k^2 \le N$.
This is a Subset sum problem as the pair product of Fibonacci squares forms a finite multiset $S$ and we want to find a subset of $S$ that sums to $N$ with a feasible non-trivial solution to the $2k$ variables $x_1, x_2 \cdots, x_k, y_1, y_2, \cdots y_k$ (subject to some conditions).
A solution is trivial if $\sum_{i=1}^{k} x_i F_{c_i}^2 \in \{1,N\}$.
In the general case, Subset sum is NP-Hard.
Does the fact that the weights are products of Fibonacci squares, permit any clever shortcuts to solve this?
I was thinking if we could apply some modular constraints. For example, isolate a single term i.e.,
$$x_i y_j F_{c_i}^2 F_{c_j}^2 \equiv N \pmod{r} \tag{2}$$
for some $r$.
Taking this approach to its full potential, we could perhaps use a Multivariable Chinese Remainder Theorem (See references) on Eqn. $(1)$ in $k^2$ variables by substituting $Z_t = x_iy_j$ for $t = 1, 2, \cdots k^2$ and then constraining the resulting solution for $Z_t$ with the $0 \le x_i \le x_{max}, 0 \le y_i \le y_{max}$.
$$ Z_t \equiv x_i y_i \pmod{r} \\ \implies \exists s \in \mathbb{Z} \text{ such that } Z_t = x_i y_i + rs \tag{3} $$
Now, Eqn. $(3)$ can be solved using bruteforce for $0 \le y_i \le y_{max}$ using the Euclidean algorithm and retaining solutions $0 \le x_i \le x_{max}$ (or iterate on $x_i$ and solve for $y_i$ depending on whichever range constraint is smaller).
The main obstruction for solving Eqn. $(1)$ using this approach seems to stem from the following theorem:
Theorem. (See Sury's paper referenced below) Let $k$ and $n$ be arbitrary positive integers and suppose $a_{ij}$ are integers (for $1 \le i \le k, 1 \le j \le n$). Suppose $m_1, \cdots , m_k$ are pairwise coprime integers and $b_1, \cdots , b_r$ are arbitrary integers. Then, the $k$ simultaneous congruences $$ a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n \equiv b_1 \pmod{m_1}, \\ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n \equiv b_2 \pmod{m_2}, \\ \cdots \\ a_{k1} x_1 + a_{k2} x_2 + \cdots + a_{kn} x_n \equiv b_k \pmod{m_k} $$
have a solution in integers $x_1, \cdots , x_n$ if and only if, for each $i \le k$, the GCD $m_i$ of $a_{i1}, a_{i2}, \cdots , a_{in}$, divides $b_i$.
Question: Is there a flaw in this approach? Does the fact that we have Fibonacci square weights help us overcome the constraint imposed by the above Theorem for multivariable CRT solutions?
References:
Knill, Oliver. A Multivariable Chinese Remainder Theorem. (2012) arxiv:1206.5114 (preprint)
Sury, B. Multivariable Chinese remainder theorem. Resonance 20, 206–216 (2015). https://doi.org/10.1007/s12045-015-0171-x (Author copy (PDF) available here)