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

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

• Statement 7 is relatively simple; find $a$ invertible (mod m) with inverse $b$ with $a n_1 \cong n_2$; then $\tilde{f}_{n_2 m}(k) = \tilde{f}_{n_1 m}(b k)$. All that's needed is that $\%m$ is periodic and that $f_{n_1 m}$ and $f_{n_2 m}$ can be seen as "dilations" of each other. – user44191 Jan 25 '19 at 13:44
• @user44191: Thanks. Am I right, and this is just a proof idea? Where and how does the magic occur? Why "then"? (Ah, you edited your comment in the meanwhile. What is a "dilation"?) – Hans-Peter Stricker Jan 25 '19 at 13:48
• I mean what GH from MO stated at the top of his post: a change of variables via multiplication by an invertible element of $\mathbb{Z}/m$. – user44191 Jan 25 '19 at 14:02
• @GHfromMO: Thanks for pointing out that you gave a simple explicit formula! That's what I didn't expect - and what I find thrilling, given the quasi-randomness of $nx\ \%\ m$ (at least in some respects). What I try to understand: Why doesn't such "taming randomness" help with Riemann's hypothesis. – Hans-Peter Stricker Jan 25 '19 at 14:43
• Thanks! My previous comment was wrong: the cotangent value indeed behaves nicely in $k$, but on the other hand $\bar n\bmod{m}$ is pretty random; its distribution is tied with Kloosterman sums. – GH from MO Jan 25 '19 at 14:45

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

• I think you may have forgotten an $i$ somewhere? Also, it may be helpful to note that the equality after the sum uses the fact that $k \neq 0$. – user44191 Jan 25 '19 at 14:09
• @user44191: Good catch, I fixed both issues. Thanks a lot! – GH from MO Jan 25 '19 at 14:23
• @GHfromMO: Thanks for the "simple explicit formula" for $\tilde{f}_{n,m}(k)$! That's what I didn't expect - and what I find thrilling, given the quasi-randomness of $nx\ \%\ m$ (at least in some respects). What I try to understand: Why doesn't such "taming randomness" help with Riemann's hypothesis. – Hans-Peter Stricker Jan 25 '19 at 14:45
• Just because the Riemann hypothesis is often summarized as saying that the primes "behave randomly" doesn't mean that every random-seeming phenomenon that gets analyzed is related to the Riemann hypothesis. The onus is on someone asserting a relationship with RH to provide some mathematical evidence. – Greg Martin Jan 25 '19 at 18:16
• @HansStricker: I think Greg Martin meant his previous comment for you. – GH from MO Jan 25 '19 at 18:18

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