# Find polynomials such that $(x-16)p(2x)=16(x-1)p(x)$

Find all polynomials $p(x)$ such that for all $x$, we have $$(x-16)p(2x)=16(x-1)p(x)$$

I tried working out with replacing $x$ by $\frac{x}{2},\frac{x}{4},\cdots$, to have $p(2x) \to p(0)$ but then factor terms seems to create a problem.

-

Putting $x=1$ and $x=16$ we see that $p(2)=p(16) = 0$.

Let $p(x) = (x-2)(x-16)g(x)$.

Thus we see that

$$(x-16)(2x-2)(2x-16)g(2x) = 16(x-1)(x-2)(x-16)g(x)$$

Thus $$(x-8)g(2x) = 4(x-2)g(x)$$

We now see that $g(4) = g(8) = 0$

Thus $g(x) = (x-4)(x-8)h(x)$

Thus $$(x-8)(2x-4)(2x-8)h(2x) = 4(x-2)(x-4)(x-8)h(x)$$

i.e

$$h(2x) = h(x)$$

This implies that $h(x)$ is a constant (as otherwise the non-identically zero polynomial $h(2x) - h(x)$ will have an infinite number of roots.)

Thus

$$p(x) = C(x-2)(x-4)(x-8)(x-16)$$

-
Good solution! –  anonymous Sep 2 '10 at 18:24

Hint $\:$ Note the equation is $\displaystyle \rm\; \frac{\sigma\:f}f \:=\; \frac{\sigma^4 g}g\$ for $\rm\ g = x-16 \:,\:\;$ shift $\rm\;\;\sigma\:f(x) = f(\sigma\:x) = f(2\:x)$

Or, written additively $\rm\ (\sigma-1) \; f \;=\: (\sigma^4 - 1) \; g \quad\;$ [see Note below on this additive notation]

Thus $\rm\;\; f\, =\,\smash{\dfrac{\sigma^4-1}{\sigma-1}}\,g\, =\, (1+\sigma+\sigma^2\!+ \sigma^3) \: g \;=\: (x-16)\:(2x-16)\:(4x-16)\:(8x-16) \;$

unique up to a factor of $\rm\;h \in ker(\sigma-1) = \{h: \sigma\:h = h\:\} = \;$ constants, i.e. $\rm deg\;h = 0 \ \$ QED

Remark $\;$ This reformulation of my prior answer is intended to dramatically illustrate the innate symmetry. Its striking simplicity arises precisely from the simple structure of the orbits of the shift automorphism $\rm\: \sigma.\;$ Namely, by orbit decomposition the problem reduces to one on the single orbit of an irreducible polynomial. By exploiting polynomial structure there, we reduce the problem to a trivial polynomial division by $\rm\:\sigma - 1.\:$ This nicely illustrates the essence of the ideas employed to solve general difference equations (recurrences) over rational function fields - ideas at the foundation of algorithms employed in computer algebra systems.

Hopefully the symmetry is clearer in the above reformulation. Based on prior comments, and someone reposting my prior solution stripped of the symmetry, I fear my prior answer did not succeed in explicitly emphasizing the beautiful innate symmetry lying at the heart of this problem - a germ of the Galois theory of difference fields. Probably the problem was devised to help spur one to discover this beautiful structure.

Note $\;\;$ The point of the additive notation is to exploit the natural polynomial structure of the action of $\rm\:\sigma\:$ on the multiplicative group generated by the elements $\rm\: \sigma^n \,f\;$ in the orbit of $\rm\!\: f \!\:$ under $\rm\:\sigma.\:$ This action is best comprehended by examining it on a specific example. Recalling $\rm\,\sigma\,f(x) = f(2\:\!x)$

