tag:blogger.com,1999:blog-3722233.post7148262845778665587..comments2021-12-01T13:41:42.544-06:00Comments on Computational Complexity: An application of VDW theorem to Number Theory- is there a better proof?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-78123922061477862352014-10-05T22:24:27.730-05:002014-10-05T22:24:27.730-05:00Very cool application of VDW! I wonder if there is...Very cool application of VDW! I wonder if there is a compilation of surprising uses of VDW (or maybe Ramsey Theory) in atypical areas. I know a lot of topological proofs that use VDW but this is the first NT one I have seen. Again, very cool!Sandeep Silwalhttp://math.stackexchange.com/users/138892/sandeep-silwalnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78446713299008924222009-08-24T10:53:42.009-05:002009-08-24T10:53:42.009-05:00Boris, if you or someone writes this up, please se...Boris, if you or someone writes this up, please send it to me--- I am both interested in when Ramsey Theory is used to proof something AND when it is no longer needed.<br />I would post a writeup of what I put on the blog AND your write up both on my<br />WEBSITE OF RAMSEY APPLICATIONS.<br /><br />bill g.bil gnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68623270145630262832009-08-24T02:37:30.624-05:002009-08-24T02:37:30.624-05:00According to my colleague's calculations, the ...According to my colleague's calculations, the proof via the Riemann Hypothesis for curves (proven by Weil around 1940) gives a bound of k^2 * 4^(k+1) at worst, but this can likely be marginally improved.Unknownhttps://www.blogger.com/profile/06229416831400925212noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12751293144916654722009-08-23T19:19:01.970-05:002009-08-23T19:19:01.970-05:00Does the proof via density give better bounds then...Does the proof via density give better bounds then the proof via VDW?bil g.noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18871744249546773652009-08-22T23:24:19.866-05:002009-08-22T23:24:19.866-05:00The set QR has very small fourier coefficients (th...The set QR has very small fourier coefficients (this is the gauss sum). This implies the result, with (1/2^k) density.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17457034934689891942009-08-22T07:09:32.348-05:002009-08-22T07:09:32.348-05:00One can look at the affine curve defined by x_1^2 ...One can look at the affine curve defined by x_1^2 + 1 = x_2^2 + 2 = x_3^2 + 3 = ... = x_k^2 + k modulo p, and then apply the Riemann hypothesis for curves (Weil) to it. If some things about irreducibility check out, then this should actually give an asymptotic on the number of solutions modulo p (about p/2^k?), not only their existence.Unknownhttps://www.blogger.com/profile/06229416831400925212noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53612128745880026062009-08-21T18:06:47.732-05:002009-08-21T18:06:47.732-05:00It feels like there should be some sort of argumen...It feels like there should be some sort of argument making use of the fact that the Quadratic Residues are in a certain sense pseudorandom. <br /><br />For example, if the appropriate Gowers norm of the set of residues is small, then we know that there should be approximately the same number of progressions in the residues as there are in a random set of density 1/2, which would be enough once p becomes much larger than 2^(2k).<br /><br />Is there a known estimate along those lines?Kevin C.https://www.blogger.com/profile/08760942816103747988noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8383512354066348162009-08-21T17:19:33.802-05:002009-08-21T17:19:33.802-05:00Wow, I feel incredibly stupid! Thank you, Bill, f...Wow, I feel incredibly stupid! Thank you, Bill, for correcting my misunderstanding.<br /><br />My excuse: I was using the infinitary version of van der Waerden's theorem, and as such was coloring all of the integers. I don't know why I was doing that, considering your proof is very clear that you are using the version with bounds, and that you're coloring [p], not Z.Unknownhttps://www.blogger.com/profile/06229416831400925212noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36225484175657105752009-08-21T17:00:54.062-05:002009-08-21T17:00:54.062-05:00Boris, Thanks for your question.
Recall that in V...Boris, Thanks for your question.<br /><br />Recall that in VDW or extended VDW we get<br />that if we c-color<br />[W] we get a monochromatic<br />k-AP. That entire k-AP is<br />contained in [W]. Hence we<br />have to have d &le W, and in <br />particular we cannot have<br />that W divides d.<br /><br />So when we 2-color [p]<br />and use VDW the d that we<br />get is such that d&le p<br />and hence p cannot divide d.<br /><br />bill gbil gnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30105355124627823852009-08-21T15:13:17.451-05:002009-08-21T15:13:17.451-05:00Here's a problem that I don't see a way ar...Here's a problem that I don't see a way around:<br /><br />What if d is a multiple of p? (For example, if you treat 0 as a quadratic residue, all multiples of p will be an infinite arithmetic progression.)<br /><br />Then d inverse mod p doesn't exist and you don't get anything.Unknownhttps://www.blogger.com/profile/06229416831400925212noreply@blogger.com