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()                                                              # needs sage.libs.pari
x^2 + 2*y^2
sage: Q(1, 1)
6

>>> from sage.all import *
>>> Q = BinaryQF([Integer(1), Integer(2), Integer(3)])
>>> Q
x^2 + 2*x*y  + 3*y^2
>>> Q.discriminant()
-8
>>> Q.reduced_form()                                                              # needs sage.libs.pari
x^2 + 2*y^2
>>> Q(Integer(1), Integer(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)[source]#

Bases: 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 xy + 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

>>> from sage.all import *
>>> b = BinaryQF([Integer(1), Integer(2), Integer(3)])
>>> b.discriminant()
-8
>>> b1 = BinaryQF(Integer(1), Integer(2), Integer(3))
>>> b1 == b
True
>>> R = ZZ['x, y']; (x, y,) = R._first_ngens(2)
>>> BinaryQF(x**Integer(2) + Integer(2)*x*y + Integer(3)*y**Integer(2)) == b
True
>>> BinaryQF(Integer(1), Integer(0), Integer(1))
x^2 + y^2
complex_point()[source]#

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()                                                     # needs sage.libs.pari
1.00000000000000*I

>>> from sage.all import *
>>> Q = BinaryQF([Integer(1), Integer(0), Integer(1)])
>>> Q.complex_point()                                                     # needs sage.libs.pari
1.00000000000000*I
content()[source]#

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

>>> from sage.all import *
>>> Q = BinaryQF(Integer(22), Integer(14), Integer(10))
>>> Q.content()
2
>>> Q = BinaryQF(Integer(4), Integer(4), -Integer(15))
>>> Q.content()
1
cycle(proper=False)[source]#

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]

>>> from sage.all import *
>>> Q = BinaryQF(Integer(14), Integer(17), -Integer(2))
>>> 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]
>>> 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]

>>> Q = BinaryQF(Integer(1), Integer(8), -Integer(3))
>>> 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]
>>> 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]

>>> Q = BinaryQF(Integer(1), Integer(7), -Integer(6))
>>> 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()[source]#

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

>>> from sage.all import *
>>> q = BinaryQF(Integer(1), -Integer(1), Integer(67))
>>> q.determinant()
267/4
determinant()[source]#

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

>>> from sage.all import *
>>> q = BinaryQF(Integer(1), -Integer(1), Integer(67))
>>> q.determinant()
267/4
discriminant()[source]#

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

>>> from sage.all import *
>>> Q = BinaryQF([Integer(1), Integer(2), Integer(3)])
>>> Q.discriminant()
-8
form_class()[source]#

Return the class of this form modulo equivalence.

EXAMPLES:

sage: F = BinaryQF([3, -16, 161])
sage: cl = F.form_class(); cl
Class of 3*x^2 + 2*x*y + 140*y^2
sage: cl.parent()
Form Class Group of Discriminant -1676
sage: cl.parent() is BQFClassGroup(-4*419)
True

>>> from sage.all import *
>>> F = BinaryQF([Integer(3), -Integer(16), Integer(161)])
>>> cl = F.form_class(); cl
Class of 3*x^2 + 2*x*y + 140*y^2
>>> cl.parent()
Form Class Group of Discriminant -1676
>>> cl.parent() is BQFClassGroup(-Integer(4)*Integer(419))
True
static from_polynomial(poly)[source]#

Construct a BinaryQF from a bivariate polynomial with integer coefficients. Inverse of polynomial().

EXAMPLES:

sage: R.<u,v> = ZZ[]
sage: f = u^2 + 419*v^2
sage: Q = BinaryQF.from_polynomial(f); Q
x^2 + 419*y^2
sage: Q.polynomial()
x^2 + 419*y^2
sage: Q.polynomial()(R.gens()) == f
True

>>> from sage.all import *
>>> R = ZZ['u, v']; (u, v,) = R._first_ngens(2)
>>> f = u**Integer(2) + Integer(419)*v**Integer(2)
>>> Q = BinaryQF.from_polynomial(f); Q
x^2 + 419*y^2
>>> Q.polynomial()
x^2 + 419*y^2
>>> Q.polynomial()(R.gens()) == f
True

The method fails if the given polynomial is not a quadratic form:

sage: BinaryQF.from_polynomial(u^3 - 5*v)
Traceback (most recent call last):
...
ValueError: polynomial has monomials of degree != 2

>>> from sage.all import *
>>> BinaryQF.from_polynomial(u**Integer(3) - Integer(5)*v)
Traceback (most recent call last):
...
ValueError: polynomial has monomials of degree != 2

…or if the coefficients aren’t integers:

sage: BinaryQF.from_polynomial(u^2/7 + v^2)
Traceback (most recent call last):
...
TypeError: no conversion of this rational to integer

>>> from sage.all import *
>>> BinaryQF.from_polynomial(u**Integer(2)/Integer(7) + v**Integer(2))
Traceback (most recent call last):
...
TypeError: no conversion of this rational to integer
has_fundamental_discriminant()[source]#

Return whether 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()                                      # needs sage.libs.pari
True

sage: Q = BinaryQF([2, 0, 2])
sage: Q.discriminant()
-16
sage: Q.has_fundamental_discriminant()                                      # needs sage.libs.pari
False

>>> from sage.all import *
>>> Q = BinaryQF([Integer(1), Integer(0), Integer(1)])
>>> Q.discriminant()
-4
>>> Q.has_fundamental_discriminant()                                      # needs sage.libs.pari
True

>>> Q = BinaryQF([Integer(2), Integer(0), Integer(2)])
>>> Q.discriminant()
-16
>>> Q.has_fundamental_discriminant()                                      # needs sage.libs.pari
False
is_equivalent(other, proper=True)[source]#

Return whether self is equivalent to other.

INPUT:

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

  • other – a binary quadratic form

EXAMPLES:

sage: # needs sage.libs.pari
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

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> Q3 = BinaryQF(Integer(4), Integer(4), Integer(15))
>>> Q2 = BinaryQF(Integer(4), -Integer(4), Integer(15))
>>> Q2.is_equivalent(Q3)
True
>>> a = BinaryQF([Integer(33), Integer(11), Integer(5)])
>>> b = a.reduced_form(); b
5*x^2 - x*y + 27*y^2
>>> a.is_equivalent(b)
True
>>> a.is_equivalent(BinaryQF((Integer(3), Integer(4), Integer(5))))
False

Some indefinite examples:

sage: Q1 = BinaryQF(9, 8, -7)
sage: Q2 = BinaryQF(9, -8, -7)
sage: Q1.is_equivalent(Q2, proper=True)                                     # needs sage.libs.pari
False
sage: Q1.is_equivalent(Q2, proper=False)                                    # needs sage.libs.pari
True

>>> from sage.all import *
>>> Q1 = BinaryQF(Integer(9), Integer(8), -Integer(7))
>>> Q2 = BinaryQF(Integer(9), -Integer(8), -Integer(7))
>>> Q1.is_equivalent(Q2, proper=True)                                     # needs sage.libs.pari
False
>>> Q1.is_equivalent(Q2, proper=False)                                    # needs sage.libs.pari
True
is_indef()[source]#

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

EXAMPLES:

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

>>> from sage.all import *
>>> Q = BinaryQF(Integer(1), Integer(3), -Integer(5))
>>> Q.is_indef()
True
is_indefinite()[source]#

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

EXAMPLES:

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

>>> from sage.all import *
>>> Q = BinaryQF(Integer(1), Integer(3), -Integer(5))
>>> Q.is_indef()
True
is_negative_definite()[source]#

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

>>> from sage.all import *
>>> Q = BinaryQF(-Integer(1), Integer(3), -Integer(5))
>>> Q.is_positive_definite()
False
>>> Q.is_negative_definite()
True
is_negdef()[source]#

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

>>> from sage.all import *
>>> Q = BinaryQF(-Integer(1), Integer(3), -Integer(5))
>>> Q.is_positive_definite()
False
>>> Q.is_negative_definite()
True
is_nonsingular()[source]#

Return whether 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

>>> from sage.all import *
>>> Q = BinaryQF(Integer(1), Integer(3), -Integer(5))
>>> Q.is_nonsingular()
True
>>> Q = BinaryQF(Integer(1), Integer(2), Integer(1))
>>> Q.is_nonsingular()
False
is_posdef()[source]#

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

>>> from sage.all import *
>>> Q = BinaryQF(Integer(195751), Integer(37615), Integer(1807))
>>> Q.is_positive_definite()
True
>>> Q = BinaryQF(Integer(195751), Integer(1212121), -Integer(1876411))
>>> Q.is_positive_definite()
False
is_positive_definite()[source]#

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

>>> from sage.all import *
>>> Q = BinaryQF(Integer(195751), Integer(37615), Integer(1807))
>>> Q.is_positive_definite()
True
>>> Q = BinaryQF(Integer(195751), Integer(1212121), -Integer(1876411))
>>> Q.is_positive_definite()
False
is_primitive()[source]#

Return whether 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]

>>> from sage.all import *
>>> Q = BinaryQF([Integer(6), Integer(3), Integer(9)])
>>> Q.is_primitive()
False

>>> Q = BinaryQF([Integer(1), Integer(1), Integer(1)])
>>> Q.is_primitive()
True

>>> Q = BinaryQF([Integer(2), Integer(2), Integer(2)])
>>> Q.is_primitive()
False

>>> rqf = BinaryQF_reduced_representatives(-Integer(23)*Integer(9), primitive_only=False)
>>> [qf.is_primitive() for qf in rqf]
[True, True, True, False, True, True, False, False, True]
>>> 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]
>>> [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]

See also

content()

is_reduced()[source]#

Return whether 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 [\(b > 0\), \(ac < 0\) and \((a-c)^2 < D\)] (equivalently 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

>>> from sage.all import *
>>> Q = BinaryQF([Integer(1), Integer(2), Integer(3)])
>>> Q.is_reduced()
False

>>> Q = BinaryQF([Integer(2), Integer(1), Integer(3)])
>>> Q.is_reduced()
True

>>> Q = BinaryQF([Integer(1), -Integer(1), Integer(1)])
>>> Q.is_reduced()
False

>>> Q = BinaryQF([Integer(1), Integer(1), Integer(1)])
>>> 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

>>> from sage.all import *
>>> f = BinaryQF(-Integer(1), Integer(2), Integer(2))
>>> f.is_reduced()
True
>>> BinaryQF(Integer(1), Integer(9), Integer(4)).is_reduced()
False
>>> BinaryQF(Integer(1), Integer(5), -Integer(1)).is_reduced()
True
is_reducible()[source]#

Return whether 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

>>> from sage.all import *
>>> q = BinaryQF([Integer(1), Integer(0), -Integer(1)])
>>> q.is_reducible()
True

Warning

Despite the similar name, this method is unrelated to reduction of binary quadratic forms as implemented by reduced_form() and is_reduced().

is_singular()[source]#

Return whether 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

>>> from sage.all import *
>>> Q = BinaryQF(Integer(1), Integer(3), -Integer(5))
>>> Q.is_singular()
False
>>> Q = BinaryQF(Integer(1), Integer(2), Integer(1))
>>> Q.is_singular()
True
is_weakly_reduced()[source]#

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

>>> from sage.all import *
>>> Q = BinaryQF([Integer(1), Integer(2), Integer(3)])
>>> Q.is_weakly_reduced()
False

>>> Q = BinaryQF([Integer(2), Integer(1), Integer(3)])
>>> Q.is_weakly_reduced()
True

>>> Q = BinaryQF([Integer(1), -Integer(1), Integer(1)])
>>> Q.is_weakly_reduced()
True
is_zero()[source]#

Return whether 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

>>> from sage.all import *
>>> Q = BinaryQF(Integer(195751), Integer(37615), Integer(1807))
>>> Q.is_zero()
False
>>> Q = BinaryQF(Integer(0), Integer(0), Integer(0))
>>> Q.is_zero()
True
matrix_action_left(M)[source]#

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

>>> from sage.all import *
>>> Q = BinaryQF([Integer(2), Integer(1), Integer(3)]); Q
2*x^2 + x*y + 3*y^2
>>> M = matrix(ZZ, [[Integer(1), Integer(2)], [Integer(3), Integer(5)]])
>>> Q.matrix_action_left(M)
16*x^2 + 83*x*y + 108*y^2
matrix_action_right(M)[source]#

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

>>> from sage.all import *
>>> Q = BinaryQF([Integer(2), Integer(1), Integer(3)]); Q
2*x^2 + x*y + 3*y^2
>>> M = matrix(ZZ, [[Integer(1), Integer(2)], [Integer(3), Integer(5)]])
>>> Q.matrix_action_right(M)
32*x^2 + 109*x*y + 93*y^2
polynomial()[source]#

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

>>> from sage.all import *
>>> Q = BinaryQF([Integer(1), Integer(2), Integer(3)])
>>> Q.polynomial()
x^2 + 2*x*y + 3*y^2

>>> Q = BinaryQF([-Integer(1), -Integer(2), Integer(3)])
>>> Q.polynomial()
-x^2 - 2*x*y + 3*y^2

>>> Q = BinaryQF([Integer(0), Integer(0), Integer(0)])
>>> Q.polynomial()
0
static principal(D)[source]#

Return the principal binary quadratic form of the given discriminant.

EXAMPLES:

sage: BinaryQF.principal(8)
x^2 - 2*y^2
sage: BinaryQF.principal(5)
x^2 + x*y - y^2
sage: BinaryQF.principal(4)
x^2 - y^2
sage: BinaryQF.principal(1)
x^2 + x*y
sage: BinaryQF.principal(-3)
x^2 + x*y + y^2
sage: BinaryQF.principal(-4)
x^2 + y^2
sage: BinaryQF.principal(-7)
x^2 + x*y + 2*y^2
sage: BinaryQF.principal(-8)
x^2 + 2*y^2

>>> from sage.all import *
>>> BinaryQF.principal(Integer(8))
x^2 - 2*y^2
>>> BinaryQF.principal(Integer(5))
x^2 + x*y - y^2
>>> BinaryQF.principal(Integer(4))
x^2 - y^2
>>> BinaryQF.principal(Integer(1))
x^2 + x*y
>>> BinaryQF.principal(-Integer(3))
x^2 + x*y + y^2
>>> BinaryQF.principal(-Integer(4))
x^2 + y^2
>>> BinaryQF.principal(-Integer(7))
x^2 + x*y + 2*y^2
>>> BinaryQF.principal(-Integer(8))
x^2 + 2*y^2
reduced_form(transformation=False, algorithm='default')[source]#

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 whose matrix_action_right() transforms self into the reduced form.

  • algorithm – string; the algorithm to use. Valid options are:

See also

EXAMPLES:

sage: a = BinaryQF([33, 11, 5])
sage: a.is_reduced()
False
sage: b = a.reduced_form(); b                                               # needs sage.libs.pari
5*x^2 - x*y + 27*y^2
sage: b.is_reduced()                                                        # needs sage.libs.pari
True

sage: a = BinaryQF([15, 0, 15])
sage: a.is_reduced()
True
sage: b = a.reduced_form(); b                                               # needs sage.libs.pari
15*x^2 + 15*y^2
sage: b.is_reduced()                                                        # needs sage.libs.pari
True

>>> from sage.all import *
>>> a = BinaryQF([Integer(33), Integer(11), Integer(5)])
>>> a.is_reduced()
False
>>> b = a.reduced_form(); b                                               # needs sage.libs.pari
5*x^2 - x*y + 27*y^2
>>> b.is_reduced()                                                        # needs sage.libs.pari
True

>>> a = BinaryQF([Integer(15), Integer(0), Integer(15)])
>>> a.is_reduced()
True
>>> b = a.reduced_form(); b                                               # needs sage.libs.pari
15*x^2 + 15*y^2
>>> b.is_reduced()                                                        # needs sage.libs.pari
True

Examples of reducing indefinite forms:

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

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

sage: BinaryQF(1, 9, 4).reduced_form(transformation=True)                   # needs sage.libs.pari
(
                     [ 0 -1]
4*x^2 + 7*x*y - y^2, [ 1  2]
)
sage: BinaryQF(3, 7, -2).reduced_form(transformation=True)                  # needs sage.libs.pari
(
                       [1 0]
3*x^2 + 7*x*y - 2*y^2, [0 1]
)
sage: BinaryQF(-6, 6, -1).reduced_form(transformation=True)                 # needs sage.libs.pari
(
                      [ 0 -1]
-x^2 + 2*x*y + 2*y^2, [ 1 -4]
)

>>> from sage.all import *
>>> f = BinaryQF(Integer(1), Integer(0), -Integer(3))
>>> f.is_reduced()
False
>>> g = f.reduced_form(); g                                               # needs sage.libs.pari
x^2 + 2*x*y - 2*y^2
>>> g.is_reduced()                                                        # needs sage.libs.pari
True

>>> q = BinaryQF(Integer(1), Integer(0), -Integer(1))
>>> q.reduced_form()                                                      # needs sage.libs.pari
x^2 + 2*x*y

>>> BinaryQF(Integer(1), Integer(9), Integer(4)).reduced_form(transformation=True)                   # needs sage.libs.pari
(
                     [ 0 -1]
4*x^2 + 7*x*y - y^2, [ 1  2]
)
>>> BinaryQF(Integer(3), Integer(7), -Integer(2)).reduced_form(transformation=True)                  # needs sage.libs.pari
(
                       [1 0]
3*x^2 + 7*x*y - 2*y^2, [0 1]
)
>>> BinaryQF(-Integer(6), Integer(6), -Integer(1)).reduced_form(transformation=True)                 # needs sage.libs.pari
(
                      [ 0 -1]
-x^2 + 2*x*y + 2*y^2, [ 1 -4]
)
small_prime_value(Bmax=1000)[source]#

Return 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()                                                # needs sage.libs.pari
....:  for Q in BinaryQF_reduced_representatives(-23, primitive_only=True)]
[23, 2, 2]
sage: [Q.small_prime_value()                                                # needs sage.libs.pari
....:  for Q in BinaryQF_reduced_representatives(-47, primitive_only=True)]
[47, 2, 2, 3, 3]

