Binary quadratic forms turn arithmetic questions about integers into a finite reduction problem on triples. A form
Q(x,y)=ax²+bxy+cy²
stores more than a polynomial. Its discriminant, represented integers and change-of-variables class carry arithmetic information that survives many transformations. For negative discriminant, every proper equivalence class contains a reduced representative, so an infinite search through equivalent forms collapses to a finite list.
This is Guide 17 in the Bukit Timah Tutor Computational Number Theory series. It follows the number-field and ideal language of Guide 16 and gives a concrete route from forms to ideal class groups. It is an advanced enrichment guide. Return to the BTT Mathematics Hub for the wider Mathematics estate.
1. The basic object and its discriminant
A binary quadratic form is written [a,b,c] for ax²+bxy+cy² with integer coefficients. Its discriminant is
D=b²−4ac.
The discriminant controls the geometry. If D<0 and a>0, the form is positive definite: Q(x,y)>0 for every nonzero real pair (x,y). If D>0, the form is indefinite and takes both positive and negative values.
For [2,1,3], the discriminant is 1−24=−23. The form is positive definite.
2. Primitive forms
A form is primitive when gcd(a,b,c)=1. Primitive forms are the natural objects for the classical class group of a fundamental discriminant.
If all three coefficients share a factor g, then every represented value is divisible by g. Removing this common factor changes the discriminant by a square factor and changes the arithmetic problem.
Primitive is therefore not a cosmetic normalisation. It separates the intrinsic form from an obvious scalar multiple.
3. Equivalence by unimodular substitution
Let
x = px' + qy' y = rx' + sy'
with integer matrix M=[[p,q],[r,s]] and det(M)=1. Substituting into Q gives another integral form with the same discriminant. Forms related by such an SL(2,Z) substitution are properly equivalent.
The determinant-one condition makes the substitution invertible over the integers. It preserves the represented integer set in the correct two-variable sense and keeps orientation, which matters for the proper class group.
Allowing determinant −1 gives the wider notion of improper equivalence. A computation should state which convention it uses.
4. Elementary moves
Two especially useful substitutions are shears and swaps. Replacing x by x+ky changes the middle coefficient while preserving the discriminant. Swapping variables exchanges a and c and changes the sign of b.
These moves are the quadratic-form analogue of Euclidean reduction: adjust a coefficient by an integer multiple, then reorder so the smaller direction comes first.
A reduction algorithm repeatedly applies such unimodular changes until simple inequalities hold.
5. Reduced positive-definite forms
For D<0, a standard reduced condition is
|b| ≤ a ≤ c,
with a sign convention on boundary cases: if |b|=a or a=c, take b≥0. Every proper equivalence class of primitive positive-definite forms has a reduced representative; for negative fundamental discriminant, the reduced representative is unique under the standard convention.
The inequalities imply a finite search. Since D=b²−4ac and |b|≤a≤c, one obtains a bound on a in terms of √|D|. Thus only finitely many triples need be checked for a fixed negative D.
6. Enumerating discriminant −23
Let D=−23. A reduced form must satisfy |b|≤a≤c and b²+23=4ac.
For a=1, b must be odd and |b|≤1, so b=1 under the boundary convention. Then c=(1+23)/4=6, giving [1,1,6].
For a=2, |b|≤2 and b must be odd. Both b=1 and b=−1 are allowed because |b|<a. Then c=(1+23)/8=3, giving [2,1,3] and [2,−1,3].
No larger a satisfies the reduced bound. Therefore the complete reduced list is
[1,1,6], [2,1,3], [2,−1,3].
This gives class number 3 for the discriminant −23 form class group. The same list is documented in standard treatments and in computational references such as Sage’s binary quadratic form tools.
7. Representation of integers
A form Q represents n if there exist integers x,y with Q(x,y)=n. The representation question depends on the class, not merely on the discriminant.
The principal form [1,1,6] represents 1 at (1,0), 6 at (0,1), 8 at (2,0? no: that gives 4), and many other values. The form [2,1,3] represents 2 at (1,0) and 3 at (0,1).
A quick modular obstruction can rule out a representation. For example, if a form has values constrained to certain congruence classes modulo a small prime, an excluded residue cannot be represented.
Such tests are necessary conditions, not automatically sufficient conditions.
8. The principal class
For a negative fundamental discriminant D, there is a distinguished principal form. When D≡1 mod4, one convenient principal representative is
[1,1,(1−D)/4].
For D=−23 this is [1,1,6]. Its class is the identity under Gauss composition.
The word principal mirrors principal ideals in the corresponding quadratic field. Under the form–ideal correspondence, the principal form represents the identity ideal class.
9. Gauss composition creates a group
Primitive proper equivalence classes of forms with fixed discriminant can be composed. The raw coefficient formula has several gcd cases, but the conceptual structure is simpler.
Associate a form to an ideal class in the quadratic order. Multiply the ideals. Convert the product back to a form class. The resulting operation is associative, has the principal class as identity and gives an inverse to every class.
Reduction can be applied after composition to return the result to the finite reduced list.
10. The complete class group at D=−23
There are only three reduced classes. Therefore any nonidentity class generates a cyclic group of order three.
With the standard composition convention, the two nonprincipal classes are inverses. One explicit multiplication table is:
e = [1,1,6] g = [2,−1,3] g² = [2,1,3] g·g = g² g·g² = e g³ = e.
William Stein’s computational notes give this exact discriminant −23 example. The finite reduced list and the composition law make the class group visible without abstract quotient notation.
11. Inverse forms
For primitive positive-definite forms, changing b to −b gives the inverse class:
[a,b,c]^−1 = [a,−b,c]
up to reduction and the boundary convention.
At D=−23, [2,1,3] and [2,−1,3] are therefore inverse classes. The principal form [1,1,6] is equivalent to its own inverse.
12. Forms and quadratic ideals
For a fundamental discriminant D and form [a,b,c], an associated ideal can be written using
a and (−b+√D)/2.
After the appropriate scaling convention, proper equivalence of forms corresponds to ideal-class equivalence in the quadratic field or order.
This correspondence explains why class numbers computed from reduced forms agree with ideal class numbers for fundamental discriminants.
It also explains composition: multiplying ideals is usually conceptually cleaner than memorising a large case-dependent coefficient formula.
13. Why reduction is computationally valuable
Without reduction, an equivalence class contains infinitely many forms. A search for equality of classes would be an infinite problem.
Reduction maps each class to a bounded representative. Equality becomes comparison of reduced triples. Composition becomes compose, then reduce. Inversion becomes sign change, then reduce.
This is the same computational pattern that appears repeatedly elsewhere: find a canonical or near-canonical representative so that structural equality can be decided finitely.
14. Reduction and continued fractions
For indefinite forms, reduction is closely connected to continued fractions of quadratic irrationals. The periodicity of continued fractions reflects cycles of reduced forms rather than a finite static list.
For positive-definite negative discriminant, the reduced class set is finite and does not cycle in the same way. The geometry and algorithm depend strongly on the sign of D.
This is why one should not import a positive-definite reduced inequality into an indefinite-form implementation without changing the theory.
15. Composition and represented primes
For suitable primes p not dividing D, the factorisation behaviour of p in the quadratic field is reflected in whether p is represented by a form of discriminant D.
Different form classes can represent different split primes. The class of a prime ideal above p corresponds to the class of a form representing p.
This creates a bridge among congruences, quadratic residues, ideals and forms: a Legendre-symbol condition predicts whether splitting is possible, while the form class records finer information about which ideal class appears.
16. A bounded enumeration algorithm
def reduced_forms_negative_discriminant(D):
assert D < 0 and D % 4 in (0, 1)
output = []
# a only needs to run through a proven sqrt(|D|)-scale bound
for a in candidate_range:
for b in range(-a, a + 1):
if (b*b - D) % (4*a):
continue
c = (b*b - D) // (4*a)
if a > c:
continue
if (abs(b) == a or a == c) and b < 0:
continue
if gcd(a, gcd(abs(b), c)) != 1:
continue
output.append((a,b,c))
return outputThe omitted candidate bound should come from the reduction theorem, not from an arbitrary search cap. The output can be checked by recomputing each discriminant and testing every reduced inequality.
17. Verification strategy
For every returned form, verify b²−4ac=D and gcd(a,b,c)=1. Verify the reduced inequalities. For a claimed complete enumeration, verify the theoretical bound on a and that every allowed b satisfying the divisibility condition was tested.
For composition, verify the output discriminant, reduce it and test group identities on the entire small class set. At D=−23, the three-element table can be checked exhaustively.
For represented integers, substitute the claimed coordinates directly. A class-number computation and a representation certificate are different outputs and need different checks.
18. Common mistakes
1. Forgetting to fix the discriminant. 2. Mixing proper and improper equivalence. 3. Dropping primitivity. 4. Treating every form with the same discriminant as identical.
5. Using reduced inequalities without boundary sign conventions. 6. Assuming a reduced form is a unique polynomial rather than a representative of a class. 7. Applying positive-definite reduction to D>0 unchanged. 8. Claiming composition from coefficient multiplication; forms do not compose by multiplying a,b,c componentwise.
19. Practice set
1. Find the discriminant of [2,1,3]. 2. Decide whether [2,1,3] is primitive. 3. State the standard positive-definite reduced inequalities. 4. Enumerate the reduced forms of discriminant −23.
5. Which form is principal at D=−23? 6. Which two reduced forms are inverse classes? 7. What is the class number? 8. What is the group structure?
9. Explain why an SL(2,Z) substitution preserves the discriminant. 10. What makes the enumeration finite? 11. What does it mean for a form to represent n? 12. Give a value represented by [2,1,3].
13. Why is composition easier to conceptualise through ideals? 14. What must be verified after a computed composition? 15. Why is the sign of D algorithmically important? 16. What does the form–ideal correspondence explain about class numbers?
20. Answers
1. −23. 2. Yes, gcd(2,1,3)=1. 3. |b|≤a≤c with b≥0 on the standard boundary cases. 4. [1,1,6], [2,1,3], [2,−1,3].
5. [1,1,6]. 6. [2,1,3] and [2,−1,3]. 7. Three. 8. Cyclic of order three.
9. The discriminant is the determinant-type invariant of the quadratic polynomial under determinant-one integral change of variables. 10. Reduction bounds a and b in terms of |D|. 11. There exist integers x,y with Q(x,y)=n. 12. It represents 2 at (1,0) and 3 at (0,1).
13. Ideal multiplication is associative and already carries a natural class-group structure. 14. Discriminant, primitivity where required, proper equivalence and reduction to the expected class. 15. Negative definite and positive/indefinite forms have different reduction theories. 16. For fundamental discriminants, reduced primitive form classes correspond to ideal classes in the quadratic field.
Sources and further study
SageMath’s Binary Quadratic Forms documentation provides computational reduction and class-number examples. William Stein’s quadratic form class-group notes give the explicit D=−23 composition table. For broader algebraic-number-theory context, use the class-group and binary-quadratic-form chapters in standard number theory texts.
Continue through Batch 05
Continue to Guide 18: Smith & Hermite Normal Forms, Integer Modules and Exact Lattice Arithmetic, then Guide 19: Dirichlet Unit Theorem, Regulators and Logarithmic Unit Lattices, and Guide 20: Class Group Algorithms, Minkowski Bounds, Relation Matrices and Principal Ideal Tests.