Patterns in modular multiplication and frequency tables

230 Views Asked by At

I moved this question from MathOverflow since it seemed not appropriate there.


Consider the multiplication table $f(n,m) = (n\cdot m) \text{ mod } N$ for $n,m \leq N/2$. For $N=30$ it looks like this:

enter image description here

Shades of gray depict the distance $|k - N/2|$, from white for $k=0$ to black for $k = N/2$. For $N = 300$ this gives the following picture:

enter image description here

Now consider a completely different table: the table of frequencies $n : N$ in which you draw in the $n$-th row $n$ dots at exact positions $i/n \cdot N$ for $i = 0,\dots n-1$. For $n,i \leq N/2$ this table looks like this:

enter image description here

When we set the positions to rounded values $[i/n \cdot N]$ the picture changes slightly

enter image description here

and it becomes more similar to the multiplication table. Overlaying the two tables reveal that the yellow dots perfectly lie on blurred "lines" in the multiplication table:

enter image description here

The two pictures next to each other: enter image description here

In more detail the top left and the bottom left part of the tables:

enter image description here

enter image description here

Here it is the voids between the yellow dots that lie on blurred "lines" visible in the multiplication table:

enter image description here

The voids disappear when the yellow dots are at their exact positions $i/n \cdot N$:

enter image description here

I wonder if someone is around who says: All of this comes as no surprise, it could easily have been expected. But a little bit more thorough "explanation" would be very much appreciated. Especially of the fact that rounding systematically creates similarities that are not present when the yellow dots are at their exact positions.

Another specific question is: Why is the center of the "whirl" in the lower right quadrant almost exactly at the position $[N/3,N/3]$, independent of $N$?

enter image description here

1

There are 1 best solutions below

3
On BEST ANSWER

The patterns observed can be explained with simple justification. In your original picture, the white regions correspond to the regions of coordinates $(m,n)$ where $mn$ is around $0 \bmod{N}$. In the yellow graph, the entry $(m,n)$ yielded from $i$ corresponds to the solution to $mn = iN$. It is pretty clear from these two facts that the yellow dots would lie in the white regions. The graph formed by $(m,n)$ has no voids because it traces rectangular hyperbolas. When you do round $m$, you create voids because of the uneven rounding.

As for the whirls and their centers, the reason becomes much more apparent when you extend your picture to an $N \times N$ grid. You will see whirls centered around $\big(\frac{N}{i},\frac{N}{i}\big)$ for $i=2,3,\cdots$ and once again, you explain this phenomenon just by looking at the rules. The curved fringes you see are rectangular hyperbolas as they are solutions to keeping the product of coordinates within a certain small range of colors. At the points of the form $\big(\frac{N}{i},\frac{N}{i}\big)$, these fringes become perpendicular lines centered at these points. The reason is that $\frac{N}{i}x$ is highly periodic modulo $N$, and thus, the vertical and horizontal lines through $\big(\frac{N}{i},\frac{N}{i}\big)$ are the fringes at this region. This is what you observe as the whirl effect.