Binäre quadratische Form

Eine binäre quadratische Form (in diesem Artikel oft kurz nur Form genannt), ist in der Mathematik eine quadratische Form in zwei Variablen x,y, also ein Polynom der Gestalt

$ax^2 + bxy+ cy^2 \,$,

wobei a,b,c die Koeffizienten der Form sind. Die Form f mit

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

schreibt man auch kurz als

$f = (a, b, c) \,$.

Im Folgenden werden binäre quadratische Formen in der Zahlentheorie betrachtet, das heisst man betrachtet nur ganzzahlige Lösungen. Quadratische Formen sind ein klassischer Bestandteil der Zahlentheorie. Bereits Adrien-Marie Legendre beschäftigte sich mit ganzzahligen binären und ternären quadratischen Formen. Aber erst Carl Friedrich Gauß begründete in seinem Werk Disquisitiones Arithmeticae^[1] (Kapitel 5) eine umfassende Theorie der binären quadratischen Formen.

Definitionen

Formal ist eine binäre quadratische Form über einem kommutativen Ring mit Einselement A ein homogenes Polynom vom Grad 2 in zwei Unbestimmten mit Koeffizienten in A.

Die binären quadratischen Formen über dem Körper der reellen Zahlen nennt man reelle binäre quadratische Formen, die binären quadratischen Formen über dem Ring der ganzen Zahlen nennt man ganzzahlige binäre quadratische Formen.

Eine ganzzahlige binären quadratischen Formen f = (a,b,c) heißt

• ambig, wenn der mittlere Koeffizient ein Vielfaches des ersten Koeffizienten ist, also b = ka mit $k\in\Z$ gilt.
• primitiv, wenn die Koeffizienten teilerfremd sind, also $\operatorname{ggT}(a,b,c) = 1\,$ (siehe größter gemeinsamer Teiler) gilt.

Die Diskriminante D_f einer binären quadratischen Form f = (a,b,c) ist definiert als $D_f := b^2-4ac\,$.

Problemfelder

In der Theorie binärer quadratischer Formen sind folgende Fragestellungen von Interesse:

Repräsentation ganzer Zahlen

1. Welche Zahlen werden von einer Form repräsentiert?
2. Wie viele und welche Repräsentationen hat eine Zahl durch eine Form?

Dabei repräsentiert eine Form f eine ganze Zahl $n\in\Z$, wenn es $(x_0,y_0)\in\Z^2$ gibt mit f(x₀,y₀) = n. Das Paar (x₀,y₀) heißt dann eine Repräsentation von n durch f. Die Repräsentation heißt primitiv, wenn gilt $\operatorname{ggT}(x_0,y_0)=1\,$.

Minimum von Formen

1. Welches Minimum hat eine Form?

Dabei ist das Minimum λ₁(f) einer Form f definiert durch $\lambda_1(f) := \inf\{\sqrt{|f(x,y)|}: (x,y)\in\Z^2, (x,y)\neq(0,0)\}\,$.

Äquivalenz von Formen

1. Sind zwei gegebene Formen äquivalent?
2. Mit welcher Matrix lassen sich zwei äquivalente Formen ineinander überführen?

Details zum Äquivalenzbegriff siehe unten.

Nutzen

Mithilfe der Theorie binärer quadratischer Formen lassen sich folgende Probleme lösen:

1. Finden von Lösungen $(x,y)\in\Z$ diophantischer Gleichungen der Form ax² + bxy + cy² = n (mittels Repräsentationen von ganzen Zahlen durch binäre quadratische Formen)
2. Finden eines kürzesten Vektors in einem Gitter (mittels des Minimums binärer quadratischer Formen)
3. Faktorisierung von ganzen Zahlen (mittels ambiger Formen)
4. Probleme der Kryptographie (über Beziehungen zu quadratischen Zahlkörpern)

Matrixdarstellungen

