走进科学
C3猜想 信息学家拿下了信息纠错码领域里的圣杯
传输一个信息。将每个字符转换成比特，每个比特转换成信号。然后通过铜缆、光纤或空气发送。尽管你尽可能地小心翼翼，但另一边收到的东西未必就是你发送的。噪声干扰不可避免。
在20世纪40年代，计算机科学家第一次面对噪声问题。五十年后，他们想出了一个优雅的方法来避开它。如果你能对信息进行编码，使其在接收者阅读之前就能明显看出是否有乱码呢？一本书不能仅通过封面来判断里面是否有印刷错误，但信息可以。
他们将这一特性称为局部可测试性，因为这样的信息可以进行超快的检验，以确定其正确性。在接下来的30年里，研究人员在创造这种测试方面取得了实质性的进展，但许多人认为局部可测试性将永远不会彻底实现。
但去年11月8日发布的一篇预印本论文里，魏兹曼科学研究院的计算机科学家Irit Dinur和四位数学家Shai Evra、Ron Livne、Alex Lubotzky和Shahar Mozes(都在耶路撒冷希伯来大学)已经找到了它。
魏茨曼科学研究所的Irit Dinur帮助构建了一个具有理想属性组合的纠错码，即使在码字规模扩大的情况下也保持不变。
"这是我所知道的数学或计算机科学中最了不起的现象之一，"华威大学的Tom Gur o说。"它是整个纠错领域的圣杯。"
哈佛大学的Madhu Sudan说："这不是一个看起来很合理的东西。结果现在突然说，你竟然能做到。"
大多数先前的数据编码方法都依赖于某种形式的随机性。但是对于局部可测试性来说，随机性是无能为力的。相反，研究人员不得不设计出一种高度非随机的图形结构，这对数学来说是全新的，他们的新方法就是基于此。这既是一种理论上的好奇心，也是使信息尽可能具有弹性的实际进步。
噪声在通信中无处不在。为了系统地分析它，研究人员首先将信息表示为一个比特序列，即1和0。然后，我们可以将噪声视为随机影响，把一段序列里的0变成1或1变成0。
有许多方法处理噪音。考虑一段信息，一个像 01 一样简短的信息。通过重复它的每一块--每一个单比特--三次来修改它，得到000111。然后，即使出现了干扰，比如说，第二和第六位--将信息变为010110--接收器仍然可以通过两次多数票(一次为0，一次为1)来纠正错误。
这样一种修改信息的方法被称为编码。应为可以纠错，所以被称为纠错码。纠错码就像字典，每一个都定义了一定的代码集，如000111。
为了工作顺利，纠错码必须有几个特性。首先，其中的码字不应该太相似：如果一个代码包含码字0000和0001，只需要一个比特翻转的噪音就可以混淆这两个词。第二，编码词不应该太长。重复的比特可能会使信息更持久，但它们也会使信息的发送时间更长。
这两个属性被称为距离和速率。一个好的代码应该同时具有大的距离(不同的码字之间)和高的速率(传输真实信息)。但如何才能同时获得这两个特性呢？1948年，克劳德·香农(Claude Shannon)表明，任何被简单地随机选择的代码都会在这两种特性之间有一个近乎最佳的权衡。然而，完全随机地选择码字会产生一个不可预测的字典，而这个字典又太难整理了。换句话说，香农表明，好的编码是存在的，但目前制造不出来。
在接下来的40年里，计算机科学家们努力找出安排比特的非随机配方，以接近随机。到20世纪80年代末，他们的编码被用于从CD到卫星传输的所有方面。
1990年，研究人员提出了局部可测试性的想法。但这个属性是不同的。如果你像香农建议的那样随机挑选一个代码，那么它就不可能是一个局部可测试的代码。这些是随机代码宇宙中的独角兽--如果它们存在的话，是很美的。
为了理解为什么可测试性如此难以获得，我们需要把一个信息不仅仅看作是一串比特，而是一个数学图：一个由边(线)连接的顶点(点)的集合。自理查德·汉明(Richard Hamming)在香农创立信息论两年后，开发第一个聪明的编码以来，这种等价关系一直是理解编码技术的核心。在(R. Michael Tanner)1981年的一篇论文之后，图论观点变得特别有影响力。
汉明的工作为20世纪80年代无处不在的纠错码创造了条件。他提出了一个规则，即每个信息都应该与一组“验证码字”配对，验证码记录信息的比特。更具体地说，每个验证码是信息中精心选择的一个比特子集的总和。当这个总和为偶数时，验证码被标记为0，当它为奇数时，被标记为1。每个由一个单一的比特表示，换句话说，研究人员称之为奇偶校验或奇偶位。
汉明指定了一个将收据附加到信息的程序。然后，收件人可以通过验证码来检测错误——计算出总和。这些汉明码工作得非常好，它们是把码看作是图和把图看作是码的起点。
德克萨斯大学奥斯汀分校的Dana Moshkovitz说："对我们来说，思考一个图形和思考一个代码是同一件事。
为了从编码转为图，对于每个信息位，画一个顶点(或节点)，称为数字节点。然后为每个奇偶校验位画一个节点；这些节点被称为奇偶校验节点。最后，从每个奇偶校验结点到数字结点画线，这些数字结点相加形成其奇偶校验值。
把代码和图形看成是等价的，成为制作代码的艺术的组成部分。1996年，迈克尔·西普斯和丹尼尔·斯皮尔曼用这种方法从一种叫做扩展图的图中创造了一种突破性的编码。他们的编码仍然不能提供局部可测试性，但它在其他方面被证明是最佳的，并最终成为新成果的基础。
扩张图有两个看似矛盾的特性。首先，它们是稀疏的。每个节点与相对较少的其他节点相连。其次，它们有一个被称为扩展性的属性--这就是它们名字的由来--这意味着没有一组节点可以成为很少有边经过的瓶颈。换句话说，每个节点都与其他节点有很好的连接--尽管它所拥有的连接很稀少。
"为什么这样的对象要存在呢？"Evra说，"如果你是稀疏的，按道理你的连接就不该那么的强。"
但是扩张图实际上出乎意料地容易创建。如果你以随机的方式构建一个图，在节点之间随机选择连接，就会不可避免地产生一个扩张图。它们就像一个纯粹的、未经提炼的随机性的来源，使它们成为香农所指向的良好代码的自然构建块。
Sipser和Spielman研究了如何将扩展图变成代码。他们想出的码是由许多由汉明码产生的更短的字组成的，他们称之为小码。他们的码字的比特被表示为扩展图的边。而小码的所有验证码都在每个节点上表示。
实际上，Sipser和Spielman表明，如果你在每个节点上定义的小码具有良好的属性，那么由于图是如此良好的连接，这些属性会传播到全局码上。这种传播给了他们一种创造良好代码的方法。
"扩展、扩展、再扩展，这就是成功的秘诀。"
然而，局部可测试性是不可能的。假设你有一个来自扩展码的有效编码，而你从一个单一的节点中移除一个验证码，或奇偶校验位。这将构成一个新的代码，它将比第一个代码有更多的有效码字，因为他们需要满足的验证码会少一个。对于根据原始代码工作的人来说，这些新的码字将满足大多数节点的收据--所有的节点，除了被抹去的那个。然而，由于这两种代码都有很大的距离，看起来正确的新码字会离原来的码字集极远。局部可测试性与扩展码根本不相容。
为了获得可测试性，最后，研究人员去了随机性不能去的地方：进入更高维度。
随机性的对立面
他们并不总是很清楚自己能做什么。2007年实现了局部可测试性，但只是以其他参数为代价，如速率和距离。特别是，这些参数会随着码字的增大而降低。在一个不断寻求发送和存储更大信息的世界里，这些收益递减是主要缺陷。(虽然在实践中，即使是现有的局部可测试的代码也已经比大多数工程师需要使用的功能更强大了)。
可以找到一个具有最佳速率、距离和局部可测试性的代码的假设--即使信息被放大，这些都保持不变--被称为c3猜想。先前的结果使一些研究人员认为，猜想是成立的。但进展开始放缓，其他结果表明该猜想可能是错误的。
"社区中的许多人认为这是一个可能好得不真实的梦想，事情看起来相当严峻。"
但在2017年，一个新的想法出现了。迪努尔和卢博茨基在参加以色列高级研究所一年的研究项目时开始合作。他们开始相信，数学家霍华德·加兰(Howard Garland)1973年的一项成果可能正是计算机科学家所寻求的。普通的扩展图基本上是一维结构，每条边只向一个方向延伸，而加兰创造了一个数学对象，可以被解释为一个跨越更高维度的扩展图，例如，该图的边被重新定义为正方形或立方体。
加兰的高维扩展图的特性似乎非常适合于局部测试性。它们必须刻意地从头开始构建，使它们成为随机性的自然对立面。而且它们的节点是如此的相互关联，以至于它们的局部特征与它们的整体外观几乎没有区别。
"对我来说，高维扩展图是一个奇迹，你对对象的局部做一个微小的调整，整体样貌会改变。"
卢博茨基和迪努尔开始尝试在加兰的工作基础上创建一个可能解决c3猜想的代码。Evra、Livne和Mozes很快加入了这个团队，他们每个人都是高维扩展器不同方面的专家。
很快，他们就在研讨会和讲座上介绍了自己的工作，但并不是每个人都相信高维扩展理论会铺平前进的道路。要完全理解它需要登上一条陡峭的学习曲线。
"当时它似乎是太空时代的技术，是计算机科学中从未见过的复杂而奇特的数学工具，"古尔说。"这似乎是矫枉过正。"
2020年，研究人员陷入了困境，直到他们意识到不依靠最复杂的新工具也能过关。他们从高维扩展中获得的灵感已经足够了。
在他们的新工作中，作者想出了如何组装扩展图来创建一个新的图，导致局部可测试代码的最佳形式。他们称他们的图为左-右Cayley复合体。
与加兰的工作一样，他们的图的组成部分不再是一维的边，而是二维的方块。编码中的每个信息位被分配到一个正方形，而奇偶校验位(或收据)被分配到边和角(是节点)。因此，每个节点都定义了可以连接到它的比特(或方块)的值。
局部可测试性的关键是结构。
为了理解他们的高维图，想象一下从内部观察它，站在一条边上。他们构建了他们的图，使每条边都有固定数量的方块相连。因此，从你的有利位置看，你会觉得你是在从一本小册子的脊柱上往外看。然而，从这本小册子的其他三面，你会看到新小册子的书脊也从它们那里分支出来。小册子会不断地从每条边上分支出来，无穷无尽。
"这是不可能想象的。这就是问题的关键所在，"卢博茨基说。"这就是为什么它是如此复杂。"
至关重要的是，这个复杂的图也具有扩张图的属性，如稀疏性和连接性，但具有更丰富的局部结构。例如，一个坐在高维扩展图一个顶点的观察者可以利用这种结构直接推断出整个图是强连接的。
"什么是随机性的反面？是结构，"埃弗拉说，"局部可测试性的关键是结构。"
为了了解这个图如何导致局部可测试的代码，请考虑在一个扩展代码中，如果一个位(也就是一个边)有错误，这个错误只能通过检查其紧邻的节点的验证码来检测。但是在一个左-右Cayley复合体中，如果一个位(一个正方形)有错误，那么这个错误可以从多个不同的节点看到，包括一些甚至没有边连接的节点。
这样一来，一个节点的测试就可以揭示出来自远处节点的错误信息。通过利用更高的维度，图的连接方式最终甚至超越了我们通常认为的连接性。
除了可测试性之外，新码还保持了速率、距离和其他所需的属性，甚至在码字扩展时也是如此，证明了c3猜想的正确性。它为纠错码建立了一个新的技术水平，同时也标志着将高维扩展图的数学应用于码的第一个实质性回报。
迪努尔说："这是看待这些物体的一种全新的方式。”
实际和理论的应用应该很快就会出现。现在，不同形式的局部可测试代码正在被用于金融行业，而最优版本将使离散工具更加完善。此外，计算机科学中有完全不同的理论构造，称为概率可检验证明，它与局部可测试码有某些相似之处。现在我们已经找到了后者的最佳形式，前者的最优形式也有了希望。
最终，新代码标志着一个概念上的里程碑，是超越随机性所设定边界的最大一步。剩下的唯一问题是，对于信息的伪造程度，是否有任何真正的限制。
https://www.quantamagazine.org/researchers-defeat-randomness-to-create-ideal-code-20211124/