Question

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.

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

Answer 1

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.

Answer 2

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

Answer 3

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>