Worked solution: The polynomial method resolves the cap set problem (Croot-Lev-Pach, Ellenberg-Gijswijt, 2016)

Step 5 of 7: A dimension count turns the rank bound into a size bound

In plain words

To finish, Ellenberg and Gijswijt do not pick just one clever polynomial $P$ -- they look at the entire space of degree- $d$ polynomials that vanish outside $-A$ , which is large whenever $A$ is large, and squeeze it through the rank bound from Step 3 to get a direct algebraic inequality relating the sizes $m_d$ , $q^n$ and $|A|$ .

|A| \le 3\, m_{(q-1)n/3}

Detailed analysis

Ellenberg and Gijswijt (2017, proof of Theorem 4) let $V$ be the subspace of $S_n^{\le d}$ consisting of polynomials vanishing everywhere outside $-A$ ; since vanishing at each of the $q^n-|A|$ points outside $-A$ is one linear condition, $\dim V \ge m_d - (q^n-|A|)$ . By Step 4, every $P \in V$ automatically satisfies the hypothesis of Proposition 2 with $\alpha=\beta=\gamma=1$ , so Proposition 2 bounds how many points of $A$ can have $P(-a) \ne 0$ ; combining this with the dimension count on $V$ yields $m_d - q^n + |A| \le 2m_{d/2}$ , i.e. $|A| \le 2m_{d/2} + (q^n - m_d)$ . Choosing the optimal split $d = 2(q-1)n/3$ and using a symmetry of the monomial counts $m_d$ collapses this to the clean bound $|A| \le 3\, m_{(q-1)n/3}$ .