FatFish

物理版主, 优秀回答者

最新动态 1小时前

  1. 上周
    2019-02-08 03:08:25

    因为不作剧透,电影没法说得太多结果写的有点跑题,那就再跑跑好了,借此谈谈我的个人经历(咳咳,听说人上岁数了就喜欢唠叨这些),以及我对科幻迷和圈外关系的看法。


    大刘的作品有些不怎么工程师,科学主要是作为一种“文化背景”出现,实际表现很玄幻(克拉克第三定律.jpg),但是一个共识是大刘的人物塑造水平不怎么样,只是偶尔有一些出彩的人物,全都是靠着人物之外的剧情展开在拉分。基于这个特点,我一度认为大刘的小说在科幻迷之外不可能获得什么太好的反响。当时我试图给一些不看科幻的同学推荐科幻小说时,都得仔细挑选。那时我的结论是大刘的《吞食者》是最适合推荐给一般同学的作品,因为这部小说相对来说更接近普通人的审美,外星人入侵是一个大部分人都熟悉的故事背景,核心伏笔有一定的工程师科幻感,也没有超出普通人的理解范围,读起来激动人心。(我一直认为这是最有电影大片感的大刘作品。实际上某种程度上和《流浪地球》电影有点像)而其他作品对圈外读者入门就不太友好了。——对于文青气息比较重的同学我会改为推荐特德·姜,因为他文笔好,而且和那些文笔好但是科学设定偏弱的作品比,科幻独特的审美特征也很明显。
      我当时的想法是借着一些常规审美上也优秀的作品来让他们也熟悉、欣赏科幻的独特性,那种不那么“科幻”的作品起不到这方面的效果所以不做考虑。换句话说,我希望发展一些科幻迷,而不是仅仅让他们看几本书。

      当然了,随后的发展远远超出我的预期,让我那个谨慎方案显得有些不合时宜了。不过我猜,科幻迷们热切期盼《死神永生》的时候,恐怕没有一个人,包括姚海军、包括大刘,猜到现实世界会呈现出多么离奇的走向。——那个时候的科幻迷们对自己的圈子的想象往往是最为保守不科幻的,最多恐怕也就期盼还能再来一次科幻高考作文题蹭蹭热度。

    【未完待

  2. 2019-02-08 03:01:25
    FatFish 发表了帖子 《流浪地球》电影个人简评

    极具大刘特色的改编。适合科幻爱好者观看。【本文基本无剧透】


    首先用大刘自己的一段话镇楼:


        在那届笔会上,阿来请来了《小说选刊》资深编辑冯敏讲授国内主流文学的现状,强调科幻小说应该在文学和科学幻想上取得某种平衡,其实,《流浪地球》就是这种平衡的结果。
        对于小说中的人类逃亡,从科幻或科学角度讲,我是百分之百的飞船派,因为推进地球的能量绝大部分消耗在无用的荷载上,也就是构成行星的地壳内部的物质,这些物质最大的意义就是产生重力,但重力也可由飞船的旋转来模拟。但从文学角度看,这篇作品的美学核心是科学推动世界在宇宙中流浪这样一个意象,而飞船逃亡则产生一个完全不同的逃离世界的意象,其科幻美感远低于前者。
        不过后来的一次经历差点儿使这篇小说流产,那是我因公外出,第一次坐飞机,从万米高空看大地时,仍然一点儿都觉察不出地球的曲率,行星的表面仍然是一个无际的水平面,推进这样的世界简直是痴人说梦!但回去后还是坚持把小说写出来,最初只有发表时的一半长,后来应编辑的要求加长了一倍。王晋康老师在笔会上看到该文时说这应该三十万字才够,可在当时是没有机会发表长篇的。
        《流浪地球》还有许多方面不得不在科幻的严谨上做出妥协,比如氦闪,只是恒星步入晚年初期的一种活动,在漫长的时间里反复发生后,恒星才能进入红巨星状态。另外,当时没有经验,竟把地球发动机的具体参数全部详细列出,详细到可以很方便地直接计算地球得到的加速度,计算的结果是:发动机只能给地球零点(N多个零)几的加速度,别说航行,改变轨道都不可能。


    摘自大刘博客 寻找家园之旅 (2009-03-25 17:05:49) (发表于《科幻世界》30周年增刊)


    根据目前的一些访谈 ,大刘没人怎么介入剧情改编,那么这个非常有工程师科幻味道的全新剧情实际是龚格尔和郭帆两个人写出来的——从剧情的构成思路来说,他们确实是科幻迷的自己人。

      我个人一直很喜欢一类“工程师科幻”,其特点是作者是电力工程师剧情驱动及转折主要依靠描写技术问题及其化解,读起来仿佛像是在看解决工程问题的纪实栏目(当然纪实的我也喜欢)——只不过是虚拟情景的虚拟问题。这方面的优秀作品我个人推荐《重力使命》和《天堂的喷泉》,重力使命中那段“为什么重力增大后不能用独木舟了”的情节,在我看来是这类情节的典范。这一片段甚至不需要幻想出来的技术,伏笔直接埋在现实物理学中。
      当然这和《流浪地球》电影的情况有点差别,因为这故事从一开始就在技术上不成立。而且电影原创那个计划也在技术上不成立。电影的情况更像是大刘另一部我很喜欢的小说:《球状闪电》。坦白来说这部小说关于量子力学特别是观察者问题的描述基本全都是毛病。而且很明显可以感觉到是那种大刘看了一些相关科普后产生的常见误解。(作为一个从小看物理科普最后学了物理的人,我基本产生过几乎完全相同的误解,而且我也见过这些观点在“科普受众”层面相当流行。)但是即使我后来了解更准确的研究之后,我仍然很喜欢这部小说——因为这部小说塑造了一个不依赖具体知识正确性的精彩剧情主线:探索实验一个未知现象,提出各种理论解释,最后再给出能解释之前种种奇怪现象的最优理论。整个过程非常有一种科研感,仿佛在看一段虚拟的科学史。(大刘创作的《山》和《三体》、以及索耶的恐龙文明三部曲中这种“探索世界的虚拟科学史”剧情都占有很大比重,读起来非常让人愉快。)用大刘的话说,这类创作本身有独特的美学意象。电影中那个(并不成立的)计划也有那种工程师科幻独特的剧情转折戏剧性。

      除去计划并不科学之外,电影的另一个缺点也非常有大刘味——人物塑造不理想。这同样和大刘本人没什么关系,主要是剪辑的问题和演员发挥的问题。主角组兄妹的部分情节因为剪辑和本身的演技限制表现并不好。倒是几个展现配角性格的片段处理的不错,令人印象深刻,问题主要出在主角组上。
      所以说,对喜欢大刘小说的人以及喜欢类似风格作品的科幻迷来说,这些缺点都在大刘那见过了,那么这些问题其实都不是问题。独特的科幻审美要素非常充足,评分会高一些。而其他观众可能重心放在人物关系感情演出上,评分就会低一些。(按我个人评估,即使对这些观众来说,这部电影也至少是及格分)

      其实工程师科幻常常都有人物塑造单薄的问题,《重力使命》的角色几乎没有性格,我都分不清他们谁叫什么,也就能分辨一下哪个是地球人哪个是外星人。《天堂的喷泉》唯一我印象比较深刻的角色其实是那个洋和尚,这还是因为他恰好在一个关键剧情的地位(而不是因为他本身的性格特点)。这当然不是说重心放在工程问题的就写不好人物,比如特德·姜的作品就做到了科学部分非常坚实、文笔也非常出色,而且科学部分对剧情和抒情的发展非常重要,并非相互割裂(可参考他的短篇《呼吸》 )。只是这种科幻作者实在是太少见了。大部分情况下,一些人物塑造差的作者是靠着靠着优秀的工程师剧情拉起了作品质量,在非科幻文学创作中,很难有机会能做这种找补。这大概是科幻审美的一种独特性。(当然了,不是绝对独特的,比如纪实工程文学也能做类似的事情。)

  3. 2019-02-06 01:30:35
    FatFish 更新于 论坛 2019 新年更新

    @京斯 (由于画师在鸽的原因,本论坛的“正式”吉祥物蛾子少女小往暂时没有设定更新,只能说敬请期待。)

    由于画师摸灵感大王,正式图进度长期鸽置。为应对此次危机,我画了五分钱水平的表情图,可以有效替代不知道何时出现的新设定图:
    [attachment:5c59c6f37b7f6][attachment:5c59c6ed5b0d7]

    图片是放在案板上被献祭的油库里摹的下面这张加百璃趴桌子表情图:
    [attachment:5c59c8378f117]

  4. 4周前
    2019-01-18 18:02:21

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

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

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

  5. 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 事后得知有分歧意见的,也只能事后再交流协调了。

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

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

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

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

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

  7. 6周前
    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 中的附件大图。

  8. 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 来看,他显然不怎么喜欢四葉这个地方的基调——毕竟这是个从日本动漫爱好者交流地发展来的匿名论坛,不是吗?

  9. 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那篇博文 ,就能找到“春日问题”的百科页面 ,不会错过证明的。

  10. 7周前
    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三人。我在下一节会详细介绍相关的出处与历史细节。

查看更多