Does there exist infinite words using the alphabet $\{A,B,C,D\}$ that avoids patterns $XX,\ XAX,\ XBX,\ XCX,\ XDX$?

Okay, I apologize for some of my previous sloppy attempts. This time I’m pretty sure my answer is correct.

In this related post, it is asked whether there exists an infinite string of three characters $1,2,3$ that avoids patterns of the form $XX$. There do exist such sequences, and the top-voted answer shows how to construct such a sequence

$$1,2,3,1,3,2,1,2,3,2,1,3,1,2,3,1,3,2,...$$

by repeatedly applying the transformation $1\mapsto 123$, $2\mapsto 13$, and $3\mapsto 2$. Let’s call this sequence $\mathcal{S}$.

Now we’re going to apply a complicated transformation to $\mathcal{S}$ to construct a sequence satisfying your constraints. Define some subsequences as follows:

$$U_1=ABCDB,\space V_1=ABDCB$$ $$U_2=ACDBC,\space V_2=ACBDC$$ $$U_3=ADBCD,\space V_3=ADCBD$$

Now take the sequence $\mathcal{S}$ and proceed as follows. Replace the odd-numbered terms (starting with the first term) with $U_i$, where $i$ is the actual term of the sequence $\mathcal{S}$, and replace the even-numbered terms with $V_i$. You will get something looking like

$$U_1 V_2 U_3 V_1 U_3 V_2 U_1 V_2 U_3 V_2 U_1 V_3 ...$$

Now replace $U_i$ and $V_i$ with their corresponding string of $A,B,C,$ and $D$ as defined above. This gives us the string

$$ABCDB \space ACBDC \space ADBCD \space ABDCB \space ADBCD \space ACBDC \space ABCDB\space ...$$

Call this string $\mathcal{S}^{*}$.

We can check case-by-case that none of the simple concatenations $U_i V_j$ or $V_i U_j$ for $i\ne j$ results in a “forbidden pattern” of the form $XX$, $XAX$, $XBX$, $XCX$, or $XDX$. Also, the second and fifth characters of each five-block chunk of this sequences uniquely determine which character ($1$,$2$, or $3$) that chunk corresponds to in $\mathcal{S}$. In other words, either of $\mathcal{S}^{*}[5n+1]$ and $\mathcal{S}^{*}[5n+4]$ uniquely determines the value of $\mathcal{S}[n]$, meaning that a pattern of the form $XX$, $XAX$, $XBX$, $XCX$, or $XDX$ would imply the existence of a pattern of the form $XX$ in $\mathcal{S}$, which is impossible.


This is not another answer, but is too long for a comment, and is an alternative presentation of the last paragraph in Franklin Pezzuti Dyer's accepted answer (which I find too concise and not explicit enough).

We wish to show that ${\cal S}^*$ has no forbidden pattern.

It suffices to show that ${\cal S}^*$ has no forbidden pattern of odd length, because it has obviously no forbidden pattern of length $2$, and any forbidden pattern of even length $>2$ contains a smaller forbidden pattern of odd length (remove the rightmost character).

So assume that $I_1xI_2$ is a forbidden pattern in ${\cal S}^*$, with $x\in\{A,B,C,D\}$ and $I_1$ and $I_2$ are identical subwords in ${\cal S}^*$. The cases where the length of $I_1$ is $\leq 4$ are seen to be impossible by hand. So $I_1$ must have length $\geq 5$ and it particular it contains an $A$.

Denote by $B_0,B_1,B_2,\ldots ,B_r$ the successive blocks in ${\cal S}^*$ that intersect $I_1$. Then we can write $I_1=B'_0B_1B_2\ldots B_{r-1}B'_r$ where $B'_0$ is a (possibly empty) suffix of $B_0$ and $B'_{r}$ is a (possibly empty) prefix of $B_r$. Similarly, we can write $I_2=C'_0C_1C_2\ldots C_{r-1}C'_r$ with obvious notation. Now, because $A$ appears at the beginning of each block and only there, this forces $I_1$ and $I_2$ to be identical "blockwise", in other words $C'_0=B'_0, C'_r=B'_r$, and $C_k=B_k$ for $1\leq k \leq r$.

Now we know that the successive blocks that intersect $I_1xI_2$ are $B_0,B_1,B_2,\ldots ,B_{r-1},B'_rxB'_0,B_1,\ldots,B_{r-1},C_r$. Since the middle block $M=B'_rxB'_0$ has length $5$, one of the two subwords $B'_r$ or $B'_0$ has length $\geq 2$, and then this subword characterizes the block it belongs to, so that either $M=B_0$ or $M=C_r$. In both cases we deduce a square in $\cal S$ which is impossible.