Prove an inequality related to sums of Legendre symbols

Question

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

Answer 1

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