12 - Formes quadratiques binaires et nombre de classes

A Course in Arithmetic, chapitres 4-6 (Serre, GTM 7). Pour chaque discriminant fondamental \(D < 0\), le nombre de classes \(h(D)\) du corps quadratique \(\mathbb{Q}(\sqrt{D})\) se calcule directement par denombrement des formes quadratiques binaires reduites \(ax^2 + bxy + cy^2\) avec \(D = b^2 - 4ac\). Cette bijection est l’un des theoremes centraux du chapitre 4 de Serre. Outils : Python stdlib pur (math.isqrt). Le carnet 11 a pose le symbole de Legendre et la decomposition \(p = a^2 + b^2\) ; celui-ci enchaine avec l’arithmetique des corps quadratiques eux-memes.

Plan

Formes quadratiques binaires et conditions de reduction
Verification d’invariants vers la composition de Gauss
Loi analytique de Dirichlet : \(h(D) = \frac{w \sqrt{|D|}}{2\pi} L(1, \chi_D)\)
Nombres de Heegner et theoreme de Stark-Heegner
Exercices

1. Formes reduites et nombre de classes

Une forme quadratique binaire est un triplet \((a, b, c)\) qui code l’expression \(ax^2 + bxy + cy^2\). Son discriminant est \(D = b^2 - 4ac\). On s’interesse aux formes reduites : - \(-a < b \le a < c\) (cas generique) - ou \(0 \le b \le a = c\) (cas frontiere) Theoreme (reduction de Lagrange-Gauss) : toute classe de formes contient exactement une forme reduite. Le nombre \(h(D)\) de classes de l’ordre de discriminant \(D\) est donc exactement le nombre de formes réduites primitives (\(\mathrm{pgcd}(a,b,c) = 1\)) de discriminant \(D\) — le code ci-dessous filtre explicitement la primitivité.

from math import isqrt
import math

