Minimizing monochromatic arithmetic progressions in \([1,n]\)

The basic question we want to answer is: among all 2-colorings of the interval \([1,n] \subset \mathbb{N}\), how few monochromatic 3-term arithmetic progressions (APs) can we possibly have? A 2-coloring of a set \(S\) is a function \(f : S \to \{0,1\}\), a 3-term AP is a set of the form \(\{a, a+k, a+2k\} \; (k > 0)\), and we say an AP is monochromatic under the coloring \(f\) if \(f\) is constant on it.

There are many obvious generalizations of this question: we could consider longer APs, more colors, and other patterns than arithmetic progressions. On the other hand, so far the simplest question still has no answer, and also gives one of the most surprising results. Below is a program that randomly 2-colors the interval \([1,800]\). It maintains a count of the number of monochromatic 3-term APs. Clicking on it will start the algorithm, which randomly chooses a number in the interval, and checks whether switching its color will reduce the number of monochromatic 3-term APs or not; if it does, the color is changed.

Each line of the coloring represents 10 new trials (a trial being an attempt to change the color of a random number). One of two patterns will generally emerge: either or, much more rarely, These colorings both represent local minima; the latter contains more 3-term APs, and is unstable under less naive algorithms. Often, one or more 1-2 pixel stripes will persist within a color block, and the blocks may be shifted slightly, but these are artifacts of the very simple algorithm and the small interval we have chosen. In fact, all serious attempts to minimize the number of monochromatic 3-term APs result in the first pattern; it remains to be proven that this coloring is the best possible.

By considering 2-colorings of the continuous interval \(I = [0,1]\) and instead minimizing the integral \[ \int_I\int_0^{1-x} \mathbb{1}_{f^{-1}(x)}(x+y/2)\,\mathbb{1}_{f^{-1}(x)}(x+y)\, dy\, dx, \] we can try to determine where the "true" boundaries for these color blocks are supposed to be, and then to prove that this is the case; so far, nobody has succeeded in doing this.

For comparison, the following programs repeat the algorithm above for 4-term and 5-term APs, respectively.


They do not produce consistent results, but it isn't clear why. Using more sophisticated algorithms (which are not interesting to watch in real time), these also show some common structure, but nothing as clean or surprising as the original case. This leaves a few outstanding questions: