Algorithm for determining whether two imaginary quadratic numbers are equivalent under a modular transformation

Question

Let $\Gamma = SL_2(\mathbb{Z})$. Let $\mathcal{H} = \{z \in \mathbb{C}\ |\ \mathcal{Im}(z) > 0\}$ be the upper half complex plane. Let $\sigma = \left( \begin{array}{ccc} p & q \\ r & s \end{array} \right)$ be an element of $\Gamma$. Let $z \in \mathcal{H}$. We write $$\sigma z = \frac{pz + q}{rz + s}$$ It is easy to see that $\sigma z \in \mathcal{H}$ and $\Gamma$ acts on $\mathcal{H}$ from left.

Let $\alpha \in \mathbb{C}$ be an algebraic number. If the minimal plynomial of $\alpha$ over $\mathbb{Q}$ has degree $2$, we say $\alpha$ is a quadratic number. There exists the unique polynomial $ax^2 + bx + c \in \mathbb{Z}[x]$ such that $a > 0$ and gcd$(a, b, c) = 1$. $D = b^2 - 4ac$ is called the discriminant of $\alpha$. Since $D \equiv b^2$ (mod $4$), $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$). Conversly suppose $D$ is a non-square integer such that $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$). Then there exists a quadratic number $\alpha$ whose discriminant is $D$.

Let $D$ be a negative non-square integer such that $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$). We denote by $\mathcal{H}(D)$ the set of quadratic numbers of discriminant $D$ in $\mathcal{H}$. By this question, $\mathcal{H}(D)$ is $\Gamma$-invariant.

My question Let $\alpha, \beta$ be explicitly given elements of $\mathcal{H}(D)$. Is there algorithm for solving the following problems? If yes, what is it?

1. Determine whether there exists $\sigma \in \Gamma$ such that $\alpha = \sigma \beta$.

2. If there exists such $\sigma$, determine the components of the matrix $\sigma$.

Remark My motivation for the above question came from this and this.

Answer 1

We do not need the assumption that $\alpha$ and $\beta$ are quadratic. We can do the test for any two points in the upper half plane.

The crucial concept is the fundamental domain: the region $F$ in which a point $z$ satisfies $-1/2\leq\text{Re}(z)<1/2$ and $|z|>1$ or $|z|=1$ and $\text{Re}(z) \leq 0$. Points in $F$ cannot be mapped onto each other by modular transformations, apart from $z=i$ which can be mapped onto itself. However, the images of $F$ under modular transformations cover the upper half plane. This is a standard construction: http://en.m.wikipedia.org/wiki/Modular_group

A strategy for testing whether two numbers are equal modulo a modular transformation is to map them both into $F$. In the remainder of this answer I will define such a function.

The transformations $z \mapsto z+1$ and $z \mapsto -1/z$ are modular transformations and in fact generate the group. I will show that iterating $z \mapsto g(f(z))$ maps any point into $F$ in a finite number of steps, where:

$$f(z) = z - \lfloor \text{Re}(z)+1/2 \rfloor$$ $$g(z) = z \text{ if } z\in F \text{ else } -1/z$$

Suppose $\text{Im}(z)<1/3$. Let $w=f(z)$. Then $-1/2\leq\text{Re}(w)<1/2$, and the imaginary part is unchanged, so $|w| < \sqrt{13/36}$. Let $z'=g(w)$. Then $\text{Im}(z')>(36/13)\text{Im}(z)$. Therefore, we need to iterate the mapping $z \mapsto z'$ at most $-\log_{36/13}(\text{Im}(z))$ times to ensure $\text{Im}(z) \geq 1/3$.

From this point two further iterations of $z \mapsto g(f(z))$ suffice to map $z$ into $F$, as I will now show.

After $z \mapsto f(z)$, we also know $|\text{Re}(z)| \leq 1/2$. It's then possible that $z \in F$ and we're finished. If not we also know $|z| \leq 1$. Those four bounds describe a shape with four sides: two circles and two straight lines.