Ordnet man einer Form f = (a,b,c) über A die Dreiecksmatrix $M_d(f) = \begin{pmatrix} a & b \\ 0 & c \end{pmatrix}$ zu, so ist $M_d(f)\in A^{2\times 2}$ und f kann auch geschrieben werden als $f(x, y) = (x, y) M_d(f) (x, y)^T\,$, wobei $\ldots^T$ die Transposition bedeutet.

Alternativ kann auch eine symmetrische 2x2-Matrix $M_s(f) = \begin{pmatrix} a & \frac b 2 \\ \frac b 2 & c \end{pmatrix}$ verwendet werden: dann gilt ebenfalls $f(x, y) = (x, y) M_s(f) (x, y)^T\,$, wobei jedoch nur $M_s(f)\in A^{2\times 2}$ gilt, wenn 2 in A invertierbar ist. Für ganzzahlige binäre quadratische Formen f ist aber $M_s(f)\in \Q^{2\times 2}$.

Die zu f korrespondierende symmetrische Matrix M_s(f) bezeichnet man auch kurz mit [a,b,c], so dass also gilt: $f(x, y) = (x,y)[a, b,c](x, y)^T\,$.

Mithilfe der symmetrischen Matrix [a,b,c] einer Form lässt sich die Diskriminante der Form darstellen als

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

Äquivalenz von Formen

Definition der Äquivalenz

Eine (unimodulare) Substitution $(x', y') = U(x, y)^T\,$ der Variablen einer Form mit $U\in SL_2(\Z)$ (also U Element der speziellen linearen Gruppe über den ganzen Zahlen) bestimmt eine Transformation der Form $(a,b,c)\,$ in eine äquivalente Form $(\alpha ,\beta ,\gamma )\,$ mit der repräsentierenden Matrix $U^T[a, b, c]U = [\alpha ,\beta ,\gamma ]\,$. Zwei Formen heißen also äquivalent, wenn es eine Matrix $U\in SL_2(\Z)$ gibt mit $U^T [a, b, c]U= [\alpha ,\beta ,\gamma ]\,$. In diesem Fall schreibt man $[\alpha ,\beta ,\gamma ] \sim [a, b, c]\,$ oder $(a,b,c)=(\alpha ,\beta ,\gamma )U\,$. Es gilt dann also $(fU)(x,y) = f(U(x,y))\,$ für eine Form f.

Motiviert ist diese Definition durch die Tatsache, dass äquivalente Formen dieselben Zahlen repräsentieren und sich die Repräsentation $(x,y)\,$ der Zahl durch die eine Form f aus der Repräsentation $(x',y')\,$ der Zahl durch die äquivalente Form g direkt ergibt als $(x,y) = U(x',y')^T\,$, wenn $f=gU\,$.

Anmerkung: Die so definierte Äquivalenz wird oft auch als "echte Äquivalenz" bezeichnet und der allgemeine Äquivalenzbegriff auf Transformationsmatrizen $U\in GL_2(\Z)$ (also U Element der allgemeinen linearen Gruppe über den ganzen Zahlen) aufgebaut.

Eigenschaften äquivalenter Formen

Äquivalente Formen haben folgende Eigenschaften, die sich dann auf die Äquivalenzklassen F (Menge von jeweils äquivalenten Formen: $F(a,b,c) := \{ (a',b',c') | (a',b',c') \sim (a,b,c) \}\,$), übertragen.

• zwei äquivalente Formen haben dieselbe Diskriminante. Damit kann die Diskriminante D_F der Äquivalenzklasse definiert werden als D_F(a,b,c): = D_(a,b,c).
• zwei äquivalente Formen repräsentieren dieselben Zahlen.

Klassifikation von Formen

Definitheit von Formen

Formen können gemäß ihrer Definitheit klassifiziert werden.

Eine binäre quadratische Form f = (a,b,c) heißt

• indefinit, wenn $D_f > 0\,$ (aber nicht $D=n^2\,$ für $n \in \N\,$ - in diesem Fall ist die Form degeneriert),
• definit, wenn $D_f < 0\,$. Ist weiterhin a > 0, dann ist (a,b,c) positiv definit, sonst (a < 0) negativ definit.

