最小超排列问题:简介与近况

  1. 2月前

    FatFish

    1楼 10月30日 物理版主, 优秀回答者
    2周前FatFish 重新编辑

    本文数学只涉及中学排列组合水平。请放心阅读。


    序言

      我们知道,对$n$个不同字符来说,他们能组成的连续不同全排列数量是$n!$个,而所谓超排列(superpermutation)字符串,就是指我们可以从这个字符串中找到所有这$n!$个排列。自然,直接将这$n!$个排列个挨个写下来,就可以得到一个长为$n\times n!$的超排列。不过这样未免铺张浪费,几个排列之间可以公用一些字符,压缩长度。例如说121就同样包含12、21两个排列。 而123121321则是一个长为9的三字符超排列,读者可以设想有一个长为3的“取景框”从开头一步步向右移动,取到123、231、312、一个并非全排列的121、213、132、321全部六种排列。自然,这时候我们会问一个问题:$n$个字符的超排列,最短能有多长?

    0.1 约定与基本概念
    在我们正式考察这个问题之前,先对文中将会频繁使用的符号和常用概念做一些说明:

    ·本文将$n$个不同字符的最小超排列长度记为$\ell_n$.

    ·此问题只关注字符之间的排序,具体采取什么字符无关紧要,如121、212、aba、d2d、$\clubsuit\heartsuit\clubsuit$等在比较排序的意义上没有区别。因此可以直接用$123\dots n$代表一个一般的n字符全排列。此处的1、2、n应当理解为标记这个全排列的第1、2、n位。这样记法比较简洁。当然了,我们把每个字符都按某个顺序标记之后,同一字符串中其他部分就得遵照这个现成的标记顺序,以免出现混乱。

    ·一串字符通常用一个大写拉丁字母代替。

    ·出于形式清晰起见,定义$n^{-}=n-1,n^{+}=n+1$.

    ·在字符串中,从一个全排列A出发,向右移动取景框k步后出现下一个全排列B,就说这是一个k步构造。k步构造中间不会有其他全排列出现。

    ·如果一个构造,步数$k\geq2$,就说这是一个长构造;1步构造也叫短构造。

    ·如果两个同长全排列A到B存在一个k步构造,是A到B的最短字符串,就说A直达B,直达距离k;如果A到B的最短字符串不会是A直接到B的构造,就说A不直达B。
    例如,123→321的最短字符串是12321,同时也是123→321的2步构造,因此123直达321,直达距离是2;123→312的最短字符串是12312,但是这是123→231→312的两次1步构造,而123→312的最短构造是123312,长度更长,因此123不直达312(反过来,312→123的最短字符串是1步构造3123,312倒是直达123。)

    ·超过$n$步的构造给出的序列,中间会有多余的字符,前后两个邻近全排列都取不到;或者字符串开头和结尾有一些不参与任何全排列的字符。直接把这些扔掉也不影响包含的全排列种类,我们称这种超排列为冗余超排列。

    一、迟来的早期结果

      这个问题涉及到的概念都很基础,也不难想到,看起来像是那种历史悠久,甚至能追溯到Euler时代的古典组合问题。但实际情况出人意料,这个问题在学术界研究的起步时间非常之晚,直到1993年,D. A. Ashlock与J. Tillotson 才给出了最早实际进展[AT1993]:
    $$n!+(n-1)!+n-2\leq\ell_n\leq\sum_{k=1}^nk!\qquad\qquad$$
    而证明这个“早期结果”需要的数学储备和技巧,其实也没有超过Euler时代——我们现在就来看一看。
    §1.1 $\ell_n$下界估计

      在最理想情况下,开头$n$个字符是第一个全排列,从此出发全是1步构造,取景框每移动一步就得到一个新的全排列。如此只需要添加$n!-1$个字符来得到剩下的那些全排列。这样我们就得到了一个简单的下界:
    $$\ell_n\geq n!+n-1$$
    不过这个下界太理想化了。对一个全排列$12\dots n$来说,1步构造只有一个,就是把开头的1搬加到末尾上,得到的$2\dots n1$,添其他字符都会出现重复,不构成全排列。这相当于把整个全排列视作头尾相接,整体左移一位,字符邻接顺序不变。重复这个过程,在第$n$次会回到原来的字符串。这样一共只得到$n$个不同字符串,可将之统称为一个轮换组。从一个全排列出发,1步构造最多只能遍历其所在的轮换组,无法跳出去,而$n!$个全排列有$n!/n=(n-1)!$个不同的轮换组。这就意味着至少要有$(n-1)!-1$个长构造来跳到所有轮换组上去,这意味着与一开始“乐观估计”相比,实际构造至少要再多出$(n-1)!-1$步来,因此我们有$$\ell_n\geq n!+(n-1)!+n-2$$
    此即欲证明的下界。n=3时,上式给出$\ell_3\geq 9$,由此知长为9的123121321就是最短3字符超排列。

    补充说明
    ①想鉴别两个等长全排列A、B是否属于同一个轮换组,比较A轮换组和B轮换组中同一字符开头的那一个是否相同即可。

    ②其实2步构造也只有一种,就是$12\dots n\Rightarrow12\dots n21$,将排列的开头两个字符颠倒后写在后面得到$3\dots n21$。另一种添加1、2的方式是$12\dots n 12$,但这实际上是两个相继的1步构造。因为$3\dots n21$中1、2的顺序与$12\dots n$相反,所以两者不属于同一轮换组,也就是说,2步构造必然会跳到另一个轮换组中。

    §1.2 递归构造给出的$\ell_n$上界

      同一轮换组可以逐次用1步构造给出:从一个全排列$12\dots n^{-}n$开始,进行$n^{-}$次1步构造给出整个轮换组,得到$12\dots n^{-}n12\dots n^{-}$,总长$2n-1$。我们称之为一个轮换组串。因为总共$(n-1)!$个不同的轮换组,每个轮换组用这样一个压缩紧凑的轮换组串构造,得到的超排列长度至多为$$(2n-1)\times(n-1)!=n!+(n-1)\times(n-1)!$$如果能再设法让轮换组串间共用一些字符,那么这个长度就可以压得更低了。
      注意到$12\dots n^{-}n12\dots n^{-}$结构是两个$12\dots n^{-}$中间夹着一个$n$,我们可得到一个$n^-$字符全排列扩充为$n$字符轮换组串的方式:对每个$n^-$长全排列,在后面添加$n$并重复这个$n^-$全排列即可。我们称之为夹心扩充。
      夹心扩充有一个好处,不同的$n^-$字符全排列A、B扩充后对应不同的轮换组。这是因为两个轮换组中n开头的全排列是nA和nB,A、B不同时自然不同。这就意味着全部$(n-1)!$个不同的$n^-$全排列恰好扩充为全部$(n-1)!$个不同的$n$字符轮换组,也就是全部$n!$个不同的$n$全排列。这给了我们一种利用$n^-$字符超排列结构来优化$n$字符超排列结构的方式。
      下面就展示如何用这种思路从一个$n^-$字符超排列构造出一个$n$字符超排列。首先预处理一下,把可能的冗余字符给扔掉,然后我们分三步构造(为了便于理解,我用3字符超排列123121321作为示范):

    第一步:把超排列中的全排列从前到后逐个按顺序写全,每个分为一段,共$(n-1)!$段。
      示范:123121321→123|231|312|213|132|321
      长度变化:可能会因为重复取字符多出$X$个。

    第二步:对每一段,都夹心扩充为$n$轮换组串,就得到一个$n$字符超排列。
      示范:123|231|312|213|132|321
         →1234123|2314231|3124312|2134213|1324132|3214321
      长度变化:每一段增加$n$,共有$(n-1)!$段,因此总共增加$n!$个。

    第三步:两个相邻$n$所夹的部分正是$n^-$字符超排列中两个相邻排列,按照原始超排列的重复利用方式压缩回去,就得到最终结果。
      示范:1234123|2314231|3124312|2134213|1324132|3214321
         →123412314231243121342132413214321
      长度变化:这一步正好删掉第一步多出来的$X$个字符。

    总计增加了$n!$个字符。整个流程下文以发现者姓氏首字母缩写简称AT流程。
    我们从单字符最短超排列1开始不断重复这个过程,就得到
    1→121→123121321→123412314231243121342132413214321→…
    如此得到的$n$字符超排列下文简记作$AT_n$,其长度$|AT_n|=\sum_{k=1}^nk!$。这就给出了本节开头的上界。

      现在上下界的证明过程都已经给出,相信大家可以看出这个证明其实并不困难。遇到问题后第一时间进行的简单分析就足给出这个下界;上界的需要的构造更有技巧性一些,但也不算神乎其技。整个证明的想法都比较自然(这也是为什么我选择了一种“探究思路”式证明叙述方式),Euler没做到这一步的关键原因只能是根本没人问过他这个问题,而之后两百多年内也没人去动一动,这一点很奇怪,因为这并不是一个难以想到的问题。如果哪一天,有人从Euler某个未被注意的手稿里或者某本一百多年前的趣味数学杂志里翻出这个结果,那我倒是一点也不会奇怪了。

    补充说明
    ①如果AT流程起始用的超排列每个全排列只出现一次,那么他们对应的轮换组串都不一样,进而结果中的超排列每个全排列只出现一次。$AT_1$就是单字符当然满足这个需求,所以$AT_n$中每个全排列均只出现一次。

    ②每个$AT_n$都是回文序列。这只要看一下AT流程就能看出:只要起始字符串回文,那么每一步构造出来的就依然是前后镜像对称的回文序列。而1显然是回文序列……

    ③字符串中的一个$k$步构造经过AT流程后,会对应拉伸为一个(k+1)步构造。详细说明如下:
    起始的$n^-$字符超排列每个全排列在AT流程之后变成了一个轮换组串,如果两个起始邻接全排列$A$、$B$之间是一个k步构造,那么取景框从A对应的轮换组串$AnA$最后一个全排列$nA$出发,k步之后刚好取到$BnB$中的第一个$B$,但是取不到$n$。再进一步才能取到下一个全排列$Bn$。
    因此,若起始串的两个邻接全排列之间是一个k步构造,那么结果串中,他们对应的两个轮换组串之间就是一个(k+1)步构造。(当然了,轮换组串内部取全排列都是一步构造。)
    这样,如果起始串无冗余(最长构造不超过n-1步),那么结果串也无冗余(最长构造不会超过n步)。

    ④$AT_1$不包含构造,$AT_2$仅包含1步构造……由本节补充说明③可递推得知,$AT_n$中最长构造是(n-1)步。
    由③还可得知,$AT_n$某种意义上可以视作若干轮换组串“拼起来”:每个初始全排列在AT流程后扩充为一个轮换组串,串内均是短构造,而两个临近轮换组串之间必然是一个长构造。因此可以说$AT_n$是轮换组串通过长构造拼在一起所得。


    ⑨可能有读者受到1.1节证明、本节补充说明④和上下界形式相近的启发,觉得可以把1.1节的证明继续推进一下:既然考虑至少需要2步构造的情形可以把上界从$n!+n-1$推进到$n!+(n-1)!+n-2$,那是不是继续考虑需要至少3步、4步、……(n-1)步构造的情形,就能一口气把下界推进到和上界一致的$\sum_{k=1}^nk!$呢?正巧$AT_n$最大就需要一个(n-1)步构造。——嗯……想法总是很美妙,但现实往往不如意。1步构造一定留存在一个轮换组中,组间跳跃至少需要2步,因此我们可以用轮换组这个结构分类,给出下限。可是,并不存在一种“至少需要3步构造进行组间跳跃”的结构,只用1步、2步构造,从任意一个全排列出发,我们可以得到所有全排列!(2步构造可以颠倒两个邻接字符顺序,与若干1步构造配合就可以交换任意两个相邻字符,进而可以任意调整字符位置,得到所有全排列。)
      由于这种原因,1.1中的下界证明无法简单“推广”,即使这个方法能够改进,也得找一些更精细和恰当的结构才行。而这样的结构……看起来并不好找,因为自1993年论文发布起,十余年内没有任何推进。而给出上界的AT构造也似乎很难改进,很多人猜想这就是最优解了,但也同样给不出证明或者否证。
      事情当然不会就这么算了,不然本文标题的“近况”就无从说起了。只不过按时间顺序来讲,下一个突破出现在一个有点奇怪的地方……

  2. FatFish

    2楼 11月6日 物理版主, 优秀回答者
    3周前FatFish 重新编辑

    第二节 走进新时代

      四葉(4chan )论坛是一个创建于2003年的网络论坛,最初定位于进行日本动漫文化相关交流,其后逐渐变得综合化。其设计上仿照了日本的双葉(2chan )论坛,有两个显著特点。其一是不需注册,发贴人完全匿名,可随意起昵称或者直接以匿名用户的身份发言;其二是论坛讨论串保留时间很短,一串讨论满十页之后就会被删除,如果没有事先保留备份的话,这个讨论串就永远消失了。因为这些特点,四葉上常常会出现大量话题敏感或者有碍社会观瞻的讨论内容;也因为这些特点,这看起来不像是一个找数学成果突破该来的地方。不过,没人规定过数学爱好者不能逛四葉,何况这个论坛还有个科学版块(/sci/ ),不是么?
      虽然四葉不提供注册功能,但是提供了一种“个人码”(tripcode )功能来区别身份。你可以在自己的昵称后面输入井号"#"并接着一段“口令”,这段口令会被散列转化为一串“乱码”,出现在昵称+空格+半角叹号后面,作为区分标志。如果想要更高的保密性可以用双井号"##"替代单井号,结果会用两个半角叹号分割。因此有些场合我们能够认出同一个人。
      在2011年9月13日,科学版上一位昵称“ニア愛 !pQsULI4sXc”的同志提了一个问题:如果想把14集《凉宫春日的忧郁》以每种排序都看一遍,那至少要看多少集?(原贴备份可见 http://4watch.org/superstring/ )这个提法可能有一些含混,不过发贴人在稍后的讨论中明确了允许各排列重叠一部分的要求,抽象出来的数学问题正是最小超排列问题。提问者本人似乎最初不熟悉这个问题的相关研究,而独立提出了这个问题。(这可以视为这个问题“不难想到”的一个佐证。)
      这个讨论串有一定热度,而原串被删后,发起人还在2011年9月14日开启了第二个讨论串(备份可见 https://warosu.org/sci/thread/3734198 ),2011年9月17日开启了第三个讨论串(备份可见 https://warosu.org/sci/thread/3751105 ),继续进行讨论,并提供了一些学术领域相关研究的资料。
      就在第三个讨论串发起才一个半小时左右,一位昵称都没有的匿名用户在回复中证明了一个新下界:$$n!+(n-1)!+(n-2)!+n-3\leq\ell_n$$发起人认为这个证明可行,并希望能保存的更长远一点。他将之上传到了Google文档 ,而后另一位讨论参与者"RenaldoMoon !!StSAw7qAp8x"在一个网络百科网站( http://mathsci.wikia.com )上创建了条目,该网站主要就用于保存四葉科学版上的一部分内容。尽管讨论串中提及了一些数学界的资料,这个条目的名字并未沿用数学界名词称之为最小超排列问题, 而是叫做“春日问题”(The Haruhi Problem )。
      虽然几位参与者认识到这个成果值得保留,但是他们似乎也就止于保留,之后没有去进一步传播以让学术界熟悉这个成果,而几位研究最小超排列问题的学者几年后如何注意到这个结果,也就成了一个很有趣的故事——不过这个故事就先按下不表,讲古的部分够长了,这几位学者也还没来得及出场呢。现在,还是把注意力回到数学上。


      本节下文给出的内容核心技巧就来自这个四葉证明,但是陈述上做了一定调整,以尽量避免引入新概念与技巧时过于突兀。此外,读者可能注意到,因为这个下界出现了$(n-2)!$,所以只有$n\geq2$,式子才有意义。事实上,这个证明的论述过程确实要求$n\geq2$(不然讨论的一些结构根本不存在),因此本节下文将始终默认$n\geq2$。

    §2.1 旧下界,新证明
      为了便于大家理清这个新结果的叙述思路,首先来预热一下,换一个角度给出1.1小节中的两个下界。
      这个思路是分析超排列逐渐“生长”的过程。从一个超排列出发,从开头到第一个全排列结束的部分记为$W_1$,以此类推,恰好取到第s个全排列结束的部分字符串记为$W_s$。最终整个超排列记为$W_t$,由于每种全排列至少出现一次,有$t\geq n!$

    $\mathcal{L}_s$为字符串$W_s$的长度;
    $\mathcal{P}_s$为字符串$W_s$出现的全排列种类数;
    $\mathcal{C}_s$为字符串$W_s$出现的轮换组种类数。
    那么首先有$\mathcal{L}_1=\mathcal{P}_1+n-1$
    从此出发,每构造一次,上式角标加1,而$\mathcal{L}_s$至少增加1(k步构造增加k),$\mathcal{P}_s$至多增加1,这样始终有
    $$\mathcal{L}_s\geq\mathcal{P}_s+n-1$$对于超排列$W_t$,应有$\mathcal{P}_t=n!$于是$$\mathcal{L}_t\geq\mathcal{P}_t+n-1=n!+n-1$$这正是1.1小节的第一个下界。
    我们进入把$\mathcal{C}_s$也纳入考量,这时候起始式变成$\mathcal{L}_1=\mathcal{P}_1+\mathcal{C}_1+n-2$
    接下来我们从此出发归纳证明
    $$\mathcal{L}_s\geq\mathcal{P}_s+\mathcal{C}_s+n-2$$
    角标增加1(即1次构造)后,$\mathcal{P}_s$与$\mathcal{C}_s$分别至多增加1,因此右边最多增加2,若某阶段该不等式成立,再进行一次构造使得角标加1:
    若这是$k\geq2$的k步构造,$\mathcal{L}_s$至少增加二,因此不等式依然成立;
    若这是1步构造时,$\mathcal{L}_s$增加1,1步构造不会进入新的轮换组,因此$\mathcal{C}_s$不变,从而不等式依然成立。
    如此该不等式得证。对$W_t$来说$\mathcal{C}_t=(n-1)!$,
    $$\mathcal{L}_t\geq n!+(n-1)!+n-2$$
    这就是1.1小节的第二个下界。

    从这种证明方式看,只要不等式右侧再加上另一个计数项,并保证右侧的增长速度依然不会超过左侧,就可以得到一个新的下界了。那么,这个待定计数项要计数怎样一种分类结构才满足需求呢?

    §2.2 单环与二级环
      1.2小节补充说明④说到,$AT_n$可以看作由轮换组串通过长构造拼接而成,敏锐的爱胡思乱想的读者可能注意到这看起来和1.1小节的证明技巧有点关系:证明1.1小节下界的一个关键因素是轮换组之间必须通过长构造跨越。
      这种关联当然不宜发散过深:1.1和2.1小节的证明都适用于任意超排列串,同一轮换组可不一定聚堆出现。不过这可以启发一下我们试试看能不能从$AT_n$上进一步榨点什么油水出来。——既然一个全排列在经过AT流程后变成一个轮换组串,那么轮换组串再经过AT流程后得到的“二阶串”,是不是适合充当一个合适的分类结构呢?我们现在就看看这样得到的“二阶串”是什么结构。


      从一个$n-1$种字符的轮换组串出发,他由$n-1$个全排列通过$(n-2)$个1步构造拼接起来,在经过AT流程后,每个全排列变成一个$n$种字符轮换组串,而每个1步构造都拉伸为2步构造。因此$n$种字符“二阶串”由$n-1$个轮换组串构成,之间由$(n-2)$个2步构造联通。其中轮换组串有$n$个全排列,因此一个$n$种字符“二阶串”共包含$n(n-1)$个全排列。(我们进行AT流程的起点是一个轮换组串,不含任何重复全排列,因此得到的二阶串所包含的这$n(n-1)$个全排列也全都不相同)

      接下来我们分析一下,由2步构造连接的两个轮换组串有什么关联。把第一个轮换组串开头初始全排列记作$123\dots n^-n$,那么第一个轮换组串结尾一个全排列就是$n12\dots n^-$,通过2步构造到达全排列$2\dots n^-1n$,这也是第二个轮换组串的初始全排列。对比两个初始全排列,我们发现,固定第一个初始全排列最后一位$n$不变,,前$(n-1)$位$123\dots n^-$作为一个首尾相接的循环单元向左轮换一位成为$2\dots n^-1$,就得到了第二个初始全排列。
      我们说$123\dots n^-n$在前$(n-1)$位局部向左轮换一位得到了$2\dots n^-1$。
      这样,若两个轮换组串由2步构造连接,则第二个轮换组串起始全排列可由第一个轮换组串起始全排列前$(n-1)$位局部向左轮换一位得到。对于一个完整的二阶串应用这个结论,整个二阶串的各轮换组串起始全排列就由第一个初始全排列的前$(n-1)$位逐渐“局部轮换”得到。这$n-1$个轮换组串的起始全排列的前$(n-1)$位也就遍历了一个$(n-1)$种字符的轮换组。
      下文中,将把最后一位相同,且前$(n-1)$位同属一个$(n-1)$种字符轮换组的$(n-1)$个$n$种字符全排列称为一个“前$(n-1)$位局部轮换组”。


      自然,非$AT_n$超排列不会老老实实按部就班走完一个“二阶串”,那么似乎应该仿照轮换组串和轮换组的关系,把“二阶串”打散,将其包含的$n(n-1)$个全排列作为一个“二阶组”,作为计数对象。但这里有个新的困难:不同“二阶组”之间会部分重叠,而不像轮换组那样界限分明。
      以4种字符的情形举例来说:考虑以1234开头的“二阶串”对应的“二阶组”甲,做“局部轮换”可知他将包括1234、2314、3124所在的三个轮换组;再考虑2341开头“二阶串”对应“二阶组”乙,他将包括2341、3421、4231所在的三个轮换组。比对一下,甲1234和乙2341属于同一轮换组、甲2314和乙4231属于同一轮换组,但是剩下的甲3124和乙3421不在同一轮换组!也就是说甲乙两个“二阶组”不相同,但是有两个共同轮换组,共计8个共同全排列。
      这在计数时显然会有麻烦。我们遇到一个分属多组的全排列时,如果都算上,那这个计数项一次能增长好几个数,这增长太快了,不太符合预期;如果只算一次,那么怎么确定该算哪一个?
      从上文的4种字符案例中我们可以看出一些这种麻烦的来源:同一轮换组选择不同起点开始构造二阶串,那么遇到2步构造的全排列就不一致,进而打乱了后继的全排列。所以最好引入一些重视起始点的概念和计数方式,更精细的处理这个问题。
      首先我们给轮换组标上顺序:先选定一个全排列作为起始点,紧跟其后的后继元素就是通过1步构造所得的那个,继续按照1步构造排序下去,经过所有全排列后回到起始点,形成一个循环。
    $$123\rightarrow231\rightarrow312\rightarrow123\rightarrow\dots$$就是一个以123为起点的单环;而
    $$231\rightarrow312\rightarrow123\rightarrow231\rightarrow\dots$$是以231为起点的另一个单环。
      由于给定起始点的全排列就可以得到整个单环,显然单环与全排列存在一一对应(因此$n$种字符的单环共计$n!$个),而轮换组串按照全排列出现先后的顺序也自然与单环一一对应。
      我们把一个超排列视为若干单环或其开头一部分通过长构造连接起来的拼接物。凡是通过长构造抵达的全排列(以及开头那个)都视为单环的起始点,而凡是通过短构造抵达的全排列都是单环的后继全排列。因此,想要确定超排列中一个特定的全排列经过哪个单环,就要从这个全排列出发,倒着往前追寻到出现一个长构造为止,以确定单环起点。
      由于每个单环只有$n$个不同全排列,而超排列包含所有$n!$个全排列,一次一个超排列至少要遇到$(n-1)!$个单环。但是对一般超排列而言,属于一个轮换组的全排列可能分属于几个不同的单环,因此经过的单环数量可能比$(n-1)!$更多。
      注意,一个全排列可以出现在同轮换组的$n$个单环中,但是对于一个特定超排列中的一个特定位置的全排列,他“经过”哪个单环依赖于他前面部分超排列的结构,这个时候可以确定这个全排列只属于某一个特定单环。

      然后参照“二阶组”的特征,定义“二级环”如下:将起始全排列属于同一“前$(n-1)$位局部轮换组”的$n-1$个单环作为元素放进同一个集合中,这个集合就叫二级环。
      由于不同起点的单环是不同元素,所以不同二级环之间不会有共同元素。
      超排列中一个全排列经过哪个单环,就说他经过了这个单环所属的二级环。因此经过哪个二级环也是一个“路径依赖”的事情,而且一个特定超排列特定位置的全排列只会经过一个特定二级环。
      一个二阶环有$n-1$个单环、$n-1$个轮换组,共出现$n(n-1)$个不同全排列,因此一个超排列至少要经过$(n-2)!$个二阶环,当然了,可能更多。


      读者可能注意到,二级环实际上是个比较“松散”的结构,我们没有给二级环指定一个“起始单环”和单环间的排序,因此也不能和“二阶串”进行一一对应。为什么要这样呢?粗略来说,这是因为现在这个样子已经符合预期效果了:超排列中出现一个全排列就能确定他到底属于哪个二级环。要是再分的更精细一些,反而过犹不及,不好控制计数项增长速度——下一小节会详细说明这一点的细节。

    §2.3 最后的调整
      定义$\mathcal{D}_s$为字符串$W_s$遇到的二级环种类数。
      上一小节说明过$\mathcal{D}_t\geq(n-2)!$,很多读者可能觉得我们简单证明一下$$\mathcal{L}_s\geq\mathcal{P}_s+\mathcal{C}_s+\mathcal{D}_s+n-3$$就万事大吉了。——很遗憾。这个式子是错的。
      $s=1$时上式取等号,没有问题。开始归纳,假设角标增加1时多了一个k步构造。
      $k\geq3$时,因为右边三项每项最多加1,没有问题。
      $k=1$时,一步构造后$\mathcal{P}_s$最多加一,而一步构造后仍在同一个轮换组和同一个单环中,因此$\mathcal{C}_s$和$\mathcal{D}_s$都不变,没有问题。
      问题出在$k=2$时,这时右边三个计数项可以同时加1: 例如,开头部分是123421,那么构造1234→3421是一个2步构造,出现了新的全排列;到达了新的轮换组;而123和342显然不在同一个轮换组,因此也是一个新的二级环。于是不等式左边增长的比右边还慢,遭到了破坏。


    看来我们还要再设法做一些调整才行,别忘了$\mathcal{D}_s$的一大特点是和$W_s$的整体结构都有关,就从此处入手,进行这个最后的调整:
    定义$\mathcal{C}'_s$为$W_{s-1}$所遍历的轮换组种类数。(一个轮换组中的所有全排列都在这个字符串中出现至少一次的情况下,就说这个字符串遍历该轮换组。)
    我们用这个替代$W_{s}$遇到的轮换组种类数$\mathcal{C}_s$。
    显然$\mathcal{C}'_s\leq \mathcal{C}_s$,不过我们这个修改的主要目的不是让计数项“延迟”大一些了事,而是借助这个包含更多$W_s$“经过路线”信息的项对$\mathcal{D}_s$的增长做出限制。
    $W_0$就是一个排列都没有,因此$\mathcal{C}'_1=0$。同样,角标s增加1,$\mathcal{C}'_s$最多增加1。


    接下来我们要证明不等式
    $$\mathcal{L}_s\geq\mathcal{P}_s+\mathcal{C}'_s+\mathcal{D}_s+n-2$$
      $s=1$时上式取等号。归纳时,设$W_{s+1}$比$W_{s}$多了一个$k$步构造。
      $k\geq3$和$k=1$时,和前面讨论一样,不再详述了。
      下面重点看$k=2$的情形,我下面将说明,这种情形中,如果$\mathcal{C}'_{s+1}=\mathcal{C}'_s+1$,那么必然有$\mathcal{D}_{s+1}=\mathcal{D}_s$,因此,三个计数项不会同时加1,不等式右侧增长速度不会超过左侧。

    证明如下:
      对$k=2$,$\mathcal{C}'_{s+1}=\mathcal{C}'_s+1$情形,记$W_{s}$的最后一个排列$P_s=123\dots n$,那么$W_{s+1}$多出的排列$P_{s+1}=3\dots n21$。由于这是一个二步构造,因此$P_{s+1}$是单环的起点。
      又,$\mathcal{C}'_{s+1}=\mathcal{C}'_s+1$说明$W_s$比$W_{s-1}$多遍历了一个轮换组,那只能是新遍历了$P_s=123\dots n$所在的那个轮换组,且$P_s$是该轮换组中最后一个出现的,只在$W_s$末尾出现了一次。
      所以,与$P_s$同轮换组的$P'=23\dots n1$已经出现在$W_{s-1}$中了。
      如果$P'$不是一个单环起点,那么他与左侧的全排列之间是短构造,但是能从短构造到达$P'$的就只有$P_s$,而这个排列一直到$W_s$末尾才出现!因此$P'$必然是另一个排列通过长构造抵达的。$P'$就是一个单环起点。
      对比两个起点为$P'=23\dots n1$和$P_{s+1}=3\dots n21$的单环,我们发现他们属于同一个二级环,因此没有新经过的二级环。$\mathcal{D}_{s+1}=\mathcal{D}_s$。证明完毕。$\blacksquare$

      这个证明也解答了2.2小节结尾的疑问,如果我们规定了二级环的单环排序、用“初始单环”区分二级环,那么起点为$P'$和$P_{s+1}$的两个单环就不一定属于同一个“有起点二级环”了,反而画蛇添足,无法限制$\mathcal{D}_s$的增长。

      接下来只要对超排列$W_t$应用该不等式就可以,别忘了$\mathcal{C}'_t$计算的是$W_{t-1}$遍历的轮换组,因此$\mathcal{C}'_t=(n-1)!-1$。于是
    $$\mathcal{L}_t\geq\mathcal{P}_t+\mathcal{C}'_t+\mathcal{D}_t+n-2\geq n!+(n-1)!+(n-2)!+n-3$$从而$$\ell_n\geq n!+(n-1)!+(n-2)!+n-3$$
    大功告成。
    $n=4$时上式成为$\ell_4\geq 33$,而$|AT_4|=33$,因此$\ell_4=33$,$AT_4$就是一个4字符最小超排列。


    这个证明是典型的“技巧式组合证明”,理解起来不需要太多数学背景,证明本身也不需要特别强力的数学工具,但如何找到恰当的结构加以恰当的处理,则需要点技巧了。我想,如果Erdős还活着,他会喜欢这个证明的。


      可能又有读者受到证明路线启发,试图进行推广,通过“三阶串”引入“三级环”以加大下界。但是2.3小节引入的修正计数项$\mathcal{C}'_s$提醒我们这个证明并非单纯靠简单的推广概念得到,还需要再做一些针对性调整。而对于“三阶串”情形,目前尚不知如何进行合适的调整,才能控制各计数项的增长之和不超过字符串的增长速度。因此还是那句话,想法总是很美妙,但现实往往不如意。有鉴于此,我们就不在这个尚不成功的推广思路上浪费笔墨了。不过读者如果对“三阶串”和更高阶的类似结构感兴趣,也不必失望,在接下来要介绍的另一个研究中,会仔细分析$AT_n$上这样的结构。——这一次,研究成果倒是没发表在什么奇怪的地方。

  3. 7周前

    FatFish

    3楼 11月28日 物理版主, 优秀回答者
    2周前FatFish 重新编辑

    三、$n$种字符最小超排列唯一吗?

      乍看起来这问题答案显然是否:121和212都是2字符的最短超排列。但是如我们在0.1小节中约定符号时所说,如果我们不关注具体的符号长什么样,那在比较排序的意义上他们都是同一形式的长为3的字符串:开头与结尾都是同一个字符,夹在其中的是另一个。因此可以认为121和212代表同一个超排列。这样,我们在把所有“超排列中一种符号全都换个造型或者几种符号整体调换”得到的超排列视为同一个超排列。那么很容易看出2字符最短超排列就唯一。

      在本节,为了方便表述和比对,我们就直接规定超排列第一个全排列均按正整数升序记为$123\dots n$。这样其余对应位置字符不一致的超排列就是真的排序结构不一致的不同超排列了。

      若$n$种字符最小超排列不惟一,那么可以将两个$n$种字符最小超排列分别进行AT流程,对应位置不一致全排列扩充为对应位置不同的轮换组串,从而得到两个不同的$n+1$种字符最小超排列。以此类推,只要我们确定某个字符种类数的最小超排列不惟一,那么更多种字符的最小超排列均不惟一。

      1、2字符最小超排列就只有$AT_1=1$、$AT_2=121$,如果读者辛苦辛苦,可以手动验证3字符最小超排列也只有$AT_3=123121321$这一个。手工分析长度为$\ell_4=33$的最小超排列有几个未免太辛苦,好在我们这个时代的计算机很发达,可以丢给他们处理。分析结论是$AT_4=123412314231243121342132413214321$就是唯一的4字符最小超排列。看来,在字符种类数$n\leq4$时,最小长度的超排列只有$AT_n$,没什么自由调整的空间。
      在2013年三月,数学家Nathaniel Johnston发表了一篇文章[J2013],详细分析了$AT_n$各全排列的出现顺序,并借此说明$n\geq5$时,我们有足够的“自由度”调整$AT_n$,得到同样长度为$|AT_n|$的其他超排列。遗憾的是,这个结果本身也不能直接说明最小超排列不惟一。因为我们还不能确定$n\geq5$时,$AT_n$是不是一个最小超排列。2.3小节的下界对于$n=5$只给出$\ell_5\geq 152$,而$|AT_5|=153$。$n$更大时这个下界和$|AT_n|$的差距就更大了。
      直到一年之后,新进展才出现。2014年三月,Benjamin Chaffin提出了一个算法,可以让计算机在较短时间内找到$n=5$的所有最小超排列。结果确认了$\ell_5=153$,因此$AT_5$是最小超排列,但是除此之外长度同为153的最小超排列还有7个!而Nathaniel Johnston当初的$AT_n$调整法在$n=5$时只给出了$AT_5$之外的1个超排列。事情一下子就变得有趣了起来:这说明字符种类数变多的时候,不仅$AT_n$出现了可以调整的余地,最小超排列还出现了一些与$AT_n$关系不大的新结构。(不知道为什么,Benjamin Chaffin自己似乎没发表这个结果,本文有关信息都来自Nathaniel Johnston于2014年8月13日在自己博客上发表的一篇博文 。)

      下面介绍数学细节。按顺序来,先看一看Nathaniel Johnston对$AT_n$的分析。

    §3.1 轮换码
      首先,出于叙述简便考量,对一个$n$位全排列定义如下操作:把前$k$位看成首尾相接的循环单元向左轮换一位,而后面$n-k$位固定不变,就说这是一个$\sigma_k$变换。$\sigma_k$变换的逆向操作就是前$k$位向右轮换一位,后面不变,我们记这个逆变换为$\sigma_k^{-1}$。
      由此定义,一个全排列通过1步构造得到的全排列,就是做一次$\sigma_n$变换得到的全排列。我们再回忆一下2.2小节的二阶串、二级环等概念,二级环里诸单环的起点就可由其中一个逐次做$\sigma_{n-1}$变换得到。
      对一个以$12\dots n$开头的二阶串,第2个到第n个全排列是$12\dots n$做1次、2次、……$n-1$次$\sigma_n$变换所得,然后我们跳到第二个轮换组串,起始全排列$2\dots 1n$是$12\dots n$做1次$\sigma_{n-1}$变换所得,接下来的一个全排列就是$12\dots n$先做1次$\sigma_{n-1}$变换再做1次$\sigma_n$变换,再接下来的一个是$12\dots n$先做1次$\sigma_{n-1}$变换再做2次$\sigma_n$变换……这个轮换组串的最后一个全排列是$12\dots n$先做1次$\sigma_{n-1}$变换再做$n-1$次$\sigma_n$变换;接下来第三个轮换组串起始列是$12\dots n$做2次$\sigma_{n-1}$变换所得……
      好了,读者现在也许有种熟悉感——因为这很像是某种“进位制”:n次$\sigma_n$变换“进位”为一个$\sigma_{n-1}$变换,而一个二阶串中的全排列就按照这种“进位制”顺序排列。
      这种“进位”关系能不能进一步扩张到由3步构造连接的二阶串之间呢?一般来说,因为3步构造有两种($12\dots n321$与$12\dots n312$),二阶串间的连接方式不惟一,也就不会有严格整齐的进位关系。但如果把情形限定在$AT_n$上,有望保持这种关系,例如,$AT_4$由两个二阶串组成:
    123412314231243121342132413214321
    标红的2就是第一个二阶串的结尾,第二个二阶串的起点。我们看到两个二阶串的起始分别是1234和2134,第二个确实是第一个经过一次$\sigma_{n-2}$(即$\sigma_2$)变换后所得。
    实际上,可以利用AT流程的特点证明$AT_n$的所有全排列均按照这种“进位制”顺序排列,不过为了写清楚这个证明,我们首先明确一下这种“进位制”的概念和基本性质。


      从全排列$12\dots n$开始,依次经过$i_1$次$\sigma_1$变换、$i_2$次$\sigma_2$变换、……$i_k$次$\sigma_k$变换、……$i_n$次$\sigma_n$变换得到一个全排列,我们就给这个全排列指定一个“轮换码”,记为$[i_1i_2\dots i_k\dots i_n]$。只要给定轮换码,我们就可以确定其代表哪一个全排列。
    例如,要确定轮换码[01013]是代表哪一个全排列,流程如下:
    ·首先,轮换码是五位,也就说明全排列字符数$n=5$,因此从全排列12345开始变换;
    ·先经过1次$\sigma_2$变换得到21345;
    ·再经过1次$\sigma_4$变换得到13425;
    ·最后经过3次$\sigma_5$变换得到25134。即[01013]是一个25134的轮换码。

    另一方面,给定任意一个全排列,我们也有办法倒推出一个轮换码。
    从$12\dots n$开始进行变换时,只有从$\sigma_k$到$\sigma_n$的变换才会调整编号为$k$的字符的位置。这样我们可以从$n$的位置开始倒推:只有$\sigma_n$才能移动$n$的位置,那么我们只要看一下要把$n$恢复到最后一位需要几个$\sigma_n^{-1}$变换,就能确定轮换码的最后一位,然后在经过相应次数$\sigma_n^{-1}$变换后的全排列上恢复$n-1$的位置,以此类推……
    例如,给定全排列31254:
    ·我们需要一次$\sigma_5^{-1}$来恢复5的位置,轮换码第五位取1;
    ·一次$\sigma_5^{-1}$后全排列为43125,需要3次$\sigma_4^{-1}$来恢复4的位置,轮换码第四位取3;
    ·3次$\sigma_4^{-1}$后全排列为31245,需要2次$\sigma_2^{-1}$恢复3,轮换码第3位取2;
    ·2次$\sigma_2^{-1}$后全排列为12345,已经回到初始状态。前两位都取0.
    这样我们就确定了31254的一个轮换码[00231]。
      这个过程中,恢复$k$的位置至多需要$k-1$次$\sigma_k^{-1}$操作,因此得到的轮换码第$k$位取值从0到$k-1$。但是由于连续进行k次$\sigma_k^{-1}$变换(或者$\sigma_k$变换)就相当于绕一圈绕回来了,和不做任何变换等效。因此轮换码第$k$位随意加上$k$的倍数,得到的新轮换码还是对应同一个全排列。我们希望去掉这种没什么意义的冗余,因此可以将轮换码第$k$位取值范围限定为从0到$k-1$,这不会损失任何实际的变换。
      下文中默认提到的轮换码都是这种限定了取值范围的“标准轮换码”。
      现在,轮换码的第一位必然是0。第$k$位有$k$种选择,因此$n$位轮换码的总种类数是$$1\times2\times\dots \times k \times \dots n=n!$$而这恰好也是$n$字符全排列的种类数。
      前面已经看到,每个特定全排列都能给出至少一个对应的特定轮换码。而既然同样长度的全排列和轮换码种类数一致,且一个特定的轮换码只给出一个特定全排列,那么只能一个萝卜一个坑,每个全排列都有唯一指定轮换码。双方一一对应。
      此外,对一个轮换组而言,其包含的$n$个全排列互相只差一些$\sigma_n$变换,所以轮换码只有最后一位不同,取值从0到$n-1$。因此给定轮换码前$n-1$位也就可以确定一个轮换组。轮换组中任取全排列也确定轮换码前$n-1$位,双方一一对应。


      接下来,我们用归纳法证明,$AT_n$中全排列的轮换码按从左到右顺序满足如下规则:起始轮换码是$[00\dots0]$,每向右一个全排列就在末尾一位加1,如果第$k$位累计到$k$,就将第$k$位变为0,并将第$k-1$位加1.(也就是“第k位逢k进1”)
      对于$AT_1=1$、$AT_2=121$,这个很容易验证,因此归纳起点没有问题。
      接下来假设$AT_{n-1}$满足题设,记其中两个相邻全排列A、B的轮换码是$[\alpha]$、$[\beta]$,则$[\alpha]$按照“第k位逢k进1”的原则在末尾(第$n-1$位)加1后得到$[\beta]$。那么$AT_{n}$中,A对应轮换组为AnA,第一个全排列An,由于n在末尾,因此未经过任何$\sigma_n$变换,而前面$n-1$位就是A,按照A的局部轮换规则即可得到,于是An的轮换码是$[\alpha 0]$,接下来同一轮换组串其他全排列可的逐个进行$\sigma_n$变换得到,即轮换码末尾逐渐加1.经过$n-1$次$\sigma_n$变换得到nA,轮换码为$[\alpha n^-]$,nA的下一个全排列是Bn,轮换码为$[\beta 0]$,而这正是$[\alpha n^-]$再在末位加1后,末尾清零进到第$n-1$位加1的结果。于是$AT_{n}$也符合题设。
      命题得证。


      既然$AT_n$诸排列轮换码确实服从一种类似进位的关系,那么给定一个轮换码,我们就能数出这个排列是$AT_n$中的第几个排列。为此我们需要看一下轮换码的第$k$位的1实际上代表从[0…00]加了多少。(提醒一下,数轮换码位数时候,我们是从左往右数的。)
      第$n$位的1就是1,第$n-1$位的1需要第$n$位累积到$n$,也就是末位加了$n$,第$n-2$位的1需要第$n-1$位累积到$n-1$,就是末位加$n(n-1)$……以此类推,第$k$位的一个1实际上代表了末尾加$n!/k!$。所以轮换码$[i_1i_2\dots i_k\dots i_n]$代表了共计加了$\sum_{k=1}^ni_k\times n!/k!$。起点[0…00]算第一个,那么数排列个数的时候还要再加一:轮换码$[i_1i_2\dots i_k\dots i_n]$代表$AT_n$的第$(1+\sum_{k=1}^ni_k\times n!/k!)$个全排列。


    §3.2 分段重排

      按照轮换码给出的变换过程调整一个全排列,一步步扩大轮换范围过程中,只有从$\sigma_1$(其实就是不动)到$\sigma_{k-1}$为止的变换过程能够调整字符1、2、… k间的相互先后关系,而从$\sigma_{k}$起,包含这些字符1、2、… k的部分将整体轮换,相互关系就不再变动了。因此,如果我们取轮换码前$k-1$位一致的若干n位全排列,将其中字符从$k^+$到$n$全部删除,残存的若干$k$位全排列,字符间的相互先后关系一致——也就是属于同一个k位全排列轮换组。对应轮换码前$k-1$位也和选取的若干n位全排列一致。
      基于这一特点,我们引入如下概念:所有“轮换码前k-1位一致”的n位全排列称为一个k轮换扩充组,字符1、2、… k称为骨架字符,其相互先后关系对应的k位轮换组称为骨架,余下字符称为填充字符。由$AT_n$中全排列轮换码排序规律,整个k轮换扩充组都连在一起。对应的字符串部分就称作一个扩充组串。
      如果在一个扩充组串内部互相调换几个填充字符(例如选择三个填充字符$p,q,r$,把扩充组串中所有$p$换成$q$,$q$换成$r$,$r$换成$p$),那么因为骨架不变,全排列调换后仍是同一扩充组的全排列。换言之,这种调换只是内部调整了扩充组串各全排列出现的顺序而已。那么这种调换就能给出另一个与$AT_n$等长的超排列了!

      当然,这一方案还有两个细节必须说明:

      第一,本节固定了超排列开头必然是$12\dots n$,因此含有开头的扩充组串不能这么调换。所以想执行这一方案要求至少两个不同扩充组串,至少用轮换码前两位(也就是至少三种骨架字符)才能分段。(而要填充字符互相调换,填充字符也得至少两种才行。因此总计五或更多种字符时才有施展这一方案的空间。)

      第二,扩充组串的首尾会与邻接的串外全排列共享几个字符,为了避免调换过程影响外界,最好保证这些共享字符全是骨架字符。的确有办法保证这一点:
      用轮换码前两位(以字符$1,2,3$为骨架字符)将$AT_n$分为轮换码形如[00…]和[01…]的两段,第一段含有开头,不能动;第二段由$[010\dots0]$,也就是$2134\dots n$打头,到超排列结束为止。而$[010\dots0]$左方的邻接排列,即[00…]系列的最后一个,轮换码应为$[010\dots0]$“减1”,也就是$[0023\dots n^-]$(轮换码前两位为0,$k\geq 3$时第k位是k-1)。这个轮换码对应超排列特点是字符$2$一定在末尾(2次$\sigma_3$后第2位的字符$2$移动到第3位,3次$\sigma_4$后第3位的字符$2$移动到第4位……以此类推,(k-1)次$\sigma_k$后第(k-1)位的字符$2$移动到第k位……最终在(n-1)次$\sigma_n$后字符$2$到达末尾第n位),而$[010\dots0]$的字符$2$就在开头。所以这两个超排列间只有一个骨架字符2共用。因此我们可以放心将[01…]段所含有的填充字符4、5 …… n互相调换,给出与$AT_n$等长的超排列。

      对于$AT_5$,我们只有将[01…]段字符4、5互换一种选择,所以$AT_5$之外还给出了1个超排列。

    §3.3 过渡字符
      对一个k步构造来说,取景框从第一个全排列出发要走$k$步才能取到第二个全排列。中间经过存在$k-1$个不作为全排列结尾的字符,我们称之为过渡字符。
    以所含全排列为基准,一个字符串的字符可分为三种不同类型:
    ①作为一个全排列结尾的字符,称为结点字符;
    ②两结点字符之间的字符,也就是过渡字符;
    ③第一个结点字符之前的字符,称为预备字符。
    对一个$n$种字符超排列而言,去掉冗余字符,那么预备字符的数量固定就是$n-1$个,即第一个全排列的前$n-1$个字符;而每个全排列有一个结点字符,因此结点字符是固定$n!$个。那么,超排列长度的仅有的变数就完全在于过渡字符数量。

      Benjamin Chaffin 提出的寻找最短超排列算法,正是围绕过渡字符数量展开。不过这一算法并不直接从完整的超排列开始。而是从0过渡字符情形开始,逐步递归,算出过渡字符数量为$r$时,一串字符所包含全排列种类最大值$N_r$是多少,以及这些包含$N_r$种全排列的字符串是什么(我们用$\mathbb{S}_r$表示这些字符串的集合)。——最终确定使$N_r$取到$n!$的$r$最小值,这也就是超排列过渡字符的最小数量。
      具体来说,在已经找到$\mathbb{S}_0$到$\mathbb{S}_r$的情况下,可以用如下方式加速对$\mathbb{S}_{r+1}$的搜寻:

    ①首先机械式搜出一个包含$(r+1)$个过渡字符的序列,包含$p$种全排列
    ②继续搜索时,凡是在第$(p_1-N_r)$个排列之前就出现一个过渡字符的序列,统统排除。(这是因为剩下的$r$个字符只够添加最多$N_r$种全排列,总计全排列少于$p$种。)同理,排除在第$(p_1-N_{r-1})$个排列之前出现两个过渡字符的序列,排除第$(p_1-N_{r-2})$个排列之前出现3个过渡字符的序列……这样就可以节省很多时间。
    ③如果搜索到一个包含$(r+1)$个过渡字符的序列含有$p'>p$个全排列,就用$p'$大于$p$执行第②步。
    ④反复执行以上流程至结束搜索。
    (我们的起点是$r=0$的情况,即使不用计算机也能看出来,这时候$N_0=n$,$\mathbb{S}_0$由所有轮换组串组成。)


    对于$n=5$,这个程序给出$N_{28}=118,N_{29}=120$.所以想给出全部$5!=120$种全排列,至少需要的字符数为$5-1+5!+29=133=|AT_5|$。
      集合$S_{29}$中符合本节要求(首个排列为$12\dots n$)的超排列共有八个。把他们全列出来我猜也没有读者会耐心一个个琢磨他们的结构,(认为自己有耐心的读者,可以去看Nathaniel Johnston相关博文 给出的完整版 ,以及相关的程序代码 。)所以我只是在这里简单描述一下其特点。
      其中一个当然就是$AT_5$,还有一个当然是3.2小节构造出的$AT_5$变体。这两个超排列在[00234]后有一个4步构造。
      剩下的六个,最显著的特点是,只有1、2、3步构造,而没有4步构造出现。这一特点昭示着最小超排列出现了一些全新的组合方式,$n\geq5$时对于$AT_n$的分析和改造已经不能反映最小超排列的特征全貌了。
      那么$n$更大时,到底还能看到什么新奇结构呢?很遗憾,即使$n=6$时,Chaffin算法运算时间也超出可接受范围了。想要继续开眼界,还得再改进算法才行。接下来,让我们把目光放的稍微长远一点……

  4. 4周前

    FatFish

    4楼 12月25日 物理版主, 优秀回答者
    12小时前FatFish 重新编辑

    四、他山之石,可以降低上界

      2014年8月,Robin Houston发布了一篇论文[H2014],宣布他发现了一个长为872的6字符超排列,比之前的上界$|AT_6|=873$短一位!这是怎么找出来的呢?
      ——答案当然不是用Chaffin算法跑一整年程序。

    §4.1 取景框旅行记

      如果换一种视角,用取景框取到各个全排列的“路径”来描述超排列中全排列的组合方式,就可以把圆问题转化为另一种表述方式:
      我们用一个点来代表一个全排列,如果全排列A直达B,直达距离是k,那么就画一条从A到B的有向线段作为边,并标记其权重为k。这样就得到了一张图$G_n$。取景框从最小超排列开头走到结尾,就可以逐步我们从图$G_n$对应点出发,沿着各条有向边走遍所有顶点的一条路线。
      为便于理解,我们以字符数$n=3$为例实际画出来示意一下:下图左侧就是$G_3$,红色箭头代表权为1的边,蓝色双线箭头代表权为2的边。而右侧则是$AT_3=123121321$对应的行进路线。
    123walk.png
      有一点需要说明,考虑所有超排列时,$G_n$上有些路线缺失。这是$G_n$只包括A直达B且构造步数就是直达距离的情况,还有两种可能未出现:①A直达B,但是构造步数比最短构造长;②A不能直达B,但在实际超排列有A→B构造出现。
      不过我们不是在讨论所有超排列,而是在找最小超排列,这时可以预先优化掉这类路线,因而不必考虑:情形1自不必说,直接换成直达步数构造就能缩短长度。对于情形2,请读者回忆一下关于直达的定义,A不能直达B,说明从A到B的最小字符串中间有过渡的其他全排列,我们把A→B构造换成这个,不仅缩短距离还赚了过渡全排列。
      综上,对最小超排列而言,其取景框路线一定全由图$G_n$的边组成。现在寻找最小超排列的问题就变成了,图$G_n$中沿着有向边遍历所有顶点的权重最小路线是哪一条?给出这条路线,我们就可以按着路线组合所有全排列,且其出现的过渡字符数量最少。(别忘了,每个$k$步构造,也即权重$k$的边,均有$k-1$个过渡字符。)换言之,给出一个最小超排列。

      乍看之下,这好像只是把一个很难的问题转化成了另一个也很难的问题。这么折腾一通到底意义何在呢?
      有个老数学笑话:一个只掌握灭火知识的数学家遇到消防隐患的时候,会选择把火点着——因为这就把他不熟悉的问题转化成了他熟悉的问题。本节情况庶几可用这个笑话解释:转化后的问题也不简单,但是数学家更熟悉。

      组合数学领域中,有一个历史悠久且备受关注的旅行商问题:给定若干城市和他们道路的地图,一个旅行商打算规划一条能访问所有城市恰好各一次后回到原点的路线,如何才能让道路距离最短?

      仔细比较一下,旅行商问题和历史很短且普遍忽视的最小超排列问题还是有些差异:①旅行商问题没有限定线路方向,而超排列问题则限制;②超排列问题不需要最后回到原点;③旅行商问题禁止重复访问城市(除了最后回来),超排列问题不预先做这种限制。

      幸运的是,这些差异不是大问题。有关旅行商问题各种变体的研究也不在少数,有可以直接处理有向图情形的程序,因此第1点不成为问题;直觉上讲,最小超排列应该没有同一全排列出现两次的余裕(需要强调一下,虽然直觉上很合理,且对于5种及以下字符情况都成立,但是这一点尚未有人给出过证明),因此第3点差异接下来暂且在实践上忽视;最后,我们可以把$G_n$中所有点加一条权重为0指向起始点的边,再考虑回到原点情形即可——因为起始点在遍历其他点之后才能回去,所以这种修改不会影响遍历路线。这些差异处理了之后,只要找个程序跑一下最小超排列问题对应的图就能行了。

      不幸的是,旅行商问题也很复杂,没什么快速算法。要处理$G_6$这种有$6!=720$个顶点连线复杂的大图依然很困难。——好嘛,绕了一圈这不绕回来了!

      幸运的是,我们的努力并没有白费,因为我们还可以退而求其次找“相对短路线”。——旅行商问题最优解很难求,而实践上又经常用,为满足需求,有研究人员开发了一些“启发式算法”。这类算法不能保证给出的是最优解,也不能保证运算时间一定很短。但是通常可以在较短时间内给出一个实践上还不错的解。Robin Houston选取的正是这样一种程序。至于程序本身则比较复杂,超出本文的介绍范围了,好奇的读者可以自己去读他的论文。从结果来看,至少这个程序本身足以胜任“把$\ell_6$上界降到$|AT_6|=873$以下”这个任务了。

      程序给出的872字符“最短超排列候选”中,只有1、2、3步构造,没有步长更大的构造。至于全貌就不贴了,还是那句话,太长了,读者也没耐心琢磨不是。

    §4.2 从置换群到超排列

      在上一小节,我们看到了如何把最小超排列问题转化成一个图论问题,并借用现成的程序搜寻了$n=6$的更优结果。在这一节,我们将看到除此之外,来自图论的帮助对一般情况(对所有$n>6$的情况)还能做什么样的改善。
      2018年10月20日,数学爱好者、科幻小说作家Greg Egan 发表了一篇博文 ,介绍了最小超排列问题的一些基本结果,以及他对这个问题上界的改进。这一改进的关键则源自Aaron Williams于2013年发表的一篇论文[W2013]。在这篇论文中,Aaron Williams 说明了,给出一个由(1 2... n)与(1 2)生成的置换群Cayley图,如何找到图上一条遍历路径。
      ——好,看到这,可能有的读者已经开始抗议了:说好的中学水平呢?我又不是上的苏联数理中学,上哪知道“(1 2... n) 与(1 2)生成的置换群Cayley图”是什么东西。
      对不熟悉这些概念含义的读者,我在此做一些不涉太多概念的简单说明。和上小节类似,我们用一个点表示一个全排列。这一次,我们用3.1小节提到的变换$\sigma_n$和$\sigma_2$来连接各点:A经过$\sigma_n$或者$\sigma_2$变换得到B,就连一条从A指向B的有向线段。因为$\sigma_n$和$\sigma_2$多次联合作用可以得到任何全排列(天才的读者应该能想起来在前面哪出现过类似的情况),所以现在图上任意两点间来回都有路联通。这张图就是“(1 2... n) 与(1 2)生成的置换群Cayley图”(其中(1 2... n) 就是$\sigma_n$,(1 2)就是$\sigma_2$),我们记作$S_n$。
      我很想介绍Aaron Williams论文给出的具体方法及论证技巧,然而论文中用到不少相对复杂的图论内容和概念,篇幅和范围都大为超出本文定位,只能略过了。我们直接来简单说明一下Greg Egan是如何应用Williams给出的方法。

      一般来说$S_n$和$G_n$差异不小,为便于应用Williams方法,我们先把$G_n$所有3步及以上构造对应的边删除,只保留1、2步构造对应边,记这个图为$G'_n$。
      现在$G'_n$和$S_n$很像,但仍不相同(读者可以自己试着画个$S_3$与$G_3$对比一下):1步构造正对应$\sigma_n$变换,然而$n>3$时2步构造并不是$\sigma_2$变换。准确来说,一个2步构造相当于1个$\sigma_2$变换接2个$\sigma_n$变换。
      不过这个相似程度已经够了:如果把$G'_n$套到Williams论文中去分析一下,就会发现多出来的2个$\sigma_n$变换没有破坏证明的整体结构,也就是说,我们可以直接对$G'_n$应用Williams方法,仍然可以得到一条遍历路线,也就给出了一个超排列。记这一超排列为$E_n$。
      虽然Williams原论文只是给出路线,没有考虑权重问题,不过从其描述的方法出发,计算这条$G'_n$遍历路线总权重并不困难,进而 Greg Egan 给出了$n\geq4$时$E_n$长度$$|E_n|=n!+(n-1)!+(n-2)!+(n-3)!+n-3$$
      需要注意一点,$n=4,5$时$|E_n|>|AT_n|$,这时候$E_n$根本不是最小超排列;而$|E_6|=|AT_6|=873$,由4.1小节我们知道他们都不是最小超排列。当$n\geq7$时确实$|E_n|<|AT_n|$,这时才给出一个更好上界$$\ell_n\leq n!+(n-1)!+(n-2)!+(n-3)!+n-3$$我们尚不确定$n\geq7$时$E_n$是不是最小超排列,虽然有线索暗示他很可能不是:比如说,$n\leq6$时的$E_n$均不是最小超排列;再比如说,通过$n\leq6$时和最小超排列对比可以发现,因为其构造直接来自$G'_n$而非完整的$G_n$,可能优化长度的3步(及以上)构造都无法出现。


      当然,还有读者会考虑另一重因素,因为Williams方法最初只是找一条遍历路径,没有考虑权重因素进行优化。那么是否,甚至对$G'_n$来说,$E_n$对应的都不是最优线路呢?
      还好,这个疑点可以消除。有办法证明,如果限制到$G'_n$上,也就是说在只允许出现1、2步构造的情况下,当$n\geq 4$时,$E_n$就是最小超排列。
      在往下看证明之前,读者最好先回顾一下第二节中的概念和记号。证明过程中默认$n\geq 4$。

    证明:
      若超排列只允许出现1、2步构造,那么只有2步构造能从一个二级环跳到另一个二级环,如果我们记一个这样的从二级环$\Gamma$到二级环$\Delta$的构造为$123\dots n\Rightarrow 3\dots n21$,那么$3\dots n21$是$\Delta$中一个单环的起始点,与之同属一个$n-1$局部轮换组的$23\dots n1$也属于$\Delta$。又$23\dots n1$与$123\dots n$同属一个轮换组,因此上面的分析表明,两个用二步构造相邻的二阶环,共享至少一个轮换组。
      回忆一下,每个二级环有$(n-1)$个轮换组。记超排列$W_t$中第s个二级环新遇到的轮换组数量为$\mathfrak{c}_s$,那么$\mathfrak{c}_1\leq n-1$。
      $s>1$时,由于现在二级环间只能用二步构造连接,每个二级环都有至少一个轮换组前面已经出现过了,于是$s>1$时$\mathfrak{c}_s\leq n-2$。
      由于$W_t$总共有$(n-1)!$个循环组,我们有$$\sum_{s=1}^{\mathcal{D}_t}\mathfrak{c}_s=(n-1)!$$代入前面$\mathfrak{c}_s$的不等式给出$$(n-1)!\leq n-1+(\mathcal{D}_t-1)(n-2)$$此式移项整理得$$\mathcal{D}_t\geq (n-2)!+(n-3)!-\frac{1}{n-2}$$由于$\mathcal{D}_t$是整数,上式实际上就是$$\mathcal{D}_t\geq (n-2)!+(n-3)!$$
      在第二节,我们证明了不等式$$\mathcal{L}_t\geq\mathcal{P}_t+\mathcal{C}'_t+\mathcal{D}_t+n-2$$并用$\mathcal{D}_t\geq(n-2)!$代入得到一个下界,现在我们限制构造步长之后,要改用$\mathcal{D}_t\geq (n-2)!+(n-3)!$来代入($\mathcal{P}_t=n!,\mathcal{C}'_t=(n-1)!-1$的论证则无影响),由此可得,限制最长2步构造时,超排列长度满足
    $$\mathcal{L}_t\geq n!+(n-1)!+(n-2)!+(n-3)!+n-3$$下界恰好是$E_n$的长度。命题得证。$\blacksquare$


    补充说明
    ①本节的上界改进一直在借助图论中有关遍历路径的研究,因此只考虑“每个点只经过一次”的情形,正如我在文中所说,最小超排列是否满足“每个全排列只出现恰好一次”尚未可知。但Greg Egan在他博文中对超排列的定义和别处不同,确实要求“每个全排列只出现恰好一次”,还把“恰好一次(exactly once)”标粗了。然而,他自己都没遵循自己这个定义:他后面提到,可以简单粗暴的把所有全排列无重叠列一起来得到一个超排列(Clearly we could build a superpermutation just by listing all the individual permutations, one after another with no overlap),但是我们看,一个这样构造的超排列123132213231312321有两个123、两个132。根本不符合他自己的定义!
      所以他很可能只是是受参考的图论研究影响多加了一个限制条件,然后自己也没留神。本文提到的其他人文章也均不采取这种额外要求“恰好一次”的定义。

    ②Aaron Williams论文的内容可以分两部分:第一部分是描述找遍历路线的程序;第二部分是证明这个程序符合要求,给出的确实是遍历路线。以知识水平看,第一部分原则上可以放进本文中,超出本文定位的是第二部分。两部分都略过,一是因为第一部分也比较长,本文篇幅已经够大了;二是因为不做证明只机械式描述一个程序,很难增进读者对此问题的实际认识。
      Greg Egan的博文 介绍了第一部分(当然是修改后适用于$G_n$的),而且也比较通俗,可供感兴趣的读者参考。第二部分就只能翻Aaron Williams的原始论文了。(先看Egan博文相关内容也有助于理解Williams论文缺乏详细解释的对应部分。)

    ③如果有读者觉得走回头还能更短比较奇怪的话,可以设想一张这样的图:所有点都有双向边联通,但是只有一个“中继点”所在的边权重很低,其他边权重都非常高。那么这张图从反复经过中继点才是最好的办法。所以,这种事情是有可能发生的。

    ④本节最后给出了一个证明,说明限制最长2步构造时,$E_n$是最小超排列,这一证明来自Michael Albert, Jay Pantone, Vince Vatter三人。我在下一节会详细介绍相关的出处与历史细节。

  5. 3周前

    FatFish

    5楼 12月31日 物理版主, 优秀回答者
    2周前FatFish 重新编辑

    五、世界线

      现在,我们已经从1993年抵达了2018年10月,自那时候起,到现在两个月来,还没有什么值得介绍的新成果。那么我们就可以停下来,回顾回顾历史了。
      在第二节的开头部分,我介绍了四葉证明的早期历史,从问题提出到这个证明被网络百科收录为止。现在,我们回到这个故事的后半部分。
      从目前的信息来看,第一个注意到这个证明的数学家应当是Nathaniel Johnston,他在自己博客2013年4月10日介绍最小超排列问题的博文 中有所提及,并将超链接指向了“春日问题”的那个条目。他看来大致读过这个证明,因为他注意到了这个证明没法简单推广。(However, the same arguments do not seem to extend to lower bounds like n! + (n-1)! + (n-2)! + (n-3)! + n-4 and so on.)另外,2013年4月22日,他还在著名的在线数列百科OEIS 中,最小超排列长度数列A180632 的条目补充了这个信息。
      2013年4月10日博文还介绍了他一个月前(2013年3月)刚刚发表的论文[J2013]的有关成果。我们在第三节已经介绍了其中一部分。此外,论文还计算了$AT_n$的变体到底有多少种——这个计算很麻烦,而且在第四节介绍的后续研究结果说明,$n\geq6$时$AT_n$已不再是最小超排列,这就使得这个计算“偏离主题”了,于是本文为压缩篇幅省去了该内容。感兴趣的读者可以自己去看论文。
      在论文结尾,作者说,虽然这个问题非常好懂,但是几乎没有人注意,因此希望论文结果能引发一些兴趣。(While computing the length of minimal superpermutations is a fundamental combinatorial problem, and one that can be understood by anyone with even a modest mathematical background, it seems to have received relatively little attention. We hope that our results spark further interest.)
      从稍后的发展来看,作者促进其他人关注的目的达到了。Benjamin Chaffin的算法正是由Nathaniel Johnston在2013年8月13日博文 公布的,可见二人有所交流;而Robin Houston的论文[H2014]不仅引用了[J2013],还引用2013年8月13日这篇博文。在[H2014]发布之后,2014年8月22日,Nathaniel Johnston发表了第三篇有关超排列问题的博文 ,介绍Robin Houston的成果。——截至目前(2019年1月1日)为止,他博客上所有标签为“组合学(Combinatorics)” 的文章,也就只有这三篇。
      尽管如此,这也只是引发了几个数学从业人员的兴趣,没有传播出这个小圈子外——直到2018年10月23日为止。这一天,Robin Houston发了一条Twitter(Tw1 ),提供了了“春日问题”的百科链接 ,并附加了说明文字:“很有趣,最小超排列下界的最好结果,似乎是一个主打动漫的百科的一个匿名用户给出的。”这种强烈的对比反差感很快就吸引了大批人来转发, 使得这个证明相关信息传播开来。
      但是就在同一天稍后,Robin Houston又发了两条Twitter(Tw2 Tw3 )。Tw2的口气透露出他对这个证明不是有特别大的信心(The proof essentially works, I think. ),Tw3则说因为来源不正规,数学家都不想去引用或者借助这个结果,导致整个证明处在一个被忽视的状态。(it's in a strange limbo state.)看起来,他也是刚刚才开始认真看这个证明。
      怎么会这样呢?五年之前Nathaniel Johnston不是已经在博客中提过了么?Robin Houston自己2014年的论文[H2014]不是都引用过Nathaniel Johnston的博客了吗?虽然这不是同一篇,但是[H2014]引用那篇甚至有一个指向四葉证明出现博文的超链接,为什么要到2018年十月,Robin Houston同志才开始去真的审查这个证明呢?又是什么契机促使他去这么做呢?

      ——欢迎收看《走近超排列》特别节目。

      Robin Houston的Tw2附带一个Google网上论坛的超链接,从这个链接我们会找到一个叫“Superpermutators”(直译大概是“超排列者”,指研究超排列的人)的讨论组 ,这个讨论组贴子不多,全看一遍就足够整理出头绪了。
      简单来说,这始于Greg Egan,以及他的新上界。(我们在4.2小节介绍过了。)

      2018年10月19日,Robin Houston在组里发贴介绍 Greg Egan的一个小成果:他找到了只有1、2步构造长154的5种字符超排列,只比最小长度大1。而且宣称6种字符的时候他也找到了只有1、2步构造,长874的超排列。(比[H2014]中的候选最小超排列长一位)因此Robin Houston邀请Greg Egan加入了这个讨论组。
      看来Greg Egan同志得到的可不只是这个“小成果”,他加入进来的同一天就发贴宣称 ,他已经对$n\geq7$的情况找到了更优解。搜寻方法参考Aaron Williams的论文[W2013]。也就是我们在4.2节介绍的方法——看起来也是刚刚发现,因为这时候他还没算出来$|E_n|$的通项公式。同一天晚些时候他就在该贴回复 中给出了结果$$|E_n|=n!+(n-1)!+(n-2)!+(n-3)!+n-3$$并提到了Nathaniel Johnston博文介绍的四葉下界$$n!+(n-1)!+(n-2)!+n-3$$这个2018年10月19日的回贴是讨论组第一次出现四葉下界。推测Robin Houston正是从这里看到的。

      2018年10月20日,Robin Houston发贴 尝试给出自己对这一下界的证明。

      2018年10月21日,Greg Egan回复 指出其存在错误,Robin Houston回复 承认是现在是四葉证明比较强(The wikia proof is starting to look better and better…)

      2018年10月22日,Vince Vatter在讨论组发贴 宣传他与Michael Engen合写的相关综述文章 ,随后Robin Houston回复 指出,文章中说“1993年 Ashlock与Tillotson给出的下界始终没有改进”(It is also remarkable that the lower bound established by Ashlock and Tillotson has never been improved)并不正确,因为有个匿名网友在2011年就给出改进了。——在这个回复中,Robin Houston的态度仍然比较谨慎,只说他相信有办法严格化这个证明。

      2018年10月23日,在回复Vince Vatter的第二天,Robin Houston发了那条广为传播的Tw1 。让这个事情受到了很多外界关注。
      不过,对研究者而言,现在当务之急是确认这个“来路不正”证明的准确性并将其整理成更严格的形式。
      同一天,Jay Pantone在Robin Houston那个失败的证明尝试贴回复 中用pdf文件贴出了他对四葉证明的整理版:
    lower-bound.pdf

      2018年10月26日,Vince Vatter在同一贴中的回复 给出了他与Jay Pantone合作的第二个整理版:
    v2.pdf
    这个整理版也参考了Robin Houston的一些想法,当然还要考虑到核心想法来自一个四葉匿名用户,因此这一版署名一栏是:
    Anonymous 4chan Poster, Robin Houston, Jay Pantone, and Vince Vatter
    没错,打头的那位就是“匿名四葉发贴人”(Anonymous 4chan Poster)。
    到此为止,这个证明的准确性已经确定了。本文第二节的行文思路基本就是在参考这两个文件。

      2018年11月6日,Vince Vatter再次发贴 ,提供了第三版pdf:
    v3.pdf
    根据他的说明,这一版新增了Greg Egan构造在限定只有1、2步构造时最短的证明(即4.2小节的结尾部分),这一证明由他、Jay Pantone、新加入的Michael Albert共同讨论给出。(Today, Michael Albert, Jay Pantone, and I considered the question of whether Egan's construction is best possible if you only allow edges of weight 1 and 2 (Michael, Jay, and I are all at the same conference this week). Our conclusion (in the attached pdf) is that it is.)
      我们看,第三版还利用四葉证明的技巧额外证明了一些内容。
      需要说明一点,这份pdf并不是一份正式的论文,写作格式非常不正规(虽然内容很正规),缺乏文献引用和摘要部分,更是只在讨论组分享了一下,所以说“匿名用户成了论文作者”这种话也不是很准确。


      到此为止,事件顺序基本梳理清楚了,其后也没有什么新的发现值得介绍。——啊,还有一件事值得一说,现在都2019年1月1日了,Vince Vatter自己参与整理完善四葉证明两个月了,他和Michael Engen合写的那篇综述 依然维持原样!没有上传补充了下界部分的第2版!不知道他是已经忘了这茬呢?还是真如Robin Houston所说,不知道怎么引用好。


      哎等等,我们现在知道Robin Houston 10月19日才因为Greg Egan注意到四葉证明了,那么,我们还是要问啊,他,和其他跟Nathaniel Johnston有所交流的数学家,怎么会这时候才注意到?

      因为Robin Houston那条Twitter吸引了很多人注意,甚至有人站出来认领 他就是当年在四葉提问的那位。自然一些新闻科普网站会对此做报导,而科普网站 Quanta Magazine 的报道 采访了几位当事人(当然了没有匿名同志)。我们可以借此看看他们的想法。
      Nathaniel Johnston自呈,他看到这个证明只是因为他在Google上搜索了超排列相关结果。( not because he was an anime fan, but because he had typed an assortment of superpermutation-related search terms into Google.)
      而且他只是粗略看了一下认为证明可行,没有检测细节。因为那时候大家觉得$|AT_n|$就是准确结果,那么提升一点下界的就不没什么意思了。(Johnston read the argument and thought it seemed plausible, but he didn’t invest much effort in checking it carefully. At the time, mathematicians believed that the factorial formula for superpermutations was probably correct, and when you think you know the exact answer to a question, a lower bound isn’t very interesting. )
      更何况,这个证明看起来没法推广,所以也没法让下界一路推上去确定准确值。——当然现在我们知道了,这个下界本来就没法一路推上去。

      而Robin Houston则只是简单评论了一下情况:“我不觉得谁真的留心了这个证明。”(I don’t think anyone really gave it any particular heed.)当然了,这也包括他自己。

      所以,数学家有时候做研究查文献也是很不上心的。

      根据 Quanta Magazine 的采访,科幻小说家Greg Egan注意到这个问题的时间非常晚:数学家 John Baez 在2018年9月26日发了一条Twitter 介绍Robin Houston在[H2014]的发现,才吸引了Greg Egan的注意。——只用不到一个月,这位同志就找到了推进这个问题的方法。看来科幻小说家的数学水平也不错嘛。
      ——嗯……Greg Egan可不是纯“业余数学爱好者”,根据维基百科 搜集的资料,他大学可是学的数学,只不过后来去创作科幻小说了而已。(即使如此,他的小说“数学味”也很重)

    注:
      从我整理的时间线来看,Quanta Magazine 的报道,有两处出了点偏差。
    ① Quanta Magazine 的文章说匿名用户在提问后不到一个小时就给出下界了(In less than an hour, an anonymous person offered an answer)。这个说法有点误导,因为我们第二节开头已经说明,匿名证明回复的已经是第三个串了。考虑到这证明实际上还是要动点脑筋的,他看见过前两个讨论串并从那时候就分析这个问题,看见第三个串直接把想到的思路贴上来,更符合实际。
    ② Quanta Magazine 的文章说,在Greg Egan的结果公开后,Nathaniel Johnston向其他人提醒了四葉下界的证明(When Egan’s result became public, Johnston reminded other mathematicians about the anonymous poster’s proof)。这个说法也不太准确。我们在本节看到,Greg Egan于2018年10月19日公布其改进上界的同时就提到了四葉下界(当然,他转引的Nathaniel Johnston博客)。那么这肯定早于Nathaniel Johnston在看到Greg Egan之后告知其他人四葉证明的时间。Greg Egan才是(2018年10月)第一个提醒大家这个下界的人。——而且你顺着超链接查过去,找到Nathaniel Johnston那篇博文 ,就能找到“春日问题”的百科页面 ,不会错过证明的。

  6. 2周前

    FatFish

    6楼 1月1日 物理版主, 优秀回答者
    2周前FatFish 重新编辑

    结语:非标准互联网数学

      互联网大为提升了人们的交流能力,也相当程度上促进了学术交流。现在用电子邮件交流学术已经是一种“传统”交流手段;而诸如arXiv 这种相对正规的论文预印本网站,也已经是很多数理方向学者必备网站。
      电子邮件节省了邮递时间以及邮递系统的地区限制、arXiv省去了审稿和发表的等待时间以及刊物订阅的限制,除去这两种“优化”传统学术交流的发明外,还有一些在传统时代很少见的特色,比如“网络社区数学”。 这方面的典范是博学者计划(Polymath Project )。这一计划由数学家Timothy Gowers在2009年部分出于社会实验目的发起。他在博客上呼吁群策群力来尝试给出密率Hales-Jewwet定理(density Hales–Jewett theorem)的组合学证明:这个定理对在组合学中意义重大,但是一直只有利用遍历论的复杂证明方法。
      整个实验很成功,在前后不下40名学者的参与之下,目标在几个月内达成。成果以假名D.H.J.Polymath(D.H.J代表density Hales–Jewett)的身份发表在arXiv上(arXiv:0910.3926 ),该组合证明(相对来说)很简洁、第一次给出了结果中有限的界,各方面意义都很重大,还得以在著名刊物《数学年刊》(Annals of Mathematics)上发表。(Polymath, D. H. J. (2012), "A new proof of the density Hales-Jewett theorem", Annals of Mathematics, Second Series, 175 (3): 1283–1327.)
      考虑到问题的难度,40名参与者已经不少了,而且,在前网络时代,很难像想这么多同一方向的数学学者能够几个月持续共同研究一个问题。——即使电子邮件和arXiv也做不到。前者只能定点投放,无法提供公开平台吸引参与者;后者不利于零散的想法交流探讨。整个讨论过程都公开在博客中进行,之后有人整理了[url= http://michaelnielsen.org/polymath1/index.php?title=Polymath1]相关资料和记录[/url],可供参考。

      既然这个实验这么成功,这个计划自然继续了下去,读者可以在下面的地址看到目前进行的所有计划和研究现状:
    http://michaelnielsen.org/polymath1/index.php?title=Main_Page
      虽然这个假名 D. H. J. 部分来自最开始的问题,但是博学者计划后继的文章,大概是出于统一考虑,一直沿用D. H. J. Polymath这个名字。你可以在arXiv上看到所有用这个名字发表的文章


      看起来这种博客聊天式网络数学与最小超排列问题的近况最为接近,但是相比之下,本文中的各位大才表现的就有些奇特了:

      有只把成果放在自己博客上的Greg Egan。
      有只把成果放在别人博客上的Benjamin Chaffin。
      有只把成果放在讨论组里就不去更新arXiv论文的Vince Vatter。
      还有一位在匿名动漫论坛匿名发表成果的匿名人士!

      而且这些成果相当零散,实际上非常不利于查找和引用。(比如说,Michael Engen和Vince Vatter以写综述为目的,都没有注意到这有个被埋没的证明。)而不事先知道的话,谁回去Google网上论坛和动漫基调的百科网站寻找数学内容呢?还好那个词条还能被Google搜到,进而出现在Nathaniel Johnston的博文中。——然后我们看这篇博文显然也没激起其他人的重视。
      还有一些本文前面没提到的内容,比如说6字符其他长度872(目前最优结果)的超排列还找到了哪些 ,他们结构 特征 如何,也都可以在那个Google网上论坛讨论组找到,而别处是没有的。

      这也许可用“问题不是特别重要”解释:比如Benjamin Chaffin的小程序看着专门写一篇论文有点夸张,Greg Egan也许觉得自己的原创内容不是很多。倒是Vince Vatter到底在干什么呢?(也许只是懒)
      ——要是问题特别重要,或者博客作者影响力大,那么大家对于搜集整理的热心可能会大不少。现在来看,这个问题进展要么依赖一些不涉及高深内容的巧计,要么依赖其他领域的成果。的确不是很重要,要不是凑巧有个“死宅论坛匿名用户为数学难题做出贡献”的噱头,甚至都没什么传播力。
      然而,这种零碎的小玩意毕竟也是数学发现的一部分,相关成果的难度绝非“谁都能解决的课后题”,加之问题又总被提出([J2013]搜集了这个问题在网上的零散出现,我在这里再补充一个中文世界的案例 ]),哪怕出于避免重复工作考虑也该做些整合。实际情况却是相关内容散碎各处,难以拼合,看来几个主要参与者也没有太多整理存档和记录历史的兴趣。我们也已经看到哪怕是亲自采访当事人的Quanta Magazine网站,也在时间线上出现了一些误导,这除非自己捋一次,否则没法发现。甚至可以说,读者现在看的这篇文章,应当是目前全世界对这个问题的历史信息整合做的最全面的文章——这其实是件比较让人遗憾的事。


      啊,顺便说一句,根据Robin Houston在2018年10月24日的一条Twitter 来看,他显然不怎么喜欢四葉这个地方的基调——毕竟这是个从日本动漫爱好者交流地发展来的匿名论坛,不是吗?

  7. FatFish

    7楼 1月1日 物理版主, 优秀回答者

    参考文献

    [AT1993] Ashlock, D. A., and Tillotson, J. Construction of small superpermutations and minimal injective superstrings. Congr. Numer. 93 (1993), 91–98.

    [J2013] Nathaniel Johnston. Non-uniqueness of minimal superpermutations. Discrete Mathematics, 313(14):1553–1557, 2013. arXiv:1303.4150 .

    [W2013] Williams A. Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ=(1 2... n) and τ=(1 2)[J]. arXiv preprint arXiv:1307.2549 , 2013.

    [H2014] Houston R. Tackling the Minimal Superpermutation Problem[J]. arXiv preprint arXiv:1408.5108 , 2014.

  8. 死宅失格

  9. 顶一下然后慢慢看吧…只有高中排列组合知识的莱茵要费好大劲才能看懂_(:з」∠)_

 

后才能发言