Number of unique terms in the nth power of a sum of sinusoids We have a sum of sinusoids of different frequencies
$$S = \sum_{i = 1}^n\cos(\omega_i t);, \qquad \omega_q \neq \omega_w$$
and take an integer power $p$ of $S$. This will also be a sum of sinusoids, but what is the highest possible number of unique terms $m$ in this sum?
$$\sum_{k = 1}^m a_k\cos(\Omega_k t) = S^p\;, \qquad \Omega_q \neq \Omega_w$$
As a low order illustration, say $n = 1$ and $p = 3$, we get
\begin{align}\cos^3{\omega t} &= \left(\frac{1}{2}(e^{-j\omega t} + e^{j\omega t})\right)^3 = \\&= \frac{1}{8}e^{-3j\omega t} + \frac{3}{8}e^{-j\omega t} + \frac{3}{8}e^{j\omega t} + \frac{1}{8}e^{3j\omega t} = \\&= \frac{1}{4}\cos(3\omega t) + \frac{3}{4}\cos(\omega t)\end{align}
as is well-known. For this case $m = 2$. 
I have made some progress with one way of solving it, but other methods might of course also be possible. Here goes what I have so far:
By decomposing each sinusoid as $\frac{1}{2}(e^{-j\omega} + e^{j\omega})$, $S$ has $2n$ components. And as familiar from (multi)binomial expansion, $S^p$ will comprise a lot of terms, each term being a unique way to choose $p$ terms from $S$. The order of the choice does not affect the number of unique components, so from this we could expect ${2n}\choose{p}$ components. Ther is however a problem with this: many of these components will be the same too, because any choice using both the positive and negative power of the same frequency, will cancel out like $e^{j\omega_qt}e^{-j\omega_qt} = 1$. Since this holds for any $\omega_i$, there are many unique choices of terms of $S$ that give the same result. 
By this, I would believe that the number of terms in the complex representation of  $S^p$ is the same as the number of unique points that can be reached by walking exactly $p$ blocks in an $n$-dimensional Manhattan. Each walk in one dimension is a representation of multiplication by $e^{-j\omega_i}$ or $e^{j\omega_i}$. And accordingly, multiplying by one of them first, then the other, corresponds to first walking in one direction, then going back in the opposite direction. Exactly $p$ blocks has to be walked. If this reasoning holds, then how can I find this number?
 A: Not an answer but some suggested clarifications...  plus an answer "approach".
I assume you want phases to not matter, in the sense that $\cos(ft + \theta)$ and $\cos(ft + \phi)$ are considered equivalent (in your counting).  This of course also means $\cos$ and $\sin$ are equivalent.
Anyway your approach is essentially using the fact that multiplication in time domain is equivalent to convolution in frequency domain (in Fourier analysis).  It is completely valid and any resulting "final" frequency is of the form $\pm \omega_{t_1} \pm \omega_{t_2} \pm \cdots \pm \omega_{t_p}$ where $\omega_{t_i}$ means the frequency you add or subtract at step $i$.
If these final frequencies are all distinct (up to $\pm$) then your argument works, i.e., the number of them equals the number of reachable points after $p$ steps in an $n$-dimensional Manhattan grid $\mathbb{Z}^n$.  Actually you need to divide by $2$ because of the $\pm$ equivalence.
However, you only assumed that the (pairwise) ratios of frequencies are irrational.  This is actually not enough.  E.g. $\{1, \sqrt{2}, e, (\sqrt{2}+e-1)\}$ have pairwise irrational ratios but you can confuse $+1 + (\sqrt{2}+e-1) = + \sqrt{2} + e$, as if your Manhattan points $(0,1,1,0)$ and $(1,0,0,1)$ are the same points.  This of course causes you to have reduced number of final frequencies.
One stronger assumption that makes your argument work is to assume there is no linear integral-coefficient combination of the frequencies that equal $0$ (unless of course all coefficients are zero).  
There are weaker assumptions if you only need your argument to work for a specific $n$, and there might be weaker assumptions even if you need your argument to work for all $n$.

Re: actually answering your question (of how many such points), If you can count the outermost "shell" reached by $p$ steps (but cannot be reached by $< p$ steps), then just add up every other layer.  Each "facet" of the shell should be countable by stars and bars, posed as "how to reach total Manhattan distance $p$ using $n$ dimensions", I think, and there are $2^n$ facets, but we need to be careful about double counting the "edges" etc.  Sorry the details elude me right now.
A: I believe that I solved the problem. I verified for all combinations $p\leq 3$ and $n\leq 3$, and values where one of them is set to one. 
As suggested, the number is related to the number of possible places one can walk using exactly $p$ steps in a $n$-dimensional Manhattan grid. Or equivalently, the number of points within in a 1-norm hypersphere of radius $p$ in $\mathbb{Z}^p$. Perhaps this is a previously solved problem, but i will post my solution anyway. 
The issue of being able to go backwards can be solved by (1) not allowing going backwards, which means that once one has moved in one direction, it is not possible to go back, (2) summing over all possibilities of initial choices of directions and (3) counting a step backwards as a reduction of $p$ by 2. 
We could start (1) by finding all points by only walking in positive directions. But we cannot simply multiply this by the number of orthants ($2^n$), because the points that do not move in one or more dimensions will be double counted. So we exclude these for now, and only counts points that move in all dimensions at least once, $P$, and multiplies that by the number of dimensions. Then we take all points we can get to by moving possibly in all but one dimension (in which we do not move in), an multiply that with the number of ways we can choose $n-1$-dimensional subspaces, ${n}\choose{n-1}$, and multiply it by the number of orthants in a $n-1$-dimensional space, $2^{n-1}$. And so we can go on until we have covered all one-dimensional subspaces. This is then the number of complex exponential, which should be divide by two to get the number of cosines. An extra 1 has to be added in the case where $p$ is even, because of the constant term. 
The above reasoning is reflected in the follow equation, which is the one that was verified
\begin{align}
m = \frac{\sum_{k = p,p-2,p-4,\ldots,(2\; \text{or}\; 1)}\sum_{i = 1}^n{n\choose i} 2^i P(k,i)}{2} + \mod(p + 1,2)
\end{align}
where 
\begin{align}
P(k,i) = \begin{cases}{{k-1}\choose{i-1}}\;&,\qquad k \geq i\\\\0\;&,\qquad k < i\end{cases}
\end{align}
