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 , also ein Polynom der Gestalt

wobei die Koeffizienten der Form sind. Die Form mit

schreibt man auch kurz als

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

Definitionen

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

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 heißt

• ambig, wenn der mittlere Koeffizient ein Vielfaches des ersten Koeffizienten ist, also mit gilt.
• primitiv, wenn die Koeffizienten teilerfremd sind, also (siehe größter gemeinsamer Teiler) gilt.

Die Diskriminante einer binären quadratischen Form ist definiert als .

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 eine ganze Zahl , wenn es gibt mit . Das Paar heißt dann eine Repräsentation von durch . Die Repräsentation heißt primitiv, wenn gilt .

Minimum von Formen

1. Welches Minimum hat eine Form?

Dabei ist das Minimum einer Form definiert durch .

Ä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 diophantischer Gleichungen der Form (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 über die Dreiecksmatrix zu, so ist und kann auch geschrieben werden als , wobei die Transposition bedeutet.

Alternativ kann auch eine symmetrische -Matrix verwendet werden: dann gilt ebenfalls , wobei jedoch nur gilt, wenn 2 in invertierbar ist. Für ganzzahlige binäre quadratische Formen ist aber .

Die zu korrespondierende symmetrische Matrix bezeichnet man auch kurz mit , so dass also gilt: .

Mithilfe der symmetrischen Matrix einer Form lässt sich die Diskriminante der Form darstellen als

.

Äquivalenz von Formen

Definition der Äquivalenz

Eine (unimodulare) Substitution der Variablen einer Form mit (also Element der speziellen linearen Gruppe über den ganzen Zahlen) bestimmt eine Transformation der Form in eine äquivalente Form mit der repräsentierenden Matrix . Zwei Formen heißen also äquivalent, wenn es eine Matrix gibt mit . In diesem Fall schreibt man oder . Es gilt dann also für eine Form .

Motiviert ist diese Definition durch die Tatsache, dass äquivalente Formen dieselben Zahlen repräsentieren und sich die Repräsentation der Zahl durch die eine Form aus der Repräsentation der Zahl durch die äquivalente Form direkt ergibt als , wenn .

Anmerkung: Die so definierte Äquivalenz wird oft auch als „echte Äquivalenz“ bezeichnet und der allgemeine Äquivalenzbegriff auf Transformationsmatrizen (also 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: ), übertragen.

• zwei äquivalente Formen haben dieselbe Diskriminante. Damit kann die Diskriminante der Äquivalenzklasse definiert werden als .
• 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 heißt

• indefinit, wenn (aber nicht für – in diesem Fall ist die Form degeneriert),
• definit, wenn . Ist weiterhin , dann ist (a,b,c) positiv definit, sonst () 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 spricht man von (positiv bzw. negativ) semidefiniten Formen (wenn bzw. ).

Formen derselben Diskriminante

Jeder ganzen Zahl , die eine Diskriminante sein kann (d. h. oder , 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 genannt (z. B. ).

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 :

• für negativ definite Formen :

• für nicht degenerierte indefinite Formen :

• für für ein (nach Lagarias):

• für :

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

Beispiele:

• für positiv definite Formen : [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 : [-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 : , [1,4,-4] etc.
• für für ein : [0, 2, 0], [0,2,1], [0,3,1], [0,3,2] etc.
• für : [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, Theorem 3.5).
• ansonsten sind zwei Formen äquivalent, wenn deren äquivalente reduzierte Formen identisch sind.

Die Transformationsmatrizen lassen sich eindeutig durch Produkte von Elementarmatrizen darstellen: .

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 darstellen: .

Die Bestimmung der Potenzen der Elementarmatrizen und 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 und notwendig.

Schon Gauß beschrieb 1801 in den Disquisitiones Arithmeticae Algorithmen zur Reduktion quadratischer Formen. Die Laufzeiten dieser Algorithmen wurden 1980 von Lagarias 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 , wobei 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 für die Laufzeit zeigen.

Rickert 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. Dieser hat die asymptotische Laufzeitschranke von .

Komposition

Allgemeine Definition der Komposition

Wenn und binäre quadratische Formen sind, dann heißt eine Komposition aus und , wenn es zwei Bilinearformen gibt, so dass für alle gilt.

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

Berechnung der Komposition

Ein mögliches Verfahren zur Berechnung der Komposition zweier Formen und mit Diskriminante D liefert folgender Algorithmus:

1. bestimme
2. bestimme mit
3. berechne
4. berechne
5. berechne

Dann gilt .

Die Bestimmung von (Schritte 1. und 2.) erfolgt dabei nach dem erweiterten Euklidischen Algorithmus.

Selbst wenn und reduziert sind, ist im Allgemeinen nicht reduziert. Um die entsprechende Formklassengruppe zu ermitteln muss 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:
• für D negativ und ungerade:
• für D positiv:

Beispiel

Sei , dann werden die Äquivalenzklassen der Formklassengruppe durch folgende reduzierte Formen repräsentiert:

Es gilt also und .

Es soll nun berechnet werden:

2. mit gilt

Also,

Weitere Hinweise

In 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 Shanks’ square forms factorization.

In finden sich weitere Gruppenstrukturen auf Äquivalenzklassen von verschiedenen Formfamilien.

In wird ein schneller Algorithmus zur Berechnung von Kompositionen beschrieben.

Markoff-Formen

Eine weitere Kategorisierung der indefiniten rationalen binären quadratischen Formen stammt von Markow. 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

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

Es stellt sich heraus, dass der größte Wert des Markoffspektrums gleich ist, dass das Markoffspektrum im Intervall keine Häufungspunkte hat, dass jeder der (isolierten) Punkte des Markoffspektrums in eins-zu-eins-Beziehung zu jeweils einer -Äquivalenzklasse mit jeweils unterschiedlicher Diskriminanten steht, und dass diese Formen in enger Beziehung zu den ganzzahligen Lösungen der diophantischen Gleichung (den Markoff-Zahlen) stehen.

Scilab-Code zum Plotten von binären quadratischen Formen

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); 

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

• binary quadratic form. Springer Encyclopaedia of Mathematics

Einzelnachweise

1. C.F. Gauß: Disquisitiones Arithmeticae,. Deutsche Ausgabe: H. Maser (Hrsg.): Untersuchungen über höhere Arithmetik. Chelsea Publishing, 1889
2. N.W. Rickert: Efficient Reduction of Quadratic Forms. In: E. Kaltofen, S.M. Watt (Hrsg.): Computers and Mathematics. Springer 1989, S. 135–139
3. D. A. Buell: Binary Quadratic Forms. Springer-Verlag, 1989
4. 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. 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. en:Shanks's square forms factorization in der englischsprachigen Wikipedia
7. Manjul Bhargava: Higher composition laws I. In: Annals of Mathematics, 159, 2004, S. 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