Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 12 1 Solution Created 2026-10-03 Updated 2026-10-14
We take and require the common difference of an arithmetic progression to be positive. An ultrafilter is a proper filter on a set deciding each subset: exactly one of and belongs to .
For the fixed length , let be the family of sets containing no m-term arithmetic progression. Any acceptable ultrafilter must contain every complement with . These mandatory sets have the finite intersection property. Otherwise finitely many would cover . Colour an integer by the first for which it belongs to . The Van der Waerden theorem gives a monochromatic m-term arithmetic progression, contained in the corresponding , a contradiction.
Generate a proper filter from those complements and extend it by the ultrafilter lemma. If some were in , its complement would also belong to , forcing the empty set into the filter. ThusNotice that sets avoiding one fixed length need not be closed under finite unions; the argument uses the finite intersection property, not an unsupported ideal claim.
For the unbounded-length version, let consist of sets whose arithmetic progression lengths are bounded. Each fails to contain a progression of some length , and hence of every greater length. If finitely many covered , colour by the first containing index and apply the Van der Waerden theorem at length . Again a contradiction results. The complements of all members of therefore have the finite intersection property. Extending their generated filter gives an ultrafilter with arithmetic-progression-rich members:All finite sets lie in , so this ultrafilter contains every cofinite set and is a nonprincipal ultrafilter. The same is true of the fixed-length construction when , because no singleton is allowed; for a principal ultrafilter also works. These constructions illustrate ultrafilter selection from a partition-rich family.
The infinite-length answer is no. Colour by , so successive intervals alternate colours. An infinite arithmetic progression , , meets every sufficiently large such interval: its first term at least is less than , which is at most once . It therefore has terms of both colours. Neither colour class contains an infinite arithmetic progression, but every ultrafilter contains one of the two colour classes. This dyadic block obstruction to infinite arithmetic progressions rules out the proposed ultrafilter.
An ultrafilter on the positive integers with every member containing finite arithmetic progressions of arbitrarily large length. The Van der Waerden theorem and ultrafilter selection from a partition-rich family give existence. Such an ultrafilter must contain the complement of every set with bounded arithmetic-progression length, and it is a nonprincipal ultrafilter. No corresponding ultrafilter can have an infinite arithmetic progression in every member, by the dyadic block obstruction to infinite arithmetic progressions.