Biquadratic SOS Rank and Double Zarankiewicz Number

Cet article introduit le nombre de Zarankiewicz double $z_2(m,n)$, basé sur des graphes bipartis contenant des arêtes simples et doubles, pour établir de nouvelles bornes inférieures précises sur le rang SOS biquadratique $\operatorname{BSR}(m,n)$, résolvant ainsi le cas $4\times3$et améliorant les bornes pour les cas$4\times4$et$5\times3$.

L'essentiel

Imaginez que vous êtes un architecte chargé de construire des structures mathématiques très spécifiques appelées formes biquadratiques. Votre objectif est de les construire en empilant des "briques carrées" (des sommes de carrés).

Le défi ? Vous voulez savoir : quelle est la taille maximale de la structure la plus complexe que vous pouvez construire sans qu'elle ne s'effondre ? En termes mathématiques, on cherche le nombre maximum de briques nécessaires pour décrire la forme la plus "difficile" possible. Ce nombre s'appelle le rang SOS (Somme de Carrés).

Voici l'histoire de ce papier, racontée simplement :

1. Le vieux problème : Le jeu du "Pas de Carré"

Pendant longtemps, les mathématiciens pensaient que la complexité de ces structures était limitée par une règle ancienne appelée le nombre de Zarankiewicz.

Imaginez un jeu sur une grille de $m$ lignes et $n$ colonnes. Vous devez placer des points (des arêtes) sur cette grille, mais avec une règle stricte : vous ne pouvez jamais former un carré parfait (un cycle de 4 points). C'est comme essayer de remplir une pièce de meubles sans jamais créer un carré vide au milieu.

• Le nombre de Zarankiewicz, noté $z(m, n)$, est le nombre maximal de meubles que vous pouvez placer sans faire de carré.
• On pensait que la complexité de nos structures mathématiques ne pouvait jamais dépasser ce nombre.

2. La découverte étrange : Le trou dans la théorie

Récemment, les auteurs ont trouvé un cas bizarre : pour une grille de 4 lignes et 3 colonnes.

• La règle du "pas de carré" permettait de placer 7 meubles.
• Mais ils ont réussi à construire une structure mathématique qui nécessitait 8 briques !
• Comment ? En ajoutant une "brique magique" qui n'est pas un simple point, mais un double point. C'est comme si, au lieu de poser une chaise, vous posiez un tabouret à deux places qui compte pour deux, mais qui ne forme pas de carré avec les autres.

Cela a créé un mystère : la théorie classique (Zarankiewicz) ne suffisait plus à expliquer la complexité réelle.

3. La nouvelle solution : Le "Double Zarankiewicz"

Pour résoudre ce mystère, les auteurs (Qi, Cui et Xu) ont inventé un nouveau concept : le nombre de Zarankiewicz Double ($z_2$).

Imaginez que votre grille de jeu a maintenant deux types de pièces :

1. Les arêtes simples (1-arêtes) : Des points classiques (une chaise).
2. Les arêtes doubles (2-arêtes) : Des "super-pièces" qui relient deux points en même temps (un tabouret à deux places).

La nouvelle règle est la suivante :

