Rainbow Arithmetic Progressions I : Search Algorithm

by Derrick Stolee

At Iowa State, we tried an experiment this year to have a Discrete Mathematics Working Seminar where the group that normally meets for a research talk stays for an extra hour a week to work on a research problem. The goal was to break into smaller groups, but we ended up staying as one giant mass of mathematicians, including 5 faculty, a lecturer, and 6 graduate students. We recently posted the result to the arXiv:

S. Butler, C. Erickson, L. Hogben, K. Hogenson, L. Kramer, R. L. Kramer, J. C.-H. Lin, R. R. Martin, D. Stolee, N. Warnberg, and M. Young, Rainbow arithmetic progressions, arXiv:1404.7232 [math.CO]

Today, we will discuss the backtrack-search that was used to gather initial data on this problem. Since the paper features proofs as its main feature, not all of the algorithmic details were discussed (but enough were that anyone could figure out the rest). Here, I’ll flesh out as much detail as I can. In a later post, I will comment on the experimental collaboration.

Anti-van der Waerden Numbers

Let G be an abelian group, and let S be a subset of G. We say that a set A \subset S of size |A| = k is a k-term arithmetic progression (k-AP) if there exists an element d \in G such that for a reordering A = \{ a_1, \dots, a_k\} we have a_{i+1} = a_i + d for all i \in \{1,\dots,k-1\}. We shall take S \subseteq G to be one of [n] \subset {\mathbb Z} or \mathbb{Z}_n \subseteq \mathbb{Z}_n.

The van der Waerden number w(k,r) is the minimum n such that every r-coloring of [n] contains a monochromatic k-AP. This is a standard Ramsey-theory definition. What we do is consider the anti-Ramsey version of van der Waerden numbers by trying to avoid rainbow arithmetic progressions.

An exact r-coloring of S is a surjective function c : S \to [r]. A set is rainbow if its elements receive distinct colors. The anti-van der Waerden number \mathrm{aw}(S,k) is the minimum positive integer r such that every exact r-coloring of S contains a rainbow k-AP. It is not difficult to see that this is well-defined and \mathrm{aw}(S,k) \leq |S|.

In the paper, we prove bounds on \mathrm{aw}([n],k) and \mathrm{aw}({\mathbb Z}_n, k). In fact, we show that for k \geq 4, the problem is only interesting in that it is strongly connected to the maximum size of \ell-AP-free sets in [n] for appropriate \ell = \ell(k). However, for k = 3 the situation is much stranger. We find logarithmic bounds on \mathrm{aw}([n],3) but for \mathrm{aw}({\mathbb Z}_n, 3) there is no such lower bound. In fact, \mathrm{aw}(\mathbb{Z}_{2^m}, 3) = 3 for all m \geq 2.

Many of these results were conjectured before they were proven, and these conjectures were formed by looking at data generated computationally. All of our data is available online. We now discuss algorithms for finding exact r-colorings of [n] and \mathbb{Z}_n that avoid rainbow k-APs.

Computing \mathrm{aw}([n],k)

To determine \mathrm{aw}([n],k), we design an algorithm that takes n, k, r as input and determines whether or not there exists an exact r-coloring of [n] that avoids rainbow k-APs. We can then start with r = k and increase r until no coloring exists, determining \mathrm{aw}([n],k).

We shall use a standard backtracking search: fill in the values for the coloring c : [n] \to [r] by assigning c(0), c(1),\dots, c(n-1) in order. The trick is not in this part, but in how we prune the search tree.

One simple trick is that we will always use a lexicographic coloring: the first appearance of the color p appears before the first appearance of the color q if and only if p < q. This will immediately drop out r! duplicate colorings. This is the only "symmetry calculation" we will perform, and it is very easy to do.

Initialize domains D(i) = [r] for all i \in [n]. At every step, D(i) will contain the colors that could be assigned to c(i) without immediately creating a rainbow k-AP. Thus, when we assign a color to c(i), we will search for any k-AP A where exactly k-1 elements of A are colored and these colors are distinct. If j \in A is the only uncolored element in A, then we can restrict the domain as D(j) \leftarrow D(j) \cap c(A\setminus j). Using only the domains, we can prune the search tree on these conditions:

  • If D(j) = \varnothing for any j, then prune (cannot color j!).
  • If \cup_{i\in [n]} D(i) \neq [r], then prune (cannot use all colors!).

With these pruning mechanisms, the algorithm will first deepen by coloring n - r elements with 0 before starting to use the larger colors. This is clearly non-optimal! So, we instead will use a trick: Assume we have pre-computed \mathrm{aw}([m],k) for all m < n. This assumption is not unreasonable, since we are likely to compute all of these numbers in a row. (If we tried to parallelize the computation, this assumption may not be as reasonable.)

We add one more pruning mechanism:

  • If \{0,\dots,i\} is colored using only \ell colors, then \{i,\dots, n-1\} must be colored using r-\ell+1 colors. Hence, if \mathrm{aw}([n-i], k) \leq r-\ell+1, then prune.

With these reasonable pruning mechanisms, we were able to compute \mathrm{aw}([n],3) for all n \leq 58 and \mathrm{aw}([n],k) for all k < n \leq 25.

Computing \mathrm{aw}({\mathbb Z}_n,k)

When transitioning to \mathbb{Z}_n, we can use a lot of the previous algorithm: domains, lexicographic coloring, etc. However, one thing we cannot use is the final pruning mechanism using previous values, since \mathbb{Z}_m is not necessarily contained within \mathbb{Z}_n for all m < n. Further, we need to be very careful about k-APs "crossing over zero" because of the modular arithmetic.

However, even with fewer pruning mechanisms, we were able to compute \mathrm{aw}(\mathbb{Z}_n,3) for all n < 100 and \mathrm{aw}(\mathbb{Z}_n,k) for all k < n < 20.

Why is this suddenly more efficient for computing exact colorings that avoid 3-APs? The trick is that \mathbb{Z}_n has more APs than [n], and hence has more constraints! The increased number of constraints means that we will find a problem with our coloring earlier in the search tree, and hence the search tree is "skinnier" than in the [n] case.

Future Work

There are some algorithmic choices you can make, especially in the \mathbb{Z}_n case, if a few conjectures are true. A singleton extremal coloring of S is an exact coloring that avoids rainbow k-APs using \mathrm{aw}(S,k)-1 colors where one color class contains exactly one element.

Conjecture. For all n > 3, there exists a singleton extremal coloring of [n] and \mathbb{Z}_n.

Assuming this conjecture, we could initialize our algorithm to have the singleton color class be the 0 color, at the 0 position. For k = 3, this actually creates even more possibilities for trimming domains, as we can immediately remove 0 from the domains of all other elements. I’ve done some initial testing with this assumption and found that we can calculate \mathrm{aw}(\mathbb{Z}_n,3) for a few more values of n beyond 100, but no more than 150 without parallelizing the algorithm, or waiting longer than 48 hours.

Are there more efficient algorithms? Can we get exact values without resorting to algorithms?

Advertisements