Given an odd prime $p$, let $S\subseteq \mathbb F_p$ be the set of quadratic residues modulo $p$. Given $a,b\in \mathbb F_p$ we write $aS+b$ for the set $$aS+b:=\{t\in\mathbb F_p:\ t=ax^2+b \text{ for some $x\in\mathbb F_p$}\}.$$

What is the cardinality of $S\cap ((S+1)\cup (2-S))$?

I would say that they are $\frac 3 8 p+ o(p)$, because of the following heuristic:

  • the residues of the form $x^2$ are $\sim \frac p 2$ out of $p$;
  • there's small correlation between a residue mod p being of the form $x^2$ or $1+y^2$;
  • so $\# S\cap (S+1)$ should be $\sim p/4$.

This in fact is quickly provable in a number of ways.

  • similar reasoning for the equation $\# S\cap (2-S)$.

Now, one would guess that, given random $x,y,z$, the equalities $x^2=1+y^2$ and $x^2=2-z^2$ are achieved for $1/4$ of the $x^2$s. So by Inclusion-Exclusion we get the heuristic.

I expect this to be provable in finite time by standard computations and the error term would be related to Weil's bound, aka Riemann Hypothesis on finite fields.

But how is it possible to make the above heuristic reasoning rigorous up to (1+o(1)), in a simple, direct and general way?

In other words, how to make oneself safe to assume the approximate independence of equations as above when doing this sort of ballpark estimates?

Let's restrict to linear equations between quadratic residues or to the specific example above, in this question. But of course the same question is interesting for other sets of residues that should "distribute randomly" modulo p, for example sets related to sums of characters.

Possible approaches so far:

  1. Estimate $\# S\cap S\cap(S+1)\cap(2-S)$ via Inclusion-Exclusion after counting precisely enough the solutions of the equation $(x^2-1-y^2)(x^2-2+z^2)=0$.
  2. Compute first effectively the expected Weil error bound, then compute the cardinality numerically for a large enough prime.
  3. Transform the problem into character sums as in Jyrki Lahtonen comment below.
  • $\begingroup$ Also, it is possible that you really wanted to ask a slightly different question :-) Anyway, thanks for adding your thoughts, I voted to reopen and +1 the question. $\endgroup$ – Jyrki Lahtonen Jun 7 '18 at 6:03
  • $\begingroup$ Say, if you want to study the (probabilistic) independence of the events of $x^2-1$ being a QR as opposed to $2-x^2$ being a QR, then you should look at character sums like $$\sum_{x\in\Bbb{F}_p}\eta(x^2-1)\eta(2-x^2)=\sum_{x\in\Bbb{F}_p}\eta((x^2-1)(2-x^2)),$$ where $\eta$ is the Legendre symbol modulo $p$. Weil's bound tells us that sum has absolute value less that $3\sqrt p$. $\endgroup$ – Jyrki Lahtonen Jun 7 '18 at 6:07
  • $\begingroup$ @Jyrki Lahtonen: you are right and you understood me perfectly..! This is just a 2-dimensional surface with 2 irreducible components, so yes it's 2p^2. Indeed it's not what I wanted to ask, I re-edit. Thank you. $\endgroup$ – Luca Ghidelli Jun 7 '18 at 8:48
  • $\begingroup$ Ok. This question matches perfectly with your earlier explanation. I still suspect that character sums can be used, but it's a bit more complicated than what my earlier comment may suggest. You see, the character sum in my comment above tells us a few things about the symmetric difference of $(S+1)$ and $(2-S)$, or their exclusive or if you prefer to call it that. I hope to return to this later. It should still be possible to write the number in terms of several character sums. $\endgroup$ – Jyrki Lahtonen Jun 7 '18 at 9:48
  • $\begingroup$ My two previous comments headed into a wrong direction. It's actually a bit simpler :-) $\endgroup$ – Jyrki Lahtonen Jun 9 '18 at 5:40

With the aid of character sums I can say the following, justifying Luca's heuristics (with some obvious exceptions).

Let $\eta$ be the usual multiplicative character given by the Legendre symbol, i.e. $\eta(0)=0$, and when $a\neq0$ we have $\eta(a)=\pm1$ according to whether $a$ is or is not a quadratic residue. Below it would be a bit more convenient to have $\eta(0)=1$, but I stick to this. For the purposes of applying the Weil bound a non-trivial multiplicative character is defined to vanish at zero.

Consider the set $aS+b, a\neq0$. Let us denote by $\chi_{aS+b}:\Bbb{F}_p\to\Bbb{R}$ its characteristic function, i.e. $$\chi_{aS+b}(t)=\begin{cases}1,&\ \text{if $t\in aS+b$, and}\\ 0,&\ \text{otherwise.}\end{cases}$$ An element $t\in\Bbb{F}_p$ is in the set if and only if $(t-b)/a$ is a square. There we almost have the identity $$ \chi_{aS+b}(t)=\frac12\left(1+\eta(\frac{t-b}a)\right). $$ The only difference is at $t=b$, when we get $1/2$ in the right hand side and one in the left.

