0
$\begingroup$

Let $p\equiv 3\pmod 4$ and $G$ be the set of nonzero quadratic residues modulo $p$ (so $G=(p-1)/2$). For $1\leq a\leq p-1$, let $G_a=\{(a+g)\pmod p\mid g\in G\}$. What is the size of $G_0\cap G_a$?

I tested for $p=3,7$ and $11$, and the size of the intersection is always $(p-3)/4$. Is this always true? If so, it sounds like it should be a basic fact of quadratic residues, but I couldn't find it.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Looking at $G_0 \cap G_a$ is close to counting solutions to $x^2 \equiv a + y^2 \bmod p$, so $x^2 - y^2 \equiv a \bmod p$. For odd prime $p$, making the change of variables $u = x + y \bmod p$ and $v = x - y \bmod p$, that would be counting solutions to $uv \equiv a \bmod p$. For $a \not\equiv 0 \bmod p$ there are obviously $p-1$ solutions (for each choice of nonzero $u$ there is one $v$). Since you're counting squares with a property rather than numbers whose squares have a property there is some double sign issue to account for ($x^2$ and $y^2$ arise from 2 choices each unless one is 0). $\endgroup$
    – KConrad
    Commented May 23, 2019 at 19:04
  • 1
    $\begingroup$ That's presumably where the division by 4 is coming from. I don't have time to deal with the bookkeeping issues involved, but the "basic fact" you couldn't find is just that hyperbolas $x^2 - y^2 \equiv a \bmod p$ for odd prime $p$ and $a \not\equiv 0 \bmod p$ each have the same number of solutions (independent of $a$). The book of Ireland & Rosen has nice coverage of the general topic of counting solutions to equations over finite fields, especially "diagonal" equations like the hyperbola (no monomials involve more than one variable). Your question is more suitable for math.stackexchange. $\endgroup$
    – KConrad
    Commented May 23, 2019 at 19:08

1 Answer 1

Reset to default
2
$\begingroup$

Yes, the intersection has $(p-3)/4$ elements and this is standard, probably this specific claim also is written somewhere. We have $$\left|G_0\cap G_a\right|=\sum_{x} \chi_{G_0}(x)\cdot \chi_{G_0}(x-a)=\sum_x \frac{1-(\frac{x}p)-\delta(x)}2\cdot \frac{1-(\frac{x-a}p)-\delta(x-a)}2.$$ Expand the brackets and calculate. $\sum 1=p$, $\sum (\frac{x}p)=\sum (\frac{x-a}p)=0$, $-\sum \delta(x)=-\sum \delta(x-a)=-1$, $\sum \delta(x)\delta(x-a)=0$, $\sum \delta(x)(\frac{x-a}p)=(\frac{-a}p)$, $\sum \delta(x-a)(\frac{x}p)=(\frac{a}p)=-(\frac{-a}p)$. Finally $\sum (\frac{x}p)(\frac{x-a}p)=\sum_{x\ne 0}(\frac{x}p)(\frac{x-a}p)=\sum_{x\ne 0} (\frac{x^{-1}}p)(\frac{x-a}p)=\sum_{x\ne 0}(\frac{1-ax^{-1}}p)=\sum_{t\ne 1}(\frac{t}p)=-1$. Totally we get $(p-3)/4$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This phenomenon is well known in combinatorial design theory. This calculation shows that the quadratic residues form a difference set in the additive group of a finite field when $q \equiv 3 \mod 4$. Generalisations of this result are studied as cyclotomic difference sets, and results are known for the quartic, septic and octic residues. $\endgroup$
    – Padraig Ó Catháin
    Commented May 23, 2019 at 22:26
  • $\begingroup$ Also studied under the heading, "cyclotomy". $\endgroup$
    – Gerry Myerson
    Commented May 23, 2019 at 22:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .