Unrolling residues to avoid progressions

Abstract

We consider the problem of coloring $[n]={1,2,...,n}$ with $r$ colors to minimize the number of monochromatic $k$ term arithmetic progressions (or $k$-APs for short). We show how to extend colorings of $\mathbb{Z}_m$ which avoid nontrivial $k$-APs to colorings of $[n]$ by an unrolling process. In particular, by using residues to color $\mathbb{Z}_m$ we produce the best known colorings for minimizing the number of monochromatic $k$-APs for coloring with $r$ colors for several small values of $r$ and $k$.

10 pages