Class groups of binary quadratic forms#

EXAMPLES:

Constructing the class of a given binary quadratic form is straightforward:

sage: F1 = BinaryQF([22, 91, 99])
sage: cl1 = F1.form_class(); cl1
Class of 5*x^2 - 3*x*y + 22*y^2
>>> from sage.all import *
>>> F1 = BinaryQF([Integer(22), Integer(91), Integer(99)])
>>> cl1 = F1.form_class(); cl1
Class of 5*x^2 - 3*x*y + 22*y^2

Every class is represented by a reduced form in it:

sage: cl1.form()
5*x^2 - 3*x*y + 22*y^2
sage: cl1.form() == F1.reduced_form()
True
>>> from sage.all import *
>>> cl1.form()
5*x^2 - 3*x*y + 22*y^2
>>> cl1.form() == F1.reduced_form()
True

Addition of form classes and derived operations are defined by composition of binary quadratic forms:

sage: F2 = BinaryQF([4, 1, 27])
sage: cl2 = F2.form_class(); cl2
Class of 4*x^2 + x*y + 27*y^2
sage: cl1 + cl2
Class of 9*x^2 + x*y + 12*y^2
sage: cl1 + cl2 == (F1 * F2).form_class()
True
sage: -cl1
Class of 5*x^2 + 3*x*y + 22*y^2
sage: cl1 - cl1
Class of x^2 + x*y + 108*y^2
>>> from sage.all import *
>>> F2 = BinaryQF([Integer(4), Integer(1), Integer(27)])
>>> cl2 = F2.form_class(); cl2
Class of 4*x^2 + x*y + 27*y^2
>>> cl1 + cl2
Class of 9*x^2 + x*y + 12*y^2
>>> cl1 + cl2 == (F1 * F2).form_class()
True
>>> -cl1
Class of 5*x^2 + 3*x*y + 22*y^2
>>> cl1 - cl1
Class of x^2 + x*y + 108*y^2

The form class group can be constructed as an explicit parent object:

sage: F1.discriminant()
-431
sage: Cl = BQFClassGroup(-431); Cl
Form Class Group of Discriminant -431
sage: cl1.parent() is Cl
True
sage: Cl(F1) == cl1
True
>>> from sage.all import *
>>> F1.discriminant()
-431
>>> Cl = BQFClassGroup(-Integer(431)); Cl
Form Class Group of Discriminant -431
>>> cl1.parent() is Cl
True
>>> Cl(F1) == cl1
True

Structural properties of the form class group, such as the class number, the group invariants, and element orders, can be computed:

sage: Cl.order()
21
sage: cl1 * Cl.order() == Cl.zero()
True
sage: cl2 * Cl.order() == Cl.zero()
True
sage: cl2.order()
7
sage: cl2 * cl2.order() == Cl.zero()
True
sage: Cl.abelian_group()
Additive abelian group isomorphic to Z/21 embedded in Form Class Group of Discriminant -431
sage: Cl.gens()  # random
[Class of 5*x^2 + 3*x*y + 22*y^2]
sage: Cl.gens()[0].order()
21
>>> from sage.all import *
>>> Cl.order()
21
>>> cl1 * Cl.order() == Cl.zero()
True
>>> cl2 * Cl.order() == Cl.zero()
True
>>> cl2.order()
7
>>> cl2 * cl2.order() == Cl.zero()
True
>>> Cl.abelian_group()
Additive abelian group isomorphic to Z/21 embedded in Form Class Group of Discriminant -431
>>> Cl.gens()  # random
[Class of 5*x^2 + 3*x*y + 22*y^2]
>>> Cl.gens()[Integer(0)].order()
21

AUTHORS:

  • Lorenz Panny (2023)

class sage.quadratic_forms.bqf_class_group.BQFClassGroup(D, *, check=True)[source]#

Bases: Parent, UniqueRepresentation

