向量差

《Discrete Mathematics》：Vector trifference

　　摘要
我们研究了Trifference概念的几何推广，这一概念最初由Elias在研究零错误信道容量时提出。在离散设置中，如果对于任意三个不同的码字??,??,?? ∈??，都存在一个坐标?? ∈[??]使得????,????,????互不相同，则称该码??为trifferent。确定此类码的最大大小仍然是一个未解决的核心问题；经典的upper bound |??| ≤2 ?(3/2)??虽然通过一个简单的“修剪”论证得到了证明，但尚未有显著改进。受到寻找新技术的启发，并且与其他经典组合概念的向量扩展保持一致，我们引入了向量trifferent码的概念。考虑?? ?(??2)??，其中字母表是单位球面??2= {??∈?3:‖??‖=1}。如果对于任意三个不同的??,??,?? ∈??，都存在一个索引i使得向量????,????,????相互正交，则称该码??为向量trifferent。将向量问题直接简化到离散设置似乎是不可行的，这使得复制Elias的修剪论证变得困难。尽管如此，我们开发了一种新方法，得出了向量trifferent码大小的下界：|??|≤(√2+???(1))?(3/2)??。有趣的是，当我们的方法被修改并适应到离散设置后，可以显著改进Elias的界限：|??| ????1/? ?(3/2)??。这种改进源自一种与[2]中的方法类似但不完全相同的技术。然而，它仍然低于[2]中得到的更精确的n?2/?因子。我们还将该概念推广到更丰富的字母表上，并证明了对于一般k-分离码的Fredman-Komlós定理[3]的向量版本。

