Biquadratic SOS Rank and Double Zarankiewicz Number

Diese Arbeit führt die verallgemeinerte doppelte Zarankiewicz-Zahl $z_2(m,n)$ ein, um durch die Berücksichtigung von „doppelten Kanten" in bipartiten Graphen die untere Schranke für den SOS-Rang biquadratischer Formen zu verbessern und liefert exakte Werte sowie neue Schranken für verschiedene Parameter.

Das Wesentliche

Stellen Sie sich vor, Sie sind ein Architekt, der versucht, ein riesiges, komplexes Gebäude aus quadratischen Ziegeln zu bauen. Ihr Ziel ist es, das Gebäude so stabil wie möglich zu machen, aber mit einer besonderen Regel: Sie dürfen keine bestimmten Muster verwenden, die das Gebäude instabil machen könnten.

In der Welt der Mathematik (genauer gesagt der linearen Algebra und Graphentheorie) ist dieses „Gebäude" eine biquadratische Form. Das ist eine komplizierte mathematische Gleichung, die von zwei Gruppen von Variablen abhängt (nennen wir sie Gruppe X und Gruppe Y).

Hier ist die einfache Erklärung der Forschung aus diesem Papier, übersetzt in eine Geschichte:

1. Das alte Problem: Der „Zarankiewicz-Vertrag"

Früher dachten die Mathematiker, sie wüssten genau, wie viele Ziegel sie maximal verwenden können, ohne dass das Gebäude einstürzt. Diese maximale Anzahl nannten sie die Zarankiewicz-Zahl.

Die Regel war einfach: Man darf keine „C4-Zyklen" bauen. Ein C4-Zykel ist wie ein kleiner, geschlossener Viereck-Ring aus vier Ziegeln. Wenn Sie vier Ziegel so anordnen, dass sie ein Quadrat bilden (zwei von Gruppe X und zwei von Gruppe Y), ist das verboten, weil es die Struktur schwächt.

Bis vor kurzem glaubten alle: „Wenn wir keine dieser verbotenen Quadrate bauen, ist die maximale Anzahl an Ziegeln genau die Zarankiewicz-Zahl."

2. Das Rätsel: Der Riss in der Wand

Dann passierte etwas Seltsames. Bei einem speziellen Fall (4 Zeilen und 3 Spalten) stellten die Forscher fest: Es geht mehr!
Sie konnten ein Gebäude mit 8 Ziegeln bauen, obwohl die alte Regel nur 7 erlaubte.

Wie ist das möglich?
Stellen Sie sich vor, anstatt einen einzelnen Ziegel zu setzen, nehmen Sie zwei Ziegel und kleben sie mit einem sehr starken Kleber zusammen, bevor Sie sie in die Wand setzen. In der Mathematik nennen wir das eine „doppelte Kante" oder einen „2-Ziegel".
Der Trick war: Sie bauten das alte, sichere Gerüst (7 Ziegel) und fügten dann diesen speziellen „doppelten Kleber-Ziegel" hinzu. Das Gebäude war immer noch stabil, hatte aber mehr Ziegel als gedacht.

3. Die neue Erfindung: Die „Doppelte Zarankiewicz-Zahl"

Die Autoren dieses Papiers (Qi, Cui und Xu) haben gesagt: „Moment mal! Wir müssen unsere Regeln neu schreiben."

Sie haben ein neues Konzept erfunden: die Doppelte Zarankiewicz-Zahl ($z_2$).
Stellen Sie sich vor, Sie haben zwei Arten von Bausteinen:

• Einfache Steine (1-Kanten): Normale Verbindungen zwischen X und Y.
• Doppelte Steine (2-Kanten): Das sind wie „Super-Steine". Ein solcher Stein verbindet nicht nur zwei Punkte, sondern ist eigentlich das Quadrat einer Verbindung (z. B. $(x_4y_2 + x_1y_3)^2$). Er zählt als ein Baustein in Ihrer Liste, aber er hat eine innere Struktur, die zwei normale Verbindungen repräsentiert.

