How to estimate the upper bound of $|S|\subset [p] ,\forall i\neq j \in S, \left(\dfrac{i-j}{p}\right)$ ,$p$ is a prime, $p\equiv 1(mod 4)$. Problem. Suppose that $p$ is a prime and $p\equiv 1(\mathrm{mod} \ 4)$. $S\subset \{1,2,\cdots,p\}$, $\forall i<j \in S$, $\left(\dfrac{i-j}{p}\right)=1$. Then estimate the upper bound of $|S|$.
The problem comes from an MO problem which asks you to prove that $|S|\leq \dfrac{p+3}{4}$.
My effort. I have already proved that $|S|\leq \dfrac{p+3}{4}$. My solution is as follows:
WLOG, $p\in S$. Then $T:=S-\{p\}\subset \{1^2,2^2,\cdots,\bigl(\dfrac{p-1}{2}\bigr)^2\}$(mod $p$). Let $T=\{a_1^2,a_2^2,\cdots,a_t^2\}(1\leq a_1,a_2,\cdots,a_t\leq \dfrac{p-1}{2})$. Then $a_2,a_3,\cdots,a_t$ are the solutions to the equation $\left(\dfrac{x^2-a_1^2}{p}\right)=1$. We have $$\sum_{k=0}^{p-1}\left(\dfrac{k^2-a_1^2}{p}\right)=-1,$$hence $$-1=\sum_{k=1}^{\frac{p-1}{2}}\left(\dfrac{k^2-a_1^2}{p}\right)=-\dfrac{p-3}{2}+2\sum_{\bigl(\frac{x^2-a_1^2}{p}\bigr)=1,1\leq x\leq \frac{p-1}{2}}1\geq -\dfrac{p-3}{2}+2(t-2),$$ so $t\leq \dfrac{p+3}{4}$.
But it's not a good estimate and I want to get a better one(e.g. What would it be like when$p\to +\infty$? )Maybe it is enough to give an estimate of an order of magnitude($O(p)?O(\sqrt p)?$ even $O(1)?$). I think the difficulty is the contradictory of the multiplicative symbol$\left(\dfrac{\cdot}{\cdot}\right)$ with the additive condition in this problem.
To get a more intuitive understanding, I tried to construct a graph $G$. Then the problem turned to find the number of edges in the largest complete graph in the induced subgraph.
 A: Your intuitions are right.
This is a known open problem; the graph that you construct is well-known and called the Paley graph. The largest clique size is known to be at most $\sqrt{p}$ (recently improved to $\sqrt{p}/2$), and the conjecture is that it is $O(\log p \log \log p)$.
For details, see this article:
https://gilkalai.wordpress.com/2020/02/08/the-largest-clique-in-the-paley-graph-unexpected-significant-progress-and-surprising-connections/
As you mentioned, the connection between multiplicative and additive aspects are likely a motivation for this problem; in additive combinatorics, people are interested in sum-product results, which say that one of $S+S$, $S \times S$ must be large. Intuitively, sets with an additive structure, like arithmetic progressions tend to have large values of the product (no multiplicative structure), and sets of squares (although not consecutive) are expected to have a large value of sum. Here, the definition of $A+B$ is $\{a+b:a \in A, b \in B\}$, likewise for $A \times B$.
Possibly, the $O(\sqrt{p})$ bound follows from the Cauchy-Davenport theorem.
