Analysis

In this part we perform a mathematical analysis of the family of curves we found previously.

Definitions

Let \(p \in \mathbb N, p > 0\) and \(q \in \mathbb N, q > 0\). Let \(d = \gcd(p, q)\), \(p' = \frac{p}{d}\) and \(q' = \frac{q}{d}\). Let \(r \in \mathbb R\) and \(\delta_r \in \mathbb R\) such that \(0 < \delta_r < r\). Let’s define the following family of functions:

\[ \begin{align}\begin{aligned}r_k : \theta \mapsto r + \delta_r \cdot \cos\left(\frac{p \cdot \theta - 2 \cdot k \cdot \pi}{q}\right)\\k \in \mathbb Z\end{aligned}\end{align} \]

Let \(\Gamma_k\) be the graph of \(r_k\) in polar coordinates, that is the graph of \(\vec{r_k} : \theta \mapsto r_k(\theta) \cdot \vec u(\theta)\) where \(\vec u(\theta)\) is the unit vector at polar angle \(\theta\).

Intersections

For \((m, n) \in \mathbb Z^2\), \(\Gamma_m\) and \(\Gamma_n\) intersect if and only if \(\exists \theta_1, \theta_2 \in \mathbb R^2, \vec{r_m}(\theta_1) = \vec{r_n}(\theta_2)\).

