Is there an efficient algorithm to find the maximum of a sum of $m$ sines?
That is, find an $x \in \mathbb{R}$ such that $$f(x) = \sum_{k=1}^m \sin(\alpha_kx)$$ is maximized? By efficient, we mean an $O(m)$ algorithm. Also, $\alpha_k$ is rational for all $k$.
Note: This is not homework.
Take $m=2$ and suppose $\alpha_2/\alpha_1$ is irrational. Then $f(x) = \sin(\alpha_1 x) + \sin(\alpha_2 x)$ comes arbitrarily close to $2$, but never reaches it. Therefore the maximum does not exist.
More generally, if the $\alpha_k$ are linearly independent over the rationals, the orbits of the corresponding linear flow on the $m$-torus are dense, and so we get values arbitrarily close to $m$, but no values of $m$.
Or did you mean $x$ to be restricted to a bounded interval rather than all of $\mathbb R$?
EDIT: Suppose all $\alpha_k$ are rational. Scaling by a common denominator, we may as well assume $\alpha_k$ are integers. $\cos(\alpha x) = T_\alpha(\cos(x))$ is a polynomial in $\cos(x)$ (the $\alpha$'th Chebyshev polynomial of the first kind), and $\sin(\alpha x) = \sin(x) U_{\alpha-1}(\cos(x))$ where $U_\alpha$ is the $\alpha$'th Chebyshev polynomial of the second kind. By solving the appropriate polynomial we can find the critical points and critical values of $f$. However, I don't see how you can hope to do this in time $O(m)$ independent of the $\alpha$'s.
EDIT: If you restrict $\alpha_k$ to be in $\{0,1,2,\ldots,N\}$ where $N$ is fixed, rewrite $f(x) = \sum_{j=0}^N c_j \sin(j x)$ where $c_j$ are nonnegative integers and $\sum_j c_j = m$. Then we can write $f(x) = s Q(t)$ and $f'(x) = P(t)$ where $t = \cos(x)$, $s = \sin(x)$, and $P$ and $Q$ are polynomials of degree at most $N$ and $N-1$ respectively with coefficients $O(m)$.
The resultant of $sQ(t) - y$ and $s^2 + t^2 - 1$ with respect to $s$ is $Q(t)^2 (t^2 - 1) + y^2$ (a polynomial of degree at most $2(N-1)$ in $t$). Let $G(y)$ be the resultant of this and $P(t)$ with respect to $t$. This is a polynomial in $y$ of bounded degree and with coefficients bounded by a polynomial in $m$, and the critical values of $f$ are roots of $G(y)$.
To find the critical values with a given accuracy $\epsilon$, it should suffice to give $G(y)$ to a global root-counting algorithm (e.g. using Sturm's theorem) using arithmetic with $O(\log m)$ digits. So the time required should be only $O(\log m)$ (but that hides a very strong dependence on $N$).