# 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
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

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$.

-
If you think that Moron's solution is the same as mine then - like Moron - it appears that you probably do not truly understand my solution. My solution explictly exploits the innate symmetry of the problem. By removng that explanation it makes the proof appear like it was pulled out of a hat. That it may appear "simpler" is only deceptive since you've merely eliminated my words explaining the motivation for how to discover the proof. You've simply copied my proof and eliminated all the useful conceptual ideas. Why do that? – Bill Dubuque Sep 2 '10 at 23:14
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
@Bill: I really don't see any substantial differences between your soln and Moron's. Your so-called "innate symmetry", was used in both solutions. You just do a left shift, and Moron squeezes from both directions. The true difference between the two solutions, I believe, is that Moron's solution is constructive in nature, while in your solution, one needs to stop and think about why one must begin from (x-16) --- but not, say, (x-17) --- in order for the left shift map to terminate in finite time. [to be cont'd] – user1551 Sep 3 '10 at 8:21
[cont'd] ... So, yes, your solution involves more advanced mathematical concepts, but I wonder if a student who cannot solve this problem can understand your solution at all. You seem to say that I strip down your proof to please the readers. No. The motive behind this rewrite is not to make them happy, but to make sure that we have a solution that at least a novice can understand. Moron's solution is easy, but a bit tedious to my taste. Yours, frankly, is too advanced for someone who, say, takes a freshman Calculus course. I only try to strike the middle ground. – user1551 Sep 3 '10 at 8:31
@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

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
@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
@Moron: My proof shows that p(x) must have at least those 4 linear factors. Since each linear factor (including x) introduces a factor of 2 in the denominator of p(x)/p(2x) it follows that p(x) can have no further factors else the constant in the denominator would exceed 16. I have no clue what "issue" you see in the first sentence. If you don't understand something that I wrote I am happy to clarify it, but please be precise. I purposely did not provide every single detail since it appeared that this might be a homework problem. – Bill Dubuque Sep 2 '10 at 22:56
@Moron: I think you misunderstood my remark. As I said, the value of 16 isn't needed except to verify that p(x) is the solution. As I said I explicitly chose to not provide all the details since it looked like homework. After seeing all the confusion I had no choice but to reveal every detail. Apologies for the confusion that caused. – Bill Dubuque Sep 2 '10 at 23:31

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.

-