>>> from sage.all import *
>>> [Q.small_prime_value()                                                # needs sage.libs.pari
...  for Q in BinaryQF_reduced_representatives(-Integer(23), primitive_only=True)]
[23, 2, 2]
>>> [Q.small_prime_value()                                                # needs sage.libs.pari
...  for Q in BinaryQF_reduced_representatives(-Integer(47), primitive_only=True)]
[47, 2, 2, 3, 3]
solve_integer(n, algorithm, _flag)[source]#

Solve \(Q(x, y) = n\) in integers \(x\) and \(y\) where \(Q\) is this quadratic form.

INPUT:

  • n – a positive integer or a \(:sage:`~sage.structure.factorization.Factorization\) object

  • algorithm – "general" (default) or "cornacchia"

  • _flag – 1, 2 (default) or 3; passed onto the pari function``qfbsolve``. For internal use only.

To use the Cornacchia algorithm, the quadratic form must have \(a=1\) and \(b=0\) and \(c>0\), and n must be a prime or four times a prime (but this is not checked).

OUTPUT:

A tuple \((x, y)\) of integers satisfying \(Q(x, y) = n\), or None if no solution exists.

ALGORITHM: pari:qfbsolve or pari:qfbcornacchia

TODO:: Replace \(_flag\) with human-readable parameters c.f. Issue #37119

EXAMPLES:

sage: Q = BinaryQF([1, 0, 419])
sage: Q.solve_integer(773187972)                                            # needs sage.libs.pari
(4919, 1337)

>>> from sage.all import *
>>> Q = BinaryQF([Integer(1), Integer(0), Integer(419)])
>>> Q.solve_integer(Integer(773187972))                                            # needs sage.libs.pari
(4919, 1337)

If \(Q\) is of the form \([1,0,c]\) as above and \(n\) is a prime (or four times a prime whenever \(c \equiv 3 \pmod 4\)), then Cornacchia’s algorithm can be used, which is typically much faster than the general method:

sage: Q = BinaryQF([1, 0, 12345])
sage: n = 2^99 + 5273
sage: Q.solve_integer(n)                                                    # needs sage.libs.pari
(-67446480057659, 7139620553488)
sage: Q.solve_integer(n, algorithm='cornacchia')                            # needs sage.libs.pari
(67446480057659, 7139620553488)
sage: timeit('Q.solve_integer(n)')                          # not tested
125 loops, best of 3: 3.13 ms per loop
sage: timeit('Q.solve_integer(n, algorithm="cornacchia")')  # not tested
625 loops, best of 3: 18.6 μs per loop

>>> from sage.all import *
>>> Q = BinaryQF([Integer(1), Integer(0), Integer(12345)])
>>> n = Integer(2)**Integer(99) + Integer(5273)
>>> Q.solve_integer(n)                                                    # needs sage.libs.pari
(-67446480057659, 7139620553488)
>>> Q.solve_integer(n, algorithm='cornacchia')                            # needs sage.libs.pari
(67446480057659, 7139620553488)
>>> timeit('Q.solve_integer(n)')                          # not tested
125 loops, best of 3: 3.13 ms per loop
>>> timeit('Q.solve_integer(n, algorithm="cornacchia")')  # not tested
625 loops, best of 3: 18.6 μs per loop

sage: # needs sage.libs.pari
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]
[(1, -1), (1, -1), (-1, -1)]

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> Qs = BinaryQF_reduced_representatives(-Integer(23), primitive_only=True)
>>> Qs
[x^2 + x*y + 6*y^2, 2*x^2 - x*y + 3*y^2, 2*x^2 + x*y + 3*y^2]
>>> [Q.solve_integer(Integer(3)) for Q in Qs]
[None, (0, -1), (0, -1)]
>>> [Q.solve_integer(Integer(5)) for Q in Qs]
[None, None, None]
>>> [Q.solve_integer(Integer(6)) for Q in Qs]
[(1, -1), (1, -1), (-1, -1)]

sage: # needs sage.libs.pari
sage: n = factor(126)
sage: Q = BinaryQF([1, 0, 5])
sage: Q.solve_integer(n)
(11, -1)

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> n = factor(Integer(126))
>>> Q = BinaryQF([Integer(1), Integer(0), Integer(5)])
>>> Q.solve_integer(n)
(11, -1)
sage.quadratic_forms.binary_qf.BinaryQF_reduced_representatives(D, primitive_only=False, proper=True)[source]#

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]

>>> from sage.all import *
>>> BinaryQF_reduced_representatives(-Integer(4))
[x^2 + y^2]

>>> BinaryQF_reduced_representatives(-Integer(163))
[x^2 + x*y + 41*y^2]

>>> BinaryQF_reduced_representatives(-Integer(12))
[x^2 + 3*y^2, 2*x^2 + 2*x*y + 2*y^2]

>>> BinaryQF_reduced_representatives(-Integer(16))
[x^2 + 4*y^2, 2*x^2 + 2*y^2]

>>> BinaryQF_reduced_representatives(-Integer(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()                                 # needs sage.rings.number_field
2

sage: # needs sage.libs.pari
sage: p = next_prime(2^20); p
1048583
sage: len(BinaryQF_reduced_representatives(-p))
689
sage: QuadraticField(-p, 'a').class_number()                                    # needs sage.rings.number_field
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]

>>> from sage.all import *
>>> len(BinaryQF_reduced_representatives(-Integer(13)*Integer(4)))
2
>>> QuadraticField(-Integer(13)*Integer(4), 'a').class_number()                                 # needs sage.rings.number_field
2

>>> # needs sage.libs.pari
>>> p = next_prime(Integer(2)**Integer(20)); p
1048583
>>> len(BinaryQF_reduced_representatives(-p))
689
>>> QuadraticField(-p, 'a').class_number()                                    # needs sage.rings.number_field
689
>>> BinaryQF_reduced_representatives(-Integer(23)*Integer(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]
>>> BinaryQF_reduced_representatives(-Integer(23)*Integer(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]