After $z \mapsto -1/z$ (the action of $g$ in this case) we have a different shape. The first bound ($\text{Im}(z) \geq 1/3$) maps to $|z-3i/2| \leq 3/2$. That's a circle of radius $3/2$ centred on a point with zero real part. We can weaken it to $|\text{Re}(z)| \leq 3/2$. The second and third bound ($|\text{Re}(z)| \leq 1/2$) map to $|z-1| \geq 1$ and $|z+1| \geq 1$. The fourth bound ($|z| \leq 1$) maps to $|z| \geq 1$.

So now we have a shape with five sides. If you draw it you will see it looks like three copies of $F$ side by side. Applying $f$ maps them all onto the central copy and ensures that $\text{Im}(z) \neq +1/2$. Applying $g$ one last time ensures that if $|z| = 1$ then $\text{Re}(z) \leq 0$.

So for an arbitrary starting point in the upper half plane, we have constructed a modular transformation that maps it into $F$. If we do this for two points, we can see if they map to the same point in $F$. If so, we can map them onto each other, otherwise it is impossible.

Answer 2

Let $F = \{z \in \mathcal{H}\ |\ -1/2 \le Re(z) \lt 1/2, |z| \gt 1$ or $|z| = 1$ and $Re(z) \le 0\}$. It is well-known that any two distincts points of $F$ are not equivalent under the action of $\Gamma$. Let $S = \left( \begin{array}{ccc} 0 & -1 \\ 1 & 0 \end{array} \right)$, $T = \left( \begin{array}{ccc} 1 & 1 \\ 0 & 1 \end{array} \right)$. Let $z \in \mathcal{H}$. We will show that applying $S, T$ or $T^{-1}$ consecutively on $z$, we can map $z$ into $F$. Hence we can find $\sigma \in \Gamma$ such that $\sigma z \in F$. We consider the following algorithm.

Algorithm 1

1. $z = T^{-\lfloor \text{Re}(z)+1/2 \rfloor}(z)$, where $\lfloor a \rfloor$ denotes the greatest integer $n$ such that $n \le a$.

2. If $|z| \gt 1$, then stop. If $|z| \lt 0$, then $z = S(z)$ and go to 1. If $|z| = 1$, then go to 3.

3. If $-1/2 \le Re(z) \le 0$, then stop. If $0 \lt Re(z) \lt 1/2$, then $z = S(z)$ and stop.

If the algorithm terminates, then $z \in F$. We will prove that it terminates in finite steps.

Lemma 1 $S(\{z \in \mathcal{H}\ |\ Im(z) \ge 1/3\}) = \{z \in \mathcal{H}\ |\ |z - 3i/2| \le 3/2\}$.

Proof: Let $w = -1/z$. Then $z = -1/w$. Since $Im(z) = (z - \bar z)/2i$, $Im(z) = (-1/w + 1/\bar w)/2i$. Hence $(-\bar w + w)/2i \ge w\bar w/3 = |w|^2/3$. Let $w = x + yi$. Then $y \ge (x^2 + y^2)/3$. Hence $x^2 + y^2 - 3y \le 0$. Hence $x^2 + (y - 3/2)^2 \le (3/2)^2$. QED

Lemma 2 $S(\{z \in \mathcal{H}\ |\ Re(z) \lt 1/2\}) = \{z \in \mathcal{H}\ |\ |z + 1| \gt 1\}$.

Proof: Let $w = -1/z$. Then $z = -1/w$. Since $Re(z) = (z + \bar z)/2$, $Re(z) \lt 1/2$ implies $-1/w - 1/\bar w \lt 1$. Hence $-\bar w - w \lt |w|^2$. Let $w = x + yi$. Then $-2x \lt x^2 + y^2$. Hence $(x + 1)^2 + y^2 \gt 1$. QED

Lemma 3 $S(\{z \in \mathcal{H}\ |\ Re(z) \ge -1/2\}) = \{z \in \mathcal{H}\ |\ |z - 1| \ge 1\}$.

