tag:blogger.com,1999:blog-3722233.post8341774139252209833..comments2023-03-23T09:50:46.959-05:00Comments on Computational Complexity: Seeking the NON-Elementary proof of...Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-81198777298909502552009-02-24T13:12:00.000-06:002009-02-24T13:12:00.000-06:00Hi Bill,I couldn't say whether something like ...Hi Bill,<BR/>I couldn't say whether something like this proof was what the authors had in mind. By the standards of the field it probably counts as obvious, but I wouldn't use such language if I were trying to write a friendly & accessible survey.<BR/>It's certainly possible there is a simpler reduction (and, e.g., mine could definitely be retooled to avoid modular arithmetic), but I don't see it. In particular, is the switch to the finitary version needed?Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14652953474642320432009-02-24T12:08:00.000-06:002009-02-24T12:08:00.000-06:00ANDY D- THANKS for the proof.Here is what I wonder...ANDY D- THANKS for the proof.<BR/>Here is what I wonder--- is<BR/>what they had in mind when various<BR/>authors said it followed<BR/>``obviosul'' from Sz theorem?<BR/>Not obvious to me, but it could be<BR/>what they meant. ANy thoughts?<BR/>easier proofs?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82870567020848092392009-02-24T08:10:00.000-06:002009-02-24T08:10:00.000-06:00Van Der WaerdenVan Der WaerdenAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21694416861754760482009-02-23T18:55:00.000-06:002009-02-23T18:55:00.000-06:00What does VDW mean?What does VDW mean?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89497009799125553982009-02-23T15:38:00.000-06:002009-02-23T15:38:00.000-06:00Also, I think I shouldn't have called Bill's #3 'f...Also, I think I shouldn't have called Bill's #3 'fishy'. I guess what was meant is that if we *also* assume no monochromatic k-AP, then there exists a colorful k-AP. I can't argue with this.Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19729215778275915392009-02-23T15:33:00.000-06:002009-02-23T15:33:00.000-06:00Sorry, last quantity should be (1 - o(1))/(2k^2).Sorry, last quantity should be <BR/>(1 - o(1))/(2k^2).Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7562388477449885952009-02-23T15:15:00.000-06:002009-02-23T15:15:00.000-06:00I believe I can give the proof. But first I'd...I believe I can give the proof. But first I'd like to observe: the previous suggestions seem to falter because Bill's assertion #3 is fishy: it's not even true that if every color class is finite, then there exists a rainbow/colorful 4-AP.<BR/><BR/>To see this consider, e.g., the coloring in which the ith color takes up a block of length 5^i. Say a 4-AP begins in block i and has second element in block j > i. Then the common difference d for the 4-AP is (crudely) at most 2*5^j. It follows that whatever block k > j the third element falls into, the fourth element will also fall in block k.<BR/><BR/>OK, so here's an alternative approach: use the *finitary* statement of Szemeredi's Thm, which follows from the infinite version by a well-known compactness argument (see Terry Tao's several posts on the subject). The finitary version says:<BR/><BR/>***<BR/>For any k, eps > 0, there exists an N = N(k,eps) such that if S \subseteq [0, 1, 2,..., N - 1] has density at least<BR/>eps in that interval, S contains a k-AP.<BR/>***<BR/><BR/>So, here's my proof assuming the above: given k, let eps > 0 be chosen tiny compared to k (how tiny we need will become clear to the author later). Let N = N(k, eps). Let rho be a coloring. If there exists a color with density at least eps in [0, 1, ...N-1], we're done, so assume this is not the case.<BR/><BR/>Pick a random pair (a, d) uniformly from [0, ... N - 1]^2, and define the set <BR/><BR/>A = {a + jd (mod N)| j=0, 1, ... k - 1}, <BR/>a k-AP over Z_N.<BR/><BR/>(Of course, we really want an integer progression... but things will work out.)<BR/><BR/>Note that for distinct indices j, j', the random variables (a + jd), (a + j'd) (both mod N) are pairwise independent (PI). Let X_{j, j'} be the indicator variable for the event that these points have the same color in rho. Using PI we see that E[X_{j, j'}] <= 1/eps, so E[Sum X_{j, j'}] <= O(k^2/eps). So if eps = o(1/k^4) this is o(1/k^2), and with high probability the Z_N k-AP is colorful.<BR/><BR/>We wanted an integer k-AP. But, one way to get this is just to have the event <BR/>{a <= N/(2k) , d <= N/k} so that no 'wraparound' occurs. This occurs with probability <BR/>~ 1/(2k^2). So, with prob. (1 - o(1))/(2k) we succeed in finding a colorful integer k-AP.Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6905249802705131652009-02-23T15:10:00.000-06:002009-02-23T15:10:00.000-06:00This comment has been removed by the author.Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53612549947256346572009-02-23T13:26:00.000-06:002009-02-23T13:26:00.000-06:00If all densities are zero, it seems to work to pic...If all densities are zero, it seems to work to pick the progression x,x+y,x+2y,... where x and y are uniformly random in the interval [1,K] for large enough K: as K -> infinity, w.h.p. the progression will have no repetition.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4650455886534818542009-02-23T12:19:00.000-06:002009-02-23T12:19:00.000-06:00(As a note, "upper density" is a limsup.)(As a note, "upper density" is a limsup.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76869356461980039872009-02-23T12:09:00.000-06:002009-02-23T12:09:00.000-06:00The seconds step MIGHT be to take the set...and sh...<I>The seconds step MIGHT be to take the set...and show that it has positive density. But I don't know how to prove that, or if its even true.</I><BR/><BR/>It's not true. Consider the coloring: 1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 ...<BR/><BR/>The set you defined has density 0, and any individual color also has density 0.Anonymousnoreply@blogger.com