Binary square shape – Wikipedia

One binary square shape (Often only in this article briefly only Form called), is a square shape in two variables in mathematics

${displaystyle x,y}$

, a polynomial of the figure

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

,

whereby

${displaystyle a,b,c}$

the coefficients of the form are. Form

${displaystyle f}$

with

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

you also write briefly as

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

.

In the following, binary square forms are considered in the number theory, which means that only integer solutions are considered. Square forms are a classic part of the number theory. Joseph-Louis Lagrange already dealt with integrated binary and ternary square forms. But only Carl Friedrich Gauß founded in his work Inquiry arithmetic ^[first] (Chapter 5) A comprehensive theory of binary square forms.

Formal is one binary square shape About a commutative ring with one -time element

${displaystyle A}$

A homogeneous polynomial from grade 2 in two indefinite with coefficients in

${displaystyle A}$

.

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

A full binary square forms

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

is called

• ambig if the middle coefficient is a multiple of the first coefficient, i.e.
  ${displaystyle b=ka}$

  with

  ${displaystyle kin mathbb {Z} }$

  is applicable.

• primitive if the coefficients are foreign to the part, so
  ${displaystyle operatorname {ggT} (a,b,c)=1,}$

  (see the largest joint divider).

The discriminants

${displaystyle D_{f}}$

a binary square shape

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

is defined as

${displaystyle D_{f}:=b^{2}-4ac,}$

.

In theory of binary square forms, the following questions are of interest:

Representation of entire numbers [ Edit | Edit the source text ]

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

A form represents

${displaystyle f}$

a whole number

${displaystyle nin mathbb {Z} }$

, if it

${displaystyle (x_{0},y_{0})in mathbb {Z} ^{2}}$

gives with

${displaystyle f(x_{0},y_{0})=n}$

. The couple

${displaystyle (x_{0},y_{0})}$

then means one representation from

${displaystyle n}$

through

${displaystyle f}$

. The representation means primitive if applies

${displaystyle operatorname {ggT} (x_{0},y_{0})=1,}$

.

Minimum of shapes [ Edit | Edit the source text ]

1. Which minimum has a form?

The minimum is

${displaystyle lambda _{1}(f)}$

a form

${displaystyle f}$

defined by

${displaystyle lambda _{1}(f):=inf{{sqrt {|f(x,y)|}}:(x,y)in mathbb {Z} ^{2},(x,y)neq (0,0)},}$

.

Equivalence of shapes [ Edit | Edit the source text ]

1. Are two given forms equivalent?
2. With which matrix can two equivalent shapes be converted into each other?

For details on the concept of equivalence, see below.

With the theory of binary square shapes, the following problems can be solved:

1. Find solutions
   ${displaystyle (x,y)in mathbb {Z} }$

   diophantic equations of the form

   ${displaystyle ax^{2}+bxy+cy^{2}=n}$

   (by means of representations of whole numbers through binary square shapes)

2. Find a shortest vector in a grid (by means of the minimum of binary square shapes)
3. Factorization of whole numbers (by means of ambigous forms)
4. Problems of cryptography (about relationships with square number bodies)

If you arrange a shape

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

above

${displaystyle A}$

The triangle matrix

${displaystyle M_{d}(f)={begin{pmatrix}a&b\0&cend{pmatrix}}}$

too, so is

${displaystyle M_{d}(f)in A^{2times 2}}$

and

${displaystyle f}$

can also be written as

${displaystyle f(x,y)=(x,y)M_{d}(f)(x,y)^{T},}$

, whereby

${displaystyle ldots ^{T}}$

The transposition means.

Alternatively, a symmetrical

${displaystyle (2times 2)}$

-Matrix

${displaystyle M_{s}(f)={begin{pmatrix}a&{frac {b}{2}}\{frac {b}{2}}&cend{pmatrix}}}$

to be used: then also applies

${displaystyle f(x,y)=(x,y)M_{s}(f)(x,y)^{T},}$

, but only

${displaystyle M_{s}(f)in A^{2times 2}}$

applies if 2 in

${displaystyle A}$

is invertable. For integrated binary square shapes

${displaystyle f}$

but is

${displaystyle M_{s}(f)in mathbb {Q} ^{2times 2}}$

.

The one too

${displaystyle f}$

Corresponding symmetrical matrix

${displaystyle M_{s}(f)}$

one also briefly referred to

${displaystyle [a,b,c]}$

so that the following applies:

${displaystyle f(x,y)=(x,y)[a,b,c](x,y)^{T},}$

.

With the help of the symmetrical matrix

${displaystyle [a,b,c]}$

The discriminant of the form can be represented as a form as

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

.

Definition of equivalence [ Edit | Edit the source text ]

One (unimodulare) Substitution

${displaystyle (x’,y’)=U(x,y)^{T},}$

the variables of a form with

${displaystyle Uin SL_{2}(mathbb {Z} )}$

(also

${displaystyle U}$

Element of the special linear group over the entire numbers) determines a transformation of the form

${displaystyle (a,b,c),}$

in a equivalent Form

${displaystyle (alpha ,beta ,gamma ),}$

With the representative matrix

${displaystyle U^{T}[a,b,c]U=[alpha ,beta ,gamma ],}$

. So two forms are called equivalent to if there is a matrix

${displaystyle Uin SL_{2}(mathbb {Z} )}$

gives with

${displaystyle U^{T}[a,b,c]U=[alpha ,beta ,gamma ],}$

.
In this case you write

${displaystyle [alpha ,beta ,gamma ]sim [a,b,c],}$

or

${displaystyle (a,b,c)=(alpha ,beta ,gamma )U,}$

. So it then applies

${displaystyle (fU)(x,y)=f(U(x,y)),}$

For a form

${displaystyle f}$

.

This definition is motivated by the fact that equivalent forms represent the same numbers and the representation

${displaystyle (x,y),}$

the number through the one form

${displaystyle f}$

From the representation

${displaystyle (x’,y’),}$

the number through the equivalent form

${displaystyle g}$

directly results as

${displaystyle (x,y)=U(x’,y’)^{T},}$

, if

${displaystyle f=gU,}$

.

Annotation: The defined one in this way equivalence is often also referred to as “real equivalence” and the general concept of equivalence on transformation matrices

${displaystyle Uin GL_{2}(mathbb {Z} )}$

(also

${displaystyle U}$

Element of the general linear group over the entire numbers).

Properties equivalent forms [ Edit | Edit the source text ]

Equivalent shapes have the following properties, which then form on the equivalence classes f (amount of equivalent forms:

${displaystyle F(a,b,c):={(a’,b’,c’)|(a’,b’,c’)sim (a,b,c)},}$

), transfer.

• Two equivalent shapes have the same discriminant. With that the Discriminating
  ${displaystyle D_{F}}$

  the equivalence class be defined as

  ${displaystyle D_{F(a,b,c)}:=D_{(a,b,c)}}$

  .

• Two equivalent shapes represent the same numbers.

Definity of shapes [ Edit | Edit the source text ]

Forms can according to their Definitheit be classified.

A binary square shape

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

is called

• indefinite , if
  ${displaystyle D_{f}>0,}$

  

  ${DisplayStyle d = n^{2},}$

  for

  ${Displaystyle nin mathbb {n},}$

  – In this case the form is degenerate ),

• defined , if
  ${displaystyle D_{f}<0,}$

  . Is furthermore

  ${displaystyle a>0}$

  

  ${displaystyle a<0}$

  ) negatively defined .

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

Regarding the representation Fully figures arise from the definition that defined positiv Forms only positive, and negatively defined Forms only represent negative numbers. Indefinite Forms can represent both positive and negative numbers.

Annotation: In case of

${displaystyle D_{f}leq 0}$

one speaks of ( positive or. negative ) semidefiniten Forms (if

${displaystyle a>0}$

${displaystyle a<0}$

).

Forms of the same discriminant [ Edit | Edit the source text ]

Every whole number

