= Solution
Color each integer independently and uniformly with one of $k$ colors. For a translate $S+t$, let $E_t$ be the event that some color is missing. The <union bound> gives
$$
\mathbb P(E_t)\le k(1-1/k)^s\le ke^{-s/k}.
$$
Join two events in the <dependency graph of events> when their translates overlap. Nonneighbors depend on disjoint sets of independent colors, giving the required joint independence. Overlap occurs only if $u-t\in S-S$, so the maximum degree is at most $s(s-1)$.
With natural logarithms, $s\ge6k\log k$ and $k\ge20$ imply
$$
eq(d+1)\le ek s^2e^{-s/k}\le\frac{36e(\log k)^2}{k^3}\le\frac{36e}{k^2}\le\frac{36e}{400}<1.
$$
The middle estimate uses that $s^2e^{-s/k}$ is decreasing for $s\ge2k$, and the next uses $\log k\le\sqrt{k}$. Therefore the <Lovász local lemma> supplies a coloring avoiding every bad event in any specified finite family of translates.
To obtain one coloring for all translates, use the <compactness extension of the Lovász local lemma>. At level $N$, consider colorings of $[-N,N]\cap\mathbb Z$ satisfying every constraint whose translate is contained in that interval. There are finitely many constraints, and the preceding argument makes the level nonempty. Restrictions connect these colorings into a finitely branching <tree>. The <König infinity lemma> gives an infinite branch, hence a coloring of all integers. Every translate eventually lies in a level of this branch, so it contains every color.
Thus \b[there exists a $k$-coloring of $\mathbb Z$ in which every translate of $S$ contains all $k$ colors]. This is a <polychromatic coloring of integer translates>; the compactness step establishes existence of one simultaneous coloring.
Back to article page
