Let $P,Q,R,S$ be non constant polynomials with real coefficients, such that $P(Q(x))=R(S(x)) $ and the degree of $P$ is multiple of the degree of $R. $ Prove that there exists a polynomial $T$ with real coefficients such that $$\displaystyle P(x)=R(T(x))$$
Problem
Source: 2023 RMM, Problem 5
Tags: Polynomials, RMM 2023, number theory, algebra
04.03.2023 20:18
Since $Q$ is non constant, it is sufficient to show it is possible to find $T$ such that $S(x)=T(Q(x))$, given the hypothesis that the degree of $S$ is a multiple of the degree of $Q$ (which is equivalent to the degree condition in the statement). Let $q$ be degree of $Q$, $mq$ the degree of $S$ and $r$ that of $R$. By performing euclidean division by $Q$ on $S$ a bunch of times, we get that we can write $S=\sum_{i=0}^m C_i Q^i$, where $C_i$ is a polynomial of degree $<q$ and $C_m$ is a constant (since the total degree has to be $mq$). If all the $C_i$'s were constants we would be done, else take the largest $k$ for which $C_k$ is not constant and write $S=U(Q)+V$, where $U(x)=\sum_{i=k+1}^m C_i x^i$ and $V=\sum_{i=0}^k C_i Q^i$, noticing that the degree $v$ of $V$ is strictly smaller than the degree $mq$ of $U(Q)$ and is not a multiple of $q$. Since $R(U(Q)+V)-R(U(Q))=P(Q)-R(U(Q))$ is a polynomial of $Q$, its degree must be a multiple of $q$, but we'll see this is not possible. Indeed, if we consider some monomial $ax^j$ of $R(x)$, we see that this corresponds to $a(U(Q)+V)^j-a(U(Q))^j=aj(U(Q))^{j-1}V+\cdots$, so its degree is $(j-1)mq+v$. This means that the maximal degree term of $R(U(Q)+V)-R(U(Q))$ has degree $(r-1)mq+v$, which is not a multiple of $q$, so we get the desired contradiction. $\square$
04.03.2023 22:07
I solved it on contest, and can attest to it being straightforward. You just need to try to prove $S(x)=T(Q(x))$ which is a common Euclidean algorithm-type argument.
05.03.2023 18:32
Same solution as above. A very instructive problem although I think it's kind of hit or miss which probably explains the low solve rate. It suffices to prove that $S=T(Q)$, now perform the division algorithm repeatedly to get $S=T(Q)+U$, clearly $deg (Q) \nmid deg (U)$. Consider $R(T(Q)+U)-R(T(Q))=P(Q)-R(T(Q))=V$ which means $deg (Q) \mid deg (V)$ but expand and notice that, $$deg (R(T(Q)+U)-R(T(Q))=deg(T) \cdot deg(Q)(deg(R)-1)+deg(U)$$which is a contradiction since this is not divisible by $deg (Q)$
07.03.2023 10:34
Solved with eisirrational, goodbear, nukelauncher, and Th3Numb3rThr33. By remainder theorem we may write \(S(x)\) in ``base \(Q(x)\)'' as \(S(x)=S_0(x)+Q(x)\cdot S_1(x)+Q(x)^2\cdot S_2(x)+\cdots+Q(x)^d\cdot S_d(x)\), where \(\deg S_i<\deg Q\). Since \(\deg Q\mid\deg S\), we know \(S_d\) is constant. It will suffice to show \(S_0\), \ldots, \(S_{d-1}\) are all constant, after which we can take \(T(x)=S_0+S_1x+\cdots+S_dx^d\). We proceed by downward induction. Suppose \(S_d\), \(S_{d-1}\), \ldots, \(S_{d-i+1}\) are constant. We will show \(S_{d-i}\) is constant. Consider the expansion of \[P(Q(x))= R(S_dQ(x)^d+\cdots+S_{d-i+1}Q(x)^{d-i+1}+S_{d-i}(x)Q(x)^{d-i}+\cdots).\]If we express the right-hand side in base \(Q(x)\), the coefficients of \(Q(x)^{d\deg R}\), \ldots, \(Q(x)^{d\deg R-i+1}\) are determined only by \(S_d\), \ldots, \(S_{d-i+1}\) and thus constant. These terms must also be present from the left-hand side, so eliminate them from both sides. Then the resulting expression on the left-hand side has degree at most \((d\deg R-i)\deg Q\). However, we may check that the only term on the right-hand expansion with terms of degree greater than \((d\deg R-i)\deg Q\) is a constant times \(S_d^{\deg R-1}Q(x)^{d(\deg R-1)}\cdot S_{d-i}(x)Q(x)^{d-i}\), which has degree \((d\deg R-i)\deg Q+\deg S_{d-i}\). It follows that \(\deg S_{d-i}=0\).
09.03.2023 15:06
17.08.2023 14:10
Let the degree of $P$ be $k\ell$ and the degree of $R$ be $\ell$. Then we can choose the numbers $a_0, a_1,\dots,a_k$ such that the two polynomials: $$R(a_0y^k+a_1y^{k-1})+\dots+a_{k-1}y+a_k)$$and $P(y)$ have the same coefficients in front of $y^{k\ell}, y^{k\ell-1},\dots, y^{k\ell}-k$. It can be done by consecutively determining the coefficients $a_0,a_1,\dots a_k$. Let us write $$P(y)=R\big(a_0y^k+a_1y^{k-1}+\dots+a_{k-1}y+a_k + \Delta(y)\big)\qquad (1)$$where $\Delta(y)$ is some quantity that can be uniquely determined when $|y|$ is sufficiently large, since $R$ is monotonic for large $|y|$. We claim that $\Delta(y)\to 0$ as $|y|\to\infty$. Indeed, assume on the contrary, it's not the case. Then there will be $\varepsilon>0$ and infinitely many $y$ with magnitude as large as we want such that $|\Delta(y)|\ge \varepsilon$. Let $a_k':=a_k+\Delta(y)$. Then $$R\big(a_0y^k+a_1y^{k-1}+\dots+a_{k-1}y+a'_k\big)-P(y)\qquad(2)$$would be a polynomial of degree $k\ell-k$ and a senior coefficient of magnitude at least $C\cdot \varepsilon$ for some constant $C$. This means that it's not possible $(2)$ be zero for large enough $|y|$. Next, let us denote $T(y):=a_0y^k+a_1y^{k-1}+\dots+a_{k-1}y+a_k$ and put $y:=Q(x)$ in $(1)$. $$R(S(x))=P(Q(x))=R(T(Q(x)) +\Delta(Q(x)))$$It follows $$S(x)=T(Q(x)) +\Delta(Q(x))$$which means that $S(x)=T(Q(x))$ since otherwise it's impossible that $\Delta(Q)\to 0$ as $Q\to \pm\infty$.
28.08.2023 17:56
Here's an overkill ,using the following lemma: Lemma. Let $P \in \mathbb{R}[x]$ and $deg(P)=ab$ then there exists a unique monic polynomial $Q$ st: $deg(P - Q^a) \leq (a-1)b$ where here , $f^n$ means $f$ is applied $n$ times.
Clearly it's enough to show that $S = T(Q)$ for some $T$ and note that $deg (Q) | deg (S)$. Assume wlog that $P,R$ are monic and assume ftsoc the statement doesn't hold.Let $P(Q(x))=R(S(x)) =A(x)$ and denote : $$deg(S) = kq , deg(Q) = q , deg(A) = t.kq , deg(P) = t ,deg(R)=tk$$Define $U,V$ as two monic polynomials satisfying the following: $$deg(P(Q) - U^t(Q)) \leq (t-1)k , deg(R(S) - V^t(S)) \leq (t-1)k$$which exists by the lemma. Now note that $$deg((U(Q)-V(S))(U^{t-1}(A)+...+V^{t-1}(B))=(deg(U^t(Q) - V^t(S)) \leq max \{deg(P(Q) - U^t(Q)) , deg(R(S) - V^t(S)) \} = (t-1)k$$But in $U^{t-1}(A)+...+V^{t-1}(B)$ , since all the terms were monic and have equal degree , the total degree would be at least $(t-1)k$ .So by the above inequality $U(Q)-V(S) = 0$.But since the statement was false , $t >1$ and we'll have two polynomials which satisfy the initial condition , but with smaller degrees than $P,Q$ which will clearly fail us after processing the same thing we've done so far a bunch of times till we get the smallest degrees for $P,R$ so that one of them has degree zero which is a contradiction since they were non-constant.
28.08.2023 22:11
The main part of the problem is to prove that there exists a polynomial $T$ such that $S(x)=T(Q(x))$. Since $\deg R \mid \deg P$, $\deg Q \mid \deg S$, so let $\deg S=m\deg Q$ where $m>0$ is an integer. The key idea is to now write $S(x)=T(Q(x))+U(x)$ according to the following algorithm. First initialize $T$ and $U$ to the zero polynomial. Then initialize a polynomial $S'(x)$ to $S(x)$ (this is not a derivative) and a counter variable $k$ to $m$. Then while $k \geq 1$, choose the constant $c$ (possibly equaling zero) such that $\deg (S'(x)-cQ(x)^k)<k\deg Q$, and subtract $cQ(x)^k$ from $S'(x)$, adding $cx^k$ to $T(x)$. Now subtract all the terms in $S'(x)$ which have degree greater than $(k-1)\deg Q$ and add them to $U(x)$, and repeat, decrementing $k$. Finally, add any remaining constant term to $T(x)$. For example, if $S(x)=x^4+x^3+2x+1$ and $Q(x)=x^2$, then $T(x)=x^2+1$ and $U(x)=x^3+2x$. In this representation, it is clear that no nonzero term in $U(x)$ has degree divisible by $\deg Q$, and that $\deg U<m\deg Q=\deg (T\circ Q)$. Now compare $P(Q(x))$ and $R(T(Q(x))+U(x))$: the former can be written in "base $Q$", i.e. as a linear combination of powers of $Q$. On the other hand, if $U$ has leading term $tx^d$ where $d>0$, then I claim that this will not be the case for $R(T(Q(x))+U(x))$. Indeed, the expansion of $R(T(Q(x))+U(x))$ will have some terms which are very clearly constant multiples of powers of $Q$, namely those obtained by multiplying $T(Q(x))$ with itself, and these can be ignored. After ignoring such terms, if $r$ is the leading coefficient of $R(x)$ then according to the binomial theorem the highest degree term that we care about will be found in $$r(nt^{n-1}T(Q(x))^{n-1}x^d),$$but since $\deg Q \nmid d$ this highest degree term (with degree $d+m(n-1)\deg Q$) will not have degree divisible by $\deg Q$ either. Since every higher degree term was accounted for in a power of $Q$ already and thus ignored, it follows that this highest degree term cannot be included in any power of $Q$: contradiction. This evidently implies that $U \equiv 0$, proving the claim. To finish, note that we are given $P(Q(x))=R(T(Q(x))$ as a polynomial identity. Since $Q$ is nonconstant, for any $w \in \mathbb{C}$ there exists some $z \in \mathbb{C}$ such that $Q(z)=w$, and by plugging in $x=z$ we obtain that $P(w)=R(T(w))$. Since this holds for all complex numbers it is also a polynomial identity, which finishes the problem. $\blacksquare$
06.11.2024 00:28
Let $\deg P = p$ and define $q, r, s$ similarly. Then $r \mid p$ and $q \mid s$ and $k = p \cdot q = r \cdot s$. Now take large real $t$ and consider the roots of \[ P(Q(x)) = R(S(x)) = t. \]We have that $z^k$ is the dominating factor asymptotically which implies that for large $t$, the roots have arguments within $\varepsilon$ of $\frac{j}{k}$ where each $j$ is distinct (here the arguments are taken as $\mathbb{R}/\mathbb{Z}$) and are large. This means that if the roots are $r_1, r_2, \dots, r_t$, where argument of $r_i$ is around $\frac{i}{t}$ then if \[ Q(r_i) = Q(r_j) \iff \frac{qi}{k} \approx \frac{qj}{k} \pmod{1} \implies \frac{si}{k} \approx \frac{sj}{k} \pmod{1} \iff S(r_i) = S(r_j). \]for large $r_i, r_j$. Claim: If $Q(x) - Q(y) = 0$ implies $S(x) - S(y)$ for large $(x, y)$ then $\deg Q \mid \deg S$ then $S = T \circ Q$ for some polynomial $T$. Proof. Fix a large $y$ then we get that $Q(x) - Q(y)$ divides $S(x) - S(y)$ so \[ S(x) = (Q(x) - Q(y)) \cdot T(x) + S(y) \]and show the result for $T(x)$ inductively, the base case of $\deg Q = \deg S$ follows as $T(x)$ becomes a constant. $\blacksquare$ As such, since $P(Q(x)) = R(T(Q(x)))$ it follows that $P(x) = R(T(x))$.