固定重みネックレスの逆余辞書式普遍サイクル
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.
数学の検証
原稿は内部レビューを完了しています。この公開版の完全な形式化は、まだ確立されていません。
検証基準