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.