# 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()