Proof: Let $w = -1/z$. Then $z = -1/w$. Since $Re(z) = (z + \bar z)/2$, $Re(z) \ge -1/2$ implies $-1/w - 1/\bar w \ge -1$. Hence $\bar w + w \le |w|^2$. Let $w = x + yi$. Then $2x \le x^2 + y^2$. Hence $(x - 1)^2 + y^2 \ge 1$. QED

Proposition 1 The algorithm terminates in finite steps.

Proof(based on the idea of apt1002):

Suppose $Im(z) \lt 1/3$ in the first place. After executing step 1, $-1/2 \le Re(z) \lt 1/2$. Hence $|z|^2 \lt 1/4 + 1/9 = 13/36$. Then $Im(S(z)) = Im(z)/|z|^2 \gt (36/13)Im(z)$. Since $\text{lim}_{n\rightarrow \infty} (36/13)^nIm(z) = \infty$, after executing finite steps, the algorithm terminates or $Im(z) \ge 1/3$. Hence we may suppose $Im(z) \ge 1/3$ in the first place.

After executing step 1, if $|z| \ge 1$, the algorithm terminates. Hence we may suppose $|z| \lt 1$. Let $w = -1/z$. Then $|w| \gt 1$. By Lemma 1, Lemma 2 and Lemma 3, $|Re(w)| \le 3/2, |w + 1| \gt 1, |w - 1| \ge 1$.

Case 1: $-3/2 \le Re(w) \lt -1/2$

Let $z = T^{-\lfloor \text{Re}(w)+1/2 \rfloor}(w) = w + 1$. Then $-1/2 \le Re(z) \lt 1/2$. Since $|z| \gt 1$, the algorithm terminates.

Case 2: $-1/2 \le Re(w) \lt 1/2$

Since $|w| \gt 1$, the algorithm terminates.

Case 3: $1/2 \le Re(w) \lt 3/2$

Let $z = T^{-\lfloor \text{Re}(w)+1/2 \rfloor}(w) = w - 1$. Then $-1/2 \le Re(z) \lt 1/2$. Since $|z| \ge 1$, the algorithm terminates.

Case 4: $Re(w) = 3/2$

Let $z = T^{-\lfloor \text{Re}(w)+1/2 \rfloor}(w) = w - 2$. Then $Re(z) = -1/2$. Since $Im(z) = Im(w) \ge \sqrt 3/2$, $|z| \ge 1$. Hence the algorithm terminates. QED

Answer 3

Let $F = \{z \in \mathcal{H}\ |\ -1/2 \le Re(z) \lt 1/2, |z| \gt 1$ or $|z| = 1$ and $Re(z) \le 0\}$. The method of apt1002 uses the fact that any two distinct points of $F$ are not equivalent under the action of $\Gamma$. This is well-known, but I will prove it for the readers' convenience.

Lemma 1 $Im(z) \ge \sqrt 3/2$ for $z \in F$.

Proof: Let $z = x + yi$. Clearly $Im(z)$ takes minimum value $y$ at $x = -1/2$, where $x^2 + y^2 = 1$. Namely $y = \sqrt {1 - 1/4} = \sqrt 3/2$. QED

Lemma 2 Let $z \in F$. Let $d$ be an integer such that $|z + d| \le 1$. Then $d = 0$ or $1$. If $d = 0$, then $|z| = 1$. If $d = 1$, then $z = (-1 + i\sqrt{-3})/2$.

Proof: Let $z = x + yi$. Since $|z + d|^2 \le 1, (x + d)^2 + y^2 \le 1$. Hence $x^2 + 2dx + d^2 + y^2 \le 1$. Hence $2dx + d^2 \le 1 - (x^2 + y^2) \le 0$. We claim that $d \ge 0$. Suppose otherwise. Then $2x + d \ge 0$. Hence $-1 \lt -2x \le d$. This is a contradiction. Hence $d \ge 0$. Then $2x + d \le 0$. Hence $0 \le d \le -2x \le 1$. Hence $d = 0$ or $1$.

If $d = 0$, then $|z| = 1$.