For any two or more subsets $U_1,U_2,\ldots,U_m\subseteq \Bbb{F}_p$ we can write the characteristic function of their intersection as the product $$ \chi_{U_1\cap U_2\cap\cdots\cap U_m}=\chi_{U_1}\chi_{U_2}\cdots\chi_{U_m}. $$ For any subset $U\subseteq\Bbb{F}_p$ we have $|U|=\sum_{t\in\Bbb{F}_p}\chi_U(t)$. Let's apply all the above to the case $U_i=a_iS+b_i, i=1,2,\ldots,m$. We shall see that we want to make the assumption $b_i\neq b_j$ whenever $i\neq j$. We get $$ \begin{aligned} |U_1\cap U_2\cap \cdots\cap U_m|&=\sum_{t\in\Bbb{F}_p}\chi_{U_1\cap U_2\cap\cdots\cap U_m}(t)\\ &=\frac1{2^m}\sum_{t\in\Bbb{F}_p}\prod_{i=1}^m\left(1+\eta(\frac{t-b_i}{a_i})\right)+\frac m2\\ &=\frac p{2^m}+\frac m2+\\ &+\frac1{2^m}\sum_{J\subseteq \{1,2,\ldots,m\},J\neq\emptyset}\sum_{t\in\Bbb{F}_p}\eta\left(\prod_{j\in J}(\frac{t-b_j}{a_j})\right). \end{aligned} $$ Here the $m/2$ comes from $1/2$-errors at $t=b_i, i=1,2,\ldots,m$. In the last sum $J$ ranges over no-empty subsets of the index set $\{1,2,\ldots,m\}$ only because the term $J=\emptyset$ gives the "main" term $p/2^m$.

Anyway, because we assumed $b_i\neq b_j$, the polynomials in all those sums of the last form have simple zeros only, and we can apply Weil's bound to all of them. The end result is the expected one:

With $b_i$s pairwise distinct, the cardinality of the intersection $\bigcap_{i=1}^m(a_iS+b_i)$ differs from $p/2^m$ by an error term whose absolute value is bounded from above by $m/2+C\sqrt p$, where $C$ is a constant depending on $m$ but independent from $p$.

Of course, for large $p$ we can more or less ignore that $m/2$ term as it is overshadowed by the error terms coming from the character sums.

Luca's specific question was about the size of the intersection $S\cap \big((S+1)\cup (2-S)\big).$ The usual exclusion-inclusion business starting with $$ \chi_{U\cup V}=\chi_U+\chi_V-\chi_{U\cap V} $$ reduces estimating the union to estimating the intersection. Luca's heuristics handles all that.

  • $\begingroup$ So the gist of this solution is: make sure all the error terms correspond to polynomials with simple zeros. I accept this solution because it was already somewhat clear to me that the triple intersection is (1) of dim=1 and (2) of irreducible. I feel better to have an algebraic criterion that backs-up my geometrical intuition! $\endgroup$ – Luca Ghidelli Jul 20 '18 at 18:15

$S \cap (S+1)$ is approximately $\frac 14 \operatorname{Card}\{(x,y) \in \Bbb F_p^2 \mid x^2 = y^2+1 \}$.

This set is an algebraic curve of dimension $1$ (and of genus $0$) so it has $p+O(1)$ points. And so $\operatorname{Card}(S \cap (S+1)) = p/4+O(1)$

Similarly, $S \cap (2-S)$ will be related to the curve $x^2 = 2-y^2$ and $(S+1) \cap (2-S)$ to $x^2+1 = 2-y^2$. They are all curves of genus $0$ so those intersections also have $p/4 + O(1)$ elements.

Finally, $S \cap (S+1) \cap (2-S)$ corresponds to a spatial curve, the intersection of $x^2 = y^2+1$ and $x^2 = 2-z^2$. At a glance, this is an elliptic curve, so the curve has $p + 2\sqrt p u(p) + O(1)$ points, where $|u(p)| \le 1$, and then the intersection has $p/8 + \sqrt p u(p)/4 + O(1)$ elements.

Gathering up everything, you get :
$\operatorname{Card}(S \cap ((S+1) \cup (2-S))) = \\ \operatorname{Card}(S \cap (S+1)) + \operatorname{Card}(S \cap (2-S)) - \operatorname{Card}(S \cap (S+1) \cap (2-S)) = \\ 3p/8 - \sqrt p u(p)/4 + O(1)$

where $|u(p)| \le 1$

Note that this doesn't require $p$ to be prime, this is valid over any finite field $\Bbb F_q$

  • $\begingroup$ Simpler for the specific case of the question! $\endgroup$ – Jyrki Lahtonen Jun 10 '18 at 8:09
  • $\begingroup$ So the gist of this solution is: make sure that all the partial intersections are irreducible (say, over C). For example, the answer is not 3p/8 if the fist S is replaced by 2S+1, because 2x^2+1=y^2+1 would be a union of 2 lines. Btw, this is more clever than what I wrote in point 1 above! +1 $\endgroup$ – Luca Ghidelli Jul 20 '18 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.