${displaystyle nin mathbb {Z} }$

that can be a discriminant (i.e.

${Displaystyle WAVIV 0 (operatorName {mod} 4)}$

or

${Displaystyle WAVIV 1 (operatorName {mod} 4)}$

, e.g. B. -8, -7, -4, -3, 0, 1, 4, 5, 8), all integer forms with this number can be assigned to this number. However, if one looks at the equivalence classes of shapes, there are only a finite number of equivalence classes of integrated forms with this discriminant per discriminant. This number will also Class number

${displaystyle h(n)}$

called (eg

${displaystyle h(-23)=3}$

).

Reduction of integer binary square shapes [ Edit | Edit the source text ]

In general, one strives to find a suitable representative for each equivalence class. In the case of binary square forms, this representative should have small coefficients if possible. Depending on the definition of the form (which is the same for all forms of an equivalence class because of the invariance, the discriminant is the same for all forms of the form:

• For positive forms
  ${displaystyle (D<0,a>0)}$

  [2] or Buell ^[3] (expanded): either

  ${displaystyle -a$

  or

  ${displaystyle 0leq bleq a=c}$

  

  Or equivalent to Gauss: ^[first]

  ${displaystyle |b|leq aleq min(c,{sqrt {-D/3}})}$

  

  • For negative definite forms
    ${displaystyle (D<0,a<0)}$

    :

  for

  ${displaystyle left[-a,-b,-cright]}$

  apply the conditions for positive definitions

  • For non -degenerated indefinite forms
    ${displaystyle (D>0)}$

    [4]

    ${displaystyle {sqrt {D}}-min(|2c|,|2a|)$

    and

    ${displaystyle b>0,}$

    [first] Lagarias ^[5] Or Buell: ^[3]

    ${Displaystyle 0$

    and

    ${displaystyle {sqrt {D}}-b<|2a|<{sqrt {D}}+b}$

    

    • for
      ${DisplayStyle d = n^{2}}$

      for a

      ${Displaystyle nin mathbb {N} ^{+}}$

      (after Lagarias ^[5] ):

    ${displaystyle b=n}$

    and

    ${displaystyle 0=aleq cleq n-1}$

    

    • for
      ${displaystyle D=0}$

      :

    ${displaystyle a=0,}$

    and

    ${displaystyle b=0,}$

    

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

    Examples:

    • For positive forms
      ${displaystyle (D<0,a>0)}$

      
      ${displaystyle (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 -degenerated indefinite forms
      ${displaystyle (D>0)}$

      

      ${displaystyle [1,2,-1]sim [-1,2,1],}$

      , [1,4,-4] etc.

    • for
      ${DisplayStyle d = n^{2}}$

      for a

      ${Displaystyle nin mathbb {N} ^{+}}$

      : [0, 2, 0], [0,2,1], [0,3,1], [0,3,2] etc.

    • for
      ${displaystyle D=0}$

      : [0,0,0], [0,0,1], [0,0,-1] etc.

    The transformation described at the beginning gives you an equivalent reduced form for each binary square shape (this is clear for definite forms).

    In general, transformation is called that reduces the size of the coefficients, Reduction . Using reductions, it can therefore be determined whether two forms are equivalent:

    • Two non -degenerated indefinite forms are equivalent if their equivalent shapes are reduced in a cycle of reduced forms (see Buell, ^[3] Theorem 3.5).
    • Otherwise, two forms are equivalent if their equivalent forms are identical.

    The transformation matrices

    ${displaystyle M}$

    can be clearly done by products from elementary matrices

    ${displaystyle S={begin{pmatrix}1&1\0&1end{pmatrix}};T={begin{pmatrix}0&-1\1&0end{pmatrix}}}$

    represent:

    ${displaystyle M=S^{i_{1}}T^{j_{1}}S^{i_{2}}T^{j_{2}}dots S^{i_{n}}T^{j_{n}}}$

    .

    However, if you are limited to positive transformation matrices (i.e. their coefficients are greater or zero), these can also be

    ${displaystyle H={begin{pmatrix}1&1\0&1end{pmatrix}};L={begin{pmatrix}1&0\1&1end{pmatrix}}}$

    represent:

    ${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 potencies of the elementary matrix

    ${displaystyle H}$

    and

    ${displaystyle L}$

    In these representations, algorithms are analogous to the extended Euclidean algorithm to determine the largest common divider of two numbers. However, this does not get any reduced shapes – there are also a few transformations with the elementary matrices

    ${displaystyle S}$

    and

    ${displaystyle T}$

    necessary.

    Gauss already described in the 1801 Inquiry arithmetic ^[first] Algorithms to reduce square shapes. The terms of these algorithms were in 1980 by Lagarias ^[5] estimated, although an exponential term can occur in the worst case. Lagarias, however, changed the Gaussian algorithm so that he in any case polynomial term (asymptotic

    ${Displaystyle o (ncdot mu (n))}$

    , whereby

    ${Displaystyle MU (n)}$

    has an upper barrier for the multiplication of binary length numbers). For degenerated forms, he could even be the asymptotic assessment

    ${Displaystyle o (log ncdot mu (n))}$

    show for the term.

    Rickert ^[2] Optimized the reduction salgorithm for definite forms in 1989, but without improving the asymptotic running time barrier

    Schönhage developed a quick algorithm to reduce any binary square forms and published in 1991. ^[4] This has the asymptotic running time barrier of

    ${Displaystyle o (log ncdot mu (n))}$

    .

    General definition of the composition [ Edit | Edit the source text ]

    If

    ${displaystyle f,g}$

    and

    ${displaystyle F}$

    are binary square forms, then means

    ${displaystyle F}$

    one composition out of

    ${displaystyle f}$

    and

    ${displaystyle g}$

    if there are two bilinear shapes

    ${displaystyle B_{1},B_{2}colon mathbb {Z} ^{2}times mathbb {Z} ^{2}to mathbb {Z} }$

    gives so that

    ${displaystyle f(x)cdot g(y)=F(B_{1}(x,y),B_{2}(x,y))}$

    for all

    ${displaystyle x,yin mathbb {Z} ^{2}}$

    is applicable.

    In case that

    ${displaystyle f}$

    and

    ${displaystyle g}$

    Gauss have demonstrated the existence of a compositionalgorithm, and it has shown that the existence of a composition salgorithm has demonstrated that they have shown that they have shown that the

    ${displaystyle SL_{2}(mathbb {Z} )}$

    -Equivalence classes of these forms form an Abelsche group, with the group operation by the above. Composition is induced. This group is called that Form class group

    ${displaystyle Cl(D)}$

    .

    Calculation of the composition [ Edit | Edit the source text ]

    A possible procedure for calculating the composition of two forms

    ${displaystyle (a,b,c)}$

    and

    ${displaystyle (a’,b’,c’)}$

    With discriminant D, the following algorithm delivers:

    1. determine
       ${displaystyle n:=operatorname {ggT} (a,a’,(b+b’)/2),}$

       

    2. determine
       ${displaystyle t,u,vin mathbb {Z} }$

       with

       ${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 apply

    ${displaystyle (a,b,c)circ (a’,b’,c’)=(A,B,C)}$

    .

    The determination of

    ${displaystyle n,t,u,v}$

    (Steps 1. and 2nd) takes place according to the extended euclidal algorithm.

    Even if

    ${displaystyle (a,b,c)}$

    and

    ${displaystyle (a’,b’,c’)}$

    are reduced is

    ${displaystyle (A,B,C)}$

    generally not reduced. To determine the corresponding form class group

    ${displaystyle (A,B,C)}$

    So to be reduced first.

    The neutral element of the form class group is the Main class , d. H. the equivalence class that the Main form the discriminant D contains. The one is Main form The discriminant D The reduced form with 1 as the first coefficient:

    • for D negative and straight:
      ${displaystyle (1,0,-D/4)}$

      

    • for D negative and odd:
      ${displaystyle (1,1,(-D-1)/4)}$

      

    • positive for D:
      ${displaystyle (1,b,(b^{2}-D)/4)}$

      

    Example [ Edit | Edit the source text ]

    May be

    ${displaystyle D=-71}$

    , then the equivalence classes of the form class group

    ${displaystyle Cl(-71)}$

    represented by the following reduced forms:

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

    

    So it applies

    ${displaystyle h(-71)=7,}$

    and

    ${displaystyle 1_{Cl(-71)}=(1,1,18),}$

    .

    It should now

    ${displaystyle (2,1,9)circ (3,1,6)}$

    be calculated:

    1. 
       ${displaystyle n=operatorname {ggT} (2,3,1)=1,}$

       

    2. with
       ${displaystyle t=-2, u=2, v=-1,}$

       is applicable

       ${displaystyle 1=n=2t+3u+1v,}$

       

    3. 
       ${displaystyle A:={frac {2cdot 3}{1^{2}}}=6}$

       

    4. 
       ${displaystyle B:={frac {2cdot 1cdot (-2)+3cdot 1cdot 2+(-1)cdot (1cdot 1-71)/2}{1}}=37}$

       

    5. 
       ${displaystyle C:={frac {37^{2}+71}{4cdot 6}}=60}$

       

    Also,

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

    

    More information [ Edit | Edit the source text ]

    In ^[3] A representation of the composition of integrated binary square forms of various discriminant.

    A modern application of the Gauß composition to the problem of prime factorial can be found in Shanks’ square forms factorization . ^[6]

    In ^[7] There are other group structures on equivalence classes of various forms of form.

    In ^[4] a quick algorithm is described for calculating compositions.

    A further categorization of the indefinites of rational binary square forms comes from Markow. The starting point is the question of how much such a shape is blocked to accept the value 0. For this purpose, a form f (x, y) = AX²+BXY+CY² is the value

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

    

    assigned. The amount of these values ​​is called Markoffspektrum .

    It turns out that the greatest value of the markoff spectrum is the same

    ${displaystyle {tfrac {1}{sqrt {5}}}}$

    is that the markoff spectrum in the interval

    ${displaystyle ({tfrac {1}{3}},{tfrac {1}{sqrt {5}}}]}$

    There is no frequency points that each of the (isolated) points of the markoff spectrum in one-to-one relationship with one

    ${displaystyle SL_{2}(mathbb {Z} )}$

    -Equivalence class, each with different discriminators, and that these forms are closely related to the integer solutions of diophantic equation

    ${displaystyle m_{1}^{2}+m_{2}^{2}+m_{3}^{2}=3m_{1}m_{2}m_{3}}$

    (the markoff numbers). ^[8]

    Scilab code for plotting binary square shapes [ Edit | Edit the source text ]

    x  =  [ - 5 : 0.1 : 5 ];  and  =  [ - 5 : 0.1 : 5 ];  m  =  length ( x );  M  =  zeros ( m , m );  for  i  =  first : m   for  j  =  first : m   M ( i ) ( j ) =  x ( j ) ^ 2  +  4 * x ( j ) * and ( i )  +  and ( i ) ^ 2 ;  // square shape     end
    end
    //disp(M)
    
    clf;
    plot3d(x,y,M);
    

    • 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
    1. ↑ ^{a b c d} C.F. Gauss: Inquiry arithmetic . German edition: H. Maser (ed.): Studies on higher arithmetics . Chelsea Publishing, 1889
    2. ↑ ^{a b} N.W. Rickert: Efficient Reduction of Quadratic Forms . In: E. Kaltofen, S.M. Watt (ed.): Computers and Mathematics . Springer 1989, S. 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 , S. 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, S. 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, S. 217–250
    8. ↑ A presentation of the above results in J. W. W. S. Cassels: An introduction to Diophantine Approximation . Cambridge University Press, 1957, Chapter 2. For more comprehensive results, mostly based on completely different methods, see Thomas W. Cusick, Mary E. Flahive: The Markoff and Lagrange Spectra . American Mathematical Society, 1989