\quad\quad\begin{align}{} \rm \sigma\:(\:f(2^{-2}\: x)^a \; f(2^3 x)^b \;\: f(2^5 x)^c)\; =& \rm\;\;\: f(\:2^{-1} x)^a \;\: f(2^4 x)^b \;\: f(2^6 x)^c \\\\ \rm \iff \quad\;\;\: \sigma\;\:(\:(\:\sigma^{-2}\: f\;)^a \;\; (\:\sigma^3\: f\:)^b \;\; (\:\sigma^5\: f\:)^c)\; =& \rm\;\; \;\; (\:\sigma^{-1} \: f\:)^a \;\; (\:\sigma^4 \: f\:)^b \;\; (\:\sigma^6 \: f\;)^c \\\\ \rm \iff \quad\;\; \sigma\; (\:a\:\sigma^{-2} \;+\:\;\; b\:\sigma^3 \;+\;\; c\:\sigma^5)\:\; f\quad\; =& \rm\; (\:a\:\sigma^{-1} \: + \:\;\: b\: \sigma^4 \; +\;\; c\: \sigma^6)\; f \\\\ \end{align}

In the Galois theory literature the above action is frequently written in a highly suggestive exponential form. To illustrate this, below is the key identity in the problem at hand, expressed in this exponential notation.

\quad\quad\begin{align}{} \rm g^{\:\sigma^4-\,1} \;=\;& \rm g^{\:(1\:+\;\sigma\:+\;\sigma^2\:+\:\,\sigma^3)\:(\sigma\,-\,1)} \\\\ \iff\quad\quad\rm \frac{\sigma^4 g}g \;=\;& \rm (g \;\: \sigma\:g \;\:\sigma^2 g \;\:\sigma^3 g)^{\sigma - 1} \;=\; \frac{\phantom{g\;\;\:} \sigma\:g \;\;\: \sigma^2 g \;\;\:\sigma^3 g \;\;\:\sigma^4 g}{g \;\;\:\sigma\:g \;\;\:\sigma^2 g \;\;\:\sigma^3 g\phantom{\;\;\:\sigma^4 g}} \\\\ \end{align}

-
very nice way to do it!! & nice to have a view toward generalizations –  anon Sep 6 '10 at 17:08
How do you get $(S-1)f = (S^4-1)g$? What does $S-1$ even mean? –  Aryabhata Sep 6 '10 at 17:10
btw, Thank you for taking the time to write this out! Sorry for the possibly basic question. –  Aryabhata Sep 6 '10 at 17:19
This is the canonical, beautiful solution. Thanks to Bill for posting it; indeed it is not equivalent to the other approaches. To place it more visibly in the familiar operator framework: let F(x) = log |p(x)| and G(x)=log |g(x)|=log |x-16| (or use logarithmic derivatives rather than logs), and S be the linear operator that takes a function h(x) to h(2x), and 1 the identity operator that takes h(x) to h(x). –  T.. Sep 6 '10 at 19:32
@Moron: I've added an explicit example to help clarify the additive action. Let me know if this is still not clear. –  Bill Dubuque Sep 6 '10 at 20:30
show 1 more comment

Moron's solution and Dubuque's solution are essentilly the same, but I think their presentations can be made neater.

Clearly, $p$ is not a constant polynomial (unless it is zero). So we may write $p(x) = C(x-z_1)(x-z_2)\ldots(x-z_n)$. Then the given equality implies that

$(2x-z_1)(2x-z_2)\ldots(2x-z_n)(x-16) = 16(x-1)(x-z_1)(x-z_2)\ldots(x-z_n)$.

By comparing the leading coefficient on both sides, one sees $n=4$. Thus,

$(x-\frac{z_1}{2})(x-\frac{z_2}{2})(x-\frac{z_3}{2})(x-\frac{z_4}{2})(x-16)=(x-1)(x-z_1)(x-z_2)(x-z_3)(x-z_n)$.

Hence $\lbrace \frac{z_1}{2}, \frac{z_2}{2}, \frac{z_3}{2}, \frac{z_4}{2}, 16\rbrace = \lbrace 1, z_1, z_2, z_3, z_4\rbrace$. Now one easily sees that, up to a relabelling of indices, we must have $z_i = 2^i$.