引言
在这项工作中，我们研究了下面定义的“trifference”概念的几何推广。定义1.1 Trdifferent码
对于一个整数??> 0，如果存在一个坐标?? ∈{1,…,??}使得三个不同的字符串??,??, z都属于{0,1,2}??且????,????,????互不相同，则称这三个字符串为trifferent。长度为n的trifferent码是一个子集?? ?{0,1,2}??，其中任意三个不同的码字??,??,?? ∈??都是trifferent的。Elias首次提出了寻找长度为n的trifferent码的最大可能大小的问题，这个问题在零错误信息论和哈希函数组合学的交叉领域占据了重要地位。对这种码的最大可能大小进行上界估计和理解引起了相当大的关注（例如，请参见2014年Shannon讲座：‘关于可区分差异的数学’，作者为János K?rner）。Elias首次提出了一个上界，表明|??| ≤23(32)??；另一方面，当前最好的下界是|??| ?(95)??/?，这是通过[4]中的半随机构造得到的。此后，关于trifference问题在更丰富的字母表和各种哈希要求下的扩展获得了许多研究成果，包括关于k-分离码（trifferent码的k进制类比）的开创性结果[3]（更多详细讨论请参见[2]的引言）。然而，要大幅改进Elias最初的界限仍然具有挑战性。后续的工作通过计算机搜索低维trifferent码来 refined 这一界限：[5]，后来[6]得出了0.6937(32)??的改进上界。在[2]中还获得了多项式因子的改进：更确切地说，界限被改进为?????2/?(32)??，其中c是一个绝对常数。还考虑了trifferent码的一些变体：例如线性trifferent码，我们将{0,1,2}视为??3，??是一个线性子空间[7],[8],[9],[10]；最近在[11]中提出了要求在多个坐标上任意三个不同的码字都互不相同的需求（与通常设置中的单个坐标相反）。本文研究了trifference概念的自然几何推广，这一研究的动机是为了引入新技术，同时也因其自身的兴趣而具有独立性。借鉴其他经典组合概念的向量扩展（如图着色中的向量色数和离散优化问题的半定松弛[12],[13]），我们将离散字母表{0,1,2}扩展到连续字母表：?3中的单位向量集，它们形成了二维球面???。此外，“trifference”的组合概念被替换为几何条件——成对正交。这导致了以下定义。定义1.2 向量trifferent码
设???= {??∈?3:‖??‖=1}。考虑一个整数?? ≥1。如果存在一个索引?? ∈{1,…,??}使得三个点??,??, z都属于(???)??且向量????,????,????相互正交，则称这三个点为向量trifferent。长度为n的向量trifferent码是一个子集?? ?(???)??，其中任意三个不同的码字??,??,?? ∈??都是向量trifferent的。这项工作的主要目标是确定向量trifferent码的最大可能大小。这种几何变体带来了独特的挑战，妨碍了直接应用离散设置中的方法。我们在下面记录了这些挑战。
1. 一种自然的方法是将几何问题简化为其离散对应问题。为此，考虑一个图G，其顶点是???上的点，并且如果相应的向量正交，则将???上的两点连接起来。如果G的色数为3，那么我们可以轻松创建一个大小为|??|的离散trifferent码：考虑使用颜色{0,1,2}对G进行任意着色，比如χ，并将?? ∈??转换为(??2(???),…,??2(???)) ∈{0,1,2}??。很容易看出，转换后的码满足上述trifference的定义。因此，如果上述情况成立，我们将得出|??| ≤23(32)??（或者使用[2]得到更强的界限）。然而，也许令人惊讶的是，G的色数是4（参见[14]的证明）。因此，上述方法将向量trifferent码转换为四进制字母表上的trifferent码：换句话说，是一个在{0,1,2,3}??上的码，对于任意三个不同的码字??,??, z，都存在一个?? ∈[??]使得????,????和????成对不同。然而，这种码的已知最佳上界是2??（遵循[1]中的相同论证），这比Elias最初的界限要差得多。有趣的是，[14]还表明，如果我们仅限制在???的有理点集上（这是???的一个稠密子集），则得到的图的色数为3。这导致了另一种尝试，我们将每个码字的每个坐标转换为{0,1,2}中的一个符号，使用与???“接近”的有理点的颜色。然而，为了使我们的转换产生trifferent码，我们需要知道图中不仅正交向量相邻，而且“几乎”正交向量也相邻的图的颜色数。因此，在某种意义上，从向量设置到熟悉的离散设置的障碍是“本质上的微不足道的”。
2. 另一种自然的尝试围绕离散设置的以下证明技术展开。考虑一个trifferent码?? ?{0,1,2}??。设??= {0,1}??。那么|?? ∩??| ≤2，因为A中的任何三个字符串都是非trifferent的。结合trifference是一个平移不变性质的观察（通过?? ∈{0,1,2}??进行平移得到?? ⊕??= {??+?????|??∈??}），我们可以说A与??的随机平移交集中的预期大小最多为2；另一方面，它是|??| ?2???。因此，我们得到|??| ≤2 ?(3/2)??。这只是对Elias界限的经典“修剪”风格的论证的重释，但实际上在[2]中被用来获得多项式改进。将上述方法应用于向量trifferent问题涉及寻找一个大的子集?? ????，使得A中不存在三个相互正交的点。设A的Lebesgue测度为α（用???(??)表示）。那么，我们得到了长度为n的向量trifferent码??的大小上界：|??|≤23(1??)??。
为了理解原因，独立且均匀地随机抽取???,…,???? ∈????2，并按坐标应用它们：映射(???,…,???) ?(???????,…,??????)保持了??的向量trdifferent性质（因为每个坐标内的正交性是旋转不变的），并且由于???上均匀测度的旋转不变性，旋转后的坐标是独立的且每个都在???上均匀分布。此外，来自??的码字落入???的预期数量是???? ?|??|。但是这个数量不能超过2，因为???中的任何三个点??,??, z都是非trifferent的。所以问题是A的最大质量是多少：越大越好，对我们的上界越有利。这个问题在[15]中被作为Witsenhausen双顶点猜想[16]的一个自然变体进行了研究。在[15]中发现存在一个A使得0.594 ≤???(??)。如果我们将这个结果应用于向量trifferent码的大小上界，我们得到的答案比(3/2)??（离散变体的近似界限）差得多。实际上，很容易将α的上界定为2/3（简单的随机论证）。这表明即使在极限情况下，这种方法也不会产生优于2 ?(3/2)??的向量trifferent码的上界。因此，向量trdifferent问题与一些有趣的几何问题相交。最近在[17]中出现了一个关于这个问题高维推广的有趣结果。
尽管存在这些挑战，本文为向量trifferent码建立了一个上界，该上界与离散情况下的界限类似。我们的主要结果表明，这种码的大小受到类似的限制，并且值得注意的是，它实现了比标准修剪论证为离散问题提供的更好”的主导常数，即Elias最初的trifferent码界限（2 ?(3/2)??）。事实上，在[2]的结果之前，改进Elias的界限依赖于寻找低块长度的最优trifferent码。

