Lovász theta 函数与零错误容量上界

一组互不混淆的码字在向量表示里两两正交。单位柄向量总共只有长度平方1，不能在太多相互正交方向上都保留很大的投影。

如果每个顶点方向都与柄至少有 $1/\sqrt{t}$ 的投影，那么每个独立码字至少消耗 $1/t$ 的投影平方预算，独立集大小就不超过 $t$。张量积把这份几何证书带到任意块长，因而不是只约束一次码。

先把一次上界推广到所有块长 ​

设某份表示满足 $|c^T{u}_i{|}^2\ge 1/t$。对独立集 $I$，其向量正交，由 Bessel 不等式

所以 $\alpha (G)\le t$。对长度 $n$ 的顶点串，用张量积公理库张量积Tensor product把双线性映射统一因子化为线性映射，并可在交换环上的模中以平衡关系构造的张量积。向量 $u_{i_1}\otimes \cdots \otimes u_{i_n}$ 和柄 $c^{\otimes n}$。强积中不相邻的两串至少有一坐标为不同非邻点，所以张量内积含有一个零因子；表示仍合法。

柄投影平方为各坐标投影平方的乘积，至少 $t^{-n}$，故 $\alpha (G^{⊠n})\le t^n$。取 $n$ 次方根及最小的 $t$，就得到容量上界。

五边形的三维证书 ​

令 $a=1/\sqrt{5}$，对 $i=0,\dots ,4$ 取

每个向量长度为1。五边形的非边对应下标差 $\pm 2$，而

最后一步用 $\cos \left(4\pi /5\right)=-(1+\sqrt{5})/4$。柄投影平方恒为 $a$，因此 $\vartheta (C_5)\le 1/a=\sqrt{5}$。结合两字五消息码 $\mathrm{\Theta }(C_5)\ge \sqrt{5}$，得到

一个可核验的SDP下界 ​

令 $A_{{\bar{C}}_5}$ 为五边形补图的邻接矩阵，取

它在原图的边上为零，迹为1。补图仍是五边形，邻接特征值为 $2$、$(\sqrt{5}-1)/2$（二重）、$-(\sqrt{5}+1)/2$（二重）。代入可见 $X$ 的特征值全部非负，故它是可行解；每行有两个相同非零非对角项，目标值为 $1+\sqrt{5}-1=\sqrt{5}$。

这里几何表示给上界，SDP 可行矩阵给下界，两张证书方向不同，最终数值一致。对完全图 $K_m$，式 (3) 只能保留对角线，目标为1；无边图可取 $X=J/m$，目标为 $m$，也与式 (1) 一致。

两个定义如何通过原对偶接上 ​

式 (3) 是实对称矩阵空间中、采用迹内积的半正定锥规划公理库锥规划的对偶与证书Conic programming certificates · Conic duality用对偶锥统一最优性与不可行性证书，并以二阶半正定规划区分零间隙、最优值可达和弱不可行。。其对偶可写成：最小化 $t$，找 $Z⪰0$，使 $Z_{ii}=t-1$，且在不同非邻点上 $Z_{ij}=-1$。记 $m=|V(G)|\ge 1$。原问题有满足全部等式的严格可行点 $I/m\succ 0$，其迹为一的半正定可行集又是紧的，目标因而取得有限最大值。采用最大化形式的 Slater 强对偶后，对偶也取得同一最优值。

从式 (1) 的表示出发，令 ${\varphi }_i=u_i/(c^T{u}_i)$，则 ${\varphi }_i=c+v_i$ 且 $v_i\perp c$。矩阵 $Z_{ij}^0=v_i^T{v}_j$ 半正定；非边上 $Z_{ij}^0=-1$，对角线 $Z_{ii}^0=1/(c^T{u}_i{)}^2-1\le t-1$。给对角线补上非负差值，便得到对偶可行 $Z$。

反过来，写对偶矩阵 $Z$ 为向量 $v_i$ 的 Gram 矩阵，取与它们正交的单位向量 $c$，令 $u_i=(c+v_i)/\sqrt{t}$。对角线保证 $u_i$ 为单位向量，非边上的 $-1$ 保证正交，并且 $|c^T{u}_i{|}^2=1/t$。这说明原对偶数值正是式 (1) 的几何量。

强积的乘法性 ​

张量正交表示已经给出 $\vartheta (G⊠H)\le \vartheta (G)\vartheta (H)$。反向使用式 (3)：若 $X,Y$ 分别可行，则 $X\otimes Y$ 半正定、迹为1。强积的一条边至少有一坐标是原图中的真边，对应因子元素为零，所以张量矩阵在强积边上为零。其目标值为两个目标值的乘积，得到反向不等式。

theta 因而把所有块长的组合问题压到一个有限维半正定证书。但它不保证每张图的容量都等于 theta，也不保证数值求解器的近似最优值已经是严格上界。需要认证的容量上界时，应保留显式正交表示或带误差余量的对偶半正定证书。