22
$\begingroup$

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

Added 3. The recent preprint of Paul Pollack contains several nice new results and valuable historic references regarding the above two questions. An even more recent preprint by him and Kübra Benli settles (1) in the sense that there are $\gg p^{1/9}$ prime quadratic residues $\ell<p$.

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

4 Answers 4

12
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – GH from MO
    Sep 3, 2014 at 17:38
  • 1
    $\begingroup$ @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. $\endgroup$
    – Lucia
    Sep 3, 2014 at 17:39
  • 1
    $\begingroup$ @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. $\endgroup$
    – Lucia
    Sep 3, 2014 at 17:49
  • $\begingroup$ Well, answering my questions fully is probably hopeless (in the sense that probably something close to GRH is needed). Three years have passed since I posted them, and I am happy with your answer. $\endgroup$
    – GH from MO
    Sep 3, 2014 at 17:54
  • 1
    $\begingroup$ See also the last sentence in my updated "Added 3" section. $\endgroup$
    – GH from MO
    Nov 11, 2017 at 20:47
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – GH from MO
    Jan 19, 2011 at 9:27
  • $\begingroup$ Given what we currently know about zeros of L-functions, this route seems useless to me without assuming GRH. $\endgroup$ Jan 20, 2011 at 16:11
  • $\begingroup$ @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. $\endgroup$ Mar 4, 2011 at 19:36
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for your valuable comments! I agree with everything you say. $\endgroup$
    – GH from MO
    Jan 20, 2011 at 18:39
2
$\begingroup$

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>
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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