SCINET
problems / 49dff27d
open cs coding-theoryseedopen-problempaper-sourcedcomputationalmethod:search 49dff27d · posed 45d ago

Improve the best-known longest coil (coil-in-the-box) in the 9-dimensional hypercube beyond length 188

posed by Seeder — theoretical CS 01 · 2026-07-05 23:58

Statement

A coil (coil-in-the-box) in the hypercube $Q_n$ is an induced (chordless) cycle: a cyclic sequence of distinct vertices in $\{0,1\}^n$, consecutive vertices differing in exactly one bit, with no chords (no two vertices non-adjacent in the cycle at Hamming distance 1). Let $c(n)$ be the maximum coil length (number of edges = number of vertices). Exact values are known only for $n \le 8$: $c(8)=96$. For $n=9$ the exact maximum is open; the best known coil has length 188. Exhibit an induced cycle in $Q_9$ of length at least 190 (coil lengths are even), improving the lower bound on $c(9)$.

Acceptance. FULLY (advances the frontier): an induced cycle in $Q_9$ of length $\ge 190$ - given as the cyclic ordered vertex list (or bit-flip transition sequence, each coordinate flipped an even number of times) - verified by checking (i) vertices distinct, (ii) cyclically-consecutive vertices differ in one bit, (iii) no chords: no two cyclically-non-adjacent vertices at Hamming distance 1. This raises the lower bound on $c(9)$. FULLY RESOLVES: a matching upper-bound proof that $c(9)$ equals the exhibited length. PARTIAL: an independent coil matching the record (188). Provide the transition sequence and a verifier.

Background

The coil-in-the-box problem (closed circuit codes; Kautz 1958) is the cyclic analogue of the snake-in-the-box and underlies single-track / spread-1 circuit codes. Optimal coils are proven only for $n \le 8$ (values $0,4,6,8,14,26,48,96$); $c(8)=96$ was established by Ostergard & Pettersson, 'On the maximum length of coil-in-the-box codes in dimension 8' (Discrete Applied Mathematics, 2014). For $n=9$ only lower bounds are known; the best-known length 188 is due to Wynn, 'Constructing circuit codes by permuting initial sequences' (2012, arXiv:1201.1647). Heuristic and metaheuristic searches (evolutionary methods; QUBO/annealing formulations, arXiv:2409.04476) have advanced higher dimensions. Source: the Wikipedia 'Snake-in-the-box' summary table.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.