Rainbow Randomness

The branch of pure mathematics known as Ramsey theory concerns the existence of highly regular patterns in sufficiently large sets of randomly selected objects, whether they are gatherings of people, piles of pebbles, stars in the night sky, or sequences of numbers generated by the throw of a die.

Patterns can arise out of randomness in a variety of ways. On a clear, moonless night, we see thousands of stars scattered across the sky. With so many stars visible, it’s not particularly difficult to pick out groups that appear in a certain pattern: four stars that nearly form a straight line or a square, six stars that define a cross, seven stars in the shape of a dipper. The human imagination fills in the rest, connecting the dots to create a menagerie of celestial creatures that inhabit the sky.

Ramsey theory goes further by proving the existence of highly regular mathematical patterns among sets of integers and other mathematical objects. Indeed, it implies that complete disorder is impossible. Somehow, no matter how complicated, chaotic, or random something appears, deep within that morass lurks a smaller entity that has a definite structure. Striking regularities are bound to arise even in a universe without rules.

Dutch mathematician Bartel L. van der Waerden (1903–1996) was for one of the first to identify such a pattern among integers–one that involves arithmetic progressions (or sequences) in sets of numbers. An arithmetic progression is a sequence of numbers in which each number is bigger (or smaller) than the number before it by a constant amount. For example, the sequence of integers 3, 5, 7 is a three-term arithmetic progression in which the difference between successive terms is 2.

Suppose that each integer from 1 through 9 is printed on a page in one of two colors, either red or blue (shown below in bold). Is it always true that either three red numbers or three blue numbers will form an arithmetic progression?

EXAMPLE: 1 2 3 4 5 6 7 8 9

For the coloring shown above, the three red numbers 1, 5, 9 form an arithmetic progression with a common difference of 4. In general, no matter how the numbers are colored, there is always either a red or a blue arithmetic progression.

In 1927, van der Waerden proved the following generalization: If n is a sufficiently large integer and if each integer from 1 through n is printed arbitrarily in one of two colors, there is always a monochromatic arithmetic progression with a certain number of terms.

EXAMPLE (n = 35):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

This example has a four-term monochromatic (blue) arithmetic progression: 6, 13, 20, 27, with a common difference of 7.

In recent years, mathematicians have started to study new variants of these integer-coloring problems. In general, for a given number of colors, the idea is to identify arithmetic progressions in which each integer has a different color. They describe this pursuit as “rainbow” Ramsey theory.

Such investigations recently won second place for high school student Jacob Licht of West Hartford, Conn., in this year’s Intel Science Talent Search (STS). Licht learned about rainbow Ramsey theory last summer while attending the Research Science Institute at the Massachusetts Institute of Technology. With the guidance of MIT graduate student Mohammad Mahdian, he was able to prove several new results.

In 2000, MIT graduate student Rados Radoicic proposed the following conjecture: Given 3n integers, where n integers are colored with each of three hues, there exists a three-term arithmetic progression in which each term has a different color.

“When I began working on Rados’ conjecture, I immediately tried out a couple of examples to get an idea of some underlying structure in the conjecture,” Licht says. One simpler case that he investigated involved a set of integers arranged in a circle rather than in a line.

EXAMPLE (n = 11; three colors): 0 1 2 3 4 5 6 7 8 9 10

In this instance, the integers 6, 9, 1 constitute a three-term rainbow arithmetic progression with a common difference of 3.

Licht initially proved Rados’ conjecture in the circular case when the number of terms is odd. He was also able to obtain valuable insights into the problem’s underlying structure.

“My mentor and I made a computer program that went through many values,” Licht says. “From this, I was able to generalize both the linear and circular case of Rados’ conjecture and another conjecture due to Jaroslav Nesteril.”

“Eventually,” he adds, “we went on to prove the circular case by proving certain structures couldn’t exist.”

Licht ended up proving several theorems. One major result concerns infinite strings of integers: If the integers are each colored red, green, or blue in such a way that at least one-sixth of the integers has a given color, then there exists a three-term rainbow arithmetic progression among the integers.

“Although we have derived quite a few results, we leave many open questions,” Licht concluded in his STS research paper. “Rainbow Ramsey theory is a new area of mathematics, and further work on any of these conjectures and formulating additional conjectures is encouraged. Rainbow Ramsey theory will definitely be an exciting field for more research.”