Biquadratic SOS Rank and Double Zarankiewicz Number

Deze paper introduceert het dubbele Zarankiewicz-getal $z_2(m,n)$, gebaseerd op bipartiete grafen met zowel gewone als dubbele randen, om de ondergrens voor de maximale som-van-kwadraten-rang van biquadratische vormen te verbeteren en exacte waarden of nauwkeurigere schattingen te bieden voor diverse kleine parameters.

De kern

Hier is een uitleg van dit wetenschappelijke artikel, vertaald naar begrijpelijk Nederlands met behulp van creatieve analogieën.

De Titel: Het Dubbele Uiteinde van de Knoop

Stel je voor dat je een enorme puzzel hebt: het is een biquadratische vorm. In gewone taal is dit een ingewikkelde wiskundige formule die twee sets variabelen (laten we ze $x$ en $y$ noemen) met elkaar vermenigvuldigt. De vraag is: hoe simpel kun je deze formule maken?

Wiskundigen willen weten of ze deze formule kunnen schrijven als een som van kwadraten (SOS). Denk hierbij aan het oplossen van een vergelijking door hem te schrijven als $(A)^2 + (B)^2 + (C)^2 + \dots$.

• De SOS-rang is het aantal termen dat je nodig hebt.
• De BSR (Maximum SOS-rang) is het ergste geval: wat is het maximale aantal termen dat je ooit nodig zou kunnen hebben voor een formule van een bepaalde grootte?

Het Oude Spel: De Zarankiewicz-uitdaging

Vroeger dachten wiskundigen dat dit maximale aantal nauwkeurig overeenkwam met een bekend probleem uit de grafentheorie: het Zarankiewicz-probleem.

• De Analogie: Stel je een feestje voor met twee groepen mensen: $m$ gasten aan de linkerkant en $n$ gasten aan de rechterkant.
• Je wilt zoveel mogelijk handdrukken (randen) organiseren tussen de twee groepen.
• De Regel: Je mag geen "vierkant" vormen. Dat wil zeggen: als persoon A handt met X en Y, en persoon B handt ook met X en Y, dan heb je een vierkantje (A-X-B-Y-A). Dit mag niet.
• Het Zarankiewicz-getal ($z(m,n)$) is het maximale aantal handdrukken dat je kunt maken zonder zo'n vierkantje te creëren.

Tot voor kort dachten wiskundigen: "Het maximale aantal termen in onze formule is precies gelijk aan dit maximale aantal handdrukken."

Het Probleem: De Gaten in de Theorie

Maar toen keken ze naar een specifiek geval: 4 gasten links, 3 rechts.

• Het oude spel (Zarankiewicz) gaf een maximum van 7 handdrukken.
• Maar wiskundigen ontdekten een formule die 8 termen nodig had!
• Hoe kan dat? Er was een "gat" in de theorie. Iemand had een slimme truc bedacht: in plaats van alleen simpele handdrukken ($x_i \cdot y_j$), gebruikte hij een term die eruitzag als $(x_4 y_2 + x_1 y_3)^2$.

Dit is alsof je niet één handdruk doet, maar twee mensen die tegelijkertijd handdrukken met twee andere mensen, en dat als één "super-handdruk" telt. Dit is geen simpele lijn meer; het is een dubbele lijn of een twee-voetige stap.

De Oplossing: Het "Dubbele Zarankiewicz-getal"

De auteurs van dit artikel (Qi, Cui en Xu) zeggen: "Oké, we moeten ons spelletje updaten." Ze introduceren het Dubbele Zarankiewicz-getal ($z_2(m,n)$).

Hoe werkt dit nieuwe spel?

1. 1-randen (Gewone handdrukken): Normale lijnen tussen $x$ en $y$.
2. 2-randen (Dubbele handdrukken): Dit zijn de "super-termen". Een 2-rand verbindt twee paren tegelijk. Het is alsof je een brug bouwt die twee mensen aan de ene kant direct koppelt aan twee mensen aan de andere kant.
   • Voorbeeld: Een 2-rand is $(x_4 y_2 + x_1 y_3)^2$. Dit telt als één term in de formule, maar het beslaat vier mogelijke posities in het diagram.

De Nieuwe Regel (De "Vierkantjes" zijn nog steeds verboden):
Je mag nog steeds geen vierkantjes vormen, maar nu moeten we oppassen voor een nieuw soort vierkantje: het veralgemeende vierkantje.

• Als je te veel gewone handdrukken én dubbele handdrukken combineert, kun je toch per ongeluk een verborgen structuur creëren die de formule "instabiel" maakt (het betekent dat je de formule kunt vereenvoudigen, dus minder termen nodig hebt).
• Als je een grafiek bouwt die geen van deze verborgen vierkantjes bevat, dan is het aantal termen in je formule exact gelijk aan het aantal randen (1-randen + 2-randen).

