Biquadratic SOS Rank and Double Zarankiewicz Number

本文引入了双 Zarankiewicz 数 $z_2(m,n)$ 这一新概念，通过研究包含普通边和“双边”的广义二部图及其对应的双简单双二次型，证明了 SOS 秩的下界可由该数确定，并计算了多个小参数下的精确值从而改进了 $\operatorname{BSR}(m,n)$ 的已知下界。

要点

这篇论文探讨了一个非常抽象的数学问题，但我们可以用**“拼图游戏”和“建筑积木”**的比喻来理解它。

1. 故事背景：我们在玩什么游戏？

想象你有一个巨大的乐高积木板，板子被分成了两排：左边有 $m$ 个插槽（代表 $x$），右边有 $n$ 个插槽（代表 $y$）。

• 普通积木（1-边）： 你可以把一块普通的积木插在左边的某个插槽和右边的某个插槽之间。这就像在两个点之间画一条线。
• 超级积木（2-边）： 这篇论文引入了一个新概念，叫“超级积木”。这种积木一次能同时连接两个左插槽和两个右插槽。在数学上，这相当于把两个普通连接“打包”在一起，变成一个平方项（比如 $(x_4y_2 + x_1y_3)^2$）。

我们的目标是什么？
我们要在这个板上尽可能多地放积木，但是有一个严格的规则：

规则： 你不能用积木拼出一个“完整的正方形”（在数学上叫 $C_4$ 环）。
想象一下，如果你选了左上、右上、左下、右下四个点，并且它们两两之间都有连线，这就形成了一个“正方形”。这是被禁止的，因为一旦有了这个正方形，整个结构就会变得“不稳定”（在数学上意味着可以分解成更少的积木，不再是“最简”结构）。

2. 核心问题：我们最多能放多少块？

数学家们一直在研究：在 $m \times n$ 的板子上，最多能放多少块普通积木而不形成正方形？

• 这个最大数量有一个著名的名字，叫扎兰凯维奇数 (Zarankiewicz number)，记作 $z(m, n)$。
• 这就好比问：在一个 $4 \times 3$ 的格子里，最多能画几条线而不围成正方形？答案是 7 条。

但是，论文发现了一个“漏洞”：
在 $4 \times 3$ 的情况下，如果你只允许用普通积木，最多只能放 7 块。但是，如果你允许使用刚才说的**“超级积木”**（2-边），你竟然可以放下 8 块！

• 这就像是你发现了一种新玩法：虽然不能画 8 条独立的线，但你可以用 7 条线 + 1 个“超级双连积木”来凑出 8 个连接点，而且依然不违反“不能形成正方形”的规则。

3. 这篇论文做了什么？

作者们决定把这个新玩法正式化，并给它起名叫**“双扎兰凯维奇数” (Double Zarankiewicz number)**，记作 $z_2(m, n)$。

他们做了三件大事：

1. 定义了规则： 他们详细规定了什么是“广义的正方形”。

   • 如果是普通积木，就是四条线围成圈。
   • 如果有超级积木，规则变得更复杂：如果超级积木的两个部分加上其他普通积木，在某个局部区域凑够了“四个连接点”，那也算违规。
   • 他们还引入了一个**“线性代数检查”**（就像检查积木是否真的稳固），确保这些积木组合在一起时，不能通过简单的数学变换被拆散。

2. 计算了具体数值： 他们像解数学题一样，算出了不同大小板子的极限：

   • $4 \times 3$ 的板子： 以前以为最多 7 块，现在算出是 8 块。
   • $5 \times 3$ 的板子： 以前以为最多 8 块，现在算出是 9 块。
   • $4 \times 4$ 的板子： 这是一个大谜题。他们证明至少能放 10 块，但能不能放 11 块还不确定（就像在 10 和 11 之间卡住了）。

3. 建立了联系： 他们证明了，这个“双扎兰凯维奇数”直接对应着一种叫**“二次型”（Biquadratic form）的数学结构的“不可分解性”**。

   • 通俗解释： 在数学优化和物理模拟中，我们经常需要把一个复杂的公式写成几个简单公式的平方和（SOS）。这篇论文告诉我们：如果你能按照他们的“双积木”规则搭出一个结构，那么你就一定能构造出一个极其复杂、无法被简化的数学公式。这个公式的“复杂度”（秩）就等于你放的积木总数。