Diese Definitionen entsprechen der Definitheit der den Formen entsprechenden Matrizen.

Bezüglich der Repräsentation ganzer Zahlen ergibt sich aus der Definitheit, dass positiv definite Formen nur positive, und negativ definite Formen nur negative Zahlen repräsentieren. Indefinite Formen können sowohl positive als auch negative Zahlen repräsentieren.

Anmerkung: Im Falle von $D_f \leq 0$ spricht man von (positiv bzw. negativ) semidefiniten Formen (wenn a > 0 bzw. a < 0).

Formen derselben Diskriminante

Jeder ganzen Zahl $n\in\Z$, die eine Diskriminante sein kann (d.h. $n \equiv 0 (mod\ 4)$ oder $n \equiv 1 (mod\ 4)$, z.B. -8, -7, -4, -3, 0, 1, 4, 5, 8), können alle ganzzahligen Formen mit dieser Zahl als Diskriminante zugeordnet werden. Betrachtet man jedoch die Äquivalenzklassen von Formen, dann gibt es pro Diskriminante nur eine endliche Anzahl von Äquivalenzklassen von ganzzahligen Formen mit dieser Diskriminante. Diese Anzahl wird auch Klassenzahl h(n) genannt (z.B. h( − 23) = 3).

Reduktion von ganzzahligen binären quadratischen Formen

Allgemein ist man bestrebt, für jede Äquivalenzklasse einen geeigneten Repräsentanten zu finden. Im Falle der binären quadratischen Formen sollte dieser Repräsentant möglichst (betragsmäßig) kleine Koeffizienten haben. Diese Forderung wird, je nach Definitheit der Form (die für alle Formen einer Äquivalenzklasse wegen der Invarianz der Diskriminante gleich ist) präzisiert:

• für positiv definite Formen (D < 0, a > 0):

nach Rickert^[2] oder Buell^[3](erweitert): entweder $-a < b \leq a < c$ oder $0 \leq b \leq a = c$

oder äquivalent nach Gauß^[1]: $|b| \le a \le \min (c, \sqrt {-D/3})$

• für negativ definite Formen (D < 0, a < 0):

für [-a, -b, -c] gelten die Bedingungen für positiv definite Formen

• für nicht degenerierte indefinite Formen (D > 0):

nach Schönhage^[4]: $\sqrt D - \min(|2c|, |2a|) < b < \sqrt D$ und $b > 0\,$

oder äquivalent nach Gauß^[1], Lagarias^[5] oder Buell^[3]: $0 < b < \sqrt D$ und $\sqrt D - b < |2a| < \sqrt D + b$

• für D = n² für ein $n\in\N^+$ (nach Lagarias^[5]):

b = n und $0 = a \leq c \leq n - 1$

• für D = 0:

$a=0\,$ und $b=0\,$

Binäre quadratische Formen, die oben genannte Bedingungen erfüllen, nennt man reduziert.

Beispiele:

• für positiv definite Formen (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.
• für negativ definite Formen (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.
• für nicht degenerierte indefinite Formen (D > 0): $[1,2,-1] \sim [-1,2,1]\,$, [1,4,-4], etc.
• für D = n² für ein $n\in\N^+$: [0, 2, 0], [0,2,1], [0,3,1], [0,3,2], etc.
• für D = 0: [0,0,0], [0,0,1], [0,0,-1], etc.

Durch die anfangs beschriebenen Transformation erhält man für jede binäre quadratische Form eine äquivalente reduzierte Form (diese ist für definite Formen eindeutig).

Generell nennt man Transformation, die die Größe der Koeffizienten verringert, Reduktion. Mittels Reduktionen kann also festgestellt werden, ob zwei Formen äquivalent sind:

• zwei nicht degenerierte indefinite Formen sind äquivalent, wenn deren äquivalente reduzierte Formen in einem Zykel reduzierter Formen liegen (siehe Buell^[3], Theorem 3.5).
• ansonsten sind zwei Formen äquivalent, wenn deren äquivalente reduzierte Formen identisch sind.

Die Transformationsmatrizen M lassen sich eindeutig durch Produkte von Elementarmatrizen $S = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}; T = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ darstellen: $M = S^{i_1}T^{j_1}S^{i_2}T^{j_2}...S^{i_n}T^{j_n}$.

Beschränkt man sich jedoch auf positive Transformationsmatrizen (d.h. deren Koeffizienten sind größer oder gleich Null), lassen sich diese auch durch die Elementarmatrizen $H = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}; L = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$ darstellen: $M = L^{i_1}H^{j_1}L^{i_2}H^{j_2}...L^{i_n}H^{j_n}$.

