定权项链的逆余字典序通用循环
Reverse-Colexicographic Universal Cycles for Fixed-Weight Necklaces
研究概述
将仅相差循环旋转的单词归为一个项链。对长度与各位总和固定的非负整数单词，本文构造一个循环序列，使每个删去末位后的合法单词恰好出现一次。文章证明 Campbell–Janik-Jones–Sawada 猜想 8：按从末位开始比较的逆余字典序，连接各项链的最短重复块，所得循环正是原题指定的缺符号后继循环。生成每个符号的均摊时间为常数，辅助空间与单词长度成正比。证明还适用于在“将第一个正坐标的一单位移至下一坐标”操作下封闭的家族，包括对规范代表的前缀和施加限制的情形。论文包含完整数学证明，尚未形式化。
原始公开问题
Campbell–Janik-Jones–Sawada 关于逆余字典序通用循环的猜想 8
Colin Campbell, Luke Janik-Jones and Joe Sawada, Universal cycle constructions for k-subsets and k-multisets — Section 3.2, Conjecture 8 and the displayed h2 successor
原文摘要（英文）
A fixed-sum word is determined by all but its final symbol. Campbell, Janik-Jones and Sawada constructed universal cycles for these shorthand words and conjectured a reverse-colexicographic necklace concatenation description. We prove that description and generate the cycle in constant amortized time per symbol using space linear in the word length. The argument uses the binary tree obtained by moving one unit from the first positive coordinate to the next coordinate. Every parent in this tree is aperiodic. We join the rotation cycles by exchanging the successors of two words that agree after their first symbol; this gives the stated concatenation and the prescribed successor rule. The same proof applies to every family closed under this transfer, including families whose lexicographically least representatives satisfy upper bounds on their prefix sums.
数学审核
稿件已完成内部审核，当前公开版本尚未完成完整形式化。
审核标准