Namespaces
Variants
Actions

Quadratic forms, reduction of

From Encyclopedia of Mathematics
Revision as of 14:54, 7 June 2020 by Ulf Rehmann (talk | contribs) (tex encoded by computer)
Jump to: navigation, search


The isolation of "reduced" forms in each class of quadratic forms over a given ring $ R $, i.e. of (one or several) "standard" forms in the class. The main aim of the reduction of quadratic forms is the solution of the problem of equivalence of quadratic forms: To establish whether or not two given quadratic forms $ q $ and $ r $ are equivalent over $ R $, and in the case of their equivalence to find (or describe) all the invertible matrices $ U $ over $ R $ taking $ q $ to $ r $( see Quadratic form). For the solution of the latter problem it suffices to know just one such matrix $ U _ {0} $ and all the automorphisms $ V $ of the form $ q $, since then $ U = V U _ {0} $. One usually has in mind equivalence of quadratic forms over $ \mathbf Z $, where one is often considering the entire collection of quadratic forms over $ \mathbf R $ and their classes over $ \mathbf Z $. There are fundamental differences in the reduction theory of positive-definite and indefinite quadratic forms.

The reduction of positive-definite quadratic forms.

There are different methods for the reduction over $ \mathbf Z $ of real positive-definite quadratic forms. Of these the most extensive and widely studied is the Minkowski (or Hermite–Minkowski) reduction method. The most general method is Venkov's method. Other prevalent reductions are those of E. Selling $ ( n = 3 ) $ and H.F. Charve $ ( n = 4 ) $.

To determine a reduced quadratic form

$$ q ( x) = B [ x ] = \ \sum _ {i , j = 1 } ^ { n } b _ {ij} x _ {i} x _ {j} ,\ \ b _ {ij} \in \mathbf R ,\ \ \| b _ {ij} \| = B , $$

means to define in the positivity cone $ \mathfrak P $ of the coefficient space $ \mathbf R ^ {N} $, $ N = n ( n + 1 ) / 2 $, a domain of reduction $ \mathfrak G $ such that $ q ( x) $ is reduced if and only if $ q = ( b _ {11} \dots b _ {n-} 1,n ) \in \mathfrak G $. It is desirable that $ \mathfrak G $ possesses good geometric properties (such as simple connectedness, convexity, etc.) and is a fundamental domain of the group $ \Gamma $ of integer transformations of determinant $ \pm 1 $. A domain $ F \subset \mathfrak P $ is called a fundamental domain of reduction of positive-definite quadratic forms if $ F $ is an open domain in $ \mathbf R ^ {N} $ and if: 1) for each $ q \in \mathfrak P $ there is an equivalent quadratic form $ h \simeq q $( $ \mathbf Z $) for which $ h \in \overline{F}\; $; and 2) if $ h _ {1} , h _ {2} \in F $ and $ h _ {1} \simeq h _ {2} $( $ \mathbf Z $), then $ h _ {1} = h _ {2} $.

a) Minkowski reduction of a quadratic form. A positive-definite quadratic form $ q ( x) $ is Minkowski reduced if for any $ k = 1 \dots n $ and any integers $ l _ {1} \dots l _ {n} $ with greatest common divisor $ ( l _ {1} \dots l _ {n} ) = 1 $,

$$ \tag{1 } a ( l _ {1} \dots l _ {n} ) \geq b _ {kk} . $$

From the infinite number of inequalities (1) for the coefficients $ b _ {ij} $ one can extract a finite number such that the remaining inequalities follow from them. In the coefficient space $ \mathbf R ^ {N} $ the set of Minkowski-reduced forms is an infinite complex pyramid (a gonohedron) with a finite number of faces, called the domain of Minkowski reduction (or Hermite–Minkowski gonohedron) $ \mathfrak E = \mathfrak E _ {n} $; $ \mathfrak E $ is a closed set, $ \mathfrak E \subset \overline{ {\mathfrak P }}\; $. For $ n \leq 7 $ the faces of $ \mathfrak E _ {n} $ have been calculated (see ).

