4
$\begingroup$

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


Added September 14, 2014.

Here is an interesting observation that I was unable to put to work so far:

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Felipe Voloch Sep 12 '14 at 14:30
  • $\begingroup$ @Felipe: that's interesting. What the improvement is like? Is it effective / explicit? (And thanks for fixing the typo.) $\endgroup$ – Seva Sep 12 '14 at 14:47
  • $\begingroup$ You should double check, but I think you get $c\sqrt{p}$ for some $c<1, c=1/\sqrt{2}$ maybe. $\endgroup$ – Felipe Voloch Sep 12 '14 at 14:51
  • $\begingroup$ This is certainly a non-trivial improvement, but still well off from what I'd be happy to have here... $\endgroup$ – Seva Sep 14 '14 at 19:36

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.