• Vous pouvez utiliser ces "super-pièces".
• Mais attention ! Si vous combinez des points simples et des super-pièces, vous ne devez toujours pas créer de "carré généralisé" (une structure trop dense qui ferait s'effondrer la construction).

En acceptant ces super-pièces, on peut remplir la grille beaucoup plus densément sans créer de carrés interdits.

4. Les résultats concrets : Ce qu'ils ont trouvé

Les auteurs ont calculé exactement combien de pièces on peut mettre dans différentes tailles de grilles :

• Grilles fines (ex: 4x3) : On passe de 7 pièces (ancienne règle) à 8 pièces (nouvelle règle). C'est la preuve que les "super-pièces" aident à construire plus grand.
• Grilles moyennes (ex: 5x3) : On passe de 8 à 9 pièces.
• Le grand mystère (4x4) :
  • L'ancienne règle permettait 9 pièces.
  • Les auteurs ont réussi à construire une structure avec 10 pièces en utilisant deux super-pièces.
  • Ils prouvent qu'on ne peut pas dépasser 11.
  • Le grand questionnement : Est-ce qu'on peut atteindre 11, ou la limite réelle est-elle 10 ? C'est encore un secret à découvrir !

5. Pourquoi est-ce important ?

Ce papier est comme une mise à jour du manuel d'instructions pour les architectes mathématiques.

• Il montre que si on accepte des formes un peu plus complexes (les "doubles arêtes"), on peut créer des structures beaucoup plus grandes et complexes qu'on ne le pensait.
• Cela relie deux mondes : la théorie des graphes (les jeux de grille) et l'algèbre (la décomposition des polynômes).
• Cela ouvre la porte à de nouvelles découvertes : peut-être que pour des grilles encore plus grandes, ces "super-pièces" permettent de construire des structures gigantesques ?

En résumé :
Les auteurs ont dit : "Hé, la vieille règle qui limitait la taille de nos constructions était trop stricte ! Si on autorise un nouveau type de pièce (le double), on peut construire des tours plus hautes. Voici exactement combien on peut monter pour les petites tours, et voici les limites pour les grandes."

C'est une avancée majeure pour comprendre la complexité cachée derrière les équations mathématiques.

Résumé technique

1. Problématique et Contexte

L'article s'inscrit à l'intersection de la théorie des graphes extrémale et de l'algèbre réelle, plus précisément dans l'étude des formes bi-quadratiques (polynômes de degré 4 en deux ensembles de variables $x$ et $y$).

• Définition du problème : On s'intéresse au rang SOS (Somme de Carrés) d'une forme bi-quadratique $P(x, y)$. Ce rang correspond au nombre minimal $r$ de formes bilinéaires $f_p(x, y)$ nécessaires pour écrire $P$ comme une somme de carrés : $P = \sum_{p=1}^r f_p^2$.
• Objectif : Déterminer le rang SOS maximal possible, noté BSR(m, n), pour les formes bi-quadratiques de taille $m \times n$.
• Contexte antérieur : Il a été établi récemment que le rang maximal est borné inférieurement par le nombre de Zarankiewicz classique $z(m, n)$, qui représente le nombre maximal d'arêtes dans un graphe biparti $m \times n$ sans cycle $C_4$ (sous-graphe complet $K_{2,2}$).
• Le paradoxe découvert : Une étude précédente a révélé un écart pour le cas $4 \times 3$:$BSR(4, 3) \ge 8$, alors que$z(4, 3) = 7$. Cet écart provient de la construction d'une forme bi-quadratique incluant le carré d'une forme bilinéaire à deux termes (ex:$(x_4y_2 + x_1y_3)^2$), qui ne correspond pas à une simple arête du graphe biparti classique.

L'objectif de cet article est de combler cet écart théorique en introduisant un nouveau paramètre combinatoire capable de capturer ces phénomènes.

2. Méthodologie et Concepts Clés

Les auteurs introduisent une généralisation du problème de Zarankiewicz pour modéliser les termes de carrés de sommes.

A. Le Nombre de Zarankiewicz Double ($z_2(m, n)$)

Les auteurs définissent une nouvelle classe de graphes bipartis $G = (S, T, E)$ où l'ensemble des arêtes $E$ est la réunion de deux types :

1. Arêtes simples (1-arêtes) : De la forme $(i, j)$, correspondant aux termes $x_i^2 y_j^2$.
2. Arêtes doubles (2-arêtes) : De la forme $(i, j; k, l)$, correspondant aux carrés de sommes $(x_i y_j + x_k y_l)^2$.

À chaque tel graphe est associée une forme bi-quadratique doublement simple :
$$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$$

B. Condition d'Irréductibilité (Cycles $C_4$ Généralisés)

Pour que le rang SOS de $P_G$ soit égal au nombre total d'arêtes $|E_1| + |E_2|$, le graphe ne doit pas contenir de cycle $C_4$ généralisé. La définition (Définition 2.1) impose deux conditions d'interdiction :

1. Condition Combinatoire (i) : Dans tout sous-graphe $2 \times 2$ (deux lignes distinctes, deux colonnes distinctes), le nombre total d'arêtes "ordinaires" (comptant une 1-arête pour 1 et une 2-arête pour 2 si ses deux composantes sont dans le bloc) ne doit pas dépasser 3.
2. Condition Algébrique (ii) : Il ne doit exister aucune combinaison linéaire non triviale des vecteurs de base associés aux arêtes dans un bloc $2 \times 2$ qui s'annule. Cela garantit l'indépendance linéaire nécessaire à l'irréductibilité.

Le nombre de Zarankiewicz double $z_2(m, n)$ est défini comme le nombre maximal d'arêtes ($|E_1| + |E_2|$) pour un graphe satisfaisant ces conditions.

C. Théorème Fondamental

Le théorème principal (Théorème 2.4) établit que si un graphe $G$ n'a pas de cycle $C_4$ généralisé, alors sa forme associée $P_G$ est irréductible et son rang SOS est exactement $|E_1| + |E_2|$. Par conséquent :
$$BSR(m, n) \ge z_2(m, n)$$

3. Résultats Principaux

Les auteurs déterminent les valeurs exactes de $z_2(m, n)$ pour plusieurs petits paramètres et établissent des bornes pour d'autres cas.

• Cas triviaux et symétriques :

  • $z_2(m, 2) = m + 1$
  • $z_2(2, n) = n + 1$
  • $z_2(3, 3) = 6$ (coïncide avec $z(3, 3)$)

• Résolution de l'écart $4 \times 3$ :

  • Les auteurs prouvent que $z_2(4, 3) = 8$.
  • Cela confirme et explique mathématiquement pourquoi $BSR(4, 3) \ge 8 > z(4, 3) = 7$. La construction utilise 7 arêtes simples et 1 arête double.

• Cas $5 \times 3$ :

  • Les auteurs prouvent que $z_2(5, 3) = 9$.
  • Cela améliore la borne inférieure connue pour $BSR(5, 3)$, qui était auparavant limitée par $z(5, 3) = 8$.

• Cas $4 \times 4$ (Problème ouvert) :

  • Une construction est proposée avec 10 arêtes (8 simples + 2 doubles) sans cycle généralisé, prouvant $z_2(4, 4) \ge 10$.
  • Une borne supérieure est établie par un argument de comptage : $z_2(4, 4) \le 11$.
  • La valeur exacte reste inconnue, bien que les auteurs conjecturent qu'elle soit égale à 10.

4. Signification et Implications

• Théorie des Graphes Extremale : Ce travail étend le problème classique de Zarankiewicz en introduisant une nouvelle structure de graphe mixte (arêtes simples et doubles). Il montre que l'interdiction des cycles $C_4$ classiques n'est pas suffisante pour borner le rang SOS ; il faut considérer des obstructions combinatoires et algébriques plus fines.
• Algèbre et Optimisation : Le résultat établit un lien direct entre la structure combinatoire des graphes et le rang de décomposition SOS des polynômes. Il démontre que l'ajout de termes de type $(x_i y_j + x_k y_l)^2$ permet d'atteindre des rangs SOS strictement supérieurs à ceux prédits par les graphes bipartis $C_4$-free classiques.
• Nouvelles bornes : Les résultats améliorent significativement les bornes inférieures connues pour le rang SOS maximal $BSR(m, n)$, en particulier pour les dimensions $4 \times 3$,$5 \times 3$et$4 \times 4$.

5. Questions Ouvertes et Perspectives

L'article conclut en identifiant plusieurs pistes de recherche futures :

1. Détermination de $z_2(4, 4)$ : Résoudre si la valeur est 10 ou 11.
2. Comportement asymptotique : Comment $z_2(m, n)$ se compare-t-il à $z(m, n)$ pour de grandes dimensions ? L'amélioration est-elle linéaire ou quadratique ?
3. Réciproque : Toute forme bi-quadratique extrémale peut-elle être représentée par une forme doublement simple issue d'un graphe $z_2$-maximal ?
4. Algorithmique : Développer des algorithmes efficaces pour calculer $z_2(m, n)$ en exploitant les conditions d'indépendance linéaire.

En résumé, cet article propose un cadre théorique robuste pour comprendre les limites du rang SOS des formes bi-quadratiques, en introduisant le concept de nombre de Zarankiewicz double comme outil central reliant la combinatoire des graphes et l'algèbre des sommes de carrés.