Die neue Frage lautet: Wie viele Steine (einfach + doppelt) können wir maximal in unser Gebäude packen, ohne dass es einen „verbotenen Riss" gibt?

4. Was ist der „verbotene Riss" (Generalisierter C4-Zykel)?

Früher war der Riss ein einfaches Quadrat aus vier Steinen. Jetzt ist es komplizierter. Ein Riss entsteht, wenn:

1. Zu viele Steine in einem kleinen 2x2-Bereich liegen (egal ob einfach oder doppelt).
2. Oder wenn die Steine so angeordnet sind, dass sie mathematisch „ineinander greifen" und sich gegenseitig aufheben (eine Art mathematisches Chaos).

Die Autoren haben bewiesen: Wenn Sie ein Gebäude bauen, das keinen dieser neuen, verbotenen Risse hat, dann ist die Anzahl Ihrer Steine die SOS-Rang (Sum-of-Squares Rank). Das ist ein Maß dafür, wie komplex die mathematische Gleichung wirklich ist.

5. Die Ergebnisse: Wir haben mehr Platz!

Die Forscher haben gerechnet und folgende Entdeckungen gemacht:

• Bei kleinen Gebäuden (z. B. 4x3): Die alte Regel sagte 7. Die neue Regel sagt 8. Der „doppelte Stein" hat uns erlaubt, einen weiteren Ziegel zu nutzen.
• Bei 5x3: Die alte Regel sagte 8. Die neue Regel sagt 9.
• Bei 4x4: Hier ist es noch ein Rätsel. Wir wissen sicher, dass wir mindestens 10 Steine nutzen können (besser als die alten 9). Aber können wir 11 schaffen? Die Autoren denken eher nein, aber es ist noch nicht bewiesen.

Warum ist das wichtig?

Stellen Sie sich vor, Sie optimieren ein Logistiknetzwerk oder eine KI. Die „SOS-Rang" sagt Ihnen, wie viele Rechenoperationen Sie mindestens brauchen, um ein Problem zu lösen.
Wenn Sie zeigen können, dass Sie mit der neuen „doppelten" Methode mehr Steine (Informationen) in ein stabiles System packen können, bedeutet das: Die alten Grenzen waren zu niedrig angesetzt.

Zusammenfassung in einem Satz:
Die Autoren haben entdeckt, dass man in bestimmten mathematischen Strukturen mehr „Bausteine" unterbringen kann als bisher gedacht, indem man nicht nur normale Verbindungen, sondern auch spezielle „doppelte Verbindungen" erlaubt, solange man ein neues, strengeres Verbot für instabile Muster (generalisierte Risse) einhält.

Das ist wie wenn man herausfände, dass man in einem Haus mehr Möbel unterbringen kann, wenn man einige Möbel als „klappbare 2-in-1-Module" baut, solange man keine instabilen Türrahmen baut.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papers auf Deutsch:

Titel: Biquadratische SOS-Ränge und die doppelte Zarankiewicz-Zahl

Autoren: Liqun Qi, Chunfeng Cui, Yi Xu
Datum: 6. März 2026

---

1. Problemstellung

Das Paper befasst sich mit der Bestimmung des maximalen Sum-of-Squares (SOS)-Rangs, bezeichnet als $BSR(m, n)$, für $m \times n$-biquadratische Formen. Eine biquadratische Form $P(x, y)$ ist eine homogene Polynomfunktion vierten Grades, die in den Variablen $x \in \mathbb{R}^m$ und $y \in \mathbb{R}^n$ quadratisch ist. Der SOS-Rang ist die minimale Anzahl $r$ von quadratischen Termen bilinearer Formen, die benötigt werden, um $P$ als Summe von Quadraten darzustellen: $P = \sum_{p=1}^r f_p(x,y)^2$.

Ein bekanntes Ergebnis verknüpft diesen Rang mit der klassischen Zarankiewicz-Zahl $z(m, n)$, welche die maximale Anzahl an Kanten in einem bipartiten Graphen ohne $C_4$-Zyklus (einen vollständigen bipartiten Untergraphen $K_{2,2}$) angibt. Es galt die Ungleichung $BSR(m, n) \ge z(m, n)$.

