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.



Upperbounding a sum of Legendre-Symbols
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](https://arxiv.org/pdf/1509.04354.pdf) (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).


