Binary Quadratic Forms with Integer Coefficients¶
This module provides a specialized class for working with a binary quadratic form \(a x^2 + b x y + c y^2\), stored as a triple of integers \((a, b, c)\).
EXAMPLES:
sage: Q = BinaryQF([1,2,3])
sage: Q
x^2 + 2*x*y + 3*y^2
sage: Q.discriminant()
-8
sage: Q.reduced_form()
x^2 + 2*y^2
sage: Q(1, 1)
6
TESTS:
sage: Q == loads(dumps(Q))
True
AUTHORS:
- Jon Hanke (2006-08-08):
- Appended to add the methods
BinaryQF_reduced_representatives()
,is_reduced()
, and__add__
on 8-3-2006 for Coding Sprint #2. - Added Documentation and
complex_point()
method on 8-8-2006.
- Appended to add the methods
- Nick Alexander: add doctests and clean code for Doc Days 2
- William Stein (2009-08-05): composition; some ReSTification.
- William Stein (2009-09-18): make immutable.
-
class
sage.quadratic_forms.binary_qf.
BinaryQF
(abc)¶ Bases:
sage.structure.sage_object.SageObject
A binary quadratic form over \(\ZZ\).
INPUT:
- \(v\) – a list or tuple of 3 entries: [a,b,c], or a quadratic homogeneous polynomial in two variables with integer coefficients
OUTPUT:
the binary quadratic form a*x^2 + b*x*y + c*y^2.
EXAMPLES:
sage: b = BinaryQF([1,2,3]) sage: b.discriminant() -8 sage: R.<x, y> = ZZ[] sage: BinaryQF(x^2 + 2*x*y + 3*y^2) == b True
-
complex_point
()¶ Returns the point in the complex upper half-plane associated to this (positive definite) quadratic form.
For positive definite forms with negative discriminants, this is a root \(\tau\) of \(a x^2 + b x + c\) with the imaginary part of \(\tau\) greater than 0.
EXAMPLES:
sage: Q = BinaryQF([1,0,1]) sage: Q.complex_point() 1.00000000000000*I
-
discriminant
()¶ Returns the discriminant \(b^2 - 4ac\) of the binary form \(ax^2 + bxy + cy^2\).
EXAMPLES:
sage: Q = BinaryQF([1,2,3]) sage: Q.discriminant() -8
-
has_fundamental_discriminant
()¶ Checks if the discriminant D of this form is a fundamental discriminant (i.e. D is the smallest element of its squareclass with D = 0 or 1 mod 4).
EXAMPLES:
sage: Q = BinaryQF([1,0,1]) sage: Q.discriminant() -4 sage: Q.has_fundamental_discriminant() True sage: Q = BinaryQF([2,0,2]) sage: Q.discriminant() -16 sage: Q.has_fundamental_discriminant() False
-
is_equivalent
(right)¶ Return true if self and right are equivalent, i.e., have the same reduced form.
INPUT:
right
– a binary quadratic form
EXAMPLES:
sage: a = BinaryQF([33,11,5]) sage: b = a.reduced_form(); b 5*x^2 - x*y + 27*y^2 sage: a.is_equivalent(b) True sage: a.is_equivalent(BinaryQF((3,4,5))) False
-
is_primitive
()¶ Checks if the form \(ax^2 + bxy + cy^2\) satisfies \(\gcd(a,b,c)=1\), i.e., is primitive.
EXAMPLES:
sage: Q = BinaryQF([6,3,9]) sage: Q.is_primitive() False sage: Q = BinaryQF([1,1,1]) sage: Q.is_primitive() True sage: Q = BinaryQF([2,2,2]) sage: Q.is_primitive() False sage: rqf = BinaryQF_reduced_representatives(-23*9) sage: [qf.is_primitive() for qf in rqf] [True, True, True, False, True, True, False, False, True] sage: rqf [x^2 + x*y + 52*y^2, 2*x^2 - x*y + 26*y^2, 2*x^2 + x*y + 26*y^2, 3*x^2 + 3*x*y + 18*y^2, 4*x^2 - x*y + 13*y^2, 4*x^2 + x*y + 13*y^2, 6*x^2 - 3*x*y + 9*y^2, 6*x^2 + 3*x*y + 9*y^2, 8*x^2 + 7*x*y + 8*y^2] sage: [qf for qf in rqf if qf.is_primitive()] [x^2 + x*y + 52*y^2, 2*x^2 - x*y + 26*y^2, 2*x^2 + x*y + 26*y^2, 4*x^2 - x*y + 13*y^2, 4*x^2 + x*y + 13*y^2, 8*x^2 + 7*x*y + 8*y^2]
-
is_reduced
()¶ Checks if the quadratic form is reduced, i.e., if the form \(ax^2 + bxy + cy^2\) satisfies \(|b|\leq a \leq c\), and that \(b\geq 0\) if either \(a = b\) or \(a = c\).
EXAMPLES:
sage: Q = BinaryQF([1,2,3]) sage: Q.is_reduced() False sage: Q = BinaryQF([2,1,3]) sage: Q.is_reduced() True sage: Q = BinaryQF([1,-1,1]) sage: Q.is_reduced() False sage: Q = BinaryQF([1,1,1]) sage: Q.is_reduced() True
-
is_weakly_reduced
()¶ Checks if the form \(ax^2 + bxy + cy^2\) satisfies \(|b| \leq a \leq c\), i.e., is weakly reduced.
EXAMPLES:
sage: Q = BinaryQF([1,2,3]) sage: Q.is_weakly_reduced() False sage: Q = BinaryQF([2,1,3]) sage: Q.is_weakly_reduced() True sage: Q = BinaryQF([1,-1,1]) sage: Q.is_weakly_reduced() True
-
matrix_action_left
(M)¶ Return the binary quadratic form resulting from the left action of the 2-by-2 matrix
M
on the quadratic formself
.Here the action of the matrix \(M = \begin{pmatrix} a & b \\ c & d \end{pmatrix}\) on the form \(Q(x, y)\) produces the form \(Q(ax+cy, bx+dy)\).
EXAMPLES:
sage: Q = BinaryQF([2, 1, 3]); Q 2*x^2 + x*y + 3*y^2 sage: M = matrix(ZZ, [[1, 2], [3, 5]]) sage: Q.matrix_action_left(M) 16*x^2 + 83*x*y + 108*y^2
-
matrix_action_right
(M)¶ Return the binary quadratic form resulting from the right action of the 2-by-2 matrix
M
on the quadratic formself
.Here the action of the matrix \(M = \begin{pmatrix} a & b \\ c & d \end{pmatrix}\) on the form \(Q(x, y)\) produces the form \(Q(ax+by, cx+dy)\).
EXAMPLES:
sage: Q = BinaryQF([2, 1, 3]); Q 2*x^2 + x*y + 3*y^2 sage: M = matrix(ZZ, [[1, 2], [3, 5]]) sage: Q.matrix_action_right(M) 32*x^2 + 109*x*y + 93*y^2
-
polynomial
()¶ Returns the binary quadratic form as a homogeneous 2-variable polynomial.
EXAMPLES:
sage: Q = BinaryQF([1,2,3]) sage: Q.polynomial() x^2 + 2*x*y + 3*y^2 sage: Q = BinaryQF([-1,-2,3]) sage: Q.polynomial() -x^2 - 2*x*y + 3*y^2 sage: Q = BinaryQF([0,0,0]) sage: Q.polynomial() 0
-
reduced_form
()¶ Return the unique reduced form equivalent to
self
. See alsois_reduced()
.EXAMPLES:
sage: a = BinaryQF([33,11,5]) sage: a.is_reduced() False sage: b = a.reduced_form(); b 5*x^2 - x*y + 27*y^2 sage: b.is_reduced() True sage: a = BinaryQF([15,0,15]) sage: a.is_reduced() True sage: b = a.reduced_form(); b 15*x^2 + 15*y^2 sage: b.is_reduced() True
-
small_prime_value
(Bmax=1000)¶ Returns a prime represented by this (primitive positive definite) binary form.
INPUT:
Bmax
– a positive bound on the representing integers.
OUTPUT:
A prime number represented by the form.
Note
This is a very elementary implementation which just substitutes values until a prime is found.
EXAMPLES:
sage: [Q.small_prime_value() for Q in BinaryQF_reduced_representatives(-23, primitive_only=True)] [23, 2, 2] sage: [Q.small_prime_value() for Q in BinaryQF_reduced_representatives(-47, primitive_only=True)] [47, 2, 2, 3, 3]
-
solve_integer
(n)¶ Solve \(Q(x,y) = n\) in integers \(x\) and \(y\) where \(Q\) is this quadratic form.
INPUT:
Q
(BinaryQF) – a positive definite primitive integral binary quadratic formn
(int) – a positive integer
OUTPUT:
A tuple (x,y) of integers satisfying \(Q(x,y) = n\) or
None
if no such \(x\) and \(y\) exist.EXAMPLES:
sage: Qs = BinaryQF_reduced_representatives(-23,primitive_only=True) sage: Qs [x^2 + x*y + 6*y^2, 2*x^2 - x*y + 3*y^2, 2*x^2 + x*y + 3*y^2] sage: [Q.solve_integer(3) for Q in Qs] [None, (0, 1), (0, 1)] sage: [Q.solve_integer(5) for Q in Qs] [None, None, None] sage: [Q.solve_integer(6) for Q in Qs] [(0, 1), (-1, 1), (1, 1)]
-
sage.quadratic_forms.binary_qf.
BinaryQF_reduced_representatives
(D, primitive_only=False)¶ Returns a list of inequivalent reduced representatives for the equivalence classes of positive definite binary forms of discriminant D.
INPUT:
- \(D\) – (integer) A negative discriminant.
primitive_only
– (bool, default False) flag controlling whether only primitive forms are included.
OUTPUT:
(list) A lexicographically-ordered list of inequivalent reduced representatives for the equivalence classes of positive definite binary forms of discriminant \(D\). If
primitive_only
isTrue
then imprimitive forms (which only exist when \(D\) is not fundamental) are omitted; otherwise they are included.EXAMPLES:
sage: BinaryQF_reduced_representatives(-4) [x^2 + y^2] sage: BinaryQF_reduced_representatives(-163) [x^2 + x*y + 41*y^2] sage: BinaryQF_reduced_representatives(-12) [x^2 + 3*y^2, 2*x^2 + 2*x*y + 2*y^2] sage: BinaryQF_reduced_representatives(-16) [x^2 + 4*y^2, 2*x^2 + 2*y^2] sage: BinaryQF_reduced_representatives(-63) [x^2 + x*y + 16*y^2, 2*x^2 - x*y + 8*y^2, 2*x^2 + x*y + 8*y^2, 3*x^2 + 3*x*y + 6*y^2, 4*x^2 + x*y + 4*y^2]
The number of inequivalent reduced binary forms with a fixed negative fundamental discriminant D is the class number of the quadratic field \(Q(\sqrt{D})\):
sage: len(BinaryQF_reduced_representatives(-13*4)) 2 sage: QuadraticField(-13*4, 'a').class_number() 2 sage: p=next_prime(2^20); p 1048583 sage: len(BinaryQF_reduced_representatives(-p)) 689 sage: QuadraticField(-p, 'a').class_number() 689 sage: BinaryQF_reduced_representatives(-23*9) [x^2 + x*y + 52*y^2, 2*x^2 - x*y + 26*y^2, 2*x^2 + x*y + 26*y^2, 3*x^2 + 3*x*y + 18*y^2, 4*x^2 - x*y + 13*y^2, 4*x^2 + x*y + 13*y^2, 6*x^2 - 3*x*y + 9*y^2, 6*x^2 + 3*x*y + 9*y^2, 8*x^2 + 7*x*y + 8*y^2] sage: BinaryQF_reduced_representatives(-23*9, primitive_only=True) [x^2 + x*y + 52*y^2, 2*x^2 - x*y + 26*y^2, 2*x^2 + x*y + 26*y^2, 4*x^2 - x*y + 13*y^2, 4*x^2 + x*y + 13*y^2, 8*x^2 + 7*x*y + 8*y^2]
TESTS:
sage: BinaryQF_reduced_representatives(5) Traceback (most recent call last): ... ValueError: discriminant must be negative and congruent to 0 or 1 modulo 4