most recent 30 from http://mathoverflow.net 2013-05-19T12:01:11Z http://mathoverflow.net/feeds/question/52393 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52393/given-a-prime-p-how-many-primes-ellp-of-a-given-quadratic-character-mod-p GH 2011-01-18T09:25:05Z 2011-01-20T20:55:59Z

<p>There was <a href="http://mathoverflow.net/questions/52318/" rel="nofollow">this question</a> for which my response was unusally popular, so I dare to ask the following:</p> <p>(1) Given a prime $p>2$, how many primes $\ell &lt; p$ there exist which are quadratic residues mod $p$?</p> <p>(2) Given a prime $p>2$, how many primes $\ell &lt; p$ there exist which are quadratic nonresidues mod $p$?</p> <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 &lt; x &lt; \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.</p> <p>EDIT: As Anonymous pointed out, we should restrict to odd $0 &lt; x &lt; \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). </p>

http://mathoverflow.net/questions/52393/given-a-prime-p-how-many-primes-ellp-of-a-given-quadratic-character-mod-p/52435#52435 Will Jagy 2011-01-18T20:51:59Z 2011-01-18T22:32:42Z

<p>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.$ </p> <p>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.</p> <p>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</p> <p>$$ \lim_{p \rightarrow \infty} \frac{R(p) \log p}{p} = \lim_{p \rightarrow \infty} \frac{N(p) \log p}{p} = \frac{1}{2}. $$</p> <p>From David's comment, this is also the prediction of a certain generalized Riemann Hypothesis.</p> <pre><code>phoebus:~/Cplusplus&gt; ./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&gt; </code></pre>

http://mathoverflow.net/questions/52393/given-a-prime-p-how-many-primes-ellp-of-a-given-quadratic-character-mod-p/52491#52491 Greg Martin 2011-01-19T09:11:14Z 2011-01-19T09:11:14Z

<p>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.</p>

http://mathoverflow.net/questions/52393/given-a-prime-p-how-many-primes-ellp-of-a-given-quadratic-character-mod-p/52660#52660 Anonymous 2011-01-20T18:06:21Z 2011-01-20T18:06:21Z

<p>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'$.</p> <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.)</p>