= Solution
A sufficient absolute constant is $\boxed{C=16}$. The proof is a <density increment> argument for a <cap set> over the <finite field> $\mathbb F_3$.
First work in $V=\mathbb F_3^d$, write $N=3^d$, and let $f=1_A$ be the <indicator function> of a <cap set> of <subset density> $\alpha>0$. All <expectations> below are uniform. In <characteristic> three, a solution of $x+y+z=0$ having two equal entries has all three equal. Consequently the normalized <linear configuration count> is
$$
T=\mathbb E_{x,y}f(x)f(y)f(-x-y)=\frac{|A|}{N^2}=\frac\alpha N.
$$
Set $\omega=e^{2\pi i/3}$ and use <Fourier analysis on a finite abelian group> with
$$
\widehat f(\xi)=\mathbb E_x f(x)\omega^{-\xi\cdot x}.
$$
The <orthogonality of roots of unity> and the <Parseval identity on a finite group> give
$$
T=\sum_{\xi\in V}\widehat f(\xi)^3,
\qquad
\widehat f(0)=\alpha,
\qquad
\sum_{\xi\ne0}|\widehat f(\xi)|^2=\alpha-\alpha^2.
$$
If $N\alpha^2\geq2$, then $\alpha<1$ for a <cap set> and
$$
\frac{\alpha^3}{2}
\leq\alpha^3-\frac\alpha N
\leq\sum_{\xi\ne0}|\widehat f(\xi)|^3
\leq\left(\max_{\xi\ne0}|\widehat f(\xi)|\right)(\alpha-\alpha^2).
$$
Thus some nonzero <finite abelian Fourier coefficient> has magnitude at least $\alpha^2/2$.
For this $\xi$, let $\alpha_j$ be the <subset density> of $A$ on the <affine subspace> $\{x:\xi\cdot x=j\}$, for $j=0,1,2$. These three <affine subspaces> have equal <cardinality>, and
$$
\alpha=\frac{\alpha_0+\alpha_1+\alpha_2}{3},
\qquad
\widehat f(\xi)=\frac13\sum_{j=0}^2\alpha_j\omega^{-j},
\qquad
\alpha_j-\alpha=2\operatorname{Re}\bigl(\widehat f(\xi)\omega^j\bigr).
$$
Among three directions separated by $2\pi/3$, one makes an angle at most $\pi/3$ with any given complex number. Hence $\max_j(\alpha_j-\alpha)\geq|\widehat f(\xi)|$. Restricting to that <hyperplane> gives the <hyperplane density increment for cap sets>
$$
\alpha'\geq\alpha+\frac{\alpha^2}{2},\qquad d'=d-1.
$$
Translate the <affine subspace> to its underlying <vector space>. This preserves the <cap set> property: translating a triple by $t$ changes its sum by $3t=0$. The same argument can therefore be iterated.
For completeness, the <density increment> iteration gives an explicit uniform bound. If $n<16$, the hypothesis $\alpha\geq16/n$ is impossible. Suppose $n\geq16$ and a <cap set> has $\alpha_0\geq16/n$. For every integer $0\leq t\leq\lfloor n/2\rfloor$, its remaining <dimension> is at least $n/2$, and its current <subset density> is at least $16/n$. Thus
$$
3^{n-t}\alpha_t^2\geq3^{n/2}\frac{256}{n^2}\geq2.
$$
The last inequality holds at $n=16$ and remains true as $n$ increases: the successive ratio of $3^{n/2}/n^2$ is $\sqrt3\,(n/(n+1))^2>1$ for $n\geq16$. At each step, as long as the <subset density> remains at most one,
$$
\frac1{\alpha_t}-\frac1{\alpha_{t+1}}
\geq\frac1{2+\alpha_t}\geq\frac13.
$$
After $L=\lfloor n/2\rfloor$ steps this would imply
$$
0<\frac1{\alpha_L}\leq\frac n{16}-\frac L3<0,
$$
a contradiction. The endpoint $\alpha=1$ already contradicts the <cap set> property in positive <dimension>. This proves the claimed existence of three distinct points and the <Meshulam bound for cap sets>.
Back to article page
