Questions concerning the Fourier analysis of $ nx\ \%\ m$

Question

Let $x\ \%\ m$ be the residue of $x$ modulo $m$, i.e.

$$x \equiv x\ \%\ m\pmod{m}$$

The plots of the functions $f_{nm}(x) = nx\ \%\ m$ exhibit characteristic patterns, especially periods of length $1/\operatorname{gcd}(n,m)$. (Look at the zeros of $f_{nm}(x)$ – there are $\operatorname{gcd}(n,m)$ of them.)

---

I found it natural to apply discrete Fourier analysis to $f_{nm}(x) = nx\ \%\ m$, i.e. to determine the coefficients

$\tilde{f}_{nm}( k) = \frac{1}{m}\sum_{x=0}^{m-1}e^{i2\pi k x/m}f_{nm}(x) = \frac{1}{m}\sum_{x=0}^{m-1}e^{i2\pi k x/m}(nx\ \%\ m)$

I've done this numerically and could reproduce

$f_{nm}(x) = \sum_{k=0}^{m-1}e^{-i2\pi k x/m}\tilde{f}_{nm}( k) = nx\ \%\ m $

well, so I'm quite confident that I calculated the coefficients correctly.

Plotting the coefficients $\tilde{f}_{nm}( k)$ in the complex plane gives the following pictures for $m = 7,8$. Note that I gave colors to the bars in the $f_{nm}$ plots that indicate, that $f_{nm}$ acts as a permutation and that the numbers $f_{nm}^l(x)$, $1 \leq l \leq l_0$ lie on a permutation cycle of some length $l_0 < m$.

---

$m = 8$

---

$m = 7$

These pictures allow to make some observations, which of course are partly related:

1. $\sum_{k=0}^{m-1} \tilde{f}_{nm}( k) = 0$

2. $\operatorname{Re}(\tilde{f}_{nm}(0)) = (m - \operatorname{gcd}(n,m))/2$

3. $\operatorname{Im}(\tilde{f}_{nm}(0)) = 0$

4. When $k \neq 0$ then $\operatorname{Re}(\tilde{f}_{nm}(k)) = -\operatorname{gcd}(n,m)/2$ for $k \equiv 0 \pmod{\operatorname{gcd}(n,m)}$ and $\operatorname{Re}(\tilde{f}_{nm}(k)) = 0$ otherwise.

5. When $m$ is prime then $\operatorname{Re}(\tilde{f}_{nm}(k)) = -1/2$ for all $n < m$ and $k\neq 0$.

6. The coefficients $\tilde{f}_{nm}(k)$ always come in conjugate pairs.

7. For $n_1, n_2$ with $\operatorname{gcd}(n_1,m) = 1$ and $\operatorname{gcd}(n_2,m) = 1$ the numbers $\tilde{f}_{n_im}(k)$ are specific permutations of each other.

8. When $m$ is even the number of $k$ with $\operatorname{Re}(\tilde{f}_{nm}(k)) < 0$ is $\frac{2}{m - 4}(n - m/2)^2 + 1$

9. When $m$ is prime the number of $k$ with $\operatorname{Re}(\tilde{f}_{nm}(k)) < 0$ is $m - 1$.

10. When $n$ and $m$ are coprime the order of the coefficients $\tilde{f}_{nm}(k)$ for $k\neq 0$ is the same as of the numbers $f_{nm}(x)$ for $x \neq 0$.

11. The number of permutation cycles – i.e. different bar colors, including the invisible 1-cycle $(0)$ – is $\sum_{d|m} \varphi(d)/\omega_d(n)$ with Euler's totient function $\varphi(d)$ and $\omega_d(n)$ the multiplicative order of $n$ modulo $d$. (But that's possibly another story.)

---

Known results that are somehow related to these findings:

• The sum of the $m$-th roots of unity is $0$: $\sum_{k=0}^{m-1}e^{i2\pi k/m} = 0$.

• Euler's totient function is the Fourier transform of the greatest common divisor function: $\sum_{k=1}^m e^{i2\pi k/m} \cdot \operatorname{gcd}(k,m) = \varphi(m)$

