# Subgroup cliques in the Paley graph

It is a famous open problem to estimate non-trivially, for a prime $p\equiv 1\pmod 4$, the largest size of a subset $A\subset{\mathbb F}_p$ such that the difference of any two elements of $A$ is a square in ${\mathbb F}_p$; some background information can be found here. The basic estimate is $|A|<\sqrt p+O(1)$, which is easy to obtain in several ways. Can we do substantially better if $A$ is known to be a subgroup of the multiplicative group of ${\mathbb F}_p$?

For a prime $p\equiv 1\pmod 4$, how large can a subgroup $H<{\mathbb F}_p^\times$ be given that the difference of any two elements of $H$ is a square?

Equivalently,

For a prime $p\equiv 1\pmod 4$, denoting by $\mathcal Q$ the set of all squares in ${\mathbb F}_p$, what is the largest size of a subgroup of ${\mathbb F}_p^\times$ contained in ${\mathcal Q}\cap({\mathcal Q}+1)$?

Since containment in ${\mathcal Q}$ is not that much restrictive for a subgroup, this seems essentially equivalent to asking about the largest possible size of a subgroup contained in ${\mathcal Q}+1$.

If $H<{\mathbb F}_p^\times$ has the required property, then for any $h\in H$ and any positive integer $m$ with $h^m\ne 1$, denoting by $\Phi_m$ the $m$th cyclotomic polynomial, the value $\Phi_m(h)$ is a quadratic residue.
In particular, taking $m=2$ we conclude that $h+1$ is a quadratic residue; hence, not only the differences, but also the sums of any two elements of $H$ must be residues, with the possible exception of sums of the form $h+h=2h\ (h\in H)$.
This follows by induction on $m$: since $1\in H$, the difference $h^m-1=\prod_{d\mid m} \Phi_d(h)$ is a quadratic residue.
• Using the improvements on the Weil bound (described e.g. by Mike Zieve here: mathoverflow.net/questions/121653/…) to curves $x^m = y^2 +1$ one can improve what you called the trivial bound a little bit. – Felipe Voloch Sep 12 '14 at 14:30
• You should double check, but I think you get $c\sqrt{p}$ for some $c<1, c=1/\sqrt{2}$ maybe. – Felipe Voloch Sep 12 '14 at 14:51