Piecewise syndetic and van der Waerden

Joel Moreira has just proved that whenever the natural numbers are finitely coloured we can find $x$ and $y$ such that $x$ , $x+y$ and $xy$ are all the same colour. He actually proves a much more general result via links to topological dynamics, but he includes a direct proof of this special case assuming only a consequence of van der Waerden’s theorem related to piecewise syndetic sets. I want to record the details here so that I remember them in future.

Syndetic, thick and piecewise syndetic

A set of natural numbers is thick if it contains (arbitrarily) long intervals, and syndetic if it has bounded gaps. It is piecewise syndetic if it has bounded gaps on long intervals (the same bound for each interval).

Piecewise syndetic sets are partition regular:

Claim. If $S = A \cup B$ is piecewise syndetic then either $A$ or $B$ is. (This extends to partitions into more parts by induction.)

Proof. Choose intervals $I_n$ of length $n$ on which the gaps in $S$ are bounded by $c$ . Suppose that $A$ is not piecewise syndetic. Then for every $d$ there is an $n_d$ such that $A \cap I_{n_d}$ has a gap more than $d$ points wide. So $B \cap I_{n_d}$ contains an interval of length $d$ on which its gaps are bounded by $c$ . $\ \Box$

It follows that, whenever the natural numbers are finitely coloured, one of the colour classes is piecewise syndetic. So to prove van der Waerden’s theorem it would suffice to show that every piecewise syndetic set has long arithmetic progressions. We’ll prove this apparent strengthening, assuming van der Waerden’s theorem itself.

Claim. If $S$ is piecewise syndetic, then it contains long APs.

Proof. If $S$ has long intervals with gaps bounded by $c$ , then the union of the $c$ translates $S+1, \ldots, S+c$ of $S$ contains long intervals. So $S+1, \ldots, S+c$ can be viewed as a $c$ -colouring of a set of long intervals, hence one of them contains long APs by van der Waerden’s theorem. But they are all translates of $S$ , so $S$ contains long APs. $\ \Box$

In fact we can say much more: for every $k$ there is a $d$ such that the set of $a$ such that the AP of length $k$ and common difference $d$ starting at $a$ is contained in $S$ is piecewise syndetic. To see this, let $B$ be a block of consecutive integers sufficiently long that whenever it is $c$ -coloured it contains an AP of length $k$ . Pack translates of $B$ greedily into the intervals in $S+1, \ldots, S+c$ . For each translate $B_i$ of $B$ there is a triple $(a_i, d, j)$ such that $B_i \cap S_j$ contains the AP of length $k$ and common difference $d$ starting at $a_i$ . Now the set of $a_i$ is piecewise syndetic (it has long intervals with gaps bounded by $2|B|$ ). And there are only finitely many choices for $d$ (at most $|B|/(k-1)$ ) and $j$ (at most $c$ ). So by the first claim there is some choice of $(d,j)$ such that the corresponding $a_i$ are piecewise syndetic. That is, the set $S \cap (S - d) \cap \cdots \cap (S-(k-1)d)$ is piecewise syndetic. This is Theorem 5.1 in Moreira’s paper, with $F = [k]$ and $n = d$ . The case of general $F$ follows by taking $k = \max F$ .

Syndetic, thick and piecewise syndetic

Leave a Reply Cancel reply