Suppose $d = 1$. Then $2x + 1 \le 0$. Hence $x \le -1/2$. Hence $x = -1/2$. Since $(x + 1)^2 + y^2 \le 1$, $1/4 + y^2 \le 1$. Hence $y \le \sqrt 3/2$. By Lemma 1, $y = \sqrt 3/2$. Hence $z = (-1 + i\sqrt{-3})/2$. QED

Proposition 2 Let $F = \{z \in \mathcal{H}\ |\ -1/2 \le Re(z) \lt 1/2, |z| \gt 1$ or $|z| = 1$ and $Re(z) \le 0\}$ (1) Any two distinct points of $F$ are not equivalent under the action of $\Gamma$.

(2) Let $\Gamma_z = \{\sigma \in \Gamma\ |\ \sigma z = z\}$. Let $S = \left( \begin{array}{ccc} 0 & -1 \\ 1 & 0 \end{array} \right)$, $T = \left( \begin{array}{ccc} 1 & 1 \\ 0 & 1 \end{array} \right)$. Let $\rho = (-1 + i\sqrt{-3})/2 = exp(2\pi i/3)$.

If $z \ne i, \rho, \Gamma_z = \{\pm1\}$.

If $z = i, \Gamma_z = \{\pm 1, \pm S\}$.

If $z = \rho, \Gamma_z = \{\pm 1, \pm ST, \pm (ST)^2\}$.

Proof: Let $z, w \in F$. Suppose there exists $\sigma = \left( \begin{array}{ccc} a & b \\ c & d \end{array} \right) \in \Gamma$ such that $w = \sigma z$. We claim that $z = w$. We may assume that $Im(w) \ge Im(z)$ without loss of generality. Since $Im(w) = Im(z)/|cz + d|^2, |cz + d| \le 1$. Hence $|Im(cz + d)| = |c y| \le 1$, where $z = x + yi$. By Lemma 1, $y \ge \sqrt 3/2$. Hence $(\sqrt 3/2)|c| \le 1$. Hence $|c| \le 2/\sqrt 3$. Hence $c = 0$ or $\pm 1$.

Case 1: $c = 0$

Since $ad - bc = 1$, $a = d = \pm 1$. Hence $w = z \pm b$. Since $z, w \in F$, $b = 0$. In this case, $\sigma = \pm\left( \begin{array}{ccc} 1 & 0 \\ 0 & 1 \end{array} \right)$.

Case 2: $c = \pm 1$

Since $\sigma z = -\sigma z$, we may assume without loss of generality $c = 1$. Then $|z + d| \le 1$. By Lemma 2, $d = 0$ or $1$. If $d = 0$, then $|z| = 1$. If $d = 1$, then $z = (-1 + i\sqrt{-3})/2$.

Suppose $d = 0$. Since $ad - bc = 1$ and $c = 1$, $b = -1$. Hence $w = a - 1/z$. Since $|z| = 1$ and $-1/2 \le Re(z) \le 0$, $0 \le Re(-1/z) \le 1/2$. Hence $a = 0$ or $a = -1$. If $a = 0$, $z = w = i$. In this case, $\sigma = \left( \begin{array}{ccc} 0 & -1 \\ 1 & 0 \end{array} \right) = S$.

If $a = -1$, $z = (-1 + i\sqrt 3)/2$. Since $z^2 + z + 1 = 0$, $w = -1 - 1/z = (-z - 1)/z = z^2/z = z$. In this case, $\sigma = \left( \begin{array}{ccc} -1 & -1 \\ 1 & 0 \end{array} \right) = (ST)^2$.

Suppose $d = 1$. Since $ad - bc = 1$ and $c = 1$, $a - b = 1$. Hence $w = ((b + 1)z + b)/(z + 1) = b + z/(z + 1) = b - z/z^2 = b - 1/z$. Since $w \in F$, $b = -1$. Hence $w = (-z - 1)/z = z^2/z = z$. In this case, $\sigma = \left( \begin{array}{ccc} 0 & -1 \\ 1 & 1 \end{array} \right) = ST$.

This completes the proof. QED

