A Ramsey Characterisation of Eventually Periodic Words

Abstract

A factorisation $x=u_1{u}_2\cdots$ of an infinite word $x$ on alphabet $X$ is called `monochromatic', for a given colouring of the finite words $X^{\ast }$ on alphabet $X$, if each $u_i$ is the same colour. Wojcik and Zamboni proved that the word $x$ is periodic if and only if for every finite colouring of $X^{\ast }$ there is a monochromatic factorisation of $x$. On the other hand, it follows from Ramsey's theorem that, for \textit{any} word $x$, for every finite colouring of $X^{\ast }$ there is a suffix of $x$ having a monochromatic factorisation. A factorisation $x=u_1{u}_2\cdots$ is called `super-monochromatic' if each word $u_{k_1}{u}_{k_2}\cdots u_{k_n}$, where $k_1<\cdots <k_n$, is the same colour. Our aim in this paper is to show that a word $x$ is eventually periodic if and only if for every finite colouring of $X^{\ast }$ there is a suffix of $x$ having a super-monochromatic factorisation. Our main tool is a Ramsey result about alternating sums that may be of independent interest.

19 pages, 4 figures

References in corpus (2)

• On a new conjecture about super-monochromatic factorisations and ultimate periodicity
• Monochromatic factorisations of words and periodicity