-
+1: This is clearer :-) –  Aryabhata Sep 2 '10 at 22:54
Have to disagree with Bill here. I might be a Moron, but this answer is way better than Bill's. This is an easy problem, accusing someone of plagiarism is just silly. –  Aryabhata Sep 2 '10 at 23:19
But it is precisely the same as my proof stripped of all the motivational and conceptual details. I'm very sad that you reposted it like that since it may have the effect that some readers may be happy with this stripped-down version and never end up seeing the conceptual background as I presented it. And this - after all - is the whole point of proofs - to learn something new - not merely to determine the boolean value of some proposition. There are always shorter paths but why take them if they miss out on all the beautiful scenery? –  Bill Dubuque Sep 2 '10 at 23:37
@Moron: Bill is not accusing me of plagiarism because I have stated clearly that the soln I give is just a rewrite of yours and Bill's. He is just unsatisfied that some of the math concepts in his soln have become hidden in my rewrite, so that one doesn't see a full picture. This is a valid point, but I think getting something that a novice can understand first is more important. –  user1551 Sep 3 '10 at 8:41
@user1551: I agree that your answer is much easier to understand (hence my comment about it being better). You can't always cover all the math concepts/insights which could be used to prove something, so I don't see any justification to his objection/accusation. –  Aryabhata Sep 3 '10 at 13:44

Since $\rm\;p(2x)\;$ has roots being half the roots $\rm\;r_i\;$ of $\rm\;p(x)\;$, and $\rm\;\frac{p(x)}{p(2x)} = \frac{x-16}{16(x-1)}\;$, for the roots to all cancel like that leaving only one term in the numerator and denominator, we must have simply that the map $\rm\;r\to r/2\;$ is a left shift map on the (intermediate) roots. The numerator shows the largest root is 16, and the denomimator shows half the smallest root is 1. The other intermediate roots must obey the left shift $\rm\;r_i/2 = r_{i-1},\;$ so the roots are $\rm\;2,4,8,16,\;$ i.e. $\rm\;p(x) = c(x-2)(x-4)(x-8)(x-16)\;$

EDIT$\:$ I purposely omitted a detail above since I thought it might be a homework problem. Based on the comments, this caused some confusion, so I will elaborate. Namely, notice that each linear linear factor of $\rm\;p(x)\;$ introduces a constant factor of $2\:$ in the denominator of $\rm\: p(x)/p(2x)$. But said denominator has constant factor $16$, so the $4$ factors found above are complete. In particular, $0$ cannot be a root of $\rm\:p(x).$

-
Where do you use the value of 16 in the denominator of the right hand side? If you replace that value by anything else, the solution is the empty set (as is readily seen by letting $x = 0$). –  whuber Sep 2 '10 at 21:50
This answer also ignores the possibility that $p(0) = 0$. –  Aryabhata Sep 2 '10 at 21:56
@Moron: No, the proof explicitly determines the roots via their shift symmetry. That zero is not one of them is not relevent. –  Bill Dubuque Sep 2 '10 at 22:03
@whuber: The proof doesn't need to use the 16 in the denominator (except to verify that said p(x) is a solution - which trivial fact I left to the reader - it's obvious if you understand the proof) –  Bill Dubuque Sep 2 '10 at 22:06
@Bill: What you said does nothing to eliminate the fact that x^k could be a factor of p(x). Why can't your 'shift symmetry map' map 0 to itself? Also, $p(x) = 0$ does not imply $p(2x) = 0$ (from the functional equation). For instance, $x=16$. –  Aryabhata Sep 2 '10 at 22:14
I love Moron's approach. Because it is usually interesting to look at other solutions, consider what happens if you just write $p(x) = p_n x^n + p_{n-1}x^{n-1} + \cdots + p_0$ and write out the equation. Comparing the coefficients of $x^k$ ($k \gt 0$) yields the recursion
$p_k= \frac{2^{k-5}-1}{2^k - 1} p_{k-1}$,
whence $p_5 = 0$, implying $p_6 = p_7 = \cdots = 0$, and the rest of the recursion yields $p_4, p_3, \ldots, p_0$ as multiples of $p_4$. This approach, although pedestrian, also demonstrates that we need only assume $p$ is analytic near 0.