The cap set conjecture is true: the size of any cap set in F_3^n is o(2.756^n)

You need to know: Addition modulo 3, vectors, notation |A| for the number of elements in finite set A, small o notation.

Background: Let {\mathbb F}_3 be the set \{0,1,2\} with addition defined modulo 3. Let {\mathbb F}_3^n be the set of n-component vectors x=(x_1, \dots, x_n) with each x_i \in {\mathbb F}_3, and with addition defined component-wise. We say that three different points x,y,z\in {\mathbb F}_3^n form a line if x+y=z+z. A set A \subseteq {\mathbb F}_3^n is called a cap set if it contains no lines.

The Theorem: On 30th May 2016, Jordan Ellenberg and Dion Gijswijt submitted to arxiv a paper in which they proved that if A \subseteq {\mathbb F}_3^N is a cap set, then |A|=o(2.756^n).

Short context: What can the maximal size of a cap set in {\mathbb F}_3^n? This problem is interesting in its own, but also studied because of hope that methods to solve it may be useful for the similar problem of finding dense sets of integers without 3-term arithmetic progressions, see here. A cap set conjecture predicted the existence of constant c<3 such that |A|<c^n for every cap set A \subseteq {\mathbb F}_3^n. The Theorem confirms this conjecture, building on an earlier similar result for subsets of {\mathbb Z}_4^n. Before 2016, the best upper bound was |A|\leq C\frac{3^n}{n^{1+\epsilon}}, see here.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

One thought on “The cap set conjecture is true: the size of any cap set in F_3^n is o(2.756^n)

Leave a comment