Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
    
@Qiaochu, is the class number formula actually used to compute in practice? –  Mariano Suárez-Alvarez Aug 21 '10 at 22:50
    
@Mariano, no idea. My guess is it is only practical for small discriminants, but I thought the OP would want to know it exists. –  Qiaochu Yuan Aug 21 '10 at 23:07
add comment

2 Answers 2

up vote 7 down vote accepted

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).

share|improve this answer
1  
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. –  Jack Schmidt Aug 21 '10 at 23:02
2  
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 –  Bill Dubuque Aug 21 '10 at 23:12
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.