1
$\begingroup$

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

enter image description here

enter image description here


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$

enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here


$m = 7$

enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user44191 Jan 25 '19 at 13:44
  • $\begingroup$ @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"?) $\endgroup$ – Hans-Peter Stricker Jan 25 '19 at 13:48
  • $\begingroup$ 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$. $\endgroup$ – user44191 Jan 25 '19 at 14:02
  • 1
    $\begingroup$ @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. $\endgroup$ – Hans-Peter Stricker Jan 25 '19 at 14:43
  • 1
    $\begingroup$ 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. $\endgroup$ – GH from MO Jan 25 '19 at 14:45
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – user44191 Jan 25 '19 at 14:09
  • $\begingroup$ @user44191: Good catch, I fixed both issues. Thanks a lot! $\endgroup$ – GH from MO Jan 25 '19 at 14:23
  • $\begingroup$ @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. $\endgroup$ – Hans-Peter Stricker Jan 25 '19 at 14:45
  • 1
    $\begingroup$ 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. $\endgroup$ – Greg Martin Jan 25 '19 at 18:16
  • $\begingroup$ @HansStricker: I think Greg Martin meant his previous comment for you. $\endgroup$ – GH from MO Jan 25 '19 at 18:18
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.