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

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

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 form
• n (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)]


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 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 $$Q(\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]


TESTS:

sage: BinaryQF_reduced_representatives(5)
Traceback (most recent call last):
...
ValueError: discriminant must be negative and congruent to 0 or 1 modulo 4