Remark Let $z, w \in \mathcal{H}$. Suppose $w = \sigma z$ and $w = \tau z$ for $\sigma, \tau \in \Gamma$. Then $\sigma z = \tau z$. Hence $\sigma^{-1}\tau z = z$. Hence $\sigma^{-1}\tau \in \Gamma_z$. Hence $\tau \in \sigma\Gamma_z$. By proposition 2, we know $\Gamma_z$ explicitly. Therefore, together with apt1002's method, we can determine the set $\{\sigma \in \Gamma \ |\ w = \sigma z\}$ for given $z, w \in \mathcal{H}$.

Answer 4

Let us apply the method of apt1002 to the OP's problem. We use the definitions and notation of this question. Let $D$ be a negative non-square integer such that $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$). We denote the set of positive definite primitive binary quadratic forms of discriminant $D$ by $\mathfrak{F}^+_0(D)$. For notational convenience, we denote an element $ax^2 + bxy + cy^2$ of $\mathfrak{F}^+_0(D)$ by $(a, b, c)$. We define a map $\phi\colon \mathfrak{F}^+_0(D) \rightarrow \mathcal{H}(D)$ by $\phi((a,b,c)) = (-b + \sqrt D)/2a$. By the question, $\phi$ is a bijection and $\phi(f^\sigma) = \sigma^{-1}\phi(f)$ for $f \in \mathfrak{F}^+_0(D),\ \sigma \in \Gamma$. We denote $f^{\sigma^{-1}}$ by $\sigma f$. Thus $\Gamma$ acts on $\mathfrak{F}^+_0(D)$ from left. Then $\phi$ is an isomorphism between the $\Gamma$-sets. Therefore it suffices to solve the corresponding problem in $\mathfrak{F}^+_0(D)$.

We denote $\phi((a,b,c))$ by $\phi(a,b,c)$ by abuse of notation.

Let $S = \left( \begin{array}{ccc} 0 & -1 \\ 1 & 0 \end{array} \right)$, $T = \left( \begin{array}{ccc} 1 & 1 \\ 0 & 1 \end{array} \right)$.

It is easy to see that $S\phi(a,b,c) = \phi(c, -b, a)$, $T^{-n}\phi(a,b,c) = \phi(a, 2an + b, an^2 + bn + c)$ for $n \in \mathbb{Z}$.

Let $F = \{z \in \mathcal{H}\ |\ -1/2 \le Re(z) \lt 1/2, |z| \gt 1$ or $|z| = 1$ and $Re(z) \le 0\}$.

Proposition 3 Let $(a,b,c) \in \mathfrak{F}^+_0(D)$. The necessary and sufficient conditions for $\phi(a,b,c) \in F$ are as follows.

1. $|b| \le a \le c$.

2. If $|b| = a$ or $a = c$, then $b \ge 0$.

Proof: Since $Re(\phi(a,b,c)) = -b/2a, -1/2 \le -b/2a \lt 1/2$. Hence $-a \le -b \lt a$. Hence $|b| \le a$. If $|b| = a$, $a = b$.

Since $|\phi(a,b,c)|^2 = (b^2 - D)/4a^2 = 4ac/4a^2 = c/a \ge 1, a \le c$. If $|\phi(a,b,c)| = 1$, i.e. $a = c$, then $-1/2 \le -b/2a \le 0$. Hence $-a \le -b \le 0$. Hence $a \ge b \ge 0$. QED

We denote the set of $(a, b, c)$ which satisfies the conditions of Proposition 3 by $\mathcal{F}(D)$. $\mathcal{F}(D)$ is a finite set as shown in my answer to this question.

Let $(a,b,c) \in \mathfrak{F}^+_0(D)$. We consider the following algorithm.

Algorithm 2

1. If $-a \le -b \lt a$, go to 2. If not, set $(a,b,c) = (a, 2an + b, an^2 + bn + c)$, where $n = \lfloor -b/2a +1/2 \rfloor$.

2. If $a \lt c$, then stop. If $a = c$, go to 3. If $a \gt c$, set $(a,b,c) = (c, -b, a)$ and go to 1.

3. If $b \ge 0$, stop. Otherwise set $(a,b,c) = (c, -b, a)$ and stop.

