# Is this model of converting integers to Gray code correct?

The model shown in the figure converts all numbers that have k digits in the binary system to Gray code without any calculation, but I have no proof that guarantees this claim.

Here is some information on how to use it.

Conversion model of all integers that have k digits in the binary system in Gray code.

Rules

1. You will need k columns of numbers. The numbers to be encoded are arranged in the last column.

2. The conversion is done gradually by transferring groups of numbers to the adjacent columns in the way the arrows show. There are two types of paired arrows, parallel (=) and intersecting (×). Symbolically, the (=) and (×) are considered inverse of each other.

3. Each column with arrows is formed by an exact copy of the previous column and by a copy of the previous column that has inverted pairs of arrows, which is placed below the exact copy.

Observation

If we set "=" = 0 and "×" = 1, then the successive columns containing arrows form the Thue Morse sequence which essentially forms the rules for converting integers to Gray code.

• I use the following mnemonic trick/inductive definition whenever I encounter gray codes: To get the Gray codes for the numbers $2^n,\ldots,2^{n+1}-1$, take the Gray codes of the numbers $1,..2^n-1$ reverse that list and change the new first bit to 1. Maybe you can prove things inductively using that description. Commented Jul 1, 2020 at 16:25

Yes, the proposed scheme always produces a Gray code. This can be proved by induction on $$k$$ as follows.

Proof. The base cases of $$k=1,2$$ are trivial. Assume that a Gray code is produced for integers with $$k=s\geq 2$$ bits, and let's prove the same for $$k=s+1$$.

Let $$c_1, \dots, c_{s+1}$$ denote the columns. We view the column $$c_s$$ as formed by blocks of size 2, where the $$i$$-th block consists of numbers $$2^s+2i-2$$ and $$2^s+2i-1$$ is some order ($$i=1,2,\dots,2^{s-1}$$). It is easy to see that each column $$c_j$$ for $$j represents a permutation of the same blocks.

Replacing $$i$$-th block in $$c_s$$ with a single number $$2^{s-1}+i-1$$ and using the induction assumption for $$k=s$$, we conclude that $$c_1$$ forms a Gray code unless we have a change in the numbers parity (i.e., unequal least significant bits) when we go from some block to the next one. It remains to show that such change in parity never happens.

Call a block positive is the numbers in it appears in their natural order, and call it negative otherwise. Absence of the parity change between adjacent blocks in $$c_1$$ means that positive and negative blocks in it alternate. Below we show that this property holds already for $$c_{s-1}$$, and then it trivially propagates to all $$c_j$$ with $$j (including $$c_1$$).

Let $$(\tau_i)_{i\geq 0}$$ denotes Thue-Morse sequence. By construction, the $$i$$-th block in $$c_s$$ is positive iff $$\tau_{i-1}=1$$. Furthermore, the $$i$$-th block in $$c_s$$ retains its position in $$c_{s-1}$$ iff $$\tau_{\lfloor(i-1)/2\rfloor}=1$$, otherwise its position shifts by 1 (down or up). Since $$\tau_{i-1} + \tau_{\lfloor(i-1)/2\rfloor} \equiv i-1\pmod{2}$$, we get that in $$c_{s-1}$$ positive blocks appear at odd positions and negative blocks appear at even positions, i.e. positive and negative blocks alternate. QED

• The proof inspires self confidence. I can't follow the subtle arguments but it shows great job. Thank you, as well as everyone who contributed, in any way, to this thread. Commented Jul 5, 2020 at 10:37
• @ΓιώργοςΠλούσος: The proof would be easier to follow if you execute it on one of your examples for $k=4$ or $k=5$. Let me know if any particular argument is unclear. Commented Jul 5, 2020 at 14:46
• Your proof is perfect, dear Max, written clearly and with emphasis on detail, I just meant that I have shortcomings in mathematics. I'm more of a visual guy and I have to get used to this notation. Commented Jul 5, 2020 at 17:50