There exists a constant $ \lambda _ {n} $ such that if the quadratic form $ q ( x) $ is Minkowski reduced, then

$$ \prod _ { i= } 1 ^ { n } b _ {ii} \leq \lambda _ {n} d ( q) , $$

where $ d ( q) = \mathop{\rm det} \| b _ {ij} \| $ is the determinant of $ q ( x) $.

Each real positive-definite quadratic form is equivalent over $ \mathbf Z $ to a Minkowski-reduced quadratic form. There is an algorithm for the reduction (for finding a reduced form that is equivalent to a given one) (see [8], [15]).

For $ n = 2 $, $ q = q ( x , y ) = ( a , b , c ) = a x ^ {2} + 2 b x y + c y ^ {2} $, $ a , b , c \in \mathbf R $, $ a > 0 $, $ d ( q) > 0 $, the conditions of being reduced have the form

$$ 0 \leq 2 b \leq a \leq c . $$

If one restricts oneself to proper equivalence (when only integer-valued transformations with determinant $ + 1 $ are admitted), then the domain of reduction has the form $ 0 \leq 2 | b | \leq a \leq c $( the Lagrange–Gauss reduction conditions). The set of all inequivalent (properly-) reduced quadratic forms can be written as the union $ F \cup F _ {1} \cup F _ {2} $, where

$$ F : 2 | b | < a < c , $$

$$ F _ {1} : 0 \leq 2 b < a = c ,\ F _ {2} : 0 < 2 b = a \leq c . $$

For $ n = 2 $ there is an algorithm for Gauss reduction, according to which one has to go over from a form not satisfying the Lagrange–Gauss conditions to its "neighbour" ,

$$ ( a ^ \prime , b ^ \prime , c ^ \prime ) = ( a , b , c ) \ \left \| \begin{array}{cr} 0 &- 1 \\ 1 & k \\ \end{array} \right \| ,\ \ a ^ \prime = c , $$

where the integer $ k $ is chosen such that $ | b ^ \prime | \leq c / 2 $. For any real quadratic form $ ( a , b , c ) $ the algorithm is broken up into a finite number of steps.

If $ q = ( a , b , c ) $, $ a , b , c \in \mathbf Z $, with greatest common divisor $ ( a , b , c ) = 1 $, then for $ d ( q) = a c - b ^ {2} > 3 $ there are only two automorphisms (of determinant 1); for $ d ( q) = 3 $, six automorphisms; and for $ d ( q) = 1 $, four automorphisms.

b) Venkov reduction of a quadratic form. This is a reduction method $ ( \mathfrak V _ \phi ) $, depending on a parameter $ \phi $, for an arbitrary real positive-definite $ n $- ary quadratic form $ q $( see [3]). A quadratic form $ q $ is said to be $ \phi $- reducible if

$$ ( q , \overline \phi \; ) \leq ( q , \overline \phi \; S ) $$

for all integer-valued $ ( n \times n ) $- matrices $ S $ of determinant 1; here $ \overline \phi \; = d ( \phi ) \phi ^ {-} 1 $ is the form reciprocal to $ \phi $, $ \overline \phi \; S $ is the quadratic form obtained from $ \overline \phi \; $ by the transformation $ S $, and $ ( q _ {1} , q _ {2} ) $ is the Voronoi semi-invariant, defined as follows: if $ q _ {1} = B _ {1} [ x ] $, $ B _ {1} = \| b _ {ij} ^ {(} 1) \| $, $ q _ {2} = B _ {2} [ x ] $, $ B _ {2} = \| b _ {ij} ^ {(} 2) \| $, then

$$ ( q _ {1} , q _ {2} ) = \ \sum _ {i , j = 1 } ^ { n } b _ {ij} ^ {(} 1) b _ {ij} ^ {(} 2) . $$

