Upperbounding a sum of Legendre-Symbols

Question

Let $p$ be a prime with $p\equiv 3 \mod 4$, for any $\mathcal{I} \subset \lbrace 0,...,p-1 \rbrace $ and any $\mathcal{J} \subset \lbrace 0,...,p-1 \rbrace $ with $\vert\mathcal{I}\vert \leq \sqrt{p} $ and $\vert\mathcal{J}\vert \leq \sqrt{p} $, I am looking for an upperbound on the following expression \begin{align*} \left\vert \sum _{i\in\mathcal{I}} \sum _{j\in\mathcal{J}} \left( \frac{i-j}{p} \right) \right\vert \leq c(p) \end{align*} Where $\left( \frac{a}{p} \right) $ is the Legendre Symbol defined by \begin{align*} \left( \frac{a}{p} \right) = \begin{cases} 1 &\quad \text{ if } a \text{ is a quadratic residue modulo } p \text{ and } a \not\equiv 0 \mod p \\ -1 &\quad \text{ if } a \text{ is a quadratic non-residue modulo } p \\ 0 &\quad \text{ if } a \equiv 0 \mod p \end{cases} \end{align*} Essentially I am looking for some expression for $c(p)$.

Some brute force attempts I have calculated on MATLAB in small dimensions suggest that for $p>7$ holds $c(p)/p > 1/2$, explicitly the values are for $p=7 \;,\; c(p) = 3 $, for $p=11 \; ,\; c(p) = 6$, for $p=19 \; ,\; c(p) = 12 $ and for $p=23 \; , \; c(p) = 13 $.

I could prove that when $\vert\mathcal{I}\vert >\sqrt{p}$ and $\vert\mathcal{J}\vert > \sqrt{p} $ then $\left\vert \sum _{i\in\mathcal{I}} \sum _{j\in\mathcal{J}} \left( \frac{i-j}{p} \right) \right\vert < \vert\mathcal{I}\vert\vert\mathcal{J}\vert $. But this doesn't really help.

Answer 1

If $A$ and $B$ are two subsets of ${\Bbb Z}/p{\Bbb Z}$ with $|A|$ and $|B|$ being bigger than $p^{\alpha}$ (for some $\alpha>0$) then one expects that $$ \Big| \sum_{a\in A} \sum_{b\in B} \chi(a+b) \Big| \le p^{-\delta} |A||B|, $$ for some $\delta >0$ (depending only on $\alpha$). Here $\chi$ denotes a non-principal character $\pmod p$. We are very far from knowing anything like this. Writing the multiplicative character in terms of additive characters, and then using Cauchy--Schwarz, one can show that $$ \Big| \sum_{a\in A} \sum_{b\in B} \chi(a+b) \Big| \le \sqrt{p |A||B|}, $$ which is useful when $|A||B| >p$. In general, this is the best bound known. Improving it even by a constant factor would have a nice consequence: a conjecture of Sarkozy asserts that the set of quadratic residues $\mod p$ cannot be expressed as the sumset $A+B$ where $A$ and $B$ both have size at least $2$. Amazingly, even this very weak conjecture is unknown. For recent work on this problem (generalized to sumsets involving three or four sets), and references to related work, see this paper of Brandon Hanson (which appeared in Acta Arith). There are a couple of situations in which non-trivial bounds are known: when $A$ is an interval (this is due to Friedlander and Iwaniec), and when $A$ has small doubling (due to Chang).