arxiv: 2605.09489 · v1 · submitted 2026-05-10 · 🧮 math.CO

Recognition: 1 theorem link

· Lean Theorem

SB(3,n) has no Hamiltonian cycle when n is even: a sign-of-permutation proof, with extension to all odd mequiv 3pmod 4

Shisheng Li

Pith reviewed 2026-05-12 04:29 UTC · model grok-4.3

classification 🧮 math.CO

keywords Hamiltonian cyclesign of permutationdigraphBurnside lemmadihedral groupSB(3,n)choice setKnuth exercise

0 comments

The pith

SB(3,n) has no Hamiltonian cycle for even n, shown by a sign-of-permutation obstruction that extends to SB(m,n) for odd m ≡ 3 mod 4.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the digraph SB(3,n) admits no Hamiltonian cycle whenever n is even. Any candidate cycle induces a successor map f_S equal to the composition of a fixed base map A_b with a permutation sigma coming from the choice set S. When m is odd the base map A_b contributes sign +1, so the sign of f_S equals the sign of sigma. A short Burnside count over the dihedral group shows that sigma always has sign -1 for even n, which cannot equal the +1 required for a single cycle of length 3^n. The identical sign mismatch rules out Hamiltonian cycles in SB(m,n) for every odd m congruent to 3 modulo 4 and even n, thereby restricting the residue classes in which existence can hold.

Core claim

Writing the successor map of a candidate Hamiltonian cycle as f_S = A_b ∘ σ, sgn(A_b) = +1 when m is odd, so sgn(f_S) = sgn(σ) for every choice set S. A short dihedral Burnside computation shows sgn(σ) = -1 on Σ_3^n for even n, contradicting the sign +1 required of a single 3^n-cycle. The same argument gives the stronger statement that SB(m,n) has no Hamiltonian cycle whenever m is odd with m ≡ 3 (mod 4) and n is even.

What carries the argument

The successor map expressed as the composition f_S = A_b ∘ σ, whose sign is forced to equal sgn(σ) for odd m, together with the dihedral Burnside count that fixes sgn(σ) = -1 for even n.

If this is right

SB(3,n) contains no Hamiltonian cycle for any even n.
SB(m,n) contains no Hamiltonian cycle whenever m is odd, m ≡ 3 mod 4, and n is even.
Knuth's suggested existence of Hamiltonian cycles in SB(m,n) for m > 3 and n > 2 can hold only outside the excluded residue classes.
The sign obstruction applies uniformly to every choice set S and does not depend on the particular selection of representatives.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

When m is even or m ≡ 1 mod 4 the sign of A_b may become negative, potentially removing the obstruction and allowing cycles for even n.
The same composition-plus-Burnside technique could be applied to other wreath-product digraphs whose base maps have known signs.
For small even n the absence can be verified by exhaustive enumeration of the finitely many choice sets.

Load-bearing premise

That the base map A_b has sign +1 whenever m is odd and that the dihedral Burnside computation correctly establishes sgn(σ) = -1 for every choice set S when n is even.

What would settle it

An explicit choice set S for SB(3,2) whose induced permutation σ has positive sign, or a direct construction of a Hamiltonian cycle in SB(3,2).

read the original abstract

We resolve exercise 7.2.2.4--224 of Knuth's Pre-Fascicle 8a (10 April 2026 draft, rated [46]): the digraph $\mathit{SB}(3,n)$ has no Hamiltonian cycle when $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 \circ \sigma$, $\operatorname{sgn}(A_b)=+1$ when $m$ is odd, so $\operatorname{sgn}(f_S)=\operatorname{sgn}(\sigma)$ for every choice set $S$. A short dihedral Burnside computation shows $\operatorname{sgn}(\sigma)=-1$ on $\Sigma_3^n$ for even $n$, contradicting the sign $+1$ required of a single $3^n$-cycle. The same argument gives the stronger statement that $\mathit{SB}(m,n)$ has no Hamiltonian cycle whenever $m$ is odd with $m\equiv 3\pmod 4$ and $n$ is even; this restricts the residue classes in which Knuth's hint to Ex.~225 (existence of Hamiltonian cycles in $\mathit{SB}(m,n)$ for all $m>3$ and $n>2$) can hold.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper resolves Knuth's exercise by proving SB(3,n) has no Hamiltonian cycle for even n via a sign obstruction, and extends the non-existence to SB(m,n) for odd m ≡ 3 mod 4.

