2 2 A Linear Recurrence Scheme for the Constant Term of , P[k](z) P[k](1/z) Where P[k](z) is the Rudin-Shapiro polynomial By Shalosh B. Ekhad Let , P[k](z), be the Rudin-Shapiro polynomial, that may be defined by the recurrence 2 2 P[k](z) = P[k - 1](z ) + z P[k - 1](-z ) and the initial condition P[0](z)=1 c1 c2 c3 c4 c5 Definition: For any monomial w, in a,b,A,B,z,, a A b B z , let c1 c2 c3 c4 c5 E[a A b B z ](k), be the coefficient of z^0 in the polynomial c1 c2 c3 c4 c5 P[k](z) P[k](1/z) P[k](-z) P[k](- 1/z) z 2 2 We are interested in getting a scheme for computing the sequence, E[a A ](k) 2 2 Let's express, E[a A ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 2 2 The monomial, a A , is shortand for 2 2 P[k](z) P[k](1/z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 2 2 2 2 2 2 2 2 A B a 2 2 A b z + 2 A a b z + a A + 2 A B z b + 4 A B a b + -------- + B b z 2 2 2 2 B a b B a + -------- + ----- z 2 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 2 2 B a 2 2 2 2 2 2 ----- + a A + 4 A B a b + B b + A b z z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 2 2 2 2 -2 B a z + 2 A a + 4 A B a b that implies 2 2 2 2 2 2 E[a A ](k) = -2 E[B a z](k - 1) + 2 E[a A ](k - 1) + 4 E[A B a b](k - 1) 2 2 Note that, in the left side, the following monomials, a A , are already treated, 2 2 but we have to handle the new arrivals, B a z, A B a b, . Note that we still have to do handle the monomials in the set, 2 2 {B a z, A B a b} 2 2 Let's express, E[B a z](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 2 2 The monomial, B a z, is shortand for 2 2 P[k](- 1/z) P[k](z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 2 3 2 2 2 2 2 2 2 A b z + 2 A a b z + z a A - 2 A B z b - 4 z A B a b - 2 A B a 2 2 2 2 2 B a + z B b + 2 B a b + ----- z Discarding all odd powers of z, and replacing z^2 by z we get that it is 2 2 2 2 -2 A B a + 2 B a b + (2 A a b - 2 A B b ) z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 2 2 2 2 2 A a b z + 2 A B a z + 2 A a b - 2 A B a that implies 2 2 2 2 2 E[B a z](k) = -2 E[A B a ](k - 1) + 2 E[A a b](k - 1) + 2 E[A a b z](k - 1) 2 + 2 E[B A z a ](k - 1) 2 2 2 2 We have to handle the new arrivals, A B a , A a b, A a b z, B A z a Note that we still have to do handle the monomials in the set, 2 2 2 2 {A B a , A a b, A B a b, A a b z, B A z a } 2 Let's express, E[A B a ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 2 The monomial, A B a , is shortand for 2 P[k](1/z) P[k](- 1/z) P[k](z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 2 2 2 2 2 2 2 2 2 2 2 B a b B a A b z + 2 A a b z + a A - B b - -------- - ----- z 2 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 2 2 B a 2 2 2 2 2 2 - ----- + a A - B b + A b z z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 0 that implies 2 E[A B a ](k) = 0 We have to handle the new arrivals, 1 Note that we still have to do handle the monomials in the set, 2 2 2 {1, A a b, A B a b, A a b z, B A z a } Let's express, E[1](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following The monomial, 1, is shortand for 1 Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 1 Discarding all odd powers of z, and replacing z^2 by z we get that it is 1 Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 1 that implies E[1](k) = E[1](k - 1) Note that, in the left side, the following monomials, 1, are already treated, Note that we still have to do handle the monomials in the set, 2 2 2 {A a b, A B a b, A a b z, B A z a } 2 Let's express, E[A a b](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 2 The monomial, A a b, is shortand for 2 P[k](1/z) P[k](z) P[k](-z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 2 2 2 2 2 2 2 2 2 A B a 2 2 B a -A b z + a A - 2 A B z b + -------- - B b + ----- z 2 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 2 2 B a 2 2 2 2 2 2 ----- + a A - B b - A b z z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 0 that implies 2 E[A a b](k) = 0 Note that, in the left side, the following monomials, 1, are already treated, Note that we still have to do handle the monomials in the set, 2 2 {A B a b, A a b z, B A z a } Let's express, E[A B a b](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following The monomial, A B a b, is shortand for P[k](1/z) P[k](- 1/z) P[k](z) P[k](-z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 2 2 2 2 2 2 2 2 B a -A b z + a A + B b - ----- 2 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 2 2 B a 2 2 2 2 2 2 - ----- + a A + B b - A b z z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 2 2 2 2 2 B a z + 2 A a that implies 2 2 2 2 E[A B a b](k) = 2 E[a A ](k - 1) + 2 E[B a z](k - 1) 2 2 2 2 Note that, in the left side, the following monomials, a A , B a z, are already treated, Note that we still have to do handle the monomials in the set, 2 2 {A a b z, B A z a } 2 Let's express, E[A a b z](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 2 The monomial, A a b z, is shortand for 2 P[k](1/z) P[k](z) P[k](-z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 2 2 2 3 2 2 2 2 2 2 2 B a -A b z + z a A - 2 A B z b + 2 A B a - z B b + ----- z Discarding all odd powers of z, and replacing z^2 by z we get that it is 2 2 -2 A B b z + 2 A B a Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 2 2 2 A B a z + 2 A B a that implies 2 2 2 E[A a b z](k) = 2 E[A B a ](k - 1) + 2 E[B A z a ](k - 1) 2 Note that, in the left side, the following monomials, A B a , are already treated, 2 but we have to handle the new arrivals, B A z a , . 2 Note that we still have to do handle the monomials in the set, {B A z a } 2 Let's express, E[B A z a ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 2 The monomial, B A z a , is shortand for 2 P[k](- 1/z) P[k](1/z) z P[k](z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 2 2 2 3 2 2 2 2 2 2 2 B a A b z + 2 A a b z + z a A - z B b - 2 B a b - ----- z Discarding all odd powers of z, and replacing z^2 by z we get that it is 2 2 2 A a b z - 2 B a b Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 2 2 2 A a b z - 2 A a b that implies 2 2 2 E[B A z a ](k) = -2 E[A a b](k - 1) + 2 E[A a b z](k - 1) 2 2 Note that, in the left side, the following monomials, A a b, A a b z, are already treated, Nothing left to do. Summing up we found the following scheme for the sequences 2 2 2 2 2 2 E[1](k), E[a A ](k), E[A B a ](k), E[A a b](k), E[B a z](k), E[A B a b](k), 2 2 E[A a b z](k), E[B A z a ](k) as follows E[1](k) = E[1](k - 1) 2 2 2 2 2 2 E[a A ](k) = -2 E[B a z](k - 1) + 2 E[a A ](k - 1) + 4 E[A B a b](k - 1) 2 E[A B a ](k) = 0 2 E[A a b](k) = 0 2 2 2 2 2 E[B a z](k) = -2 E[A B a ](k - 1) + 2 E[A a b](k - 1) + 2 E[A a b z](k - 1) 2 + 2 E[B A z a ](k - 1) 2 2 2 2 E[A B a b](k) = 2 E[a A ](k - 1) + 2 E[B a z](k - 1) 2 2 2 E[A a b z](k) = 2 E[A B a ](k - 1) + 2 E[B A z a ](k - 1) 2 2 2 E[B A z a ](k) = -2 E[A a b](k - 1) + 2 E[A a b z](k - 1) In order to simplify notation, let 2 2 2 2 2 E[1](k) = E[a A ](k), E[2](k) = E[B a z](k), E[3](k) = E[A B a ](k), 2 E[4](k) = E[1](k), E[5](k) = E[A a b](k), E[6](k) = E[A B a b](k), 2 2 E[7](k) = E[A a b z](k), E[8](k) = E[B A z a ](k) Our scheme becomes E[1](k) = -2 E[2](k - 1) + 2 E[1](k - 1) + 4 E[6](k - 1) E[2](k) = -2 E[3](k - 1) + 2 E[5](k - 1) + 2 E[7](k - 1) + 2 E[8](k - 1) E[3](k) = 0 E[4](k) = E[4](k - 1) E[5](k) = 0 E[6](k) = 2 E[1](k - 1) + 2 E[2](k - 1) E[7](k) = 2 E[3](k - 1) + 2 E[8](k - 1) E[8](k) = -2 E[5](k - 1) + 2 E[7](k - 1) Subject to the obvious initial conditions E[1](0) = 1, E[2](0) = 0, E[3](0) = 1, E[4](0) = 1, E[5](0) = 1, E[6](0) = 1, E[7](0) = 0, E[8](0) = 0 Now let's try to find explicit expressions for the (ordinary) generating fun\ ctions, in the variable infinity ----- \ k F[i](t) = ) E[i](k) t / ----- k = 0 For i from 1 to, 8 The above recurrences for the sequences, E[i](k), translate to the following system of linear equations for F[i](t), for i from 1 to, 8 F[1](t) = 1 + t (-2 F[2](t) + 2 F[1](t) + 4 F[6](t)) F[2](t) = t (-2 F[3](t) + 2 F[5](t) + 2 F[7](t) + 2 F[8](t)) F[3](t) = 1 F[4](t) = 1 + t F[4](t) F[5](t) = 1 F[6](t) = 1 + t (2 F[1](t) + 2 F[2](t)) F[7](t) = t (2 F[3](t) + 2 F[8](t)) F[8](t) = t (-2 F[5](t) + 2 F[7](t)) Solving this system gives explicit expressions for each of, F[i](t), and in particular, we find that our object of desire 4 t + 1 F[1](t) = - ------------------- (2 t + 1) (4 t - 1) This concludes the article that took, 0.018, seconds to generate.