Problem 1.2.14 (b) in Symbolic Dynamics and Coding

Question

Given the alphabet $\mathcal{A}$ of size 3, let $X=\{x\in\mathcal{A}^{\mathbb{Z}}: x_{i+n^2}\neq x_{i} \forall i\in\mathbb{Z} \forall n\in\mathbb{N}\}$. Here $x_i$ is shorthand for $x(i)$. Show that $X=\emptyset$ I tried to use Pythagorean triples $a^2+b^2=c^2$ and concluded that $x_{a^2}=x_{b^2}$ if such an $x$ existed. So now all I need to do is prove $x_{a^2}\neq x_{b^2}$ and I'll have a proof by contradiction.

Answer 1

(Fill in the gaps as needed. If you're stuck, write out your working and thought process to demonstrate where you're at.)

Suppose that such a sequence exists. Let $\mathcal{A} = \{R, B, G \}$.

1. WLOG let $ x_1 = R$.
2. We will focus on number of the form $ x_{1 + n^2}$, and label them $y_n$. Clearly $y_n = B$ or $G$.
3. Claim: If $ a^2 + b^2 = c^2$, then $ y_a, y_b$ have the same color, which is distinct from $y_c$.
4. WLOG let $ y_3 = y_4 = B$ so $y_5 = G$.
5. So $y_5 = y_{12} = G, y_{13} = B$.
6. So $y_{12}=y_{16} = G, y_{20} = B$.
7. Using the pythagorean triples (and their multiples), keep on adding in known terms till you get a contradiction. (I get a contradiction with $y_{16}$, as it eventually needs to be $B$. Of course, you might reach another contradiction.)

$ y_{12} = y_{9} = G, y_{15} = B$
$y_{15} = y_8 = B, y_{17} = G$
$y_8 = y_6 = B, y_{10} = G$
$y_{10} = y_{24} = G, y_{26} = B $
$y_{24} = y_{18} = G, y_{30} = B $
$y_{30} = y_{16} = B, y_{34} = G $