Binary square shape

A binary square form (often just called form in this article ) is a square form in mathematics in two variables , i.e. a polynomial of the shape ${\displaystyle x,y}$

${\displaystyle ax^{2}+bxy+cy^{2}\,}$,

where are the coefficients of the form. The shape with ${\displaystyle a,b,c}$ ${\displaystyle f}$

${\displaystyle f(x,y)=ax^{2}+bxy+cy^{2}\,}$

is also written briefly as

${\displaystyle f=(a,b,c)\,}$.

In the following, binary quadratic forms are considered in number theory , i.e. only integer solutions are considered. Square shapes are a classic part of number theory. Joseph-Louis Lagrange was already concerned with integer binary and ternary quadratic forms. But it was only Carl Friedrich Gauß who founded a comprehensive theory of binary quadratic forms in his work Disquisitiones Arithmeticae (Chapter 5).

Definitions

Formally, a binary square form over a commutative ring with one element is a homogeneous polynomial of degree  2 in two indeterminate with coefficients in . ${\displaystyle A}$ ${\displaystyle A}$

The binary square shapes above the body of real numbers are called real binary square shapes, and the binary square shapes above the ring of whole numbers are called integer binary square shapes.

An integral binary quadratic forms is ${\displaystyle f=(a,b,c)}$

• ambiguous when the average coefficient is a multiple of the first coefficient, ie with applicable. ${\displaystyle b=ka}$ ${\displaystyle k\in \mathbb {Z} }$
• primitive , if the coefficients are relatively prime, i.e. (see greatest common divisor ). ${\displaystyle \operatorname {ggT} (a,b,c)=1\,}$

The discriminant of a binary quadratic form is defined as . ${\displaystyle D_{f}}$ ${\displaystyle f=(a,b,c)}$ ${\displaystyle D_{f}:=b^{2}-4ac\,}$

Problem areas

The following questions are of interest in the theory of binary quadratic forms:

Representation of whole numbers

1. Which numbers are represented by a shape?
2. How many and which representations does a number have by a form?

A shape represents an integer if there is with . The pair is then called a representation of through . The representation is called primitive if it holds . ${\displaystyle f}$ ${\displaystyle n\in \mathbb {Z} }$ ${\displaystyle (x_{0},y_{0})\in \mathbb {Z} ^{2}}$ ${\displaystyle f(x_{0},y_{0})=n}$ ${\displaystyle (x_{0},y_{0})}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle \operatorname {ggT} (x_{0},y_{0})=1\,}$

Minimum of forms

1. Which minimum has a shape?

The minimum of a shape is defined by . ${\displaystyle \lambda _{1}(f)}$ ${\displaystyle f}$ ${\displaystyle \lambda _{1}(f):=\inf\{{\sqrt {|f(x,y)|}}:(x,y)\in \mathbb {Z} ^{2},(x,y)\neq (0,0)\}\,}$

Equivalence of forms

1. Are two given forms equivalent?
2. With which matrix can two equivalent forms be converted into one another?

For details on the term equivalence see below .

Use

Using the theory of binary quadratic forms, the following problems can be solved:

1. Finding solutions to Diophantine equations of the form (using representations of integers by binary quadratic forms) ${\displaystyle (x,y)\in \mathbb {Z} }$ ${\displaystyle ax^{2}+bxy+cy^{2}=n}$
2. Finding a shortest vector in a lattice (using the minimum of binary quadratic forms)
3. Factoring whole numbers (using ambiguous forms)
4. Problems of cryptography (via relationships to quadratic number fields )

Matrix representations

If one assigns a shape via the triangular matrix , then is and can also be written as , where the means transposition . ${\displaystyle f=(a,b,c)}$ ${\displaystyle A}$ ${\displaystyle M_{d}(f)={\begin{pmatrix}a&b\\0&c\end{pmatrix}}}$ ${\displaystyle M_{d}(f)\in A^{2\times 2}}$ ${\displaystyle f}$ ${\displaystyle f(x,y)=(x,y)M_{d}(f)(x,y)^{T}\,}$ ${\displaystyle \ldots ^{T}}$

