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

AUTHORS:

  • Jon Hanke (2006-08-08):

  • 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.

  • Justin C. Walker (2011-02-06):

    • Add support for indefinite forms.

class sage.quadratic_forms.binary_qf.BinaryQF(a, b=None, c=None)

Bases: sage.structure.sage_object.SageObject

A binary quadratic form over \(\ZZ\).

INPUT:

One of the following:

  • a – either a 3-tuple of integers, or a quadratic homogeneous polynomial in two variables with integer coefficients

  • a, b, c – three integers

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: b1 = BinaryQF(1, 2, 3)
sage: b1 == b
True
sage: R.<x, y> = ZZ[]
sage: BinaryQF(x^2 + 2*x*y + 3*y^2) == b
True
sage: BinaryQF(1, 0, 1)
x^2 + y^2
complex_point()

Return the point in the complex upper half-plane associated to self.

This form, \(ax^2 + b xy + cy^2\), must be definite with negative discriminant \(b^2 - 4 a c < 0\).

OUTPUT:

  • the unique complex root of \(a x^2 + b x + c\) with positive imaginary part

EXAMPLES:

sage: Q = BinaryQF([1, 0, 1])
sage: Q.complex_point()
1.00000000000000*I
content()

Return the content of the form, i.e., the gcd of the coefficients.

EXAMPLES:

sage: Q = BinaryQF(22, 14, 10)
sage: Q.content()
2
sage: Q = BinaryQF(4, 4, -15)
sage: Q.content()
1
cycle(proper=False)

Return the cycle of reduced forms to which self belongs.

This is based on Algorithm 6.1 of [BUVO2007].

INPUT:

  • self – reduced, indefinite form of non-square discriminant

  • proper – boolean (default: False); if True, return the proper cycle

The proper cycle of a form \(f\) consists of all reduced forms that are properly equivalent to \(f\). This is useful when testing for proper equivalence (or equivalence) between indefinite forms.

The cycle of \(f\) is a technical tool that is used when computing the proper cycle. Our definition of the cycle is slightly different from the one in [BUVO2007]. In our definition, the cycle consists of all reduced forms \(g\), such that the \(a\)-coefficient of \(g\) has the same sign as the \(a\)-coefficient of \(f\), and \(g\) can be obtained from \(f\) by performing a change of variables, and then multiplying by the determinant of the change-of-variables matrix. It is important to note that \(g\) might not be equivalent to \(f\) (because of multiplying by the determinant). However, either ‘g’ or ‘-g’ must be equivalent to \(f\). Also note that the cycle does contain \(f\). (Under the definition in [BUVO2007], the cycle might not contain \(f\), because all forms in the cycle are required to have positive \(a\)-coefficient, even if the \(a\)-coefficient of \(f\) is negative.)

EXAMPLES:

sage: Q = BinaryQF(14, 17, -2)
sage: Q.cycle()
[14*x^2 + 17*x*y - 2*y^2,
 2*x^2 + 19*x*y - 5*y^2,
 5*x^2 + 11*x*y - 14*y^2]
sage: Q.cycle(proper=True)
[14*x^2 + 17*x*y - 2*y^2,
 -2*x^2 + 19*x*y + 5*y^2,
 5*x^2 + 11*x*y - 14*y^2,
 -14*x^2 + 17*x*y + 2*y^2,
 2*x^2 + 19*x*y - 5*y^2,
 -5*x^2 + 11*x*y + 14*y^2]

sage: Q = BinaryQF(1, 8, -3)
sage: Q.cycle()
[x^2 + 8*x*y - 3*y^2,
3*x^2 + 4*x*y - 5*y^2,
5*x^2 + 6*x*y - 2*y^2,
2*x^2 + 6*x*y - 5*y^2,
5*x^2 + 4*x*y - 3*y^2,
3*x^2 + 8*x*y - y^2]
sage: Q.cycle(proper=True)
[x^2 + 8*x*y - 3*y^2,
-3*x^2 + 4*x*y + 5*y^2,
 5*x^2 + 6*x*y - 2*y^2,
 -2*x^2 + 6*x*y + 5*y^2,
 5*x^2 + 4*x*y - 3*y^2,
 -3*x^2 + 8*x*y + y^2]

