There are a few pieces of background information that help in answering this question:
- Geometric series and in particular geometric series as applying to music
- A geometric series, $x_n$, is one where each successive term is generated by multiplying the previous term by some factor. For example: $x_{n+1} = a x_n$
- Geometric series are everywhere in music, because harmony is all about ratios between different tones (an interval) and the difference in auditory result they produce. Some are consonant, some are dissonant, some sound happy, some sound sad and so on.
- On the keys of a piano, every successive tone results by multiplying the previous tone by a constant factor. What factor is this? Suppose two tones with frequencies $f_1, f_2$ where $f_2=2 f_1$. That would be some tone and the same tone one octave above it. The doubling of the frequency happens in 12 steps (e.g. $C, C \sharp, D, D\sharp, E, F, F\sharp, G, G\sharp, A, A\sharp, B$). This means that $a \cdot a \cdot a \cdot a \cdot a \cdot a \cdot a \cdot a \cdot a \cdot a \cdot a \cdot a = 2$ and therefore $a = \sqrt[12]{2}$ which is approximately $1.0594\ldots$. It's the same story on the fretboard of a stringed instrument. The tones produced by plucking the string in two successive frets have a ratio of $a$.
- So, if we start with an $A=440$ Hz, we know that $A \sharp = a A \approx 466.136$ Hz and 12 steps later $440 \cdot a^{12} =880$ Hz.
- Why is it like this? Because it is a good compromise. Because otherwise, the piano would not have this distinct shape of two black keys, gap, three black keys, gap, two black keys but a different pattern depending on the interval, chosen, to tune it. Which is what you can do with a Sitar because its frets are movable.
Now, assuming a reference tone $A_{r}$, all successive tones are produced by $A_k = a^kA_{r}$ where $k$ is the number of semitones (the smallest difference in frequency between two successive keys on a piano or two successive frets on a guitar).
So, if we were to create a signal that contains a number of successive tones in octave intervals then, assuming that we start somewhere low enough, we would end up with something like 10,20,40,80,160,320,640,1280, 2560, 5120, 10240.
Playing this back, it sounds...sort of nice. "Speeding" this up at twice the speed, we get another signal which now contains tones: 20,40,80,160,320,640,1280, 2560, 5120, 10240, 20480.
Which is (almost) exactly the same as the one we started with. Of course, if we keep "pitch shifting", all we are achieving is pushing more and more tones past the limits of human hearing or within the region of suppression of the anti-imaging filter. In both cases, after a large number of shifts, the difference is audible because the signal does not contain as many harmonics.
These are called Sheppard Tones and they sound like this.
In fact, Sheppard did specify that if you keep "feeding" the pitch shifting with low tones, then the perception is that the tones keep rising in pitch.
This is where DSP might step in and actually use the "aliasing". All that we have to do is remove the anti-imaging filter and make sure that we choose our $A_{r}$ in such a way that when the highest harmonic possible (given an $F_s$) is pitch shifted, it "folds" around the spectrum and ends up becoming $A_{r}$ again.
In such a "degenerate" case, we could keep pitch shifting the same number of harmonics again and again and again without the need to be "feeding" the shifter with "new" low frequencies.
For this to happen, given some $F_s$, we seek that geometric series which includes both $A_r, (F_s - A_r)$ and of course $\log_2\left(\frac{Fs-A_r}{A_r}\right) \in \mathbb{Z}$ and as large as possible.
This covers waveforms that do not "change" when pitch shifted by some even factor.
Pitch shifting and having the pitch go downwards is based on the same principle but is a bit more complex.
This can be done by that detuning mentioned by Hilmar in his response. The actual example that I had in mind when setting this dsp-puzzle, was that of the Weierstrass function.
The Weierstrass function is:
$$ f(t) = \sum_{k=1}^{\infty} a^k \cos(b^k \pi t)$$
Note here that the function is nothing more than a sum of cosines with an exponential amplitude profile. So, relatively low bass but lots of detail.
Things get out of hand with this function when $ab>1+\frac{3 \pi}{2}$ and $a \in \mathbb{R}, b \in \{2l: l \in \mathbb{Z}\}$ (i.e. b is odd).
In that region, the function is continuous but not differentiable. Nowhere.
The informal way to understand why (or rather, the one that works for me (?)) is to consider $g(t)=t^2$ and try to find its derivative in two successive $t, t+\Delta t$, points. The derivative would be $\lim_{\Delta t \to 0} \frac{g(t + \Delta t) - g(t)}{\Delta t}$. Now, on $g$, that is not going to be a problem, because the more the limit "zooms in" (by successively reducing the $\Delta t$), the more the function tends to become like a line. After all, all we are doing is raising a number to a power. But, the more we are zooming in on the Weierstrass function ($f(t)$), the more detail it reveals and that derivative never settles to a value. Never!. Check this out:
(Visualisation from this link)
And here is what happens, when you try to listen to that $f(t)$ at a different speed. Similarly to what happened with the Shepard tones:
What if we were to speed up $f(t)$ by a factor of $b$? Then:
$$ f(b t) = \sum_{k=1}^{\infty} a^k \cos(b b^k \pi t) \implies \sum_{k=1}^{\infty} a^k \cos(b^{k+1} \pi t)$$
And if we were to ignore the amplitude profile ($a^k$) and make the sum finite to some $K$, then:
$$ f(b t) = \sum_{k=2}^{K+1} \cos(b^k \pi t)$$
Notice here how, $k+1$ was "absorbed" to show the similarity with the unshifted version.
So, pitch shifting by $b$ seems to be leaving us more or less with the same function. Now, set $b = 2^{\frac{13}{12}}$ and pitch shift by two:
$$f_{before}(t) = \sum_{k=1}^{K} \cos(2^{\frac{13}{12} k} \pi t)$$
$$\begin{matrix} f_{after}(2 t) = & \sum_{k=1}^{K} \cos(2 \cdot 2^{\frac{13}{12} k} \pi t) \implies \\ & \sum_{k=1}^{K} \cos(2^{\frac{12}{12}} \cdot 2^{\frac{13}{12} k} \pi t) \implies \\ & \sum_{k=1}^{K} \cos(2^{\frac{13}{12}-\frac{1}{12}} \cdot 2^{\frac{13}{12} k} \pi t) \implies \\ & \sum_{k=1}^{K} \cos(2^{(\frac{13}{12}-\frac{1}{12}) + \frac{13}{12} k} \pi t) \implies \\ & \sum_{k=1}^{K} \cos(2^{(k+1)\frac{13}{12}-\frac{1}{12}} \pi t) \implies \\ & \sum_{k=2}^{K+1} \cos(2^{k\frac{13}{12}-\frac{1}{12}} \pi t) \implies \\ & \sum_{k=2}^{K+1} \cos(2^{k\frac{13}{12}} 2^{-\frac{1}{12}} \pi t) \end{matrix}$$
So, the only difference between $f_{before}, f_{after}$ is that $2^{-\frac{1}{12}}$. That is, pitch shifting by two, introduces a "lower by 1 semitone" factor.
It gets freakier than this, for $b=2^{\frac{14}{12}}$ the lowering is a full tone and so on ($b=2^{\frac{q}{12}}$ with $q \in \left[13,14,15 \ldots 23\right]$) until $q=24$ where the pitch shifting now has come "full cycle".
And of course, to link it back to what Hilmar mentions, notice that $2^{\frac{13}{12}} \approx 2.1189\ldots$, that $0.1189\ldots$ "detuning" factor lands the components in such a way that the human ear choses to "latch" on the nearest tone (between $f_{before},f_{after}$) and thus perceived pitch goes down.
This covers waveforms for which the perceived pitch is lowered upon pitch shifting.
A note on sources:
Long time ago, I read a book on Fractals and that is where I first saw the Weierstrass function. At the time of reading the book, I did not understand fully everything I read. But I was impressed and puzzled. That book was in a different language (than English) and in fact, it was a (bit of a sloppy) "copy-paste-translate" from various books. Very recently, I found the original book those authors had used and I couldn't believe my luck, I just grabed it. That original book is "Fractals, Chaos, Power Laws: Minutes from an infinite paradise" by Manfred Schroeder. It is absolutely E P I C.
Sheppard tones and the Weierstrass function are mentioned in pages 95-97 (in my edition).
The part of the discussion on aliasing in this answer was added after quite a few people mentioned aliasing which motivated me to think about using it.
The breakdown of how does the $2^{\frac{1}{12}}$ emerges is not mentioned in the book. I added it here because it is not exactly obvious. To this, I was helped by a friend (M.P.L) as initially I was trying to substitute $k+1$ when it really emerges on its own.
The point about the Weierstrass function being continuous but not differentiable is the most difficult to grasp. Or, that has been very difficult for me. The mathematical proof, the way you go about pinpointing this fact, is not incomprehensible but it requires a lot of effort. Towards that goal, I found Johan Thim's Masters thesis incredibly useful. It contains a large number of such functions too, it's great.
The initial part on geometric series and music is general knowledge from various sources and experiences, cannot exactly pinpoint their source but I have added as many links as I could.