Alternatively, a symmetric matrix can be used: then the same applies , but only applies if 2 is invertible in. For integer binary quadratic forms but . ${\displaystyle (2\times 2)}$ ${\displaystyle M_{s}(f)={\begin{pmatrix}a&{\frac {b}{2}}\\{\frac {b}{2}}&c\end{pmatrix}}}$ ${\displaystyle f(x,y)=(x,y)M_{s}(f)(x,y)^{T}\,}$ ${\displaystyle M_{s}(f)\in A^{2\times 2}}$ ${\displaystyle A}$ ${\displaystyle f}$ ${\displaystyle M_{s}(f)\in \mathbb {Q} ^{2\times 2}}$

To symmetrical corresponding matrix is also referred to briefly , ie so that: . ${\displaystyle f}$ ${\displaystyle M_{s}(f)}$ ${\displaystyle [a,b,c]}$ ${\displaystyle f(x,y)=(x,y)[a,b,c](x,y)^{T}\,}$

With the help of the symmetrical matrix of a shape, the discriminant of the shape can be represented as ${\displaystyle [a,b,c]}$

${\displaystyle D=b^{2}-4ac=-4\cdot \det[a,b,c]\,}$.

Equivalence of forms

Definition of equivalence

A (unimodular) substitution of the variables of a form with (i.e. element of the special linear group over the whole numbers) determines a transformation of the form into an equivalent form with the representing matrix . So two forms are called equivalent if there is a matrix with . In this case you write or . It then applies to a form . ${\displaystyle (x',y')=U(x,y)^{T}\,}$ ${\displaystyle U\in SL_{2}(\mathbb {Z} )}$ ${\displaystyle U}$ ${\displaystyle (a,b,c)\,}$ ${\displaystyle (\alpha ,\beta ,\gamma )\,}$ ${\displaystyle U^{T}[a,b,c]U=[\alpha ,\beta ,\gamma ]\,}$ ${\displaystyle U\in SL_{2}(\mathbb {Z} )}$ ${\displaystyle U^{T}[a,b,c]U=[\alpha ,\beta ,\gamma ]\,}$ ${\displaystyle [\alpha ,\beta ,\gamma ]\sim [a,b,c]\,}$ ${\displaystyle (a,b,c)=(\alpha ,\beta ,\gamma )U\,}$ ${\displaystyle (fU)(x,y)=f(U(x,y))\,}$ ${\displaystyle f}$

This definition is motivated by the fact that equivalent forms represent the same numbers and the representation of the number by the one form results directly from the representation of the number by the equivalent form as if . ${\displaystyle (x,y)\,}$ ${\displaystyle f}$ ${\displaystyle (x',y')\,}$ ${\displaystyle g}$ ${\displaystyle (x,y)=U(x',y')^{T}\,}$ ${\displaystyle f=gU\,}$

Note: The equivalence defined in this way is often also referred to as "real equivalence" and the general concept of equivalence is based on transformation matrices (i.e. element of the general linear group over the whole numbers). ${\displaystyle U\in GL_{2}(\mathbb {Z} )}$ ${\displaystyle U}$

Properties of equivalent shapes

Equivalent shapes have the following properties, which are then transferred to the equivalence classes F (set of equivalent shapes in each case:) . ${\displaystyle F(a,b,c):=\{(a',b',c')|(a',b',c')\sim (a,b,c)\}\,}$

• two equivalent forms have the same discriminant. Thus the discriminant of the equivalence class ${\displaystyle D_{F}}$ can be defined as . ${\displaystyle D_{F(a,b,c)}:=D_{(a,b,c)}}$
• two equivalent forms represent the same numbers.

Classification of forms

Definiteness of forms

Shapes can be classified according to their definiteness .

A binary square shape is called ${\displaystyle f=(a,b,c)}$

• indefinite if (but not for - in this case the form is degenerate ), ${\displaystyle D_{f}>0\,}$ ${\displaystyle D=n^{2}\,}$ ${\displaystyle n\in \mathbb {N} \,}$
• definitely if . If further , then (a, b, c) is positive definite , otherwise ( ) negative definite . ${\displaystyle D_{f}<0\,}$ ${\displaystyle a>0}$ ${\displaystyle a<0}$

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

With regard to the representation of whole numbers, the definiteness implies that positive definite forms only represent positive and negative definite forms only negative numbers. Indefinite forms can represent both positive and negative numbers.

Note: In the case of one speaks of ( positive or negative ) semidefinite forms (if or ). ${\displaystyle D_{f}\leq 0}$ ${\displaystyle a>0}$ ${\displaystyle a<0}$

Forms of the same discriminant

