分组散步引发的一个烧脑排列组合问题

原文作者：Marianne Freiberger，此文原载于+Plus Magazine网站。

翻译作者：333，哆嗒数学网翻译组成员，就读于中南大学数学专业。

如果你曾经制作过时间计划表或者之类的东西，你就会知道这不是一项轻松的工作——这也就是为什么组合数学，一门根据特定的规则设计东西的艺术，能够在数学世界中占有一席之地的原因。最近，正是在这个领域，数学家们有了一些突破。他们发现了一些很多人觉得根本不存在的特殊设计。这些设计所包含的结构非常抽象，但是它们在通讯技术领域很可能大有用处。

理解这一新发现最好的方式是从一个有趣的益智题开始。假设你有一组人，人数为9。每天他们以三个人为一组出去散步。你能做出合适的安排，以保证在四天的散步中任意两个人同组的次数不超过一次吗？

它构成了所谓的斯坦纳三元系：把n个对象（在这个例子中，n=9，对象是人）安排进一些三元组，以使得任意两个对象同组的次数不超过一次。上图显示了一个S(2,3,7)的斯坦纳系，有7个点和7条线（我们把中间的圆也当作一条线），每条线包含3个点，每两个点只同时出现在一条线上。换句话说，这些线就给出了这7个点满足上述条件的三元组。更一般地，一个斯坦纳系S(t,k,n)是指将n个对象安排进一些k元组，并满足任意t个对象在同一个k元组中出现的次数不超过一次（译注：原文为“不超过一次”，但根据“斯坦纳系”的定义，应为“恰好一次”）。

你会问一个很自然的问题：t,k,n取哪些值的时候，存在斯坦纳系？很明显，并非所有的数的组合都能够使系存在。事实上的确如此，我们有一个可除性条件：一个由t,k,n的值所确定的斯坦纳系S(t,k,n)能够存在，t,k,n必须要满足可除性条件（如图所示）。一个重要的结果来自于2014年数学家Peter Keevash的工作，这一结果表明当n充分大时，可除性条件是足够好的：如果n足够大，且t,k,n满足可除性条件，那么一个S(t,k,n)斯坦纳系必定存在。

这一结果包含了斯坦纳系的一个推广。让我们不再去想n个抽象的对象，而是考虑一个由0和1组成的长度为n的字符串（计算机使用这样的字符串，这表明它和信息技术有关联）。对于n=3,这样的字符串有(1,1,1)和(1,0,1)等。对于一个给定的n，所有这样的字符串的集合构成了一个向量空间（此处我们不详述向量空间定义的细节，读者可以参阅任何一本关于线性代数的书）。让我们把这个向量空间记作F(2,n)：2表明在我们的字符串中所出现的不同的符号只有两个（0和1）；n表明字符串的长度。每个向量空间都有一个维数，在这里，维数就是n，即字符串的长度。

正如一个n元集合有子集，一个n维的向量空间也有维数小一些的子空间。这导致我们思考一个类似于斯坦纳系的问题：给定一个向量空间F(2,n)，数字t和k，你能找出F(2,n)的某些k维子空间，使得F(2,n)的每一个t维子空间都只包含于其中的一个k维子空间中吗？如果这样的系存在，我们称其为S(2;t,k,n)。（用数字2也是有可能构成一个向量空间的，数字2在我们的这个例子中告诉我们字符串只由两个符号构成，用别的数q代替2，我们记这样的向量空间为F(q,n)，与之相关的斯坦纳系统记作S(q;t,k,n)）

直到最近，数学家们都认为大家关心的形如S(q;t,k,n)形式的系的具体例子并不存在。不过，Michael Braun, Tuvi Etzion, Patric R.J. Östergård, Alexander Vardy 和Alfred Wassermann实力打脸，他们把这个预言证否了。特别的，他们找到了S(2;2,3,13)形式的几个不同的系。

“寻找过程充满挑战，因为所涉及的结构数目巨大，” Ostergard说，“即使是在高性能计算机的帮助下，寻找它们也是一项艰苦的行动。因此，除了使用代数技巧和计算机，我们也得运用自己的经验去猜测从何处开始搜寻，以缩小搜索的范围。”

数学家们会很高兴，因为这一结果解决了一个长期屹立不倒的问题。然而，这个结果还有一个令人惊讶的实际用处。通讯行业严重依赖于纠错码：这个想法是给信息用某种方式编码，使其即使在传输过程中产生了错误，这些错误也能被自动消除。结果证明，S(2;2,3,13)系统给某种特别的纠错技术提供了最优的编码。“我们的发现并不能直接变成产品，但是它或许将逐渐成为因特网的一部分。” Ostergard说道。最新结果已在Forum of Mathematics, Pi发帖（剑桥大学出版社网站的数学论坛）。