def enumerate_reduced_forms(D):
    # Formes reduites PRIMITIVES ax^2 + bxy + cy^2 avec D = b^2 - 4ac
    # Conditions : -a < b <= a < c, ou 0 <= b <= a = c ; gcd(a,b,c)=1
    # (classes de l'ORDRE de discriminant D : les formes imprimitives,
    # ex. (2,2,2) pour D=-12, ne sont pas inversibles dans l'ordre -- le
    # groupe de classes de l'ordre ne compte que les primitives)
    assert D < 0 and D % 4 in (0, 1), f'D doit etre congru 0, 1 mod 4 (D = {D})'
    forms = []
    a_max = isqrt(abs(D) // 3) + 1
    for a in range(1, a_max + 1):
        for b in range(-a + 1, a + 1):
            if (b * b - D) % (4 * a) != 0:
                continue
            c = (b * b - D) // (4 * a)
            if c < a:
                continue
            if a == c and b < 0:
                continue
            if math.gcd(math.gcd(a, b), c) != 1:
                continue
            forms.append((a, b, c))
    return forms

def kronecker(d, p):
    if p == 2:
        if d % 2 == 0:
            return 0
        if d % 8 in (1, 7):
            return 1
        return -1
    if d % p == 0:
        return 0
    v = pow(d % p, (p - 1) // 2, p)
    return -1 if v == p - 1 else 1

def conductor(d):
    if d % 4 == 1:
        return abs(d)
    while d % 4 == 0:
        d //= 4
    return abs(d)

def chi_D(d, n):
    if n == 0:
        return 0
    if n < 0:
        return chi_D(d, -n)
    out = 1
    m = n
    e = 0
    while m % 2 == 0:
        m //= 2
        e += 1
    if e > 0:
        k2 = kronecker(d, 2)
        if k2 == 0:
            return 0
        out *= k2 ** e
    p = 3
    while m > 1 and p * p <= m:
        if m % p == 0:
            e = 0
            while m % p == 0:
                m //= p
                e += 1
            kp = kronecker(d, p)
            if kp == 0:
                return 0
            out *= kp ** e
        p += 2
    if m > 1:
        out *= kronecker(d, m)
    return out

def roots_of_unit_count(d):
    if d == -4:
        return 4
    if d == -3:
        return 6
    return 2

def L_1_chi_d(d, N):
    # Produit d'Euler tronque (cf. section 3) : L(1, chi_d) ~= prod_{p <= N} (1 - chi(p)/p)^(-1).
    # Un premier p avec chi(p) = 0 (p divisant le conducteur) n'entre pas : facteur local = 1.
    prod = 1.0
    for k in range(2, N + 1):
        is_p = k > 1
        for r in range(2, int(k**0.5) + 1):
            if k % r == 0:
                is_p = False
                break
        if is_p:
            chi = chi_D(d, k)
            if chi != 0:
                prod /= (1.0 - chi / k)
    return prod

corpus = [-3, -4, -7, -8, -11, -19, -43, -67, -163, -23, -31, -59, -83]
print('Denombrement h(D) par formes reduites :')
print()
print(f"{'D':>6} | {'h(D)':>5} | {'formes reduites'}")
print('-' * 60)
for D in corpus:
    forms = enumerate_reduced_forms(D)
    h_D = len(forms)
    sample = ', '.join(f'({a},{b},{c})' for a, b, c in forms[:3])
    extra = f' + {len(forms) - 3} autres' if len(forms) > 3 else ''
    print(f'{D:>6} | {h_D:>5} | {sample}{extra}')

Denombrement h(D) par formes reduites :

     D |  h(D) | formes reduites
------------------------------------------------------------
    -3 |     1 | (1,1,1)
    -4 |     1 | (1,0,1)
    -7 |     1 | (1,1,2)
    -8 |     1 | (1,0,2)
   -11 |     1 | (1,1,3)
   -19 |     1 | (1,1,5)
   -43 |     1 | (1,1,11)
   -67 |     1 | (1,1,17)
  -163 |     1 | (1,1,41)
   -23 |     3 | (1,1,6), (2,-1,3), (2,1,3)
   -31 |     3 | (1,1,8), (2,-1,4), (2,1,4)
   -59 |     3 | (1,1,15), (3,-1,5), (3,1,5)
   -83 |     3 | (1,1,21), (3,-1,7), (3,1,7)

Lecture du resultat

Le decompte \(h(D)\) est correct pour tous les discriminants testes : - \(h(-3) = h(-4) = h(-7) = h(-8) = h(-11) = h(-19) = h(-43) = h(-67) = h(-163) = 1\) - les seuls corps quadratiques imaginaires dont l’anneau des entiers est factoriel (theoreme de Stark-Heegner, demontre independamment par Stark en 1967 et Heegner en 1952). - \(h(-23) = h(-31) = h(-59) = h(-83) = 3\) - ces discriminants portent trois classes. Ces valeurs sont les denombrements de reference que ce carnet fournit comme source canonique de \(h(D)\) ; le denombrement direct des formes est l’algorithme le plus primitif et le plus rapide pour \(|D| \le 10^4\). Pour \(|D|\) plus grand, l’algorithme sub-exponentiel de Schoof ou les methodes de reduction continue deviennent necessaires.

2. Le groupe des classes : composition de Gauss-Dirichlet par ideaux

Gauss a montre que les classes de formes quadratiques de discriminant \(D\) forment un groupe abelien fini. La construction la plus transparente (Dirichlet) passe par les ideaux de l’ordre \(O_D = \mathbb{Z}[\omega]\), \(\omega = (D + \sqrt{D})/2\) :

A la forme \(f = (a, b, c)\) on associe l’ideal \(I(f) = a\mathbb{Z} + \tau\mathbb{Z}\) avec \(\tau = (-b + \sqrt{D})/2\).
Le produit \(I(f_1) \cdot I(f_2)\) est le \(\mathbb{Z}\)-module engendre par les quatre produits \(a_1 a_2\), \(a_1 \tau_2\), \(a_2 \tau_1\), \(\tau_1 \tau_2\).
Une reduction de Hermite de ce module (base \((d_1, 0)\), \((d_{12}, d_2)\) en coordonnees \(1, \omega\)) rend sa structure : le module vaut \(d_2 \cdot (\mathbb{Z} a_3 + \mathbb{Z}(\omega + e))\) avec \(a_3 = d_1/d_2\).
La forme composite est \((a_3, b_3, c_3)\) avec \(b_3 \equiv -2e - D \pmod{2a_3}\), suivie d’une reduction de Gauss.

Les formes primitives seulement : les ideaux inversibles de l’ordre de discriminant \(D\) correspondent exactement aux formes de gcd\((a, b, c) = 1\) – c’est le meme filtre que la section 1, et la raison d’etre de la restriction aux formes primitives. L’identite du groupe est la classe principale \((1, b_0, (b_0^2 - D)/4)\) avec \(b_0 = D \bmod 2\) ; l’inverse de \((a, b, c)\) est \((a, -b, c)\).

def reduce_form(f, D):
    a, b, c = f
    while True:
        b = ((b - (-a + 1)) % (2 * a)) + (-a + 1)
        c = (b * b - D) // (4 * a)
        if a > c or (a == c and b < 0):
            a, b, c = c, -b, a
            continue
        return (a, b, c)

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x, y = extended_gcd(b % a, a)
    return g, y - (b // a) * x, x

def compose_forms(f1, f2, D):
    # Composition de Gauss-Dirichlet par produit d'ideaux dans Z[omega],
    # omega = (D + sqrt(D))/2 (cf. la section ci-dessus).
    # Forme (a, b, c) <-> ideal a.Z + tau.Z avec tau = omega - (D + b)/2.
    a1, b1, c1 = f1
    a2, b2, c2 = f2
    e1 = (D + b1) // 2
    e2 = (D + b2) // 2
    # Identite omega^2 = D*omega + (D - D^2)/4 dans l'ordre
    k = (D - D * D) // 4
    # Generateurs du produit I(f1).I(f2), en coordonnees (x, y) pour x + y*omega
    gens = [
        (a1 * a2, 0),                # a1 * a2
        (-a1 * e2, a1),              # a1 * tau2 = a1*(omega - e2)
        (-a2 * e1, a2),              # a2 * tau1
        (k + e1 * e2, D - e1 - e2),  # tau1 * tau2
    ]
    # Reduction de Hermite du Z-module de rang 2 engendre par gens :
    # base finale (d1, 0) et (d12, d2) avec 0 <= d12 < d1
    zero = [x for x, y in gens if y == 0]
    pos = [[x, y] for x, y in gens if y != 0]
    while len(pos) > 1:
        x1, y1 = pos[0]
        x2, y2 = pos[1]
        g, s, t = extended_gcd(y1, y2)
        if g < 0:
            g, s, t = -g, -s, -t
        A = (s * x1 + t * x2, g)             # seconde coordonnee : s*y1 + t*y2 = g
        B = (y2 // g * x1 - y1 // g * x2, 0) # seconde coordonnee : 0
        pos = [A] + pos[2:]
        zero.append(B[0])
    d1 = 0
    for x in zero:
        d1 = math.gcd(d1, x)
    d1 = abs(d1)
    d12, d2 = pos[0]
    if d2 < 0:
        d12, d2 = -d12, -d2
    d12 %= d1
    # I(f1).I(f2) = d2 * (Z*a3 + Z*(omega + e)) avec a3 = d1/d2, e = d12/d2
    assert d1 % d2 == 0 and d12 % d2 == 0, 'module non propre : forme non primitive ?'
    a3 = d1 // d2
    e = d12 // d2
    # tau3 = omega + e = omega - (D + b3)/2  ==>  D + b3 = -2e (mod 2*a3)
    b3 = (-2 * e - D) % (2 * a3)
    c3 = (b3 * b3 - D) // (4 * a3)
    return reduce_form((a3, b3, c3), D)

# --- Le groupe des classes de D = -23 est-il vraiment d'ordre 3 ? ---
D = -23
forms = enumerate_reduced_forms(D)
b0 = abs(D) % 2
identity = reduce_form((1, b0, (b0 * b0 - D) // 4), D)
print(f'D = {D} : formes reduites = {forms}, identite = {identity}')
print()
print('Verification du discriminant (invariant de Lagrange) :')
for a, b, c in forms:
    assert b * b - 4 * a * c == D
print('  les 3 formes satisfont bien b^2 - 4ac = -23')
print()
print('Composition g = (2, 1, 3) avec elle-meme :')
g = (2, 1, 3)
g2 = compose_forms(g, g, D)
g3 = compose_forms(g2, g, D)
print(f'  g   = {g}')
print(f'  g^2 = g compose g   = {g2}')
print(f'  g^3 = g^2 compose g = {g3}  (identite)')
assert g2 == (2, -1, 3) and g3 == identity
print()
print('Table complete des compositions (fermeture du groupe) :')
header = '        ' + ''.join(f'{str(f):>12}' for f in forms)
print(header)
for f1 in forms:
    row = f'{str(f1):>6}  '
    for f2 in forms:
        comp = compose_forms(f1, f2, D)
        assert comp in forms
        row += f'{str(comp):>12}'
    print(row)
print()
print('g^3 = identite : le groupe est cyclique, isomorphe a Z/3Z.')

# --- Cas trivial : D = -12, ordre non maximal, une seule classe primitive ---
D = -12
forms12 = enumerate_reduced_forms(D)
print(f'D = {D} : formes primitives = {forms12}')
for f1 in forms12:
    for f2 in forms12:
        assert compose_forms(f1, f2, D) in forms12
print('La composee reste dans la classe unique : h = 1, groupe trivial.')

D = -23 : formes reduites = [(1, 1, 6), (2, -1, 3), (2, 1, 3)], identite = (1, 1, 6)

Verification du discriminant (invariant de Lagrange) :
  les 3 formes satisfont bien b^2 - 4ac = -23

Composition g = (2, 1, 3) avec elle-meme :
  g   = (2, 1, 3)
  g^2 = g compose g   = (2, -1, 3)
  g^3 = g^2 compose g = (1, 1, 6)  (identite)

Table complete des compositions (fermeture du groupe) :
           (1, 1, 6)  (2, -1, 3)   (2, 1, 3)
(1, 1, 6)     (1, 1, 6)  (2, -1, 3)   (2, 1, 3)
(2, -1, 3)    (2, -1, 3)   (2, 1, 3)   (1, 1, 6)
(2, 1, 3)     (2, 1, 3)   (1, 1, 6)  (2, -1, 3)

g^3 = identite : le groupe est cyclique, isomorphe a Z/3Z.
D = -12 : formes primitives = [(1, 0, 3)]
La composee reste dans la classe unique : h = 1, groupe trivial.

Lecture du resultat

Sur \(D = -23\) (\(h = 3\)), la composition calculee confirme la structure de groupe annoncee par Gauss : \(g = (2, 1, 3)\) composee avec elle-meme donne \(g^2 = (2, -1, 3)\), puis \(g^3 = (1, 1, 6)\) l’identite – le groupe des classes est cyclique d’ordre 3, et la table complete des \(3 \times 3\) compositions est fermee sur les formes reduites. Le nombre de classes \(h(D)\) n’est pas seulement un compte : c’est l’ordre d’un groupe, dont la table se calcule effectivement.

Sur les discriminants de Heegner (\(h = 1\)), chaque forme est equivalente a la principale et la composition est triviale ; sur \(D = -12\) (ordre non maximal, \(h = 1\)) il en va de meme avec l’unique forme primitive \((1, 0, 3)\). Cette équivalence vaut pour les anneaux d’entiers (discriminants fondamentaux) : \(h(D) = 1\) y garantit la factorisation unique, \(h(D) > 1\) la rompt. Elle ne s’étend pas telle quelle aux ordres non maximaux : pour \(\mathcal{O}_{-12} = \mathbb{Z}[\sqrt{-3}]\), ordre non intégralement clos de conducteur 2, le compte \(h = 1\) des classes d’idéaux inversibles ne rend pas l’ordre factoriel.

3. Loi analytique de Dirichlet

La formule de Dirichlet relie le nombre de classes au \(L\) de Dirichlet du caractere de Kronecker \(\chi_D\) : \[h(D) = \frac{w \sqrt{|D|}}{2\pi} L(1, \chi_D)\] ou \(w\) est le nombre de racines de l’unite dans \(\mathbb{Q}(\sqrt{D})\) (\(w = 4\) pour \(D = -4\), \(w = 6\) pour \(D = -3\), \(w = 2\) sinon), et \[L(1, \chi_D) = \prod_{p \text{ premier}} \left(1 - \frac{\chi_D(p)}{p}\right)^{-1}.\] Cette formule est la maniere dont on calcule \(h(D)\) en pratique pour \(|D| > 10^4\) : on calcule le produit d’Euler jusqu’a convergence.

import math
print('Comparaison directe : h(D) par denombrement vs formule analytique')
print()
print(f"{'D':>6} | {'h(D)':>5} | {'h_an':>8} | {'w':>2} | ratio analytique / h(D)")
print('-' * 65)
for D in corpus:
    forms = enumerate_reduced_forms(D)
    h_D = len(forms)
    w = 4 if D == -4 else (6 if D == -3 else 2)
    L1 = L_1_chi_d(D, 200)
    h_an = w * math.sqrt(abs(D)) / (2 * math.pi) * L1
    ratio = h_an / h_D if h_D > 0 else 0
    print(f'{D:>6} | {h_D:>5} | {h_an:>8.3f} | {w:>2} | {ratio:.3f}')

Comparaison directe : h(D) par denombrement vs formule analytique

     D |  h(D) |     h_an |  w | ratio analytique / h(D)
-----------------------------------------------------------------
    -3 |     1 |    1.009 |  6 | 1.009
    -4 |     1 |    1.010 |  4 | 1.010
    -7 |     1 |    1.019 |  2 | 1.019
    -8 |     1 |    1.000 |  2 | 1.000
   -11 |     1 |    1.013 |  2 | 1.013
   -19 |     1 |    0.998 |  2 | 0.998
   -43 |     1 |    1.022 |  2 | 1.022
   -67 |     1 |    0.993 |  2 | 0.993
  -163 |     1 |    1.024 |  2 | 1.024
   -23 |     3 |    3.017 |  2 | 1.006
   -31 |     3 |    3.058 |  2 | 1.019
   -59 |     3 |    2.978 |  2 | 0.993
   -83 |     3 |    3.081 |  2 | 1.027

Lecture du resultat

La formule analytique \(h(D) = \frac{w \sqrt{|D|}}{2\pi} L(1, \chi_D)\), avec le produit d’Euler tronque a la borne \(p \leq N = 200\) (les 46 premiers \(\leq 200\), pas 200 premiers), restitue \(h(D)\) a mieux que 3 % sur tout le corpus (rapports de 0.993 a 1.027) : - le facteur \(2\pi\) est indispensable : le remplacer par \(\pi\) doublerait l’approximation, et l’omettre entierement la multiplierait par \(2\pi\) ; - le produit d’Euler d’un caractere reel converge lentement : l’ecart residuel de quelques pourcents est le prix de la troncature, et il se resorbe quand \(N\) croit. Pour \(|D| > 10^4\), on utilise en pratique l’algorithme de Schoof : - Schoof : \(O(|D|^{1/5+\epsilon})\) operations, polynomial. Pour les petits \(|D|\) (comme le corpus ci-dessus), le denombrement direct est imbattable : \(O(\sqrt{|D|})\) operations de l’arithmetique entiere elementaire.

4. Nombres de Heegner et theoreme de Stark-Heegner

Un nombre de Heegner est un entier \(d > 0\) tel que l’anneau des entiers de \(\mathbb{Q}(\sqrt{-d})\) soit factoriel (a factorisation unique ; pour ces anneaux d’entiers, factoriel equivaut a principal, donc \(h(D) = 1\)). L’euclideanite est une condition plus forte : parmi les neuf, seuls \(d \in \{1, 2, 3, 7, 11\}\) sont euclidiens pour la norme – \(d = 19, 43, 67, 163\) sont principaux sans l’etre. Heegner (1952), Baker (1966) et Stark (1967) ont demontre independamment que la liste est exactement : \[d \in \{1, 2, 3, 7, 11, 19, 43, 67, 163\}.\] Le \(163\) est remarquable : il donne \(\mathbb{Q}(\sqrt{-163})\) avec \(j\)-invariant \(j = -262537412640768000\), soit l’un des plus grands entiers algebriques totalement reels de la table des valeurs speciales.

# Verification : h(D) = 1 pour les 9 nombres de Heegner
heegner = [-3, -4, -7, -8, -11, -19, -43, -67, -163]
print('Cohérence numérique avec la liste de Stark-Heegner :')
print()
all_ok = True
for D in heegner:
    forms = enumerate_reduced_forms(D)
    h = len(forms)
    ok = h == 1
    all_ok = all_ok and ok
    status = 'OK' if ok else 'KO'
    print(f'  D = {D:>5} : h = {h} (attendu 1) {status}')
print()
print(f'Les 9 discriminants de Heegner donnent bien h = 1 : {all_ok}')
print('Attention : ce test ne prouve PAS le theoreme. Ce que neuf valeurs')
print('eprouvent, c est la cohérence de la liste ; l exhaustivite -- aucun')
print('autre discriminant negatif FONDAMENTAL n a h = 1 -- est exactement')
print('ce que neuf cas ne peuvent pas etablir (preuve : Heegner 1952,')
print('Stark/Baker 1967). Les ordres non maximaux comme D = -12, -16, -27')
print('ou -28 ont aussi h = 1 (cf. section 5) sans etre des corps de Heegner.')
print(f'Liste : d ∈ {{1, 2, 3, 7, 11, 19, 43, 67, 163}}')

Cohérence numérique avec la liste de Stark-Heegner :

  D =    -3 : h = 1 (attendu 1) OK
  D =    -4 : h = 1 (attendu 1) OK
  D =    -7 : h = 1 (attendu 1) OK
  D =    -8 : h = 1 (attendu 1) OK
  D =   -11 : h = 1 (attendu 1) OK
  D =   -19 : h = 1 (attendu 1) OK
  D =   -43 : h = 1 (attendu 1) OK
  D =   -67 : h = 1 (attendu 1) OK
  D =  -163 : h = 1 (attendu 1) OK

Les 9 discriminants de Heegner donnent bien h = 1 : True
Attention : ce test ne prouve PAS le theoreme. Ce que neuf valeurs
eprouvent, c est la cohérence de la liste ; l exhaustivite -- aucun
autre discriminant negatif FONDAMENTAL n a h = 1 -- est exactement
ce que neuf cas ne peuvent pas etablir (preuve : Heegner 1952,
Stark/Baker 1967). Les ordres non maximaux comme D = -12, -16, -27
ou -28 ont aussi h = 1 (cf. section 5) sans etre des corps de Heegner.
Liste : d ∈ {1, 2, 3, 7, 11, 19, 43, 67, 163}

Lecture du resultat

Le theoreme de Stark-Heegner est confirme numeriquement : pour les 9 discriminants \(D = -\{3, 4, 7, 8, 11, 19, 43, 67, 163\}\), le dénombrement donne exactement une forme réduite. Le théorème énonce l’exhaustivité pour les discriminants fondamentaux : les sorties de la section 5 montrent aussi \(h(-12) = h(-16) = h(-27) = h(-28) = 1\), ordres non maximaux de corps déjà comptés (\(\mathbb{Q}(i)\), \(\mathbb{Q}(\sqrt{-3})\) à deux reprises, \(\mathbb{Q}(\sqrt{-7})\)) — pas quatre corps de Heegner supplémentaires. La preuve est profonde : Heegner (1952) donne une preuve qui s’avere contenir une lacune comblee par Stark (1967) et Baker (1966) ; le theoreme est maintenant considere comme bien etabli. C’est l’un des resultats emblematiques de la theorie algebrique des nombres du XX\(^e\) siecle.

5. Exemples guidés et exercices

Trois exemples guidés résolus (solutions complètes lisibles ligne à ligne), chacun suivi d’un exercice à compléter sur le même terrain : Exemple guidé 1 : dénombrement de \(h(D)\) sur \(D = -163\), \(-23\), \(-1000\). Exemple guidé 2 : round-trip de composition sur \(D = -23\) — chaque forme composée avec son inverse \((a, -b, c)\) redonne la classe identité. Exemple guidé 3 : table des \(h(D)\) pour les 30 premiers discriminants négatifs (jusqu’à \(|D| = 100\)). Exercice 1 (à compléter) : discriminants fondamentaux vs ordres non maximaux parmi les \(h = 1\) de la table. Exercice 2 (à compléter) : ordre effectif d’une classe par composition itérée, sur \(D = -31\). Exercice 3 (à compléter) : croissance de \(h(D)\) confrontée à la loi de Dirichlet (\(h(D) \sim c\sqrt{|D|}\)).

# Exemple guide 1 : denombrement de h(D) -- solution commentee.
# L'Exercice 1 ci-dessous reprend un terrain voisin a completer.
def exo1_count_reduced(D):
    if D >= 0:
        raise ValueError(f'D doit etre < 0, recu {D}')
    if D % 4 not in (0, 1):
        raise ValueError(f'D doit etre congru 0, 1 mod 4, recu {D}')
    return len(enumerate_reduced_forms(D))

print(f'D = -163 : h = {exo1_count_reduced(-163)} (attendu 1)')
print(f'D = -23 : h = {exo1_count_reduced(-23)} (attendu 3)')
print(f'D = -1000 : h = {exo1_count_reduced(-1000)}')

D = -163 : h = 1 (attendu 1)
D = -23 : h = 3 (attendu 3)
D = -1000 : h = 10

Exercice 1 (à compléter) — Discriminants fondamentaux. Dans la table de l’exemple guidé 3, onze valeurs ont \(h = 1\) : les sept discriminants fondamentaux \(-3, -4, -7, -8, -11, -19, -43\) (membres de la liste de Heegner, avec \(-67\) et \(-163\) hors table) et quatre ordres non maximaux \(-12, -16, -27, -28\). Écrire is_fundamental(D) qui applique le critère : \(D \equiv 1 \pmod 4\) et \(D\) sans facteur carré, ou \(D = 4m\) avec \(m \equiv 2, 3 \pmod 4\) et \(m\) sans facteur carré — puis séparer les deux familles.

# Exercice 1 : discriminants fondamentaux -- separer Heegner et ordres non
# maximaux parmi les h = 1 de la table des 30 discriminants.
# Indice : un entier n est sans facteur carre ssi aucun carre p**2 de premier
# p <= sqrt(|n|) ne divise n.
# Etape 1 : ecrire carre_libre(n).
# Etape 2 : appliquer le critere (D % 4 == 1, ou D = 4*m avec m % 4 in (2, 3)).
# Etape 3 : filtrer les D de la table avec h(D) = 1 et afficher les deux familles.
def is_fundamental(D):
    pass  # TODO etudiant
    return None

print('Exercice 1 a completer : is_fundamental(D)')
print('Attendu : fondamentaux h=1 dans la table des 30 = [-3, -4, -7, -8, -11, -19, -43]')
print('          non fondamentaux h=1 = [-12, -16, -27, -28]')

Exercice 1 a completer : is_fundamental(D)
Attendu : fondamentaux h=1 dans la table des 30 = [-3, -4, -7, -8, -11, -19, -43]
          non fondamentaux h=1 = [-12, -16, -27, -28]

# Exemple guide 2 : round-trip de composition -- chaque forme composee avec son
# inverse (a, -b, c) doit redonner la classe identite.
D = -23
forms = enumerate_reduced_forms(D)
b0 = abs(D) % 2
identity = reduce_form((1, b0, (b0 * b0 - D) // 4), D)
print(f'D = {D}, formes reduites = {forms}, identite = {identity}')
print()
print('Round-trip f o f^-1 (inverse explicite (a, -b, c)) :')
all_ok = True
for a, b, c in forms:
    comp = compose_forms((a, b, c), (a, -b, c), D)
    ok = comp == identity
    all_ok = all_ok and ok
    print(f'  ({a},{b},{c}) o ({a},{-b},{c}) = {comp}  (identite : {ok})')
assert all_ok
print()
print('Invariant de Lagrange, verifie au passage :')
for a, b, c in forms:
    assert b * b - 4 * a * c == D
print('  les 3 formes satisfont bien b^2 - 4ac = -23')

D = -23, formes reduites = [(1, 1, 6), (2, -1, 3), (2, 1, 3)], identite = (1, 1, 6)

Round-trip f o f^-1 (inverse explicite (a, -b, c)) :
  (1,1,6) o (1,-1,6) = (1, 1, 6)  (identite : True)
  (2,-1,3) o (2,1,3) = (1, 1, 6)  (identite : True)
  (2,1,3) o (2,-1,3) = (1, 1, 6)  (identite : True)

Invariant de Lagrange, verifie au passage :
  les 3 formes satisfont bien b^2 - 4ac = -23

Exercice 2 (à compléter) — Ordre d’une classe. Le groupe des classes de \(D = -31\) a \(h(-31) = 3\) éléments ; l’identité est la forme principale \((1, 1, 8)\) et \(g = (2, 1, 4)\) n’est pas neutre. Comme 3 est premier, la classe de \(g\) est d’ordre 3 : le vérifier par composition itérative effective, sans afficher la table complète.

# Exercice 2 : ordre effectif de la classe de (2, 1, 4) dans Cl(D = -31).
# Indice : composer g avec g0 par compose_forms puis reduce_form, jusqu'a
# retrouver la forme identite reduite (1, b0, (b0*b0 - D)//4), b0 = abs(D) % 2.
# Etape 1 : calculer et reduire l'identite.
# Etape 2 : iterer g = reduce_form(compose_forms(g, g_depart, D), D) en comptant.
# Etape 3 : verifier que l'ordre trouve divise h(-31) = 3.
def ordre_de_classe(D, g):
    pass  # TODO etudiant
    return None

print('Exercice 2 a completer : ordre_de_classe(-31, (2, 1, 4))')
print('Attendu : ordre 3 -- le groupe etant d ordre premier 3, cyclique')

Exercice 2 a completer : ordre_de_classe(-31, (2, 1, 4))
Attendu : ordre 3 -- le groupe etant d ordre premier 3, cyclique

# Exemple guide 3 : table des h(D) des 30 premiers discriminants negatifs.
discriminants_negatifs = sorted((D for D in range(-100, 0) if D % 4 in (0, 1)), key=abs)[:30]
print(f'30 premiers discriminants negatifs (D = 0, 1 mod 4), par |D| croissant : {len(discriminants_negatifs)}')
print()
print(f"{'D':>6} | {'h(D)':>5}")
print('-' * 20)
for D in discriminants_negatifs[:30]:
    h = len(enumerate_reduced_forms(D))
    print(f'{D:>6} | {h:>5}')

30 premiers discriminants negatifs (D = 0, 1 mod 4), par |D| croissant : 30

     D |  h(D)
--------------------
    -3 |     1
    -4 |     1
    -7 |     1
    -8 |     1
   -11 |     1
   -12 |     1
   -15 |     2
   -16 |     1
   -19 |     1
   -20 |     2
   -23 |     3
   -24 |     2
   -27 |     1
   -28 |     1
   -31 |     3
   -32 |     2
   -35 |     2
   -36 |     2
   -39 |     4
   -40 |     2
   -43 |     1
   -44 |     3
   -47 |     5
   -48 |     2
   -51 |     2
   -52 |     2
   -55 |     4
   -56 |     4
   -59 |     3
   -60 |     2

Exercice 3 (à compléter) — Croissance de \(h(D)\). La formule de Dirichlet (section 3) prédit \(h(D)\) de l’ordre de \(\sqrt{|D|}\). Vérifier sur la table des 30 discriminants que le rapport \(h(D) / \sqrt{|D|}\) reste borné (sur cette table : entre \(0{,}15\) et \(0{,}73\) environ), et repérer que le maximum est atteint pour \(D = -47\).

# Exercice 3 : croissance de h(D) -- rapport h(D)/sqrt(|D|) sur la table des
# 30 premiers discriminants negatifs (loi analytique de Dirichlet, section 3).
# Indice : math.sqrt ; reutiliser enumerate_reduced_forms comme dans les exemples.
# Etape 1 : reconstruire la table (D % 4 in (0, 1), -100 < D < 0, 30 premiers).
# Etape 2 : afficher D, h(D), h(D)/sqrt(|D|) et le min/max du rapport.
def rapport_h_sur_racine(D):
    pass  # TODO etudiant
    return None

print('Exercice 3 a completer : rapport h(D)/sqrt(|D|) sur la table des 30')
print('Attendu : rapport borne, min ~0.15 (D = -43), max ~0.73 (D = -47)')

Exercice 3 a completer : rapport h(D)/sqrt(|D|) sur la table des 30
Attendu : rapport borne, min ~0.15 (D = -43), max ~0.73 (D = -47)

Conclusion

Le decompte des classes \(h(D)\) par denombrement des formes quadratiques binaires reduites est l’un des algorithmes les plus elementaires de la theorie algebrique des nombres. Il suffit de la condition de reduction (\(-a < b \le a < c\), ou \(0 \le b \le a = c\)) et du filtre de primitivite (\(\mathrm{pgcd}(a,b,c) = 1\) – pour \(D = -12\), la reduction seule admet \((2,2,2)\), exclue par ce filtre) pour transformer un probleme infini en un comptage fini, et la bijection avec les classes d’ideaux primitives est etablie par Lagrange et Gauss. Le theoreme de Stark-Heegner couronne ce calcul : il dit que la liste des discriminants fondamentaux de \(h = 1\) est exactement celle de ces 9 corps quadratiques — les ordres non maximaux comme \(-12\), \(-16\), \(-27\), \(-28\) ont aussi \(h = 1\) sans être des corps de Heegner — et le dernier (\(-163\)) est remarquable - c’est l’un des calculs algebriques les plus celebres de l’arithmetique.

Ressources

Serre, A Course in Arithmetic, chapitres 4-6 (Springer GTM 7) - la reference canonique.
Cohen, A Course in Computational Algebraic Number Theory (Springer GTM 138), vol. I ch. 5 - algorithmes.
Cohn, A Classical Invitation to Modern Number Theory - pour une introduction motivee.
OEIS A014603 - nombres de Heegner : 1, 2, 3, 7, 11, 19, 43, 67, 163.
OEIS A003649 - nombre de classes \(h(D)\) pour les corps quadratiques imaginaires.

Retour au sommet