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[1] (Kapitel 5) eine umfassende Theorie der binären quadratischen Formen.

Definitionen

Bearbeiten

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

Bearbeiten

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

Repräsentation ganzer Zahlen

Bearbeiten
  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

Bearbeiten
  1. Welches Minimum hat eine Form?

Dabei ist das Minimum   einer Form   definiert durch  .

Äquivalenz von Formen

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

Details zum Äquivalenzbegriff siehe unten.

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

Bearbeiten

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

Bearbeiten

Definition der Äquivalenz

Bearbeiten

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

Bearbeiten

Ä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

Bearbeiten

Definitheit von Formen

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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  :
nach Rickert[2] oder Buell[3] (erweitert): entweder   oder  
oder äquivalent nach Gauß:[1]  
  • für negativ definite Formen  :
für   gelten die Bedingungen für positiv definite Formen
  • für nicht degenerierte indefinite Formen  :
nach Schönhage:[4]   und  
oder äquivalent nach Gauß,[1] Lagarias[5] oder Buell:[3]   und  
  • für   für ein   (nach Lagarias[5]):
  und  
  • für  :
  und  

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,[3] 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[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  , 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[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  .

Komposition

Bearbeiten

Allgemeine Definition der Komposition

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

 

Es gilt also   und  .

Es soll nun   berechnet werden:

  1.  
  2. mit   gilt  
  3.  
  4.  
  5.  

Also,  

Weitere Hinweise

Bearbeiten

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

Bearbeiten

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.[8]

Scilab-Code zum Plotten von binären quadratischen Formen

Bearbeiten
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

Bearbeiten
  • 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
Bearbeiten

Einzelnachweise

Bearbeiten
  1. a b c d C.F. Gauß: Disquisitiones Arithmeticae,. Deutsche Ausgabe: H. Maser (Hrsg.): Untersuchungen über höhere Arithmetik. Chelsea Publishing, 1889
  2. a b N.W. Rickert: Efficient Reduction of Quadratic Forms. In: E. Kaltofen, S.M. Watt (Hrsg.): 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. 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