Can we colourize the natural numbers with a finite number of colours such that, for all \((a,b)\ne(2,2)\), the colour of the sum \(a+b\) is different from the colour of the product \(ab\)? (The exception is because given two natural numbers \(a\), \(b\in\mathbf {N}\), there is only one case in which \(a+b=ab\), when \(a=b=2\).) For example, $$\pi=3.14159\,26535\,89793\,23846\,26433\,83279\,\dots ,$$ we can think that we colour the numbers with 10 colours \(0\), \(1\), \(2\),…, \(9\) colouring the \begin{align*} &\text{1 of colour 3},\\ &\text{2 with colour 1},\\ &\text{3 with colour 4},\\ &\text{4 with colour 1},\\ &\text{5 with colour 5},\\ &\text{6 with colour 9},\\&\dots\end{align*} according to the figures of \(\pi\). In this case the colour of \(2+8=10\) and \(2\times8=16\) are equal to \(3\). But this is only one case, there are infinite ways of colouring and we can use millions of colours! We need at least 3 colours, since taking \((a,b)=(1,6)\), \((1,7)\) or \((2,4)\) we have that the pairs \((6,7)\), \((7,8)\) and \((6,8)\) have to have different colour. Then the colour of \(6\), \(7\) and \(8\) must be different.
I already anticipate that the answer is negative, but let’s not be premature.
The problem is an old one, although it is difficult to give a citation for its exact origin. In 1979 there are publications studying the problem of whether we can colour the natural numbers in such a way that no quartet \(\{a, b, a+b, ab\}\) is monochromatic. These questions fall under Ramsey theory. In 1892 Hilbert was the first to use a Ramsey theorem, but more spectacular is Schur’s application in 1916 which is connected to Fermat’s last theorem. One method of proving that a diophantine equation has no solutions is to try to find a prime \(p\) such that the equation has no solution \(\bmod\ p\). Schur proved the following theorem as a lemma in a paper on Fermat’s equation \(x^n+y^n=z^n\).
Schur’s Theorem. If we colour the natural numbers with a finite number of colours, there exist three numbers of the same colour \(x\), \(y\), \(z\) such that \(x+y=z\).
Using this result Schur was able to prove that given \(n\), if \(p\) is a sufficiently large prime, then the equation \(x^n+y^n=z^n\) has a non-zero solution \(\bmod\ p\). It therefore closes the way to proving that there is no solution of Fermat’s equation by this method.
Ronald Graham and Neil Hindman in 1979 thought of a variant of our problem; they ask that \(\{a,b,a+b, ab\}\) not to be monochromatic. They went so far as to prove that they could colour the numbers 1 to 251 with two colours on the condition that they have no monochromatic \(\{a,b,a+b, ab\}\) quartets. On the other hand, the numbers 1 to 252 need at least 3 colours. This statement was proved with the help of a computer. We could ask: What would be the smallest number \(N\) such that we cannot colour \(\{1,2,\dots, N\}\) with three colours satisfying the condition \(a+b\) and \(ab\) are of different colours? (when \(ab\ne a+b\) is implied).
The greedy algorithm
One way to approach the problem is to use the greedy algorithm, colouring the numbers successively. Assuming we coloured \(1\), \(2\), …, \(n-1\) we then colour \(n\) so that it satisfies the condition (\(a+b\) and \(ab\) different colours) but using the minimum number of colours. If we designate the colours by numbers and the colour of \(n\) by \(f(n)\), we define a function. The first steps of the greedy would be the following
- \(f(1)=1\), we must use one colour and we have no restriction, we use the first available colour \(1\).
- \(f(2)=2\), we cannot put \(f(2)=1\) because \(\{2,1\}=\{1+1,1\times1\}\) so \(1\) and \(2\) must have different colours. I use the first available colour: \(2\).
- \(f(3)=1\). The only restriction we have is that the colour of \(3=1+2\) has to be different from that of \(2=1\times2\). We use \(1\) which is the first available colour for \(3\).
- \(f(4)= 2\) since the colour of \(4=1+3\) must be different from that of \(3=1\times3\). So \(f(4)\) cannot be \(1\) but there is nothing forbidding \(f(4)=2\).
- \(f(5)= 1\) We have \(5=1+4=2+3=1\times5\). So \(f(5)\) cannot be \(f(1\times4)\), \(f(2\times3)\) or \(f(1+5)\). Then only \(2\) is forbidden and we can paint with \(1\) colour.
- \(f(6)= 2\). Since \(6=1+5=2+4=1\times6=2\times3\) we must avoid the values of \(f(5)\), \(f(8)\), \(f(7)\), \(f(5)\). Which prohibits only \(1\).
- …
This process can continue indefinitely. In each case there is only a finite number of colours to avoid and if necessary we can use a colour never used before. But will we need an infinite number of colours? This question is interesting but does not solve the original question. The greedy method may not be the best possible one.
The function \(f(n)\) thus defined has very interesting properties. The sequence \(f(n)\) is number A235726 in OEIS. For many years I proposed to my students to study the properties of \(f(n)\), showing them the origin of the problem. It is still open today to know how \(g(n):=\max_{1\le j\le n}f(j)\) grows. What proves the result we discuss today is that \(\lim g(n)=\infty\).
An unexpected solution
Although I have been interested in the problem since I first heard about it about a decade ago, I did not learn of its solution until three years after its publication in the Annals of Mathematics. Its author is Joel Moreira, a Portuguese mathematician now at the University of Warwick, who has shown that given any finite colouring of the natural numbers there will always exist infinitely many monochromatic \(\{ a+b,a\times b \}\) pairs (in fact he shows more: that there are infinitely many monochromatic \(\{ a,a+b,a\times b \}\) triads). Moreira maintains a blog, I Can’t Believe It’s Not Random!, about the mathematics he is interested in.
The solution to this problem has a long history. The philosophy in Ramsey-type problems is that a sufficiently large set will contain predetermined finite structures. For example, a meeting of enough people will contain a group of 5 who all know each other, or a group of 7 in which no two people know each other. But there are many variants, for example our problem fits into the following scheme:
We will say that a finite family of polynomials \(\{f_1,\dots, f_k\}\) in several variables \(x=(x_1,\dots, x_s)\) is Ramsey-type if for every partition of \(\mathbf{N}\) into a finite number of colours \(\mathbf{N}=C_1\cup\cdots\cup C_r\), there is a colour \(i\) and a \(x\in \mathbf{N}^s\) such that \(\{f_1(x),\dots, f_k(x)\}\subset C_i\). Our problem asks whether the family \(\{x+y, xy\}\) is Ramsey-type.
Topological Dynamics
The first surprise one finds in Joel Moreira’s article is that he turns the problem into a problem of topological dynamics. In principle, topological dynamics studies a topological space in which a group of transformations acts, and it was developed to study the solutions of differential equations. There are many technical difficulties in obtaining a (compact) space and a group of transformations such that their recurrence properties have to do with pairs of natural numbers \(\{a+b,ab\}\). The final result is arithmetic but the points of the space \(X\) used in the proof are ultrafilters in \(\textbf{N}\), which is a compactification of the set of natural numbers \(\textbf{N}\).
Actually, in some of Joel’s earlier work with his thesis supervisor Vitaly Bergelson, they successfully apply this technique to prove that if we colour \(\mathbf{Q}\) with a finite number of colours, there is always \(x\in \mathbf{Q}\) and \(y\in \mathbf{N}\) with \(\{x+y,xy\}\) monochromatic and \(x+y\ne xy\). Working with \(\mathbf{Q}\) gives much more play in the problem. Bergelson and Moreira used ergodic theory to solve the analogue problem in \(\mathbf{Q}\). They had good reasons why this proof would not work on \(\mathbf{N}\), that the semigroup of affine transformations on \(\mathbf{N}\) is not amenable. Joel Moreira later found that using topological dynamics instead of ergodic theory could transfer the proof.
The theorem that he succeeds in proving refers to finite families of functions \(\mathcal F\) of the type \begin{gather*} x_0x_1\cdots x_N,\\ x_0x_1\cdots x_m+f(x_{m+1},\dots, x_n),\quad 0\le m<n\le N,\end{gather*} where the \(f\)’s are functions which fulfill the condition that fixing their variables minus the last one leaves a polynomial in \(x_n\) with no constant term.
Moreira proves that if we colour \(\mathbf{N}\) with a finite number of colours, we find \(x_0\), \(x_1\), …, \(x_N\) such that all the values of the functions of \(\mathcal F\) have the same colour at those points.
Elements of proof
The proof obtained has the property that we can eliminate the language of topological dynamics and understand it to some extent.
It is based on a concept of a large set of natural numbers. There are many possibilities to define the concept of large for subsets of \(\textbf{N}\). But we need the concept to have certain properties:
- Any large set is non-empty.
- \(\textbf{N}\) is large.
- If \(A\supset B\) and \(B\) is large, then \(A\) is large.
- If we divide a large set \(A\) in a finite number of parts \(A=B_1\cup B_2\cup\cdots\cup B_N\), at least one of the \(B_r\) is large.
- If \(A\) is large, then \(nA=\{na\colon a\in A\}\) is large.
- If \(A\) is large, \(n+A=\{n+a\colon a\in A\}\) is large.
- If \(A\) is large, \(A-n=\{a-n\colon a\in A, a-n\ge1\}\) is large.
We can use the following definition: We will call large a subset \(M\subset\textbf{N}\) that can be written as an intersection \(M=A\cap B\), where \(A\) has bounded gaps. That is, there exists a number \(a\) such that any set of \(a\) consecutive numbers cuts \(A\). On the other hand \(B\) contains intervals of arbitrary length.
(The sets I have called large sets are called piecewise syndetic sets in the article).
The large sets we have defined have an important and difficult to prove property, which is going to be key in the proof.
Van der Waerden-type theorem. Let \(M\) be large and \(F\subset \textbf{N}\) be a finite set, then there exist infinitely many \(y\in\textbf{N}\) such that the sets $$ M\cap\bigcap_{m\in F}(M-my)$$ are large.
Once admitted this theorem, the proof is really ingenious and I cannot resist detailing it. It is one of those constructions, frequent in mathematics, where we see human ingenuity at its best. It takes a lot of patience, a desire to see the problem solved, and hours of attempts to arrive at a solution of this type. Perhaps this is where topological dynamics has brought its magic. Don’t hesitate to read it, but when you have a while, it is mathematics in its purest form.
The inductive construct
We already have all the machinery. Let’s suppose that we are given a colouring of the set of natural numbers $$\textbf{N}=C_1\cup C_2\cup \cdots\cup C_r.$$ Our problem is to find infinite pairs \(\{a+b,ab\}\) all contained in the same colour \(C_t\). For this we are going to construct inductively a succession of large sets $$B_0, B_1, B_2, \dots$$ and a succession of natural numbers $$y_1, y_2, y_3, \dots$$ such that $$B_n\subset y_n B_{n-1}.$$ At the same time we will construct a succession of colours $$t_0,t_1,t_2,t_3,\dots$$ and auxiliary large sets $$D_1,D_2, D_3,\dots$$ We begin by noting that by the fourth property of the large sets one of the colours \(C_{t_0}\) has to be large. Thus we have chosen the two elements with index \(0\), the first colour \(t_0\) and \(B_0=C_{t_0}\).
Now we apply the van der Waerden type theorem to obtain a number \(y_1\) such that $$D_1=B_0\cap(B_0-y_1) \text{ is large.}$$ Then, using property 5 of large sets, \(y_1 D_1\) is large, and then (by property 4) there is a colour \(t_1\) such that $$B_1=y_1 D_1\cap C_{t_1}\text{ is large}.$$ Thus we have constructed \(D_1\), \(y_1\), \(t_1\), and \(B_1\), we can assume that we have already constructed all \(B_j\), \(D_j\), \(y_j\) and \(t_j\) with \(1\le j\le n-1\) and we are going to construct the elements with index \(n\). Let \(F_n\) be the set formed by \(1\) and the products of the form $$y_j^2y_{j+1}^2\cdots y_{n-1}^2,\quad 1\le j\le n-1.$$ With this set \(F_n\), by the van der Waerden type theorem, we find \(y_n>y_{n-1}\) and such that $$D_n=B_{n-1}\cap\bigcap_{u\in F_n}(B_{n-1}-u y_n)$$ is large.
By the properties of large sets \(y_n D_n\) is large and we can choose a colour \(t_n\) such that $$B_n=y_n D_n \cap C_{t_n}\text{ is large.}$$ Note that by definition the elements of \(B_n\) have the colour \(t_n\). In this way we have constructed \(D_n\), \(y_n\), \(t_n\) and \(B_n\) and we are able to show the infinite \(\{a+b,ab\}\) monochromatic pairs.
Let’s note that, as we said, the construction proves that $$B_n \subset y_n D_n\subset y_n B_{n-1}.$$ In particular for \(m<n\) we will have $$B_n\subset y_{m+1}y_{m+2}\cdots y_n B_m.$$ There is only a finite number of colours, so for infinite pairs of natural numbers \(m<n\) we have \(t_m=t_n\), let’s take \(c\in B_n\) and put \(b=y_{m+1}\cdots y_n\), so that \(B_n\subset b B_m\). Then \(c\) is a multiple of \(b\) and we can define \(a=c/b\). Since \(c=ab\in B_n\) its colour is \(t_n\).
\(a\) has also colour \(t_n\) since $$ab\in B_n\subset b B_m,$$ then \(a\in B_m\) whose colour is \(t_m=t_n\). We will see now that also \(a+b\in B_m\). With this we finish, since the colour of \(a+b\) will be \(t_m=t_n\). Let’s note $$b(a+b)=c+b^2\in B_n+b^2\subset y_n D_n+b^2.$$ By its definition \(D_n\subset B_{n-1}-u y_n\) with \(u=y_{m+1}^2\cdots y_{n-1}^2\) (when \(m=n-1\) we must assume \(y_{m+1}^2\cdots y_{n-1}^2=1\), remembering that \(F_n\) contains the \(1\), one can also take \(m<n-1\), which is possible) we have $$y_nD_n +b^2\subset y_n(B_{n-1}-y_{m+1}^2\cdots y_{n-1}^2 y_n)+b^2.$$ We now use that \(B_n\subset y_{m+1}y_{m+2}\cdots y_n B_m\), $$b(a+b)\in y_n(y_{m+1}\cdots y_{n-1}B_{m}-y_{m+1}^2\cdots y_{n-1}^2 y_n)+b^2$$ $$= b B_{m}-b^2+b^2=b B_{m},$$ this is \(a+b\in B_m\) as said. Then we have proved that there exist infinite monochromatic \(\{a,a+b,ab\}\) triplets.
In Moreira’s own words, I don’t think I could have come up with this combinatorial proof without having previously used topological dynamics to prove it in the first place and without the earlier work with Bergelson.
Learn more
The paper published in Annals is freely downloadable from arXiv, it contains the simple proof we have included:
Joel Moreira, Monochromatic sums and products in \(\mathbf{N}\), Annals of Math. 185 (2017), 1069-1090.
A little earlier Ben Green and Tom Sanders have proved the theorem on \(F_p\), the prime field of \(p\) elements. Since here the set is finite they prove that a fraction of the \(c_rp^2\) ternaries are monochromatic, the constant \(c_r>0\) being dependent only on the number of colours.
Their proof is also free on the web:
Ben Green y Tom Sanders, Monochromatic sums and products, Discrete Analysis 2016:5 (48 pages).
The journal Discrete Analysis is an experiment in electronic journals. There is no publication but a page with a description of the work and its merit. The article rests on arXiv (with its own style that gives it a published feel). On the other hand, the journal has its review process and is of high quality. In addition, there are no (or minimal) costs for publishers. It is a model of what a mathematical publication should be. As we can see, the best mathematicians publish in it: Green is the one who, together with Tao, proved that primes contain arbitrarily long arithmetic progressions.
On the subject of mathematics and the combinatorics of colours (and despite my colour blindness), I cannot resist recommending here the book:
Alexander Soifer, The mathematical Coloring Book. Mathematics of Coloring and the Colourful Life of Its Creators, Springer, 2009.
It is a new kind of mathematical book. It exposes mathematics without forgetting the mathematicians who created it. It reads like a novel.
Leave a Reply