This type represents the class group for a given discriminant \(D\).

  • For \(D < 0\), the group is the class group of positive definite binary quadratic forms. The “full” form class group is the direct sum of two isomorphic copies of this group (one for positive definite forms and one for negative definite forms).

  • For \(D > 0\), this functionality is currently not implemented.

EXAMPLES:

sage: BQFClassGroup(-4)
Form Class Group of Discriminant -4
sage: BQFClassGroup(-6)
Traceback (most recent call last):
...
ValueError: not a discriminant
>>> from sage.all import *
>>> BQFClassGroup(-Integer(4))
Form Class Group of Discriminant -4
>>> BQFClassGroup(-Integer(6))
Traceback (most recent call last):
...
ValueError: not a discriminant

The discriminant need not be fundamental:

sage: BQFClassGroup(-22^2)
Form Class Group of Discriminant -484
>>> from sage.all import *
>>> BQFClassGroup(-Integer(22)**Integer(2))
Form Class Group of Discriminant -484
abelian_group()[source]#

Return the structure of this form class group as an AdditiveAbelianGroupWrapper object.

ALGORITHM: pari:quadclassunit

EXAMPLES:

sage: Cl = BQFClassGroup(-4*777)
sage: Cl.order()
16
sage: G = Cl.abelian_group(); G
Additive abelian group isomorphic to Z/4 + Z/2 + Z/2 embedded in Form Class Group of Discriminant -3108
sage: G.gens()  # random
(Class of 11*x^2 + 4*x*y + 71*y^2,
 Class of 6*x^2 + 6*x*y + 131*y^2,
 Class of 2*x^2 + 2*x*y + 389*y^2)
sage: [g.order() for g in G.gens()]
[4, 2, 2]
sage: G.discrete_log(Cl.random_element())  # random
(3, 0, 1)
>>> from sage.all import *
>>> Cl = BQFClassGroup(-Integer(4)*Integer(777))
>>> Cl.order()
16
>>> G = Cl.abelian_group(); G
Additive abelian group isomorphic to Z/4 + Z/2 + Z/2 embedded in Form Class Group of Discriminant -3108
>>> G.gens()  # random
(Class of 11*x^2 + 4*x*y + 71*y^2,
 Class of 6*x^2 + 6*x*y + 131*y^2,
 Class of 2*x^2 + 2*x*y + 389*y^2)
>>> [g.order() for g in G.gens()]
[4, 2, 2]
>>> G.discrete_log(Cl.random_element())  # random
(3, 0, 1)
cardinality()[source]#

Return the order of this form class group (the class number).

ALGORITHM: sage.rings.number_field.order.quadratic_order_class_number().

EXAMPLES:

sage: BQFClassGroup(-4).order()
1
sage: BQFClassGroup(-11).order()
1
sage: BQFClassGroup(-67).order()
1
sage: BQFClassGroup(-163).order()
1
sage: BQFClassGroup(-999).order()
24
sage: BQFClassGroup(-9999).order()
88
sage: BQFClassGroup(-99999).order()
224
>>> from sage.all import *
>>> BQFClassGroup(-Integer(4)).order()
1
>>> BQFClassGroup(-Integer(11)).order()
1
>>> BQFClassGroup(-Integer(67)).order()
1
>>> BQFClassGroup(-Integer(163)).order()
1
>>> BQFClassGroup(-Integer(999)).order()
24
>>> BQFClassGroup(-Integer(9999)).order()
88
>>> BQFClassGroup(-Integer(99999)).order()
224
discriminant()[source]#

Return the discriminant of the forms in this form class group.

EXAMPLES:

sage: BQFClassGroup(-999).discriminant()
-999
>>> from sage.all import *
>>> BQFClassGroup(-Integer(999)).discriminant()
-999
gens()[source]#

Return a generating set of this form class group.

EXAMPLES:

sage: Cl = BQFClassGroup(-4*419)
sage: Cl.gens()
[Class of 3*x^2 + 2*x*y + 140*y^2]
>>> from sage.all import *
>>> Cl = BQFClassGroup(-Integer(4)*Integer(419))
>>> Cl.gens()
[Class of 3*x^2 + 2*x*y + 140*y^2]
sage: Cl = BQFClassGroup(-4*777)
sage: Cl.gens()  # random
[Class of 11*x^2 + 4*x*y + 71*y^2,
 Class of 6*x^2 + 6*x*y + 131*y^2,
 Class of 2*x^2 + 2*x*y + 389*y^2]
>>> from sage.all import *
>>> Cl = BQFClassGroup(-Integer(4)*Integer(777))
>>> Cl.gens()  # random
[Class of 11*x^2 + 4*x*y + 71*y^2,
 Class of 6*x^2 + 6*x*y + 131*y^2,
 Class of 2*x^2 + 2*x*y + 389*y^2]
order()[source]#

Return the order of this form class group (the class number).

ALGORITHM: sage.rings.number_field.order.quadratic_order_class_number().

EXAMPLES:

sage: BQFClassGroup(-4).order()
1
sage: BQFClassGroup(-11).order()
1
sage: BQFClassGroup(-67).order()
1
sage: BQFClassGroup(-163).order()
1
sage: BQFClassGroup(-999).order()
24
sage: BQFClassGroup(-9999).order()
88
sage: BQFClassGroup(-99999).order()
224
>>> from sage.all import *
>>> BQFClassGroup(-Integer(4)).order()
1
>>> BQFClassGroup(-Integer(11)).order()
1
>>> BQFClassGroup(-Integer(67)).order()
1
>>> BQFClassGroup(-Integer(163)).order()
1
>>> BQFClassGroup(-Integer(999)).order()
24
>>> BQFClassGroup(-Integer(9999)).order()
88
>>> BQFClassGroup(-Integer(99999)).order()
224
random_element()[source]#

Return a somewhat random element of this form class group.

ALGORITHM:

Sample random odd primes \(a\) until \(b^2 = D \pmod{4a}\) has a solution \(b \in \ZZ\) and set \(c = (b^2-D)/(4a)\). Flip a coin to choose the sign of \(b\). Then return the class of \([a,b,c]\).

Note

No strict guarantees are being made about the distribution of classes sampled by this function. Heuristically, however, it should be fairly close to uniform.

EXAMPLES:

sage: Cl = BQFClassGroup(-999); Cl
Form Class Group of Discriminant -999
sage: cl = Cl.random_element(); cl  # random
Class of 10*x^2 + x*y + 25*y^2
sage: cl.form().discriminant()
-999
>>> from sage.all import *
>>> Cl = BQFClassGroup(-Integer(999)); Cl
Form Class Group of Discriminant -999
>>> cl = Cl.random_element(); cl  # random
Class of 10*x^2 + x*y + 25*y^2
>>> cl.form().discriminant()
-999
zero()[source]#

Return the neutral element of this group, i.e., the class of the principal binary quadratic form of the respective discriminant.

EXAMPLES:

sage: Cl = BQFClassGroup(-999)
sage: cl = Cl.zero(); cl
Class of x^2 + x*y + 250*y^2
sage: cl + cl == cl
True
>>> from sage.all import *
>>> Cl = BQFClassGroup(-Integer(999))
>>> cl = Cl.zero(); cl
Class of x^2 + x*y + 250*y^2
>>> cl + cl == cl
True
class sage.quadratic_forms.bqf_class_group.BQFClassGroupQuotientMorphism(G, H)[source]#

Bases: Morphism

Let \(D\) be a discriminant and \(f > 0\) an integer.

Given the class groups \(G\) and \(H\) of discriminants \(f^2 D\) and \(D\), this class represents the natural projection morphism \(G \to H\) which is defined by finding a class representative \([a,b,c]\) satisfying \(f^2 \mid a\) and \(f \mid b\) and substituting \(x \mapsto x/f\).

This map is a well-defined group homomorphism.

EXAMPLES:

sage: from sage.quadratic_forms.bqf_class_group import BQFClassGroupQuotientMorphism
sage: G = BQFClassGroup(-4*117117)
sage: H = BQFClassGroup(-4*77)
sage: proj = BQFClassGroupQuotientMorphism(G, H)
sage: elt = G(BinaryQF(333, 306, 422))
sage: proj(elt)
Class of 9*x^2 + 4*x*y + 9*y^2
>>> from sage.all import *
>>> from sage.quadratic_forms.bqf_class_group import BQFClassGroupQuotientMorphism
>>> G = BQFClassGroup(-Integer(4)*Integer(117117))
>>> H = BQFClassGroup(-Integer(4)*Integer(77))
>>> proj = BQFClassGroupQuotientMorphism(G, H)
>>> elt = G(BinaryQF(Integer(333), Integer(306), Integer(422)))
>>> proj(elt)
Class of 9*x^2 + 4*x*y + 9*y^2
class sage.quadratic_forms.bqf_class_group.BQFClassGroup_element(F, parent, *, check=True, reduce=True)[source]#

Bases: AdditiveGroupElement

This type represents elements of class groups of binary quadratic forms.

Users should not need to construct objects of this type directly; it can be accessed via either the BQFClassGroup parent object or the form_class() method associated to binary quadratic forms.

Currently only classes of positive definite forms are supported.

EXAMPLES:

sage: F = BinaryQF([22, 91, 99])
sage: F.form_class()  # implicit doctest
Class of 5*x^2 - 3*x*y + 22*y^2
>>> from sage.all import *
>>> F = BinaryQF([Integer(22), Integer(91), Integer(99)])
>>> F.form_class()  # implicit doctest
Class of 5*x^2 - 3*x*y + 22*y^2
sage: Cl = BQFClassGroup(-4*419)
sage: Cl.zero()
Class of x^2 + 419*y^2
sage: Cl.gens()[0]  # implicit doctest
Class of 3*x^2 + 2*x*y + 140*y^2
>>> from sage.all import *
>>> Cl = BQFClassGroup(-Integer(4)*Integer(419))
>>> Cl.zero()
Class of x^2 + 419*y^2
>>> Cl.gens()[Integer(0)]  # implicit doctest
Class of 3*x^2 + 2*x*y + 140*y^2
form()[source]#

Return a reduced quadratic form in this class.

(For \(D < 0\), each class contains a unique reduced form.)

EXAMPLES:

sage: F = BinaryQF([3221, 2114, 350])
sage: cl = F.form_class()
sage: cl.form()
29*x^2 + 14*x*y + 350*y^2
sage: cl.form() == F.reduced_form()
True
>>> from sage.all import *
>>> F = BinaryQF([Integer(3221), Integer(2114), Integer(350)])
>>> cl = F.form_class()
>>> cl.form()
29*x^2 + 14*x*y + 350*y^2
>>> cl.form() == F.reduced_form()
True
is_zero()[source]#

Return True if this form class is the principal class and False otherwise.

EXAMPLES:

sage: cl = BinaryQF([11,21,31]).form_class()
sage: cl.is_zero()
False
sage: (0*cl).is_zero()
True
>>> from sage.all import *
>>> cl = BinaryQF([Integer(11),Integer(21),Integer(31)]).form_class()
>>> cl.is_zero()
False
>>> (Integer(0)*cl).is_zero()
True
order()[source]#

Return the order of this form class in its class group.

ALGORITHM: BQFClassGroup.order() and order_from_multiple()

EXAMPLES:

sage: cl = BinaryQF([11,21,31]).form_class()
sage: cl.order()
10
sage: (cl+cl).order()
5
sage: (cl+cl+cl).order()
10
sage: (5*cl).order()
2
>>> from sage.all import *
>>> cl = BinaryQF([Integer(11),Integer(21),Integer(31)]).form_class()
>>> cl.order()
10
>>> (cl+cl).order()
5
>>> (cl+cl+cl).order()
10
>>> (Integer(5)*cl).order()
2