Julian's musings

I recently had the fun of reading Ellenberg and Gijswijt’s paper on the capset problem, where they bound the size of a subset of $\mathbb{F}_q^n$ with no three terms in arithmetic progression by $c^n$ with $c<q$.

The paper is beautifully written, and amazingly needs only relatively elementary undergraduate algebra. (It is generalised to the Galois field $\mathbb{F}_q$, but if we take $q$ to be prime, then even that is unnecessary to understand the argument.)

I was somewhat stuck on two small points at the start of the proof of Proposition 4, and thought I would share my realisation of the argument here for others’ benefit.

The first is the assertion in the first paragraph that “The space $V$ of polynomials in $S_n^d$ vanishing on the complement of $-\gamma A$ has dimension at least $m_d-q^n+|A|$”. For simplicity, write $B$ for the complement of $-\gamma A$, so $|B|=q^n-|A|$ (assuming that $\gamma\ne0$). Considering now the evaluation function $e:S_n\to \mathbb{F}_q^{\mathbb{F}_q^n}$ described before Proposition 2, we can look at the restriction $e_d$ of $e$ to $S_n^d$, and then take the restriction of the image of $e_d$ to $B$. In other words, if $p\in S_n^d$, then $e_d(p)$ is a function $\mathbb{F}_q^n\to\mathbb{F}_q$; we then take the restriction of this: $e_d(p)|_B$. This composition $e_d|_B$ therefore gives us a linear map $S_n^d\to\mathbb{F}_q^B$, from a vector space of dimension $m_d$ to one of dimension $|B|$. The required space $V$ vanishing on $B$ is the kernel of this linear map, which therefore has dimension at least $m_d-|B|$, as required.

The second point is the assertion in the next paragraph that if $|\Sigma|<\dim V$, then there is a non-zero $Q\in V$ vanishing on $\Sigma$. The argument for this is fairly similar. Let $p_1$, $p_2$, …, $p_k$ be a basis for $V$, where $k>|\Sigma|$. Then under the linear isomorphism $e$, the functions on $\mathbb{F}_q^n$ given by $e(p_1)$, …, $e(p_k)$ are linearly independent. But now restricting them to functions on $\Sigma$, a space of dimension $|\Sigma|$, necessarily gives a linear dependence between the restricted functions (as $k>|\Sigma|$). So this gives a non-trivial linear combination of these functions which will be zero on $\Sigma$ but is not the zero function on the whole of $\mathbb{F}_n^q$, as they are linearly independent in $V$.