In $\mathbb{F_p}$, $p$ prime what is the larget subset $S$ of quadratic residues with no pair of elements differing by 1?
In this related question Seva gives an example:
"...assuming $p\equiv\pm3\pmod 8$, consider the set of all those quadratic residues $r$ such that if $r'$ is the smallest quadratic non-residue exceeding $r$, then $r'-r$ is odd."
This gives a density $|A|/p = 1/3 + o(1)$ for any $p$ (the condition $p\equiv\pm3\pmod 8$ is not necessary for this problem). Can one do better?
No.
Let $T$ be any subset of $\mathbb F_p$. We can consider the general problem of finding a set $S \subseteq T$ with no pair of elements differing by $1$ that maximizes $|S|$.
The same construction works, i.e. $\{x \in T \mid x-y$ is odd for $y$ the largest nonmember of $T$ less than $x \}$ attains the maximal cardinality.
Proof: Consider another solution $S'$. For each $x\in S$, only one of $x$ and $x+1$ can lie in $S'$. Every $x \in T$ lies in one of these pairs since if $x-y$ is not odd then it's even and $x-1-y$ is odd (and $x-1 \in T$ since $x-y >0$ and is even and thus is $\geq 2$).
So the maximum size of $S'$ is at most the number of such pairs. Since these pairs don't overlap, and every pair contains one element of $S$, this is also the size of $S$, QED.
There's also an intuitive/visual proof by example. If $T$ is the set of stars
_***_**_*_*****_
then S is the set of x's
_x*x_x*_x_x*x*x_
and this is clearly optimal
