Note that $P(0)$ could be any negative real number, since for any $a\in (-\infty,0)$, we can choose big enough $A>0$, such that $|y^2-(-A\cdot x^{2}+a)|\leq 2|x|$ doesn't have any solutions. Suppose that it's possible $P(0)=0$. Denote $\ell=\lim_{x\to 0}\frac{P(x)}{x}. $ Look at $|y^2/x - P(x)/x|$. If $|\ell |\leq 2$, we can tend both $x,y\to 0$, so that $y^2/x \to 0$, but $x^2/y\to \infty$, thus obtaining a contradiction. If $|\ell |> 2$, we can tend $x,y\to 0$, so that $y^2/x \to \ell$, but $x^2/y\to 0$, again a contradiction. Suppose now $P(0)>0$. Consider the leading coefficient of $P$. If it's negative, then setting $y=0$ and $x$ something near $x_0$ we obtain that $x^2=P(0)$ for all $x$ in some neighbourhood of $x_0$, a contradiction. Thus, if $P(0)>0$, then the leading coefficient of $P$ is positive. Consider again the inequality: \[|y^2/x - P(x)/x| \leq 2 \]Suppose $\deg (P) >2$ and tend $x\to\infty$ and set $y:=\sqrt{P(x)}$. Then the above inequality would be satisfied, but $|x^2/y - P(y)/y| \leq 2$ would not hold, a contradiction. So, $\deg(P)=2$. Moreover, exactly the same argument yields the leading coefficient of $P$ is $1$. Thus, $P(x)=x^2+bx+c$. Now, some routine calculations give us the only possibility is $P(x)=x^2+1$, which indeed satisfies the requirements. Finally $\boxed{P(0) \in (-\infty,0)\cup \{1\} }$.

Sorry for going off topic, but I've never seen this forum so active before! There's 10 topics that have been posted in this hour.

The answer is $(-\infty, -0) \cup \{1\}$. For constructions: Given any $c < 0$, take $P(x) = -x^2 + c$. Take $P(x) = x^2+1$. Now we prove they are the only ones. Assume that $P$ is nonconstant and $P(0) \ge 0$. In fact, we will prove that only $P(x) = x^2+1$ works. For this I will prove just that $\deg P \le 2$ in this case, since the rest of the problem can then be done by hand. The proof is divided into two major cases, based on the sign of the leading coefficient of $P$. First case: The leading coefficient of $P$ is negative. We contend $\deg P \le 1$ in this situation. Let $M > 0$ be huge, with $P(M) < -2M$ and $M^2 > P(0)$. Then $|x^2 - P(M)| > 2M$ for all $x$, hence \[ \left\lvert M^2 - P(y) \right\rvert > 2|y| \qquad \forall y. \]But note that $M^2 - P(0) > 0$ while $M^2 - P(Y) < 2Y$ for $Y > 0$ sufficiently large (in $M$). So this contradicts intermediate value theorem. Second case: The leading coefficient of $P$ is positive. We contend $\deg P \le 2$ in this situation. Indeed, the problem condition implies that \[ \left\lvert X^2 - P(\sqrt{P(X)}) \right\rvert \le 2\sqrt{P(X)} \]holds for all $X$ large enough (namely those $X$ for which $P(X) > 0$). If $n = \deg P \ge 3$ then the left-hand side is degree $n^2/2$ while the right-hand side is degree $n/2$, contradiction.

