tag:blogger.com,1999:blog-3722233.post304621929943029721..comments2020-02-19T03:43:18.369-05:00Comments on Computational Complexity: A(nother) nice use of Gen FunctionsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-69021562310173780402013-10-08T01:19:49.995-04:002013-10-08T01:19:49.995-04:00So, one thing I didn't understand in your proo...So, one thing I didn't understand in your proof (or Noga's proof or whatever): In page 3, when you divide both sides of Equation by (x-1)^m, you can only do that if $x$ is not 1. So, you get a condition on the side (that you don't mention) and that says the resulting equation is true for $x \neq 1$. Now, you put $x$ to be 1 which is in direct contradiction with that condition on the side and you get to your desired result this way.<br /><br />While the final result happens to be the same as the original way of doing it, your proof (or Noga's proof or ...) seems not to be valid.<br /><br />Please tell me if I'm missing something ....Shahabhttps://www.blogger.com/profile/15635159089551928063noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80885297919400869432013-07-19T12:30:35.215-04:002013-07-19T12:30:35.215-04:00That's a nice proof! As for complex numbers, j...That's a nice proof! As for complex numbers, just having the proof for natural numbers seems to give away everything.<br /><br />Claim 1: The result holds for integers.<br />Proof: Translate A so that it now holds natural numbers, and notice that no information is lost.<br /><br />Claim 2: The result holds for Z^k.<br />Proof idea: Let A be a set of k-vectors, with maximum element M (in absolute value). Treat the vectors in A as (something like) base-(4M+1) representations of integers, and let A' be the corresponding set of integers. Given A +* A, we can translate to A' +* A', then recover A', and then recover A.<br /><br />Claim 3: The result holds for complex numbers.<br />Proof: View C as a vector space over Z and apply claim 2. (Note that this doesn't use the axiom of choice, since a finite set A only generates a finite-dimensional vector space over Z.)Andy Parrishhttps://www.blogger.com/profile/12252029594014518238noreply@blogger.com