Computing in the class group

The primitive positive definite binary quadratic forms of a discriminant D < 0, up to \mathrm{SL}_2(\mathbb{Z})-equivalence, form the form class group \mathrm{Cl}(D), a finite abelian group whose order is the class number h(D). For a fundamental discriminant it is isomorphic to the ideal class group of the imaginary quadratic field \mathbb{Q}(\sqrt D) [Coh1996, §5.2], [Buell1989].

Representing classes#

Each class contains exactly one reduced form (a, b, c), with |b| \le a \le c and b \ge 0 if |b| = a or a = c; qfb_reduce finds it, and the reduced form serves as the canonical representative, so that two classes are equal if and only if their reduced forms are equal (qfb_equal). The identity is the principal form (qfb_principal_form), and the inverse of (a, b, c) is (a, -b, c) (qfb_inverse). Since a \le \sqrt{|D|/3} for a reduced form, all reduced forms can be listed for moderate |D| (qfb_reduced_forms), which gives h(D) in O(|D|^{1/2 + o(1)}) time.

Composition and powers#

The group operation is Gauss composition. qfb_nucomp computes it with Shanks' NUCOMP algorithm, which interleaves the composition with a partial reduction so that the intermediate numbers stay of the size of |D|^{1/2} rather than |D|; its output is nearly reduced and must be passed to qfb_reduce:

fmpz_abs(L, D);
fmpz_root(L, L, 4);            /* L = floor(|D|^(1/4)) */
qfb_nucomp(r, f, g, D, L);
qfb_reduce(r, r, D);

qfb_nudupl squares a form, and qfb_pow_ui and qfb_pow compute reduced powers by binary powering; their exponents must be nonnegative. The inputs of the composition functions must be primitive.

Orders and the exponent#

For large |D| the reduced forms cannot be listed, but the structure of the group can still be explored. qfb_exponent_element finds the order of a form whose order has only small prime factors, except possibly one larger prime (a two-stage method like Pollard's p - 1), and qfb_exponent and qfb_exponent_grh compute the exponent of the class group from the orders of prime forms (qfb_prime_form) for small primes; the GRH version uses enough primes to generate the group if the generalised Riemann hypothesis holds. The exponent is a multiple of the order of every element and divides h(D); for most discriminants the class group is cyclic or nearly so, and the exponent is close to h(D). The stage 1 bound B1 should be at least about 8200 (see the warning at qfb_exponent_element).

Example#

The program lists the four reduced forms of discriminant -56, shows that (3, 2, 5) generates the cyclic group \mathrm{Cl}(-56) of order 4, compares the class number of -1000003 with the exponent found from prime forms, and computes the exponent of the class group of discriminant -(10^{18} + 3), whose class number is near 10^8.

#include <flint/flint.h>
#include <flint/fmpz.h>
#include <flint/qfb.h>

int main(void)
{
    qfb * forms;
    qfb_t f, g;
    fmpz_t D, e;
    slong i, num;

    fmpz_init(D);
    fmpz_init(e);
    qfb_init(f);
    qfb_init(g);

    num = qfb_reduced_forms(&forms, -56);
    flint_printf("h(-56) = %wd:", num);
    for (i = 0; i < num; i++)
    {
        flint_printf(" ");
        qfb_print(forms + i);
    }
    flint_printf("\n");

    fmpz_set_si(D, -56);
    qfb_set(f, forms + 2);
    flint_printf("powers of ");
    qfb_print(f);
    flint_printf(":");
    for (i = 1; i <= 4; i++)
    {
        qfb_pow_ui(g, f, D, i);
        flint_printf(" ");
        qfb_print(g);
    }
    flint_printf("\n");
    qfb_array_clear(&forms, num);

    num = qfb_reduced_forms(&forms, -1000003);
    qfb_array_clear(&forms, num);
    fmpz_set_si(D, -1000003);
    qfb_exponent_grh(e, D, 10000, 100);
    flint_printf("h(-1000003) = %wd, exponent ", num);
    fmpz_print(e);
    flint_printf("\n");

    fmpz_set_str(D, "-1000000000000000003", 10);
    if (qfb_exponent_grh(e, D, 100000, 10000))
    {
        flint_printf("exponent of Cl(-(10^18 + 3)) = ");
        fmpz_print(e);
        flint_printf("\n");
    }

    qfb_clear(f);
    qfb_clear(g);
    fmpz_clear(D);
    fmpz_clear(e);
    return 0;
}

h(-56) = 4: (1, 0, 14) (2, 0, 7) (3, 2, 5) (3, -2, 5)
powers of (3, 2, 5): (3, 2, 5) (2, 0, 7) (3, -2, 5) (1, 0, 14)
h(-1000003) = 105, exponent 105
exponent of Cl(-(10^18 + 3)) = 102764373