The set of $ \phi $- reducible quadratic forms in the coefficient space $ \mathbf R ^ {N} $ is a convex gonohedron $ \mathfrak V _ \phi $ with a finite number of faces lying in $ \mathfrak P $. If $ \phi = x _ {1} ^ {2} + \dots + x _ {n} ^ {2} $ and $ n \leq 6 $, then $ \mathfrak V _ \phi $ is the same as the domain of Minkowski reduction.

c) Selling and Charve reduction of a quadratic form. If in the Venkov reduction one puts $ \phi = \phi _ {n} ^ {(} 0) = \sum _ {i \leq j } x _ {i} x _ {j} $, where $ \phi _ {n} ^ {(} 0) $ is the Voronoi first perfect form, then for $ n = 3 $ one obtains the Selling reduction, and for $ n = 4 $ the Charve reduction (see , [6]).

The reduction of indefinite quadratic forms.

This is in principle more complicated than that of positive quadratic forms. There are no fundamental domains for them. Only for $ n = 2 $ is there a definitive reduction theory of quadratic forms over $ \mathbf Z $.

a) Reduction of indefinite binary quadratic forms. Let

$$ q = q ( x , y ) = \ ( a , b , c ) = a x ^ {2} + 2 b x y + c y ^ {2} ,\ \ a , b , c \in \mathbf Z , $$

be a quadratic form with determinant $ d = a c - c ^ {2} = - | d | $, where $ | d | $ is not a perfect square. Associated with $ q $ is the quadratic equation $ a z ^ {2} + 2 b z + c = 0 $ and its distinct irrational roots

$$ \Omega = \Omega ( q) = \ \frac{- b- \sqrt {| d | } }{d} ,\ \ \omega = \omega ( q) = \ \frac{- b + \sqrt {| d | } }{d} . $$

The form $ q $ is said to be reduced if $ | \Omega | > 1 $, $ | \omega | < 1 $, $ \Omega \omega < 0 $. These conditions are equivalent to the conditions

$$ 0 < \sqrt {| d | } - b < | a | < \sqrt {| d | } + b $$

(and also to the conditions $ 0 < \sqrt {| d | } - b < | c | < \sqrt {| d | } + b $). The number of reduced integer-valued quadratic forms of given determinant is finite. Every quadratic form is equivalent to a reduced one. There is an algorithm for reduction, using continued fractions (see [1]).

For a reduced quadratic form there exists precisely one "right neighbouring" and precisely one "left neighbouring" reduced quadratic form (see [1]). By going over from a reduced quadratic form to its "neighbouring" , one obtains a doubly-infinite chain of reduced forms. This chain is periodic. A finite segment of inequivalent forms of this chain is called a period. Two reduced forms are properly equivalent if and only if one of them is in the period of the other.

The foregoing theory is valid also for forms with real coefficients $ a , b , c $ if $ \Omega ( q) $ and $ \omega ( q) $ are distinct irrational roots; however, in this case a chain of reduced forms need not be periodic.

All proper automorphisms (of determinant 1) of a quadratic form with greatest common divisor $ ( a , b , c ) = 1 $, greatest common divisor $ ( a , 2 b , c ) = \sigma $, $ d = a c - b ^ {2} < 0 $, have the form

$$ \left \| \begin{array}{cc} \frac{t - b u } \sigma &- \frac{c u } \sigma \\ \frac{a u } \sigma & \frac{t + b u } \sigma \\ \end{array} \right \| = \pm \left \| \begin{array}{cc} \frac{T - b U } \sigma &- \frac{c U } \sigma \\ \frac{a U } \sigma & \frac{T + b U } \sigma \\ \end{array} \right \| ^ {n} , $$

$$ n = 0 , \pm 1 \dots $$

where $ ( t , u ) $ runs through all the solutions of the Pell equation $ t ^ {2} + d u ^ {2} = \sigma ^ {2} $ and $ ( T , U ) $ is the fundamental solution of this equation, that is, the smallest positive solution. Improper automorphisms (of determinant $ - 1 $) exist only for two-sided (or ambiguous) forms, that is, forms whose class coincides with that of its inverse (see [1]). The subgroup of proper automorphisms of a two-sided form has index 2 in the group of all automorphisms.

