# Why is $n_{n^2-1}$ the smallest graph that clearly shows the structure of multiplication by $n$?

Initially, I wanted to ask this question as a puzzle.

1. Consider a regular $$m$$-gon. Let $$0$$ be the lower corner and count the corners clockwise.

2. Let $$n_m$$ be the multiplication-by-$$n$$-graph of $$m$$ for $$n < m$$ by drawing an arrow from every corner $$a$$ to the corner $$a\cdot n\operatorname{mod}m$$.
These are the eight relevant multiplication-by-$$n$$-graphs of $$10$$ as (hopefully) intelligible to every school kid:

3. For fixed $$n$$, in the limit $$m \rightarrow \infty$$ the graph $$n_m$$ will somehow display $$n-1$$ cusps.
E.g. $$10_{517}$$:

4. What is the smallest graph $$n_m$$ that undeniably displays $$n-1$$ cusps?

You may think hard about this (or not), but the (probably right) answer can be found easily by simulation: Just draw the graphs

and you will find that the graph with $$m = n^2-1$$

yields this smallest graph.

Be promised: It's the same for arbitrary $$n$$ instead of $$10$$:

Even for smaller $$n$$ than $$10$$:

My question is:

Why is this so?

I'm looking for strong algebraic and/or arithmetic arguments. I have no idea.

• So I don't quite understand what counts at undeniably displaying $n-1$ cusps but, as (hopefully) intelligible to every school kid, $n^2-1=(n-1)(n+1)$, so you have $n-1$ group linked by two-way edges (reflecting the fact that $n^2$ is $1$), which produces a nice figure as in your pictures. For smaller values, there is a perturbation related to the fact that either $n^2$ is not $1$ which destroys somewhat the symmetry or there are not enough groups (or both). To be more mathematically precise, I would need to be able to give a mathematical content to "undeniably displaying cusps". – Olivier Nov 14 '18 at 16:32
• Because $n^2-1=(n-1)(n+1)$, multiplication by $n$ modulo $n^2-1$ is an involution that sends the $n+1$ terms $0,2,\cdots,n$ each to one of the $n-1$ another $n$-ade (decade for $n=10$). This it seems to me, entirely explains the nice (but trivially simple) geometric design observed. – Olivier Nov 14 '18 at 19:02
• @HansStricker I do understand that your question is about the smallest $m$ for every $n$ and not simply small values of $n$, but if we try to find the pattern of $m$'s for various small values of $n$ it can help guess why this pattern should start at $n^2-1$; and it can also help others understand what your "seeing clearly" is. This is why I suggested this. But if you are somehow opposed to even considering larger $m$'s, hey, it's your question, not mine. – Gro-Tsen Nov 14 '18 at 21:31
• If your "seeing clearly" isn't my "seeing clearly", Hans, then doesn't that justify a vote to close the question as "primarily opinion-based"? Mind you, I'm not voting to close it, but I do think Olivier's comment about involutions explains what's going on. – Gerry Myerson Nov 14 '18 at 21:46
• "I cannot understand that my question is considered to be unclear (supposing one accepts my admittedly somehow unclear - but strongly supported by examples - definition of "undeniably displaying cusps")" That's precisely how one can consider your question unclear: by finding it hinges on a too-unclear definition. – Noah Schweber Nov 15 '18 at 2:49

At the request of Gerry Myerson, here is what I understand.

As $$n^2=1$$ modulo $$n^2-1$$, the multiplication by $$n$$ graph on $$m=n^2-1$$ vertices as defined in the question is formed

1) First, of isolated points which satisfy $$nx=x$$, or equivalently $$(n+1)|x$$, of which there are $$n-1$$. These are the $$n-1$$ initial point of each "cusps" (a "cusp" is a group of $$n+1$$ consecutive points on the circle starting with a point congruent to 0 modulo $$n+1$$).

2) Second, of bi-directional edges relating a pair of points. Now, if $$x=y+k(n+1)$$ with $$0\leq y\leq n$$, then $$nx=ny+k+kn=ny+k(n+1)=-y+(k+y)(n+1)$$ so each point in the $$n+1$$ terms are linked to a different group.

This entirely explains the nice display when $$m=n^2-1$$. If $$m, then $$(n-1)(n+1)>m$$, so there can be no periodicity of the form above.

Now, how about the assertion that when $$m$$ is large with respect to $$n$$, we do see $$n-1$$ "cusps"? The slopes of two consecutive edges (corresponding to $$nx$$ and $$n(x+1)$$) are increasing. Visually, if you incrementally increase slopes of lines, this draws the convex envelope of a cusp (people who know more than me about geometry, that is to say people who know anything at all, will tell us the equation of the cusp drawn in this way). Whence the cusps. When will the cusps be dark (almost vertical slope)? When the edges are close to diameters. And when will that be? When $$nx$$ is close to $$x+m/2$$. If that is the case, then $$n(x+m/(n-1))$$ will also be close to $$x+m/(n-1)+m/2$$. So we see $$n-1$$ maximally dark cusps (and likewise one can count the relatively darker cusps by cutting the circle in 3, 4 etc. and translate in terms of congruences).

Putting everything together, if $$m$$ is large, we see $$n-1$$ dark cusps, if $$m=(n-1)(n+1)$$ we see $$n-1$$ grouping shuffled by multiplication by $$n$$ and this periodicity can not occurred if $$m<(n-1)(n+1)$$. So yes, $$n^2-1$$ is the first instance in which the ultimate pattern unambiguously appear.

• Thanks for taking the time to understand my question, and thanks for the answer which is as definite as I could hope for. – Hans-Peter Stricker Nov 15 '18 at 12:08
• @HansStricker What I'd like to know is how you drew the pictures (and if that is not too much to ask, if you could send me a couple of the large ones as large png?). – Olivier Nov 15 '18 at 14:01
• If you send me an email to stricker@syspedia.de, I'll send you a link. – Hans-Peter Stricker Nov 15 '18 at 14:48