\[\begin{split}\begin{array}{rcl} \vec{r_m}(\theta_1) = \vec{r_n}(\theta_2) & \iff & r_m(\theta_1) \cdot \vec u(\theta_1) = r_n(\theta_2) \cdot \vec u(\theta_2) \\ & \iff & \left| \begin{array}{l} \left\{ \begin{array}{l} \vec u(\theta_1) = \vec u(\theta_2) \\ r_m(\theta_1) = r_n(\theta_2) \end{array} \right. \\ \mbox{or} \\ \left\{ \begin{array}{l} \vec u(\theta_1) = -\vec u(\theta_2) \\ r_m(\theta_1) = -r_n(\theta_2) \end{array} \right. \end{array} \right. \end{array}\end{split}\]

\(0 < \delta_r < r\) and \(\cos\) is between \(-1\) and \(1\) so \(r_k(\theta) > 0\) and we can drop the second case.

\[\begin{split}\begin{array}{rcl} \vec{r_m}(\theta_1) = \vec{r_n}(\theta_2) & \iff & \left\{ \begin{array}{l} \vec u(\theta_1) = \vec u(\theta_2) \\ r_m(\theta_1) = r_n(\theta_2) \end{array} \right. \\ & \iff & \left\{ \begin{array}{l} \vec u(\theta_1) = \vec u(\theta_2) \\ \cos\left(\frac{p \cdot \theta_1 - 2 \cdot m \cdot \pi}{q}\right) = \cos\left(\frac{p \cdot \theta_2 - 2 \cdot n \cdot \pi}{q}\right) \end{array} \right. \end{array}\end{split}\]

\(\vec u\) is \(2 \pi \mbox{-periodic}\) and \(\cos\) is even and \(2 \pi \mbox{-periodic}\) so:

\[\begin{split}\begin{array}{rcl} \vec{r_m}(\theta_1) = \vec{r_n}(\theta_2) & \iff & \left\{ \begin{array}{l} \exists a \in \mathbb Z, \theta_2 = \theta_1 + 2 \cdot a \cdot \pi \\ \exists b \in \mathbb Z, \left| \begin{array}{l} \frac{p \cdot \theta_1 - 2 \cdot m \cdot \pi}{q} = 2 \cdot b \cdot \pi + \frac{p \cdot \theta_2 - 2 \cdot n \cdot \pi}{q} \\ \mbox{or} \\ \frac{p \cdot \theta_1 - 2 \cdot m \cdot \pi}{q} = 2 \cdot b \cdot \pi - \frac{p \cdot \theta_2 - 2 \cdot n \cdot \pi}{q} \end{array} \right. \end{array} \right. \\ & \iff & \left| \begin{array}{l} \exists (a, b) \in \mathbb Z^2, \left\{ \begin{array}{l} \theta_2 = \theta_1 + 2 \cdot a \cdot \pi \\ \frac{p \cdot \theta_1 - 2 \cdot m \cdot \pi}{q} = 2 \cdot b \cdot \pi + \frac{p \cdot \theta_2 - 2 \cdot n \cdot \pi}{q} \end{array}\right. \qquad \mbox{Case 1} \\ \mbox{or} \\ \exists (a, b) \in \mathbb Z^2, \left\{ \begin{array}{l} \theta_2 = \theta_1 + 2 \cdot a \cdot \pi \\ \frac{p \cdot \theta_1 - 2 \cdot m \cdot \pi}{q} = 2 \cdot b \cdot \pi - \frac{p \cdot \theta_2 - 2 \cdot n \cdot \pi}{q} \end{array}\right. \qquad \mbox{Case 2} \end{array} \right. \end{array}\end{split}\]

Case 1

\[\begin{split}\begin{array}{cl} & \exists (a, b) \in \mathbb Z^2, \left\{ \begin{array}{l} \theta_2 = \theta_1 + 2 \cdot a \cdot \pi \\ \frac{p \cdot \theta_1 - 2 \cdot m \cdot \pi}{q} = 2 \cdot b \cdot \pi + \frac{p \cdot \theta_2 - 2 \cdot n \cdot \pi}{q} \end{array}\right. \\ \iff & \exists (a, b) \in \mathbb Z^2, \left\{ \begin{array}{l} \theta_2 = \theta_1 + 2 \cdot a \cdot \pi \\ n - m = a \cdot p + b \cdot q \end{array}\right. \end{array}\end{split}\]

So if we can find \(a\) and \(b\) such that \(n - m = a \cdot p + b \cdot q\), then \(\Gamma_m\) and \(\Gamma_n\) have an infinite number of intersection points and are identical.

According to Bézout’s identity, \(\exists (a, b) \in \mathbb Z, n - m = a \cdot p + b \cdot q\) if and only if \(n - m\) is a multiple of \(d\).

Reduction of the family

Applying this to \(n = m + d\) proves that \(\Gamma_{n + d}\) is identical to \(\Gamma_n\). It’s sufficient to consider intersections between \(\Gamma_m\) and \(\Gamma_n\) for \((m, n) \in [0, d-1]^2\) and \(m \le n\). And it’s enough to draw \(\Gamma_k\) for \(k \in [0, d-1]\).

Periodicity of \(r_k\)

By construction, \(r_k\) is \(2 \cdot q \cdot \pi \mbox{-periodic}\).

For \(m = n\), we can use \(a = q'\) and \(b = -p'\). Then we have \(\theta_2 = \theta_1 + 2 \cdot q' \cdot \pi\). So \(r_k\) is \(2 \cdot q' \cdot \pi \mbox{-periodic}\). It’s sufficient to consider intersections where \((\theta_1, \theta_2) \in \left[0, 2 \cdot q' \cdot \pi\right[^2\). And it’s enough to draw each \(\Gamma_k\) on \(\theta \in \left[0, 2 \cdot q' \cdot \pi\right[\).

Case 2

\[\begin{split}\begin{array}{cl} & \exists (a, b) \in \mathbb Z^2, \left\{ \begin{array}{l} \theta_2 = \theta_1 + 2 \cdot a \cdot \pi \\ \frac{p \cdot \theta_1 - 2 \cdot m \cdot \pi}{q} = 2 \cdot b \cdot \pi - \frac{p \cdot \theta_2 - 2 \cdot n \cdot \pi}{q} \end{array}\right. \\ \iff & \exists (a, b) \in \mathbb Z^2, \left\{ \begin{array}{l} \theta_1 = \frac{b \cdot q - a \cdot p + m + n}{p} \cdot \pi \\ \theta_2 = \frac{b \cdot q + a \cdot p + m + n}{p} \cdot \pi \end{array}\right. \end{array}\end{split}\]

So this case correspond to “real”, individual intersection points.

Let’s reduce the domain we need to search for \(a\) and \(b\). So far, we have:

\[ \begin{align}\begin{aligned}0 \le k \lt d\\0 \le \theta_1 \lt 2 \cdot q' \cdot \pi\\0 \le \theta_2 \lt 2 \cdot q' \cdot \pi\\\theta_1 = \frac{b \cdot q - a \cdot p + 2 \cdot k}{p} \cdot \pi\\\theta_2 = \frac{b \cdot q + a \cdot p + 2 \cdot k}{p} \cdot \pi\end{aligned}\end{align} \]

Replacing \(\theta_1\) and \(\theta_2\) in \(-2 \cdot q' \cdot \pi \lt \theta_2 - \theta_1 \lt 2 \cdot q' \cdot \pi\) and isolating \(a\), we obtain \(-q' + 1 \le a \lt q'\).

Then, replacing \(\theta_1\) and \(\theta_2\) in \(0 \le \theta_1 \lt 2 \cdot q' \cdot \pi\) and \(0 \le \theta_2 \lt 2 \cdot q' \cdot \pi\) and isolating b, we obtain:

\[ \begin{align}\begin{aligned}\frac{a \cdot p - m - n}{q} \le b \lt 2 \cdot p' - \frac{-a \cdot p + m + n}{q}\\\frac{-a \cdot p - m - n}{q} \le b \lt 2 \cdot p' - \frac{a \cdot p + m + n}{q}\end{aligned}\end{align} \]

We can regroup those two conditions in:

\[\frac{|a| \cdot p - m - n}{q} \le b \lt 2 \cdot p' - \frac{|a| \cdot p + m + n}{q}\]

So to obtain all intersections, it’s enough to iterate on \(a\) and \(b\) in those ranges. Note that if \(m = n\), this will give us each intersection twice. We can consider only the cases where \(\theta_1 \lt \theta_2\), which reduces the range of \(a\) to \(1 \le a \lt q'\).

This is just a necessary condition on \(a\) and \(b\). We have proven that we obtain all intersections, but @todoc we might want to prove that we don’t get duplicates.

import fractions
import math
import matplotlib.pyplot as plt
import numpy as np

P = 7
Q = 8

plt.figure(figsize=(P, Q))

for p in range(1, P + 1):
  for q in range(1, Q + 1):
    d = fractions.gcd(p, q)
    p_prime = p / d
    q_prime = q / d

    r = []
    for k in range(d):
      r.append(
        lambda theta, k=k: 2 + np.cos((p * theta - 2 * k * np.pi) / q)
      )
    theta = np.arange(0, 2 * q_prime * np.pi, 0.01)

    intersections = []
    # Note that these 4 imbricated loops are only O(p*q)
    for m in range(d):
      for n in range(m, d):
        if m == n:
            min_a = 1
        else:
            min_a = -q_prime + 1
        max_a = q_prime
        for a in range(min_a, max_a):
          min_b = int(math.ceil(float(abs(a) * p - m - n) / q))
          max_b = 2 * p_prime - int(math.floor(float(abs(a) * p + m + n) / q))
          for b in range(min_b, max_b):
            theta_1 = (b * q - a * p + m + n) * np.pi / p
            theta_2 = (b * q + a * p + m + n) * np.pi / p
            assert 0 <= theta_1 < 2 * q_prime * np.pi
            assert 0 <= theta_2 < 2 * q_prime * np.pi
            assert m != n or theta_1 < theta_2
            intersections.append((theta_1, r[m](theta_1)))
    assert len(intersections) == p * (q - 1)  # @todoc Explain

    sp = plt.subplot(Q, P, (q - 1) * P + p, polar=True)
    for k in range(d):
      sp.plot(theta, r[k](theta))
    sp.plot(
      [theta for theta, r in intersections],
      [r for theta, r in intersections],
      "r."
    )
    sp.set_rmin(0)
    sp.set_rmax(3.1)
    sp.set_yticks([1, 2, 3])
    sp.set_yticklabels([])
    sp.set_xticklabels([])
    sp.spines['polar'].set_visible(False)

plt.tight_layout()