#### [SOLVED] An enigmatic pattern in division graphs

Draw the numbers $$1,2,\dots,N$$ on a circle and draw a line from $$n$$ to $$m>n$$ when $$n$$ divides $$m$$:

For larger $$N$$ some kind of stable structure emerges

which remains perfectly in place for ever larger $$N$$, even though the points on the circle get ever closer, i.e. are moving.

This really astonishes me, I wouldn't have guessed. Can someone explain?

In its full beauty the case $$N=1000$$ (cheating a bit by adding also lines from $$m$$ to $$n$$ when $$(m-N)\%N$$ divides $$(n-N)\%N$$ thus symmetrizing the picture):

Note that a similar phenomenon – stable asymptotic patterns, esp. cardioids, nephroids, and so on – can be observed in modular multiplication graphs $$M:N$$ with a line drawn from $$n$$ to $$m$$ if $$M\cdot n \equiv m \pmod{N}$$.

For the graphs $$M:N$$, $$N > M$$ for small $$M$$

But not for larger $$M$$

For $$M:(3M -1)$$

It would be interesting to understand how these two phenomena relate.

Note that one can create arbitrary large division graphs with circle and compass alone, without even explicitly checking if a number $$n$$ divides another number $$m$$:

1. Create a regular $$2^n$$-gon.

2. Mark an initial corner $$C_1$$.

3. For each corner $$C_k$$ do the following:

1. Set the radius $$r$$ of the compass to $$|C_1C_k|$$.

2. Draw a circle around $$C_{k_0} = C_k$$ with radius $$r$$.

3. On the circle do lie two other corners, pick the next one in counter-clockwise direction, $$C_{k_1}$$.

4. If $$C_1$$ does not lie between $$C_{k_0}$$ and $$C_{k_1}$$ (in counter-clockwise direction) or equals $$C_{k_1}$$:

5. Draw a line from $$C_k$$ to $$C_{k_1}$$.

6. Let $$C_{k_0} = C_{k_1}$$ and proceed with 5.

7. Else: Stop.

There are three equivalent ways to create the division graph for $$N$$ edge by edge:

1. For each $$n = 1,2,...,N$$: For each $$m\leq N$$ draw an edge between $$n$$ and $$m$$ when $$n$$ divides $$m$$.

2. For each $$n = 1,2,...,N$$: For each $$k = 1,2,...,N$$ draw an edge between $$n$$ and $$m = k\cdot n$$ when $$m \leq N$$.

3. For each $$k = 1,2,...,N$$: For each $$n = 1,2,...,N$$ draw an edge between $$n$$ and $$m = k\cdot n$$ when $$m \leq N$$.

#### @Hans-Peter Stricker 2019-01-14 09:21:10

Putting the pieces together one may explain the pattern like this:

• The division graph for $$N$$ can be seen as the sum of the multiplication graphs $$G_N^k$$, $$k=2,3,..,N$$ with an edge from $$n$$ to $$m$$ when $$k\cdot n = m$$. When $$n > N/k$$ there's no line emanating from $$n$$. (This relates to step 7 in the geometric construction above.)

• The multiplication-modulo-$$N$$ graphs $$H_{N}^k$$ have a weaker condition: there's an edge from $$n$$ to $$m$$ when $$k\cdot n \equiv m \pmod{N}$$.

• So the division graph for $$N$$ is a proper subgraph of the sum of multiplication graphs $$H_{N+1}^k$$.

• The multiplication graphs $$H_{N}^k$$ exhibit characteristic $$k-1$$-lobed patterns:

• These patterns are truncated in the graphs $$G_{N}^k$$ exactly at $$N/k$$.

• Overlaying the truncated patterns gives the pattern in question.

#### @Hans-Peter Stricker 2019-01-12 08:41:24

To add some visual sugar to Alex R's comment (thanks for it):