<dgrozev> wrote: Note that $P(0)$ could be any negative real number, since for any $a\in (-\infty,0)$, we can choose big enough $A>0$, such that $|y^2-(-A\cdot x^{2}+a)|\leq 2|x|$ doesn't have any solutions. Suppose that it's possible $P(0)=0$. Denote $\ell=\lim_{x\to 0}\frac{f(x)}{x}. $ Look at $|y^2/x - P(x)/x|$. If $|\ell |\leq 2$, we can tend both $x,y\to 0$, so that $y^2/x \to 0$, but $x^2/y\to \infty$, thus obtaining a contradiction. If $|\ell |> 2$, we can tend $x,y\to 0$, so that $y^2/x \to \ell$, but $x^2/y\to 0$, again a contradiction. Suppose now $P(0)>0$. Consider the leading coefficient of $f$. If it's negative, then setting $y=0$ and $x$ something near $x_0$ we obtain that $x^2=P(0)$ for all $x$ in some neighbourhood of $x_0$, a contradiction. Thus, if $P(0)>0$, then the leading coefficient of $P$ is positive. Consider again the inequality: \[|y^2/x - P(x)/x| \leq 2 \]Suppose $\deg (P) >2$ and tend $x\to\infty$ and set $y:=\sqrt{P(x)}$. Then the above inequality would be satisfied, but $|x^2/y - P(y)/y| \leq 2$ would not hold, a contradiction. So, $\deg(P)=2$. Moreover, exactly the same argument yields the leading coefficient of $P$ is $1$. Thus, $P(x)=x^2+bx+c$. Now, some routine calculations give us the only possibility is $P(x)=x^2+1$, which indeed satisfies the requirements. Finally $\boxed{P(0) \in (-\infty,0)\cup \{1\} }$. Can you be more specific for the case $\left| \ell \right| =2$?

Is there any motivation as to the solution or do you just keep trying to find polynomials that fit.

dgrozev wrote: Suppose now $P(0)>0$. Consider the leading coefficient of $P$. If it's negative, then setting $y=0$ and $x$ something near $x_0$ we obtain that $x^2=P(0)$ for all $x$ in some neighbourhood of $x_0$, a contradiction. Could anyone explain this to me?

Solved with brian6liu and Eugene V. Debs. We claim that $P(0)\in (-\infty,0)\cup \{1\}$. Note that, to achieve $P(0)=c<0$, we can set $P(x)=-Mx^2+c$ for some very large $M$. For the condition to be applicable, we would need $P(x)+2|x|\ge 0$. However, for $M>\frac{1}{c}$, we get $P(x)+2|x|=-M\left(|x|-\frac{1}{M}\right)^2+\left(c-\frac{1}{M}\right)<0$ for all $x$. Hence, no $(x,y)$ satisfy the requirement of the condition, and it vacuosly holds. So, we can assume that $P(0)\ge 0$. Note that, plugging in $y=0$ into the condition, we get that $|P(x)|\le 2|x|\iff x=\pm\sqrt{P(0)}\,\,(*)$. This immediately implies that $|P(x)|\ge 2|x|\forall x$, since if $|P(x)|<2|x|$ we can generate infinite $x$ which satisfy this inequality by continuity. Suppose that $P(x)\le 0\forall x$. This would imply that $P(0)=0$ and $P'(0)=0$, and $\deg P\ge 2$. So, by continuity of $P'$, we get $\varepsilon>0$ such that for all $0<x<\varepsilon$ we have $|P'(x)|<2$. This means that, for all $x$ in this range, $|P(x)|<2|x|$ by MVT, which is a contradiction. Hence, $P(x)$ can't be uniformly negative. This means that if we have $x'$ such that $P(x')\le 0,x'\neq 0$, there must exist $z\neq 0$ such that $P(z)=0$ by continuity. This is once again contradiction to $(*)$, and hence $P(x)>0\forall x\neq 0$. Furthermore, by a similar argument to when we assumed $P(x)\le 0\forall x$, we get $P(0)\neq 0$, so $P(x)>0\forall x$. This means that we can plug into our expression the pair $\left(x,\sqrt{P(x)}\right)$, which gives $\left|x^2-P(\sqrt{P(x)})\right|\le 2\sqrt{P(x)}$. If we consider degrees, if $d=\deg P >2$, then the LHS has degree $d^2/2$ and the RHS has degree $d/2$, which is a contradiction for large $x$. Hence, we must have $\deg P=2$. This would make the RHS have degree 1, so the quadratic term on the LHS must cancel. If $P(x)$ has leading coefficient $c$, then $LHS$ grows like $x^2-c^2x^2\implies c=1$. So, we can express $P(x)$ as $P(x)=x^2+ax+b$. We now consider what happens when we plug in $\left(x,\sqrt{P(x)+2x}\right)$ for $x>0$. We obtain $\left|x^2-P\left(\sqrt{P(x)+2x}\right)\right|\le 2\sqrt{P(x)+2x}$. The RHS grows like $2x$, whereas the expanding the LHS gives the argument of the absolute value to grow like $-(a+2)x-ax$. So, we need $2|a+1|\le 2$, implying that $-2\le a\le 0$. However, if we perform the exact same steps for $\left(x,\sqrt{P(x)-2x}\right)$ we will get $2|a-1|\le 2\implies 0\le a\le 2$ instead. So, $a=0$. Hence, we are left with $P(x)=x^2+b$. Now, recall from $(*)$ that $x=\pm\sqrt{P(0)}\iff |P(x)|= 2|x|$. So, $b^2+b=2b\implies b=1$. It is easy to check that $P(x)=x^2+1$ does indeed work, so our final solution set is $P(0)=\mathbb{R}_{<0}\cup \{1\}$, as desired.