Indefinite integer-valued quadratic forms of determinant $ d = - s ^ {2} $, $ s > 0 $, $ s \in \mathbf Z $, reduce to the form $ ( 0 , - s , r ) $, where $ r \in \mathbf Z $, $ 0 \leq r < 2 s $. Two quadratic forms $ ( 0 , s , r _ {1} ) $ and $ ( 0 , - s , r _ {2} ) $, $ 0 \leq r _ {1} , r _ {2} < 2 s $, are properly equivalent if and only if $ r _ {1} = r _ {2} $. All the automorphisms of such forms are

$$ \pm \left \| \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ \end{array} \right \| $$

(see [1]).

b) Reduction of indefinite $ n $- ary quadratic forms. Let $ q ( x) = B [ x ] = x ^ {T} B x $ be such a form with real coefficients and $ d ( q) \neq 0 $. Then there exists a change of variables (over $ \mathbf R $), $ x = S y $, such that

$$ q ( x) = y _ {1} ^ {2} + \dots + y _ {1} ^ {2} - y _ {t+} 1 ^ {2} - \dots - y _ {n} ^ {2} , $$

where $ ( t , n - t ) $ is the signature of $ q $. Let

$$ \left \| \begin{array}{cccccc} 1 &{} &{} &{} &{} & 0 \\ {} &\cdot &{} &{} &{} &{} \\ {} &{} & 1 &{} &{} &{} \\ {} &{} &{} &- 1 &{} &{} \\ {} &{} &{} &{} &\cdot &{} \\ 0 &{} &{} &{} &{} &- 1 \\ \end{array} \right \| $$

( $ t $ rows 1; $ n - t $ rows $ - 1 $) and $ B = S ^ {T} D S $. The quadratic form $ q ( x) $ is associated with the positive-definite quadratic form

$$ h _ {S} ( x) = y _ {1} ^ {2} + \dots + y _ {t} ^ {2} + y _ {t+} 1 ^ {2} + \dots + y _ {n} ^ {2} = S ^ {T} S [ x ] . $$

The form $ q $ is called (Hermite) reducible if there is a transformation $ S $ of the form $ q $ into a sum of squares such that $ h _ {S} ( x) $ is (for example, Minkowski) reduced.

Equivalent to this definition of a reduced quadratic form is the following [13], [14]. Let $ \Phi ( q) $ be the set of matrices $ H $ over $ \mathbf R $ of positive $ n $- ary quadratic forms satisfying the equation $ H B ^ {-} 1 H = B $. This is a connected $ t ( n - 1 ) $- dimensional manifold of the positivity cone $ \mathfrak P \subset \mathbf R ^ {N} $( which can be written out in explicit form). Let $ F \subset \mathfrak P $ be the domain of reduction of positive-definite quadratic forms. The form $ q $ is called reducible if $ \Phi ( q) \cap F $ is non-empty.

The number of classes of integral indefinite quadratic forms in $ n $ variables with a given determinant $ d $ is finite (this is true also for positive-definite quadratic forms). The number of reduced forms in a given class is also finite. If two integral quadratic forms $ q _ {1} $ and $ q _ {2} $ are equivalent, then there exists an integral transformation $ S $, the absolute values of the elements of which are bounded by a constant depending only on $ n $ and $ d $, that takes $ q _ {1} $ to $ q _ {2} $. Thus the problem of determining whether or not two indefinite integral quadratic forms are equivalent is solved in a finite number of steps.

c) Automorphisms of indefinite quadratic forms. The problem of the description of all automorphisms of an indefinite integral quadratic form has two aspects: 1) to construct a fundamental domain of the group of automorphisms; 2) to describe the general form of the automorphisms (similar to the description of automorphisms by means of the Pell equation).

The general form of the automorphisms of a quadratic form was described by Ch. Hermite for $ n = 3 $ and by A. Cayley for arbitrary $ n $( see [10]).