read the letter

The paper gives a sign-of-permutation proof that SB(3,n) has no Hamiltonian cycle for even n, resolving an exercise in Knuth, and extends the result to SB(m,n) when m is odd and m ≡ 3 mod 4. It does this by writing the successor map as f_S = A_b ∘ σ, noting that sgn(A_b) is +1 for odd m, so sgn(f_S) equals sgn(σ). Then a Burnside count over the dihedral group shows sgn(σ) = -1 when n is even, which can't be for a 3^n-cycle that must have sign +1. This is new because it fills in the proof for the exercise and provides the stronger statement that restricts where Knuth's hinted existence results can apply. The approach is direct and uses basic group theory without extra machinery. The argument looks solid on the surface. The central assumptions are that sgn(A_b)=+1 and that the Burnside computation correctly gives the negative sign for sigma. The stress test notes no internal inconsistency, and the abstract presents it as short verifications, so it probably holds up. One minor thing to check is the exact definition of the sets and maps in the full paper, but nothing suggests a flaw in the logic. This work is for combinatorial graph theorists or anyone tackling Knuth's exercises. A reader looking for explicit non-existence proofs in small cases would find it useful. It deserves to go to peer review because it provides a complete, self-contained proof for a specific open question.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that the digraph SB(3,n) has no Hamiltonian cycle when n is even via a sign-of-permutation obstruction. It decomposes the successor map of any candidate cycle as f_S = A_b ∘ σ, notes that sgn(A_b) = +1 for odd m, and applies a short dihedral Burnside computation to show sgn(σ) = -1 for every choice set S on Σ_3^n when n is even; this contradicts the requirement that sgn(f_S) = +1 for a 3^n-cycle. The argument extends directly to show that SB(m,n) has no Hamiltonian cycle for any odd m ≡ 3 (mod 4) and even n.

Significance. If the central argument holds, the result cleanly resolves Knuth exercise 7.2.2.4--224 and supplies a uniform combinatorial obstruction (via the sign homomorphism and Burnside averaging over the dihedral group) that restricts the residue classes in which Hamiltonian cycles can exist in the SB(m,n) family. The proof uses only standard tools, contains no free parameters or ad-hoc constructions, and yields an explicit, falsifiable statement about non-existence.

minor comments (2)

The precise definition of the set Σ_3^n and the explicit action of the dihedral group elements on choice sets S should be stated in the opening paragraph of the proof (rather than left implicit from the abstract) to facilitate immediate verification of the Burnside count.
The manuscript should include a one-sentence reminder of the sign-multiplicativity property used for f_S = A_b ∘ σ, even though it is standard, to make the contradiction step self-contained for readers outside permutation-group combinatorics.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for the positive recommendation to accept. The summary accurately captures the sign-of-permutation obstruction and its extension to the indicated residue classes of m.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central argument applies the sign homomorphism property of the symmetric group (sgn(f_S) = sgn(A_b) * sgn(sigma)) together with an explicit Burnside count over the dihedral group action on Sigma_m^n to obtain sgn(sigma) = -1 for even n. Both ingredients are standard external facts from group theory and are verified directly on the finite sets in question; neither is defined in terms of the target non-existence result, fitted to data, nor justified by self-citation. The contradiction with the required sign +1 of a 3^n-cycle (odd length) follows immediately without intermediate parameters or renamings. The extension to m ≡ 3 mod 4 likewise rests only on the parity of m determining sgn(A_b) = +1, again a direct verification. No load-bearing step reduces to its own input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof invokes only standard facts from group theory; no free parameters are fitted and no new entities are postulated.

axioms (2)

standard math The sign map is a group homomorphism from the symmetric group to {+1, -1}.
Used to equate sgn(f_S) with sgn(sigma) once sgn(A_b) is known.
standard math Burnside's lemma computes the average number of fixed points under a group action, here applied to signs under the dihedral action.
Invoked for the short computation that determines sgn(sigma) on Sigma_3^n.

pith-pipeline@v0.9.0 · 5557 in / 1606 out tokens · 60920 ms · 2026-05-12T04:29:47.188332+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear
sgn(f_S) = sgn(σ) ... dihedral Burnside computation shows sgn(σ)=-1 ... N(n,m) is even (Lemma 10)

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

