Extractors in Paley graphs: a random model

Rudi Mrazović

Published 2015-10-20Version 1

A well-known conjecture in analytic number theory states that for every pair of sets $X,Y\subset\mathbb{Z}/p\mathbb{Z}$, each of size at least $\log ^C p$ (for some constant $C$) we have that for $(\frac12+o(1))|X||Y|$ of the pairs $(x,y)\in X\times Y$, $x+y$ is a quadratic residue modulo $p$. We address the probabilistic analogue of this question, that is for every fixed $\delta>0$, given a finite group $G$ and $A\subset G$ a random subset of density $\frac12$, we prove that with high probability for all subsets $|X|,|Y|\geq \log ^{2+\delta} |G|$ for $(\frac12+o(1))|X||Y|$ of the pairs $(x,y)\in X\times Y$ we have $xy\in A$.