Write for the red-blue finite colouring of unordered pairs. The two alternatives concern one arithmetic progression or a pair of disjoint arithmetic progressions; they need not be mutually exclusive. For , a singleton already has no non-blue edge, so the first alternative holds. Assume henceforth .
If the first alternative fails, every -term arithmetic progression contains a red pair. Label each by one such pair's positions , choosing the first in a fixed ordering when there are several. This is a finite colouring with at most colours. The following two branches establish the arithmetic-progression bipartite Ramsey dichotomy.
For , give the pair the color determined by , where is the 2-adic valuation: use red for even valuation and blue for odd valuation. This finite coloring works because the pairs and have valuations and . They therefore have opposite colors. In particular, no three-term arithmetic progression has all its pairs monochromatic.
For the second assertion, is immediate: every singleton is a blue complete arithmetic progression, since it has no pairs to check. Assume . If some -term arithmetic progression has all its pairs blue, we are done. Otherwise, every such arithmetic progression contains a red pair. For each , choose, say lexicographically, indices for which is red, and color by this chosen pair . This is a finite coloring with at most colors.
We need a lattice pattern that works whichever pair becomes the common color. Fix, before applying the Gallai theorem for an integer lattice, the finite set
Translate into the positive quadrant and apply the Gallai theorem for an integer lattice to that translated pattern. Absorbing the translation into the base point gives integers and such that is monochromatic. Write for its common color. Since , the base point itself has positive coordinates.
For each , the parameter point
belongs to that monochromatic copy and has chosen red pair . Its red endpoints simplify to
Consequently, putting
gives two -term arithmetic progressions of positive common difference , with every cross-pair red. These arithmetic progressions really are disjoint: the parameter point corresponding to has positive second coordinate, so . Hence
This proves the arithmetic-progression bipartite Ramsey dichotomy, including the required disjointness.