A fundamental domain has been constructed of the group of automorphisms of an indefinite integral quadratic form $ q ( x) $ in a manifold $ \Phi ( q) $ bounded by a finite number of algebraic surfaces, and its volume has been calculated [13]. For the case $ t = 1 $ in the $ n $- dimensional space a fundamental domain has been constructed of the group of automorphisms of a quadratic form $ q ( x) $ in the form of an infinite pyramid with a finite number of plane faces (see [2], [4]).

There is a reduction theory of quadratic forms in algebraic number fields (see [11]).

References

[1] B.A. Venkov, "Elementary number theory" , Wolters-Noordhoff (1970) (Translated from Russian) MR0265267 Zbl 0204.37101
[2] B.A. Venkov, Izv. Akad. Nauk SSSR. Ser. Mat. , 1 (1937) pp. 139–170
[3] B.A. Venkov, "The reduction of positive-definite quadratic forms" Izv. Akad. Nauk SSSR. Ser. Mat. , 4 (1940) pp. 37–52 (In Russian)
[4] B.A. Venkov, "On indeterminate quadratic forms with integral coefficients" Trudy Mat. Inst. Steklov. , 38 (1951) pp. 30–41 (In Russian) MR0048498
[5a] B.N. Delone, "The geometry of positive definite quadratic forms" Uspekhi Mat. Nauk : 3 (1937) pp. 16–62 (In Russian)
[5b] B.N. Delone, "The geometry of positive definite quadratic forms" Uspekhi Mat. Nauk : 4 (1938) pp. 104–164 (In Russian)
[6] B.N. Delone, R.V. Galiulin, M.I. Shtorgin, "The types of Bravais lattices" , Current problems in mathematics , 2 , Moscow (1973) pp. 119–254 (In Russian) MR0412947 Zbl 0334.50005
[7] P.G. Lejeune-Dirichlet, "Vorlesungen über Zahlentheorie" , Vieweg (1894) Zbl 25.0252.01
[8] S.S. Ryshkov, "The theory of Hermite–Minkowski reduction of positive definite quadratic forms" J. Soviet Math. , 6 : 6 (1976) pp. 651–671 Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. , 33 (1973) pp. 37–64 Zbl 0374.10019
[9a] P.P. Tammela, "Reduction theory of positive quadratic forms" J. Soviet Math. , 11 : 2 (1979) pp. 197–277 Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. , 50 (1975) pp. 6–96 MR0563103 MR0321875 Zbl 0403.10012
[9b] P.P. Tammela, "Minkowski reduction region for positive quadratic forms in seven variables" J. Soviet Math. , 16 : 1 (1981) pp. 836–857 Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. , 67 (1977) pp. 108–143; 226 Zbl 0453.10033
[10] P. Bachmann, "Zahlentheorie. Die Arithmetik der quadratischen Formen" , 1–2 , Teubner (1923–1925) MR0238661 MR1522322
[11] P. Humbert, "Réduction de formes quadratiques dans un corps algébrique fini" Comm. Math. Helv. , 23 (1949) pp. 50–63 MR0031521 Zbl 0034.31102
[12] H. Minkowski, "Diskontinuitätsbereich für arithmetische Äquivalenz" J. Reine Angew. Math. , 129 (1905) pp. 220–274 Zbl 37.0251.02
[13] C.L. Siegel, "Einheiten quadratischer Formen" Abh. Math. Sem. Univ. Hamburg , 13 (1939) pp. 209–239 MR0003003 Zbl 0023.00701 Zbl 66.0125.03
[14] C.L. Siegel, "Zur Theorie der quadratischen Formen" Nachr. Akad. Wiss. Göttingen Math.-Phys. Kl. (1972) pp. 21–46 MR0311578 Zbl 0252.10019
[15] B.L. van der Waerden, "Die Reduktionstheorie der positiven quadratischen Formen" Acta Math. , 96 (1956) pp. 265–309 Zbl 0072.03601
How to Cite This Entry:
Quadratic forms, reduction of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Quadratic_forms,_reduction_of&oldid=49540
This article was adapted from an original article by A.V. Malyshev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article