sage: Q = BinaryQF(1, 7, -6)
sage: Q.cycle()
[x^2 + 7*x*y - 6*y^2,
6*x^2 + 5*x*y - 2*y^2,
2*x^2 + 7*x*y - 3*y^2,
3*x^2 + 5*x*y - 4*y^2,
4*x^2 + 3*x*y - 4*y^2,
4*x^2 + 5*x*y - 3*y^2,
3*x^2 + 7*x*y - 2*y^2,
2*x^2 + 5*x*y - 6*y^2,
6*x^2 + 7*x*y - y^2]
det()

Return the determinant of the matrix associated to self.

The determinant is used by Gauss and by Conway-Sloane, for whom an integral quadratic form has coefficients \((a, 2b, c)\) with \(a\), \(b\), \(c\) integers.

OUTPUT:

The determinant of the matrix:

[  a  b/2]
[b/2    c]

as a rational

REMARK:

This is just \(-D/4\) where \(D\) is the discriminant. The return type is rational even if \(b\) (and hence \(D\)) is even.

EXAMPLES:

sage: q = BinaryQF(1, -1, 67)
sage: q.determinant()
267/4
determinant()

Return the determinant of the matrix associated to self.

The determinant is used by Gauss and by Conway-Sloane, for whom an integral quadratic form has coefficients \((a, 2b, c)\) with \(a\), \(b\), \(c\) integers.

OUTPUT:

The determinant of the matrix:

[  a  b/2]
[b/2    c]

as a rational

REMARK:

This is just \(-D/4\) where \(D\) is the discriminant. The return type is rational even if \(b\) (and hence \(D\)) is even.

EXAMPLES:

sage: q = BinaryQF(1, -1, 67)
sage: q.determinant()
267/4
discriminant()

Return the discriminant of self.

Given a form \(ax^2 + bxy + cy^2\), this returns \(b^2 - 4ac\).

EXAMPLES:

sage: Q = BinaryQF([1, 2, 3])
sage: Q.discriminant()
-8
has_fundamental_discriminant()

Return 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\) modulo \(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(other, proper=True)

Return if self is equivalent to other.

INPUT:

  • proper – bool (default: True); if True use proper equivalence

  • other – a binary quadratic form

EXAMPLES:

sage: Q3 = BinaryQF(4, 4, 15)
sage: Q2 = BinaryQF(4, -4, 15)
sage: Q2.is_equivalent(Q3)
True
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

Some indefinite examples:

sage: Q1 = BinaryQF(9, 8, -7)
sage: Q2 = BinaryQF(9, -8, -7)
sage: Q1.is_equivalent(Q2, proper=True)
False
sage: Q1.is_equivalent(Q2, proper=False)
True
is_indef()

Return if self is indefinite, i.e., has positive discriminant.

EXAMPLES:

sage: Q = BinaryQF(1, 3, -5)
sage: Q.is_indef()
True
is_indefinite()

Return if self is indefinite, i.e., has positive discriminant.

EXAMPLES:

sage: Q = BinaryQF(1, 3, -5)
sage: Q.is_indef()
True
is_negative_definite()

Return True if self is negative definite, i.e., has negative discriminant with \(a < 0\).

EXAMPLES:

sage: Q = BinaryQF(-1, 3, -5)
sage: Q.is_positive_definite()
False
sage: Q.is_negative_definite()
True
is_negdef()

Return True if self is negative definite, i.e., has negative discriminant with \(a < 0\).

EXAMPLES:

sage: Q = BinaryQF(-1, 3, -5)
sage: Q.is_positive_definite()
False
sage: Q.is_negative_definite()
True
is_nonsingular()

Return if this form is nonsingular, i.e., has non-zero discriminant.

EXAMPLES:

sage: Q = BinaryQF(1, 3, -5)
sage: Q.is_nonsingular()
True
sage: Q = BinaryQF(1, 2, 1)
sage: Q.is_nonsingular()
False
is_posdef()

Return True if self is positive definite, i.e., has negative discriminant with \(a > 0\).

EXAMPLES:

sage: Q = BinaryQF(195751, 37615, 1807)
sage: Q.is_positive_definite()
True
sage: Q = BinaryQF(195751, 1212121, -1876411)
sage: Q.is_positive_definite()
False
is_positive_definite()

Return True if self is positive definite, i.e., has negative discriminant with \(a > 0\).

EXAMPLES:

sage: Q = BinaryQF(195751, 37615, 1807)
sage: Q.is_positive_definite()
True
sage: Q = BinaryQF(195751, 1212121, -1876411)
sage: Q.is_positive_definite()
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, primitive_only=False)
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()

