Binary quadratic form

A binary quadratic form ( in this article often only short form called ), in mathematics, a quadratic form in two variables, ie, a polynomial of the form

Wherein the coefficients of the shape. The form with

To write for short as

The following binary quadratic forms in number theory are considered, ie we consider only integer solutions. Quadratic forms are a classic part of number theory. Adrien -Marie Legendre already dealt with integer binary and ternary quadratic forms. But it was Carl Friedrich Gauss reasoned in his work Disquisitiones Arithmeticae (Chapter 5) a comprehensive theory of binary quadratic forms.

• 5.1 Definition of the equivalence
• 5.2 Properties of equivalent forms

• 6.1 definiteness of forms
• 6.2 forms of the same discriminant

• 8.1 General definition of composition
• 8.2 Calculation of composition
• 8.3 Example
• 8.4 further evidence

Definitions

Formally, a binary quadratic form over a commutative ring with unit element is a homogeneous polynomial of degree 2 in two indeterminates with coefficients in.

The binary square shapes over the field of real numbers referred to as real binary square shapes, the binary square shapes on the ring of integers called binary integer quadratic forms.

An integer binary quadratic forms is called

• Ambiguous when the average coefficient is a multiple of the first coefficient so applies to.
• Primitive if the coefficients are relatively prime, ie (see greatest common divisor ) holds.

The discriminant of a binary quadratic form is defined as.

Problem areas

In the theory of binary quadratic forms following questions are of interest:

Representation of integers

Here, a represents an integer form, with, if there is. The couple then called a representation of by. The representation is called primitive if and only if.

Minimum of forms

In this case, the minimum shape is defined by a.

Equivalence of forms

Details for equivalence concept, see below.

Benefit

Using the theory of binary quadratic forms can solve the following problems:

Matrix representations

Assigns one of a shape of the triangular matrix, it is, and can also be written as, where the transposition means.

Alternatively, a symmetric 2x2 matrix are used: then also applies, however, only applies if 2 is invertible. For integer binary quadratic forms, however.

The corresponding symmetric matrix is referred to with also short, so so true.

Using the symmetric matrix form, the discriminant of the form can be represented as

.

Equivalence of forms

Definition of equivalence

A ( unimodular ) substitution of the variables of a shape (that is, the particular linear element group throughout the figures ) defining a transformation of the form into a shape equivalent to the representative matrix. Two forms so called equivalent if there is a matrix with. In this case, to write or. It then applies a form.

Motivated by this definition is the fact that equivalent forms represent the same numbers and the representation of the number by which a form of the representation of the number by the equivalent form results directly as if.

Note: The so defined equivalent is often referred to as "real equivalence " and general equivalence term based on transformation matrices (that element of the general linear array over the integers ).

Properties equivalent forms

Equivalent forms have the following properties that are then the equivalence classes F ( amount of each equivalent forms: ) is transmitted.

• Two equivalent forms have the same discriminant. Thus, the discriminant of the equivalence class can be defined as.
• Two equivalent forms represent the same numbers.

Classification of forms

Definiteness of forms

Forms can be classified according to their definiteness.

A binary quadratic form is called

• Is indefinite when (but not for - in this case, the shape of degenerate )
• Definite if. Continues, then ( a, b, c ) is positive definite, otherwise ( ) is negative definite.

These definitions correspond to the definiteness of the corresponding forms of the matrices.

Regarding the representation of integers resulting from the definiteness that positive definite forms only positive and negative definite forms represent only negative numbers. Indefinite shapes can represent both positive and negative numbers.

Note: In the case of one speaks of (positive or negative) semidefinite forms ( or when ).

Forms of the same discriminant

Each integer, which may be a discriminant ( or that is, for example, -8, -7, -4, -3, 0, 1, 4, 5, 8), all integral molding with this number can be assigned as a discriminant. However, considering the equivalence classes of shapes, it is per discriminant only a finite number of equivalence classes of integral molding using this discriminant. This number is also called the class number (eg).

Reduction of integer binary square shapes

In general, the aim is to find a suitable representative for each equivalence class. In the case of binary quadratic forms of this representative should have as ( magnitude ) small coefficients. This requirement is, depending on the definiteness of the form (which is the same for all forms of an equivalence class because of the invariance of the discriminant ) specifies:

• For positive definite forms ( D < 0, a> 0):

• For negative definite forms ( D < 0, a < 0):

• For non-degenerate indefinite forms ( D> 0):

• For a ( according to Lagarias ):

• For:

Binary quadratic forms that meet the above conditions is called reduced.

Examples:

• For positive definite forms ( D < 0, a> 0): [ 1,0,1 ], [ 1,1,1 ], [ 1,1,2 ], [ 2,1,2 ], [ 2 - 1,3 ], [ 2,2,3 ], [ 6,5,7 ], etc.
• For negative definite shapes ( D < 0, a < 0): [ -1,0, -1 ], [ -1, -1, -1 ], [ -1, -1, -2 ], [ -2, -1, -2 ], [ -2.1, -3 ], [ -2, -2, -3 ], [ -6, -5, -7], etc.
• For non-degenerate indefinite forms ( D> 0 ), [1,4, -4 ], etc.
• For a: [0, 2, 0], [ 0,2,1 ], [ 0,3,1 ], [ 0,3,2 ], etc.
• For: [ 0,0,0 ], [ 0,0,1 ], [ 0,0, -1], etc.

Due to the transformation described initially obtained for each binary quadratic form an equivalent reduced form ( this is for definite forms clearly ).

Generally called transformation, which reduces the size of the coefficient reduction. Means reductions can therefore be determined whether two forms are equivalent:

• Two non-degenerate indefinite forms are equivalent if their reduced forms are equivalent in a Cycles reduced forms (see Buell, Theorem 3.5).
• Otherwise are two forms are equivalent if their equivalent reduced forms are identical.

The transformation matrices M can be uniquely represented by products of elementary matrices.

If we restrict ourselves but on positive transformation matrices (ie, the coefficients of which are greater than or equal to zero ), this can be represented by the elementary matrices.

Determination of the powers of the elementary matrices H and L shown in these figures is carried out analogously to the extended Euclidean algorithm by means of algorithms for determining the greatest common divisor of two numbers. This, however, gives no reduced forms - this are still a few transformations with the elementary matrices S and T are necessary.

Already Gauss described in 1801 in the " Disquisitiones Arithmeticae " Algorithms for the reduction of quadratic forms. The terms of these algorithms were estimated in 1980 by Lagarias, where for indefinite forms in the worst case exponential running time can occur. But Lagarias converted the Gaussian algorithm down so that he in any case polynomial running time ( asymptotically, an upper bound for the multiplication of numbers of binary length n ) has. For degenerate forms he could even show the asymptotic estimate for the runtime.

Rickert 1989 optimized reduction algorithm for definite forms, but without improving the asymptotic running time bound

A fast algorithm for reducing arbitrary binary quadratic forms Schönhage has developed and published in 1991. This has the asymptotic running time bound of.

Composition

General definition of composition

If and binary quadratic forms are, then that means a composition of and, if there are two bilinear forms, such that for all.

In the event that and integral forms with common discriminant D and each prime coefficients, Gauss proved the existence of a composition algorithm, and it has shown that the equivalence classes of these shapes form an abelian group, where the group operation by the above Composition is induced. This group is called the form class group.

Calculation of composition

One possible method for calculating the composition of two forms of discriminant D and provides the following algorithm:

Then we have.

The determination of ( steps 1 and 2 ) is carried out after the extended Euclidean algorithm.

Even if and are reduced, is not reduced in general. Needs to determine the appropriate form class group be reduced so first.

The neutral element of the form class group is the main class, ie the equivalence class that contains the main form of discriminant D. The main shape of the discriminant D is the reduced form with 1 as the first coefficient:

• Negative for D and just:
• Negative for D and odd:
• Positive for D:

Example

Be, then the equivalence classes of the form class group represented by the following reduced forms:

It is therefore and.

It should now be calculated:

So,

Further notes

In a representation to the composition of integral binary quadratic forms of various discriminant.

A modern application of Gaußkomposition to the problem of prime factorization is found in.

Add to another group structures found on equivalence classes of different shape families.

In a fast algorithm for the calculation of media will be described.

Markoff forms

A further categorization of rational indefinite binary quadratic forms is derived from Markov. The starting point is the question of how much such a shape much opposed to accept the value 0. For this purpose, a mold f ( x, y) = ax ² bxy cy ² value

Assigned. The amount of these values ​​is called the Markoffspektrum.

It turns out that the largest value of the Markoffspektrums is equal to that Markoffspektrum in the interval has no accumulation points that each of the ( isolated ) points of Markoffspektrums is in one-to- one relationship with each one equivalence class, each with different discriminant, and that these forms closely related to the integer solutions of the diophantine equation ( the Markov figures) represent.

Scilab Code for plotting of binary quadratic forms

X = [ -5:0.1:5 ]; y = [ -5:0.1:5 ];   m = length (x);   M = zeros (m, m);   for i = 1: m     for j = 1: m       M (i) (j) = x (j) ^ 2 4 * x (j) * Y (i) y (i ) ^ 2; / / quadratic form     end end / / disp (M)   clf; plot3d ( X, Y, M); References