Any integer that can be a discriminant (i.e., or , e.g., -8, -7, -4, -3, 0, 1, 4, 5, 8) can be assigned any of the integer forms with that number as a discriminant become. However, if one considers the equivalence classes of forms, then there is only a finite number of equivalence classes of integer forms with this discriminant per discriminant. This number is also called the class number (e.g. ). ${\displaystyle n\in \mathbb {Z} }$ ${\displaystyle n\equiv 0(\operatorname {mod} 4)}$ ${\displaystyle n\equiv 1(\operatorname {mod} 4)}$ ${\displaystyle h(n)}$ ${\displaystyle h(-23)=3}$

Reduction of integer binary quadratic forms

In general, one endeavors to find a suitable representative for each equivalence class. In the case of the binary quadratic forms, this representative should have coefficients that are as small as possible (in terms of amount). Depending on the definition of the form (which is the same for all forms of an equivalence class due to the invariance of the discriminants), this requirement is specified:

• for positive definite forms : ${\displaystyle (D<0,a>0)}$

after Rickert or Buell (extended): either or ${\displaystyle -a<b\leq a<c}$ ${\displaystyle 0\leq b\leq a=c}$

or equivalent according to Gauss: ${\displaystyle |b|\leq a\leq \min(c,{\sqrt {-D/3}})}$

• for negative definite forms : ${\displaystyle (D<0,a<0)}$

for the conditions are for positive definite forms ${\displaystyle \left[-a,-b,-c\right]}$

• for non-degenerate indefinite forms : ${\displaystyle (D>0)}$

after Schönhage: and ${\displaystyle {\sqrt {D}}-\min(|2c|,|2a|)<b<{\sqrt {D}}}$ ${\displaystyle b>0\,}$

or equivalent according to Gauss, Lagarias or Buell: and ${\displaystyle 0<b<{\sqrt {D}}}$ ${\displaystyle {\sqrt {D}}-b<|2a|<{\sqrt {D}}+b}$

• for for one (after Lagarias): ${\displaystyle D=n^{2}}$ ${\displaystyle n\in \mathbb {N} ^{+}}$

${\displaystyle b=n}$ and ${\displaystyle 0=a\leq c\leq n-1}$

• for : ${\displaystyle D=0}$

${\displaystyle a=0\,}$ and ${\displaystyle b=0\,}$

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

Examples:

• for positive definite forms : [1,0,1], [1,1,1], [1,1,2], [2,1,2], [2, -1,3], [2,2 , 3], [6,5,7] etc. ${\displaystyle (D<0,a>0)}$
• for negative definite forms : [-1,0, -1], [-1, -1, -1], [-1, -1, -2], [-2, -1, -2], [- 2,1, -3], [-2, -2, -3], [-6, -5, -7] etc. ${\displaystyle (D<0,a<0)}$
• for non-degenerate indefinite forms : [1,4, -4] etc. ${\displaystyle (D>0)}$ ${\displaystyle [1,2,-1]\sim [-1,2,1]\,}$
• for for a : [0, 2, 0], [0,2,1], [0,3,1], [0,3,2] etc. ${\displaystyle D=n^{2}}$ ${\displaystyle n\in \mathbb {N} ^{+}}$
• for : [0,0,0], [0,0,1], [0,0, -1] etc. ${\displaystyle D=0}$

The transformation described at the beginning gives an equivalent reduced form for every binary quadratic form (this is unique for definite forms).

In general, a transformation that reduces the size of the coefficient is called a reduction . By means of reductions it can be determined whether two forms are equivalent:

• two non-degenerate indefinite forms are equivalent if their equivalent reduced forms lie in a cycle of reduced forms (see Buell, Theorem 3.5).
• otherwise, two forms are equivalent if their equivalent reduced forms are identical.

The transformation can be uniquely determined by products of elementary matrices represent: . ${\displaystyle M}$ ${\displaystyle S={\begin{pmatrix}1&1\\0&1\end{pmatrix}};T={\begin{pmatrix}0&-1\\1&0\end{pmatrix}}}$ ${\displaystyle M=S^{i_{1}}T^{j_{1}}S^{i_{2}}T^{j_{2}}\dots S^{i_{n}}T^{j_{n}}}$

