Symmetric 1 – Dependent Colorings of the Integers

In a recent paper by the same authors, we constructed a stationary 1−dependent 4−coloring of the integers that is invariant under permutations of the colors. This was the first stationary k−dependent q−coloring for any k and q. When the analogous construction is carried out for q > 4 colors, the resulting process is not k−dependent for any k. We construct here a process that is symmetric in the colors and 1−dependent for every q ≥ 4. The construction uses a recursion involving Chebyshev polynomials evaluated at √ q/2.