On the (n,t)-antipodal Gray codes

An n-bit Gray code is a circular listing of all -bit binary strings in which consecutive strings differ at exactly one bit. For n≤t≤2n−1, an (n,t)-antipodal Gray code is a Gray code in which the complement of any string appears t steps away from the string, clockwise or counterclockwise. Killian and Savage proved that an (n,n)-antipodal Gray code exists when n is a power of 2 or n=3, and does not exist for n=6 or odd n>3. Motivated by these results, we prove that for odd n≥3, an (n,t)-antipodal Gray code exists if and only if t=2n−1−1. For even n, we establish two recursive constructions for (n,t) codes from smaller (n′,t′). Consequently, various (n,t)-antipodal Gray codes are found for even n’s. Examples are for t=2n−1−2k with k odd and 1≤k≤n−3 when n≥4, for t=2n−k when n≥2k with 1≤k≤3, for t=n when n=2k≥2 (an alternative proof for Killian and Savage’s result) …etc.