10
$\begingroup$

Let the class number $h(d)$ denote the number of distinct binary quadratic forms with discriminant $d < 0$.

Is there a better algorithm for $h$ than brute force?

To be precise, by brute force I meant to generate enough forms to completely cover the space and then reducing them down to see how many equivalence classes there are.

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Class_number_formula $\endgroup$ – Qiaochu Yuan Aug 21 '10 at 22:35
  • $\begingroup$ @Qiaochu, is the class number formula actually used to compute in practice? $\endgroup$ – Mariano Suárez-Álvarez Aug 21 '10 at 22:50
  • $\begingroup$ @Mariano, no idea. My guess is it is only practical for small discriminants, but I thought the OP would want to know it exists. $\endgroup$ – Qiaochu Yuan Aug 21 '10 at 23:07
11
$\begingroup$

Yes, there are algorithms that are much better than brute force. For example, see section 5.4 in Henri Cohen's book "A course in computational algebraic number theory" for Shanks's baby-step giant-step algorithm $O(|D|^{1/4+\epsilon})$ - which is practical for negative discriminants $D$ up to 25 digits or more and, further, McCurley's sub-exponential algorithm (including Atkin's variant) which is $O(L(|D|)^\alpha)$ for $\alpha = \sqrt 2 \;$ or perhaps even $\alpha = \sqrt{9/8},$ where $\; L(x) = e^{\sqrt {\ln x \ln\ln x}}$. This can handle $D$ up to 50 digits or more (nowadays, with various improvements, probably around 80 digits or more - the prior numbers are quoted from the 1993 edition of Cohen's book - currently the bible for computational algebraic number theory).

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ And if you can read French and C, then his Pari/GP software is a very useful and up-to-date "appendix" with (usually) very efficient and easy to read implementations of those algorithms. $\endgroup$ – Jack Schmidt Aug 21 '10 at 23:02
  • 2
    $\begingroup$ You don't need to know much French to grok the code. But it's a good idea to read the code simply to avoid bugs - e.g. doing so I found a major bug in integer division in 1994 around the same time Nicely found the Pentium FDIV bug, see loria.fr/~zimmerma/talks/henri.pdf#page=69 $\endgroup$ – Gone Aug 21 '10 at 23:12
5
$\begingroup$

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$). Let $\Gamma = SL_2(\mathbb{Z})$. 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 $h(D) = |\mathfrak{F}^+_0(D)/\Gamma|$.

Let $\mathcal{H} = \{z \in \mathbb{C}; Im(z) > 0\}$. 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. We denote the set of $\Gamma$-orbits on $\mathcal{H}(D)$ by $\mathcal{H}(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, computing $h(D)$ is the same as computing $|\mathcal{H}(D)/\Gamma|$.

Let $G = \{ 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 known that $G$ is a fundamental domain of $\mathcal{H}/\Gamma$(e.g. Serre's A Course in Arithmetic).

Hence it suffices to count the number of $f \in \mathfrak{F}^+_0(D)$ such that $\phi(f) \in G$. Let $f = ax^2 + bxy + cy^2$. Then $\phi(f) \in G$ if and only if $|b| \le a \le c$(if $|b| = a$ or $a = c, b \ge 0)$. Hence it suffices to count the number of $(a, b, c)$ which satisfies the following conditions.

  1. $a \gt 0$.
  2. gcd$(a, b, c) = 1$.
  3. $D = b^2 - 4ac$.
  4. $|b| \le a \le c$, if $|b| = a$ or $a = c, b \ge 0$.

The following observation suffices to determine $(a, b, c)$.

Since $D = b^2 - 4ac, 4ac = b^2 + |D|$. Hence $c = (b^2 + |D|)/4a$. Hence it suffices to determine $a$ and $b$.

Since $a \le c$, $a \le (b^2 + |D|)/4a$. Hence $4a^2 \le b^2 + |D| \le a^2 + |D|$. Hence $3a^2 \le |D|$. Hence $a^2 \le |D|/3$. Hence $a \le \sqrt{|D|/3}$.

As an example, we compute $h(D)$ when $D = -584 = -2^3\cdot73$ by our method. This is the class number of $\mathbb{Q}(\sqrt {-146})$.

$a \le \sqrt{|D|/3} = \sqrt{\frac{584}{3}} = 13.95\cdots$. Hence $1 \le a \le 13$.

$4ac = b^2 + |D| = b^2 + 584$. Hence $b^2 \equiv 0$ (mod $2$). Hence $b$ is even. We compute $b^2 + 584$ for $0 \le b \le 13$.

$0^2 + 584 = 584 = 4\cdot146 = 4\cdot2\cdot73$

$2^2 + 584 = 588 = 4\cdot147 = 4\cdot3\cdot7^2$

$4^2 + 584 = 600 = 4\cdot150 = 4\cdot2\cdot3\cdot5^2$

$6^2 + 584 = 620 = 4\cdot155 = 4\cdot5\cdot31$

$8^2 + 584 = 648 = 4\cdot162 = 4\cdot2\cdot3^4$

$10^2 + 584 = 684 = 4\cdot171 = 4\cdot3^2\cdot19$

$12^2 + 584 = 728 = 4\cdot182 = 4\cdot2\cdot7\cdot13$

Thus we get the following results.

$a = 1\colon\ |b| = 0, c = 2\cdot73 = 146, (a, b, c) = (1, 0, 146)$

$a = 2\colon\ |b| = 0,c = 73, (a, b, c) = (2, 0, 73)$

$a = 3\colon\ |b| = 2,c = 7^2 = 49,(a, b, c) = (3, \pm2, 49)$

$a = 4\colon$ none

$a = 5\colon\ |b| = 4,c = 2\cdot3\cdot5 = 30,(a, b, c) = (5, \pm4, 30)$

$a = 6\colon\ |b| = 4,c = 5^2 = 25,(a, b, c) = (6, \pm4, 25)$

$a = 7\colon\ |b| = 2,c = 3\cdot7 = 21,(a, b, c) = (7, \pm2, 21)$

$a = 8 \colon$ none

$a = 9 \colon\ |b| = 8,c = 2\cdot3^2 = 18,(a, b, c) = (9, \pm8, 18)$

$a = 10 \colon\ |b| = 4,c = 3\cdot5 = 15,(a, b, c) = (10, \pm4, 15)$

$a = 11\colon$ none

$a = 12\colon$ none

$a = 13\colon\ |b| = 12,c = 2\cdot7 = 14,(a,b,c) = (13, \pm12, 14)$

Therefore $h(D) = 16$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy