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

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

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 solution exists.

ALGORITHM: pari:qfbsolve

EXAMPLES:

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

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


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
2
sage: p = next_prime(2^20); p
1048583
sage: len(BinaryQF_reduced_representatives(-p))
689
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]