Das spezifische Problem:
Für den Fall $m=4, n=3$ wurde eine Lücke entdeckt: Es gilt $BSR(4, 3) \ge 8$, während die klassische Zarankiewicz-Zahl $z(4, 3) = 7$ beträgt. Dieser Unterschied entsteht durch eine Konstruktion, die das Quadrat einer zweigliedrigen bilinearen Form $(x_4y_2 + x_1y_3)^2$ zu einer einfachen biquadratischen Form hinzufügt. Diese Konstruktion lässt sich nicht durch den klassischen Zarankiewicz-Ansatz (nur einfache Kanten) erklären. Das Paper zielt darauf ab, diese Lücke theoretisch zu schließen und eine neue kombinatorische Invariante zu definieren, die diesen Phänomenen gerecht wird.

---

2. Methodik und Definitionen

Um die beobachtete Lücke zu erklären, führen die Autoren das Konzept der doppelten Zarankiewicz-Zahl, $z_2(m, n)$, ein.

Definition des erweiterten Graphen:
Es wird eine neue Klasse von bipartiten Graphen $G = (S, T, E)$ definiert, wobei $S=\{1,\dots,m\}$ und $T=\{1,\dots,n\}$. Die Kantenmenge $E$ besteht aus zwei Typen:

1. 1-Kanten (Ordinary Edges): Standardkanten der Form $(i, j)$ mit $i \in S, j \in T$. Sie entsprechen Termen der Form $x_i^2 y_j^2$.
2. 2-Kanten (Double Edges): Kanten der Form $(i, j; k, l)$ mit $i, k \in S$ und $j, l \in T$. Sie entsprechen dem Quadrat einer Summe zweier Terme, also $(x_i y_j + x_k y_l)^2$.
   • Einschränkung: Es darf nicht gelten, dass $i=k$ und $j=l$ gleichzeitig (keine trivialen Verdopplungen).

Zugeordnete biquadratische Form:
Jedem solchen Graphen wird eine "doppelt einfache" biquadratische Form $P_G$ zugeordnet:
$$P_G(x, y) = \sum_{(i,j) \in E_1} x_i^2 y_j^2 + \sum_{(i,j;k,l) \in E_2} (x_i y_j + x_k y_l)^2$$

Verallgemeinerte $C_4$-Zyklen:
Der Schlüssel zur Irreduzibilität (d.h. dass der SOS-Rang genau $|E_1| + |E_2|$ ist) ist das Fehlen von "verallgemeinerten $C_4$-Zyklen". Dies wird durch zwei Bedingungen definiert:

1. Kombinatorische Bedingung: In jedem $2 \times 2$-Submatrix (bestehend aus zwei Zeilen und zwei Spalten) darf die Anzahl der "gewöhnlichen Kanten" (wobei eine 2-Kante als zwei gewöhnliche Kanten gezählt wird, wenn beide ihre Komponenten im Submatrix liegen) höchstens 3 betragen.
2. Lineare Unabhängigkeits-Bedingung: Es darf keine nicht-triviale lineare Kombination der Basisvektoren geben, die innerhalb eines solchen $2 \times 2$-Blocks verschwindet. Dies stellt sicher, dass die Koeffizienten der SOS-Darstellung nicht reduziert werden können.

Die doppelte Zarankiewicz-Zahl $z_2(m, n)$ ist definiert als die maximale Gesamtzahl der Kanten $|E_1| + |E_2|$ in einem solchen Graphen, der keine verallgemeinerten $C_4$-Zyklen enthält.

---

3. Wichtige Beiträge und Ergebnisse

Haupttheorem (Theorem 2.4):
Es wurde bewiesen, dass für alle $m, n \ge 2$ gilt:
$$BSR(m, n) \ge z_2(m, n)$$
Das bedeutet, dass jeder Graph, der die doppelte Zarankiewicz-Zahl erreicht, eine irreduzible biquadratische Form mit einem SOS-Rang gleich der Anzahl der Kanten liefert.

Exakte Werte für kleine Parameter:
Die Autoren bestimmen die exakten Werte für $z_2(m, n)$ in mehreren Fällen:

