tag:blogger.com,1999:blog-3722233.post7448114190319986834..comments2024-10-30T20:00:47.980-05:00Comments on Computational Complexity: A Taylor Series Problem Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-68649452214856340742021-03-27T00:46:59.360-05:002021-03-27T00:46:59.360-05:00I think you can factor it out by hand by looking a...I think you can factor it out by hand by looking at pairs of terms. Since there are even terms that come in pairs in the initial expression, you can get the x-1 factor out naturally as: <br /><br />p(x) = (x_41 - x_40) - (x_36 - x^35) - (x_31 - x^30) ... - (x - 1)<br /> = x^40(x - 1) - x^35(x - 1) - .... - (x - 1)<br /> = (x - 1)(x^40 - x^35 - x^30 + x^25 - x^15 + x^10 + x^5 - 1)<br /><br />And if you repeat the same process with the new expression, pairing of terms and factoring out the largest power per pair, you will get the (x^5 - 1), (x^10 - 1), and (x^25 - 1) factors out too. <br />alinoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73902663351630931692021-03-24T16:53:33.526-05:002021-03-24T16:53:33.526-05:00that is the solution I had in mind.
I will be post...that is the solution I had in mind.<br />I will be posting on Thursday.<br />Curious- did you use a program to factor or did you do it by hand? <br /><br />I think this would be a much harder problem to do by hand.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8745965288362178052021-03-24T16:50:54.423-05:002021-03-24T16:50:54.423-05:00Let f(x) denote the expression. It is clear that
f...Let f(x) denote the expression. It is clear that<br />f(x) = (1-x)(1-x^5)(1-x^10)(1-x^25)<br />Then,<br />1/f(x) = 1/((1-x)(1-x^5)(1-x^10)(1-x^25))<br /> = (1+x+x^2+...)(1+x^5+x^10+...)(1+x^10+x^20+...)(1+x^25+x^50+...)<br /><br />We are interested in the coeff of x^100. Let us choose x^k1 from first term, x^(5*k2) from second,<br />x^(10*k3) from third and x^(25*k4) from the fourth. So we get<br /><br />x^100 = x^(k1 + 5*k2 + 10*k3 + 25*k4)<br /><br />100 = k1 + 5*k2 + 10*k3 + 25*k4<br /><br />The number of non-negative integer solutions to this above equation determines the coeff of x^100.<br /><br />Taking (mod 5) on both sides, we see that k1 = 5*k0 some non-negative integer k0.<br /><br />Therefore,<br />100 = 5*k0 + 5*k2 + 10*k3 + 25*k4<br /><br />which implies<br />20 = k0 + k2 + 2*k3 + 5*k4<br />where k0,k2 in {0,1,...,20}, k3 in {0,1,2,...,10} and k4 in {0,1,2,3,4}<br /><br />If k4 = 0, then for each k3 we have 20-2*k3 choices for pairs (k0, k2)<br /> ==> 21 + 19 + 17 + ... + 1 = 121 choices<br /><br />If k4 = 1, then for each k3 we have 15-2*k3 choices for pairs (k0, k2)<br /> ==> 16 + 14 + ... + 0 = 72 choices<br /><br />If k4 = 2, then for each k3 we have 10-2*k3 choices for pairs (k0, k2)<br /> ==> 11 + 9 + ... + 1 = 36 choices<br /><br />If k4 = 3, then for each k3 we have 5-2*k3 choices for pairs (k0, k2)<br /> ==> 6 + 4 + 2 = 12 choices<br /><br />If k4 = 4, then (k0, k2, k3) = (0,0,0)<br /> ==> 1 choice<br /><br />Total = 121 + 72 + 36 + 12+ 1 = 242<br /><br />Therefore coeff of x^100 is 242.<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6407753488894135562021-03-23T18:27:33.958-05:002021-03-23T18:27:33.958-05:00the 2 was a typo, YES its 1,5,10,25.the 2 was a typo, YES its 1,5,10,25.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6848098071876453592021-03-23T18:26:28.193-05:002021-03-23T18:26:28.193-05:00This comment has been removed by the author.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29083107086232645652021-03-23T14:03:45.894-05:002021-03-23T14:03:45.894-05:00Is this of any use? (-1 + x)^5 * (1 + x + x^2 + x...Is this of any use? (-1 + x)^5 * (1 + x + x^2 + x^3 + x^4)^3 * (1 + 2 x^5 + 2 x^10 + 2 x^15 + 2 x^20 + x^25))Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14469194699312415162021-03-23T13:05:04.490-05:002021-03-23T13:05:04.490-05:00There is a recent paper by A. Bostan and R. Mori t...There is a recent paper by A. Bostan and R. Mori that provides a fast algorithm for this task, and more generally is able to compute any coefficient of the Taylor expansion of any rational function, in quasi-optimal time: "A Simple and Fast Algorithm for Computing the N-th Term of a Linearly Recurrent Sequence." with a short version at SOSA'21. (cf https://specfun.inria.fr/bostan/BoMo20.pdf)<br /><br />The main, simple and elegant idea to compute the N-th term of F = P/Q is as follows:<br /><br />1. Write F = P(X)Q(-X)/Q(X)Q(-X)<br /><br />2. Compute V s.t. Q(X)Q(-X) = V(X²)<br /><br />3. Compute U_o, U_e s.t. P(X)Q(-X) = U_e(X²) + X U_o(X²)<br /><br />4. Recursively compute the N/2-th term of either U_e/V or U_o/V, depending on the parity of N<br /><br />This provides a divide-and-conquer algorithm that runs very fast (see details in the paper).B.noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26322080873713589572021-03-23T12:09:39.735-05:002021-03-23T12:09:39.735-05:00I did make an error (the 1-x factor is in the deno...I did make an error (the 1-x factor is in the denominator, not the numerator) so indeed you need to make change with 1,5, 10 and 25 cents (though not 2, I think) and the answer is an order of magnitude higher than what I wrote.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51813667542180088192021-03-23T11:53:14.733-05:002021-03-23T11:53:14.733-05:00That IS what I had in mind, though either you or I...That IS what I had in mind, though either you or I has made an error, please respond since if it was me I need to fix my Thursday post.<br />I thought I had making 100 dollar with 1,2,5,10,25 (I was thinking of change of a dollar with pennies, nickels, dimes, and quarters.) <br />Please check your work and get back to me either by email or by comments. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46056074118063547942021-03-23T11:47:28.087-05:002021-03-23T11:47:28.087-05:00Obviously partial fractions is one way. In this in...Obviously partial fractions is one way. In this instance a slicker way is to factor out 1-x and notice the other factor has only powers of x^5. So you need the coefficient of x^100 in the reciprocal of that other factor. Replace x^5 by y and you need the coefficient of y^20 in 1/((1-y)*(1-y^2)*(1-y^5)), or equivalently the number of ways to make $20 with 1,2 and 5 dollar bills, which is easy enough to calculate by hand and is 29.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86362279021138366382021-03-23T09:13:27.046-05:002021-03-23T09:13:27.046-05:00Yes, taylor series at 0Yes, taylor series at 0gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60933806352105336982021-03-23T07:26:40.577-05:002021-03-23T07:26:40.577-05:00Do you mean at x = 0? Do you mean at x = 0? Anonymoushttps://www.blogger.com/profile/14575573140600376611noreply@blogger.com