论文技术总结：基于 Toeplitz SDP 的 $q$ 进制 $B_2$ 码更紧的上界

1. 研究背景与问题定义

$B_2$ 码（B2 Codes）定义：
$q$ 进制 $B_2$ 码（也称为 $2$-可分码）是指一个码字集合$C_n \subset [0, q-1]^n$，其中任意两个码字（允许相同）的和（在实数域上）都是唯一的。即对于任意$1 \le i \le j \le M$，和$c_i + c_j$ 互不相同。

研究目标：
确定 $q$ 进制 $B_2$ 码的渐近速率 $R$ 的上界。速率定义为 $R = \limsup_{n \to \infty} \frac{1}{n} \log_q |C_n|$。

现有方法的局限性：
作者之前的工作 [5] 利用信息论方法，通过考察两个独立同分布（i.i.d.）随机变量 $X, Y$ 的差 $D = X - Y$ 的熵 $H(D)$ 来推导速率上界。

• 旧方法：仅利用了碰撞概率约束 $P(X=Y) = r_0 \ge 1/q$。
• 缺陷：这种松弛（Relaxation）过于粗糙，忽略了差分布 $D$ 的完整统计结构，导致得到的熵上界 $H(D)$ 偏大，进而使得速率上界不够紧。

2. 核心方法论

本文提出了一种基于傅里叶分析和**半定规划（SDP）**的新方法来改进熵的上界估计。

2.1 差分布的傅里叶结构

设 $X, Y$ 为定义在 $\{0, \dots, q-1\}$ 上的 i.i.d. 随机变量，其概率质量函数（pmf）为 $p$。差 $D = X - Y$ 的 pmf 为 $r$。

• 自相关性质：$D$ 的 pmf $r$ 是 $p$ 的自相关函数。
• 傅里叶变换：$D$ 的特征函数 $\psi_D(\theta)$ 等于 $X$ 的特征函数模的平方，即 $\psi_D(\theta) = |\phi(\theta)|^2$。
• 非负三角多项式：这意味着 $r$ 的傅里叶级数 $R(\theta) = \sum r_k e^{ik\theta}$ 必须是一个非负三角多项式（Nonnegative Trigonometric Polynomial），且次数不超过 $q-1$。

2.2 凸优化问题构建

作者将寻找最大熵 $H(D)$ 的问题转化为一个凸优化问题：

• 目标：最大化 $-\sum r_k \log r_k$。
• 约束条件：
  1. 概率归一化：$\sum r_k = 1$。
  2. 对称性：$r_{-k} = r_k$。
  3. 碰撞概率：$r_0 \ge 1/q$。
  4. 关键新约束：$R(\theta) \ge 0, \forall \theta \in [0, 2\pi]$。

2.3 Toeplitz 半定规划（SDP）转化

利用 Fejér-Riesz 定理和 Herglotz 定理，非负三角多项式条件 $R(\theta) \ge 0$ 等价于其系数序列生成的所有 Toeplitz 矩阵 均为半正定（PSD）。

• 定义 Toeplitz 矩阵 $T^{(N)}(r)$，其元素 $T_{ij} = r_{i-j}$。
• 约束转化为：对于所有 $N \ge 1$，$T^{(N)}(r) \succeq 0$。
• 数值求解：通过截断 $N$（即 $N \le N_{max}$），将无限约束转化为有限维的半定规划问题（SDP），利用凸优化求解器计算最优熵值 $h^F_q$。

2.4 速率上界推导

将改进后的熵上界 $h^F_q$ 代入前缀 - 后缀（Prefix-Suffix）论证框架中：

1. 将码字分为前缀和后缀。
2. 利用 $B_2$ 性质证明后缀差集合无重复。
3. 建立速率不等式：$R \le \frac{h^F_q}{\log q + h^F_q}$。

3. 主要贡献

1. 引入傅里叶分析松弛：首次将差分布 $D=X-Y$ 的特征函数非负性（即 $R(\theta) \ge 0$）作为约束引入 $B_2$ 码速率上界的推导中，超越了仅使用 $P(X=Y) \ge 1/q$ 的旧方法。
2. 建立 Toeplitz SDP 等价性：明确证明了非负三角多项式约束等价于无穷族 Toeplitz 矩阵的半正定约束，将问题转化为标准的凸优化问题。
3. 严格改进的速率上界：证明了新的熵上界 $h^F_q$ 严格小于旧的上界 $\bar{h}_q$，从而导出了更紧的 $B_2$ 码速率上界。
4. 数值验证与新纪录：通过截断 Toeplitz SDP 进行数值计算，针对 $q \in \{9, 10, 11, 12, 13\}$ 的情况，获得了优于现有文献（包括 Lindström [3], Wang [7] 及作者之前的工作 [5]）的最佳已知上界。

4. 数值结果

论文在 Section V 中提供了具体的数值对比（见表 I）。对于 $q=9$ 到 $13$，新方法（$R^{new}_q$）显著降低了速率上界：

$q$	新方法 ($R^{new}_q$)	Lindström [3]	作者之前 [5]	Wang [7]
9	0.55792	0.57551	0.56149	0.55841
10	0.55611	0.56839	0.55966	0.55727
11	0.55457	0.56264	0.55807	0.55626
12	0.55323	0.55789	0.55668	0.55536
13	0.55206	0.55390	0.55545	0.55454

注：所有数值均向上取整。新方法在所有列出的 $q$ 值上均优于其他所有已知界限。

5. 意义与展望

学术意义：

• 本文展示了在组合编码理论中，利用**调和分析（Harmonic Analysis）**工具（特别是非负三角多项式和 Toeplitz 矩阵性质）可以显著改进基于信息论的界限。
• 它揭示了仅依靠碰撞概率（Collision Probability）约束是不够的，差分布的整体正定性结构对于限制熵至关重要。

未来方向：

• 松弛间隙分析：研究当前松弛（仅要求 $R(\theta) \ge 0$）与原始问题（要求存在非负系数的谱因子）之间的间隙大小。
• 扩展应用：将该方法推广到更高阶的和集问题（如 $B_h$ 码），或应用于其他具有结构化差分布的码型。
• 额外约束：探索是否可以通过添加矩约束（Moment Constraints）来进一步收紧松弛。

总结：
该论文通过结合傅里叶分析与半定规划，成功打破了 $q$ 进制 $B_2$ 码速率上界的长期瓶颈，为 $q \in \{9, \dots, 13\}$ 提供了目前最紧的理论界限，为后续编码理论的研究提供了新的数学工具和视角。