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 be an abelian group, and let be a subset of . We say that a set of size is a -term arithmetic progression (-AP) if there exists an element such that for a reordering we have for all . We shall take to be one of or .
The van der Waerden number is the minimum such that every -coloring of contains a monochromatic -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 -coloring of is a surjective function . A set is rainbow if its elements receive distinct colors. The anti-van der Waerden number is the minimum positive integer such that every exact -coloring of contains a rainbow -AP. It is not difficult to see that this is well-defined and .
In the paper, we prove bounds on and . In fact, we show that for , the problem is only interesting in that it is strongly connected to the maximum size of -AP-free sets in for appropriate . However, for the situation is much stranger. We find logarithmic bounds on but for there is no such lower bound. In fact, for all .
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 -colorings of and that avoid rainbow -APs.
To determine , we design an algorithm that takes as input and determines whether or not there exists an exact -coloring of that avoids rainbow -APs. We can then start with and increase until no coloring exists, determining .
We shall use a standard backtracking search: fill in the values for the coloring by assigning 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 appears before the first appearance of the color if and only if . This will immediately drop out duplicate colorings. This is the only "symmetry calculation" we will perform, and it is very easy to do.
Initialize domains for all . At every step, will contain the colors that could be assigned to without immediately creating a rainbow -AP. Thus, when we assign a color to , we will search for any -AP where exactly elements of are colored and these colors are distinct. If is the only uncolored element in , then we can restrict the domain as . Using only the domains, we can prune the search tree on these conditions:
- If for any , then prune (cannot color !).
- If , then prune (cannot use all colors!).
With these pruning mechanisms, the algorithm will first deepen by coloring elements with before starting to use the larger colors. This is clearly non-optimal! So, we instead will use a trick: Assume we have pre-computed for all . 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 is colored using only colors, then must be colored using colors. Hence, if , then prune.
With these reasonable pruning mechanisms, we were able to compute for all and for all .
When transitioning to , 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 is not necessarily contained within for all . Further, we need to be very careful about -APs "crossing over zero" because of the modular arithmetic.
However, even with fewer pruning mechanisms, we were able to compute for all and for all .
Why is this suddenly more efficient for computing exact colorings that avoid -APs? The trick is that has more APs than , 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 case.
There are some algorithmic choices you can make, especially in the case, if a few conjectures are true. A singleton extremal coloring of is an exact coloring that avoids rainbow -APs using colors where one color class contains exactly one element.
Conjecture. For all , there exists a singleton extremal coloring of and .
Assuming this conjecture, we could initialize our algorithm to have the singleton color class be the 0 color, at the 0 position. For , 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 for a few more values of 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?