# Upperbounding a sum of Legendre-Symbols

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.

• Well, $c(p)<p$ is obvious, since $\vert\mathcal{I}\vert\vert\mathcal{J}\vert<p$. Commented Jul 25, 2018 at 23:21
• Thanks for pointing out, I should have double checked what I have written down. I meant to write that $c(p)/p>1/2$ with the exception of $p=7$. The fact that $c(p)/p>1/2$ essentially implies that there exists choices of $\mathcal{I}$ and $\mathcal{J}$ s.t. the differences of their elements are concentrated either on quadratic residues or quadratic non-residues. I was wondering if $c(p)/p>1/2$ would also hold for larger values of $p$. Commented Jul 26, 2018 at 1:23

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).