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

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 \mathbb{Z } , wenn es (x_{0},y_{0})\in \mathbb{Z } ^{2} gibt mit f(x_{0},y_{0})=n. Das Paar (x_{0},y_{0}) 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 \lambda _{1}(f) einer Form f definiert durch \lambda _{1}(f):=\inf\{{\sqrt  {|f(x,y)|}}:(x,y)\in \mathbb{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 \mathbb{Z } diophantischer Gleichungen der Form ax^{2}+bxy+cy^{2}=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 (2\times 2)-Matrix M_{s}(f)={\begin{pmatrix}a&{\frac  b2}\\{\frac  b2}&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 \mathbb{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}(\mathbb{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}(\mathbb{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}(\mathbb{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.

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

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 \mathbb{Z } , die eine Diskriminante sein kann (d.h. n\equiv 0(\operatorname {mod}4) oder n\equiv 1(\operatorname {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:

nach Rickert[1] oder Buell[2] (erweitert): entweder -a<b\leq a<c oder 0\leq b\leq a=c
oder äquivalent nach Gauß: |b|\leq a\leq \min(c,{\sqrt  {-D/3}})
für {\displaystyle \left[-a,-b,-c\right]} gelten die Bedingungen für positiv definite Formen
nach Schönhage:[3] {\sqrt  D}-\min(|2c|,|2a|)<b<{\sqrt  D} und b>0\,
oder äquivalent nach Gauß, Lagarias[4] oder Buell:[2] 0<b<{\sqrt  D} und {\sqrt  D}-b<|2a|<{\sqrt  D}+b
b=n und 0=a\leq c\leq n-1
a=0\, und b=0\,

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

Beispiele:

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:

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}}}\dots 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}}}\dots 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 Algorithmen zur Reduktion quadratischer Formen. Die Laufzeiten dieser Algorithmen wurden 1980 von Lagarias[4] 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 \mu (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[1] 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 Arnold Schönhage entwickelt und 1991 veröffentlicht.[3] 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 \mathbb{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}(\mathbb{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 {\displaystyle n:=\operatorname {ggT} (a,a',(b+b')/2)\,}
  2. bestimme t,u,v\in \mathbb{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:

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 {\displaystyle 1_{Cl(-71)}=(1,1,18)\,}.

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

  1. {\displaystyle n=\operatorname {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\cdot 6}}=60

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

Weitere Hinweise

In[2] 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.[5]

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

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

Markoff-Formen

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

\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{{\sqrt  5}}}] 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_{1}m_{2}m_{3} (den Markoff-Zahlen) stehen.[7]

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

Anmerkungen

  1. 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
  2. a b c d D. A. Buell: Binary Quadratic Forms. Springer-Verlag, 1989
  3. 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
  4. a b c .C. Lagarias: Worst-Case Complexity Bounds for Algorithms in the Theory of Integral Quadratic Forms. In: J. Algorithms, 1, 1980, S. 142–186
  5. Shanks’ square forms factorization in der englischsprachigen Wikipedia
  6. Manjul Bhargava: Higher composition laws I. In: Annals of Mathematics, 159, 2004, S. 217–250
  7. 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
Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung: Jena, den: 31.07. 2022