Reverse-Colexicographic Universal Cycles for Fixed-Weight Necklaces
Overview
Words that differ only by cyclic rotation form a necklace. For nonnegative integer words of fixed length and sum, this paper constructs a circular sequence containing every admissible word with its final symbol omitted exactly once. It proves Campbell–Janik-Jones–Sawada Conjecture 8: concatenating the shortest repeating blocks in reverse colexicographic order, which compares words from their last coordinate, gives the prescribed missing-symbol successor cycle. Generation takes constant amortized time per symbol and space linear in the word length. The proof also covers families closed under moving one unit from the first positive coordinate to the next, including canonical-prefix sum restrictions. The complete proofs have not yet been formalized.
Original public questions
Campbell–Janik-Jones–Sawada Conjecture 8 on reverse-colex universal cycles
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
Original abstract (English)
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.
Mathematical review
The manuscript has completed internal review. Complete formalization is not yet established for this public version.
Review standard