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.