# 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.

• I suppose the subset $S$ should be nonempty. Feb 24 at 8:33
• If you look for an approximation, do you need something that works well for small $n$ (say smaller than 10) or rather something that works well for larger n, say $n=100$, and in the latter case, are your $z_i$ approximately uniformly random or follow some other known distribution? Feb 24 at 17:44

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

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

1. 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
2. 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.