Numbers as figures

Why the figure n/k falls into exactly as many parts as the greatest common divisor says, why ten is the first number with all four kinds of figure, and why primes are exactly the simplexes without a compound figure.

The Geometry and Number theory sections of this website rest on one observation: if you join every k-th point of a regular n-gon, the resulting figure reveals how the numbers n and k relate to each other (see The key to the tetractys). This chapter proves that this is not an accident of the examples drawn, but holds for all numbers. The symbols are explained in the chapter The language of mathematics.

What we need

Only one notion, the greatest common divisor. Chapter 3 treats it in more detail, here the definition is enough.

Definition

For $n, k \in \mathbb{N}$

\begin{aligned} \gcd(n, k) := \max\,\{\, d \in \mathbb{N} :\; & d \mid n \\ \land\; & d \mid k \,\} \end{aligned}

is the greatest common divisor. If $\gcd(n, k) = 1$ , then $n$ and $k$ are called coprime.

Examples: $\gcd(10, 4) = 2$ , since 10 and 4 are both divisible by 2, but not jointly by any larger number. $\gcd(10, 3) = 1$ , the two are coprime. $\gcd(10, 5) = 5$ , since 5 divides 10 itself.

We also need an exact definition of the figure.

Definition

Let $n \ge 3$ and $1 \le k \le \lfloor n/2 \rfloor$ . On a circle lie the points $P_0, P_1, \dots, P_{n-1}$ at equal distances, with indices taken modulo $n$ . The figure $\{n/k\}$ consists of all segments

P_i P_{i+k}, \qquad i = 0, 1, \dots, n-1.

A part is a closed path $P_i,\, P_{i+k},\, P_{i+2k},\, \dots$ that returns to its start.

In words: from a point you always move k points on and join, until you are back at the start. If some points are still free, you begin a further part at the next free point. Step sizes beyond $n/2$ are not needed, since $k$ steps forward give the same figure as $n - k$ steps backward.

How many parts a figure has

n k

The decagon, every fourth point. After five steps you are back at the start although only five points have been reached, and a second pentagram fills the rest. The sliders draw all figures up to the dodecagon.

Theorem 1

Let $n, k$ be as above and $g := \gcd(n, k)$ . Then $\{n/k\}$ falls into exactly $g$ parts. Each has $n/g$ corners and is congruent to $\{\tfrac{n}{g} / \tfrac{k}{g}\}$ .

Proof

The path starting at $P_0$ reaches the point $P_{jk}$ after $j$ steps. We have

\begin{aligned} P_{jk} = P_0 &\iff n \mid jk \\ &\iff \tfrac{n}{g} \mid j \cdot \tfrac{k}{g} \\ &\iff \tfrac{n}{g} \mid j. \end{aligned}

The middle step is dividing by $g$ . The last holds because $\gcd\!\bigl(\tfrac{n}{g}, \tfrac{k}{g}\bigr) = 1$ , otherwise $g$ would not have been the greatest common divisor, and because a divisor of a product that is coprime to one factor must divide the other (by the same argument as Euclid’s lemma, Chapter 4). So the smallest step count $j \ge 1$ back to the start is $j = n/g$ , and the part through $P_0$ has $n/g$ corners.

The part through $P_i$ arises from the one through $P_0$ by turning it on by $i$ points. So all parts have $n/g$ corners, and since together they occupy each of the $n$ points exactly once, there are $n / (n/g) = g$ of them.

The part through $P_0$ occupies the points $P_0, P_g, P_{2g}, \dots$ , that is every $g$ -th point, $n/g$ points at equal distances in all. A step $k = g \cdot \tfrac{k}{g}$ moves $k/g$ places on along these points. Hence it is the figure $\{\tfrac{n}{g} / \tfrac{k}{g}\}$ .

∎

For example: $\gcd(10, 4) = 2$ , so $\{10/4\}$ falls into 2 parts with 5 corners each, and each part is $\{5/2\}$ , a pentagram. $\gcd(10,5) = 5$ , so $\{10/5\}$ consists of 5 parts with 2 corners each, five lines through the centre.

The four kinds follow by themselves

Theorem 1 tells us which kinds of figure can exist at all. Only two questions matter: does the figure fall into several parts, that is $g > 1$ ? And is each part a polygon or a star, that is $k/g = 1$ or $k/g \ge 2$ ?

	$k/g = 1$ , polygon	$k/g \ge 2$ , star
$g = 1$ , one part	Polygon, $k = 1$	Star polygon, $\gcd(n,k) = 1$
$g \ge 2$ , several parts	Compound polygon, $k \mid n$	Compound star, $1 < g < k$