Limiting the discussion, however, (i.e., the coefficients of which are greater than or equal to zero..) Positive transformation matrices, they can be also by the elementary matrices represent: . ${\displaystyle H={\begin{pmatrix}1&1\\0&1\end{pmatrix}};L={\begin{pmatrix}1&0\\1&1\end{pmatrix}}}$ ${\displaystyle M=L^{i_{1}}H^{j_{1}}L^{i_{2}}H^{j_{2}}\dots L^{i_{n}}H^{j_{n}}}$

The determination of the powers of the elementary matrices and in these representations is carried out by algorithms analogous to the extended Euclidean algorithm for determining the greatest common divisor of two numbers. However, this does not yet result in reduced forms - a few more transformations with the elementary matrices and are necessary. ${\displaystyle H}$ ${\displaystyle L}$ ${\displaystyle S}$ ${\displaystyle T}$

Already Gauss described algorithms for the reduction of square forms in the Disquisitiones Arithmeticae in 1801 . The running times of these algorithms were estimated by Lagarias in 1980, whereby an exponential running time can occur for indefinite forms in the worst case. Lagarias modified the Gaussian algorithm in such a way that it always has a polynomial running time (asymptotically , with an upper bound for the multiplication of numbers of binary length n). For degenerate forms he could even show the asymptotic estimate for the running time. ${\displaystyle O(n\cdot \mu (n))}$ ${\displaystyle \mu (n)}$ ${\displaystyle O(\log n\cdot \mu (n))}$

In 1989 Rickert optimized the reduction algorithm for definite forms, but without improving the asymptotic term limit

Schönhage developed a fast algorithm for reducing arbitrary binary quadratic forms and published it in 1991. This has the asymptotic term bound of . ${\displaystyle O(\log n\cdot \mu (n))}$

composition

General definition of the composition

If and are binary quadratic forms, then a composition of and is called if there are two bilinear forms such that applies to all . ${\displaystyle f,g}$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle B_{1},B_{2}\colon \mathbb {Z} ^{2}\times \mathbb {Z} ^{2}\to \mathbb {Z} }$ ${\displaystyle f(x)\cdot g(y)=F(B_{1}(x,y),B_{2}(x,y))}$ ${\displaystyle x,y\in \mathbb {Z} ^{2}}$

In the event that and are integer forms with a common discriminant D and in each case coprime coefficients, Gauss has proven the existence of a composition algorithm, and he has shown that the -equivalence classes of these forms form an Abelian group , the group operation being given by the above. Composition is induced. This group is called the shape class group . ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle SL_{2}(\mathbb {Z} )}$ ${\displaystyle Cl(D)}$

Calculation of the composition

