  A sequence $S=s_{1}s_{2}..._{n}$ is \emph{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$ and every $c\geqslant 1$ there exist
arbitrarily long sequences over at most $(1+\frac{1}{c})k+18k^{c/c+1}$ symbols
whose subsequences indexed by arithmetic progressions with common differences
from the set $\{1,2,...,k\}$ are nonrepetitive. This improves a previous bound
obtained in \cite{Grytczuk Rainbow}. Our approach is based on a technique
introduced recently in \cite{GrytczukKozikMicek}, which was originally inspired
by a constructive proof of the Lov\'{a}sz Local Lemma due to Moser and Tardos
\cite{MoserTardos}. We also discuss some related problems that can be
successfully attacked by this method.
