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

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

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