Wat hebben ze ontdekt? (De Resultaten)

Ze hebben het nieuwe getal $z_2$ berekend voor verschillende maten:

• Kleine maten (zoals 3x3): Hier verandert er niets. Het oude getal was al goed.
• Het 4x3 geval:
  • Oud getal (Zarankiewicz): 7.
  • Nieuw getal (Dubbel): 8.
  • Betekenis: De formule heeft inderdaad 8 termen nodig. De "dubbele handdruk" truc werkt!
• Het 5x3 geval:
  • Oud getal: 8.
  • Nieuw getal: 9.
  • Ook hier wint de nieuwe methode.
• Het 4x4 geval (De grote mysterie):
  • Oud getal: 9.
  • Nieuw getal: Ze weten zeker dat het minimaal 10 is (ze hebben een constructie gevonden).
  • Ze weten zeker dat het maximaal 11 is.
  • Het raadsel: Is het precies 10 of toch 11? Dit is nog een open vraag.

Waarom is dit belangrijk?

Stel je voor dat je een ingenieur bent die een brug ontwerpt.

• Het oude model (Zarankiewicz) zei: "Je hebt maximaal 7 balken nodig."
• Het nieuwe model (Dubbel Zarankiewicz) zegt: "Wacht, als je slimme dubbele balken gebruikt, heb je er misschien 8 nodig om de brug stabiel te houden."

Dit artikel laat zien dat de wiskundige wereld van "som van kwadraten" (belangrijk voor optimalisatie, kunstmatige intelligentie en fysica) complexer is dan we dachten. Er zijn meer manieren om formules op te bouwen dan alleen simpele lijntjes.

Samengevat in één zin:
De auteurs hebben een nieuw soort "puzzelstuk" (de dubbele rand) ontdekt dat het maximale aantal bouwstenen voor bepaalde wiskundige formules verhoogt, en ze hebben de regels opgeschreven om te voorkomen dat deze puzzelstukken in elkaar vallen.

De Toekomst

Nu weten we dat het getal $z_2$ groter kan zijn dan het oude getal $z$. De volgende stap is om uit te zoeken of dit patroon doorgaat voor nog grotere formules en of we slimme algoritmen kunnen bouwen om dit sneller te berekenen. Het is een brug tussen de abstracte wereld van grafen (punten en lijnen) en de praktische wereld van het oplossen van complexe vergelijkingen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Biquadratic SOS Rank and Double Zarankiewicz Number" in het Nederlands.

Titel: Biquadratische SOS-rang en het Dubbele Zarankiewicz-getal

Auteurs: Liqun Qi, Chunfeng Cui en Yi Xu
Datum: 6 maart 2026

---

1. Probleemstelling en Achtergrond

Het artikel richt zich op het maximaliseren van de Som-van-Kwadraten (SOS) rang van $m \times n$ biquadratische vormen. Een biquadratische vorm $P(x, y)$ is een polynoom van de vorm:
$$P(x, y) = \sum_{i,k=1}^m \sum_{j,l=1}^n a_{ijkl} x_i x_k y_j y_l$$
die positief semi-definiet is ($P(x,y) \geq 0$ voor alle $x, y$). De SOS-rang is het kleinste aantal $r$ waarvoor $P$ geschreven kan worden als een som van $r$ kwadraten van bilineaire vormen. De maximale SOS-rang voor gegeven $m$ en $n$ wordt aangeduid als BSR($m, n$).

De kern van het probleem:
Recente studies hebben aangetoond dat BSR($m, n$) ondergrenzen heeft die gerelateerd zijn aan het klassieke Zarankiewicz-getal $z(m, n)$. Dit getal definieert het maximale aantal randen in een bipartiete graaf zonder $C_4$-cycli (complexe bipartiete subgrafieken $K_{2,2}$).
Echter, er werd een discrepantie ontdekt voor de parameter $4 \times 3$:

• Het klassieke Zarankiewicz-getal is $z(4, 3) = 7$.
• De maximale SOS-rang is echter $BSR(4, 3) \geq 8$.

Deze kloof ontstaat doordat een constructie een kwadraat van een bilineaire vorm met twee termen (bijv. $(x_4y_2 + x_1y_3)^2$) toevoegt aan een eenvoudige biquadratische vorm. De auteurs vragen zich af hoe dit fenomeen theoretisch kan worden gevangen binnen de extremale grafentheorie en of dit leidt tot een nieuwe ondergrens voor BSR($m, n$).

---

2. Methodologie: Het Dubbele Zarankiewicz-getal

Om de kloof tussen $z(m, n)$ en BSR($m, n$) te verklaren, introduceren de auteurs het concept van het Dubbele Zarankiewicz-getal, genoteerd als $z_2(m, n)$.

Definitie van de nieuwe graafstructuur:
In plaats van alleen gewone randen (1-randen), definiëren ze een bipartiete graaf $G = (S, T, E_1 \cup E_2)$ met twee soorten randen:

1. 1-randen ($E_1$): Gewone randen $(i, j)$ die corresponderen met termen $x_i^2 y_j^2$.
2. 2-randen ($E_2$): Randen van de vorm $(i, j; k, l)$ die corresponderen met kwadraten van sommen van twee termen, namelijk $(x_i y_j + x_k y_l)^2$.

De bijbehorende vorm:
Aan zo'n graaf wordt een "dubbel eenvoudige" biquadratische vorm $P_G$ gekoppeld:
$$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$$

Voorwaarde voor irreducibiliteit (Generalised $C_4$-cyclus):
Om te garanderen dat de SOS-rang van $P_G$ exact gelijk is aan het totale aantal randen ($|E_1| + |E_2|$), moet de graaf geen "generaliseerde $C_4$-cyclus" bevatten. Dit wordt gedefinieerd via twee voorwaarden:

1. Combinatorische voorwaarde: In elke $2 \times 2$ submatrix (twee rijen, twee kolommen) mag het totale aantal "gewone randen" (waarbij een 2-rand als twee randen telt als beide componenten in de submatrix zitten) niet meer dan 3 bedragen.
2. Lineaire onafhankelijkheid: Er mag geen niet-triviale lineaire combinatie van de basisvectoren bestaan die binnen een $2 \times 2$ blok nul wordt. Dit zorgt ervoor dat de kwadraten lineair onafhankelijk zijn.

Het getal $z_2(m, n)$ is het maximale totale aantal randen ($|E_1| + |E_2|$) in een dergelijke graaf die aan deze voorwaarden voldoet.

---

3. Belangrijkste Resultaten

De auteurs bewijzen de fundamentele ongelijkheid:
$$BSR(m, n) \geq z_2(m, n)$$
Dit betekent dat elke graaf die het dubbele Zarankiewicz-getal bereikt, direct leidt tot een irreducibele biquadratische vorm met een SOS-rang gelijk aan dat getal.

Exacte waarden en grenzen voor kleine parameters:
De paper bepaalt de exacte waarden voor diverse kleine $m$ en $n$:

• $z_2(m, 2) = m + 1$ en $z_2(2, n) = n + 1$ (overeenkomend met de bekende BSR-waarden).
• $z_2(3, 3) = 6$ (overeenkomend met $z(3, 3)$).
• $z_2(4, 3) = 8$: Dit verklaart de eerder ontdekte kloof. De constructie gebruikt 7 1-randen en 1 2-rand.
• $z_2(5, 3) = 9$: Dit verbetert de bekende ondergrens voor $BSR(5, 3)$ (waar $z(5, 3) = 8$).
• $4 \times 4$geval:** De auteurs bewijzen de grenzen **$10 \leq z_2(4, 4) \leq 11$.
  • Een constructie met 8 1-randen en 2 2-randen levert een ondergrens van 10.
  • Een tellend argument (combinatorische telling over $2 \times 2$ submatrices) levert een bovengrens van 11.
  • De exacte waarde voor $4 \times 4$ blijft een open vraag, hoewel de auteurs vermoeden dat het 10 is.

---

4. Significatie en Impact

1. Theoretische doorbraak: Het artikel biedt een verklaring voor de discrepantie tussen de klassieke Zarankiewicz-theorie en de werkelijke SOS-rang van biquadratische vormen. Het toont aan dat het toevoegen van kwadraten van bilineaire vormen met twee termen (2-randen) de maximale rang kan verhogen boven de klassieke grafische limieten.
2. Verbeterde ondergrenzen: De resultaten verbeteren de bekende ondergrenzen voor $BSR(4, 4)$ (van 9 naar ten minste 10) en $BSR(5, 3)$ (van 8 naar 9).
3. Interdisciplinaire link: Het werk creëert een sterke brug tussen extremale grafentheorie (het bestuderen van maximale randen zonder specifieke subgrafieken) en algebraïsche meetkunde/optimalisatie (de representatie van polynomen als sommen van kwadraten).
4. Toekomstperspectief: De paper identificeert de berekening van $z_2(m, n)$ als een nieuw uitdagend probleem in de combinatoriek. Het suggereert dat algoritmen gebaseerd op lineaire algebra (voor het controleren van de lineaire onafhankelijkheidsvoorwaarde) essentieel zullen zijn om deze waarden voor grotere parameters te bepalen.

Conclusie:
De introductie van het "Dubbele Zarankiewicz-getal" is een cruciale stap om de complexiteit van SOS-representaties te begrijpen. Het bewijst dat de structuur van biquadratische vormen rijker is dan wat alleen door eenvoudige bipartiete grafen (zonder $C_4$) kan worden beschreven, en opent de deur naar nieuwe onderzoeksvragen over de asymptotische gedrag en de exacte waarden van deze getallen.