Proposition 4 The algorithm terminates in finite steps. Moreover when it terminates, $(a, b, c) \in \mathcal{F}(D)$.

Proof: This follows immediately from Proposition 1. However, we will prove it directly. If $|b| \gt a$ or $-b = a$, by executing step 1, $b$ satisfies $-a \le -b \lt a$, hence $|b| \le a$.Hence $|b|$ decreases at least by $1$. If $-b = a$, by executing step 1, $b = a$. Hence |b| does not change.

In step 2, the algorithm terminates or $|b|$ does not change and $a$ decreases and it goes to step 1. Hence the algorithm must terminate in finite steps. QED

Proposition 5 (1) Any two distinct forms of $\mathcal{F}(D)$ are not equivalent under the action of $\Gamma$.

(2) Let $\Gamma_f = \{\sigma \in \Gamma\ |\ \sigma f = f\}$ for $f \in \mathcal{F}(D)$. Let $S = \left( \begin{array}{ccc} 0 & -1 \\ 1 & 0 \end{array} \right)$, $T = \left( \begin{array}{ccc} 1 & 1 \\ 0 & 1 \end{array} \right)$.

If $D \ne -4, -3$, then $\Gamma_f = \{\pm1\}$ for every $f \in \mathcal{F}(D)$. Let $g = x^2 + y^2$. Let $h = x^2 + xy + y^2$. $\mathcal{F}(-4) = \{g\}$. $\mathcal{F}(-3) = \{h\}$.

$\Gamma_g = \{\pm 1, \pm S\}$.

$\Gamma_h = \{\pm 1, \pm ST, \pm (ST)^2\}$.

Proof: This follows immediately from Proposition 2 except $\mathcal{F}(-4) = \{g\}$, $\mathcal{F}(-3) = \{h\}$.But this is easy to see by the method of my answer to this question.

Answer 5

Algorithm 1 can be simplified as follows. Let $[F]$ be the closure of $F$, i.e. $[F] = \{z \in \mathcal{H}\ |\ |Re(z)| \le 1/2, |z| \ge 1 \}$. Then $[F] - F = \{z \in \mathcal{H}\ |\ Re(z) = 1/2$ or $|z| = 1$ and $0 \lt Re(z) \lt 1/2 \}$. Let $z \in [F] - F$. If $Re(z) = 1/2$, then $T^{-1}(z) \in F$. If $|z| = 1$ and $0 \lt Re(z) \lt 1/2$, then $S(z) \in F$. Hence the following algorithm which transforms any element $z \in \mathcal{H}$ into $[F]$ will do.

Algorithm 1a

1. If $|Re(z)| \le 1/2$, then go to 2. Otherwise set $z = T^{-\lfloor \text{Re}(z)+1/2 \rfloor}(z)$.

2. If $|z| \ge 1$, then stop. Otherwise set $z = S(z)$ and go to 1.

Similarly Algorithm 2 can be simplified as follows. We denote the set $\{(a,b,c) \in \mathfrak{F}^+_0(D)\ |\ |b| \le a \le c\}$ by $[\mathcal{F}(D)]$. Let $(a,b,c) \in \mathfrak{F}^+_0(D)$. Suppose $|b| = a$ and $b \lt 0$. i.e. $-b = a$. Then $T^{-1}(a,b,c) = (a, 2a + b, a + b + c) = (a, a, c) \in \mathcal{F}(D)$. Suppose $a = c$ and $b \lt 0$. Then $S(a, b, c) = (a, -b, a) \in \mathcal{F}(D)$. Hence the following algorithm which transforms any element $(a,b,c) \in \mathfrak{F}^+_0(D)$ into $[\mathcal{F}(D)]$ will do.

Algorithm 2a

1. If $|b| \le a$ go to 2. Otherwise set $(a,b,c) = T^{-n}(a, b, c)$, where $n = \lfloor -b/2a +1/2 \rfloor$.

2. If $a \le c$, then stop. Otherwise set $(a,b,c) = S(a, b, c)$ and go to 1.