 Solution

Put $F=1_A\ast 1_A$. Then $0\le F\le 1$, $\mathbb{E}F={\alpha }^2$, and the Parseval identity givesSet $d=\lfloor {\alpha }^{2}n/(8p^2)\rfloor$. If $d<2$, the asserted integer lower bound is trivial. Otherwise take $q=d$ and $ϵ=3\alpha /(4p)$ in part b. The resulting subspace $W$ hasThus $\dim W\ge n/9>d$, and we may choose a $d$-dimensional subspace $D\le W$.

For $x\in D$, part b givesApply the supplied maximal inequality to $g(x,y)=F(y+x)-F(y)$. Since $|D{|}^{1/q}=p$, it givesHence some $y$ satisfies $F(y)>su{p}_{x\in D}|F(y+x)-F(y)|$, so $F(y+x)>0$ for every $x\in D$. Since $\mathrm{supp}F=A+A$, this proves