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

Piecewise syndetic sets are partition regular<\/em>:<\/p>\n

Claim.<\/strong> If is piecewise syndetic then either or is. (This extends to partitions into more parts by induction.)<\/p>\n

Proof.<\/em> Choose intervals of length on which the gaps in are bounded by . Suppose that is not piecewise syndetic. Then for every there is an such that has a gap more than points wide. So contains an interval of length on which its gaps are bounded by . <\/p>\n

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.<\/p>\n

Claim.<\/strong> If is piecewise syndetic, then it contains long APs.<\/p>\n

Proof.<\/em> If has long intervals with gaps bounded by , then the union of the translates of contains long intervals. So can be viewed as a -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 , so contains long APs. <\/p>\n

In fact we can say much more: for every there is a such that the set of such that the AP of length and common difference starting at is contained in is piecewise syndetic. To see this, let be a block of consecutive integers sufficiently long that whenever it is -coloured it contains an AP of length . Pack translates of greedily into the intervals in . For each translate of there is a triple such that contains the AP of length and common difference starting at . Now the set of is piecewise syndetic (it has long intervals with gaps bounded by ). And there are only finitely many choices for (at most ) and (at most ). So by the first claim there is some choice of such that the corresponding are piecewise syndetic. That is, the set is piecewise syndetic. This is Theorem 5.1 in Moreira’s paper, with and . The case of general follows by taking .<\/p>\n","protected":false},"excerpt":{"rendered":"

Joel Moreira\u00a0has just proved that\u00a0whenever the natural numbers are finitely coloured we can find and such that , and are all the same colour. \u00a0He 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 … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[30],"_links":{"self":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/14"}],"collection":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/comments?post=14"}],"version-history":[{"count":0,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/14\/revisions"}],"wp:attachment":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/media?parent=14"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/categories?post=14"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/tags?post=14"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}