Binäre quadratische Form

Grundbegriffe, Eigenschaften und Ziele

Eine binäre quadratische Form ist eine quadratische Form in zwei Variablen x und y, also ein Polynom der Gestalt f(x,y)=ax²+bxy+cy². Die Koeffizienten a,b,c werden kurz als f=(a,b,c) geschrieben. In der Zahlentheorie betrachtet man vor allem ganzzahlige Lösungen. 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. Formen über den reellen Zahlen heißen reelle, Formen über dem Ring der ganzen Zahlen ganzzahlige binäre quadratische Formen.

Eine ganzzahlige Form f=(a,b,c) heißt ambig, wenn b=ka mit k∈ℤ gilt, und primitiv, wenn ggT(a,b,c)=1 gilt. Ihre Diskriminante ist D_f:=b²−4ac.

Eine Form repräsentiert eine ganze Zahl n∈ℤ, wenn es ein Paar (x₀,y₀)∈ℤ² mit f(x₀,y₀)=n gibt. Dieses Paar heißt Repräsentation von n; sie ist primitiv, wenn ggT(x₀,y₀)=1 gilt. Wichtige Fragen sind, welche Zahlen eine Form repräsentiert und wie viele beziehungsweise welche Repräsentationen sie besitzen. Das Minimum ist definiert durch λ₁(f):=inf{√|f(x,y)| : (x,y)∈ℤ², (x,y)≠(0,0)}.

Die Theorie dient unter anderem zum Lösen diophantischer Gleichungen ax²+bxy+cy²=n, zum Finden eines kürzesten Vektors in einem Gitter, zur Faktorisierung ganzer Zahlen mithilfe ambiger Formen und zur Behandlung kryptographischer Probleme über Beziehungen zu quadratischen Zahlkörpern.

Matrizen und Äquivalenz

Zu f=(a,b,c) gehört die Dreiecksmatrix M_d(f)=((a,b),(0,c)). Damit gilt f(x,y)=(x,y)M_d(f)(x,y)^T, wobei T die Transposition bezeichnet. Alternativ verwendet man die symmetrische Matrix M_s(f)=((a,b/2),(b/2,c)), kurz [a,b,c]. Auch dann gilt f(x,y)=(x,y)a,b,c^T. Diese Matrix liegt nur dann in A^{2×2}, wenn 2 in A invertierbar ist; bei ganzzahligen Formen liegt sie im Allgemeinen in ℚ^{2×2}. Außerdem gilt D=b²−4ac=−4·det[a,b,c].

Eine unimodulare Substitution (x′,y′)=U(x,y)^T mit U∈SL₂(ℤ) überführt eine Form in eine äquivalente Form. Genauer gilt U^T[a,b,c]U=[α,β,γ]. Zwei Formen heißen äquivalent, wenn eine solche Matrix U existiert. Man schreibt [α,β,γ]∼[a,b,c] oder (a,b,c)=(α,β,γ)U; für eine Form f gilt (fU)(x,y)=f(U(x,y)). Diese Äquivalenz wird auch echte Äquivalenz genannt. Ein allgemeinerer Äquivalenzbegriff verwendet Matrizen aus GL₂(ℤ).

Äquivalente Formen repräsentieren dieselben Zahlen, und aus einer Repräsentation einer Zahl durch die eine Form lässt sich eine Repräsentation durch die andere mit der Transformationsmatrix gewinnen. Außerdem besitzen äquivalente Formen dieselbe Diskriminante. Daher kann man für eine Äquivalenzklasse F(a,b,c)={ (a′,b′,c′) | (a′,b′,c′)∼(a,b,c) } eine gemeinsame Diskriminante D_F definieren.

Definitheit, Klassifikation und Reduktion

Eine Form f=(a,b,c) ist indefinit, wenn D_f>0 gilt, außer wenn D=n² für ein n∈ℕ; in diesem Fall ist sie degeneriert. Sie ist definit, wenn D_f<0. Bei a>0 heißt sie positiv definit, bei a<0 negativ definit. Positiv definite Formen repräsentieren nur positive, negativ definite nur negative Zahlen; indefinite Formen können positive und negative Zahlen repräsentieren. Für D_f≤0 spricht man auch von positiv beziehungsweise negativ semidefiniten Formen, je nachdem ob a>0 beziehungsweise a<0 gilt.

Für jede mögliche Diskriminante n∈ℤ gilt n≡0 (mod 4) oder n≡1 (mod 4); Beispiele sind −8, −7, −4, −3, 0, 1, 4, 5 und 8. Zu einer Diskriminante gehören zwar unendlich viele ganzzahlige Formen, aber nur endlich viele Äquivalenzklassen. Ihre Anzahl heißt Klassenzahl h(n); beispielsweise ist h(−23)=3.

Durch Reduktion sucht man in jeder Äquivalenzklasse einen Repräsentanten mit möglichst kleinen Koeffizienten. Eine Form heißt reduziert, wenn entsprechende Bedingungen erfüllt sind. Für positiv definite Formen gelten etwa −a<b≤a<c oder 0≤b≤a=c; äquivalent nach Gauß gilt |b|≤a≤min(c,√(−D/3)). Für negativ definite Formen gelten diese Bedingungen für [−a,−b,−c]. Für nicht degenerierte indefinite Formen gelten nach Schönhage √D−min(|2c|,|2a|)<b<√D und b>0; äquivalent nach Gauß, Lagarias oder Buell gilt 0<b<√D und √D−b<|2a|<√D. Für D=n² mit n∈ℕ⁺ gelten b=n und 0=a≤c≤n−1, für D=0 gelten a=0 und b=0.

