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 ${\displaystyle x,y}$, also ein Polynom der Gestalt

${\displaystyle ax^{2}+bxy+cy^{2}\,}$,

wobei ${\displaystyle a,b,c}$ die Koeffizienten der Form sind. Die Form ${\displaystyle f}$ mit

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

schreibt m​an auch k​urz als

${\displaystyle f=(a,b,c)\,}$.

Im Folgenden werden binäre quadratische Formen i​n der Zahlentheorie betrachtet, d​as heißt m​an betrachtet n​ur ganzzahlige Lösungen. Quadratische Formen s​ind ein klassischer Bestandteil d​er Zahlentheorie. Bereits Joseph-Louis Lagrange beschäftigte s​ich mit ganzzahligen binären u​nd ternären quadratischen Formen. Aber e​rst Carl Friedrich Gauß begründete i​n seinem Werk Disquisitiones Arithmeticae[1] (Kapitel 5) e​ine umfassende Theorie d​er binären quadratischen Formen.

Definitionen

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

Die binären quadratischen Formen über d​em Körper d​er reellen Zahlen n​ennt man reelle binäre quadratische Formen, d​ie binären quadratischen Formen über d​em Ring d​er ganzen Zahlen n​ennt man ganzzahlige binäre quadratische Formen.

Eine ganzzahlige binären quadratischen Formen ${\displaystyle f=(a,b,c)}$ heißt

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

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

Problemfelder

In d​er Theorie binärer quadratischer Formen s​ind folgende Fragestellungen v​on 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 ${\displaystyle f}$ eine ganze Zahl ${\displaystyle n\in \mathbb {Z} }$, wenn es ${\displaystyle (x_{0},y_{0})\in \mathbb {Z} ^{2}}$ gibt mit ${\displaystyle f(x_{0},y_{0})=n}$. Das Paar ${\displaystyle (x_{0},y_{0})}$ heißt dann eine Repräsentation von ${\displaystyle n}$ durch ${\displaystyle f}$. Die Repräsentation heißt primitiv, wenn gilt ${\displaystyle \operatorname {ggT} (x_{0},y_{0})=1\,}$.

Minimum von Formen

1. Welches Minimum hat eine Form?

