Nonrepetitive sequences on arithmetic progressions (Q648401)

Summary: A sequence \(S=s_1s_2\dots s_n\) is said to be nonrepetitive if no two adjacent blocks of \(S\) are identical. In 1906, \textit{A. Thue} [Christiania Vidensk.-Selsk. Skr. 1906, Nr. 7, 22 S. (1906; JFM 39.0283.01)] proved that there exist arbitrarily long nonrepetitive sequences over a 3-element set of symbols. We study a generalization of nonrepetitive sequences involving arithmetic progressions. We prove that for every \(k\geq 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,\dots,k\}\), are nonrepetitive. This improves a previous bound of \(e^{33}k\) obtained by the first author. Our approach is based on a technique introduced recently by the first two authors and \textit{P. Micek} [``A new approach to nonrepetitive sequences'' (submitted), \url{arXiv:1103.3809}] which was originally inspired by a constructive proof of the Lovász local lemma due to \textit{R. A. Moser} and \textit{G. Tardos} [``A constructive proof of the general Lovász local lemma'', J. ACM 57, No. 2, Art. No. 11, 15 p. (2010), \url{arXiv:0903.0544}]. We also discuss some related problems that can be attacked by this method.