• Triviale Fälle: $z_2(m, 2) = m + 1$ und $z_2(2, n) = n + 1$ (entspricht den bekannten Werten für $BSR$).
• **$3 \times 3$:**$z_2(3, 3) = 6$(entspricht$z(3, 3)$).
• **$4 \times 3$:**$z_2(4, 3) = 8$. Dies erklärt die zuvor bekannte Lücke, da$z(4, 3) = 7$ ist. Die Konstruktion nutzt 7 1-Kanten und 1 2-Kante.
• **$5 \times 3$:**$z_2(5, 3) = 9$. Dies verbessert die bekannte untere Schranke für$BSR(5, 3)$, da$z(5, 3) = 8$ ist.

Der Fall $4 \times 4$:

• Untere Schranke: Durch eine Konstruktion mit 8 1-Kanten und 2 2-Kanten wurde gezeigt, dass $z_2(4, 4) \ge 10$. Dies verbessert die klassische Schranke $z(4, 4) = 9$ und die triviale Schranke $m+n=8$.
• Obere Schranke: Mittels eines Zählarguments über alle $2 \times 2$-Submatrizen wurde gezeigt, dass$z_2(4, 4) \le 11$.
• Offenes Problem: Der exakte Wert von $z_2(4, 4)$ ist ungelöst (10 oder 11). Die Autoren vermuten, dass 10 der korrekte Wert ist.

Beweistechniken:
Die Beweise kombinieren Methoden der Extremalen Graphentheorie (Zählen von Kanten in Submatrizen) mit linearer Algebra (Analyse der linearen Unabhängigkeit der Vektoren, die den Kanten entsprechen). Ein zentraler Schritt ist der Nachweis, dass die Existenz einer linearen Abhängigkeit in einem $2 \times 2$-Block zu einem verallgemeinerten$C_4$-Zyklus führt, was die Irreduzibilität der Form zerstören würde.

---

4. Bedeutung und Ausblick

Wissenschaftliche Bedeutung:

1. Überwindung der klassischen Schranke: Das Paper zeigt, dass die klassische Zarankiewicz-Zahl $z(m, n)$ keine scharfe untere Schranke für den SOS-Rang biquadratischer Formen ist, wenn man Terme betrachtet, die Quadrate von Summen (2-Kanten) beinhalten.
2. Neue Verbindung: Es stellt eine tiefgreifende Verbindung zwischen der Theorie der Sum-of-Squares-Darstellungen (ein zentrales Thema in der Optimierung und algebraischen Geometrie) und der Extremalen Graphentheorie her.
3. Erweiterung des Modells: Die Einführung von "2-Kanten" erweitert das Modell der einfachen biquadratischen Formen und erlaubt eine präzisere Modellierung komplexerer algebraischer Strukturen.

Offene Fragen und zukünftige Forschung:

• Bestimmung von $z_2(4, 4)$: Ist der Wert 10 oder 11? Dies erfordert entweder eine geschicktere Konstruktion oder einen schärferen kombinatorischen Beweis.
• Asymptotisches Verhalten: Wie verhält sich $z_2(m, n)$ für große $m, n$ im Vergleich zu $z(m, n)$? Führt die Einführung von 2-Kanten zu einer quadratischen Verbesserung der Schranken?
• Algorithmische Aspekte: Kann die Prüfung auf verallgemeinerte $C_4$-Zyklen effizient auf lineare Algebra-Verfahren zurückgeführt werden, um $z_2(m, n)$ für moderate Parameter zu berechnen?
• Umkehrung: Gilt die Umkehrung des Hauptsatzes? Kann jede extremale SOS-Form durch eine doppelt einfache Form aus einem $z_2$-maximalen Graphen dargestellt werden?

Zusammenfassend etabliert dieses Paper die doppelte Zarankiewicz-Zahl als ein neues, mächtiges Werkzeug zur Bestimmung unterer Schranken für SOS-Ränge und löst dabei spezifische Lücken in der Literatur für kleine Dimensionen, während es gleichzeitig neue fundamentale Fragen für die kombinatorische Optimierung aufwirft.