{"analysis":{"reports":[{"analyzer":{"cost_borne_by":"Eksmu operator","kind":"model","name":"gpt-6-luna","operator":"eksmu.com","prompt_template":"eksmu-analysis-v1","requested_model":"gpt-6-luna"},"created_at":"2026-10-11T07:25:49.464608+00:00","findings":[{"category":"missing_definition","confidence":"high","id":"F1","kind":"opinion","location":{"quote":"若长词 v 是周期文本的一段，且其前缀 w 比 v 短了 k 个周期，那么当 v 的计数中存在没有被“括定词”解释的出现时，规则会要求 w 至少多出 k+1 个相应计数。","section":"1. 用子串出现次数造出下界"},"quote_verified":false,"severity":"major","statement":"周期性约束是计数构造及其下界引理的关键部分，但这里没有说明怎样判定某个出现是否已被“括定词”解释，也没有定义“相应计数”或给出实际的不等式。因此读者无法据此计算 m(s)，也无法核验后文声称的 m(s)≤N_T(s)。请给出约束的完整形式化定义，并说明其适用条件。"},{"category":"derivation_gap","confidence":"high","id":"F2","kind":"opinion","location":{"quote":"分别赋予适当的非负整数重数，使每个顶点的入度等于出度。","section":"2. 把计数编码成平衡有向图"},"quote_verified":true,"severity":"major","statement":"“适当的”边重数没有由 m(s) 明确给出，文中也未说明空串处边重数如何处理。仅凭这一描述无法推出图平衡，更无法核验上行边和下行边总数各为 W。请给出边重数的公式，并证明它们满足平衡条件及所述总数。"},{"category":"derivation_gap","confidence":"high","id":"F3","kind":"opinion","location":{"quote":"这样每个层的连接预算最多使用一次，总额仍不超过 W。","section":"3. 周期层与组件连接"},"quote_verified":false,"severity":"major","statement":"这句话陈述了控制近似比的关键预算结论，但此前的层连接、延后处理和有向环处理均以概述方式描述；没有给出可执行的边添加规则，也没有说明如何证明环处理后每个层的预算确实至多使用一次、连接后的图连通。请给出相应构造及预算不变量的证明。"},{"category":"unsupported_claim","confidence":"high","id":"F4","kind":"opinion","location":{"quote":"论文还通过显式枚举子串、有限个周期模板、图边和窗口，说明计数、重排、连接与欧拉回路构造均可在输入编码长度的多项式时间内完成。","section":"4. 从欧拉回路得到超串"},"quote_verified":true,"severity":"major","statement":"“有限个”并不能单独推出多项式规模。文中没有给出周期模板、窗口及其重排数量相对于输入编码长度的上界，也没有说明计数和边重数的编码长度。因此多项式时间结论在此处无法核验；请给出各枚举规模及算术运算位复杂度的界。"}],"format":"oic.analysis-report.v1","id":"9e50c435-c8b9-4648-be78-055278269401","limitations":"本评阅针对所给中文导读；其自述并非原论文逐段翻译，因此无法判断原预印本是否已补足这些细节。","revision_id":"3587fd16-9d37-4c99-9068-d98df6751cf2","revision_sha256":"0f76d02da1d55b3ceaa960dba6462e93bc3852b3c91f6e0e3a407a91e61d37e2","scope":{"not_checked":["未能依据所给文本核对链接中的预印本是否包含上述省略的定义、构造和证明。","未独立验证该结果与既有最短公共超串近似算法文献之间的关系。","attachments, data files and code were not read"],"read":"title and full body of this revision; no attachments"},"sha256":"ebdb1dda73c8a10a3844b336e1fa4e423e72c6eb7f9c662841794c4d85c41b2f","suspicious_instructions":false,"usage":{"cost_usd":0.0028,"input_tokens":2512,"output_tokens":5012}},{"analyzer":{"cost_borne_by":"Eksmu operator","kind":"model","name":"gpt-6-luna","operator":"eksmu.com","prompt_template":"eksmu-analysis-v2","requested_model":"gpt-6-luna"},"claims":[{"assessment":"not_established","claim":"该构造给出一个确定性多项式时间算法，输出长度至多为 2OPT(S) 的公共超串。","id":"C1","reasoning":"稿件陈述了结论并概述证明架构，但关键的计数构造和分量连接论证没有给出足以核验的定义或推导。因此，本文本本身没有建立这一主定理；这并不表示该结论为假。","section":"问题与主要结论"},{"assessment":"not_established","claim":"计数 m(s) 满足 m(s)≤N_T(s)，从而 W=∑c∈Σm(c)≤OPT(S)。","id":"C2","reasoning":"稿件称有关键引理证明此结论，但没有展示证明。尤其是周期性约束仅以文字描述，m(s) 的完整定义及其计算或选择规则也未给出，读者无法据此检验该引理或复现 W。","section":"1. 用子串出现次数造出下界"},{"assessment":"not_established","claim":"基础图可用不超过 W 条额外上行边连接，并且所有连接预算至多使用一次。","id":"C3","reasoning":"稿件把这一点称为技术核心，但只列举层、接触窗口、按周期长度处理及字典序极大旋转等操作，没有给出这些对象的精确定义、操作规则或各情形下的预算核算。因此，额外代价不超过 W 的关键结论无法从所给论述推出。","section":"3. 周期层与组件连接"},{"assessment":"supported","claim":"若得到包含空串、连通且平衡的图，则从空串出发的欧拉回路可读出公共超串，长度等于上行边数。","id":"C4","reasoning":"在稿件给定的边标签规则下，欧拉回路遍历所有顶点；上行边追加字符、下行边不追加字符，因而边数与输出长度的关系以及由顶点访问得到子串的思路是连贯的。此结论以相应图确已构造并满足所述性质为前提；这些前提本身尚未由稿件建立。","section":"4. 从欧拉回路得到超串"},{"assessment":"not_established","claim":"计数、重排、连接和欧拉回路构造均可在输入编码长度的多项式时间内完成。","id":"C5","reasoning":"稿件称所枚举的对象是有限的，但没有给出周期模板、窗口、图边等对象的数量上界，也未说明计数值的位数或各步骤的运行时间。因此，“有限枚举”本身不足以推出多项式时间界。","section":"4. 从欧拉回路得到超串；贡献与边界"}],"created_at":"2026-10-11T08:02:42.967911+00:00","findings":[{"category":"missing_definition","confidence":"high","id":"F1","kind":"opinion","location":{"quote":"论文还加入一类周期性约束。","section":"1. 用子串出现次数造出下界"},"quote_verified":true,"severity":"major","statement":"周期性约束是下界构造的关键组成，但这里只给出概括性描述，没有明确量化周期文本 A、词 v、前缀 w、差值 k 及“括定词”的条件，也没有写出约束的精确公式或算法。请补充可直接判定和计算的正式定义，并说明如何据此选取 m(s)；否则下界 W 无法复现或核验。"},{"category":"derivation_gap","confidence":"high","id":"F2","kind":"opinion","location":{"quote":"关键引理证明，对任意公共超串 T，都有 m(s)≤N_T(s)","section":"1. 用子串出现次数造出下界"},"quote_verified":false,"severity":"major","statement":"该引理承担了 W≤OPT(S) 的全部论证，但稿件没有提供证明或足以检查的归纳步骤。请说明普通扩展约束和周期性约束分别如何保证出现次数界，并解释这些约束如何共同覆盖任意 T 中可能重叠或周期重复的出现。"},{"category":"derivation_gap","confidence":"high","id":"F3","kind":"opinion","location":{"quote":"这一部分是证明的技术核心：周期文本的对齐、窗口排序和字典序极大旋转共同保证连接时既能找到真实图顶点，也能把额外长度控制在预算内。","section":"3. 周期层与组件连接"},"quote_verified":true,"severity":"blocking","statement":"这里直接断言关键连接性质，却没有定义层和块、接触窗口及“真实图顶点”的判定，也没有逐项说明连接操作如何使用预算、为何不会重复计费，以及有向环处理为何总能以不超过相应周期预算完成。由于 2 近似界依赖总额外代价不超过 W，这一缺口使主结论无法由本文所给论证推出。请给出精确算法和完整的预算证明，包括每种连接情形及环处理的论证。"},{"category":"unsupported_claim","confidence":"high","id":"F4","kind":"opinion","location":{"quote":"论文还通过显式枚举子串、有限个周期模板、图边和窗口，说明计数、重排、连接与欧拉回路构造均可在输入编码长度的多项式时间内完成。","section":"4. 从欧拉回路得到超串；贡献与边界"},"quote_verified":true,"severity":"major","statement":"“有限”并不说明枚举量相对于输入编码长度是多项式。稿件没有给出候选周期模板、窗口、边或重排的数量上界，也没有分析整数计数的编码长度及各步骤的时间复杂度。请逐步给出这些上界，并说明输入字符串总长度 n 下各步骤的多项式界。"}],"format":"oic.analysis-report.v2","id":"a27eb036-bee0-420f-8a60-93926164ffd1","limitations":"由于所审阅文本明确是证明结构概述而非逐段翻译，无法据此判断其省略的技术细节是否在所链接原文中完整给出，也无法判断概述是否准确转述原文。","overall":"稿件提供了清晰的证明路线图，并且在图已构造完成的前提下，欧拉回路读出超串的部分是连贯的。但当前文本没有给出足以核验计数下界、至多 W 成本的分量连接或多项式时间界的细节；其中分量连接是得到 2OPT(S) 主界的关键步骤。因此，本文目前说明了所声称结果的思路，却尚未在本文本身建立该算法及其保证。补入正式定义、关键引理证明和复杂度界后，读者才能判断这一构造是否确实给出所述保证。","questions":["周期性计数约束的完整形式是什么？“括定词”、周期文本的平移等价及相关计数分别如何严格定义？","m(s) 是由一个明确的构造算法选出，还是从某个可行解中选取？若存在多个可行计数，算法如何保证所选计数满足出现次数引理？","层连接与环处理的具体规则是什么？能否给出一个逐步例子，展示每个连接请求如何对应到图中的顶点和边，以及预算如何核算？","多项式时间分析中的输入规模、周期模板数量和窗口数量分别如何界定？"],"revision_id":"3587fd16-9d37-4c99-9068-d98df6751cf2","revision_sha256":"0f76d02da1d55b3ceaa960dba6462e93bc3852b3c91f6e0e3a407a91e61d37e2","scope":{"not_checked":["未独立核对所链接预印本 PDF、仓库条目及原文中的定理和证明；本报告评估的是所提供的中文稿件。","未检查原文中可能存在的详细计算、辅助引理或实验材料。","attachments, data files and code were not read"],"read":"title and full body of this revision; no attachments"},"sha256":"c874d5b50e6159d59badfe806712c5e90e1152ada5720471d453c08b0bee28fa","strengths":["稿件清楚地区分了所述新构造与经典最大重叠贪心算法，没有把前者的近似保证错误归到后者名下。","“先构造长度下界，再以相同预算连接分量”的证明架构易于把握，也指出了周期性连接论证在整体证明中的位置。","单个重复字符 a^h 的例子具体说明普通左右扩展约束可能低估重复需求，并解释了引入周期性约束的动机。"],"suggestions":["将当前概述中的计数规则改写为形式化定义或可执行伪代码，并给出计数下界引理的完整证明。","对组件连接部分逐类列出连接操作、前置条件、增添的边及成本；随后证明预算不重复使用，并单独证明有向环处理中的周期比较结论。","给出基于总输入长度的显式复杂度分析，包括候选模板、窗口、图规模和整数位数的上界。","若本文定位为导读而非原论文的完整证明，建议提供原文对应的定理、引理和证明页码或章节，便于读者核对哪些论证来自原文、哪些是本文的概述。"],"summary":"稿件是一篇关于最短公共超串问题的中文导读，概述一篇所链接预印本据称提出的确定性多项式时间 2-近似算法。其证明思路是先用子串出现计数及周期性约束构造一个长度下界，再把这些计数编码为平衡有向图。稿件随后概述如何以至多该下界的额外代价连接图的分量，并通过欧拉回路读出公共超串。它还声称该算法可在多项式时间内实现，并明确指出这不等于证明经典最大重叠贪心算法有相同保证。","suspicious_instructions":false,"usage":{"cost_usd":0.0029,"input_tokens":2921,"output_tokens":5168}}],"responses":[]},"anchors":[{"bitcoin":{"height":970875,"merkle_root":"92fd1c9da1e4c97b1ab39ceb6a00d6a99eb3d4356e0bfd99a805f5f7f05cfec3"},"checked":{"at":"2026-10-11T06:16:08.756871+00:00","block_time":"2026-10-11T05:33:53+00:00","matched":2,"method":"public block explorers (not a full Bitcoin node)","mismatch":false,"results":[{"block_hash":"000000000000000000018c9d321d9177f1cc9a10b0b07297da4d48f44f177ca3","match":true,"source":"mempool.space","time":1791696833},{"block_hash":"000000000000000000018c9d321d9177f1cc9a10b0b07297da4d48f44f177ca3","match":true,"source":"blockstream.info","time":1791696833}]},"head":"86afd82ca46150ccbc1351d8f5e20feab8c934b14bb6796b8e1b300395682b94","id":1,"method":"opentimestamps","proof_b64":"AE9wZW5UaW1lc3RhbXBzAABQcm9vZgC/ieLohOiSlAEIC7dq3tBmqRBzP2H0qAtE1+UjOksvwohpcVtndoLulhrwEDNlWJ+FB4pMCuIku2MHAZ4I//AQL0X7uiWM+4g9CwnONQ1/+AjxIJzW5d1mBvupDELvREowO1oV47qjcpVPGM9nLVMVNJIHCPAg7qf0YHXm2jMamWbmZpEsdrornqLCGn2IrgOuZKg30ZsI8QRqyxUW8AhVHhhNbgAhJwCD3+MNLvkMjiMiaHR0cHM6Ly9idGMuY2FsZW5kYXIuY2F0YWxsYXh5LmNvbf/wCD2MnXk4ivnDCPAgB3sH6l7+j8PBPBQcBPiPksJtk1/6ilmhnt2u5nNK0H0I8BDVkHxBNlSD0iH40Y2DWsrwCPAgj12RvIPXbNoBpu6UtnuxvswU/24LX96ENzppBlzNv+4I8SDIbyZIiukbzSA5zaK7nOuit0kXE3jQwjzw8IeC6OWp0gjwIA2hYhUSkA9EfeEkZFIuJ/s0S48/Adz1KFN1zlV7rmncCPEEassVFfAItFbo7FWmB9T/AIPf4w0u+QyOLCtodHRwczovL2JvYi5idGMuY2FsZW5kYXIub3BlbnRpbWVzdGFtcHMub3JnCPEg/kkwZkvUByz/DtINWhyM7AMlUjD+Zz8BRYJC/1n6vDgI8SCav7FQYn2Nf6rvPVaAI8AkouuAS9kP/+51kWLMQwlm/wjwIMwpWrUJEtEHOYfxjkGPzwBL9eB7gbqojU41Co54gZr1CPEg/GE77RJaJOh2BQmCh8SjK1J2s2nt3QI7ewbC4Zg1FCkI8SAsVF/lgRh3yusAJEuMlz2ViK0cZJXxz1XLTsgZokxPowjxIOCIBP7kXS92hnu0x/inaiOhDwdEIou36j5UCdXyUyq0CPEgwE5Agj0NSNG17+24vs9fFHpfpv1BY8Ktr7l5xJcp7OII8CBtkDrFGfX6rm1KTh7xXNmJMaX/aVNxT7VHSU8du2RR0AjwIIbdlxkaBHznWJCk0X8SMVRZR8fmWp0OMFzn2D6xiriBCPAg621w4n0u0ZQeb6heoo+seY6wO00hxNu83QKxx1SARmEI8CC70xM1Ecle/yz/wA7LNiFx7Mrtdqh0AvWzDiuY1kNivAjxIDncJ+fkXW24KHwkWpo9x0VfmOO1bDmxZozRZy5OuxNTCPAgX5pVZz+Xgb07hSTjsBrnt4rePnaDohZFq3Dq4cklXvII8VkBAAAAAaR+U4ed+tOau84zwGWLOgIZaNyU5+mNC9BVpT1lTTr5AAAAAAD+////AoCtAAAAAAAAFgAUexf0V4XxYOpbrLrN5LzI8LCqeBcAAAAAAAAAACJqIPAEetAOAAgI8SDwoBa0uEkvMtxjpUBmtP8L/JlkbOkrNrCR2ZBmk8A3EwgI8CBttj0lRxiUAzBkQt4foraHtF84EXRBwnsrT6z1VXsyaQgI8CDwbvWlgJzG4rapQdCYEY135frnvh9nV0yq+drmZ+e3tAgI8CD9tFBqFg0irDrxcl+y1m1D5WDysgkjNy9WFvsDgOeZyAgI8SCKDHual3/hmMRTUqCsNAuRaiBaplXEd8n+0ekEl+H/mwgI8CBBjx4jl7LHmx8RHfoey5Ve8r+KPLhDISZIJPA9OOlerAgI8SBCNVZyHZXqIHKWcsgC1+FFOdvqyHk2YLFSauLURqnicQgI8CCs3OdorSaQPcQ+Cl9b1eyBI0xBbi31oLJguiHtjZFmNwgI8SBxUzOahF8PoHKYG8yOpPD5Sew1qeDUIMKk448NclJe8QgI8SBEQukiJH7rrcb2XJ2vaaDUUWvNeBSsPtulZW8lz+bQfAgI8SAI7IzzfTlzZXOTZs27l8dhBE7kckSYxN0HJlo2QATh+wgI8CBKPg6momRCNPp0q3t7usFKTNAyNm6uCkqM/UpwKMWgDggI8CCAt1r3Kau6lR+9ziHWLKrDV5gwzwadC9iQw7qu6EgUswgIAAWIlg1z1xkBA/ugO//wEN1NEmP4l7eMzTs+RL+B3HwI8SC6KPOrf9gFpASQ2h1tyYmGtOw2QoQf0WCDGS4lpYjZugjwIDflrW0QakkkWYvSWldsBrtxsSGXp1tZY/wGyekSjiobCPAgz/SsBc8fOss37imp2qapUKGj2rnAGAFwPKg9IGphgAwI8QRqyxUW8Ah3hFt8haa9xwCD3+MNLvkMjikoaHR0cHM6Ly9maW5uZXkuY2FsZW5kYXIuZXRlcm5pdHl3YWxsLmNvbfAI+ghm2wApcZMI8SBvTN9n+o9PErycJXWLLVdkwqduwd3+nuYCyeE5/ADchgjwEPpnbias+hcFyOE/bKTohCwI8CAzMCLLnPl5ryzoDS7MOBFbzKl9Rl4B2Qx3pwLYDMwv6gjxIBbbtmoqkPyUFMfn/JUh6rZCXA/NLpv5dDs8G9avXKUsCPAgHIQTvA3whXylROQL9FHPtbEcQsLVQB8WlxdLyCK+9HgI8QRqyxUV8AgTywGHw4WDUACD3+MNLvkMji4taHR0cHM6Ly9hbGljZS5idGMuY2FsZW5kYXIub3BlbnRpbWVzdGFtcHMub3Jn","seq":6,"state":"confirmed","submitted_at":"2026-10-11T04:48:23.001705+00:00"},{"bitcoin":{"height":971056,"merkle_root":"5890e312a5f01afaaec0a75d6256b022d33e85164ff9b80091cb77e6433bcbb6"},"checked":{"at":"2026-10-12T12:19:09.463902+00:00","block_time":"2026-10-12T06:54:47+00:00","matched":2,"method":"public block explorers (not a full Bitcoin node)","mismatch":false,"results":[{"block_hash":"00000000000000000000c66d99e32a6ab0ff659a50365d8827858bfb837db668","match":true,"source":"mempool.space","time":1791788087},{"block_hash":"00000000000000000000c66d99e32a6ab0ff659a50365d8827858bfb837db668","match":true,"source":"blockstream.info","time":1791788087}]},"head":"1560ed82a829deac3273eef044f79a91c22465ab2c1859ddafbd0189824d666e","id":2,"method":"opentimestamps","proof_b64":"AE9wZW5UaW1lc3RhbXBzAABQcm9vZgC/ieLohOiSlAEIG8u3fBpFz814UkSONI1+VHmLeTBxBX+4ayTjNHZMGT3wEP1Y+5sa/tNrw8qG0dIXiyUI//AICNWhV5t+xU8I8SBMDq1ETARV//e97eyrD63J/QmiSfx/ifjP2FcOdOrJuwjwEAcxHAUR9TVJcrbTKbl/nTAI8SAGQ4T89JjnuOHSamaB9yMLP6eXz2WqsXeY3gcacqyDoQjwIFocjFg8UEpuQpjYp5L3QhQLfBQU4PEwZK0cfayoqyfUCPAg3429TuKrqmOJaARTf5kL0xG37b6hEMLE6yzywE8SD8MI8QRqzHsn8Ah9GHybDrgMr/8Ag9/jDS75DI4sK2h0dHBzOi8vYm9iLmJ0Yy5jYWxlbmRhci5vcGVudGltZXN0YW1wcy5vcmcI8CAJqP5pMd39MArshZDwbN+/xtfL5dlOuMi4C2LJFGJDRAjwIDgaCj3ybXD9O/b4f/i2KVyCEKlK0DD5FTF84tQsmT6kCPEgEwM2zCBy4JxDDSY+sb5ddRByI38/7bY3MYoKSWk2bbII8CDsoiB2bVAbCt3LI6melAv71aBpjenBFYEt/PAvXbDKdAjxIE7pJmwiAkKvRvvrtw9YhGWz2UnxHat/vcBRMyNjUQELCPAg2WoiI4OW+jyC36qDL/EDfLX7YQkjfWmbMgRxwFrpXCwI8SBZv1rB1UgDZXVr+nNdS2z4ZCFTEWPOiQAsDZIrsFKs3QjxILgsTJSjNGDJqi2h4Oi0qUprvICWIl2cVbeu6TxlRRYLCPEgPsYR7ReGUGbTWwq08R0rHXNAXpgHD+SwZmuxv5bKghMI8SBCbJyseyVnuLdBzuaXAkF9YutG3sd89WAu5bA0hAQUOQjxIAKgn/YKXwFEwVQ+Ca1kQwxx6Zwz+KOPFzzxDGRNEpN9CPAgXDkDav/muXRZow3ggW0w734+HVG9bll2pzK51obUpJYI8VkBAAAAAWI+NORyS3eLJvsx/nU4peBh4YFoadUO1ycs0hibSoqxAAAAAAD+////AvWgAAAAAAAAFgAU7YLOUYDVwlcxIH7g/CS5lu+zwFQAAAAAAAAAACJqIPAEL9EOAAgI8CAtQ02mhLoUOGIBfgYAsHGORC3lQIyhgx5GIAp9S6i0FggI8SBNhE2aj+p6OTMdJX6c7uRRn8Mvkmgv9qhlOLdi92WWpAgI8CBv33r+ZX+zfPMH1lg8zpkT+fQ0Z/1A8oCAEQiG2agJmggI8SA2JQNTplh6VCNchAqXUPYNI88uzPhFi8KPf6AIXfQvgggI8SAdiMuzFtjRImk+iE8GZgz42UzC9G6+iqh0Saq/uh1mbggI8CD0kfZPkElMrKVIc1lQa5mXJr8Y8ebrRzgRIP8j/KjjEggI8SDKWOq0DgUTBu5N21jnfu/N/B+rbt/p4LvvlLUb6YC3WwgI8CB99rq0misL2UaSCNC8UDybxjxrY1WpQTg3j3EFpxhMqggI8SBwRyPPwSqQcO5YwanFhhQZreAEd6dUrHvBgVVFbPOP0QgI8SCcBChTdA94fe6SszfL60fJQ1Y/sQxrip7m4RCrNRHkxggI8CDStu2CRNRra9chOoaXwSqSjptPPhAsj7yE24EazPUVNQgI8SCaWbWU2DVfnPda7LiGbEd5FM3BTqTIqhTt0KDdrxolEwgI8CBBJkW4G/cmiplBkdK9pZxIi+exVY4RxzcmdtIpyqSRqAgIAAWIlg1z1xkBA7CiO//wEEImpM3MlDqnbmf6cXyswH8I8SBTWvocipbdGYDiz/1k8vB5pOhEtE6XUjPh0HlFefO5uwjwIKypXrtzxmgT0sg5lwe/ECA9gBtY1bWEXZWwuDlEGFRfCPAgXjfXIrf/MeFoFgIqGxE6Qweswf01EDACk3rBABJUdrMI8CAHcdZeM8AxDRvr2zX/XkLCkTKR34HGy5KHZsgbG0T2igjwICeKBDNMT4ODZ/skfcyKL8VD2ebdeB6kfNSVmbYQzsKRCPEEasx7J/AIP2xef4IYZzUAg9/jDS75DI4jImh0dHBzOi8vYnRjLmNhbGVuZGFyLmNhdGFsbGF4eS5jb23/8BCQYSZ3U/1sW6+tfxhFuRBbCPAgt97+SCLPCl0dhUWlVDkTJNvPj0DOxK9Wz+jZ8U5uQk4I8SCy/DxpdBDF2pMClvEeEXA6aYA6B1RkywbwDpu0k86gYwjwICxD4kn7FnexgoR5A6Q1lCY12PS7ca0SXycL4pK3TfsnCPEgi+CfAolahWEvSTllJhV69iCgX4HZYL9CuZunBSUDGlII8QRqzHsn8Ahvf7GlPqtZ4wCD3+MNLvkMjikoaHR0cHM6Ly9maW5uZXkuY2FsZW5kYXIuZXRlcm5pdHl3YWxsLmNvbfAIuvhTc0N9U0cI8CD093G613zR+rJjLxJ5b87hmFd4mqiqv3bQDNc6LpFcbAjwEJprlRdT12HBEtMIGVH9n+QI8SCp+Ga0wM6NzDSjMS3b70aJXYSFFGWi/hf4Kzgus7+cUQjxIOdJmruTR+e6iBRYSvLqfjK19WPijjqgcl19MJdWlVYUCPAgIvqrRZtGhBSyZ3AhQ59R9cVpOoUwyn9dWKXWfsKPauMI8QRqzHsn8Ag+42Y/FKZkvwCD3+MNLvkMji4taHR0cHM6Ly9hbGljZS5idGMuY2FsZW5kYXIub3BlbnRpbWVzdGFtcHMub3Jn","seq":8,"state":"confirmed","submitted_at":"2026-10-12T06:16:08.069666+00:00"}],"chain":{"algorithm":{"chain":"head_0 = 32 zero bytes; head_n = SHA-256(\"oic.record-chain.v1\" || 0x00 || head_(n-1) || record_sha256_n), hashes as raw 32-byte values","opentimestamps":"the stamped file is the 32 raw bytes of anchor.head; verify with: ots verify -f (needs a Bitcoin node)","record_proof":"start from previous_head, fold the record digest, then each following_record_sha256 in order; the result must equal anchor.head","record_sha256":"SHA-256 of the record without its \"sha256\" field, as JSON with sorted keys, separators \",\" and \":\", UTF-8, non-ASCII characters unescaped"},"entries":[{"backfilled":true,"chained_at":"2026-10-08T14:00:00.613605+00:00","head":"3b4a191557f5ba0526107e7202b20a656b8eb81f06bf9e772c6026d7ec27e068","record_id":"1c80c356-fc13-4289-a2e0-c14d26977067","record_sha256":"ad255dbbcba0ab2f4c5d3e01a4803cce31dd421e30e27d03a7e38c679ca9d6c1","seq":1},{"backfilled":true,"chained_at":"2026-10-08T14:00:00.613605+00:00","head":"074baf8db29cba1b3eac2d407a3658bfd804e3794dd2370ee07eb3257b82b1f5","record_id":"38ccd43f-763e-4586-ac24-e7ed3c3ea076","record_sha256":"9944ec8d2240c5d89bef0e4fa7e24ad713153cf11cae0810e3ad3d23221ffe64","seq":2},{"backfilled":true,"chained_at":"2026-10-08T14:00:00.613605+00:00","head":"b81ab6947c7b75ee73c7b3e8467dee6cec69262271dac3fe4968412339051921","record_id":"586e11fb-797a-4e24-9fb2-b23b0aeec9f4","record_sha256":"d9818abb5b42f4a74aad0b115be08aaaab70196426e456e50aaaf481663251bf","seq":3},{"backfilled":true,"chained_at":"2026-10-08T14:00:00.613605+00:00","head":"b52017ff876452f1a21b85cab458b6f51514d2c44e466f21a2af6625c6b16522","record_id":"2268de50-942e-4ccc-80f3-882669ecf72c","record_sha256":"3320478ef7a33cd628bd9e57a7c08d20335311af7b18002cab6bcc41ed4feafe","seq":4},{"backfilled":true,"chained_at":"2026-10-08T14:00:00.613605+00:00","head":"35f634e6b1c51025b1548bf155a7ea9541fb5fadb01a9ce868364c6c39ddcf55","record_id":"ca6b9401-e9e3-4079-ad53-e99f61579399","record_sha256":"91478ebe006a87d80986591bd7bdf1b528fbaa79447dcae4baea7d6050714a5a","seq":5},{"backfilled":true,"chained_at":"2026-10-08T14:00:00.613605+00:00","head":"86afd82ca46150ccbc1351d8f5e20feab8c934b14bb6796b8e1b300395682b94","record_id":"3dc2d521-7bb8-45e4-acb1-00470642e80e","record_sha256":"14ffba3aeac2743b9d6598ddbb4f29834dd34dab9ed4d06dfa0ebd71b5573d87","seq":6},{"backfilled":false,"chained_at":"2026-10-11T07:17:36.994191+00:00","head":"d8c89844d1117926a76d2fac729381eda97726331b5148e0ed3bbdf3e2c47a87","record_id":"6d5e4fa2-4ed3-41e1-a44f-a709b65ae427","record_sha256":"bac21de614221ae72aafc61a24a4116821368f7592aa7bfa84fb392c49dd5656","seq":7},{"backfilled":false,"chained_at":"2026-10-11T07:17:36.994191+00:00","head":"1560ed82a829deac3273eef044f79a91c22465ab2c1859ddafbd0189824d666e","record_id":"3587fd16-9d37-4c99-9068-d98df6751cf2","record_sha256":"0f76d02da1d55b3ceaa960dba6462e93bc3852b3c91f6e0e3a407a91e61d37e2","seq":8}],"format":"oic.record-chain.v1"},"excluded":["account e-mail addresses, password hashes, sessions and recovery material","private behavior reports, notifications, bookmarks and reading state","attachments that the author did not pin into a publication snapshot","community topic metadata and Lean/verification worker queues"],"format":"oic.public-mirror.v1","generated_at":"2026-10-25T00:15:22.370737+00:00","origin":"https://eksmu.com","publications":{"events":[],"package_path":"/api/publications/export?snapshot_id={id}","snapshots":[]},"records":{"format":"oic.bundle.v1","records":[{"actor_id":"1c80c356-fc13-4289-a2e0-c14d26977067","created_at":"2026-10-07T14:51:55.862008+00:00","id":"1c80c356-fc13-4289-a2e0-c14d26977067","payload":{"alias":"Eksmu 上线测试（维护者）","key_hash":"3291a1f26f65034bc74cd081815b84c31af3ac23ecf0f3cc8a47818ae94cbc41"},"sha256":"ad255dbbcba0ab2f4c5d3e01a4803cce31dd421e30e27d03a7e38c679ca9d6c1","type":"actor"},{"actor_id":"38ccd43f-763e-4586-ac24-e7ed3c3ea076","created_at":"2026-10-08T10:14:29.259325+00:00","id":"38ccd43f-763e-4586-ac24-e7ed3c3ea076","payload":{"alias":"梁植华","key_hash":"adbc6f6cdf37b9a0a793094ba390bd9dbcb88c190e6d01ff5f7f9196124990f6"},"sha256":"9944ec8d2240c5d89bef0e4fa7e24ad713153cf11cae0810e3ad3d23221ffe64","type":"actor"},{"actor_id":"38ccd43f-763e-4586-ac24-e7ed3c3ea076","created_at":"2026-10-08T10:51:58.319127+00:00","id":"586e11fb-797a-4e24-9fb2-b23b0aeec9f4","payload":{"kind":"finding"},"sha256":"d9818abb5b42f4a74aad0b115be08aaaab70196426e456e50aaaf481663251bf","type":"exploration"},{"actor_id":"38ccd43f-763e-4586-ac24-e7ed3c3ea076","created_at":"2026-10-08T10:51:58.319175+00:00","id":"2268de50-942e-4ccc-80f3-882669ecf72c","payload":{"body":"# 概述：《π 的无理性指数等于 2》（OpenAI 数学手稿集 · 结果族 017）\n\n> **性质说明**：本文是 AI 助手（Claude）撰写的导读性概述，不是原论文，也不是同行评审意见。概述者通读了论文全文，但没有逐行核验证明，也没有运行其 Lean 形式化。下文所说的“证明”“形式化”都只是转述原作者的说法。\n\n- **原文**：*The irrationality exponent of π is 2*，OpenAI，2026 年 9 月 24 日版，共 23 页\n- **来源**：GitHub 仓库 `openai/math`，路径为 `preprints/The-irrationality-exponent-of-pi-is-2-September-24-2026/paper.pdf`（Apache-2.0 许可）\n- **作者说明**：仓库 README 称，手稿由一个未公开的 OpenAI 内部模型生成。截至 2026-10-08，目录共收 719 篇手稿，分为 372 个结果族。\n- **查阅日期**：2026-10-08\n\n## 1. 问题是什么\n\n实数 $x$ 的**无理性指数** $\\mu(x)$ 衡量有理数能把 $x$ 逼近到多近。它的定义是：使不等式\n$$0<\\left|x-\\frac{p}{q}\\right|2$，存在 $Q(\\nu)$，使得对所有整数 $p$ 和所有 $q\\ge Q(\\nu)$，都有 $|\\pi-p/q|\\ge q^{-\\nu}$。\n\n需要注意两点：\n\n- 这个结论是**不可计算（ineffective）**的：论证只说明 $Q(\\nu)$ 存在，不给出它的具体数值。\n- 指数等于 2 比“$|\\pi-p/q|\\ge c/q^2$”（等价于 π 的连分数部分商有界）要弱。论文没有声称后者。\n\n**推论 1.2（Flint–Hills 级数）。** 级数 $\\sum_{n\\ge1}\\dfrac{1}{n^3\\sin^2 n}$ 收敛，其中角度以弧度计。此前 Alekseyev 证明，收敛需要 $\\mu(\\pi)\\le 5/2$；Meiburg 证明 $\\mu(\\pi)<5/2$ 就足以保证收敛。定理 1.1 满足后一个条件。\n\n**推论 5.2（推广）。** 对 $a,b>0$，级数 $\\sum n^{-a}|\\sin n|^{-b}$ 收敛当且仅当 $a>\\max\\{1,b\\}$。\n\n## 3. 证明思路\n\n整体框架是**插值行列式**（Laurent），加上类似 Roth 定理中“多个相互分离的逼近分母”的思想。证明用反证法：固定 $\\nu>2$，假设存在无穷多个满足 $|\\pi-p/q|\\le q^{-\\nu}$ 的好逼近。\n\n1. **取样。** 依次挑出 $m$ 个好逼近 $p_i/q_i$，令权重 $w_i=\\lceil\\log q_i\\rceil$，中心 $c_{ji}=2\\mathrm{i}\\,j\\,p_i/q_i$。这些中心近似于指数函数的周期 $2\\pi\\mathrm{i}\\,j$，因为 $e^{2\\pi \\mathrm{i} j}=1$。\n2. **分离权插值定理（第 2 节）。** 考虑变量 $Y,X_1,\\dots,X_m$ 的多项式，并按加权次数截断。论文证明：沿对数曲线 $Y=1+t,\\ X_i=c_{ji}+u_i+\\log(1+t)$，在 $K$ 个中心处，可以同时实现任意指定的 Taylor 系数包（jet）。关键在于各权重的下界**不依赖中心的位置**，因此“先定权重、再挑逼近”不会循环论证。证明分三层：\n - 局部加权重数比较（引理 2.2）；\n - 曲线不等式（命题 2.3），其中用对数微分 $dY/Y$ 的留数非零、而恰当微分的留数为零来排除障碍；\n - 在普通爆破上利用 nef、ample 和 Serre 消没定理，把曲线上的正性提升为满射。\n3. **算术下界（引理 3.1）。** 插值给出一个非零方阵子式 $\\Delta_H$。清掉分母后，它是一个非零的高斯整数，因此模长至少为 1。由此得到 $\\log|\\Delta_H|$ 的下界。\n4. **解析上界（引理 3.2–3.3，命题 3.4）。** 把各行平移到精确周期 $2\\pi \\mathrm{i}\\,j$ 处展开。展开的每一项二者必居其一：\n - 许多行的横向指标较小，那么在同一组内，重复的 Taylor 次数会使行列式项相消，带来二次节省 $c\\sum_a n_a^2$；\n - 许多行的横向指标较大，那么这些行携带逼近误差 $q_i^{-\\nu}$ 的幂次。\n\n 两种情形都会使 $|\\Delta_H|$ 很小。\n5. **选参数（第 4 节）。** 取 $K=\\lfloor C^m\\rfloor$、$w_0=B^{-m}$ 等。当维数 $m\\to\\infty$ 时，“碰撞节省”$L\\sim(B/A)^m/(2(m+1))$ 趋于无穷，而所有误差项趋于零。于是上界和下界矛盾。参数的选取顺序是关键：先固定维数，再挑逼近，最后令多项式次数 $H\\to\\infty$。\n\n第 5 节用一个简短的二进分块间距论证，从 $\\mu(\\pi)<5/2$ 推出 Flint–Hills 级数收敛。\n\n## 4. 验证状态（据仓库文档）\n\n- 仓库 `lean/docs/017.md` 称，Lean 形式化覆盖主定理：对每个 $\\nu>2$，最终下界成立，并且给出了上确界的刻画。对应的比对陈述文件是 `lean/ComparatorChallenges/PiExponent.lean`。\n- **Flint–Hills 推论不在形式化范围内。**\n- 仓库还附有该结果的推理过程摘要（`reasoning_traces/irrationality-exponent-of-pi.pdf`）。据摘要，模型先尝试证明一个低于 5/2 的上界（摘要中提到 62/25），用来解决 Flint–Hills 问题；随后以插值行列式技术为起点，转向指数恰好为 2 的结论。\n- 本概述者没有运行 Lean 检查，也无法确认形式化陈述与论文陈述是否逐字对应。\n\n## 5. 读者可关注的问题\n\n- 第 2 节的插值定理是全文最新、也最重的部分，特别是加权重数引理 2.2 和曲线不等式 2.3。它用到代数几何中的爆破与正性理论，值得专家重点审阅。\n- 这个方法看起来不依赖 π 的特殊积分表示，只用到 $e^{2\\pi \\mathrm i}=1$ 这一周期性。它对其他对数周期是否同样适用，是自然的追问。\n- 结论不可计算：它说明 $\\mu(\\pi)=2$，但没有给出显式常数。\n- 论文脚注指出 Carella 的一个相关证明中存在符号错误。论文明确说，没有使用 Carella 或 Mantzakouras–López Zapata 的结论。\n\n*本概述由 AI 撰写，仅作导读。引用请以原文为准。若发现转述错误，欢迎指出。*\n","exploration_id":"586e11fb-797a-4e24-9fb2-b23b0aeec9f4","note":"Initial version","parent_revision_id":null,"title":"未命名探索"},"sha256":"3320478ef7a33cd628bd9e57a7c08d20335311af7b18002cab6bcc41ed4feafe","type":"revision"},{"actor_id":"38ccd43f-763e-4586-ac24-e7ed3c3ea076","created_at":"2026-10-08T10:53:11.408920+00:00","id":"ca6b9401-e9e3-4079-ad53-e99f61579399","payload":{"kind":"question"},"sha256":"91478ebe006a87d80986591bd7bdf1b528fbaa79447dcae4baea7d6050714a5a","type":"exploration"},{"actor_id":"38ccd43f-763e-4586-ac24-e7ed3c3ea076","created_at":"2026-10-08T10:53:11.408965+00:00","id":"3dc2d521-7bb8-45e4-acb1-00470642e80e","payload":{"body":"\n> **性质说明**：本文是 AI 助手（Claude）撰写的导读性概述，不是原论文，也不是同行评审意见。原文共 198 页。概述者完整阅读了摘要、引言（第 1 节）和第 2 节的框架部分，其余技术章节没有逐行核验，也没有运行 Lean 形式化。文中的“证明”都只是转述原作者的说法。\n\n- **原文**：*Quasipolynomial Bounds for Arithmetic Progressions*，OpenAI，2026 年 9 月 23 日版，198 页\n- **来源**：GitHub 仓库 `openai/math`，路径为 `preprints/Quasipolynomial-Bounds-for-Arithmetic-Progressions-September-23-2026/paper.pdf`（Apache-2.0 许可）\n- **作者说明**：仓库 README 称，这些手稿由一个未公开的 OpenAI 内部模型生成，平均每个结果约用 3 小时 ChatGPT Pro 级别的思考算力。\n- **查阅日期**：2026-10-08\n\n## 1. 问题是什么\n\n**Erdős 倒数和猜想**：如果正整数集合 $A$ 满足 $\\sum_{a\\in A}1/a=\\infty$，那么 $A$ 是否一定包含任意有限长度的等差数列？素数集合就满足这个条件，所以这个猜想把 Green–Tao 定理（素数中有任意长的等差数列）推广到了所有“倒数和发散”的集合。\n\n记 $r_k(N)$ 为 $\\{1,\\dots,N\\}$ 中不含非平凡 $k$ 项等差数列的子集的最大元素个数。若要用二进分块的办法推出 Erdős 猜想，只知道 $r_k(N)=o(N)$（即 Szemerédi 定理）还不够，需要更强的条件：\n$$\\sum_{m\\ge1}\\frac{r_k(2^m)}{2^m}<\\infty .$$\n\n已知进展（据论文第 1.2 节）：\n\n- **$k=3$**：经过 Roth、Heath-Brown、Szemerédi、Bourgain、Sanders、Bloom 等人的工作，Bloom–Sisask 首先越过了可和性门槛，解决了 3 项情形的倒数和猜想。随后 Kelley–Meka 得到 $r_3(N)\\ll N\\exp(-c(\\log N)^{1/12})$，后续又被改进到指数 $1/9$ 和 $1/6-o(1)$。\n- **一般 $k$**：Gowers 证明 $r_k(N)\\ll N/(\\log\\log N)^{c_k}$；Green–Tao 得到 $r_4$ 的多对数界；Leng–Sah–Sawhney 证明 $r_k(N)\\ll N\\exp(-(\\log\\log N)^{c_k})$。这些界的节省量都只体现在 $\\log\\log N$ 上，不足以推出二进可和性。\n\n## 2. 论文声称的结果\n\n**定理 1.1。** 对每个固定的 $k\\ge3$，存在常数 $C_k,c_k,\\varepsilon_k>0$，使得\n$$r_k(N)\\le C_k\\,N\\exp\\!\\big(-c_k(\\log N)^{\\varepsilon_k}\\big).$$\n等价的说法是：只要 $\\log N\\ge A_k(2+\\log(1/\\alpha))^{A_k}$，密度为 $\\alpha$ 的子集就一定包含 $k$ 项等差数列。也就是说，所需区间长度是 $1/\\alpha$ 的**拟多项式**函数。\n\n**推论 1.2（Erdős 猜想）。** 倒数和发散的正整数集合包含任意有限长度的等差数列。从定理 1.1 推出这一点只需对二进区间 $[2^m,2^{m+1})$ 求和，因为 $\\sum_m e^{-c m^{\\varepsilon}}<\\infty$。\n\n**其他推论（第 1.1、1.4、11 节）：**\n\n- 更强的发散判据：对任意固定的 $B\\ge0$，只要 $\\sum_{a\\in A}(\\log(2+a))^B/a=\\infty$，结论仍然成立。\n- 由此重新得到 Green–Tao 关于素数正相对密度子集的定理。\n- van der Waerden 数的上界：$W_r(k)\\le\\exp\\!\\big(A_k(2+\\log r)^{A_k}\\big)$，即对固定的 $k$，它关于颜色数 $r$ 是拟多项式的。同一手稿族中的另一篇论文给出了超多项式下界。\n\n论文明确说明：指数 $\\varepsilon_k$ 没有经过优化，对 $k=3$ 也没有声称改进已知结果。\n\n## 3. 证明思路\n\n主线是经典的**密度增量法**：如果集合中等差数列“太少”，就能在某个更有结构的子区域上找到更高的密度；不断重复，直到密度超过 1，得出矛盾。难点在于**代价核算**。密度每次只能按固定倍数提升，所以最多迭代 $O_k(1+\\log(1/\\alpha))$ 次。要得到定理 1.1，所有迭代累计的对数损失必须是 $\\log(1/\\alpha)$ 的多项式。\n\n论文的处理方式是：\n\n1. **三角多项式胞腔（第 2 节）。** 每一步所在的区域由一串整数块 $b_1,\\dots,b_D$ 依次确定，约束形如\n$$\\|b_h-C_h(u,b_{ 根据 OpenAI 数学预印本 *A Polynomial-Time 2-Approximation for Shortest Common Superstring* 整理。以下是论文的中文导读与证明结构概述，并非逐段翻译。\n\n- **作者：** OpenAI（按仓库页面所列）\n- **日期：** 2026 年 9 月 24 日\n- **原文：** [论文 PDF](https://github.com/openai/math/blob/main/preprints/A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring-September-24-2026/paper.pdf)\n- **仓库目录：** [preprints 条目](https://github.com/openai/math/tree/main/preprints/A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring-September-24-2026)\n\n## 问题与主要结论\n\n给定有限字符串集合 $S$，要找一个最短字符串 $T$，使每个输入串都作为连续子串出现在 $T$ 中。记最优长度为 $\\operatorname{OPT}(S)$。论文构造了一个确定性多项式时间算法，输出公共超串 $T$，满足\n\n$$\n|T| \\le 2\\operatorname{OPT}(S).\n$$\n\n这里的保证针对论文新构造的算法；论文没有证明经典的“每次合并最大重叠字符串”的 Greedy 算法达到 2-近似。\n\n## 核心想法\n\n证明分成两件事：先从输入中造出一个长度至多最优解的“基础图”，再以不超过同等长度的额外代价把图连通。最终把连通平衡图的欧拉回路读成一个公共超串。\n\n### 1. 用子串出现次数造出下界\n\n先删去空串、重复串和被其他输入串包含的串；这不会改变可行解。令 $V$ 为输入串的所有不同子串以及空串组成的集合。算法按字符串长度从长到短，为每个非空 $s\\in V$ 计算整数计数 $m(s)$。主要约束是\n\n$$\nm(s)\\ge\\sum_{c\\in\\Sigma}m(cs),\\qquad\nm(s)\\ge\\sum_{c\\in\\Sigma}m(sc),\n$$\n\n并要求每个输入串的计数至少为 1。直观上，一个较长子串的计数不能超过其左扩展或右扩展计数之和所允许的范围。\n\n论文还加入一类周期性约束。对周期文本 $A$，若长词 $v$ 是周期文本的一段，且其前缀 $w$ 比 $v$ 短了 $k$ 个周期，那么当 $v$ 的计数中存在没有被“括定词”解释的出现时，规则会要求 $w$ 至少多出 $k+1$ 个相应计数。括定词是指：中间匹配周期文本的一段，两端各紧邻一个不匹配字符。这个规则补足了普通左右扩展约束可能漏掉的周期重复信息。\n\n关键引理证明，对任意公共超串 $T$，都有 $m(s)\\le N_T(s)$，其中 $N_T(s)$ 是 $s$ 在 $T$ 中的出现次数。因此\n\n$$\nW:=\\sum_{c\\in\\Sigma}m(c)\\le \\operatorname{OPT}(S).\n$$\n\n也就是说，$W$ 是可计算的最优长度下界。\n\n### 2. 把计数编码成平衡有向图\n\n图的顶点是 $V$ 中的子串。对每个非空词 $s$，放入两类边：从删去末字符的前缀指向 $s$ 的“上行边”，以及从 $s$ 指向删去首字符的后缀的“下行边”。分别赋予适当的非负整数重数，使每个顶点的入度等于出度。\n\n这样得到的基础图具有三个性质：\n\n- 每个输入串都是图中被使用的顶点；\n- 图是平衡的；\n- 上行边总数和下行边总数都恰为 $W$。\n\n由于图可能分成多个连通分量，还需要把它们连起来。若能以最多 $W$ 条额外上行边的代价连接到空串，整体代价就至多为 $2W\\le 2\\operatorname{OPT}(S)$。\n\n### 3. 周期层与组件连接\n\n基础图的边可分解为闭游走。沿闭游走记录上行边追加的字符，并在两侧无限重复，就得到周期文本。论文把同一周期文本（允许平移）的游走重新排序成“层”：每层在一个最小周期内前进，周期为 $p$ 的层花费恰为 $p$。给每层再分配 $p$ 的连接预算；所有层预算总和正好是 $W$。\n\n论文接下来用实际出现的子串窗口作为接触点，设计若干种连接操作：\n\n- 同一周期文本中的有序层可一起连接，费用由层预算承担；\n- 不同周期文本若在某个窗口上吻合，可将源层接到目标层；\n- 某些连接请求延后到较长周期的目标组处理，以避免重复使用目标预算。\n\n按周期长度递增处理这些层组后，尚未完成的连接可表示为每个块最多指向一个目标块的有向图。若出现有向环，论文选择字典序最大的周期旋转来保留一条连接，并省略另一条出边。周期性比较引理保证保留的连接能提供一个长度不超过目标周期 $q$ 的短接触词；省下的 $q$ 预算足以将其连回空串。这样每个层的连接预算最多使用一次，总额仍不超过 $W$。\n\n这一部分是证明的技术核心：周期文本的对齐、窗口排序和字典序极大旋转共同保证连接时既能找到真实图顶点，也能把额外长度控制在预算内。\n\n### 4. 从欧拉回路得到超串\n\n连接完成后，得到包含空串、连通且平衡的有向多重图。对它取从空串出发的欧拉回路：每经过上行边就把对应字符追加到输出；下行边不追加字符。每个图顶点在回路中被访问，特别是所有输入串都出现为输出串的子串。输出长度等于上行边数，不超过\n\n$$\nW+W=2W\\le 2\\operatorname{OPT}(S).\n$$\n\n论文还通过显式枚举子串、有限个周期模板、图边和窗口，说明计数、重排、连接与欧拉回路构造均可在输入编码长度的多项式时间内完成。\n\n## 一个小例子：单个重复字符\n\n若唯一必需的输入串为 $a^h$，仅靠左右扩展约束可能只给每个前缀计数 1，导致基础图低估重复字符所需的长度。周期性规则会对常值周期文本 $A=\\ldots aaa\\ldots$ 起作用，强制前缀 $a^j$ 的计数至少为 $h-j+1$。因此 $W=h$，与最优超串长度一致。这个例子说明额外周期规则为何必要。\n\n## 贡献与边界\n\n论文给出最短公共超串问题的一个确定性多项式时间 2-近似算法，回答了“是否存在多项式时间 2-近似”这一存在性问题。结果本身不意味着算法容易实现：证明中的计数规则、层分解和环处理都较复杂。论文也明确区分了“存在一个达到因子 2 的算法”和“某个经典贪心过程达到因子 2”。\n\n## 引用\n\n```bibtex\n@misc{OAI:A-Polynomial-Time-2-Approximation-for-Shortest-Common-Superstring-September-24-2026,\n author = {{OpenAI}},\n title = {{A Polynomial-Time 2-Approximation for Shortest Common Superstring}},\n year = {2026},\n howpublished = {OpenAI Math Release preprint}\n}\n```\n","exploration_id":"6d5e4fa2-4ed3-41e1-a44f-a709b65ae427","note":"Initial version","parent_revision_id":null,"title":"最短公共超串的多项式时间 2-近似算法"},"sha256":"0f76d02da1d55b3ceaa960dba6462e93bc3852b3c91f6e0e3a407a91e61d37e2","type":"revision"}],"sha256":"ed81ad7cd9a7a5132b2c2093761c27b0004d16213ed1653eb66af31869f70209"},"signatures":null}