Let $f(x)$ be a non-constant polynomial with integer coefficients such that $f(1) \neq 1$. For a positive integer $n$, define $\text{divs}(n)$ to be the set of positive divisors of $n$. A positive integer $m$ is $f$-cool if there exists a positive integer $n$ for which $$f[\text{divs}(m)]=\text{divs}(n).$$Prove that for any such $f$, there are finitely many $f$-cool integers. (The notation $f[S]$ for some set $S$ denotes the set $\{f(s):s \in S\}$.)
Problem
Source: CMO 2023 P4
Tags: algebra, polynomial, CMO, CMO 2023
11.03.2023 04:44
Take prime $p$ dividing $f(1)$ and $m >> N$ where $f$ is strictly increasing past $N$. $f$ of largest factors of $m$ must correspond to largest factors of $n$, and size argument (relying on the fact that $l^n$ cannot equal $p$ ever for n > 1) wins
11.03.2023 05:35
alternatively: there are finitely many $a$ where $f(a)=1$ (at most degree of $f$), so one must divide infinitely many $m$, so then $f(m/a)\mid f(m) \implies f(x)\mid f(ax)$ has infinitely many solutions (again for large enough $m$ where it's strictly increasing and $f(m)>f(n)$ for all $0<n<m$). do division algorithm, $f(ax)=qf(x)+g(x)$ where deg g < deg f, so $f(x)\mid g(x)$ infinitely many times. after some point $|f(x)| > |g(x)|$ so $g(x)=0$ for infinitely many $x$ and has to be the zero polynomial; $f(ax)=qf(x) \implies f(x)$ is a monomial $cx^d$, but this is clearly bad (no integer sols to $f(a)=1$)
11.03.2023 05:47
Note that eventually the function will be strictly increasing, therefore we must have $f(m) = n$ and $f(\frac{m}{p}) = \frac{n}{q}$, where $p$ and $q$ are the smallest prime divisors of $m$ and $n$ respectively. These two can be rewritten to $$f(\frac{m}{p}) = \frac{f(m)}{q}$$But note that $f(1) \neq 1$ be among the divisors of $n$ and hence divide $n$, so the value of $q$ is actually bounded. As a consequence, due to the above equation, $p$ is bounded too, therefore there exist infinitely many values of $m$ which have the same value of $p$, and for all of these we have that $f(k) \mid f(kp)$ for $k = \frac{m}{p}$. Since this is true for infinitely many big integers, it forces that $f(kp) = Q(k)f(k)$, implying $f$ can only be a monomial. But this is clearly impossible since nothing goes to one here except one itself.
11.03.2023 17:58
Some people might get a -1 by not considering $f(1)<0$ (in particular $f(1)=-1$)? We will prove that there are finitely many cool pairs of positive integers $(m,n)$ such that $f(\text{divs}(m))=\text{divs}(n)$. Throwing out the finitely many pairs with $m=1$ or $n=1$, The key is to consider the least prime divisor of $m$ and $n$. If $f(1)\leq 0$ we cannot have any $f$-cool pairs because $f(\text{divs}(m))$ will always have a nonpositive number but $\text{divs}(n)$ cannot. Thus $f(1)>1$, so since $f(1)$ must divide $n$ the least prime divisor of $n$ in any cool pair $(m,n)$ is bounded. Furthermore, since $1 \in \text{divs}(n)$, one of the divisors $d$ of $m$ must have $f(d)=1$. Since there are finitely many solutions in the positive integers to this, and $1$ is not one of them, the least prime divisor of any $m$ in a cool pair $(m,n)$ is also bounded (in particular, by the largest prime divisor over all these solutions). For $m$ large enough, the largest value in $f(\text{divs}(m))$ should be $f(m)$, and the second-largest should be $f(m/p)$, where $p$ is the least prime divisor of $m$. Thus for a good pair $(m,n)$ we should have $(m,n)$, we should have $f(m)=n$ and $f(m/p)=n/q$ where $q$ is the least prime divisor of $n$. Since we proved $p$ and $q$ were bounded, if there are infinitely many cool pairs $(m,n)$, by pigeonhole there should be some pair of primes $(p,q)$ that occurs infinitely often, i.e. there are infinitely many $m$ with $$f\left(\frac{m}{p}\right)=\frac{f(m)}{q}.$$Thus this must be a polynomial equality. But if there is an $x^k$ term in $f$ with nonzero coefficient, it gets multiplied by $p^{-k}$ on the LHS and $q^{-1}$ on the RHS, implying that $k$ must be unique, so $f(x)=cx^d$ is the only polynomial we must consider, where $c>1$. However, such polynomials will not have any integers solutions to $f(x)=1$ by taking modulo $c$, which is necessary for any pair $(m,n)$ to be cool, so we are done. $\blacksquare$
11.03.2023 20:06
Sad problem. Assume contradiction and notice that there are finitely many $a_i$ such that $f(a_i)=1$ and suppose $\mathbb{P}$ is the prime-set of these numbers $a_i$. Let $1 < d_a < d_{a-1} < \cdots < d_1 <m$ and $1 < e_a < e_{a-1} < \cdots < e_1 <n$ be the divisors of $m$ and $n$ respectively where $m$ is cool and $n$ is its cool conjugate. WLOG assume that the leading coefficient of $f$ is positive and we can find $N$ such that for all $m \geq N$, $f(m)=n$ and $f(d_i)=e_i$ where $1 \leq i \leq a$. This means, $$f(d_a) \mid f(m)=f(d_ad_1)$$Notice that $d_a$ is bounded as $d_a \in \mathbb{P}$, thus for some prime $d_a = p_i \in \mathbb{P}$, the divisibility is true infinitely many times. Now we can force $f(d_1x) = f(x)g(x)$ for some polynomial $g$ for all $x$ (say by the euclidean algorithm), thus $f(x) = cx^d$ but then $f$ is never mapped to $1$ which is a contradiction. $\blacksquare$
10.04.2023 01:54
The original (harder) version of this problem had the condition that $f(x)\neq x$ (as polynomials) instead of $f(1)\neq 1$, with the goal to prove that there are finitely many $f-$cool composite integers.
24.08.2023 16:47
Bacteria wrote: The original (harder) version of this problem had the condition that $f(x)\neq x$ (as polynomials) instead of $f(1)\neq 1$, with the goal to prove that there are finitely many $f-$cool composite integers. May I ask which problem you referred to above or in which competition?
22.12.2023 00:43
Suppose WLOG that the leading coefficient of $f$ is positive. Let $M$ be the largest local maximum of $f$, and let $N$ be the largest number such that $f(N) = M$. Assume that there exist infinitely many $f$-cool integers $m$; then there exists such a $m$ with $m > N$. Let $p_1$ be the smallest prime factor of $m$ and $q_1$ the smallest factor of $n$. It follows that $f(n) = m > M$ and $f\left(\frac n{p_1}\right) = \frac m{p_1}$. But setting $c$ to be the leading coefficient of $f$, by taking $n$ sufficiently large, we can force $$(p_1^d - 1) f\left(\frac n{p_1}\right) < f(n) < (p_1^d + 1) f\left(\frac n{p_1}\right).$$In particular, this implies that $q_1 = p_1^d$, which is absurd for $d \geq 2$. Thus $d=1$; but because there exists an integer $k$ with $f(k) = 1$, it follows the leading coefficient of $f$ is $\pm 1$. Having $f(1) < 0$, on the other hand, is clearly impossible, so this yields an immediate contradiction.
08.08.2024 22:30
Impossible to write the solution correctly FTSOC assume there there are infinitely many $f-$cool integers. Claim I: $f(m)=n$ Proof: It is easy to see that $f$ has positive coefficients. So $f(m)$ and $n$ are the largest value in the sets $f[d(m)]$ and $d(n)$ respectively , so $f(m)=n$. Also note that $1$ is the smallest $d(m)$, so let $f(k)=1$ for some $k$. Also $k\neq 1$ according to the problem. Claim II: $f(k)\mid f(ak)$, for $f(k)=1$ Proof: $\exists k$ such that $\displaystyle f\biggl(\frac{m}{k}\biggr) \in f[d(m)]=d(f(m))\implies f\biggl(\frac{m}{k}\biggr)\bigg|f(m)\implies f(k)\mid f(ak)$ which has infinite solutions. Let $\text{deg}(f)=d$ and $f(ak)=g\cdot f(k)+h(k) \implies f(k)\mid h(k)$, but $\text{deg}(h)<\text{deg}(f)$ hence we have a contradiction, so $h$ is $0$. We get $f(ak)=g \cdot f(k) \implies f(k)=ck^d$. But if $c=1$ then $f(1)=1$ which is a contradiction so there are finitely $f-$cool integers. $\blacksquare$
09.08.2024 02:52
Notice that since $f$ is eventually positive, there exists $N$ such that for every $u \ge N$ and $u > v$ we have $f(u) > f(v)$. Hence if $m$ is big enough we get that $f(m)$ is the biggest so $f(m) = n$. We also exclude prime $m$ because we can only have finitely many of these. Now let $p$ be the smallest prime dividing $m$ and $q$ be the smallest prime dividing $n$. Since $m$ isn't prime, we have that $\frac{m}{p} \ge p$ so it can be sufficiently large. So we get that $f\left(\frac{m}{p}\right)$ is the second biggest and so $f\left(\frac{m}{p}\right)=\frac{n}{q}$. So we finally get: $$f\left(\frac{m}{p}\right)=\frac{f(m)}{q}$$ Also notice that $f(1)$ must be greater than $1$ hence we have that $f(1)\ge q$ since $f(1)\in \text{divs}(n)$. So we get that $$f\left(\frac{m}{p}\right)\ge \frac{f(m)}{f(1)}$$ Therefore $p \le f(1)$ (for sufficiently large $m$). And so $p$ is bounded meaning that there are infinitely many $f$-cool integers with least prime factor $p$. Hence we must have $f(x)=P(x)f\left(\frac{x}{p}\right)$. Hence $\text{deg}P = 0$ and looking at some non-zero coefficient of $x^{k}$ we get $P(x) = 1$ which is clearly a contradiction.