Timeline for Consecutive non-quadratic residues
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| Mar 24, 2014 at 18:40 | vote | accept | u1571372 | ||
| Mar 24, 2014 at 18:25 | answer | added | Seva | timeline score: 23 | |
| Mar 24, 2014 at 18:23 | comment | added | Douglas Zare | @André: Although that particular proof used $p=4k+1$, the idea that you can control whether the first few primes are quadratic residues by choosing $p$ to be in a particular arithmetic progression works even if we choose $p=4k+3$. Choose $p$ so that it is congruent to $-1$ mod $8$ and mod $q$ for the first few odd primes. By quadratic reciprocity this makes the first few primes squares mod $p$, while $-1$ is not a square. By Dirichlet's theorem on primes in arithmetic progressions there are primes satisfying these congruences. | |
| Mar 24, 2014 at 18:15 | comment | added | GH from MO | @André: I made a mistake in my comment. Here it is corrected: Weil's bound (not Weyl's) shows that for any polynomial $Q\in\mathbb{F}_p[x]$ with distinct roots we have that $\left|\sum_{x\in\mathbb{F}_p}\left(\frac{Q(x)}{p}\right)\right|$ is bounded by a constant times $\sqrt{p}$. Factoring out the product in Seva's sum yields several such character sums and also a sum of $1$'s, hence the sum is $p+O(\sqrt{p})$. On the other hand, the product in the sum vanishes whenever $x+j$ is a quadratic residue for some $j$. | |
| Mar 24, 2014 at 18:10 | comment | added | u1571372 | @GHfromMO, got it, thank you for your patience! | |
| Mar 24, 2014 at 18:01 | comment | added | u1571372 | @Seva, thank you, but could you please elaborate on your answer, mainly why does the sum you mentioned aproaches $0$ and how Weyl's bound actually implies that it has to aproach $p$? | |
| Mar 24, 2014 at 18:01 | comment | added | GH from MO | @André: You are right. At any rate, the reference in Douglas' s comment, and also Seva's comment, shows that for large $p$ there are $k$ consecutive residues and also $k$ consecutive non-residues. | |
| Mar 24, 2014 at 17:55 | comment | added | u1571372 | @DouglasZare, thank you for your answer, although the solution I've linked for the problem with consecutive quadratic residues requires that $p \equiv 1 \mod{4}$... | |
| Mar 24, 2014 at 17:48 | comment | added | GH from MO | @Douglas: Fair enough, and you are very kind. | |
| Mar 24, 2014 at 17:48 | comment | added | GH from MO | @Seva: Please turn your comment to an answer for the sake of future readers! | |
| Mar 24, 2014 at 17:46 | comment | added | Douglas Zare | @GH: I didn't add any real ideas, but I think Seva's argument should be an answer. | |
| Mar 24, 2014 at 17:44 | comment | added | GH from MO | @Douglas: It seems that you answered the OP's question, why not give it as an answer? | |
| Mar 24, 2014 at 17:44 | review | Close votes | |||
| Mar 29, 2014 at 22:08 | |||||
| Mar 24, 2014 at 17:44 | comment | added | GH from MO | @Seva: I did not know about this application of Weil's bound. On the other hand, I think the sum is close to $p$, not $p/2^k$. Am I wrong? | |
| Mar 24, 2014 at 17:39 | comment | added | Seva | @GH: it may not be trivial, but is very standard: if for a prime $p$ every run of $k$ residues contained a square, then the sum $$\sum_x \prod_{j=1}^k \left(1-\left(\frac{x+j}{p}\right)\right)$$ would be very close to $0$, while from Wwyl's bound it is actually close to $p$. Have I got anything wrong? | |
| Mar 24, 2014 at 17:36 | comment | added | Douglas Zare | For the first problem, you can choose $p=4k+3$ and multiply a sequence of consecutive quadratic residues by $-1$. I didn't read the second problem before voting to close, and I apologize for that and would undo it if I could. The second problem is more interesting. However, the abstract of the Buell and Hudson paper "On runs of consecutive quadratic residues and quadratic nonresidues" mentioned on the math.stackexchange.com question you linked claims to show that for all sufficiently large primes, there are arbitrarily long runs of quadratic nonresidues (and the same for residues). | |
| Mar 24, 2014 at 17:32 | comment | added | GH from MO | Why do people vote to close this question? It does not seem trivial to me. Also, I wanted to call attention to a related post: mathoverflow.net/questions/85842/… | |
| Mar 24, 2014 at 17:16 | history | asked | u1571372 | CC BY-SA 3.0 |