← All problems

Optimal single-track Gray-code conjecture

For every prime integer nn, there exists a cyclic sequence of length 2n−22^n-2 of distinct words x0,x1,…,x2n−3∈{0,1}nx_0,x_1,\ldots,x_{2^n-3}\in\{0,1\}^n such that consecutive words, including x2n−3x_{2^n-3} and x0x_0, differ in exactly one coordinate, and every column is a cyclic shift of the first: for each coordinate j∈{0,…,n−1}j\in\{0,\ldots,n-1\} there is an index sj∈Z/(2n−2)Zs_j\in\mathbb{Z}/(2^n-2)\mathbb{Z} such that (xi)j=(xi+sj)0(x_i)_j=(x_{i+s_j})_0 for every i∈Z/(2n−2)Zi\in\mathbb{Z}/(2^n-2)\mathbb{Z}.

References

Progress summary

Refreshed
Open · progress reported

A new preprint reports computer-checked progress through prime 47, but the conjecture for all primes remains open.

The conjecture asks whether optimal single-track Gray codes exist for every prime dimension. A necklace-cycle construction would imply the desired codes, but no general proof is known.

Known results

  • Schwartz and Etzion established the relevant maximum-length bound.
  • Etzion's 2007 survey identified the prime case as a central open problem.
  • The conjecture was computationally confirmed for every prime n≤19n \le 19.

October 17, 2026 extension through prime 4747

This is claimed progress, not a proof of the general conjecture, and the reported extension has not received independent expert assessment in the retrieved sources.

Current status (as of October 2026): the conjecture is known through prime 4747 according to an unverified preprint claim, while the assertion for every prime remains open.

Sources

Solutions 0

No solutions have been posted yet.