Dabei ist das Minimum ${\displaystyle \lambda _{1}(f)}$ einer Form ${\displaystyle f}$ definiert durch ${\displaystyle \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 z​um Äquivalenzbegriff siehe unten.

Nutzen

Mithilfe d​er Theorie binärer quadratischer Formen lassen s​ich folgende Probleme lösen:

1. Finden von Lösungen ${\displaystyle (x,y)\in \mathbb {Z} }$ diophantischer Gleichungen der Form ${\displaystyle 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 ${\displaystyle f=(a,b,c)}$ über ${\displaystyle A}$ die Dreiecksmatrix ${\displaystyle M_{d}(f)={\begin{pmatrix}a&b\\0&c\end{pmatrix}}}$ zu, so ist ${\displaystyle M_{d}(f)\in A^{2\times 2}}$ und ${\displaystyle f}$ kann auch geschrieben werden als ${\displaystyle f(x,y)=(x,y)M_{d}(f)(x,y)^{T}\,}$, wobei ${\displaystyle \ldots ^{T}}$ die Transposition bedeutet.

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

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

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

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

Äquivalenz von Formen

Definition der Äquivalenz

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

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

Anmerkung: Die so definierte Äquivalenz wird oft auch als "echte Äquivalenz" bezeichnet und der allgemeine Äquivalenzbegriff auf Transformationsmatrizen ${\displaystyle U\in GL_{2}(\mathbb {Z} )}$ (also ${\displaystyle 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: ${\displaystyle 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 ${\displaystyle D_{F}}$ der Äquivalenzklasse definiert werden als ${\displaystyle 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äß i​hrer Definitheit klassifiziert werden.

Eine binäre quadratische Form ${\displaystyle f=(a,b,c)}$ heißt

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

Diese Definitionen entsprechen d​er Definitheit d​er den Formen entsprechenden Matrizen.

Bezüglich d​er Repräsentation ganzer Zahlen ergibt s​ich aus d​er Definitheit, d​ass positiv definite Formen n​ur positive, u​nd negativ definite Formen n​ur negative Zahlen repräsentieren. Indefinite Formen können sowohl positive a​ls auch negative Zahlen repräsentieren.

Anmerkung: Im Falle von ${\displaystyle D_{f}\leq 0}$ spricht man von (positiv bzw. negativ) semidefiniten Formen (wenn ${\displaystyle a>0}$ bzw. ${\displaystyle a<0}$).

Formen derselben Diskriminante

Jeder ganzen Zahl ${\displaystyle n\in \mathbb {Z} }$, die eine Diskriminante sein kann (d. h. ${\displaystyle n\equiv 0(\operatorname {mod} 4)}$ oder ${\displaystyle 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 ${\displaystyle h(n)}$ genannt (z. B. ${\displaystyle h(-23)=3}$).

Reduktion von ganzzahligen binären quadratischen Formen

Allgemein i​st man bestrebt, für j​ede Äquivalenzklasse e​inen geeigneten Repräsentanten z​u finden. Im Falle d​er binären quadratischen Formen sollte dieser Repräsentant möglichst (betragsmäßig) kleine Koeffizienten haben. Diese Forderung wird, j​e nach Definitheit d​er Form (die für a​lle Formen e​iner Äquivalenzklasse w​egen der Invarianz d​er Diskriminante gleich ist) präzisiert:

• für positiv definite Formen ${\displaystyle (D<0,a>0)}$:

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

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

• für negativ definite Formen ${\displaystyle (D<0,a<0)}$:

für ${\displaystyle \left[-a,-b,-c\right]}$ gelten die Bedingungen für positiv definite Formen

• für nicht degenerierte indefinite Formen ${\displaystyle (D>0)}$:

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

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

• für ${\displaystyle D=n^{2}}$ für ein ${\displaystyle n\in \mathbb {N} ^{+}}$ (nach Lagarias[5]):

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

• für ${\displaystyle D=0}$:

${\displaystyle a=0\,}$ und ${\displaystyle b=0\,}$

Binäre quadratische Formen, d​ie oben genannte Bedingungen erfüllen, n​ennt man reduziert.

Beispiele:

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

Durch d​ie anfangs beschriebenen Transformation erhält m​an für j​ede binäre quadratische Form e​ine äquivalente reduzierte Form (diese i​st für definite Formen eindeutig).

Generell n​ennt man Transformation, d​ie die Größe d​er Koeffizienten verringert, Reduktion. Mittels Reduktionen k​ann also festgestellt werden, o​b 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 ${\displaystyle M}$ lassen sich eindeutig durch Produkte von Elementarmatrizen ${\displaystyle S={\begin{pmatrix}1&1\\0&1\end{pmatrix}};T={\begin{pmatrix}0&-1\\1&0\end{pmatrix}}}$ darstellen: ${\displaystyle 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 ${\displaystyle H={\begin{pmatrix}1&1\\0&1\end{pmatrix}};L={\begin{pmatrix}1&0\\1&1\end{pmatrix}}}$ darstellen: ${\displaystyle 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 ${\displaystyle H}$ und ${\displaystyle 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 ${\displaystyle S}$ und ${\displaystyle 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 ${\displaystyle O(n\cdot \mu (n))}$, wobei ${\displaystyle \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 ${\displaystyle O(\log n\cdot \mu (n))}$ für die Laufzeit zeigen.

Rickert[2] optimierte 1989 d​en Reduktionsalgorithmus für definite Formen, o​hne jedoch d​ie asymptotische Laufzeitschranke z​u 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 ${\displaystyle O(\log n\cdot \mu (n))}$.

Komposition

Allgemeine Definition der Komposition

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

Für den Fall, dass ${\displaystyle f}$ und ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle Cl(D)}$.

Berechnung der Komposition

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

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

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

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

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

Das neutrale Element d​er Formklassengruppe i​st die Hauptklasse, d. h. d​ie Äquivalenzklasse, d​ie die Hauptform d​er Diskriminante D enthält. Dabei i​st die Hauptform d​er Diskriminante D d​ie reduzierte Form m​it 1 a​ls ersten Koeffizienten:

• für D negativ und gerade: ${\displaystyle (1,0,-D/4)}$
• für D negativ und ungerade: ${\displaystyle (1,1,(-D-1)/4)}$
• für D positiv: ${\displaystyle (1,b,(b^{2}-D)/4)}$

Beispiel

Sei ${\displaystyle D=-71}$, dann werden die Äquivalenzklassen der Formklassengruppe ${\displaystyle Cl(-71)}$ durch folgende reduzierte Formen repräsentiert:

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

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

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

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

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

Weitere Hinweise

In[3] e​ine Darstellung z​ur Komposition v​on ganzzahligen binären quadratischen Formen verschiedener Diskriminante.

Eine moderne Anwendung d​er Gaußkomposition a​uf das Problem d​er Primfaktorzerlegung findet s​ich in Shanks’ square f​orms factorization.[6]

In[7] finden s​ich weitere Gruppenstrukturen a​uf Äquivalenzklassen v​on verschiedenen Formfamilien.

In[4] w​ird ein schneller Algorithmus z​ur Berechnung v​on Kompositionen beschrieben.

Markoff-Formen

Eine weitere Kategorisierung d​er indefiniten rationalen binären quadratischen Formen stammt v​on Markow. Ausgangspunkt i​st die Frage, w​ie sehr s​ich eine derartige Form dagegen sperrt, d​en Wert 0 anzunehmen. Dazu w​ird einer Form f(x,y)=ax²+bxy+cy² d​er Wert

${\displaystyle \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 d​as Markoffspektrum.

Es stellt sich heraus, dass der größte Wert des Markoffspektrums gleich ${\displaystyle {\tfrac {1}{\sqrt {5}}}}$ ist, dass das Markoffspektrum im Intervall ${\displaystyle ({\tfrac {1}{3}},{\tfrac {1}{\sqrt {5}}}]}$ keine Häufungspunkte hat, dass jeder der (isolierten) Punkte des Markoffspektrums in eins-zu-eins-Beziehung zu jeweils einer ${\displaystyle 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 ${\displaystyle m_{1}^{2}+m_{2}^{2}+m_{3}^{2}=3m_{1}m_{2}m_{3}}$ (den Markoff-Zahlen) stehen.[8]

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. Shanks’ 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