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:

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

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

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

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.

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

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

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.

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$

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

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$.

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$.

idea? Where and how does the magic occur? Why "then"? (Ah, you edited your comment in the meanwhile. What is a "dilation"?) $\endgroup$ – Hans-Peter Stricker Jan 25 '19 at 13:48