定理1.3 主要结果
设??是一个长度为n的向量trdifferent码。那么，当?? →∞时，|??|≤(√2+???(1))?(32)??。证明见第3节。如讨论所述，证明需要使用与离散设置中不同的技术，这反映了几何表述带来的挑战。在此过程中，我们证明了一个几何引理，即引理2.2，它可能具有独立的兴趣：它涉及从同一个分布在??中独立抽取的两个向量正交的最大概率。随后，我们将这些技术转移到离散设置中，并证明它们产生了一种替代方法——在精神上相似但在方法上有所不同——用于改进Elias的原始界限，如[2]中所实现的。更多细节请参见附录A。
1.4 证明概述
我们对定理1.3的证明是通过将组合“trifference”条件转化为关于某些张量积子空间的几何陈述来进行的。核心思想是在??上固定一个任意的全序，并将每对码字??< ??关联到一个结构化的子空间????,???(?3)???，该子空间捕获了????和????不成正交的坐标。论证分为三个主要步骤：
1. 成对子空间构造和正交性约束。对于每个坐标i，根据????是否与????正交，我们定义一个1维或2维的子空间??2(????,????) ??3，并获得所有坐标的张量积????,??。使用固定的全序来定向每一对，向量trifference性质确保对于任意两个不同的有序对??< ??和??< ??，子空间????,??和????,??都是正交的。这里的排序是必要的：它保证了进入论证的码字形成三个不同的元素，这正是调用trifference性质所必需的（见命题3.1）。
2. 直和分解和维度界限。上述正交性质意味着集合{????,?? :??< ??}在环境空间(?3)???内形成一个直和，其总维度为3??。对所有配对{??,??}的维度求和得到关键不等式(|??|2)???{??,??}∈(??2)2[2??2(??,??)]≤3??，其中??2(??,??)计算了????和????不成正交的坐标数，期望值是在不放回的情况下从??中均匀随机抽取x和y得到的。
3. 下界估计。数量 ??{??,??}∈(??2)?[2???(??,??)] 首先通过 ??{??,??}∈??×??2[2???(??,??)] 进行近似（即 x 和 y 从 ?? 中以有放回的方式均匀随机抽取），然后在坐标的子集 ?? ?[??] 上展开。对于每个 S，所有 ?? ∈?? 的 ????⊥???? 的概率可以通过两种方式下界限定：

- **平凡下界**：至少为 1/|??|，因为当 x = y 时该事件必然发生。
- **几何下界**：适当使用推论 2.3，我们可以证明对于任何给定的 ?? ?[??]，所有 ?? ∈?? 的 ????⊥???? 的概率至少为 (1/3)|??|。取这些下界的最大值并对所有 S 求和，可以得到一个可以通过命题 2.4 控制的组合表达式。通过优化截断参数可以平衡这两种情况，从而得到渐近下界 |??|≤(√2+??2(1))32??。

**向量 k-分离码**
在离散设置中，自然可以将概念推广到大于 3 的字母表上。

**定义 1.5** 设 ?? ≥2 为一个整数。如果对于 ?? 中的任意 k 个不同的码字，存在一个坐标 ?? ∈[??] 使得这些码字在第 i 个坐标上的符号都互不相同，则称 ?? 为 k-分离码。因此，通常所说的 trifferent 码在上述术语中就是 3-分离码。同理，我们可以定义向量 k-分离码。

**定义 1.6** 设 ?? ≥2 为一个整数，并考虑 ????1 为 ?? 中的单位球面。如果对于 ?? 中的任意 k 个不同的码字，存在一个坐标 ?? ∈[??] 使得这些码字在第 i 个坐标上的向量都互相正交，则称 ?? 为向量 k-分离码。因此，向量 trifferent 码就是向量 3-分离码。

对于 k > 3 的向量 k-分离码，已经有很多研究（见第 1.8 节）。[3] 的开创性结果表明，任何此类码的大小必须满足以下条件：log?|??|? ≤ k!k??1+??2(1) 当 ?? →∞ 时。我们希望为向量 k-分离码建立类似的结果。

一种自然的方法是尝试将其归约为离散设置；然而，与向量 trdifferent 码的情况类似，这种方法也会遇到同样的根本性障碍。特别是，球面上正交图的色数随维度呈指数增长 [18]，这阻碍了直接的归约。不过，通过将最初为 k-分离码开发的证明技术适应到向量设置中，并利用引理 2.2，我们能够得到所需的结果（见第 4 节）。

**定理 1.7** 设 ?? 为一个块长度为 n 的向量 k-分离码。那么，log?|??|? ≤ k!k??1+??2(1) 当 ?? →∞ 时。

