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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.