# Algorithm for finding full representatives of the orbit space of imaginary quadratic numbers of discriminant $D$ under the modular group

Let $\Gamma = SL_2(\mathbb{Z})$. Let $\mathcal{H} = \{z \in \mathbb{C}\ |\ Im(z) > 0\}$ be the upper half plane of complex numbers. 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 polynomial 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 Is there algorithm for finding full representatives of the orbit space $\mathcal{H}(D)/\Gamma$? If yes, what is it?

Remark My motivation for the above question came from this and this. This is a closely related question.

• What's the reason for the downvote? Unless you tell me, I cannot improve the question. – Makoto Kato Nov 20 '13 at 3:43
• I believe that people are slightly annoyed at your use of math.se as a conjecture checker. I understand that technically you are in the right, and I am not even saying I disagree with your practices, but the sheer number of your posts, all of which reference recents posts you have made seem, well, masturbatory. – Alex Youcis Nov 20 '13 at 8:14
• @AlexYoucis If you don't like my questions, please ignore them. But please don't downvote for them if there is nothing wrong with them. There might be people who are interested in them. The downvotes are sending wrong messages to them. – Makoto Kato Nov 20 '13 at 9:00
• I didn't downvote--I'm just telling you a likely reason that people are down voting your questions. – Alex Youcis Nov 20 '13 at 9:47
• @AlexYoucis I wonder why they don't leave me alone. – Makoto Kato Nov 20 '13 at 12:18

We use the 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)$. By this question, $\mathfrak{F}^+_0(D)$ is $\Gamma$-invariant. We denote the set of $\Gamma$-orbits on $\mathfrak{F}^+_0(D)$ by $\mathfrak{F}^+_0(D)/\Gamma$.
Let $f = ax^2 + bxy + cy^2 \in \mathfrak{F}^+_0(D)$. We denote $\phi(f) = (-b + \sqrt{D})/2a$, where $\sqrt{D} = i\sqrt{|D|}$. It is clear that $\phi(f) \in \mathcal{H}(D)$. Hence we get a map $\phi\colon \mathfrak{F}^+_0(D) \rightarrow \mathcal{H}(D)$. By this question, $\phi$ is a bijection and induces a bijection $\mathfrak{F}^+_0(D)/\Gamma \rightarrow \mathcal{H}(D)/\Gamma$. Hence, it suffices to find algorithm to determine full representatives of $\mathfrak{F}^+_0(D)/\Gamma$. For notational convenience, we denote an element $ax^2 + bxy + cy^2$ of $\mathfrak{F}^+_0(D)$ by $(a, b, c)$.
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 \}$. $F$ is a fundamental domain of $\mathcal{H}/\Gamma$, i.e. every point of $\mathcal{H}$ is $\Gamma$-equivalent to a unique point of $F$(e.g. Serre's A Course in Arithmetic or Proposition 1 and Proposition 2 of my answer to this question).
Let $\mathcal{F}(D) = \{(a, b, c) \in \mathfrak{F}^+_0(D)\ |\ |b| \le a \le c$ If $|b| = a$ or $a = c$, then $b \ge 0\}$. It is easy to see that $\phi^{-1}(F) = \mathcal{F}(D)$(see Proposition 3 of my answer to this question). Hence it suffices to determine the set $\mathcal{F}(D)$. This is done in my answer to this question.