One possible method for calculating the composition of two shapes and with discriminant D is provided by the following algorithm: ${\displaystyle (a,b,c)}$ ${\displaystyle (a',b',c')}$

1. determine ${\displaystyle n:=\operatorname {ggT} (a,a',(b+b')/2)\,}$
2. determine with ${\displaystyle t,u,v\in \mathbb {Z} }$ ${\displaystyle n=at+a'u+((b+b')/2)v\,}$
3. calculate ${\displaystyle A:={\frac {aa'}{n^{2}}}}$
4. calculate ${\displaystyle B:={\frac {ab't+a'bu+v(bb'+D)/2}{n}}}$
5. calculate ${\displaystyle C:={\frac {B^{2}-D}{4A}}}$

Then applies . ${\displaystyle (a,b,c)\circ (a',b',c')=(A,B,C)}$

The determination of (steps 1 and 2) takes place according to the extended Euclidean algorithm . ${\displaystyle n,t,u,v}$

Even when and are reduced, it is generally not reduced. In order to determine the corresponding shape class group, it must first be reduced. ${\displaystyle (a,b,c)}$ ${\displaystyle (a',b',c')}$ ${\displaystyle (A,B,C)}$ ${\displaystyle (A,B,C)}$

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

• for D negative and even: ${\displaystyle (1,0,-D/4)}$
• for D negative and odd: ${\displaystyle (1,1,(-D-1)/4)}$
• for D positive: ${\displaystyle (1,b,(b^{2}-D)/4)}$

example

Let , then the equivalence classes of the shape class group are represented by the following reduced forms: ${\displaystyle D=-71}$ ${\displaystyle Cl(-71)}$

${\displaystyle (1,1,18),(2,1,9),(2,-1,9),(3,1,6),(3,-1,6),(4,3,5),(4,-3,5)\,}$

So it is and . ${\displaystyle h(-71)=7\,}$ ${\displaystyle 1_{Cl(-71)}=(1,1,18)\,}$

It should now be calculated: ${\displaystyle (2,1,9)\circ (3,1,6)}$

1. ${\displaystyle n=\operatorname {ggT} (2,3,1)=1\,}$
2. with applies ${\displaystyle t=-2,\ u=2,\ v=-1\,}$ ${\displaystyle 1=n=2t+3u+1v\,}$
3. ${\displaystyle A:={\frac {2\cdot 3}{1^{2}}}=6}$
4. ${\displaystyle B:={\frac {2\cdot 1\cdot (-2)+3\cdot 1\cdot 2+(-1)\cdot (1\cdot 1-71)/2}{1}}=37}$
5. ${\displaystyle C:={\frac {37^{2}+71}{4\cdot 6}}=60}$

So, ${\displaystyle (2,1,9)\circ (3,1,6)=(6,37,60)\sim (6,1,3)\sim (3,-1,6)}$

More information

In a representation for the composition of integer binary quadratic forms of different discriminants.

A modern application of Gaussian composition to the problem of prime factorization is found in Shanks' square forms factorization .

In there are further group structures on equivalence classes of different shape families.

A fast algorithm for calculating compositions is described in.

Markoff forms

Another categorization of the indefinite rational binary quadratic forms comes from Markow . The starting point is the question of how much such a form is opposed to assuming the value 0. For this purpose f (x, y) = ax² + bxy + cy² becomes the value

${\displaystyle \inf\{|f(x,y)|\colon (x,y)\in \mathbb {Z} ^{2}\setminus \{(0,0)\}\}/{\sqrt {b^{2}-4ac}}}$

assigned. The set of these values ​​is called the Markoff spectrum .

It turns out that the largest value of the Markoff spectrum is the same , that the Markoff spectrum has no accumulation points in the interval , that each of the (isolated) points of the Markoff spectrum has a one-to-one relationship with an equivalence class with different discriminants , and that these forms are closely related to the integer solutions of the Diophantine equation (the Markoff numbers ). ${\displaystyle {\tfrac {1}{\sqrt {5}}}}$ ${\displaystyle ({\tfrac {1}{3}},{\tfrac {1}{\sqrt {5}}}]}$ ${\displaystyle SL_{2}(\mathbb {Z} )}$ ${\displaystyle m_{1}^{2}+m_{2}^{2}+m_{3}^{2}=3m_{1}m_{2}m_{3}}$

Scilab code for plotting binary square shapes

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;   //quadratische Form
   end
end
//disp(M)

clf;
plot3d(x,y,M);

literature

• Johannes Buchmann, Ulrich Vollmer: Binary Quadratic Forms . Springer, Berlin 2007, ISBN 3-540-46367-4
• Duncan A. Buell: Binary Quadratic Forms . Springer, New York 1989

Web links

• binary quadratic form . Springer Encyclopaedia of Mathematics

Individual evidence

1. ↑ ^{a b c d} C.F. Gauss: Disquisitiones Arithmeticae . German edition: H. Maser (Hrsg.): Studies on higher arithmetic . Chelsea Publishing, 1889
2. ↑ ^{a b} N.W. Rickert: Efficient Reduction of Quadratic Forms . In: E. Kaltofen, SM Watt (Ed.): Computers and Mathematics . Springer 1989, pp. 135-139
3. ↑ ^{a b c d} D. A. Buell: Binary Quadratic Forms . Springer-Verlag, 1989
4. ^ ^{A b c} Arnold Schönhage: Fast reduction and composition of binary quadratic forms . In: Proceedings of the 1991 international symposium on Symbolic and algebraic computation , pp. 128-133
5. ↑ ^{a b c} J.C. Lagarias: Worst-Case Complexity Bounds for Algorithms in the Theory of Integral Quadratic Forms . In: J. Algorithms , 1, 1980, pp. 142-186
6. ^ Shanks' square forms factorization in the English language Wikipedia
7. ↑ Manjul Bhargava: Higher composition laws I . In: Annals of Mathematics , 159, 2004, pp. 217-250
8. ↑ A presentation of the above results in JWS Cassels: An introduction to Diophantine Approximation is of a classical character . Cambridge University Press, 1957, Chapter 2. For more complete results, mostly based on entirely different methods, see Thomas W. Cusick, Mary E. Flahive: The Markoff and Lagrange Spectra . American Mathematical Society, 1989