Repetitions in Toeplitz Words and the Thue Threshold

摘要

A (finite or infinite) word is said to be k-th power-free if it does not contain k consecutive equal blocks. A colouring of the integer lattice points in the n-dimensional Euclidean space is power-free if there exists a positive integer k such that the sequence of colours of consecutive points on any straight line is a k-th power-free word. The Thue threshold of Z~n is the least number of colours t(n) allowing a power-free colouring of the integer lattice points in the n-dimensional Euclidean space.Answering a question of Grytczuk (2008), we prove that t(2) = t(3) = 2. Moreover, we show the existence of a 2-colouring of the integer lattice points in the Euclidean plane such that the sequence of colours of consecutive points on any straight line does not contain squares of length larger than 26.In order to obtain these results, we study repetitions in Toeplitz words. We show that the Toeplitz word generated by any sequence of primitive partial words of maximal length k is k-th power-free. Moreover, adding a suitable hypothesis on the positions of the holes in the generating sequence, we obtain that also the subwords occurring in the considered Toeplitz word according to an arithmetic progression of suitable difference, are k-th power-free words.