There are no other possibilities. The four basic figures of the site are therefore not a selection but the complete list. There is one borderline case: for $k = n/2$ each part has only two corners, and the figure consists of lines through the centre.

Corollary 2

If $\{m/j\}$ with $2 \le j < m/2$ is a star, then $m \ge 5$ . The pentagram $\{5/2\}$ is the smallest star.

Proof

From $2 \le j < m/2$ it follows that $4 \le 2j < m$ , so $m \ge 5$ . For $m = 5, j = 2$ we have $\gcd(5, 2) = 1$ , and $\{5/2\}$ is a star.

∎

Why ten

n-gon

PolygonCompound polygonStar polygonCompound starLine star

The figures of the decagon, coloured by kind. Polygon, compound polygon, star polygon and compound star all appear together here for the first time.

Theorem 3

Ten is the smallest number whose simplex contains all four kinds of figure. In particular, $\{10/4\}$ is the smallest compound star.

Proof

Let $\{n/k\}$ be a compound star. By Theorem 1 it consists of $g \ge 2$ parts, and each part is the star $\{\tfrac{n}{g}/\tfrac{k}{g}\}$ with $2 \le \tfrac{k}{g} < \tfrac{n}{2g}$ . By Corollary 2, $\tfrac{n}{g} \ge 5$ , so

n = g \cdot \frac{n}{g} \ge 2 \cdot 5 = 10.

Hence no number $n < 10$ contains this kind. For $n = 10$ all four occur: $\{10/1\}$ is the decagon, $\{10/2\}$ two pentagons, $\{10/3\}$ a star in a single stroke, and $\{10/4\}$ two pentagrams.

∎

This proof also shows where the ten comes from. It is $2 \cdot 5$ : the figure needs at least two parts, and each part, being a star, needs at least five points. The five in turn comes from the fact that a star must jump at least two points and this jump must be less than half the number of corners. So the ten is not arbitrary, but it is no mystery either. It follows from the two, applied twice.

The primes as figures

Theorem 4

For $n \ge 3$ :

\begin{aligned} & n \text{ is prime} \\ \iff\; & \gcd(n, k) = 1 \\ & \text{for all } k \le \lfloor n/2 \rfloor. \end{aligned}

By Theorem 1 this means: $n$ is prime exactly when every figure of its simplex consists of a single part.

Proof

“ $\Rightarrow$ ”: Let $n$ be prime and $1 \le k \le n/2$ . Then $\gcd(n,k)$ divides $n$ , so it is 1 or $n$ . Since $\gcd(n,k) \le k < n$ , it is 1.

“ $\Leftarrow$ ”: Let $n$ not be prime. Then there are $a, b \ge 2$ with $n = ab$ , and without loss of generality $a \le b$ . It follows that $2a \le ab = n$ , so $a \le n/2$ , and $\gcd(n, a) = a \ge 2$ . The condition fails for $k = a$ .

∎

This theorem is the precise form of what the page The order of the primes hints at: primes are the simplexes in which every figure can be drawn in a single stroke. Being divisible only by 1 and itself thus has an exact geometric counterpart.

Checked by computer: the proof in Lean

Here Lean checks two things. First Theorem 4: IsPrime is the usual definition of a prime, OnlyOnePart is the right-hand side of Theorem 4. The theorem prime_iff_onlyOnePart shows that both are the same, with the same two directions as the proof above. Then Theorem 3: kind determines the kind of a figure from the gcd alone, as in the table, and decide makes Lean work through all numbers up to 10. For the statement “no smaller number” that is a complete proof, since there are only finitely many smaller numbers.

/-! Numbers as figures: Theorem 4 and Theorem 3 -/

/-- n is larger than 1 and divisible only by 1 and n. -/
def IsPrime (n : Nat) : Prop :=
  2 ≤ n ∧ ∀ d, d ∣ n → d = 1 ∨ d = n

/-- Every figure n/k with 1 ≤ k ≤ n/2 has only one part,
    by Theorem 1 this means: gcd(n, k) = 1. -/
def OnlyOnePart (n : Nat) : Prop :=
  ∀ k, 1 ≤ k → k ≤ n / 2 → Nat.gcd n k = 1

/-- Theorem 4: The primes are exactly the simplexes
    without a compound figure. -/
