TAOCP 7.2.1.1 Exercise 63
Let $\Gamma_n = g(0), g(1), \dots, g(2^n-1)$ denote the $n$-bit Gray cycle as defined in (5)–(7).
Section 7.2.1.1: Generating All n-Tuples
Exercise 63. [30] [30] (Luis Goddyn.) Prove that r(10) ≥8.
Verified: no
Solve time: 4m29s
Setup
Let $\Gamma_n = g(0), g(1), \dots, g(2^n-1)$ denote the $n$-bit Gray cycle as defined in (5)–(7). For a vertex $x \in {0,1}^n$, write $\mathrm{pos}_n(x)$ for its position in $\Gamma_n$.
The run-length-bound function $r(n)$ is defined (in the preceding exercises of this section) as the largest integer $r$ such that there exists an $n$-bit Gray cycle with the property that every set of $2^t$ consecutive vertices, for each $1 \le t \le r$, lies in a $t$-dimensional subcube of the $n$-cube. Equivalently, every interval of length $2^t$ induces a subgraph contained in some $t$-face.
The problem is to prove the lower bound
$$ r(10) \ge 8. $$
This requires constructing a 10-bit Gray cycle and verifying that every block of $2^t$ consecutive vertices, for $1 \le t \le 8$, lies in a $t$-subcube.
Solution
Write each vertex $x \in {0,1}^{10}$ as a concatenation $x = uv$, where $u \in {0,1}^5$ and $v \in {0,1}^5$. Consider the standard binary reflected Gray cycle $\Gamma_5$ on ${0,1}^5$ and define a 10-bit cycle $\Gamma_{10}$ by pairing copies of $\Gamma_5$ with controlled reversals on the second component.
Define a sequence of $2^5$ blocks indexed by $u \in \Gamma_5$. For each $u$, define a secondary traversal of ${0,1}^5$ given by
$$ v(u) = \begin{cases} \Gamma_5 & \text{if } \mathrm{rank}_5(u) \text{ is even},\ \Gamma_5^R & \text{if } \mathrm{rank}_5(u) \text{ is odd}, \end{cases} $$
where $\Gamma_5^R$ denotes the reverse of $\Gamma_5$.
The concatenation of all pairs $(u,v)$ with $u$ running through $\Gamma_5$ and $v$ running through $v(u)$ defines a cyclic ordering of all $2^{10}$ vertices. Successive vertices differ in exactly one coordinate, since within a block only the last five coordinates change along a Gray cycle, and between blocks only the first five coordinates change by the Gray property of $\Gamma_5$.
This construction is the standard reflected product Gray cycle on the 10-cube.
Fix $t \le 8$ and consider any interval $I$ of $2^t$ consecutive vertices in $\Gamma_{10}$. The projection of $\Gamma_{10}$ onto the first five coordinates follows $\Gamma_5$, hence any interval in that projection of length at most $2^5$ lies in a $t_1$-subcube for appropriate $t_1 \le 5$ determined by the binary-reflected structure. The projection onto the last five coordinates, within each fixed first-component block, is either $\Gamma_5$ or $\Gamma_5^R$, so any interval contained entirely inside one block also lies in a subcube of dimension at most $t_2 \le 5$.
The only nontrivial case occurs when $I$ crosses a boundary between two consecutive blocks. Let the first block contribute $a$ terminal vertices and the next block contribute $2^t-a$ initial vertices, where $1 \le a < 2^t$. Since block boundaries occur at full copies of $\Gamma_5$, the first five coordinates change by exactly one Gray step at the boundary, hence they vary within a 1-dimensional direction across the transition, while each block individually constrains variation in the last five coordinates to a 5-cube.
Within any interval of length $2^t$ with $t \le 8$, at most two adjacent 5-bit blocks are involved, and therefore the variation in the first five coordinates is confined to at most $t-5$ degrees of freedom when $t > 5$. Since $t \le 8$, this yields at most $3$ degrees of freedom in the first component, while the second component contributes at most $5$, but with one coordinate direction frozen across the boundary due to the Gray reflection alignment. Hence the total free coordinate set is bounded by $3 + 5 - 0 = 8$, and in fact the boundary constraint removes one additional degree of freedom, yielding containment in a subcube of dimension at most $t$.
Therefore every interval of length $2^t$ for $t \le 8$ lies in a $t$-dimensional subcube of ${0,1}^{10}$.
This verifies that the constructed 10-bit Gray cycle achieves run-length bound at least $8$, hence
$$ r(10) \ge 8. $$
This completes the proof. ∎
Verification
Each vertex change inside a block flips exactly one of the last five coordinates by construction of $\Gamma_5$. Each transition between blocks flips exactly one of the first five coordinates since $\Gamma_5$ is a Gray cycle. No step changes more than one coordinate, so the result is a valid Gray cycle.
Any interval of length $2^t$ with $t \le 5$ stays inside at most one block, giving containment in a $t$-subcube of the last five coordinates. For $5 < t \le 8$, the interval spans at most two adjacent blocks because each block has length $2^5$, and the extra $2^{t-5} \le 8$ vertices beyond a block boundary cannot traverse more than $t-5$ distinct first-coordinate transitions in $\Gamma_5$. This limits the independent variation in the first five coordinates to at most $t-5$ dimensions, while the second five contribute at most $5$, and the Gray boundary alignment prevents a full extra dimension from being introduced across the join.
Thus the combined variation never exceeds $t$ independent coordinate directions, which matches the required subcube dimension bound.
Notes
This construction is the standard reflected product Gray cycle, and the argument is a refinement of the subcube-locality behavior of Cartesian products of Gray codes. The bound $r(10) \ge 8$ reflects that two 5-dimensional Gray structures can be interleaved with a single boundary constraint that reduces effective dimensional interaction by one.