You are currently browsing the tag archive for the ‘cap sets’ tag.

Earlier this month, in the previous incarnation of this page, I posed a question which I thought was unsolved, and obtained the answer (in fact, it was solved 25 years ago) within a week. Now that this new version of the page has better feedback capability, I am now tempted to try again, since I have a large number of such questions which I would like to publicise. (Actually, I even have a secret web page full of these somewhere near my home page, though it will take a non-trivial amount of effort to find it!)

Perhaps my favourite open question is the problem on the maximal size of a cap set – a subset of ${\Bbb F}^n_3$ (${\Bbb F}_3$ being the finite field of three elements) which contains no lines, or equivalently no non-trivial arithmetic progressions of length three. As an upper bound, one can easily modify the proof of Roth’s theorem to show that cap sets must have size $O(3^n/n)$ (see e.g. this paper of Meshulam). This of course is better than the trivial bound of $3^n$ once n is large. In the converse direction, the trivial example $\{0,1\}^n$ shows that cap sets can be as large as $2^n$; the current world record is $(2.2174\ldots)^n$, held by Edel. The gap between these two bounds is rather enormous; I would be very interested in either an improvement of the upper bound to $o(3^n/n)$, or an improvement of the lower bound to $(3-o(1))^n$. (I believe both improvements are true, though a good friend of mine disagrees about the improvement to the lower bound.)