In an additive group $G$, a $k$-term arithmetic progression ($k$-AP) is a set $X = \{ a + i\ell : i \in \{0,\dots,k-1\} \}$ for some pair $a, \ell \in G$. For a set $S \subseteq G$, an exact $r$-coloring of $S$ is a function $c : S \to [r]$ such that for every $j \in [r]$, $c^{-1}(j) \neq \varnothing$. We call the elements in $[r]$ colors and we wish to use as many colors as possible while avoiding rainbow $k$-APs ($k$-APs $X \subseteq S$ where every element of $X$ receives a distinct color).

Let $S \subseteq G$ be a subset of the group $G$ and define $\operatorname{aw}(S,k)$ be the minimum number $r$ such that every exact $r$-coloring of $S$ has at least one rainbow $k$-AP. When $S$ is finite, this number exists and is at most $|S|$. In [P16], we consider the two cases $S = [n] \subset {\mathbb Z} = G$ or $S = {\mathbb Z}_n \subset Z_n = G$. Our main results are summarized as follows:

• There exist constants $c_3, c_2$ such that $\log_3(n) + c_3 \leq \operatorname{aw}([n],3) \leq \log_2(n) + c_2$.
• $\operatorname{aw}({\mathbb Z}_{2^k},3) = 3$ for all $k$.
• $\operatorname{aw}([n],k) = n$ if and only if $k \geq \lceil (n+3)/2\rceil$.

We found the following open problem very interesting:

Conjecture. For all $n \geq 3$, $\operatorname{aw}([n+1],3) \geq \operatorname{aw}([n],3) - 1$.

It is worth discussing the previous work on this topic. Most previous work was focused on a different problem:

Question. Fix $r \geq k \geq 3$. Does there exist a value $\alpha_r$ has the property that if a coloring $c$ of the integers using $r$ colors such that every color class has density (strictly) more than $\alpha_r$ then there is a rainbow $k$-AP under $c$? What is the minimum such $\alpha_r$?

Download rainbowaps.zip, unzip it, and type make to compile. The program rainbow.exe computes values of $\operatorname{aw}([n],k)$ and if given the argument k=3 it will compute only values $\operatorname{aw}([n],3)$. The program rainbow_zn.exe computes values of $\operatorname{aw}({\mathbb Z}_n,k)$ and if given the argument k=3 it will compute only values $\operatorname{aw}({\mathbb Z}_n,3)$.

• rainbowapdata.zip contains complete output files for runs of the above software.
• rainbowaps_all_values.txt contains all output information from the computational experiments.
• For information regarding computations of $\operatorname{aw}([n],k)$, see
  • rainbowaps_k3_examples.txt (Extremal examples for $k = 3$)
  • rainbowaps_k3_times.txt (Computation times for $k=3$)
  • rainbowaps_allk_examples.txt (Extremal examples for all $k$)
  • rainbowaps_allk_times.txt (Computation times for all $k$).
• For information regarding computations of $\operatorname{aw}({\mathbb Z}_n,k)$, see
  • rainbowaps_zn_k3_examples.txt (Extremal examples for $k = 3$)
  • rainbowaps_zn_k3_times.txt (Computation times for $k=3$)
  • rainbowaps_zn_allk_examples.txt (Extremal examples for all $k$)
  • rainbowaps_zn_allk_times.txt (Computation times for all $k$).

This research was completed as part of the Discrete Mathematics Working Seminar at Iowa State University. Ryan Martin is partially supported by National Security Agency grant H98230-13-1-0226. Michael Young is partially supported by National Science Foundation grant DMS 0946431.

J., Veselin, J. Licht (Fox), M. Mahdian, J. Nesetril, and R. Radoicic. Rainbow arithmetic progressions and anti-Ramsey results, Combinatorics, Probability & Computing 12:5-6 (2003) 599-620.

M. Axenovich and D. Fon-Der-Flaass, On rainbow arithmetic progressions, Electronic Journal of Combinatorics 11 (2004) #R1.

Rainbow Arithmetic Progressions I: Search Algorithm, Computational Combinatorics (Blog).

Rainbow Arithmetic Progressions II: The Collaboration, Computational Combinatorics (Blog).

(M. Young, presenter) Coloring the Integers with Rainbow Arithmetic Progressions Forty-Fifth Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, March 6, 2014.
Slides