Binary Gray Codes with Long Bit Runs

Abstract

We show that there exists an $n$-bit cyclic binary Gray code all of whose bit runs have length at least $n - 3\log_2 n$. That is, there exists a cyclic ordering of $\{0,1\}^n$ such that adjacent words differ in exactly one (coordinate) bit, and such that no bit changes its value twice in any subsequence of $n-3\log_2 n$ consecutive words. Such Gray codes are 'locally distance preserving' in that Hamming distance equals index separation for nearby words in the sequence.