Cap-set status and a sharp quadratic-graph dimension barrier

Definitions and mathematical statement

Let $r\ge1$ and let $\mathbb F_3^r$ be the $r$-dimensional vector space over the field of three elements. An affine line has the form \[ \{x,x+d,x+2d\},\qquad d\ne0, \] with $x,d\in\mathbb F_3^r$. It has exactly three distinct points. A cap set is a subset containing no such line. Since the characteristic is three, this is equivalently the condition that $x+y+z=0$ with $x,y,z\in A$ has no solution with three distinct entries; any solution with two equal entries has all three equal.

Define \[ M(r)=\max\{|A|:A\subseteq\mathbb F_3^r, A\text{ contains no affine line}\}. \] The problem asks for the largest possible cap-set size, as a function of dimension, including sharp asymptotic estimates as $r\to\infty$. The maximum is over arbitrary subsets, not just subspaces, graphs of functions, or sets invariant under a specified symmetry group. A fundamental asymptotic parameter is the exponential growth rate $\sup_{r\ge1}M(r)^{1/r}$: Cartesian products of cap sets are cap sets, so $M(r+s)\ge M(r)M(s)$ and the corresponding root limit exists. Determining this rate is one precise aspect of determining the growth of $M(r)$; it is weaker than an exact formula in every dimension. Exponential upper bounds alone do not specify the optimal rate or resolve the full extremal question posed by the workshop.

Short English statement

Determine the maximum number of points in a vector space over the three-element field with no three on an affine line.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001088 (AIM-COMBINATORICS-0213), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, Recent trends in additive combinatorics, item 1.7. Original workshop question underlying AIM-COMBINATORICS-0213. https://aimath.org/WWN/additivecomb/additivecomb.pdf.