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?

  • $\begingroup$ Why is $\sin(\omega_it)\sin(\omega_kt)$ again a sinusoid? $\endgroup$ – amsmath Mar 26 '19 at 18:40
  • $\begingroup$ $\sin(\omega_i t)\sin(\omega_k t)$ is not a sinusoid, it is a sum of two sinusoids. One sinusouid of $\omega_i + \omega_t$ and one of $\omega_i - \omega_t$. $\endgroup$ – joro Mar 26 '19 at 18:50
  • $\begingroup$ I can see that it's a sum of two (weighted) cosinusoids... $\endgroup$ – amsmath Mar 26 '19 at 18:51
  • $\begingroup$ So, your assumption is actually false. You cannot write $S^p$ in that way. $\endgroup$ – amsmath Mar 26 '19 at 18:57
  • $\begingroup$ I see that i messed up some $\cos$ versus $\sin$ in the original post. Everything should be $\cos$ to make it easier. I will edit. I used the term sinusoid because the phase does not matter. Sorry! :) $\endgroup$ – joro Mar 26 '19 at 18:58

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.

| cite | improve this answer | |
  • $\begingroup$ Thank you! Yes, the phase is irrelevant, so cosines make things much simpler. What I am looking for in the end is to illustrate how the number of frequencies skyrocket as $n,p$ grows. The point is to show that a frequency domain representation is not very useful in this case. For my application (audio signal processing), $n = 10$, $p = 10$ is not a high value. Division by two and rounding up (due to the constant term) is necessary. You are entirely correct in your observation about ratios. What I really seek is the highest value for any set of frequencies. I will edit this. $\endgroup$ – joro Mar 27 '19 at 9:02

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}

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.