$\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.$$



Prove an inequality related to sums of Legendre symbols
$\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](https://arxiv.org/abs/1905.09134), 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}$.)


