Monochromatic Sums and Products of Polynomials

Monochromatic sums and products of polynomials, Discrete Analysis 2024:5, 7 pp.

An early result in Ramsey theory, Schur’s theorem, states that if the positive integers are finitely coloured, then there will always be $x$ and $y$ such that $x,y$ and $x+y$ have the same colour. It follows easily (e.g. by restricting to powers of 2) that there will also be $x$ and $y$ such that $x, y$ and $xy$ have the same colour. A famous open problem is whether the two are guaranteed to happen simultaneously – that is, must there always be $x$ and $y$ such that $x,y,x+y$ and $xy$ all have the same colour?

Even weaker versions of this question are far from trivial: for instance, it was for a long time not known whether one could even find $x$ and $y$ such that $x+y$ and $xy$ have the same colour. (This question can be reformulated graph theoretically. Form a graph by joining two integers $m$ and $n$ if there exist positive integers $x$ and $y$ such that $x+y=m$ and $xy=n$, or equivalently if the quadratic equation $x^2-mx+n$ has a solution in positive integers. Then the question is equivalent to asking whether this graph has infinite chromatic number.) This weaker question was finally answered by Joel Moreira in 2016 using methods from topological dynamics: in fact he proved that one can find $x$ and $y$ such that $x, x+y$ and $xy$ all have the same colour.

More recently there has been interesting further progress. In 2022, Matt Bowen and Marcin Sabok proved the full conjecture for the rationals: that is, if the rationals are finitely coloured then one can find $x,y,x+y$ and $xy$ all of the same colour. (It is recommended to spend a bit of time trying to deduce the integer statement from this, just to understand why it does not straightforwardly follow.) Also in 2022, Matt Bowen obtained a positive answer to the problem for 2-colourings. More precisely, he showed that if the integers are 2-coloured, then one can find infinitely many pairs $(x,y)$ of distinct integers such that $x,y,x+y$ and $xy$ have the same colour. (Merely proving that one such pair exists can be done by a brute-force search.)

This paper proves a similar result to Moreira’s, but with the integers replaced by the semigroup of polynomials with non-negative integer coefficients and zero constant term. By a standard compactness argument, one can deduce from this that for a given number of colours there will exist $M$ such that the result is true for polynomials of degree at most $M$ and with coefficients of size at most $M$ (though in fact the paper provides explicit bounds). If we evaluate these polynomials for a sufficiently large $n$, all their values will be distinct, from which we readily see that this polynomial result implies the integer one. (In fact, this argument also shows that in principle the two-colour case discussed above can be solved by brute force, since a solution to the polynomial version yields infinitely many solutions to the integer version, but it is not clear that this can be done in practice, and it was not Bowen’s approach.)

However, Moreira’s proof for the positive integers made essential use of the structure of the integers, so the result for polynomials requires new ideas. A key element of Moreira’s argument was the use of the following equivalent version of van der Waerden’s theorem. A set $A$ of integers is called syndetic if it has bounded gaps: that is, if there exists $k$ such that for every $n$, the intersection $A\cap\{n,n+1,\dots,n+k-1\}$ is non-empty. It is called piecewise syndetic if it has bounded gaps in arbitrarily long intervals: that is, there exists $k$ such that for all $m$ there exists an interval $I$ of length $m$ such that $A\cap\{n,n+1,\dots,n+k-1\}$ is non-empty for every $n\in I$. It is an easy exercise to show that if a piecewise syndetic set is finitely coloured, then one of the colour classes is piecewise syndetic. It is also an easy exercise to show that van der Waerden’s theorem is equivalent to the statement that every piecewise syndetic set contains arbitrarily long arithmetic progressions.

Instead of relying on the piecewise syndetic version of van der Waerden’s theorem, this paper uses the polynomial van der Waerden theorem, which is the following famous result of Bergelson and Leibman.

Theorem. Let $P_1,\dots,P_k$ be polynomials with integer coefficients and zero constant term. Then for every finite colouring of the natural numbers there exist $a$ and $d\ne 0$ such that all of $a, a+P_1(d),\dots,a+P_k(d)$ have the same colour.

Using this result (or rather a known generalization of it from $\mathbb N$ to arbitrary semigroups) has a number of advantages. One is that, as we have already remarked, it leads to a more general result. Another is that, at least if one is prepared to take the polynomial van der Waerden theorem on trust, it yields a surprisingly short proof. A third is that the author has used this basic idea to obtain further results, such as that over the rationals one can find an arbitrary number of distinct elements $x_1,\dots,x_k$ such that all $x_i, x_i+x_j$ and $x_ix_j$ (with $i\ne j$) have the same colour. And a final potential bonus is that the polynomial van der Waerden theorem is iterated in a gentler way and therefore provides primitive recursive bounds, though for this conclusion one must rely on an unpublished paper of Shelah, in which he shows that his approach to obtaining primitive recursive bounds for the Hales-Jewett theorem can be generalized to give primitive recursive bounds for the polynomial Hales-Jewett theorem, and it is not clear to what extent that paper has been carefully checked.