# Problem 3: Magic Squares and the Thue-Morse Word

$$\def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}}$$

The goal of the problem is to build magic squares with the help of the infinite Thue-Morse word $\mathbf{t}$ on the binary alphabet $\{\sa{0},\sa{1}\}$ (instead of $\{\sa{a},\sa{b}\}$). The word $\mathbf{t}$ is $\mu^\infty(0)$ obtained by iterating the morphism $\mu$ defined by $\mu(0)=\sa{01}$ and $\mu(1)=\sa{10}$: $$\mathbf{t}=\sa{01101001100101101001}\cdots.$$ The $n\times n$ array $S_n$, where $n=2^m$ for a positive natural number $m$, is defined, for $0\leq i,j \le n$, by $$S_n[i,j] = \mathbf{t}[k](k+1) + (1-\mathbf{t}[k])(n^2-k),$$ where $k=i.n+j$. The generated array $S_4$ is

 $\mathbf{16}$ $2$ $3$ $\mathbf{13}$ $5$ $\mathbf{11}$ $\mathbf{10}$ $8$ $9$ $\mathbf{7}$ $\mathbf{6}$ $12$ $\mathbf{4}$ $14$ $15$ $\mathbf{1}$
The array is a magic square because it contains all the integers from $1$ to $16$ and the sum of elements on each row is $34$, as well as the sums on each column and on each diagonal.

Show the $n\times n$ array $S_n$ is a magic square for any natural number $n$ power of $2$.

## References

• Magic squares on Wikipedia