Beispiele reduzierter Formen sind [1,0,1] bei positiver Definitheit, [−1,0,−1] bei negativer Definitheit, [1,2,−1] bei nicht degenerierter Indefinitheit und [0,2,0] bei D=n². Jede Form besitzt eine äquivalente reduzierte Form; bei definiten Formen ist sie eindeutig. Zwei nicht degenerierte indefinite Formen sind äquivalent, wenn ihre reduzierten Formen in demselben Zyklus liegen; sonst genau dann, wenn die reduzierten Formen identisch sind.

Transformationsmatrizen lassen sich aus S=((1,1),(0,1)) und T=((0,−1),(1,0)) zusammensetzen. Positive Transformationsmatrizen können mit H=((1,1),(0,1)) und L=((1,0),(1,1)) dargestellt werden. Die benötigten Potenzen werden mit Algorithmen analog zum erweiterten Euklidischen Algorithmus bestimmt. Gauß beschrieb 1801 Reduktionsalgorithmen. Lagarias schätzte 1980 deren Laufzeit ab und entwickelte eine Variante mit polynomialer Laufzeit O(n·μ(n)); für degenerierte Formen gilt O(log n·μ(n)). Rickert optimierte 1989 die Reduktion definitiver Formen. Schönhages schneller Algorithmus von 1991 besitzt die Schranke O(log n·μ(n)).

Komposition von Formen

Eine Form F heißt Komposition aus zwei Formen f und g, wenn es Bilinearformen B₁,B₂:ℤ²×ℤ²→ℤ gibt mit f(x)·g(y)=F(B₁(x,y),B₂(x,y)) für alle x,y∈ℤ². Für primitive ganzzahlige Formen f und g mit gemeinsamer Diskriminante D zeigte Gauß die Existenz eines Kompositionsalgorithmus. Die SL₂(ℤ)-Äquivalenzklassen bilden mit dieser Operation eine abelsche Gruppe, die Formklassengruppe Cl(D).

Für (a,b,c) und (a′,b′,c′) mit Diskriminante D wird zunächst n=ggT(a,a′,(b+b′)/2) bestimmt. Danach wählt man t,u,v∈ℤ mit n=at+a′u+((b+b′)/2)v und berechnet A=aa′/n², B=(ab′t+a′bu+v(bb′+D)/2)/n, C=(B²−D)/(4A).

Dann gilt (a,b,c)∘(a′,b′,c′)=(A,B,C). Die ersten beiden Schritte verwenden den erweiterten Euklidischen Algorithmus. Das Ergebnis ist im Allgemeinen noch nicht reduziert und muss zur Bestimmung der Formklassengruppe anschließend reduziert werden. Das neutrale Element ist die Hauptklasse mit der Hauptform: bei negativem geradem D ist sie (1,0,−D/4), bei negativem ungeradem D (1,1,(−D−1)/4), bei positivem D (1,b,(b²−D)/4).

Beispiel für D=−71: Die reduzierten Vertreter sind (1,1,18), (2,1,9), (2,−1,9), (3,1,6), (3,−1,6), (4,3,5) und (4,−3,5). Daher ist h(−71)=7 und die Hauptklasse (1,1,18). Für (2,1,9)∘(3,1,6) erhält man n=1, t=−2, u=2, v=−1, anschließend A=6, B=37 und C=60. Somit gilt (2,1,9)∘(3,1,6)=(6,37,60)∼(6,1,3)∼(3,−1,6). Die Gaußkomposition steht außerdem in Beziehung zur Primfaktorzerlegung, etwa bei Shanks’ square forms factorization.

Markoff-Formen und Markoffspektrum

Bei indefiniten rationalen binären quadratischen Formen untersucht man, wie stark sich eine Form dagegen sperrt, den Wert 0 anzunehmen. Einer Form f(x,y)=ax²+bxy+cy² wird der Wert inf{ |f(x,y)| : (x,y)∈ℤ²{(0,0)} } / √(b²−4ac) zugeordnet. Die Menge dieser Werte heißt Markoffspektrum.

Der größte Wert des Markoffspektrums ist 1/√5. Im Intervall (1/3,1/√5] besitzt das Markoffspektrum keine Häufungspunkte. Jeder isolierte Punkt steht in einer Eins-zu-eins-Beziehung zu einer SL₂(ℤ)-Äquivalenzklasse mit jeweils anderer Diskriminante. Die zugehörigen Formen stehen in enger Beziehung zu den ganzzahligen Lösungen der diophantischen Gleichung m₁²+m₂²+m₃²=3m₁m₂m₃, den Markoff-Zahlen.

Numerische Darstellung

Der Artikel enthält Scilab-Code zur dreidimensionalen Darstellung der Form x²+4xy+y² auf dem Bereich x,y∈[−5,5] mit Schrittweite 0,1. Dazu werden zunächst die Wertevektoren x und y und eine Nullmatrix M angelegt. In zwei Schleifen wird M(i)(j)=x(j)²+4x(j)y(i)+y(i)² berechnet. Anschließend wird die Oberfläche mit plot3d(x,y,M) geplottet.