Reverse-Colexicographic Universal Cycles for Fixed-Weight Necklaces

Abstract

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. This version presents complete mathematical proofs. These proofs have not yet been formalized in a proof assistant. Formal verification is planned; under the author's verification standard, this version is archived as a dated preprint, with active promotion of its results deferred until formal verification is complete. First publicly available on 9 September 2026 through the GitHub paper archive. This Zenodo deposit mirrors the unchanged first-release PDF; the archive date does not date a new mathematical result.