**1.8 讨论与未解决的问题**
如前所述，引入向量 trdifferent 码的动机是为了开发新的技术，这些技术可以应用于原始的离散设置，并可能进而改进长期存在的界限。我们的证明技术通过配对向量 trdifferent 码的码字，并展示与这些配对相关的向量空间在 3?维环境中构成直和来实现。这种方法已经取得了实质性的进展：实际上可以在离散设置中进行类似的基于配对的分析，得到一个上限为 (3/2)?，其中主要常数为 1。此外，通过结合 [2] 中的思想，这个界限可以进一步精炼为 ??(???1/4?(3/2)?，虽然这个界限不如上述工作中已知的最优界限强，但它突显了另一种解决问题的思路。（更多细节见附录 A。）这自然引出了问题：Q1. 是否可以通过调整基于配对的证明或其他方法改进向量 trdifferent 码的界限中的主要常数（目前为 √2），并且这样的改进是否也能在多项式时间内改进当前的上限？从另一个角度来说，构建大型 trdifferent 码仍然是一个具有挑战性的问题。一个简单的随机构造表明存在大小约为 (9/7)?/2 的 trdifferent 码。[4] 中给出了一个更强的构造方法，通过将块长度为 4 的内部码（所谓的 tetra 码）进行随机串联，得到了大小约为 (9/5)?/4 的 trdifferent 码。由于每个 trdifferent 码根据定义也是向量 trdifferent 码，人们可能会认为构建向量 trdifferent 码至少同样可行。这自然引出了问题：Q2. ??2 的连续几何结构是否允许构建比已知离散码大得多的向量 trdifferent 码？

最后，已知有许多对经典 k-分离码界限的改进，有些针对特定的 k 值进行定制，有些则更通用地应用 [19]、[20]、[21]、[22]。还探索了放松哈希或分离要求的进一步扩展。例如，可以要求对于某些整数 ? ≥??，每当考虑 ? 个不同的码字时，存在一个坐标使得所有 k 个符号都出现 [23]、[24]。Q3. 我们能否将这些更复杂的技术适应到向量设置中？

**技术预备知识**
2.1 符号说明
如果 μ 是空间 X 上的概率测度，那么我们用 ????? 表示 μ 在 ??2 上的乘积测度。更一般地，对于任何正整数 ?，我们用 ???????? 表示 μ 与其自身的 ? 次乘积，这是一个在 ??? 上的概率测度。

接下来，我们陈述一个引理，该引理确定了从 (???1)-维球面上独立同分布抽取 ? 个向量时获得相互正交向量的最大概率。这个引理在定理 1.3 的证明中起着关键作用。

**定理 1.3 的证明**
我们首先定义一个关键的局部构造，该构造将两个向量之间的关系编码到 ?3 的一个子空间中。设 ???(?3) 表示所有 ?3 的线性子空间的集合，定义函数 ??:(?3?{0})×(?3?{0})→???(?3) 如下：
???(??,??) = {??⊥∩??⊥, 如果 ??⊥??; 否则 ??⊥。这里 ??⊥ 表示 u 在 ?3 中的正交补。注意，对于所有非零的 u 和 v，有 ???(??,??) ???⊥。

对于 ??,?? ∈??，定义对子空间 ????,?? := ∑?=1???(???,???)????=1?3，其中 ? 表示空间的张量积。根据构造，有dim????,?? = 2??(??,??)。

**定理 1.7 的证明**
我们现在转向之前介绍的向量 k-分离码。

**定理 1.7 的证明**
设 ?? ?(????1)? 为一个块长度为 n 的向量 k-分离码，并设 ???(??) ∈????1 表示码字 ?? ∈(????1)? 的第 j 个坐标。设 ? = ???2。由于 k 是固定的，?? 是一个常数；如果 |??| ≤ 2?2，则随着 ?? →∞，|??| 是有界的，因此 log?|??|/?? → 0，所声称的不等式显然成立。因此我们可以假设 |??| > 2?2，特别地 |??| > ?2；这保证了 (????) 是非空的，并且出现的因子 1???2/|??| 确保了...

**在写作过程中声明生成式 AI 和 AI 辅助技术**
在准备这项工作时，作者使用了 Claude (Anthropic) 和 ChatGPT (OpenAI) 来提高语言的流畅性、可读性和清晰度。使用这些工具后，作者根据需要进行审查和编辑，并对发表文章的内容负全责。

Siddharth Bhandari | Abhishek Khetan