[1]

A simple combinatorial algorithm for de Bruijn sequences,

Abbas Alhakim, “A simple combinatorial algorithm for de Bruijn sequences,”American Mathematical Monthly117(2010), 728–732

work page 2010
[2]

A combinatorial problem,

N. G. de Bruijn, “A combinatorial problem,”Koninklijke Nederlandse Akademie van Wetenschappen, Proc.49(1946), 758–764

work page 1946
[3]

Circuits and trees in oriented linear graphs,

T. van Aardenne-Ehrenfest and N. G. de Bruijn, “Circuits and trees in oriented linear graphs,”Simon Stevin28(1951), 203–217

work page 1951
[4]

Tuvi Etzion,Sequences and the de Bruijn Graph: Properties, Constructions, and Applications, Academic Press / Elsevier, 2024

work page 2024
[5]

Algorithms for the generation of full-length shift-register sequences,

Tuvi Etzion and Abraham Lempel, “Algorithms for the generation of full-length shift-register sequences,”IEEE Transactions on Information Theory30(1984), 480–484

work page 1984
[6]

A survey of full length nonlinear shift register cycle algorithms,

Harold Fredricksen, “A survey of full length nonlinear shift register cycle algorithms,”SIAM Review24(1982), 195–221

work page 1982
[7]

Necklaces of beads in k colors and k-ary de Bruijn sequences,

Harold Fredricksen and James Maiorana, “Necklaces of beads in k colors and k-ary de Bruijn sequences,”Discrete Mathematics23(1978), 207–210

work page 1978
[8]

A successor rule framework for constructing k-ary de Bruijn sequences and universal cycles,

Daniel Gabric, Joe Sawada, Aaron Williams, and Dennis Wong, “A successor rule framework for constructing k-ary de Bruijn sequences and universal cycles,”IEEE Transactions on Information Theory66(2020), 679–687

work page 2020
[9]

Golomb,Shift Register Sequences, Holden-Day, San Francisco, 1967; revised edition, Aegean Park Press, Laguna Hills, 1982

Solomon W. Golomb,Shift Register Sequences, Holden-Day, San Francisco, 1967; revised edition, Aegean Park Press, Laguna Hills, 1982

work page 1967
[10]

Normal recurring decimals,

I. J. Good, “Normal recurring decimals,”Journal of the London Mathematical Society21(1946), 167–169

work page 1946
[11]

On the classification of de Bruijn sequences,

Erik R. Hauge and Johannes Mykkeltveit, “On the classification of de Bruijn sequences,”Discrete Mathematics148(1996), 65–83. 7

work page 1996
[12]

Knuth,The Art of Computer Programming, Volume 4, Pre-Fascicle 8a: Generating All Compositions and Subroutines for Combinatorial Searches(draft of 10 April 2026)

Donald E. Knuth,The Art of Computer Programming, Volume 4, Pre-Fascicle 8a: Generating All Compositions and Subroutines for Combinatorial Searches(draft of 10 April 2026). PDF: https://cs.stanford.edu/~knuth/fasc8a.pdf; PostScript:https://cs.stanford.edu/ ~knuth/fasc8a.ps.gz. Exercises 7.2.2.4–223, 7.2.2.4–224, 7.2.2.4–225

work page 2026
[13]

On a homomorphism of the de Bruijn graph and its applications to the design of feedback shift registers,

Abraham Lempel, “On a homomorphism of the de Bruijn graph and its applications to the design of feedback shift registers,” IEEE Transactions on ComputersC-19(1970), 1204–1209

work page 1970
[14]

A proof of Golomb’s conjecture for the de Bruijn graph,

Johannes Mykkeltveit, “A proof of Golomb’s conjecture for the de Bruijn graph,”Journal of Combinatorial Theory, Series B13(1972), 40–45

work page 1972
[15]

Number of n-bead necklaces with 3 colors,

N. J. A. Sloane et al.,The On-Line Encyclopedia of Integer Sequences, sequence A001867: “Number of n-bead necklaces with 3 colors,”https://oeis.org/A001867

work page
[16]

A simple shift rule for k-ary de Bruijn sequences,

Joe Sawada, Aaron Williams, and Dennis Wong, “A simple shift rule for k-ary de Bruijn sequences,”Discrete Mathematics 340(2017), 524–531. 8

work page 2017