1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It is necessary and sufficient to find an algorithm for mapping any element of the upper half plane into the fundamental domain. $\endgroup$ – apt1002 Nov 19 '13 at 0:47
  • $\begingroup$ Does this algorithm work (if you fix the edge cases)? 1. Map $z$ onto $z-\text{round}(\text{Re}(z))$. 2. If $|z|<1$, map $z$ onto $-1/z$ and goto 1. $\endgroup$ – apt1002 Nov 19 '13 at 0:59
  • $\begingroup$ @apt1002 We need to prove it terminates. $\endgroup$ – Makoto Kato Nov 19 '13 at 1:36
  • $\begingroup$ Indeed. Can we assume that for all admissable $z$ a matrix exists with finite elements? If so I think we could prove termination. $\endgroup$ – apt1002 Nov 19 '13 at 1:44
  • $\begingroup$ @apt1002 I don't know what you mean by a matrix for an admissable $z$. We can assume that $\alpha$ is a root of a quadratic equation $ax^2 + bx + c$ of discriminant $D$, where $a \gt 0$, gcd$(a, b, c) = 1$. Similarly for $\beta$. $\endgroup$ – Makoto Kato Nov 19 '13 at 1:57
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you tel me what $\lfloor z \rfloor$ means? $\endgroup$ – Makoto Kato Nov 19 '13 at 11:09
  • $\begingroup$ Sorry, that was a typo. I'll edit that. $\endgroup$ – apt1002 Nov 19 '13 at 16:24
  • $\begingroup$ I have made some other corrections and clarifications too. I was a bit rushed when I first wrote the answer, sorry. $\endgroup$ – apt1002 Nov 19 '13 at 16:37
  • $\begingroup$ [For all other points $z$, $g(f(g(f(z))))\in F$, so two further iterations suffice.] I'm afraid I don't understand this. Could you elaborate? $\endgroup$ – Makoto Kato Nov 20 '13 at 7:28
  • $\begingroup$ Sure. "other points $z$" means those with $\text{Im}(z)>=1/\sqrt{12}$. After applying $f$, we have in addition $-1/2\leq\text{Re}(z)<1/2$. If at that point we still do not have $z\in F$, then we also have $|z|\leq 1$. After $z\mapsto -1/z$, each of these bounds gives us a bound on the new $z$. Specifically, we have $|z-n|\geq1$ for $n\in\{-1,0,1\}$ and $|z-i\sqrt{3}|\leq\sqrt{3}$. From these we can deduce $|\text{Re}(z)|\leq 3/2$. Applying $f$ again and then $g$ again maps it into $F$ with all the edge cases fixed. $\endgroup$ – apt1002 Nov 20 '13 at 9:26
-1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ "to the OP's problem" is a strange way of saying "to my own question". This appears to be your third answer to this particular question that you asked. I believe that this sort of thing should go on your blog or some other personal website, not on math.SE. $\endgroup$ – Carl Mummert Dec 3 '13 at 0:30
  • $\begingroup$ @CarlMummert [I believe that this sort of thing should go on your blog or some other personal website, not on math.SE.] Could you explain why you believe so? $\endgroup$ – Makoto Kato Dec 3 '13 at 0:44
-1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

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

| cite | improve this answer | |
$\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.