Die Bestimmung der Potenzen der Elementarmatrizen H und L in diesen Darstellungen erfolgt durch Algorithmen analog zum erweiterten Euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier Zahlen. Damit erhält man jedoch noch keine reduzierten Formen - dazu sind noch einige wenige Transformationen mit den Elementarmatrizen S und T notwendig.

Schon Gauß beschrieb 1801 in den "Disquisitiones Arithmeticae"^[1] Algorithmen zur Reduktion quadratischer Formen. Die Laufzeiten dieser Algorithmen wurden 1980 von Lagarias^[5] abgeschätzt, wobei für indefinite Formen im schlimmsten Fall eine exponentielle Laufzeit auftreten kann. Lagarias wandelte aber den Gaußschen Algorithmus so ab, dass er in jedem Fall polynomielle Laufzeit (asymptotisch $O(n\cdot\mu(n))$, wobei μ(n) eine obere Schranke für die Multiplikation von Zahlen der Binärlänge n ist) hat. Für degenerierte Formen konnte er sogar die asymptotische Abschätzung $O(\log n\cdot\mu(n))$ für die Laufzeit zeigen.

Rickert^[2] optimierte 1989 den Reduktionsalgorithmus für definite Formen, ohne jedoch die asymptotische Laufzeitschranke zu verbessern

Einen schnellen Algorithmus zur Reduktion beliebiger binärer quadratischer Formen hat Schönhage entwickelt und 1991 veröffentlicht^[4]. Dieser hat die asymptotische Laufzeitschranke von $O(\log n\cdot\mu(n))$.

Komposition

Allgemeine Definition der Komposition

Wenn f,g und F binäre quadratische Formen sind, dann heißt F eine Komposition aus f und g, wenn es zwei Bilinearformen $B_1 , B_2\colon\mathbb{Z}^2 \times \mathbb{Z}^2 \to \mathbb{Z}$ gibt, so dass $f(x) \cdot g(y)=F(B_1(x,y), B_2(x,y) )$ für alle $x,y \in \Z^2$ gilt.

Für den Fall, dass f und g ganzzahlige Formen mit gemeinsamer Diskriminante D und jeweils teilerfremden Koeffizienten sind, hat Gauß die Existenz eines Kompositionsalgorithmus nachgewiesen, und er hat gezeigt, dass die $SL_2(\Z)$-Äquivalenzklassen dieser Formen eine abelsche Gruppe bilden, wobei die Gruppenoperation durch die o.g. Komposition induziert wird. Diese Gruppe heißt die Formklassengruppe Cl(D).

Berechnung der Komposition

