Product of complex numbers on the unit circle with largest real part Let $T = \{z_1, \ldots z_n\}$ be a finite set of complex numbers on the unit circle. I would like an algorithm which can quickly compute the nonempty subset $S \subset T$ which maximizes $$\left| \operatorname{Re}\left(\prod_{z \in S} z\right) \right|.$$ I suspect this problem may be NP-Hard, but I'm not sure. I'm fine with an algorithm which computes an approximately maximal product.
 A: If you write $z = \exp(2\pi i\theta_z)$ for arguments $\theta_z\in [0,1)$, then as
$$\Re(\prod_{z\in S}z) = \Re(\exp(2\pi \sum_{z\in S}\theta_z)) = \cos(2\pi\sum_{z\in S}\theta_z).$$
the problem is equivalent to finding $S$ such that $\sum_{z\in S}\theta_z\bmod 1$ is closest to either of $0$ (when the absolute value is positive) or $1/2$ (when it is negative).
If one assumes that all $\theta_z$ are rational, and moreover that for $N\in\mathbb{N}$ they are all of the form $\theta_z = a_z / n$ for $a_z\in[0,1,\dots,n-1]$, one can rewrite this as finding $S$ such that
$\sum_{z\in S}a_z \bmod n$ is closest to $0$ or $n/2$.
This seems to be a modular version of the 0-1 knapsack (optimization) problem. This is a simultaneous generalization of the standard 0-1 knapsack problem in 2 ways

*

*there is a modular constraint --- the objective function is $\sum_{z\in S}a_z \bmod n$ rather than $\sum_{z\in S}a_z$, and

*it is an optimization problem rather than a decision problem.

If you only had one of these generalizations, casual searching would lead to known results. For example, if you knew that $\sum_{z\in S}a_z\bmod n = 0$ (or $n/2$) exactly, then there is a standard reduction to lattice problems, which is even efficient if the instance is "sparse" in a certain sense.
I expect one can similarly attack this problem by reducing it to SVP/CVP on a suitable lattice. As a brief sketch, if one defines the matrix
$$B =\begin{pmatrix}
N &0&0 &\dots & 0\\
a_{z_1} & 1 & 0 & &0\\
a_{z_2} & 0 & 1 & \dots &0\\
\vdots &&&\ddots&\vdots\\
a_{z_k} & 0 & 0 & \dots & 1 
\end{pmatrix},$$
Then one can check that any (integer) linear combination of the rows of the above takes the form
$$
\begin{pmatrix}
Nx_0 + a_{z_1}x_1 + \dots + a_{z_k}x_k\\
x_1\\
\vdots\\
x_k
\end{pmatrix}
$$
where $\vec x = (x_0,\dots, x_k)\in\mathbb{Z}^{k+1}$.
Clearly, the norm of this is minimized for $\vec x = 0$.
One can argue that the shortest non-zero vector will lead to $Nx_0 + \sum_i a_{z_i}x_i$ being small.
There is still of course work to do (for example, the shortest vector in the aforementioned lattice may lead to a "solution" to a knapsack problem without 0/1 weights. This could plausibly be fixed by using a lattice basis with $M$ on the diagonal instead of $1$, to penalize choosing $x_1,\dots, x_k > 1$).
Still, I expect a solution to your problem will proceed in a route similar to this, as this is fairly typical for "modular knapsack" problems.
A: This is NP-hard, because the subset sum problem with target number zero is reducible to it.
Suppose we want to find a nonempty subset of an integer subset $\{x_1,\cdots,x_n\}$ that sums up to zero.
Then we can let $z_k=\exp(2\pi i (x_k/a))$ where $a=|x_1|+\cdots+|x_n|+1$. There is a choice of $z_k$s that achieves the maximum value $1$ iff the corresponding nonempty subset sums up to $0$.
