# Given a prime $p$ how many primes $\ell<p$ of a given quadratic character mod $p$?

There was this question for which my response was unusally popular, so I dare to ask the following:

(1) Given a prime $p>2$, how many primes $\ell < p$ there exist which are quadratic residues mod $p$?

(2) Given a prime $p>2$, how many primes $\ell < p$ there exist which are quadratic nonresidues mod $p$?

As for (1) I can prove $\gg\log p/\log\log p$ by an elementary argument. Indeed, put $p':=(-1)^{(p-1)/2}p$ and observe, by quadratic reciprocity, that a prime $\ell\neq p$ divides some value $x^2-p'$ for $x\in\mathbb{Z}$ if and only if $\ell$ is a quadratic residue mod $p$. Now consider $|x^2-p'|$ for $0 < x < \sqrt{p}$: these are integers in $(0,p)$ or $(p,2p)$ depending on $p$ mod $4$. At any rate, these numbers are built up from the $k$ primes enumerated under (1), and their number is $\gg\sqrt{p}$. As each of the $k$ prime exponents is $\ll\log p$, we conclude $\sqrt{p}\ll(\log p)^k$ and my claim follows.

Added 1. As Anonymous pointed out, we should restrict to odd $0 < x < \sqrt{p}$, and talk about the odd part of $|x^2-p'|$. In addition, using the upper bound part of (7.16) on p. 203 of Montgomery-Vaughan: Multiplicative Number Theory (proof on pp. 204-208), we can see $k>(\log p)^{2-o(1)}$ for the number of primes under (1).

Added 2. Regarding (2), Lucia pointed out that $\gg p^\delta$ follows with a decent $\delta>0$ from a result of Bourgain and Lindenstrauss. I found this response very satisfactory, and I accepted it officially. Still, I would welcome any further developments regarding the above questions (1) and (2).

-
GRH for quadratic Dirichlet L-functions implies both counts are $\frac{1}{2}\mathrm{Li}(p)+O(p^{1/2}\log^2{p})$. –  David Hansen Jan 18 '11 at 21:07
I was aware of this, but certainly an important comment. I'm am interested in what can be said unconditionally or with weaker hypotheses. –  GH from MO Jan 19 '11 at 9:19

## 4 Answers

GH from MO and Anonymous have commented above on (modest) lower bounds for the first problem. Let me mention here that a version of problem 2 (of producing many non-residues) appeared in work of Bourgain and Lindenstrauss in connection with the QUE conjecture. In particular, from Theorem 5.1 of their paper it follows that there is a positive constant $\delta$ such that at least $p^{\delta}$ of the primes $\ell$ below $p$ are quadratic non-residues $\pmod p$. The proof is based on the fundamental lemma of sieve theory together with cancelation in character sums.

Added: To elaborate, Theorem 5.1 of Bourgain and Lindenstrauss's paper shows that if $N=p^{\beta}$ with $\beta \ge 1/4+\epsilon$ then there exists $\alpha>0$ such that ($\ell$ runs over primes below) $$\sum_{N^{\alpha} <\ell < N; (\frac{\ell}{p}) = -1} \frac{1}{\ell} \ge \frac 12 -\epsilon.$$ In particular the number of primes $\ell$ with $(\frac{\ell}{p}) =-1$ is trivially at least $(1/2-\epsilon)N^{\alpha}$. Now use this with $N=p$, and we deduce the result mentioned above. I didn't check the details, but I think one can get a pretty decent value of $\delta$ above -- maybe even as big as $3/8$ (the level of distribution is like $p^{\frac 34}$ and the sifting limit should be $1/2$).

