$\mathbb{Z}[x]$ represents the set of all polynomials with integer coefficients. Find all functions $f:\mathbb{Z}[x]\rightarrow \mathbb{Z}[x]$ such that for any 2 polynomials $P,Q$ with integer coefficients and integer $r$, the following statement is true. \[P(r)\mid Q(r) \iff f(P)(r)\mid f(Q)(r).\] (We define $a|b$ if and only if $b=za$ for some integer $z$. In particular, $0|0$.) Proposed by the4seasons.
Problem
Source: 2023 IRN-SGP-TWN Friendly Math Competition P6
Tags: functional equation, polynomial, polynomial with integer coeffi, algebra, number theory
R8kt
16.07.2023 18:37
Nice problem! Is it possible to find other problems from this competition?
R8kt
16.07.2023 18:38
I’m also assuming it’s F(P(r)) that divides F(Q(r))
the4seasons
16.07.2023 18:50
@above Oh it's not, that's why this problem is weird. $f(P)(r)$ is referring to the value of polynomial $f(P)$ evaluated at $x=r$.
ckliao914
17.07.2023 10:04
R8kt wrote: Nice problem! Is it possible to find other problems from this competition? https://artofproblemsolving.com/community/c3395791 this is the link to the competition this year
gghx
17.07.2023 13:12
This problem is amazing, in that it uses involved techniques in both the subtopics of Polynomials and FEs, in both fields of algebra and number theory. No guarantee this is the easiest solution: We first introduce some facts about integer polynomials Fact 1: If $P(r)\mid Q(r)$ for infinitely many $r$, then $\text{deg}(P)\le\text{deg}(Q)$ or $Q\equiv 0$. This is blatantly obvious. Fact 2: If $P,Q$ (non-zero) have the same degree and $P(r)\mid Q(r)$ for infinitely many $r$, then there exists some integer $n$ such that $Q\equiv n\cdot P$.
Let the leading coefficient of $P,Q$ be $a,b$. Note $P(r)\mid a\cdot Q(r)-b\cdot P(r)$. The RHS has smaller degree than $P$. By Fact 1 this means $aQ(r)-bP(r)=0$ so $Q(r)=\frac{b}{a}P(r)$. Substituting this back we get $a\mid b$ and we are done.
Fact 3: If $P(r)\mid Q(r)$ for infinitely many $r$, then there exists a rational polynomial $A$ such that $Q\equiv A\cdot P.$
Using long division over $\mathbb{Q}[x]$, we can find $A,B$ such that $Q\equiv A\cdot P+B$, and $\deg(B)<\deg(P)$. Multiplying the equation by the denominator of $A,B$, we can find an integer $n$ and integer polynomials $A_1,B_1$ such that $$nQ\equiv A_1\cdot P+B_1.$$Thus $P(r)\mid Q(r)$ means that $$P(r)\mid nQ(r)\implies P(r)\mid A_1(r)\cdot P(r)+B_1(r)\implies P(r)\mid B_1(r).$$But $\deg(B_1)<\deg(P)$ so $B_1\equiv 0$. This implies the result.
We now go back to the question: Find all $f:\mathbb{Z}[x]\rightarrow \mathbb{Z}[x]$ such that for any integer polynomials $P,Q$ and integer $r$ we have $$P(r)\mid Q(r)\iff f_P(r)\mid f_Q(r).$$ Claim 1: $|P(r)|=|Q(r)|\iff |f_P(r)|=|f_Q(r)|$ (if they are non zero).
Take both divisibilities and flip.
Claim 2: $f$ is injective at 0: if $f_Q\equiv0$ then $Q\equiv 0$.
Else $f_P(r)\mid f_Q(r)$ for all $P$ and $r$ so $\text{anything}\mid Q(r)$ for all $r$ so $Q\equiv 0$.
Claim 3: The degree of $f(\text{constant})$ is bounded.
Pick $Q\equiv x$ and $P\equiv a$ where $a$ is a constant. Pick $r=an$ for integer $n$. Then $$a=P(r)\mid Q(r)=an\implies f_a(an)\mid f_x(an).$$By Fact 1 we are done.
Consider the sequence of polynomials $$f_1,f_2,f_6,\cdots,f_{n!},\cdots.$$Note that for any $f_{i!},f_{(i+1)!}$, since $i!\mid (i+1)!$ we get that $$f_{i!}(r)\mid f_{(i+1)!}(r)\implies \deg(f_{i!})\le\deg(f_{(i+1)!}).$$By Claim 3 the degree is bounded, so at some point it becomes constant. Suppose $$\deg(f_{k!})=\deg(f_{(k+1)!})=\cdots.$$Consider any integer $n$ and the polynomial $f_{n\cdot k!}$. We know that $$f_{k!}(r)\mid f_{n\cdot k!}(r)\mid f_{(nk)!}(r).$$Since the degree of both sides is equal, this means $\deg (f_{n\cdot k!})=\deg (f_{k!})$. By Fact 2, this means we can find an integer $g(n)$ such that $f_{n\cdot k!}(r)=g(n)f_{k!}(r)$. Set $k!=C$. We have $f_{nC}(r)=g(n)f_{C}(r)$ for all $n\in \mathbb{Z}$, for some $g:\mathbb{Z}\rightarrow \mathbb{Z}$. Claim 4: $g$ is a rational polynomial.
Consider $P\equiv xC$ and $Q\equiv nC$. We have, for all sufficiently large $n$, $$|P(n)|=|Q(n)|\implies |f_{xC}(n)|=|f_{nC}(n)|=|g(n)f_C(n)|.$$Note $f_{xC}$ and $f_C$ are fixed. Hence by Fact 3 we get that $g(n)$ is a rational polynomial.
Thus $f_{nC}(r)=g(n)f_C(r)$ for $n\in \mathbb{Z}$, where $C$ is an integer constant and $g$ is a rational polynomial. Claim 5: $g(n)\equiv a\cdot n^b$ for some rational $a$ and integer $b$.
Note that $$a\mid b \iff aC\mid bC\iff g(a)f_C(r)\mid g(b)f_C(r)\iff g(a)\mid g(b).$$Consider some fixed integer $k$ and sufficiently large $n$. $$\frac{g(kn)}{g(n)}=\frac{a_0+a_1(kn)+\cdots+a_m(kn)^m}{a_0+a_1(n)+\cdots +a_m(n)^m}=k^m+\mathcal{O}\left(\frac{1}{n}\right).$$Since it is an integer, we must have $\frac{g(kn)}{g(n)}=k^m$ for all sufficiently large $n$, hence $g(kn)=k^mg(n)$ for all $n$. Taking $n=1, g(k)=k^mg(1)$ as desired.
Now $f_{nC}(r)=a\cdot n^bf_C(r)=n^b\cdot T(r)$ where $T$ is the rational polynomial. Claim 6: $f_{x+z}(r)\equiv \pm (r+z)^b\cdot \frac{T(r)}{C^b}$ for any integer $z$ (note $C^b$ is a constant).
Take $P\equiv x+z$, $Q\equiv nC$, $r=nC-z$. Note that $$P(r)=Q(r)\implies |f_{x+z}(nC-z)|=|f_{nC}(nC-z)|=|n^b\cdot T(nC-z)|.$$Both sides are polynomials in $n$, hence we can uniquely determine it (up to a sign flip) using lagrange interpolation. One can easily verify that $f_{x+z}(r)=\pm (r+z)^b\cdot \frac{T(r)}{C^b}$ works.
Claim 7: $f_d(r)\equiv \pm d^b \cdot \frac{T(r)}{C^b}$ for constant $d$.
Pick $P\equiv x+z$ and $Q\equiv d$ with $r=d-z$. Note that $$P(r)=Q(r)\implies |f_{x+z}(r)|=|f_d(r)|\implies |d^b\cdot \frac{T(d-z)}{C^b}|=|f_d(d-z)|.$$Similarly, the polynomial is unique by lagrange (up to a sign flip)and we can verify that $f_d(r)=\pm d^b\cdot \frac{T(r)}{C^b}$.
Claim 8: $f_P(r)\equiv \pm P(r)^b\cdot\frac{T(r)}{C^b}$ for any polynomial $P$.
From Claim 1, if we let $r$ be fixed and $Q\equiv P(r)$ be a constant polynomial, $$|P(r)|=|Q(r)|\implies |f_P(r)|=|f_Q(r)|=|P(r)^b\cdot\frac{T(r)}{C^b}.$$Now treat both sides as polynomials in $r$, by lagrange interpolation we get the desired result.
In conclusion, the only functions are $f_P=\pm P^k\cdot A$ where $k$ is a constant positive integer and $A$ is a fixed integer polynomial.
math_comb01
10.02.2024 12:37
Amazing Problem!, mixes Algebraic, number theoretic and combinatorial ideas. Sketch: Clearly, $|P(r)| = |Q(r)|$ $\iff$ $|f(P)(r)| = |f(Q)(r)|$, now $f$ must be injective at $0$, assume $f(Q) \equiv 0$ then anything $\mid Q$ so $Q \equiv 0$. Next by putting $P \equiv c, Q \equiv x$ for $r = cn$ gives degree $f(c)$ is bounded, then choose the sequence of factorials, since every term divides other, after a point degree gets constant, say $deg(f_{k!}) = deg(f_{(k+1)!}) = \cdots$, then we also have $deg(f_{n \cdot k!}) = deg(f_{k!})$, so let $k! = C$, and we can find integer $g(n)$ s.t. $f_{n \cdot k!}(r) = g(n) f_{k!}(r)$, it is easy to see that $g$ must be rational, $a \mid b \iff aC \mid bC \iff g(a) \mid g(b)$ so now $g = a \cdot n^b$ for rational $a$ and integer $b$, so we have $f_{nC} = a \cdot n^b f_{C}(r) = n^b \cdot T(r)$, now the idea is to get same values same from linear polynomials and constants to get different forms of $f$. choose $P \equiv x+z, Q \equiv nC, r = nC - z$ so $f_{x+z}(r) = \pm (r+z)^b \frac{T(r)}{C^b}$, then choose $P \equiv x+z, Q \equiv d, r = d-z$ for some constant $d$ to get $f_d(r) = \pm d^b \cdot \frac{T(r)}{C^b}$, now we get $f_P(r) = \pm P(r)^b \frac{T(r)}{C^b}$, and therfore the only solutions are $f_P = \pm P^k \cdot A$, where $k$ is fixed constant, $A$ is a fixed integer polynomial.
IAmTheHazard
11.02.2024 22:09
The answer is $f(P)=\pm AP^d$ where $d>0$ is a fixed integer and $A$ is a fixed integer polynomial with no integer roots (note that $f(P)(x)=xP(x)$ fails because we get $P(0) \mid Q(0)$ for all $P,Q$—absurd); the choice of sign is not fixed. We will need the following lemma. Lemma: Let $P,Q \in \mathbb{Z}[x]$ such that $P(n) \mid Q(n)$ for infinitely many $n \in \mathbb{Z}$. Then $\frac{P(x)}{Q(x)} \in \mathbb{Q}[x]$. Proof: Suppose otherwise. Then by the division algorithm we can write $$\frac{P(x)}{Q(x)}=A(x)+\frac{B(x)}{Q(x)}$$for some $A(x),B(x) \in \mathbb{Q}[x]$ with $B \not \equiv 0$ and $\deg B<\deg Q$. Then by picking some $M$ with $MA(x) \in \mathbb{Z}[x]$ we get $\frac{MB(n)}{Q(n)} \in \mathbb{Z}$ for infinitely many $n$, but this is impossible for size reasons when $|n|$ is large. $\blacksquare$ We also have the following key fact. Fact: $|P(n)|=|Q(n)| \iff |f(P)(n)|=|f(Q)(n)|$. Proof: Swap $P$ and $Q$. As a corollary of the above fact, if $f(P) \equiv f(Q)$ then $|P| \equiv |Q|$, i.e. $f$ is "pseudo-injective". Returning to the actual problem, we first find $f(0)$. Suppose that it is nonzero. Then $P(n) \mid 0 \implies f(P)(n) \mid f(0)(n)$ for all $n$, so $\deg f(P) \leq \deg f(0)$ for all $P$. Pick $k=\deg P+1$ integers $x_0,\ldots,x_k$ such that $f(0)(x_i) \neq 0$. Then each $f(P)(x_i)$ can only attain finitely many values, hence by Lagrange interpolation $f(P)$ can only equal finitely many integer polynomials, but this contradicts pseudo-injectivity since $|\mathbb{Z}[x]|=\infty$. Thus $f(0) \equiv 0$. Note that obviously $f(P) \not \equiv 0$ for nonzero $P$. Not that this implies that the integer roots of $f(P)$ are the same as those of $P$, since if $P(r)=0 \implies 0 \mid P(r) \implies 0 \mid f(P)(r)$ and the reverse follows similarly. For any polynomial $P$, we have $f(1) \mid f(P)$; note that $f(1)$ has no integer roots, so in fact we may "factor it out" (specifically, factor out its primitive part, i.e. the polynomial obtained by dividing out the GCD of the coefficients of $f(1)$) and suppose that $f(1)$ is constant. Furthermore, for all $k$ and $c$ we have $f(k)(n) \mid f(x-c)(n)$ whenever $n \equiv c \pmod{k}$, hence $f(k) \mid f(x-c)$ in the polynomial sense. Suppose that some $k$ has $\deg f(k)>0$, and let $A \in \mathbb{Z}[x]$ denote its primitive part. Then $\frac{f(x-c)}{A}$ should be an integer polynomial by Gauss' lemma. But then we have $$(c+1)-c=1 \implies |f(1)(c+1)|=|f(x-c)(c+1)| \implies A(c+1) \mid f(1),$$but since $\deg A>0$ this is absurd as $f(1) \not \equiv 0$, hence $f(k)$ is identically constant. Now note that $i \mid j \implies f(i) \mid f(j)$ (in the integer sense); note that $f(0)=0$ but $f(i) \neq 0$ for $i \neq 0$. But on the other hand we have $|f(i)(i)|=|f(x)(i)|$, so $i \mid j \implies f(x)(i)\mid f(x)(j)$. In particular, $\frac{f(x)(2n)}{f(x)(n)}$ is an integer for all $n \neq 0$. But it's also a rational polynomial in $n$ with "degree $0$", so it must be identically constant. Then if $r \in \mathbb{C}$ is a root of $f(x)$, so is $2r$; iterating this implies that $f(x)$ has infinitely many roots (impossible) unless its roots are all $0$, i.e. $f(x)$ is of the form $cx^d$. Hence $f(n) \equiv \pm cn^d$ for some fixed $c,d$; by pseudo-injectivity it follows that $d \geq 1$, and from $n=1$ it follows that $c \in \mathbb{Z}$. Finally, for any $P \in \mathbb{Z}[x]$ and $n \in \mathbb{Z}$, we should have $$|f(P)(n)|=|f(P(n))(n)| \implies f(P)(n)=\pm cP(n)^d,$$so $f(P) \equiv \pm cP(n)^d$. Multiplying the primitive part of $f(1)$ back in, we obtain the advertised solution set. $\blacksquare$