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

Step 6 of 7: Counting monomials with large deviations: the constant

2.756

Previous step Next step

In plain words

All that remains is arithmetic: how many of the $3^n$ monomials actually have total degree at most $2n/3$ , out of a maximum possible degree of $2n$ ? Since each of the $n$ coordinates independently contributes degree $0$ , $1$ , or $2$ , this is exactly the probability that a sum of $n$ independent random digits falls below its usual average -- a classical large-deviations (Chernoff-type) computation.

3e^{-I(2/3)} < 2.756

Detailed analysis

Ellenberg and Gijswijt (2017, final computation) observe that $m_{(q-1)n/3}/q^n$ is exactly the probability that the sum of $n$ independent uniform random variables on $\{0,\ldots,q-1\}$ is at most $(q-1)n/3$ , i.e. far below its mean of $(q-1)n/2$ ; standard large-deviations theory gives $\lim_{n\to\infty} \frac{1}{n}\log(m_{(q-1)n/3}/q^n) = -I((q-1)/3)$ , where $I(x) = \sup_\theta \left(\theta x - \log\frac{1+e^\theta+\cdots+e^{(q-1)\theta}}{q}\right)$ is the Legendre-transform rate function of a single uniform digit. Plugging in $q=3,\ x=2/3$ for the cap-set case and optimising over $\theta$ yields the numeric bound $3e^{-I(2/3)} < 2.756$ .

Terms in this step

Large deviations / rate function: The theory of large deviations estimates the exponentially small probability that a sum of many independent random variables lands far from its average; the rate function $I(x)$ controls the exponent of that probability.