Ein mögliches Verfahren zur Berechnung der Komposition zweier Formen (a,b,c) und (a',b',c') mit Diskriminante D liefert folgender Algorithmus:

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

Dann gilt $(a,b,c) \circ (a',b',c') = (A,B,C)$.

Die Bestimmung von n,t,u,v (Schritte 1. und 2.) erfolgt dabei nach dem erweiterten Euklidischen Algorithmus.

Selbst wenn (a,b,c) und (a',b',c') reduziert sind, ist (A,B,C) im Allgemeinen nicht reduziert. Um die entsprechende Formklassengruppe zu ermitteln muss (A,B,C) also zuerst reduziert werden.

Das neutrale Element der Formklassengruppe ist die Hauptklasse, d.h. die Äquivalenzklasse, die die Hauptform der Diskriminante D enthält. Dabei ist die Hauptform der Diskriminante D die reduzierte Form mit 1 als ersten Koeffizienten:

• für D negativ und gerade: (1,0, − D / 4)
• für D negativ und ungerade: (1,1,( − D − 1) / 4)
• für D positiv: (1,b,(b² − D) / 4)

Beispiel

Sei D = − 71, dann werden die Äquivalenzklassen der Formklassengruppe Cl( − 71) durch folgende reduzierte Formen repräsentiert:

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

Es gilt also $h(-71)=7\,$ und $1_{Cl(-71)} = (1,1,8)\,$.

Es soll nun $(2,1,9) \circ (3,1,6)$ berechnet werden:

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

Also, $(2,1,9) \circ (3,1,6) = (6,37,60) \sim (6,1,3) \sim (3,-1,6)$

weitere Hinweise

In ^[3] eine Darstellung zur Komposition von ganzzahligen binären quadratischen Formen verschiedener Diskriminante.

Eine moderne Anwendung der Gaußkomposition auf das Problem der Primfaktorzerlegung findet sich in ^[6].

In ^[7] finden sich weitere Gruppenstrukturen auf Äquivalenzklassen von verschiedenen Formfamilien.

In ^[4] wird ein schneller Algorithmus zur Berechnung von Kompositionen beschrieben.

Markoff-Formen

Eine weitere Kategorisierung der indefiniten rationalen binären quadratischen Formen stammt von Markoff. Ausgangspunkt ist die Frage, wie sehr sich eine derartige Form dagegen sperrt, den Wert 0 anzunehmen. Dazu wird einer Form f(x,y)=ax²+bxy+cy² der Wert

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

zugeordnet. Die Menge dieser Werte heißt das Markoffspektrum.

Es stellt sich heraus, dass der größte Wert des Markoffspektrums gleich $\tfrac 1{\sqrt 5}$ ist, dass das Markoffspektrum im Intervall $(\tfrac 13, \tfrac 1{\sqrt5}]$ keine Häufungspunkte hat, dass jeder der (isolierten) Punkte des Markoffspektrums in eins-zu-eins-Beziehung zu jeweils einer $SL_2(\mathbb{Z})$-Äquivalenzklasse mit jeweils unterschiedlicher Diskriminanten steht, und dass diese Formen in enger Beziehung zu den ganzzahligen Lösungen der diophantischen Gleichung $m_1^2 + m_2^2 + m_3^2 = 3m_1m_2m_3$ (den Markoff-Zahlen) stehen.^[8]

Einzelnachweise

1. ↑ ^{a b c d} C.F. Gauß: Disquisitiones Arithmeticae, Deutsche Ausgabe Untersuchungen über höhere Arithmetik (Hrsg. H. Maser), Chelsea Publiching Company 1889
2. ↑ ^{a b} N.W. Rickert: Efficient Reduction of Quadratic Forms, in Computers and Mathematics (Hrsg. E. Kaltofen, S.M. Watt), Springer 1989, 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. Proceedings of the 1991 international symposium on Symbolic and algebraic computation, 128-133
5. ↑ ^{a b c} J.C. Lagarias: Worst-Case Complexity Bounds for Algorithms in the Theory of Integral Quadratic Forms, J. Algorithms 1 (1980), 142-186
6. ↑ Shanks' square forms factorization
7. ↑ Manjul Bhargava , Higher composition laws I. Annals of Mathematics, 159 (2004), 217–250
8. ↑ Von klassischem Charakter ist eine Präsentation der obengenannten Ergebnisse in J. W. S. Cassels An introduction to Diophantine Approximation Cambridge University Press, 1957, Kapitel 2. Für umfassendere Ergebnisse, zumeist auf ganz anderen Methoden basierend, siehe Thomas W. Cusick, Mary E. Flahive , The Markoff and Lagrange Spectra. American Mathematical Society, 1989

Literatur

• 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

Weblinks

• Springer Encyclopaedia of Mathematics: binary quadratic form