Tiling Periodicity *

NEW

Problem: Reconstructed statement: every primitive tiling period of a finite word is a tiling period of minimum size, where a tiling period is a partial word whose shifted solid positions disjointly cover the word, size means number of solid positions, and primitive means not tileable by any smaller partial word.

Result: The statement is false.

Let the alphabet be $\{a,b,c\}$, and let

Equivalently, in blocks of length $7$,

Define the partial word

Its support is

so $|u|=21$. The two shifts $0,7$ of $u$ disjointly cover $w$, hence $u$ is a tiling period of $w$.

But $w$ also has the smaller tiling period

whose support has size $14$, tiled by shifts $0,2,4$. Thus $u$ is not minimal-size.

It remains to show $u$ is primitive. Suppose a smaller partial word with support $S$ tiles $u$, with translation set $T$. Then $S\oplus T=A$, and $|S|$ properly divides $21$, so $|S|\in\{1,3,7\}$.

If $|S|=1$, all letters of $u$ would be equal, impossible.

Assume $|S|=3$ or $7$, normalized so $0\in S,T$. Let

Because $A\cap[0,12]=[0,6]$, we get

Hence $|S_0||T_0|=7$.

If $|S|=3$, then necessarily $S_0=\{0\}$ and $T_0=[0,6]$, so $T=[0,6]$ and $S=\{0,14,28\}$. But then the letter at coordinate $0$ of the smaller period would have to equal all letters of $u_0,u_1,\dots,u_6$, namely $\texttt{a,b,a,b,a,b,b}$, impossible.

If $|S|=7$, similarly $S=[0,6]$ and $T=\{0,14,28\}$. Then the coordinate $0$ letter would have to equal $u_0,u_{14},u_{28}$, namely $\texttt{a,b,b}$, impossible.

So $u$ is primitive but not minimal-size. This disproves the conjecture.

Citation: Original problem and terminology: J. Karhumäki, Y. Lifshits, W. Rytter, “Tiling Periodicity,” Discrete Mathematics & Theoretical Computer Science 12(2), 237–248, 2010, DOI: 10.46298/dmtcs.517.