Plops wrote: Is there any motivation as to the solution or do you just keep trying to find polynomials that fit. The idea is to eliminate one variable by making one of the inequalities trivially true. In this case, if you can set $y = \sqrt{P(x)}$ (which is only possible if $P(x) \geq 0$, which is why most solutions need to find a reason why this can be done), you find that $|x^2 - P(\sqrt{P(x)})| \leq 2|x|$ for all $x$ for which $P(x) \geq 0$, and at this point you feel that this is very restrictive, as $P(\sqrt{P(x)})$ grows as $x^{deg(P)^2/2}$, which is why you suspect that $\deg(P) = 2$. The rest is a matter of writing out details. As the designer of this problem, I can also tell you what its motivation was. I noticed that the Hasse-Weil inequality for the number $N_q$ of rational points on an elliptic curve over a finite field $\mathbb{F}_q$ is symmetrical: $|N_q - (q+1)| \leq 2\sqrt{q}$ is equivalent to $|q - (N_q + 1)| \leq \sqrt{N_q}$, which can be rewritten as $|y^2 - (x^2 + 1)|\leq 2x \Longleftrightarrow |x^2 - (y^2 + 1)|\leq 2y$ for $x = \sqrt{q}$ and $y = \sqrt{N_q}$, which naturally led to the condition in the problem statement. This is a fun observation when you'd like to find curves with small Picard groups/class number of the function field, as it restricts $q$ as you bound $N_q$. Amajor123 wrote: dgrozev wrote: Suppose now $P(0)>0$. Consider the leading coefficient of $P$. If it's negative, then setting $y=0$ and $x$ something near $x_0$ we obtain that $x^2=P(0)$ for all $x$ in some neighbourhood of $x_0$, a contradiction. Could anyone explain this to me? I think they forgot a sentence defining $x_0$, and I can only guess is that they wanted to do something like this: If the leading coefficient is negative, $P(x)$ will be negative for large $x$, so by the intermediate value theorem and $P(0) > 0$, there would exist an $x_0 > 0$ such that $P(x_0) = 0$. The continuous function $x \mapsto 2|x| - P(x)$ is positive at $x_0$, so it is positive in a neighbourhood $I = (x_0-\varepsilon,x_0+\varepsilon)$ of $x_0$, i.e., for all $x\in I$ we have $|0 - P(x)| \leq 2|x|$, which is equivalent to $|x^2 - P(0)| \leq 0$, i.e. $x = \sqrt{P(0)}$ because of the condition in the problem statement, which would imply that $I = \{\sqrt{P(0)}\}$, a contradiction.

Who was the author of this interesting problem

v_Enhance wrote: First case: The leading coefficient of $P$ is negative. We contend $\deg P \le 1$ in this situation. Let $M > 0$ be huge, with $P(M) < -2M$ and $M^2 > P(0)$. Then $|x^2 - P(M)| > 2M$ for all $x$, hence \[ \left\lvert M^2 - P(y) \right\rvert > 2|y| \qquad \forall y. \]But note that $M^2 - P(0) > 0$ while $M^2 - P(Y) < 2Y$ for $Y > 0$ sufficiently large (in $M$). So this contradicts intermediate value theorem. Just checking on this, in particular the part on $M^2 - P(Y) < 2Y$ for suff large $Y>0$; if $P(Y)$ gets very negative as $Y$ gets larger, shouldn't it be $M^2-P(Y) > 2Y$ for large $Y$? For instance, I think the polynomial $P(x) = -x^3 - 2x$ might not produce a contradiction for the proof here...

