A polynomial product of the form \[(1-z)^{b_1}(1-z^2)^{b_2}(1-z^3)^{b_3}(1-z^4)^{b_4}(1-z^5)^{b_5}\cdots(1-z^{32})^{b_{32}},\]where the $b_k$ are positive integers, has the surprising property that if we multiply it out and discard all terms involving $z$ to a power larger than $32$, what is left is just $1-2z$. Determine, with proof, $b_{32}$.
Problem
Source:
Tags: AMC, USA(J)MO, USAMO, algebra, polynomial, algebra unsolved
13.03.2018 20:32
As a preface, I'll remark that I only managed to solve this problem after three days of on and off work and through extensive computer usage. That being said, this problem is freaking amazing. First generalize the problem. Turn $b_1,b_2,\ldots$ into an infinite sequence such that for all $k\in\mathbb N$, the polynomial \[P_k(z) := (1-z)^{b_1}(1-z^2)^{b_2}\cdots(1-z^{k})^{b_{k}}\]has the property that if we multiply it out and discard all terms involving $z$ to a power larger than $k$, what is left is just $1-2z$. It is easy to see that by induction this is unique. Indeed, if $P_k(z) = 1-2z + a_{k+1}z^{k+1} + \cdots$, then $P_{k+1}(z) = P_k(z)(1-z^{k+1})^{a_{k+1}}$, i.e. $b_k = a_{k+1}$. Further remark that each $P_k$ has the property that $P_k(\tfrac 1z) = (-z)^{\deg P_k}P_k(z)$ - this will be useful later. Now let $Q_{n,k}$ denote the sum of the $k^{\text{th}}$ powers of the roots of $P_n$. I claim that $Q_{n,n} = 2^n$ for all $n$. We prove this by induction. The base case of $n=1$ is easy, since we need $b_1 = 2$, and so the sum of the roots of $P_1$ is two. Now assume the result holds for some $n$. Note that the sum of the $n^{\text{th}}$ powers of the roots of $P_{n+1}$ is equal to the sum of the $n^{\text{th}}$ powers of $P_n$ plus the sum of the $n^{\text{th}}$ powers of the roots of $(1-z^{n+1})^{b_{n+1}}$. But upon letting $\omega$ be a primitive $(n+1)^{\text{st}}$ root of unity, we see that \[1 + \omega^n + \omega^{2n} + \cdots + \omega^{n^2} = \overline{1+\omega + \omega^2 + \cdots + \omega^n} = 0,\]and so $Q_{n+1,n} = Q_{n,n}$. Now by Newton's Sums, since all coefficients of $P_n$ smaller than $n$ (not including the $1-2z$ terms) are zero, we obtain \[0 = Q_{n+1,n+1} - 2Q_{n+1,n} = Q_{n+1,n+1} - 2Q_{n,n}\quad\Rightarrow\quad Q_{n+1,n+1} = 2Q_{n,n} \stackrel{\text{(IH)}}= 2^{n+1}\]as desired. (Note that here we use the antisymmetry result from earlier, since it says that we can focus on the lower terms as opposed to the higher terms to perform the Newton's sum calculations.) Now we need another expression for $Q_{n,n}$ in terms of the $b_i$. This is actually not so bad. Indeed, note that $Q_{n,n}$ is the sum of the $n^{\text{th}}$ powers of the roots of $(1-z^k)^{b_k}$ for all $k$. A quick check shows that this equals $kb_k$ if $k\mid n$ and $0$ otherwise, and so we obtain the formula \[2^n = \sum_{d\mid n}db_d.\]It follows by Mobius Inversion that \[b_n = \frac1n\sum_{d\mid n}\mu\left(\frac nd\right)2^d\qquad\text{for all }n\geq 1,\]and so $b_{32} = \tfrac1{32}(2^{32} - 2^{16}) = \boxed{2^{27} - 2^{11}}$.
07.11.2020 19:48
Taking the logarithm we would obtain ($n=32$) \[ \sum_{k=1}^{n} b_k \sum_{j \geqslant 1} \frac{z^{jk}}{j} = -\log (1-2z+O(z^{n+1})) = \sum_{\ell = 1}^{n} \frac{2^{\ell} z^{\ell}}{\ell} + O(z^{n+1}) .\]By comparing the coefficient of $z^{\ell}$ we derive that \[ \sum_{k \mid \ell} kb_k = 2^{\ell}, \qquad \ell \leqslant n .\]It follows that \[b_n = \frac1n\sum_{d\mid n}\mu\left(\frac nd\right)2^d.\]
17.12.2022 20:18
djmathman wrote: As a preface, I'll remark that I only managed to solve this problem after three days of on and off work and through extensive computer usage. That being said, this problem is freaking amazing. First generalize the problem. Turn $b_1,b_2,\ldots$ into an infinite sequence such that for all $k\in\mathbb N$, the polynomial \[P_k(z) := (1-z)^{b_1}(1-z^2)^{b_2}\cdots(1-z^{k})^{b_{k}}\]has the property that if we multiply it out and discard all terms involving $z$ to a power larger than $k$, what is left is just $1-2z$. It is easy to see that by induction this is unique. Indeed, if $P_k(z) = 1-2z + a_{k+1}z^{k+1} + \cdots$, then $P_{k+1}(z) = P_k(z)(1-z^{k+1})^{a_{k+1}}$, i.e. $b_k = a_{k+1}$. Further remark that each $P_k$ has the property that $P_k(\tfrac 1z) = (-z)^{\deg P_k}P_k(z)$ - this will be useful later. Now let $Q_{n,k}$ denote the sum of the $k^{\text{th}}$ powers of the roots of $P_n$. I claim that $Q_{n,n} = 2^n$ for all $n$. We prove this by induction. The base case of $n=1$ is easy, since we need $b_1 = 2$, and so the sum of the roots of $P_1$ is two. Now assume the result holds for some $n$. Note that the sum of the $n^{\text{th}}$ powers of the roots of $P_{n+1}$ is equal to the sum of the $n^{\text{th}}$ powers of $P_n$ plus the sum of the $n^{\text{th}}$ powers of the roots of $(1-z^{n+1})^{b_{n+1}}$. But upon letting $\omega$ be a primitive $(n+1)^{\text{st}}$ root of unity, we see that \[1 + \omega^n + \omega^{2n} + \cdots + \omega^{n^2} = \overline{1+\omega + \omega^2 + \cdots + \omega^n} = 0,\]and so $Q_{n+1,n} = Q_{n,n}$. Now by Newton's Sums, since all coefficients of $P_n$ smaller than $n$ (not including the $1-2z$ terms) are zero, we obtain \[0 = Q_{n+1,n+1} - 2Q_{n+1,n} = Q_{n+1,n+1} - 2Q_{n,n}\quad\Rightarrow\quad Q_{n+1,n+1} = 2Q_{n,n} \stackrel{\text{(IH)}}= 2^{n+1}\]as desired. (Note that here we use the antisymmetry result from earlier, since it says that we can focus on the lower terms as opposed to the higher terms to perform the Newton's sum calculations.) Now we need another expression for $Q_{n,n}$ in terms of the $b_i$. This is actually not so bad. Indeed, note that $Q_{n,n}$ is the sum of the $n^{\text{th}}$ powers of the roots of $(1-z^k)^{b_k}$ for all $k$. A quick check shows that this equals $kb_k$ if $k\mid n$ and $0$ otherwise, and so we obtain the formula \[2^n = \sum_{d\mid n}db_d.\]It follows by Mobius Inversion that \[b_n = \frac1n\sum_{d\mid n}\mu\left(\frac nd\right)2^d\qquad\text{for all }n\geq 1,\]and so $b_{32} = \tfrac1{32}(2^{32} - 2^{16}) = \boxed{2^{27} - 2^{11}}$. Could you clarify a bit more why $Q_{n+1,n+1} - 2Q_{n+1,n}=0$? Moreover, did you use $P_k(\tfrac 1z) = (-z)^{\deg P_k}P_k(z)$? Should not it be $P_k(\frac{1}{z})=(-1)^{b_1+b_2+...+b_k}\cdot z^{-{\deg P_k}}P_k(z)$?