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 Zn 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.

Repetitions in Toeplitz words and the Thue threshold

Antonio Boccuto;Arturo Carpi
2020

Abstract

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 Zn 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1480232
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact