FatFish

物理版主, 优秀回答者

最新动态 1小时前

  1. 4天前
    2019-01-18 18:02:21

    @自然法师之神 满足欧式定理及公设的几何性质的空间叫欧式空间

    咳,一般来说,欧式空间就是$\mathbb{R}^n$,以n元有序数组为元素的一个集合,至于在上面定义符合欧几里得几何的点线面距离,还是定义符合向量空间定义的向量法则,都是根据需要后加的。当然了,概念起源上看,$\mathbb{R}^n$是来自于欧几里得几何的直观印象。

    另外,你也可以在$\mathbb{R}^n$(的一部分)上搞非欧几里得几何模型,比如说我们定义球的大圆是“非欧直线”,对径点是一个“非欧点”,那么就可以在球面搞出一套满足非欧几何公设的体系——数学细节就不写了,不过这类模型是早期验证非欧几何不会出现矛盾的重要依据:这个“非欧几何”的任何矛盾都可以对应转化为欧几里得几何中球面命题的一些矛盾。所以只要欧几里得内部无矛盾,那这个非欧几何模型也不可能有。

  2. 上周
    2019-01-15 23:14:30

    关于这个封禁问题,虽然 @京斯 和 @但是法官…… 开会决定封禁的时候我不在,不过我事后进行了一些沟通。虽然我是物理版主不是数学版主,但是论坛现在只支持全区封禁,可以认为这个事应该涉及所有管理层。何况这两个争议贴我都批评过楼主——再说从维持整体论坛气氛的角度讲,我也应该说说我的意见。


    我是认为楼主不至于封禁,特别是我还很想问问“既然你说欧几里得几何就是欧几里得空间,那你觉得非欧空间又是什么,如何定义”呢。不过被封了么,我觉得也没什么冤枉的。

    但是另一方面,封禁应该有个预期。之前论坛是封过几个溜过来的民科,那个倒是没公告,直接灭杀了。不过我认为这种论坛封杀民科基本上是个共识了倒不用太声明。而且论坛有个相当霸道且口袋的使用协议 ,可以确保这些行为有预先说明。但是这个协议不够具体,对本贴这种争议场景只能提供个“法理依据”,没法提供今后类似事件的具体的执行标准。

    这种情况,在封禁前预先警告比较好,“如果你再做某种行为,可能会被封禁”,然后再犯再封禁。

    另外由于论坛的封禁功能比较简陋,空间上不能单区封禁,实践上无法限时封禁,只能依靠手动操作,因此一般执行时默认就是封杀,而不是 @DTSIo 的警告了——不过在无预警的情况下彻底封杀就有点过分了。现在既然被 @Phantom_Ghost 解封了,我不支持在没有进一步恶劣表现前追加封禁。


    我也不认同 @Phantom_Ghost 的标准。这个拿来律己还不错,但是论坛管理不只是个人问题。有一个完全无法沟通的问问题,懒得理的走了,又有一个根本不看回复的乱聊天,懒得搭理的走了,长期下去很多论坛用户的热情会被打磨掉的。现在论坛活跃用户很少,维持一个观感更好的环境也很有必要。
    对用户个人来说,论坛什么用户做了什么不太喜欢的事情,可以不管;论坛很多用户做了不太喜欢的事情,可以走人。但管理如果不注重这种事情,长此以往,某些不犯原则错误但是有所争议分歧的行为就会对论坛的活跃人员组成造成很大影响——特别是这种缺乏大基本盘的小论坛。我认为社区管理不只维护一些底线规则,还需要维护一个比较健康的符合论坛主题的文化环境。

    具体到本楼楼主,他当然表现的很“礼貌”,比如说对于@折木 奉太郎 的长篇回答表示了感谢:

    @自然法师之神 @折木 奉太郎 ,谢谢你的精彩回答!

    很客气是吧,但是我们看之后的某个发言:

    @自然法师之神 @FatFish,我就是认为欧几里得几何就是欧几里得空间,几何和空间等价

    看来他根本没搞懂折木写的东西。那么他到底在感谢什么?我不认为这种“友善客气”对于论坛的健康氛围有任何促进作用。不知道折木自己怎么想,但是我很郁闷。虽然我不想直接封禁,但我认为适当警告有所必要。
    ——这不单纯是对方是否缺乏理解能力、是否需要宽容理解程度低的问题,甚至楼主“没理解相关回复”都得从他的回复中推断。他自己从未明确表述过,对这些回复,自己有哪里存在理解困难。很多人因为过往经验、知识背景,会对一些特定的问题存在理解困难、接受困难。这是所有专业学习者都可能遇到的情况,论坛也没有对此进行排斥,看了之后仍然不理解需要多次询问也并非禁忌。但是想要答疑解惑,特别是针对性解答个人困惑,至少需要提问者明确做出合适的反馈。而本楼楼主似乎总是在重复自己最初的观念,其他人的回答造成了什么影响?他哪里不能接受?哪里看懂了?哪里没有?这些我们都不知道。特别是本楼各位回答者尝试了各种风格的答案之后楼主依然只表现出一股“我没仔细看你们说什么但是我这么想的”的态度,这个恐怕不单纯是“知识背景不足”“理解能力有限”“回答观点太高”“回答不易理解”等合情合理原因所致。换言之,这个人被封禁的原因(包括我也觉得该警告的原因)并不是大家觉得他太笨了,怎么说都没法理解而怒封。而是他的行为看不出任何对其他人回复的实质性尊重。从某种角度上说,虽然楼主只是概念比较混乱,而没有去发明什么奇怪的理论,但是这种近乎自说自话无视他人意见的行为很是有“民科”气息,完全没有表现出足够参与正常交流的“理性”.


    此外,
    论坛物理版有一个主要从物理吧吧规迁移过来的版规: http://chaoli.club/index.php/50
    版规中有很多对提问者的要求,远高于基本的“自由理性讨论”,当然,这个物理版规管不到数学版。但是这个版规大部分内容不是专门针对物理学科的特征制定,而是一些一般性的提问回答规范,虽不能作为本次行为的法理基础,作为一个“论坛管理层希望打造的文化氛围”说明却不为过。


    最后,由于论坛框架原因,现在全区封禁权力下放到版主,原则上这个权利应该只属于管理员才对。不过目前来看,考虑到封禁普遍不是因为被封禁用户只在某个学科上表现恶劣,版主封禁程度过大没有实际上造成任何困难。事实上本次封禁也是管理员 @京斯 主持的。而且流程上,因为封人直接缘由是数学版的贴子,封禁决定还署名了 @但是法官…… ,问题么,就是实际上这不只是数学版的问题, @京斯 对于其在生物版贴子 http://chaoli.club/index.php/4465 长篇大论离题万里的表现也很不满,本贴甚至也有所提及:

    @京斯 如果这帖还表现不明显,楼主在生物版另一帖下的大量回复就是通篇乱推理。要怎么定义才能把这看作理性讨论啊?

    可以说这其实是综合考虑其表现后进行的封禁,那封禁说明也该提到生物版主的意见。这个被忽视了。而且当时只是单纯封禁,没有说明理由,是我主张这种不是特别恶劣的行为,封禁需要声明清楚之后,才发布带有决策人信息的封禁说明。

    这个流程虽然算得上正式但是显然疏漏不少,不过诸如全体版主圆桌会议之类的事情毫无实践价值,所以也只能从部分版主意见中参考了。像是 @Phantom_Ghost 事后得知有分歧意见的,也只能事后再交流协调了。

    (这个贴子似乎偏到了管理政策上,不过坦白来说,我觉得题目的问题已经该说的都说了。偏就偏吧,为避免类似情况今后造成混乱,吸收其他人的意见,也许茶馆区应该准备个议政广场之类的?)

  3. 2019-01-13 16:39:27

    楼主这个问题在我看来仿佛是在问“爆米花是不是阿兹特克历法”。答案:当然不是,但是是什么知识背景驱动你问出这么奇怪的问题?阿兹特克人崇拜玉米之神?

    一般说欧几里得几何、非欧几何,说的是一个公理框架,或者满足这个公理框架的模型,一个整套的推理体系和相关结果。而向量空间是满足若干性质的一个集合。就我能想到的,他们之间那么点关系,不比玉米和阿兹特克人的关系多:欧几里得空间$\mathbb{R}^n$可以是一个向量空间,且这个空间可以作为一个欧几里得几何模型的背景。但是这个空间本身不是“欧几里得几何”,最多说是某个欧几里得几何模型的一部分。从你10楼的回复来看,你似乎是把欧几里得空间和欧几里得几何搞混了。

    另:
     楼主如果只是概念不清,则问题不大。但在发现有概念分歧的时候应该立刻说出来,然而你看2~5楼的对话,完全就没构成任何有效信息交流。2楼和我表达了差不多的意见,而楼主在3楼的回复除了念一遍线性空间的定义外,完全没有谈对2楼有关“非欧几何”的定义什么看法。根本不清楚你是没看懂这个定义还是不认同这个定义。而5楼更是和4楼的内容牛头不对马嘴,之前的讨论完全没出现“矢量空间”这个词,也看不出这个“等价”对于4楼的疑问有任何帮助,更何况矢量和向量本来只是一个东西的两个名字,就是一回事,而不只是个“可以等价……吧”,楼主在这里的概念也有些奇怪的错误认识。
         总之我是不明白这个交流是怎么变成这个样子的,楼主3楼和5楼的回复给我感觉就是完全没能理解2楼和4楼在说什么,而不只是概念不清。(如果概念不清至少应该有一些针对性的发问或反驳)这种交流风格完全无助于搞清问题关键。楼主应该好好想一下为什么会出现这种交流障碍,不然以后这种场合还会出问题。

  4. 3周前
    2019-01-01 20:51:03

    参考文献

    [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.


    本文题图即最早的四葉讨论串(备份 http://4watch.org/superstring/ )的题图,因为备份网站的大图似乎已经失效,所以我选的是wikia词条 http://mathsci.wikia.com/wiki/The_Haruhi_Problem 中的附件大图。

  5. 2019-01-01 19:29:32

    结语:非标准互联网数学

      互联网大为提升了人们的交流能力,也相当程度上促进了学术交流。现在用电子邮件交流学术已经是一种“传统”交流手段;而诸如arXiv 这种相对正规的论文预印本网站,也已经是很多数理方向学者必备网站。
      电子邮件节省了邮递时间以及邮递系统的地区限制、arXiv省去了审稿和发表的等待时间以及刊物订阅的限制,除去这两种“优化”传统学术交流的发明外,还有一些在传统时代很少见的特色,比如“网络社区数学”。 这方面的典范是博学者计划(Polymath Project )。这一计划由数学家Timothy Gowers在2009年部分出于社会实验目的发起。他在博客上呼吁群策群力来尝试给出密率Hales-Jewett定理(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也做不到。前者只能定点投放,无法提供公开平台吸引参与者;后者不利于零散的想法交流探讨。整个讨论过程都公开在博客中进行,之后有人整理了相关资料和记录 ,可供参考。

      既然这个实验这么成功,这个计划自然继续了下去,读者可以在下面的地址看到目前进行的所有计划和研究现状:
    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 来看,他显然不怎么喜欢四葉这个地方的基调——毕竟这是个从日本动漫爱好者交流地发展来的匿名论坛,不是吗?

  6. 2018-12-31 12:10:49

    五、世界线

      现在,我们已经从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文件贴出了他对四葉证明的整理版:
    [attachment:5c2b5b45073ec]

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

      2018年11月6日,Vince Vatter再次发贴 ,提供了第三版pdf:
    [attachment:5c2b5dfb3c956]
    根据他的说明,这一版新增了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那篇博文 ,就能找到“春日问题”的百科页面 ,不会错过证明的。

  7. 4周前
    2018-12-25 01:22:37

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

      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$对应的行进路线。
    [attachment:5c292184a52be]
      有一点需要说明,考虑所有超排列时,$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三人。我在下一节会详细介绍相关的出处与历史细节。

  8. 2018-12-22 23:34:59

    关于线性和循环时间观我恰巧知道一点,不过也不是太熟,相关论述无法保证准确性,楼主就当这是提供个关键词和文献索引好了。
    西方哲学传统上一般认为奥古斯丁是第一个强调线性时间观的哲学家。奥古斯丁本人就把循环和线性时间观强烈对立区分,不过这种区分方式是否恰当就不好说了。
    正巧今年有人写了篇中文的《重新衡定线性时间观与循环时间观之争》( http://www.fx361.com/page/2018/0926/4281019.shtml )。可以参考这个文章或者当个文献索引去进一步了解一下。我自己其实在这方面缺乏足够的知识来进行评判。

  9. 7周前
    2018-11-28 20:27:13

    三、$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算法运算时间也超出可接受范围了。想要继续开眼界,还得再改进算法才行。接下来,让我们把目光放的稍微长远一点……

  10. 2018-11-28 20:15:01
    FatFish 更新于 推导光速不变

    光速不变是来自于……实验结论。当然不是很基础。
    另外,其实可以认为相对论中有两个数值恰好相等的常数,通常都叫光速,这可能造成一些哪个更基本的混乱。我们可以如下进行区分:

    ·其中一个可以称之为“时空当量”,如果我们选择时空几何切入,以闵科夫斯基空间作为相对论的出发点,那他物理意义上就是时间和空间的转换量度,类似于热功当量。

    要求惯性系变换保证度规$ds^2=-c^2dt^2+dx^2+dy^2+dz^2$不变就导出了洛伦兹变换,因此洛伦兹变换中的那个参数$c$是时空当量,反映的是时空结构。即使研究的不是光子,一样要服从洛伦兹变换。而不是说时空的结构紧密依赖于电磁波。

    ·另一个就是电磁波在真空中的运动速度。这个波速恰好等于时空当量,这要归因于电磁场本身的物理性质。也就是通常说的“光子以光速运动的原因是光子无质量”。麦克斯韦方程组就是在表述电磁场的物理性质。从这个意义上他确实不够基本,只表述电磁场,不过这种区分之后我们看到时空当量本身并不依赖于电磁场性质如何,如果我们修改成光子有质量的形式,光子速度会慢下来,时空当量也不会受牵连变慢。

    而“光速不变”说的可能是一个以速度$c$运动的物体在洛伦兹变换下速度不变,这里出现的是时空当量,推导依赖于洛伦兹变换的形式;也可能是说得就是电磁波,先从电磁波的物理性质给出光以时空当量$c$运动,再结合前一条说明他洛伦兹变换下速度不变,推导还依赖电磁场满足的方程。

    不过仍然需要说明,即使第一种含义也本质上来自于实验。洛伦兹变换不能直接从相对性原理“导出”,需要再引入一条关于度规形式的初始假设,结合“惯性系变换不改变标量”的足够“基本”的要求才可以导出。然后我们仍然需要实验中验证洛伦兹变换,,以确保我们的初始假设符合实验结论。毕竟物理学是一门实验科学,对吧。(而物理学史上,也是先从实验得到了洛伦兹变换,后整理成时空几何形式的。)

查看更多