Large sums of quadratic residues Let $p \equiv 3 \pmod{4}$ be prime, and define
$$
f(p)=\sum_{m=1}^{\frac{p-1}{2}}\sum_{n=1}^{\frac{p-1}{2}}\left(\frac{m+n-\frac{p+1}{4}}{p}\right),
$$
where $\left(\frac{a}{p}\right)$ denotes the Legendre symbol (i.e. +1,-1,0, depending on whether $a$ is a quadratic residue/non-residue/zero).
The construction of $f(p)$ is admittedly artificial and was essentially done by trial-and-error to create a "large" f(p). What I'm interested in showing (which I'm not even sure is true) is that
$$
f(p) = \Theta(p \sqrt{p}).
$$
Now, I've programmatically computed $f(p)$ for all $p < 50000$, and it is from this that I'm conjecturing
$$
\frac{p \sqrt{p}}{6} \le f(p) \le \frac{p \sqrt{p}}{4}.
$$
In particular, it is the lower bound that I'm actually interested in (though the upper bound might also be interesting in its own way), since I would have expected $f(p)$ to be close to zero.
More generally, are there any papers that research something similar to this? The closest things I can find are related to clique numbers of Paley graphs, or the smallest quadratic non-residue, but neither of these seem to relate directly to this question.
 A: What an interesting question! The following is just an observation on rewriting the sum, not an answer. For $i\in\{0,1,\dots,p-1\}$, let $$a(i)=|\{(m,n)\in \{1,\dots,(p-1)/2\}^2| m+n-(p+1)/4\equiv i \bmod p\}|.$$ We may check that for sufficiently large $p$, $p\equiv 3\bmod 4$, $a(i)$ takes the value of $(p-3)/4$ at $0$, then increases by $1$ at each subsequent value until it attains a maximum value of $(p-1)/2$ at $(p+1)/4$. Then it decreases by $1$ until it reaches $0$ at some value, takes $0$ again at the next value, then increases by $1$ until it reaches $(p-7)/4$ at $(p-1)$. Therefore by the properties of the Legendre symbol your sum is equal to
$$
\sum_{i=0}^{(p-3)/4}2i\left(\frac{i}{p}\right)+((p-1)/2)\left(\frac{(p+1)/4}{p}\right)+\sum_{i=(p+5)/4}^{(p-1)/2}\left((p-1)/2-2-2(i-(p+5)/4)\right)\left(\frac{i}{p}\right).
$$ 
Let $h(-p)$ be the class number of the imaginary quadratic field $\mathbb{Q}[\sqrt{-p}]$, $p\equiv 3 \bmod 4$. By Dirichlet, we know that
$$
h(-p)\left(2-\left(\frac{2}{p}\right)\right)=\sum_{i=1}^{(p-1)/2}\left(\frac{i}{p}\right).
$$
From what is known on upper and lower bounds on these class numbers, and since in the considered sum the coefficients of the Legendre symbols take the form specified, perhaps it gives insight relevant to your observation.
