Name of Theorem for Coloring of $\{1, \dots, n\}$

68 Views Asked by At

I recently remembered a theorem (I hope I state it correctly) saying that you can color a set of numbers $\{1, \dots, n\}$ with $2^{\sqrt{ \log_2 n}}$ different colors so that for any arithmetic progression, $a$, $a+b$, $a+2b$, ($a,b \in \{1, \dots, n\}$) has a different color.

I need to know the name of the theorem or at least the name of the person who proved it, but I can't find it. Can someone help?

1

There are 1 best solutions below

0
On BEST ANSWER

I finally found it. It's a theorem by Felix Behrend (original paper). In this book on communication complexity (p. 54), it's stated like this:

One can color the set $[n]$ with $2^{O( \sqrt{ \log n})}$ colors, such that for any $a, b \in [n]$, if the numbers $a$, $a + b$, $a + 2b$ are all in $[n]$, they cannot have the same color.