𝑆𝐵 ( 3 , n ) \mathit{SB}(3,n) has no Hamiltonian cycle when n n is even A sign-of-permutation proof, with extension to all odd m ≡ 3 ( mod 4 ) m\equiv 3\pmod{4}
Shisheng Li · 2026
Read 𝑆𝐵 ( 3 , n ) \mathit{SB}(3,n) has no Hamiltonian cycle when n n is even A sign-of-permutation proof, with extension to all odd m ≡ 3 ( mod 4 ) m\equiv 3\pmod{4} by Shisheng Li (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-09489.txt.
Introduction
Li resolves exercise 7.2.2.4–224 of Knuth's Pre-Fascicle 8a, research-rated, showing SB(3,n) lacks a Hamiltonian cycle for even n. The proof turns on a sign-of-permutation argument. Writing the successor map of a candidate cycle as fS equals Ab composed with sigma, the sign of Ab is plus 1 when m is odd. So the sign of fS equals the sign of sigma for every S. A dihedral Burnside computation shows the sign of sigma is minus 1 on 3-to-the-n strings for even n, contradicting the sign plus 1 required of a 3-to-the-n cycle.
That yields the claim that SB(m,n) lacks a Hamiltonian cycle whenever m is odd with m congruent to 3 mod 4 and n is even. That restricts the residue classes where Knuth's hint to exercise 225, on Hamiltonian cycles in SB(m,n) for m greater than 3 and n greater than 2, can hold.
Catalog record
| CREATOR | Shisheng Li |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.09489
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
𝑆𝐵 ( 3 , n ) \mathit{SB}(3,n) has no Hamiltonian cycle when n n is even A sign-of-permutation proof, with extension to all odd m ≡ 3 ( mod 4 ) m\equiv 3\pmod{4} Thanks: Resolution of Exercise 7.2.2.4–224 in D. E. Knuth, The Art of Computer Programming , Volume 4, Pre-Fascicle 8a (draft of 10 April 2026) [ 12 ] . Knuth ranks problem difficulty on a 0–50 scale; [46] denotes a research-level problem. Shisheng Li Abstract We resolve exercise 7.2.2.4–224 of Knuth’s Pre-Fascicle 8a (10 April 2026 draft, rated [46]): the digraph 𝑆𝐵 ( 3 , n ) \mathit{SB}(3,n) has no Hamiltonian cycle when n n is even. The argument is a sign-of-permutation obstruction. Writing the successor map of a candidate Hamiltonian cycle as f S = A b ∘ σ f_{S}=A_{b}\circ\sigma (Definition 4 ), sgn ( A b ) = + 1 \operatorname{sgn}(A_{b})=+1 when m m is odd, so sgn ( f S ) = sgn ( σ ) \operatorname{sgn}(f_{S})=\operatorname{sgn}(\sigma) for every choice set S S . A short dihedral Burnside computation shows sgn ( σ ) = − 1 \operatorname{sgn}(\sigma)=-1 on Σ 3 n \Sigma_{3}^{n} for even n n , contradicting the sign + 1 +1 required of a single 3 n 3^{n} -cycle. The same argument gives the stronger statement that 𝑆𝐵 ( m , n ) \mathit{SB}(m,n) has no Hamiltonian cycle whenever m m is odd with m ≡ 3 ( mod 4 ) m\equiv 3\pmod{4} and n n is even; this restricts the residue classes in which Knuth’s hint to Ex. 225 (existence of Hamiltonian cycles in 𝑆𝐵 ( m , n ) \mathit{SB}(m,n) for all m > 3 m>3 and n > 2 n>2 ) can hold. MSC2020: 05C45 (Eulerian and Hamiltonian graphs); 05A05 (Permutations, words, matrices); 20B30 (Symmetric groups); 94A55 (Shift register sequences and sequences over finite alphabets). Keywords: Hamiltonian cycle, de Bruijn cycle, shift register, necklace, Burnside lemma, sign of a permutation, TAOCP exercise. 1 Knuth’s exercise: definitions and current status 1.1 The digraph \mathit{SB}(m,n) (Ex. 223) Definition 1 (Knuth, Ex. 7.2.2.4–223) . Let m,n\geq 1 be integers, and let \Sigma=\Sigma_{m}=\{0,1,\dots,m-1\} . The shift-and-save-or-bump digraph \mathit{SB}(m,n) has vertex set \Sigma^{n} and arcs (save) \displaystyle x_{1}x_{2}\dots x_{n}\;\longrightarrow\;x_{2}\dots x_{n}\,x_{1}, (bump) \displaystyle x_{1}x_{2}\dots x_{n}\;\longrightarrow\;x_{2}\dots x_{n}\,x_{1}^{+},\hskip 20.00003ptx_{1}^{+}:=(x_{1}+1)\bmod m. There is a self-loop at x iff x_{1}=x_{2}=\dots=x_{n} (then the save arc returns to x ; the bump does not). Every vertex has in-degree 2 and out-degree 2 (Ex. 223a). In particular, \mathit{SB}(m,n) is a 2 -regular subdigraph of the full m -ary de Bruijn digraph, which is itself m -regular and is well known to be Hamiltonian for all m,n\geq 1 (Good [ 10 ] and de Bruijn [ 2 ] for m=2 ; the m -ary case is folklore, traceable to van Aardenne-Ehrenfest and de Bruijn [ 3 ] ). The structural surprise of this paper is that, although the larger de Bruijn digraph is Hamiltonian in abundance, the restriction to the \{ save, bump \} pair of out-arcs is sharp enough to forbid Hamiltonicity for m\equiv 3\pmod{4} and even n . Knuth’s pre-fascicle records the following facts and questions about \mathit{SB}(m,n) . • Ex. 223(b). Hamiltonian cycles of \mathit{SB}(m,n) correspond naturally to m -ary de Bruijn cycles of length m^{n} ; the correspondence is one-to-one for m=2 and many-to-one for m\geq 3 . • Ex. 223(c). \mathit{SB}(m,2) has no Hamiltonian cycle for m>2 . • Ex. 223(d). \mathit{SB}(3,3) has the Hamiltonian cycle \texttt{(000100201202210211011121222)}, meaning 000\to 001\to 010\to\dots\to 222\to 220\to 200\to 000 . • Ex. 223(e) — the choice-set reformulation . If C is a Hamiltonian cycle of \mathit{SB}(m,n) , then there is a unique S\subseteq\Sigma^{n-1} such that x_{1}\dots x_{n}\to x_{2}\dots x_{n}x_{1}\in C iff x_{2}\dots x_{n}\in S . (Proof, writing x_{1}^{-}:=(x_{1}-1)\bmod m : if the save arc out of x_{1}y is in C , then it has the same target as the bump arc out of x_{1}^{-}\,y ; that bump arc is therefore not in C , so the save arc out of x_{1}^{-}\,y must be. Iterating shows that whether to save depends only on the suffix y .) • Ex. 223(f). The numbers of Hamiltonian cycles of \mathit{SB}(m,3) for 2\leq m\leq 7 are 2,\;12,\;88,\;7510,\;675714,\;459086712. 1.2 Ex. 224 and Knuth’s progress The research-level problem we solve is: Ex. 224 [46]. Prove or disprove: \mathit{SB}(3,n) has no Hamiltonian cycles when n is even. The corresponding answer in the pre-fascicle reads, in full: Algorithm B proves this when n=4 . But its search tree even in that small case has 3 million nodes; there’s no evident way to rule out tons of feasible near-solutions. So the case n=4 is the only one that has been verified, via Knuth’s Algorithm B, whose search tree at n=4 already has \sim 3 million nodes. Knuth records no structural argument and explicitly notes the absence of one. The cases n=6 (729 vertices, 2^{240}\sim 10^{72} valid choice sets after the no-self-loop pruning) and beyond are open in the literature. To the best of the author’s knowledge, no preprint or publication on the question beyond Knuth’s pre-fascicle has appeared at the time of submission, although the author is aware of independent unpublished investigations and has corresponded with the relevant parties. The companion problem Ex. 225 asks for a construction of a Hamiltonian cycle in \mathit{SB}(m,3) for every m>1 , with the answer adding the broader hint “ More generally, construct one in \mathit{SB}(m,n) for all m>3 and n>2 . ” For the constructive side, k -ary de Bruijn shift rules in the spirit of Fredricksen–Maiorana [ 7 ] , Alhakim [ 1 ] , Sawada–Williams–Wong [ 16 ] , and the successor-rule framework of Gabric–Sawada–Williams–Wong [ 8 ] provide existence in the de Bruijn graph; what distinguishes the \mathit{SB}(m,n) Hamiltonicity question is the constraint that the feedback function takes only the values \{0,1\} rather than the full \Sigma_{m} . 2 Reformulation as an FSR sign problem By Ex. 223(e), the search for a Hamiltonian cycle of \mathit{SB}(m,n) reduces to choosing a suitable subset S\subseteq\Sigma^{n-1} . We package this into a function b\colon\Sigma^{n-1}\to\{0,1\},\hskip 20.00003ptb(y)=[y\notin S], and the resulting successor map f_{S}\colon\Sigma^{n}\to\Sigma^{n},\hskip 20.00003pt(x_{1},\dots,x_{n})\;\longmapsto\;\bigl(x_{2},\dots,x_{n},\;x_{1}+b(x_{2},\dots,x_{n})\bmod m\bigr). (1) The map f_{S} is invertible: given (y_{1},\dots,y_{n}) , the unique pre-image is (y_{n}-b(y_{1},\dots,y_{n-1}),\,y_{1},\dots,y_{n-1}) . Hence f_{S} is a permutation of \Sigma^{n} , i.e. an element of the symmetric group \operatorname{Sym}(\Sigma^{n}) — by which we always mean the group of all bijections \Sigma^{n}\to\Sigma^{n} under composition. The Hamiltonian-cycle problem is now compact: Proposition 2 . \mathit{SB}(m,n) has a Hamiltonian cycle if and only if there exists b\colon\Sigma^{n-1}\to\{0,1\} such that f_{S} is a single m^{n} -cycle in \operatorname{Sym}(\Sigma^{n}) . This is the standard nonsingular feedback-shift register viewpoint (Golomb [ 9 ] ; see also Lempel [ 13 ] , Etzion–Lempel [ 5 ] , and Fredricksen’s survey [ 6 ] ): if (s_{k})_{k\geq 0} is the periodic sequence of first coordinates of the cycle vertices — so that f_{S}^{\,k}(v_{0})=(s_{k},s_{k+1},\dots,s_{k+n-1}) for every k — then the recurrence generating (s_{k}) is s_{k+n}=s_{k}+b(s_{k+1},\dots,s_{k+n-1})\bmod m. The constraint that b takes values in \{0,1\} (rather than the full \Sigma_{m} ) is what distinguishes \mathit{SB}(m,n) Hamiltonian cycles from arbitrary m -ary de Bruijn cycles; in FSR language, b is a binary-valued feedback function on an m -ary register. Such sign-of-permutation arguments