
> 
> 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](https://mathoverflow.net/q/427035/7113) 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?



Largest subset of quadratic residues with no pair of elements differing by 1
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


