A construction related to the cosine problem

Abstract:

We give a constructive proof of the fact that for any sequence of positive integers ${n_1},{n_2}, \ldots ,{n_N}$ there is a subsequence ${m_1}, \ldots ,{m_r}$ for which \[ - \min \limits _x \sum \limits _1^r {\cos {m_j}x \geq CN,} \] where C is a positive constant. Uchiyama previously proved the above inequality with the right-hand side replaced by $C\sqrt N$. We give a polynomial time algorithm for the selection of the subsequence ${m_j}$.