theorem prime_iff_onlyOnePart (n : Nat) (h : 3 ≤ n) :
    IsPrime n ↔ OnlyOnePart n := by
  constructor
  · -- n prime: gcd(n, k) divides n, so it is 1 or n.
    -- n is impossible, since n would then divide the smaller k.
    intro ⟨_, hp⟩ k hk1 hk2
    have hg : Nat.gcd n k ∣ n := Nat.gcd_dvd_left n k
    rcases hp _ hg with h1 | hn
    · exact h1
    · have hdiv : n ∣ k := hn ▸ Nat.gcd_dvd_right n k
      have := Nat.le_of_dvd (by omega) hdiv
      omega
  · -- n = d · b with d ≠ 1 and d ≠ n: then d is at most
    -- n/2 and gcd(n, d) = d, so there are several parts.
    intro hf
    refine ⟨by omega, fun d hd => ?_⟩
    obtain ⟨b, hb⟩ := hd
    by_cases h1 : d = 1
    · exact Or.inl h1
    by_cases h2 : d = n
    · exact Or.inr h2
    exfalso
    -- d and b are not 0, and b is not 1
    have hd0 : d ≠ 0 := by
      intro h0
      subst h0
      omega
    have hb0 : b ≠ 0 := by
      intro h0
      subst h0
      omega
    have hb1 : b ≠ 1 := by
      intro h0
      subst h0
      omega
    have hdb : d * 2 ≤ n := by
      have : d * 2 ≤ d * b :=
        Nat.mul_le_mul_left d (by omega)
      omega
    have hg := hf d (by omega) (by omega)
    rw [Nat.gcd_eq_right ⟨b, hb⟩] at hg
    exact h1 hg

/-- The kind of the figure n/k, from the gcd alone (Theorem 1):
    0 polygon, 1 compound polygon, 2 star polygon,
    3 compound star, 4 lines through the centre -/
def kind (n k : Nat) : Nat :=
  if 2 * k = n then 4
  else if k = 1 then 0
  else if Nat.gcd n k = 1 then 2
  else if Nat.gcd n k = k then 1
  else 3

/-- Does kind a occur among n/1 to n/(n/2)?
    Compound polygons count only with area (n/k ≥ 3). -/
def hasKind (n a : Nat) : Bool :=
  (List.range (n / 2 + 1)).any fun k =>
    1 ≤ k && kind n k == a && (a != 1 || 3 * k ≤ n)

def allFour (n : Nat) : Bool :=
  3 ≤ n && hasKind n 0 && hasKind n 1
    && hasKind n 2 && hasKind n 3

/-- Theorem 3: Ten contains all four kinds … -/
theorem ten_all_four : allFour 10 = true := by decide

/-- … and no smaller number does. -/
theorem none_smaller :
    ∀ n, n < 10 → allFour n = false := by
  decide

Try it in the browser at live.lean-lang.org ↗How to read Lean

The exception 12

The page The simplex: the solid form of number says that all composite numbers from ten on contain a compound star, with a single exception, 12. This too can be proven.

Theorem 5

A composite number $n$ contains no compound star exactly when $n \in \{4, 6, 8, 9, 12\}$ .

Proof

Let $q$ be the smallest prime divisor of $n$ and $m = n/q$ . If there is a number $j$ with $2 \le j < m/2$ and $\gcd(m, j) = 1$ , then $k = qj$ is a step size with $\gcd(n, k) = q$ , so with $1 < g < k$ , and $\{n/k\}$ is a compound star. Such a $j$ exists for every $m \ge 5$ except $m = 6$ : for odd $m$ take $j = 2$ , for $m = 2l$ with even $l$ take $j = l - 1$ , with odd $l \ge 5$ take $j = l - 2$ . Both are odd and coprime to $m$ .

What remains is $m \in \{2, 3, 4, 6\}$ . Since $q$ is the smallest prime divisor of $n$ , $q$ is at most the smallest prime divisor of $m$ . This gives $n = 4$ ( $m = 2$ ), $n = 6$ or $9$ ( $m = 3$ ), $n = 8$ ( $m = 4$ ) and $n = 12$ ( $m = 6$ ). For these five numbers, going through all step sizes shows that none gives a compound star.

∎

So 12 is not the last exception by chance: it is $2 \cdot 6$ , and 6 is the only number from 5 on without a single star.

What has been proven and what has not

What is proven: the figures of the simplexes are an exact picture of divisibility. Every statement about gcd and divisors can be translated into a statement about figures and back, and the ten and the primes have a demonstrable special position in it.

What is not proven by this is that these figures reveal anything about the distribution of the primes that one would not know without them. The translation is exact, but it is a translation. Whether looking at the figures opens up new questions or new answers is the question the Number theory section pursues, and there theorem, finding and interpretation have to be told apart each time.

Sources and further reading

Sources

Louis Poinsot, Mémoire sur les polygones et les polyèdres, Journal de l’École polytechnique 10, 1810
H. S. M. Coxeter, Regular Polytopes, 3rd ed. New York 1973

Numbers as figures

What we need

How many parts a figure has

The four kinds follow by themselves

Why ten

The primes as figures

The exception 12

What has been proven and what has not

Sources

Further reading