Constructions for the cap set problem

Abstract

The objective of the cap set problem is finding the maximum size of a d-cap: a subset of  𝔽3d not containing three elements in line. This thesis aims to give a comprehensive overview of constructions for the cap set problem, with a focus on improvements of the asymptotic lower bound on the size of caps that have already been made.

Finding an asymptotic lower bound on the size of caps boils down to finding a cap C in a dimension d such that its solidity, given by |D|1/d, is as large as possible. We start with studying caps in low dimensions, of which the maximum sizes are exactly known. Then to further improve the asymptotic lower bound we turn to caps in higher dimensions. Here, the art lies in carefully combining large caps in low dimensions to construct large caps in higher dimensions by taking products. One construction that allows us to do this is the extended product construction, which extends extendable collections of caps with admissible sets.

This thesis explains the extended product construction and gives an overview of how it has been used and expanded to repeatedly increase the asymptotic lower bound. As the literature sometimes lacks detail, this thesis adds to the literature by incorporating examples, explicit constructions of (recursively) admissible sets, and experiments with the extended product construction.

In Chapter 6, we prove the existence of recursively admissible sets of constant weight 2 and 3 for any dimension k by giving explicit constructions and proving that the resulting sets satisfy all necessary conditions. Moreover, we classify all admissible sets in dimensions 2 and 3 and all extendable collections in dimensions 1, 2, and 3. Then, we use these to deduce that the extended product construction is less effective in low dimensions by showing that the largest possible caps we can construct this way in dimensions 4, 6, and 8 are never as large as caps constructed by taking direct products of maximum caps.