The answer is all $P(x)<0$ and $P(x)=1$. Let $P(0)=c$, if $c<0$ then picking $P(x)=-\frac{1}{c-\epsilon}x^2+c$, by AM-GM and triangle inequailty we have $$|y^2-P(x)|\geq |P(x)|> 2|x|$$so the equivalence is obviously true. If $P(x)=1$ we can pick $P(x)=x^2+1$, then it works. Now we show that Claim. If $P(x)>0$ for some $x$ then $P$ is even. Proof. Since $P$ is continuous, $P(x)\geq 0$ for all $x\in(a,b)$, where $(a,b)$ is a neighborhood of $x$. We show that $P(x)=P(-x)$ for all $x\in (a,b)$. Indeed, if $P(x)>P(-x)$ then pick $y$ such that $y^2-P(x)=2|x|$, then we have $$|(-x)^2-P(y)|\leq 2|y|\implies |y^2-P(-x)|\leq 2|x|$$but $y^2>P(x)>P(-x)$, hence $$|y^2-P(-x)|=y^2-P(-x)>y^2-P(x)=2|x|$$contradiction similarly $P(-x)>P(x)$ is impossible, so $P(x)=P(-x)$ for all $x\in (a,b)$ which implies $P$ is even. $\square$ Claim. $|P(x)|\geq |x|$ for all $x$. Proof. If $|P(x)|<|x|$ for some $x$ then again by continuity $|P(x)|\leq |x|$ for some $x\in[a,b]$. Then put $y=0$ in the equivalence we have $$|x^2-P(0)|=0$$obviously a contradiction. $\square$ Now if $c=0$, we divide into two case. If $P$ consists of only degree $2$ or greater terms then $|P(x)|<|x|$ for some $x$ since $\lim_{x\to 0}\frac{P(x)}{x}= 0$. If $P$ consists of a linear term then $P(x)>0$ for some $x$, hence it is even, contradiction. If $c>0$, we divide into two cases: Case I: $P$ has negative leading coefficient Since $P(0)>0$ and $\lim_{x\to\infty}P(x)=-\infty$, there exists a real root by intermediate value theorem, say $\alpha$, then obviously $|P(\alpha)|<\alpha$, contradiction. Case II: $P$ has positive leading coefficient. We have $\sqrt{P(x)}$ exists for sufficiently large $x$, hence pick $y=\sqrt{P(x)}$ we have $$|x^2-P(\sqrt{P(x)})|\leq 2|\sqrt{P(x)}|$$Notice that $P$ is even, and in order for this to hold for large $x$ we must have $\deg P=2$ and that $P$ is monic, hence $P(x)=x^2+c$ for some $c>0$. If $c<1$ then $P(1)<2|1|$. If $c>0$, pick $x=0,y=\sqrt{c}$, then we have $$|c|<|\sqrt{c}|$$so we are done.

The answer is all negative numbers as well as $1$. Taking $P(x) = \frac{-x^2}{\epsilon} - \frac{\epsilon^2 + d}{\epsilon}$ ensures that $P(x) > 2|x|$ always and so neither of the two conditions ever hold, and this covers all negative numbers, and taking $P(x) = x^2 + 1$ works for $P(0) = 1$, which I'll show works at the end. Assume $P(0)$ is nonnegative for now.

