Interesting Esoterica

Fibbinary Zippers in a Monoid of Toroidal Hamiltonian Cycles that Generate Hilbert-Style Square-Filling Curves

Article by Douglas M. McKenna
  • Published in 2022
  • Added on
Within the recursive subdivision of the \(n \times n\) square, what characterizes a Hilbert-style space-filling curve motif of length \(n^2\) when—under iterated, self-similar, pure edge-replacement—a sequence of always self-avoiding lattice paths results? How many motifs are there and what do they look like? Such motifs are composable elements of a monoid, where all such motifs map to a particular subset of Hamiltonian cycles on the \(n \times n\) toroidal grid-graph. We prove that for any odd \(n \geq 1\) each motif has a shape that falls into exactly one of \(F_{(n−3)/2}\) boundary “zipping” modes, where \(F_i\) is the \(i\)th Fibonacci number; for even \(n\) no solution motifs exist. Each mode is governed by a special palindromic Fibbinary bit sequence (i.e., having no adjacent 1 bits). To varying degrees, each zipping mode emanates further combinatorial constraint inward from the square’s boundary, especially at the corners. The zipping mode whose Fibbinary bits have the most consecutive 0s freezes over half of the \(n^2\) edges of an order-\(n\) motif into only one distinct (either left- or right-handed) configuration. Manual and machine enumeration for small \(n\) is significantly enhanced by these results. For \(n = 1, 3, 5, 7, 9, 11\) there are 1, 0, 1, 7, 10101, 20305328 distinct, globally self-avoiding motifs, falling into \(F_{(n−3)/2} = 1, 0, 1, 1, 2, 3\) zipping modes, respectively. For \(n \geq 5\), each such motif, when infinitely exponentiated within its monoid, converges to an open-ended, square-filling, continuous curve.

Links


BibTeX entry

@article{FibbinaryZippers,
	title = {Fibbinary Zippers in a Monoid of Toroidal Hamiltonian Cycles that Generate Hilbert-Style Square-Filling Curves},
	abstract = {Within the recursive subdivision of the \(n \times n\) square, what characterizes a Hilbert-style space-filling curve motif of length \(n^2\) when—under iterated, self-similar, pure edge-replacement—a sequence of always self-avoiding lattice paths results? How many motifs are there and what do they look like? Such motifs are composable elements of a monoid, where all such motifs map to a particular subset of Hamiltonian cycles on the \(n \times n\) toroidal grid-graph. We prove that for any odd \(n \geq 1\) each motif has a shape that falls into exactly one of \(F{\_}{\{}(n−3)/2{\}}\) boundary “zipping” modes, where \(F{\_}i\) is the \(i\)th Fibonacci number; for even \(n\) no solution motifs exist. Each mode is governed by a special palindromic Fibbinary bit sequence (i.e., having no adjacent 1 bits). To varying degrees, each zipping mode emanates further combinatorial constraint inward from the square’s
boundary, especially at the corners. The zipping mode whose Fibbinary bits have the most consecutive 0s freezes over half of the \(n^2\) edges of an order-\(n\) motif into only one distinct (either left- or right-handed) configuration. Manual and machine enumeration for small \(n\) is significantly enhanced by these results. For \(n = 1, 3, 5, 7, 9, 11\) there are 1, 0, 1, 7, 10101, 20305328 distinct, globally self-avoiding motifs, falling into \(F{\_}{\{}(n−3)/2{\}} = 1, 0, 1, 1, 2, 3\) zipping modes, respectively. For \(n \geq 5\), each such motif, when infinitely exponentiated within its monoid, converges to an open-ended, square-filling, continuous curve.},
	url = {http://ecajournal.haifa.ac.il/Volume2022/ECA2022{\_}S2A13.pdf},
	year = 2022,
	author = {Douglas M. McKenna},
	comment = {},
	urldate = {2021-12-08},
	collections = {art,combinatorics,fibonaccinalia,things-to-make-and-do}
}