24
$\begingroup$

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

enter image description here

For larger $N$ some kind of stable structure emerges

enter image description here

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

enter image description here enter image description here

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):

![enter image description here


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$

enter image description here

But not for larger $M$

enter image description here

For $M:(3M -1)$

![![enter image description here

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Henry Jan 11 at 16:51
  • $\begingroup$ @Henry. Thanks! Can you tell if the "main" envelope is a half cardoid? $\endgroup$ – Hans-Peter Stricker Jan 11 at 16:55
  • 5
    $\begingroup$ Yes it is: Wikipedia says this is a result of Luigi Cremona $\endgroup$ – Henry Jan 11 at 16:57
  • 1
    $\begingroup$ 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, $\endgroup$ – Alex R. Jan 11 at 21:03
  • 1
    $\begingroup$ @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.) $\endgroup$ – Hans-Peter Stricker Jan 16 at 13:28
8
$\begingroup$

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

enter image description here enter image description here enter image description here enter image description here

$\endgroup$
2
$\begingroup$

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:

enter image description hereenter image description hereenter image description here

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

  • Overlaying the truncated patterns gives the pattern in question.

$\endgroup$

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.