11
$\begingroup$

Consider multiplication group tables modulo $n$ with entries $k_{ij} = (i\cdot j)\ \%\ n$ visualized according to these principles:

  • Colors are assigned to numbers $0 \leq k \leq n$ from

    • $\color{black}{\textsf{black}}$ for $k=0$ over

    • $\color{red}{\textsf{red}}$ for $k=\lfloor n/4\rfloor$ and

    • $\color{silver}{\textsf{white}}$ for $k=\lfloor n/2\rfloor$ and

    • $\color{blue}{\textsf{blue}}$ for $k=\lfloor 3n/4\rfloor$ back to

    • $\color{black}{\textsf{black}}$ for $k = n$

  • Sizes are assigned to numbers $0 \leq k \leq n$ by

    • $\textsf{1.5}$ if $k=\lfloor n/4\rfloor$ or $\lfloor 3n/4\rfloor$

    • $\textsf{1.0}$ otherwise

  • Positions are shifted by $(n/2,n/2)$ modulo $n$ to bring $(0,0)$ to the center of the table.

Visualized this way, you will occasionally find (for some $n$) highly regular multiplication group tables like these (with $n=12,20,28,44,52,68$):

enter image description here

My question is:

Why do these patterns occur exactly when $n = 4p$ with a prime number $p$?


Find here some examples for $n \neq 4p$, e.g. $n=61, 62, 63, 64$:

enter image description here


Here for some other prime numbers: $n = 4\cdot 31 = 124$ and $n = 4\cdot 37 = 148$:

enter image description here


One may observe that for $n = 4m$ and $x,y = m$ or $x,y = 3m$ the "size 1.5" dots are systematically separated by $0$ (= black) and $n/2$ (= white) dots, i.e. that there are only and exactly $4$ values along these lines.

enter image description here


For the sake of completeness: the multiplication group table modulo $8 = 4\cdot 2$ (which also qualifies, but not so obviously):

enter image description here

$\endgroup$
  • 7
    $\begingroup$ What do they look like when $n$ is not $4$ times a prime? $\endgroup$ – Robert Israel Feb 26 at 21:53
  • $\begingroup$ Could you include an example of a not so regular table? $\endgroup$ – Servaes Feb 26 at 21:54
  • $\begingroup$ To me the $n\ne 4p$ examples look just about as regular as the $n=4p$ ones, with the exception of the locations of the "size $1.5$" dots. $\endgroup$ – Robert Israel Feb 26 at 22:02
  • $\begingroup$ @RobertIsrael: To me, too. My question is just about the "size 1.5" dots. $\endgroup$ – Hans-Peter Stricker Feb 26 at 22:04
5
$\begingroup$

To elaborate a bit on Robert Israels fine answer, first note that: $$ \begin{align} xy&\equiv n/4\\ xy&\equiv 3n/4 \end{align} $$ implies that $n$ must be divisible by $4$. Hence we only have such situations when $n=4q$ for some $q$. This is true whether $q$ is prime or not. So let us consider $n=4q$ a bit further. Then we look at: $$ \begin{align} xy&\equiv q\\ xy&\equiv 3q \end{align} $$ which can be summarized as: $$ xy=q(2m+1) $$ for some $m$. This actually reveals why $n=64=4\cdot 16$ also appears to somewhat work. Here $q=16$ so any solutions to $xy=16(2m+1)$ will work. We have the lines $x,y=\pm2,\pm4,\pm8,\pm16$ with varying density of "size 1.5" points.

When $q$ is prime, the picture becomes simpler since all solutions to $xy=q(2m+1)$ have to lie on one of the four lines $x=\pm q,y=\pm q$.


UPDATE: Some insights on the general case here. Write $n=4q+t$ for $t\in\{-1,0,1,2\}$. Then we have: $$ \begin{align} \lfloor n/4\rfloor &= q+\lfloor t/4\rfloor\\ \lfloor 3n/4\rfloor &= 3q+\lfloor 3t/4\rfloor \end{align} $$ where we can make the following table: $$ \begin{array}{c|r|r|r|r} t & -1 & 0 & 1 & 2\\ \hline \lfloor t/4\rfloor & -1 & 0 & 0 & 0\\ \lfloor 3t/4\rfloor & -1 & 0 & 0 & 1 \end{array} $$ and so we can cover each $t$-case based on that.


CASE $t=0$

Let us first reconsider the case $t=0$ so that $n=4q$, which was already covered above. Then: $$ xy=q(2\mu+1) $$ will yield "size 1.5" dots. If $q=ab$ is composite then: $$ \begin{align} x&=a\\ y&=b(2\mu+1) \end{align} $$ will yield a vertical line of points $2b$ apart that are all of "size 1.5". If on the other hand $q$ is prime, then: $$ \begin{align} x&=q\\ y&=2\mu+1 \end{align} $$ will yield a very visible vertical line of points only $2$ apart.


CASE $t=1$

Suppose $t=1$. Then $n=4q+1$. For this case, having $xy\equiv\lfloor n/4\rfloor=q$ implies: $$ \begin{align} xy &=q+\mu n \end{align} $$ Now, since $q,n$ are relatively prime, $\mu$ must be a multiple of $q$ for two such situations to have any shared factor. So assume $\mu=\gamma q$. Then: $$ xy=(\gamma n+1)q $$ So if $q=ab$ we have: $$ \begin{align} x &= a\\ y &= (\gamma n+1)b \end{align} $$ showing that no vertical lines can exist, since the $y$-values must be far more than $n$ units apart. On the other hand, plugging in $\mu=0$ in the $y$-expression above shows why points tend to lie on the hyperbola: $$ xy=q $$


I think the other cases can be broken down in a similar fashion, so I will stop here.

$\endgroup$
  • $\begingroup$ Thanks for this answer! May I help with specific visualizations? Where and why are you "still a bit unsure"? $\endgroup$ – Hans-Peter Stricker Feb 26 at 23:43
  • $\begingroup$ @HansStricker: Thank you. Well, it is just that the "patternless" cases, ie. no horizontal or vertical lines, behave in a more chaotic-seeming manner regarding the 1.5 dots. $\endgroup$ – String Feb 26 at 23:47
  • $\begingroup$ @HansStricker: If you are able to draw more clear conclusions for those "chaotic" cases where $n\neq 4q$ or to visualize them in order to see different principles at play, please let me know. I think the floor function is what throws in the "chaos" in the first place :o) $\endgroup$ – String Feb 26 at 23:50
  • 1
    $\begingroup$ @HansStricker: I would put my money on Robert Israel or the like for deeper insights. I merely took his work and explained some helpful details, I guess :o) I regret my comment about the floor function. The main players are the factorizations themselves. The floor function merely compensates for the unsuccesful division of $n$. Any rounding technique would be equally chaotic, I think. $\endgroup$ – String Feb 27 at 0:00
  • 1
    $\begingroup$ @HansStricker: I updated my answer. It has turned into more of a full distinct answer now. I hope it makes sense and sheds some light! $\endgroup$ – String Feb 27 at 10:44
9
$\begingroup$

If $n=4p$, then for $xy \equiv p$ or $3p$ mod $n$ you need $p$ to divide $x$ or $y$ but $2$ to divide neither: thus the "size $1.5$" dots are all on the lines $x = p$, $x = 3p$, $y = p$ and $y = 3p$.

$\endgroup$
  • 1
    $\begingroup$ Where and how does the primeness of $p$ come into play? $\endgroup$ – Hans-Peter Stricker Feb 26 at 22:14

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.