Find all injective $f:\mathbb{Z}\ge0 \to \mathbb{Z}\ge0 $ that for every natural number $n$ and real numbers $a_0,a_1,...,a_n$ (not everyone equal to $0$), polynomial $\sum_{i=0}^{n}{a_i x^i}$ have real root if and only if $\sum_{i=0}^{n}{a_i x^{f(i)}}$ have real root. Proposed by Hesam Rajabzadeh
Problem
Source: Iran TST 2023 ; Exam 2 Problem 5
Tags: algebra, polynomial, function
18.03.2023 14:03
18.03.2023 14:39
I claim that the answer is $f(x)=cx$ where $c$ is an odd positive integer. Hope its correct:D Firstly this function clearly works since if there is a real root $a$ then $\sqrt[c]{a}$ is clearly a root to the new polynomial, otherwise both polynomials don't have real roots. Now, I'll show that no other function exists. Claim 1: $f(0)=0$ Proof: Polynomials $x^2+1$ and $x^4+1$ does not have real roots so $x^{f(2)}+x^{f(0)}$ and $x^{f(4)}+x^{f(0)}$ does not have real root. $\Rightarrow$ $x=0$ is not a root so $f(2)*f(0)=0=f(4)*f(0)$ and since the function is injective $f(0)=0$ $\blacksquare$ Claim 2: $f(n) \equiv n (mod 2)$ Proof: The polynomial $x^n+1$ have real root if and only if $n$ is odd so the conclusion follows $\blacksquare$ Claim3: $f(1)=c$ $\Rightarrow$ $f(2k)=2kc$ where $k \in Z^+$ Proof: For every $\epsilon >0$, $x^{2k}-2kx+(2k-1)+\epsilon>0$ (If $x<0$ it is obvious, if not by AM-GM) so does not have a real root. $\Rightarrow$ $x^{f(2k)}-2kx^c+(2k-1)+\epsilon$ does not have a real root If $f(2k)<2kc$ and for small enough $\epsilon$ taking $x=1+\epsilon$ makes the expression is negative which is a contradiction. So $f(2k)\ge2kc$. $f(2k)>2kc$ $\Rightarrow$ If we take $x=1-\epsilon$ for small enough $\epsilon$ the expression is again negative and another contradiction $\blacksquare$ Now for the rest let k be an odd integer. i) Suppose $f(k)>kc$: $x^{2k}-2x^k+1+\epsilon$ does not have real root so is $x^{2kc}-2x^{f(k)}+1+\epsilon$ but again small enough $\epsilon$ there is a root for that expression. Contradiction. ii) Suppose $f(k)=a<kc$: $x^{2ac}-2cx^a+(2c-1)+\epsilon$ does not have real roots so is $x^2a-2cx^k+(2c-1)+\epsilon$. But agaion for small enough $\epsilon$ there is a root for that expression (You may look the case when $x=1-\epsilon$ if its not trivial for you) Contradiction. So $f(k)=ck$ for all k $\blacksquare$ I saw someone wrote a solution while I am writing but I'll post it anyway hope its correct
21.05.2023 07:25
Solved with mueller.25, starchan, Siddharth03, AdhityaMV The only solution is $f(x) = cx$ with $c$ being an odd positive integer. Clearly these work. First, taking $n = 1$, $a_1 = 0$ and $a_0 = 1$, we get that $f(0) = 0$. Next, note that $f(n)$ and $n$ always have the same parity, for example if $i$ is even and $f(i)$ is odd, taking $a_n = a_0 = 1$, $x^i + 1$ has no real roots, but $x^{f(i)} + 1$ has a real root because it has odd degree. Consider the polynomials $x^{2a} - cx^b + a_0$ and $x^{f(2a)} - cx^{f(b)} + a_0$ with $2a > b$. Clearly $f(2a) > f(b)$. Since each one has a real root if and only if the other does, we see that both polynomials have the same minimum value. But the minimum value of $x^{p} - cx^{q}$ occurs when $px^{p-1} = qcx^{q-1}$, or when $x = \sqrt[p-q]{\frac{qc}{p}}$. At this point, the value of the polynomial is $\left(\frac{qc}{p} \right)^{\frac{p}{p-q}} - c \left(\frac{qc}{p} \right)^{\frac{q}{p-q}}$. But for large values of $c$, this is asymptotically equal to $d \cdot c^{\frac{p}{p-q}}$ for some fixed constant $d$. Since the minimum values for those two polynomials are equal, we get that actually $\frac{2a}{2a-b} = \frac{f(2a)}{f(2a) - f(b)}$ or that $\frac{f(2a)}{2a} = \frac{f(b)}{b}$ for all pairs of positive integers $a,b$ with $2a > b$. This clearly finishes, as it forces $f$ to be linear, and since $f(n)$ and $n$ have the same parity, $f(x) = cx$ with $c$ odd, as desired. $\blacksquare$
17.09.2023 17:27
The answer is $f(n)=kn$ only, where $k$ is an odd positive integer. This clearly works, so now we prove it is the only one. Let $g : \mathbb{R}[x] \to \mathbb{R}[x]$ send $\sum_{i=0}^n a_ix^i$ to $\sum_{i=0}^n a_ix^{f(i)}$. When we say "consider $P(x)$", this means considering what happens when we plug $P$ into $g$. By considering $P(x)=1$, it follows that $f(0)=0$. By considering $P(x)=x+1$, it follows that $f(1)$ is odd. Let $f(1)=k$; I will prove by strong induction that $f(n)=kn$ for all $k$. This follows by the following two inductive steps. If we have $f(i)=ki$ for $i=0,\ldots,n$, then we also have $f(2n)=2kn$. By considering $P(x)=(x^n-2)^2+\varepsilon$ for some small $\varepsilon>0$, we find that $g(P(x))$ should always be positive, hence $g((x^n-2)^2)$ should always be nonnegative. By plugging in $x=2^{1/kn}$, it follows that $f(2n) \geq 2kn$. Likewise, by considering $P(x)=(x^n-1/2)^2+\varepsilon$ and plugging in $x=2^{-1/kn}$, it follows that $f(2n) \leq 2kn$, hence $f(2n)=2kn$. If we have $f(i)=ki$ for $i=0,1\ldots,2n-2,2n$, then we also have $f(2n-1)=2n-1$. This follows by the same logic as before, except now we consider $P(x)=(x-2)^{2n}+\varepsilon$ and $P(x)=(x-1/2)^{2n}+\varepsilon$. Hence the induction is finished. $\blacksquare$
06.05.2024 21:15
The only answer is $\boxed{f(n)=cn}$ for some odd integer $c$. It is not hard to see that these functions work. Claim: $f(0)=0$ Consider the polynomial $1$. Claim: $f(n)$ and $n$ have the same parity Consider the polynomial $x^n+1$. Claim: $f(n)$ is strictly increasing If $n=2k$ then consider the polynomial $x^{2k}+x^{2k-1}+B$ where $B$ is an arbitrarily large number. This polynomial does not have a root so the other polynomial cannot have a maximal degree of odd parity. This implies that $f(2k-1)<f(2k)$. A similar argument works if $n=2k+1$. Claim: $f(n)=cn$ for some odd positive integer $c$ Let $f(1)=c$. Assume both polynomials are of even degree. Notice that the minimum value of both polynomials must be the same otherwise we could chose $a_0$ to arrive at a contradiction. Now consider the polynomial $x^{2n}+2nx$ which has a minimum at $1-2n$. The polynomial $x^{f(2n)}+x^c$ must also have a minimum at $1-2n$. However as $f(2n)$ increases so will the minimum and we notice that $f(2n)=2nc$ yields the same minimum so we must have $f(2n)=2nc$. As $f(n)$ is strictly increasing the result follows.