tag:blogger.com,1999:blog-3722233.post3146977898028303732..comments2023-09-30T21:44:03.907-05:00Comments on Computational Complexity: Seeking an EASIER proof of s x s^2 theoremLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-6104689157035912662009-03-09T23:13:00.000-05:002009-03-09T23:13:00.000-05:00never mind, I found the information from Bill's po...never mind, I found the information from Bill's post here: http://lucatrevisan.wordpress.com/2007/01/26/the-multi-dimensional-polynomial-van-der-waerden-theorem/<BR/><BR/>I love this problem!Unknownhttps://www.blogger.com/profile/16071760708189328829noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69555485942293598412009-03-09T15:00:00.000-05:002009-03-09T15:00:00.000-05:00Bill - this is an interesting problem. Can you des...Bill - this is an interesting problem. Can you describe in your own language the intuition behind: 1) the direct proof of s x s, 2) the combinatorial extension of HJ to poly HJ?jhawksleyhttps://www.blogger.com/profile/16120305073670082251noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76499621469856319412009-03-06T11:56:00.000-06:002009-03-06T11:56:00.000-06:00Andy Parrish is, of course,correct--- solving then...Andy Parrish is, of course,<BR/>correct--- solving the<BR/>non-ness-axis-parallel may lead to insights for the problem I am asking about.<BR/>OKAY- SOMEONE- please solve.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85253966617310717882009-03-06T10:17:00.000-06:002009-03-06T10:17:00.000-06:00satisfy condition В of Theorem В and. (ii) {pv2}v ...satisfy condition В of Theorem В and. (ii) {pv2}v is bounded away from one. Proof: From condition (i) and Theorem B, Sx2lsx * 1. Now we can write sxs. 2„ 2 ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88277905746041336542009-03-05T20:51:00.000-06:002009-03-05T20:51:00.000-06:00Bill, that seems closed minded to demand first a s...Bill, that seems closed minded to demand first a solution to exactly the problem you asked. Doesn't math teach us that the best way to solve a problem is often to solve a different problem first and then get the desired result as a corollary? Perhaps there's a really neat way to force a rotated n by n^2 rectangle which we could generalize to get one parallel to the axes.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84918528095543104432009-03-05T16:18:00.000-06:002009-03-05T16:18:00.000-06:00YES in both problems I DO meanaxis-parallel. Thoug...YES in both problems I DO mean<BR/>axis-parallel. Though axis-not-necc parallel might be a good problem also.<BR/>The axis-parallel problem proofs<BR/>lead to VDW_type large bounds<BR/>on things. the axis-not-necc-parallel<BR/>might lead to much smaller numbres.<BR/><BR/>But for now, lets solve THIS problem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58207280196298994512009-03-05T15:11:00.000-06:002009-03-05T15:11:00.000-06:00Hi Bill,Nice problems... in both, do you mean axis...Hi Bill,<BR/><BR/>Nice problems... in both, do you mean axis-parallel?Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63687655156688803552009-03-05T12:42:00.000-06:002009-03-05T12:42:00.000-06:00I have a meeting in a minute-so this may be very h...I have a meeting in a minute-so this may be very half baked. Did you try using the polynomial method. Its likely you might be able to write down a polynomial for each prime p so that counts the number non-solutions mod p. Then, use Chevalley-Warning and Ax to get a contradiction....there will be too many non-solutions...dickdick liptonhttps://www.blogger.com/profile/04007670682499339173noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73615363216062959292009-03-05T12:04:00.000-06:002009-03-05T12:04:00.000-06:00Very neat problem...rjliptonVery neat problem...rjliptondick liptonhttps://www.blogger.com/profile/04007670682499339173noreply@blogger.com