4. 为什么这很重要？（比喻总结）

想象你在设计一座最坚固的桥。

• 传统的数学家（扎兰凯维奇）告诉你：如果你只用单根钢筋（普通边），最多只能搭 7 根而不塌（形成正方形）。
• 这篇论文的作者说：“等等！如果我们用一种特殊的双股钢筋（超级边），虽然看起来还是 7 根的位置，但实际上我们利用了双股钢筋的强度，可以安全地承载 8 根钢筋的负荷，而且桥依然不会塌！”

这篇论文的意义在于：
它打破了旧有的思维定式，告诉我们通过引入新的“连接方式”（平方项），我们可以构建出比传统理论认为的更复杂、更强大的数学结构。这不仅解决了几个具体的数学难题（比如 $4 \times 3$和$5 \times 3$的情况），还为未来研究更大的数学结构（比如$4 \times 4$ 甚至更大）提供了一把新的钥匙。

一句话总结：
这篇论文发现了一种新的“积木玩法”，证明在特定的数学结构中，我们可以比传统规则允许的数量多放一块，从而构建出更复杂、更强大的数学模型。

技术摘要

这篇论文《双二次型 SOS 秩与双重 Zarankiewicz 数》（Biquadratic SOS Rank and Double Zarankiewicz Number）由 Liqun Qi、Chunfeng Cui 和 Yi Xu 撰写，主要探讨了双二次型（biquadratic forms）的平方和（SOS）秩的上界问题，并引入了一个新的图论参数——双重 Zarankiewicz 数（$z_2(m, n)$）来改进现有的下界估计。

以下是对该论文的详细技术总结：

1. 研究背景与问题提出

• 核心问题：确定 $m \times n$ 双二次型 $P(x, y)$ 的最大 SOS 秩，记为 $BSR(m, n)$。一个双二次型是 SOS 的，如果它可以表示为有限个双线性形式的平方和。
• 现有进展：
  • 已知 $BSR(m, 2) = m+1$，$BSR(2, n) = n+1$，$BSR(3, 3) = 6$。
  • 近期研究证明 $BSR(m, n) \ge z(m, n)$，其中 $z(m, n)$ 是经典的 Zarankiewicz 数，即不含 $C_4$（长度为 4 的环）的二分图的最大边数。
  • 发现缺口：在 $4 \times 3$的情况下，发现$BSR(4, 3) \ge 8$，而经典 Zarankiewicz 数$z(4, 3) = 7$。这一差距源于一种构造：在一个不含$C_4$的简单双二次型基础上，添加一个双线性形式的平方项$(x_4y_2 + x_1y_3)^2$。
• 研究动机：这种“添加平方项”的现象无法用传统的仅包含单一项（$x_i^2 y_j^2$）的简单双二次型解释。论文旨在通过引入“双重边”的概念，将这种结构纳入图论框架，从而更精确地刻画 $BSR(m, n)$ 的下界。

2. 方法论与核心定义

论文引入了双重 Zarankiewicz 数 $z_2(m, n)$ 的概念，扩展了传统的二分图模型。

• 双重二分图（Doubly Bipartite Graph）：

  • 定义了一个包含两类边的二分图 $G = (S, T, E_1 \cup E_2)$：
    • 1-边（1-edges, $E_1$）：形式为 $(i, j)$，对应传统的双二次项 $x_i^2 y_j^2$。
    • 2-边（2-edges, $E_2$）：形式为 $(i, j; k, l)$，对应双线性形式的平方 $(x_i y_j + x_k y_l)^2$。注意 $i=k$ 或 $j=l$ 是允许的，但不能同时相等。
  • 关联的双二次型定义为：
    $$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$$
  • 称此类形式为双重简单双二次型（doubly simple biquadratic form）。

• 广义 $C_4$-环（Generalized $C_4$-cycle）：
  为了保证 $P_G$ 是不可约的（即其 SOS 秩等于边数 $|E_1| + |E_2|$），必须禁止图中存在“广义 $C_4$-环”。定义包含两个条件：

  1. 计数条件：对于任意两行 $i, k$ 和两列 $j, l$ 构成的 $2 \times 2$ 子矩阵，其中包含的“普通边”总数（1-边计 1 次，2-边若完全包含在子矩阵内则计 2 次）不能超过 3。
  2. 线性无关条件：在任意 $2 \times 2$ 子矩阵对应的向量空间中，由边生成的向量不存在非平凡的线性组合为零。这确保了代数上的不可约性。