So we have that for sufficiently positive/negative $x$, $P(x)$ becomes arbitrarily large. Take $y = \sqrt{P(x)}$ to get that $|x^2 - P(\sqrt{P(x)})| \le 2|\sqrt{P(x)}|$ if $P(x)$ is positive. Say $d$ is the degree of $P$, then if $d \neq 2$, then the degree of the LHS is $\max(2, \frac{d^2}{2})$ and the degree of the RHS is $\frac{d}{2}$, which cannot happen since the left is strictly bigger. So we have that $P$ is a quadratic polynomial and further, we need its leading coefficient to be $1$. Let $P(x) = x^2 + ax + b^2$, since we need $P(x) \ge 2|x|$ with equality iff $x^2 = P(0)$, we must have $P(b) = P(-b) = 2b$ so this gives $a = 0$ and $b = \pm 1$, either way we have $P(x) = x^2 + 1$ only which can work. So it remains to check that this works. We want to show $|y^2 - x^2 - 1| \le 2|x| \iff |x^2 - y^2 - 1| \le 2|y|$. Suppose $y^2 > x^2 + 1$, then the first condition is $y^2 \le (|x|+1)^2$ and the second condition is $(|y|-1)^2 \le x^2$, which its easy to see imply each other. Similarly, if $x^2 > y^2 + 1$, this holds so only we need to check when $x^2 \le y^2 + 1$ and $y^2 \le x^2 + 1$, but in this case the conditions rewrite as $y^2 \le (|x|+1)^2 \iff x^2 \le (|y|+1)^2$, which is just true because $x^2 \le y^2 + 1 \le y^2 + 2|y|+1 = (|y|+1)^2$, so this works and we're done. $\blacksquare$

Claim: $\deg P = 2$ with leading coefficient $\pm 1$. Proof. Let $P = a_d x^d + \dots + a_0$. Then for large $x$, we have that $y = (a_d + o(1))x^{\frac{d}{2}}$ so $P(y) \pm 2y = (a_d^2 + o(1))x^{\frac{d^2}{2}}$ and thus $x = (a_d + o(1))x^{\frac{d^2}{4}}$ which only holds if $d = 2$ and the leading coefficient is $\pm 1$. $\blacksquare$ As such, let $P(x) = x^2 + ax + b$. Claim: The only possible value with positive leading coefficient is $x^2 + 1$. Proof. It thus follows that if $y = \sqrt{x^2 + (a \pm 2)x + b}$, on the domain then that $x^2 - P(y) \in \{-2y, 2y\}$. Continously varying $x$ implies that only one of these can hold. In both cases, we get that $-(a \pm 2)x - 2b = (a \pm 2)y$ where the second $\pm$ may be flipped. In either case, it must follow that $a = 0, b = 1$, which can be seen to work. $\blacksquare$ As for the negative coefficient case, it follows that $a = 0$, and that $x^2 + y^2 + b \ge \max\{x, y\}$ must always hold, so $b$ must be negative which works. As such, $P(0) \in (-\infty, 0] \cup \{1\}$ works.

v_Enhance wrote: First case: The leading coefficient of $P$ is negative. We contend $\deg P \le 1$ in this situation. Let $M > 0$ be huge, with $P(M) < -2M$ and $M^2 > P(0)$. Then $|x^2 - P(M)| > 2M$ for all $x$, hence \[ \left\lvert M^2 - P(y) \right\rvert > 2|y| \qquad \forall y. \]But note that $M^2 - P(0) > 0$ while $M^2 - P(Y) < 2Y$ for $Y > 0$ sufficiently large (in $M$). So this contradicts intermediate value theorem. The inequality $M^2 - P(Y) < 2Y$ is not true, since the leading coefficient is negative, I think?

YaoAOPS wrote: Claim: $\deg P = 2$ with leading coefficient $\pm 1$. Proof. Let $P = a_d x^d + \dots + a_0$. Then for large $x$, we have that $y = (a_d + o(1))x^{\frac{d}{2}}$. I don't think this follows if the leading coefficient of $P$ is negative.

dgrozev wrote: Suppose now $P(0)>0$. Consider the leading coefficient of $P$. If it's negative, then setting $y=0$ and $x$ something near $x_0$ we obtain that $x^2=P(0)$ for all $x$ in some neighbourhood of $x_0$, a contradiction. Why? Since $|x^2 -P(0)| \leq 0 \Leftrightarrow x = \sqrt{P(0)}$, what is the problem with $|P(x)| \leq 2|x|$ have only $x = \pm\sqrt{P(0)}$ as solutions (e.g. by having them as double roots).