Composite Ramsey theorems via trees

Composite Ramsey theorems via trees, Discrete Analysis 2026:4, 17 pp.

A famous unsolved problem in Ramsey theory, asked by Neil Hindman, is the question of whether if the natural numbers are finitely coloured, one can find x and y such that x , y , x + y and x y all have the same colour. The problem turns out to be hard even if one asks merely for x + y and x y to have the same colour, but a 2016 breakthrough of Moreira showed that one can ensure the stronger result that x, x+y and xy have the same colour.

Returning to the weaker result, let us call a pair { x , y } good for a colour c if x + y and x y both have colour c . Moreira’s result implies that good pairs exist, but it is natural to wonder whether we can find a colour C such that the pairs that are good for C form a graph that is rich in some suitable sense. For example, must there be a colour such that the corresponding graph contains a 4-cycle?

This question, which was among several questions asked by Kra, Moreira, Richter and Robertson, is equivalent to asking for x 1 , x 2 , y 1 and y 2 such that all x i + y j and all x i y j have the same colour. They expressed the view that the problem was probably out of reach of current techniques.

This paper proves a rather general result that gives as a consequence a positive answer to a considerable strengthening of the 4-cycle question. One can in fact find a colour C , an infinite set A , and an arbitrarily large finite set B such that a + b and a b have colour C for all a ∈ A and b ∈ B .

To achieve this, the author develops a mechanism for boosting existing Ramsey results. Suppose we have a family B that we already know to be Ramsey, meaning that for every finite colouring of the natural numbers there is a monochromatic set B that belongs to B . If this family has certain other properties identified in the paper, then the paper concludes that for every finite set P of polynomials with integer coefficients and every finite colouring of the natural numbers there exists a colour C and an infinite set A and a set B ∈ B such that for every a ∈ A , every b ∈ B and every p ∈ P all of a , a + b and a + p ( b ) have colour C .

The properties required of B for this conclusion to hold are satisfied by the families that are provided by well-known Ramsey results such as Rado’s theorem and its obvious multiplicative analogue. Also, from the boosting result above, one can obviously deduce the same result where A is required to have size m for some fixed finite m : the resulting Ramsey family has the required property if B does.

By iterating this boosting operation, one can obtain a wide variety of results. One particularly appealing consequence, obtained by looking at sets of size 1, is that given any finite colouring of N and any r , one can find positive integers a 1 , … , a r such that every number a 1 ∘ 1 ( a 2 ∘ 2 ( … ( a r − 1 ∘ r − 1 a r ) … ) , where each operation ∘ i is either addition or multiplication, has the same colour. For example, if r = 3 , then this tells us that we can find a , b and c such that a + ( b + c ) , a + b c , a ( b + c ) and a b c all have the same colour.

There are also some attractive questions left open in the paper. For example, the result just described concerns compositions of addition and multiplication for which one associates to the right. But for different bracketing we still do not know what happens. The first case that cannot be deduced from the result above is whether one can find a , b , c , d such that all eight numbers of the form ( a ∘ 1 b ) ∘ 2 ( c ∘ 3 d ) have the same colour.

The proof uses the colour-focusing method but along trees rather than sequences, hence the title of the paper. As with Moreira’s argument, and with other papers in the general area of Ramsey theorems that involve sums and produts, one of the main external tools (which can also be proved using colour-focusing, as was shown by Walters), is the polynomial van der Waerden theorem of Bergelson and Leibman.