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

• Very pretty. The envelopes stay in place because each corresponds to connecting angle point $\theta$ (measured anticlockwise from the bottom) to angle point $k\theta$ for given integer $k \ge 2$ and all possible up to $0 \lt \theta \le \frac{2\pi}{k}$. For given $N$ you only get lines when $\theta = 2\pi \frac{n}{N}$ and $0 \lt n \le \frac{N}{k}$, but that has little effect on the envelopes. – Henry Jan 11 at 16:51
• @Henry. Thanks! Can you tell if the "main" envelope is a half cardoid? – Hans-Peter Stricker Jan 11 at 16:55
• Yes it is: Wikipedia says this is a result of Luigi Cremona – Henry Jan 11 at 16:57
• Rephrasing, these curves are arising as the envelopes of pairs of numbers whose division gives $2,3,4,...$, hence the resemblance to cardioids, where the second coordinate "moves faster" than the first. With some care you can probably also show a much lower density of near-perpendicular curves through each cardioid, – Alex R. Jan 11 at 21:03
• @AlexRavsky: Not quite the same when it comes to the order in which edges are created - which of course may be neglected. (Note that the first to ways create the edges in the same order.) – Hans-Peter Stricker Jan 16 at 13:28

## 2 Answers

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.