• 定义 $z_2(m, n)$：
  在不含广义 $C_4$-环的前提下，双重二分图 $G$ 的总边数 $|E_1| + |E_2|$ 的最大值。

3. 主要理论结果

• 基本不等式：
  定理 2.4：对于所有 $m, n \ge 2$，有 $BSR(m, n) \ge z_2(m, n)$。

  • 证明思路：构造一个不含广义 $C_4$-环的图 $G$，证明其对应的 $P_G$ 是不可约的，且其 SOS 秩恰好等于边数。

• 精确值与界限：
  论文计算了若干小参数下的 $z_2(m, n)$ 值：

  • 基础情形：$z_2(m, 2) = m + 1$，$z_2(2, n) = n + 1$（与经典情况一致）。
  • **$3 \times 3$**：$z_2(3, 3) = 6$（与$z(3, 3)$ 一致）。
  • $4 \times 3$**：证明了 **$z_2(4, 3) = 8$。
    • 构造：包含 7 条 1-边和 1 条 2-边（对应 $(x_4y_2 + x_1y_3)^2$）。
    • 这解释了文献 [9] 中发现的 $BSR(4, 3) \ge 8 > z(4, 3)=7$ 的缺口。
  • $5 \times 3$**：证明了 **$z_2(5, 3) = 9$。
    • 构造：包含 8 条 1-边和 1 条 2-边。
    • 改进了下界：$BSR(5, 3) \ge 9$（此前已知 $z(5, 3)=8$）。
  • $4 \times 4$**：建立了界限 **$10 \le z_2(4, 4) \le 11$。
    • 下界：构造了一个包含 8 条 1-边和 2 条 2-边的图，总边数为 10。
    • 上界：通过计数论证证明 $M \le 12$（$M$ 为普通边加权总数），进而推导出 $T \le 11$。
    • 开放问题：$z_2(4, 4)$ 的确切值是 10 还是 11？作者猜想为 10。

4. 关键贡献

1. 概念创新：提出了“双重 Zarankiewicz 数”和“双重简单双二次型”，成功将双线性形式平方项的代数结构映射为图论中的“双重边”。
2. 解释缺口：从图论角度严格解释了为何 $BSR(4, 3)$ 可以超过经典 Zarankiewicz 数 $z(4, 3)$，揭示了 $C_4$-free 条件在引入平方项后的推广形式（广义 $C_4$-环）。
3. 改进下界：显著改进了 $BSR(4, 4)$ 和 $BSR(5, 3)$ 的已知下界。特别是对于 $4 \times 4$情形，将下界从$z(4, 4)=9$ 提升至 10。
4. 方法论结合：展示了极值图论（Extremal Graph Theory）与多项式 SOS 表示理论之间的深刻联系，利用线性代数条件（向量线性无关性）来刻画图的结构限制。

5. 意义与未来展望

• 理论意义：该工作表明，在研究双二次型的 SOS 秩时，仅考虑单项式（对应 1-边）是不够的，必须考虑交叉项的平方（对应 2-边）。这为理解高维 SOS 分解的复杂性提供了新的视角。
• 开放问题：
  • 确定 $z_2(4, 4)$ 的确切值（10 或 11）。
  • 研究更大参数（$m, n \ge 5$）下 $z_2(m, n)$ 的渐近行为，特别是它相对于经典 $z(m, n)$ 的增长幅度。
  • 探索是否存在逆命题：是否每个极值 SOS 双二次型都可以通过某种变量变换由双重简单形式表示？
  • 开发算法来高效计算或界定 $z_2(m, n)$。

总结：这篇论文通过引入图论中的“双重边”概念，成功解决了 $BSR(m, n)$ 下界估计中的一个长期存在的缺口，建立了 $BSR(m, n) \ge z_2(m, n)$ 的强不等式，并为极值图论与优化理论（SOS 规划）的交叉研究开辟了新路径。