• The sum $\sum _{d\mid m}\varphi (d)$ equals $m$.

• The sum of the roots $\rho_k$ of a polynomial $a_mx^m + a_{m-1}x^{m-1} + \dots + a_1x + a_0$ equals $-a_{m-1}/a_m$: $\sum _{k = 0}^{m-1}\rho_k = -a_{m-1}/a_m$.

• Riemann's hypothesis: The real part of every non-trivial zero of the Riemann zeta function is $1/2$.

• Concerning permutations (see statement 7) also Galois theory may be related, which considers permutations of roots as opposed to permutations of Fourier coefficients.

---

Considering that for arbitrary $n,m$ the functions $f_{nm}(x) =nx\ \%\ m$ behave rather unpredicatable and pseudo-random (like prime numbers do), I guess that proofs of the above statements 5 and 7 (to pick the more tricky ones) may be not elementary or even trivial, especially because there's no closed formula for $nx\ \%\ m$ that would allow to evaluate the sum $\sum e^{i2\pi k x/m}(nx\ \%\ m)$. But I may be wrong, and elementary proofs do exist. On the other hand, a proof might be as hard as a proof of Riemann's hypothesis. Who knows – I don't?

---

So my question is:

Is any proof of the above statements known:

5. When $m$ is prime then $\operatorname{Re}(\tilde{f}_{nm}(k)) = -1/2$ for all $n < m$ and $k\neq 0$?

7. For $n_1, n_2$ with $\operatorname{gcd}(n_1,m) = 1$ and $\operatorname{gcd}(n_2,m) = 1$ the numbers $\tilde{f}_{n_im}(k)$ are specific permutations of each other.

10. When $n$ and $m$ are coprime the order of the coefficients $\tilde{f}_{nm}(k)$ for $k\neq 0$ is the same as of the numbers $f_{nm}(x)$ for $x \neq 0$.

Answer 1

For $\gcd(n,m)=1$, we have by a change of variable $nx\mapsto x$ that $$\tilde f_{n,m}(k)=\tilde f_{1,m}(\bar n k),$$ where $\bar n\bmod{m}$ is the multiplicative inverse of $n\bmod{m}$. This proves Claim 7 (as user44191 said earlier).

Claim 5 now follows easily, since for $k\not\equiv 0\pmod{m}$ we have $$\tilde f_{n,m}(k)=\tilde f_{1,m}(\bar n k)=\frac{1}{m}\sum_{x=0}^{m-1}e^{2\pi i\bar nk x/m}x=\frac{1}{e^{2\pi i\bar nk/m}-1}=-\frac{1}{2}-\frac{i}{2}\cot\frac{\pi \bar nk}{m}.$$

Answer 2

This is an elementary proof for statement 7:

If $\gcd(n_1, m) = \gcd(n_2, m)$, then there is some $\text{(mod m)}$-invertible $a$ (with inverse $b$) such that $a n_1 \equiv n_2 \text{(mod m)}$ (this statement is surprisingly not immediately easy to prove, but isn't hard with Chinese Remainder Theorem). Then $\tilde{f}_{n_2 m}(k) = \frac{1}{m} \sum_{x = 0}^{m - 1} e^{2 \pi i k x/m} (n_2 x \% m)$

$= \frac{1}{m} \sum_{x \in \{0, \dots, m - 1\}} e^{2 \pi i k x/m} (a n_1 x \% m)$

$= \frac{1}{m} \sum_{x' \in \{0, \dots, m - 1\}} e^{2 \pi i k bx'/m} (a n_1 bx' \% m)$ (using the substitution $x \equiv b x' (mod m)$)

$= \frac{1}{m} \sum_{x' \in \{0, \dots, m - 1\}} e^{2 \pi i k bx'/m} (n_1 x' \% m)$

Let $k' = bk$:

$= \frac{1}{m} \sum_{x' \in \{0, \dots, m - 1\}} e^{2 \pi i k' x'/m} (n_1 x' \% m)$

$= \tilde{f}_{n_1 m}(k')$.