Prove an inequality related to sums of Legendre symbols $\newcommand\Legendre{\genfrac(){}{}}$Let  $p\equiv 1\pmod 4$ be a prime number, and $x_{i}\ge 0$ be such that $$x_{1}+x_{2}+\dotsb+x_{p}=1.$$
Show that
$$\sum_{1\le i<j\le p}\Legendre{i-j}{p}x_{i}x_{j}\le\dfrac{p-1}{2p+6}$$
Here $\Legendre\cdot\cdot$ is the Legendre symbol.
This problem was encountered by a  colleague of mine when he was writing a paper, and we couldn't  prove this inequality. So I ask it. We found  the constant in the right-hand side seems to be the best one because when  $p = 5$ it can be reached:
$$p=5,x_{1}=x_{2}=0.5,x_{3}=x_{4}=\dotsb=0.$$
 A: $\newcommand\Legendre{\genfrac(){}{}}$We have $$\sum_{1\le i<j\le p}\Legendre{i-j}{p}x_{i}x_{j} \leq \frac{k-1}{2k }$$ where $k$ is the size of the largest clique in the Paley graph, and this is sharp.
Indeed, if the number of $i$ such that $x_i>0$ is at most $k$ then
$$\sum_{1\le i<j\le p}\Legendre{i-j}{p}x_{i}x_{j} \leq \sum_{1\le i<j\le p}x_{i}x_{j} = \frac{1}{2} \sum_{i \neq j} x_i x_j =\frac{1 - \sum_i x_i^2}{2}   \leq  \frac{ 1- k^{-1}}{2} = \frac{k-1}{2k }$$
by Cauchy-Schwarz.
Otherwise, there exist $i_1,i_2 $ with $\Legendre{i_1-i_2}{p} = -1$ and $x_{i_1},x_{i_2}>0$. Without loss of generality, we may assume $$\sum_{j \neq i_1} \Legendre{ i_1 - j}{p} x_j \geq \sum_{j \neq i_2} \Legendre{ i_2 - j}{p} x_j.$$
Let $y_j = x_j$ for $j\not\in\{i_1, i_2\}$, let $y_j = x_{i_1} + x_{i_2} $ for $j=i_1$, and let $y_j=0$ for $j =i_2$. Then $\sum_j y_j = \sum_j x_j=1$ and the number of nonzero $y_j$ is at most the number of nonzero $x_j$. Now, using the $i\neq j$ sum which is twice as large as the $i<j$ sum but much easier to work with, we have
$$\sum_{1\leq i,j \leq p, i \neq j }\Legendre{i-j}{p}y_{i}y_{j} $$ $$= \sum_{1\leq i,j \leq p, i \neq j }\Legendre{i-j}{p}x_{i}x_{j}  +  2\sum_{1 \leq j \leq p, j \neq i_1}\Legendre{i_1-j}{p}(y_{i_1}-x_{i_1}) x_{j}   +  2\sum_{1 \leq j \leq p, j \neq i_2}\Legendre{i_2-j}{p}(y_{i_2}-x_{i_1}) x_{j} + 2 \Legendre{ i_1 i_2}{p} (y_{i_1} - x_{i_1} ) (y_{i_2} -x_{i_2}) $$
$$= \sum_{1\leq i,j \leq p, i \neq j }\Legendre{i-j}{p}x_{i}x_{j}  +  2\sum_{1 \leq j \leq p, j \neq i_1}\Legendre{i_1-j}{p} x_{i_2}  x_{j}   -  2\sum_{1 \leq j \leq p, j \neq i_2}\Legendre{i_2-j}{p}x_{i_2}  x_{j} - 2 \Legendre{ i_1 i_2}{p} x_{i_2}^2 $$
$$ > \sum_{1\leq i,j \leq p, i \neq j }\Legendre{i-j}{p}x_{i}x_{j} .$$
Thus, we have increased your sum while reducing the number of nonzero $x_i$'s. We may keep doing this until the number of nonzero $x_i$'s is at most $k$, proving the claimed upper bound.
Sharpness follows from taking $x_i=1/k$ for $i$ in a clique of size $k$ and $x_i=0$ for all other $i$.
By the recent breakthrough upper bound on the clique number of the Paley graph by Hanson and Petridis, we have $k \leq \lceil \sqrt{p/2} \rceil$. Plugging this in, we obtain your claimed bound for $p=5$ and do better for all larger $p$. (To do better, it suffices to have $k < \frac{p+3}{4}$.)