Return if self is reduced.

Let \(f = a x^2 + b xy + c y^2\) be a binary quadratic form of discriminant \(D\).

  • If \(f\) is positive definite (\(D < 0\) and \(a > 0\)), then \(f\) is reduced if and only if \(|b|\leq a \leq c\), and \(b\geq 0\) if either \(a = b\) or \(a = c\).

  • If \(f\) is negative definite (\(D < 0\) and \(a < 0\)), then \(f\) is reduced if and only if the positive definite form with coefficients \((-a, b, -c)\) is reduced.

  • If \(f\) is indefinite (\(D > 0\)), then \(f\) is reduced if and only if \(|\sqrt{D} - 2|a|| < b < \sqrt{D}\) or \(a = 0\) and \(-b < 2c \leq b\) or \(c = 0\) and \(-b < 2a \leq b\)

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

Examples using indefinite forms:

sage: f = BinaryQF(-1, 2, 2)
sage: f.is_reduced()
True
sage: BinaryQF(1, 9, 4).is_reduced()
False
sage: BinaryQF(1, 5, -1).is_reduced()
True
is_reducible()

Return if this form is reducible and cache the result.

A binary form \(q\) is called reducible if it is the product of two linear forms \(q = (a x + b y) (c x + d y)\), or equivalently if its discriminant is a square.

EXAMPLES:

sage: q = BinaryQF([1, 0, -1])
sage: q.is_reducible()
True
is_singular()

Return if self is singular, i.e., has zero discriminant.

EXAMPLES:

sage: Q = BinaryQF(1, 3, -5)
sage: Q.is_singular()
False
sage: Q = BinaryQF(1, 2, 1)
sage: Q.is_singular()
True
is_weakly_reduced()

Check 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
is_zero()

Return if self is identically zero.

EXAMPLES:

sage: Q = BinaryQF(195751, 37615, 1807)
sage: Q.is_zero()
False
sage: Q = BinaryQF(0, 0, 0)
sage: Q.is_zero()
True
matrix_action_left(M)

Return the binary quadratic form resulting from the left action of the 2-by-2 matrix \(M\) on self.

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 self.

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()

Return self 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(transformation=False, algorithm='default')

Return a reduced form equivalent to self.

INPUT:

  • self – binary quadratic form of non-square discriminant

  • transformation – boolean (default: False): if True, return both the reduced form and a matrix transforming self into the reduced form. Currently only implemented for indefinite forms.

  • algorithm – String. The algorithm to use: Valid options are:

    • 'default' – Let Sage pick an algorithm (default).

    • 'pari' – use PARI

    • 'sage' – use Sage

See also

is_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

Examples of reducing indefinite forms:

sage: f = BinaryQF(1, 0, -3)
sage: f.is_reduced()
False
sage: g = f.reduced_form(); g
x^2 + 2*x*y - 2*y^2
sage: g.is_reduced()
True

sage: q = BinaryQF(1, 0, -1)
sage: q.reduced_form()
x^2 + 2*x*y

sage: BinaryQF(1, 9, 4).reduced_form(transformation=True)
(
                     [ 0 -1]
4*x^2 + 7*x*y - y^2, [ 1  2]
)
sage: BinaryQF(3, 7, -2).reduced_form(transformation=True)
(
                       [1 0]
3*x^2 + 7*x*y - 2*y^2, [0 1]
)
sage: BinaryQF(-6, 6, -1).reduced_form(transformation=True)
(
                      [ 0 -1]
-x^2 + 2*x*y + 2*y^2, [ 1 -4]
)
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:

  • n – 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, proper=True)

Return representatives for the classes of binary quadratic forms of discriminant \(D\).

INPUT:

  • D – (integer) a discriminant

  • primitive_only – (boolean; default: True): if True, only return primitive forms.

  • proper – (boolean; default: True)

OUTPUT:

(list) A lexicographically-ordered list of inequivalent reduced representatives for the (im)proper equivalence classes of binary quadratic forms of discriminant \(D\). If primitive_only is True 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 \(\QQ(\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]