While reading Wolfgang Schramm's original paper concerning the relationship between the discrete Fourier transform and gcd, I came across the following condensed argument for his more general theorem relating the discrete Fourier transform of a particular type of arithmetic function to a Dirichlet convolution with the arithmetic function and the Ramanujan sum (see bottom of pg.3 in linked pdf):
A corollary of this fact is given as follows (see top of pg.4 in pdf):
Corollary. If $f$ is a multiplicative function, then $F_{f}(m,n)$ is also multiplicative in variable $n$.
Proof. The Ramanujan sum $c_{n}(m)$ is multiplicative in $n$ and the Dirichlet convolution preserves the multiplicativity of functions.
As I'm not a number theorist by training, an answer to this post should accomplish the following:
- Very carefully explicate, in full detail, the chain of equalities we observe in the condensed proof.
- Similarly, explain how the corollary follows from the theorem on pg.2 of the linked pdf.
- Bonus points if you can elaborate on why the inverse Fourier transform takes the form it does in the theorem on pg.2
By definition, $$F_f(m,n):=\sum_{k=1}^n f((k,n))\cdot \exp(-2\pi i k m/n),$$ $$c_n(m):=\sum^n_{k=1,(k,n)=1}\exp(2\pi i k m/n),$$ and the convolution product is given by $$(f\ast g)(n) :=\sum_{d|n}f(d)g(\frac{n}{d}).$$ The third definition gives the third equality immediately, and it is not hard to see that the second definition gives the second equality, with $n\sim n/d$ and $j\sim k$. Note that the minus sign just means we are taking the sum backwards, $\exp(-2\pi i k m/n) = \exp(2\pi i k (n-m)/n)$.
The first definition also gives the first equality directly, but here there is more to keep track of. But there is nothing really number theoretic going on, it's only combinatorics. If you write out the first above definition and group terms according to what the paper tells you to do, you arrive at the desired formula directly. I can provide more details if you want, but it gets a little messy if one wants to be careful.
The corollary is proven in the following way: The theorem shows that the discrete Fourier transformation is really a convolution product. Now, if we assume $f$ is multiplicative, then its discrete Fourier transformation is hence a convolution product of multiplicative functions (since it is a separate fact that $c_n$ is multiplicative). Finally, it is a standard result, and not hard to show directly, that the convolution product of multiplicative functions are multiplicative. This implies the corollary.
Edit: I'll add some more details. I don't think I can be more explicit in the two latter equalities, it is literally just checking that the definition is satisfied, symbol for symbol basically.
To see the first equality, the only non-trivial step is regrouping the $k$ in families where the $\gcd$ with $n$ is the same. So for each $d|n$, we collect all the indices $k$ that satisfies $(k,n)=d$. For all these entries, we see that $f((k,n))=f(d)$ agree. This can also be thought of another way: for each such $k$, write $k=d\cdot j$, where $(k,n)=d$ and $j$ is relatively prime to $n$. Of course, the possible values of $j$ lies between $1$ and $n/d$, as $1\leq k\leq n$. So we don't have to run over all $k$ satisfying $(k,n)=d$, we can reduce to going over all $j\leq n/d$ with $(j,n)=1$. We get a double sum: check that you are convinced of the bijection $\lbrace 1,2,\dots, n\rbrace \leftrightarrow \bigcup_{d|n} \lbrace 1\leq j\leq n/d\mid (j,n)=d\rbrace.$ You can then pull out the $f(d)$ term, as that is independent of $j$ when $d$ is given, and the remaining exponential term is exactly what you see in the proof.
One can check that $c_n$ is multiplicative directly, but a reference is Arithmetical Functions by Schwarz and Spilker, see p. $16$ here https://books.google.dk/books?id=12hjjwEACAAJ. The proof uses that the convolution product of two multiplicative functions is multiplicative, which I suspect is proved in the full book, but left out in the Google Books version. A proof of this fact is given here http://mathonline.wikidot.com/the-dirichlet-convolution-of-two-arithmetic-functions.