Nonrepetitive Sequences on Arithmetic Progressions

Abstract

A sequence $S=s_{1}s_{2}\ldots s_{n}$ is said to be nonrepetitive if no two adjacent blocks of $S$ are identical. In 1906 Thue proved that there exist arbitrarily long nonrepetitive sequences over $3$-element set of symbols. We study a generalization of nonrepetitive sequences involving arithmetic progressions. We prove that for every $k\geqslant 1$, there exist arbitrarily long sequences over at most $2k+10 \sqrt{k}$ symbols whose subsequences, indexed by arithmetic progressions with common differences from the set $\{1,2,\ldots ,k\}$, are nonrepetitive. This improves a previous bound of $e^{33}k$ obtained by Grytczuk. Our approach is based on a technique introduced recently by Grytczuk Kozik and Micek, which was originally inspired by a constructive proof of the Lovász Local Lemma due to Moser and Tardos. We also discuss some related problems that can be attacked by this method.