The Cap Set Problem

Abstract

In this paper we will take a look at bounds that are found on the cap set problem. We will especially discuss results from the article `Progression-free sets in Z^n_4 are exponentially small' by Croot, Lev and Pach and elaborate some of the proofs in this article. Before these specific results, we will extensively explain the idea of the cap set problem and show that the biggest cap set in the game Set with two attributes has size four. Besides that, we will give some background information on arithmetic progressions in different group settings. Moreover we will discuss entropy functions, the pigeonhole principle and the polynomial method, which play an important role in the work of Croot, Lev and Pach and the work of Ellenberg and Gijswijt, where they solve the classical cap set problem. Lastly we will take a look at the reasoning behind an improved construction of progression-free sets, where Elkin improves the best lower bound that was found in 1946 by Behrend.