-
Very interesting! I don't see immediately how Theorem 5.1 yields the lower bound $p^\delta$ you claim. Can you provide a detailed proof? –  GH from MO Sep 3 at 14:57
Well, the quoted theorem uses $(\frac{p}{\ell}) =-1$ instead of $(\frac{\ell}{p}) =-1$. For $p\equiv 1\pmod{4}$ the two conditions are the same, but for $p\equiv 3\pmod{4}$ we need a restriction to $\ell\equiv 1\pmod{4}$. Can we do this by modifying their proof? I have no time to think about this. –  GH from MO Sep 3 at 17:38
@GHfromMO: If $p$ is $3\pmod 4$ use the Theorem with the discriminant $-p$. The proof (which is just a simple sieve) works fine for positive or negative discriminants. –  Lucia Sep 3 at 17:39
Thank you! I will accept your answer officially. –  GH from MO Sep 3 at 17:47
@GHfromMO: Thanks, but I'm not sure I've answered your question fully! (It's probably too hard to say much more though.) It's also very interesting that there is such an asymmetry between questions (1) and (2); certainly it would be very nice to push the bound in (1) to some power of $p$, but this is probably too closely tied up with Siegel zeros. –  Lucia Sep 3 at 17:49

Let $\chi(n)$ denote the quadratic character modulo $p$ (so $\chi(n) = 1$ if $n$ is a quadratic residue modulo $p$, and $\chi(n)=-1$ if $n$ is a quadratic nonresidue modulo $p$). The difference between the number of primes that are quadratic residues and quadratic nonresidues is exactly $\sum_{\ell\lt p} \chi(\ell)$ where $\ell$ denotes a prime. One can deduce information about $\sum_{\ell\lt p} \chi(\ell)$ from information about $\sum_{\ell\lt p} \chi(\ell)\log\ell$, which in turn is almost the same as $\sum_{n\lt p} \chi(n)\Lambda(n)$ where $\Lambda$ is the von Mangoldt function. Such information is classically known, since the proof of the prime number theorem for arithmetic progressions hinges on it; it's important to note here that the summation goes up to $p$ itself rather than a general large $x$ as is typical for such statements. The answer then depends upon what zero-free region for the associated $L(s,\chi)$ you want to use or assume; if you get a bound that is $o(p)$, then the numbers of prime quadratic residues and prime quadratic nonresidues are very close to equal.

-
Instead of "such information is classically known" I would say the problem of estimating these sums is classically known. As you point out, a good error term is tied with knowledge about the relevant $L$-function. However, as I remarked in the original question, something can be said without any hypothesis, too. So I propose we examine what can be said unconditionally or with weaker hypotheses. The range of the sum is indeed too short for advanced techniques like Linnik's to work in their original form. –  GH from MO Jan 19 '11 at 9:27
Given what we currently know about zeros of L-functions, this route seems useless to me without assuming GRH. –  David Hansen Jan 20 '11 at 16:11
@David: That's possible, yes. On the other hand, we only have one character here rather than all $\phi(q)$ characters, so the error term might be much better. –  Greg Martin Mar 4 '11 at 19:36

A comment to GH's elementary lower bound in question (1): Maybe there's a very minor error here. For example, if $p=7$ and $x=2$, then $x^2-p' = 11$ is not built up of primes enumerated in (1). But this is easily resolved by restricting to odd values of $x$ in the case when $p\equiv3\pmod{4}$, and noting we then already know the prime factor $2$ of $x^2-p'$.

More substantial comment: Doesn't this construction give something a bit better than $\log p/\log\log p$? If $q_1, \dots, q_k$ are the primes enumerated in (1), then we get that $\gg\sqrt{p}$ numbers in $[1, 2p]$ are supported on primes from the list $2, q_1, \dots, q_k$. But the count of numbers in $[1,2p]$ supported on this set of primes is at most the count of numbers supported on the primes $2, 3, 5, \dots, p_{k+1}$, where $p_i$ denotes the $i$th prime in increasing order. In other words, it's at most $\Psi(2p, p_{k+1})$. It is known from the theory of smooth numbers that $\Psi(x, (\log x)^{A}) = x^{1-1/A +o(1)}$, as $x\to\infty$. So it looks like GH's argument gives that $k \geq (\log{p})^{2-o(1)}$, as $p\to\infty$. (Of course this is a little less elementary.)

-
Thanks for your valuable comments! I agree with everything you say. –  GH from MO Jan 20 '11 at 18:39
I might be missing something but I think that there is problem here: the numbers satisfying (1) can get rather large. (For example if $p=4q+1$, where $q$ is a prime, then $1=(-1/p)=(4q/p)=(q/p)$, so $q=(p-1)/4$ is a quadratic residue modulo $p$.) I believe that the argument based on smooth numbers only gives that there must be at least one of them that is $>(\log p)^{2-o(1)}$. –  Dimitris Koukoulopoulos Mar 17 '13 at 0:06

This was fun. I did my usual experiment. For each new prime $p,$ I looked at the prime numbers from 2 to $p-2,$ counted these by Jacobi symbol as either res or non, then took the difference diff = res - non. Then I printed out a line if either diff took on a new world record negative value or a world record positive value. Finally I put a decimal value, diff/(res + non), where res + non is the total number of primes up to $p-2.$

My interpretation is that the ratio column is approaching 0, with unusual rapidity for this sort of problem. Note that, for any prime not printed, the final column must be even closer to 0 than nearby primes that are printed.

In short, if $R(p)$ is the number of primes up to $p-2$ that are quadratic residues $\pmod p,$ and if $N(p)$ is the number of primes up to $p-2$ that are quadratic nonresidues $\pmod p,$ I suggest

$$\lim_{p \rightarrow \infty} \frac{R(p) \log p}{p} = \lim_{p \rightarrow \infty} \frac{N(p) \log p}{p} = \frac{1}{2}.$$

From David's comment, this is also the prediction of a certain generalized Riemann Hypothesis.

phoebus:~/Cplusplus> ./prime_res
p    res   non  diff    diff/(res + non)
5     0     2    -2              -1
13     1     4    -3            -0.6
19     4     3     1        0.142857
37     3     8    -5       -0.454545
107    15    12     3        0.111111
113    11    18    -7       -0.241379
139    19    14     5        0.151515
163    11    26   -15       -0.405405
211    26    20     6        0.130435
317    37    28     9        0.138462
373    28    45   -17       -0.232877
571    59    45    14        0.134615
647    49    68   -19       -0.162393
911    66    89   -23       -0.148387
1013    92    77    15       0.0887574
1031    74    98   -24       -0.139535
1093    77   105   -28       -0.153846
1097   100    83    17       0.0928962
1487   102   133   -31       -0.131915
1553   131   113    18       0.0737705
1613   139   115    24       0.0944882
1741   119   151   -32       -0.118519
1871   126   159   -33       -0.115789
2029   135   172   -37       -0.120521
2179   177   149    28       0.0858896
2293   149   191   -42       -0.123529
2851   223   190    33       0.0799031
2971   235   193    42       0.0981308
3637   230   278   -48      -0.0944882
4957   303   359   -56      -0.0845921
5419   379   336    43       0.0601399
5879   358   415   -57      -0.0737387
5923   357   420   -63      -0.0810811
6211   427   380    47       0.0582404
7213   423   498   -75      -0.0814332
7219   491   431    60       0.0650759
8731   581   506    75       0.0689972
10357   596   674   -78      -0.0614173
10627   596   699  -103      -0.0795367
15451   945   859    86       0.0476718
17491  1054   958    96       0.0477137
18119   985  1089  -104      -0.0501446
18439  1002  1109  -107      -0.0506869
21739  1277  1161   116         0.04758
21839  1168  1280  -112      -0.0457516
22669  1204  1327  -123      -0.0485974
23251  1355  1237   118       0.0455247
24181  1281  1410  -129      -0.0479376
26701  1396  1532  -136      -0.0464481
28607  1487  1626  -139      -0.0446515
31253  1748  1620   128       0.0380048
34483  1765  1917  -152      -0.0412819
35491  1958  1819   139       0.0368017
35933  1980  1836   144       0.0377358
36373  1852  2006  -154      -0.0399171
39839  2013  2173  -160      -0.0382226
43117  2168  2336  -168      -0.0373002
52453  2581  2775  -194      -0.0362211
56039  2744  2941  -197      -0.0346526
56333  2936  2775   161       0.0281912
59399  2902  3102  -200      -0.0333111
61333  2976  3193  -217      -0.0351759
65539  3354  3189   165       0.0252178
69833  3351  3571  -220      -0.0317827
71971  3652  3471   181       0.0254106
81197  4074  3872   202       0.0254216
85223  4038  4259  -221      -0.0266361
85669  4053  4285  -232      -0.0278244
88919  4188  4425  -237      -0.0275165
89591  4216  4458  -242      -0.0278995
89659  4454  4229   225       0.0259127
95989  4504  4747  -243      -0.0262674
p    res   non  diff    diff/(res + non)
phoebus:~/Cplusplus>

-