How to complete the NP-hardness proof of GENERAL-SQUARE-PRODUCT? I am interested in the complexity of the following problem:
GENERAL-SQUARE-PRODUCT
INSTANCE: Two sets $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_n\}$ of integers, a positive integer $k<n$ and a positive integer $\Delta$. 
QUESTION: Is there a subset $S$ of $\{1,\ldots,n\}$ of size $|S|\leq k$ such that
$$\left(1+\left(\sum_{i\in S}a_i\right)^2\right)\left(1+\left(\sum_{i\in S}b_i\right)^2\right)\geq\Delta ?$$
Note: $\Delta$ is greater than $1$.
My question is:


*

*Is this problem NP-hard?


I have proved that the restricted version PRODUCT is NP-hard. (The restricted version consists of non-negative integers and without the squares.)

Attempt to prove:
Here is my proof which I think incomplete. Can you help me complete it?
I will reduce EQUAL-PARTITION to GENERAL-SQUARE-PRODUCT.
Given an instance $\{x_1,\ldots,x_n\}$ of EQUAL-PARTITION (with $x_i > 0$ and $n$ is even), consider an instance of my problem with $k = n/2$, $\Delta=\left(1+\left(A/2\right)^2\right)^2$ and $A=\sum_{i}x_i$ , and let $a_i=x_i$ for all $i$ and $b_i=2A/n-x_i$ for all $i$. 
This is a polynomial time reduction.
Now let us prove that EQUAL-PARTITION is solved $\iff$ GENERAL-SQUARE-PRODUCT is solved.


*

*"$\Rightarrow$" Suppose that EQUAL-PARTITION is solved. Then there exists $S$ of size $|S|=n/2$ such that 
$$
\sum_{i\in S}x_i=\sum_{i\in S'}x_i=A/2,
$$
where $S\cup S'=\{1,\ldots,n\}$ and $S\cap S'=\emptyset$ and $|S|=|S'|=n/2$.
Now take the solution to GENERAL-SQUARE-PRODUCT to be $S$. We have 
\begin{align}
&\left(1+\left(\sum_{i\in S}a_i\right)^2\right)\left(1+\left(\sum_{i\in S}b_i\right)^2\right)\geq\Delta\\
\Rightarrow&\left(1+\left(\sum_{i\in S}x_i\right)^2\right)\left(1+\left(\sum_{i\in S}(2A/n-x_i)\right)^2\right)\geq\Delta\\
\Rightarrow&\left(1+\left(\sum_{i\in S}x_i\right)^2\right)\left(1+\left(A-\sum_{i\in S}x_i\right)^2\right)\geq\Delta\\
\Rightarrow&\left(1+\left(A/2\right)^2\right)\left(1+\left(A/2\right)^2\right)=\left(1+\left(A/2\right)^2\right)^2\\
\end{align}

*"$\Leftarrow$" Suppose that GENERAL-SQUARE-PRODUCT is solved. Then there exists $S$ of size $|S|=n/2$ such that
\begin{align}
\require{overset}
&\left(1+\left(\sum_{i\in S}a_i\right)^2\right)\left(1+\left(\sum_{i\in S}b_i\right)^2\right)\geq\Delta\\
\Rightarrow&\left(1+\left(\sum_{i\in S}x_i\right)^2\right)\left(1+\left(\sum_{i\in S}(2A/n-x_i)\right)^2\right)\geq\Delta\\
\overset{(a)}{\Rightarrow}&\left(1+\sum_{i\in S}x_i\right)\left(1+\sum_{i\in S}(2A/n-x_i)\right)\geq\sqrt{\Delta}\\
\Rightarrow&\left(1+\sum_{i\in S}x_i\right)\left(1+A-\sum_{i\in S}x_i\right)\geq\sqrt{\Delta}\\
\Rightarrow&1+ A+A\sum_{i\in S}x_i-\left(\sum_{i\in S}x_i\right)^2\geq\sqrt{\Delta}\\
\Rightarrow&\left(\sum_{i\in S}x_i\right)^2-A\sum_{i\in S}x_i+\sqrt{\Delta}-1- A\leq 0\\
\Rightarrow&X^2-AX+\sqrt{\Delta}-1- A\leq 0\\
\Rightarrow&A/2-\sqrt{A}\leq X\leq A/2+\sqrt{A}\\ 
\Rightarrow&\left|\sum_{i\in S}x_i-\sum_{i\in S'}x_i\right|\leq\sqrt{A}\\
\end{align}


Finally, can I say that GENERAL-SQUARE-PRODUCT is NP-hard? If not, how to fix this?
where $(a)$ is due to the fact that for all $X>0$, $\left(1+X\right)^2\geq\left(1+X^2\right)$.
Note:
I asked a restricted version of GENERAL-SQUARE-PRODUCT here where $a_i$ and $b_i$ are non-negative but I get no answers.
 A: Yes, your problem is NP-hard. The proof is by reduction from Subset Sum. Given the Subset Sum problem "does set $S$ have a subset with less than $k$ members summing to $d$?", create an instance of your problem with $A=S$, $B=$"all zeros", $\Delta=1-d^2$, $k=k$. Then the solution to your problem with that $(k,A,B,\Delta)$ will also be the solution to that Subset Sum problem. Subset Sum is NP-complete, therefore your problem is NP-hard.
If you want to go further and prove your problem is NP-complete, simply notice that it must be NP because it's easy to check an answer. Therefore it's NP-complete.
A: What do you mean by $\Delta$ "not too big"?  If there are at least   $ \sqrt{\Delta}$ positive $a_i$ or at least $\sqrt{\Delta}$ negative $a_i$, the answer is yes.  Otherwise, there are at most $2^{2 \sqrt{\Delta}}$ possibilities for  $S \cap \{i: a_i \ne 0\}$ to consider, and each of 
these cases is easy.  So if "not too big" means $\Delta \le k \log(n)^2$ for some $k$, there is a polynomial-time algorithm.
