very very nice problem. I don't have an elementary proof as of now so I would really like to see you solution. I excluded P from having degree $ \geq 3$ so i'm assuming the only solutions are $ P(x)=k^2x$

can we say that if a polynomial P(x) takes square values for all integers , then P(x) = {f(x)}^2 where f(x) = polynomial with integer coefficients

gagan_goku wrote: can we say that if a polynomial P(x) takes square values for all integers , then P(x) = {f(x)}^2 where f(x) = polynomial with integer coefficients Yes, that's a well-known theorem. See for instance H. Davenport, D.J. Lewis, A. Schinzel: Polynomials of certain special types. Acta Arithmetica 9, 1964, 107-116.

if thats true , then you can say that f(x,y) = P(x) + P(y^2 -x) = g(x,y) ^ 2 maybe this yields something

I've been spending a lot of time mulling this one over in my head. Can anyone solve it?

If $ P$ is not an odd polynomial there exists an $ a$ so that $ P(x)+P(a)$ is not divisible by $ x+a$ $ P(x^2-a)+P(a)=Q(x)^2$ so $ P(x)+P(a)=Q(\sqrt{x+a})^2$ and $ P(x)+P(a)=R(x)^2$ also $ P(x)+P(b)=K(x)^2$ but $ R(x)^2-K(x)^2=c$ can not hold as an identity so $ c=0$ and the polynomial is a constant function $ P(x)=2m^2$ if P is an odd polynomial $ P(x)+P(a)=(x+a)R(x)^2$ and $ P(x)+P(b)=(x+b)K(x)^2$. how can we show that these last two equations imply some contradiction if the degree of $ P$ is too large?...

Albanian Eagle wrote: If $ P$ is not an odd polynomial there exists an $ a$ so that $ P(x) + P(a)$ is not divisible by $ x + a$ Do you have a proof of this?

Albanian Eagle wrote: i'm assuming the only solutions are $ P(x) = k^2x$ Of course there's also $ P(x) = 2k^2$.

Albanian Eagle wrote: and $ P(x) + P(a) = R(x)^2$ why?...can you say more details please?

I will assume the answers to the preceeding questions have already been given, so let me try to answer Albanian Eagle's question. Suppose that $ (X+a)R(x)^2-(X+b)P(X)^2=c$, a nonzero constant (otherwise the conclusion is obvious...). Then obviously $ P$ and $ R$ are relatively prime and have the same degree. Differentiate the relation to obtain $ (X+a)2RR'+R^2-P^2-(X+b)2PP'=0$, thus $ R$ divides $ P+2(X-b)P'$ and thus must be a constant times this thing, by the remark on the degree. This gives you a differential equation on $ P$ and allows finding all solutions, but unfortunately it may very well happen that there are solutions of arbitrarily large degree (and it happens, actually...), but this imposes however very strong conditions on $ P$. Now, by choosing some other value $ d,e,..$ for $ a,b$, I think we can conclude. I'm still puzzled by this apparently extremely easy problem, which however does not seem to have a decent solution.

Oh nice.. so Harazi can substitute "a constant times" with "equal" by considering leading coefficients. and so we have $ R=K+2(x+b)K'$ but also vice versa so $ (x+b)K'+(x+a)R'=0$ and particularly $ K'=R'=...$ by putting different choices So $ P(x)+P(m)=(x+m)(Q(x)+c_m)^2$ holds for some fixed $ Q$ this is possible only when $ Q$ is constant so $ P$ is linear and we can easily conclude we don't even need the differential equations.

But I love differential equations! Just kidding, I really hate them, thanks for pointing out this simplification, I had no paper with me to check if indeed it can be made easier. Anyway, great problem.

fearailhold wrote: Albanian Eagle wrote: If $ P$ is not an odd polynomial there exists an $ a$ so that $ P(x) + P(a)$ is not divisible by $ x + a$ Do you have a proof of this? if for all $ a$, $ P(x)+P(a)$ is diviseble by $ x+a$ then $ G(x)=P(x)+P(-x)$ is zero for all $ a$....and P is odd...

If the words Iran and Polynomial appear in the same thread it can never disappoint you

1 doubt how does $ P(x) + P(a) = P(\sqrt{x+a})^2$ imply $ P(x) + P(a) = R(x)^2$ secondly , if you have $ P(x) + P(a) = R(x,a)^2$ , then i think we can conclude that the degree of $ P$ is 0 but then we dont get the solution $ P(x) = k^2x$ does this solution come from $ P$ being odd

gagan_goku wrote: can we say that if a polynomial P(x) takes square values for all integers , then P(x) = {f(x)}^2 where f(x) = polynomial with integer coefficients This claim should be slightly modified, cause $ f(x)$ do not need to be with integer coefficients. For example $ P(x)=\frac{x^2(x-1)^2}{4}$. Then I think I have a elementary proof to this fact. The most important case is that the degree of $ P$ is even. In this case we let $ \deg P=2n$ and tha cofficent of the $ 2n-th$ power is $ A$. Consider $ L=\lim_{x \rightarrow \infty}{(\sqrt{P(x+n-1)} -C_{n-1}^1 \sqrt{P(x+n-2)}+\ldots+(-1)^{n-1} \sqrt{P(x)})}$ Here is the most important result: We claim that $ L$ is a constant. In fact, we can find a polynomial $ Q(x)$ such that $ \deg Q=n$ and $ \deg(P-AQ^2) \leq n-1$ (This is true due to Newton's formula for symmitric sums.) Then we have ${ \lim_{x \rightarrow \infty}{\sqrt{P(x)}-\sqrt{A}Q(x)}=\lim_{x \rightarrow \infty}{\frac{P(x)-AQ^2(x)}{\sqrt{P(x)}+\sqrt{A}Q(x)}}}=0$ So $ L=\sqrt{A} \lim_{x \rightarrow \infty}{(Q(x+n-1) -C_{n-1}^1 Q(x+n-2)+\ldots+(-1)^{n-1} Q(x))}= \sqrt{A} (n-1)!$ is a constant. Finally, suppose $ P(x)=a_x^2$ for all $ x \in Z$. Then $ \lim_{x \rightarrow \infty}{(a_{x+n-1}-C_{n-1}^1 a_{x+n-2}+ \ldots +(-1)^{n-1} a_{x})}=L$. Therefore $ L$ is a integer, and for large enough $ x \in Z$, we have ${ a_{x+n-1}-C_{n-1}^1 a_{x+n-2}+ \ldots +(-1)^{n-1} a_{n}}=L$. Note that the sequence $ {a_n}$ has the fomula $ a_n=f(n)$ where $ \deg{f}=n$ for large enough $ n$. So we conclude $ P(x)=f^2(x)$ for large enough $ x \in Z$ and therefore $ P(x)=f^2(x)$ for all $ x$. And it's obvious that $ f(x) \in Q[x]$. In the case that the degree of $ P$ is odd, let $ P'(x)=P(x^2)$ we do the same thing, and it's easy to claim that such $ P(x)$ don't exist.

rchlch wrote: gagan_goku wrote: can we say that if a polynomial P(x) takes square values for all integers , then P(x) = {f(x)}^2 where f(x) = polynomial with integer coefficients This claim should be slightly modified, cause $ f(x)$ do not need to be with integer coefficients. For example $ P(x) = \frac {x^2(x - 1)^2}{4}$. Aaah, yes indeed. The correct statement is: If a MONIC polynomial $ P(x)$ takes square values for all integers $ x$, then $ P(x) = {f(x)}^2$ where $ f(x)$ is a polynomial with integer coefficients.

There are stronger lemmas out there like http://www.mathlinks.ro/Forum/viewtopic.php?search_id=1576618391&t=148696

Albanian Eagle wrote: There are stronger lemmas out there like http://www.mathlinks.ro/Forum/viewtopic.php?search_id=1576618391&t=148696 I think this lemma cannot be used in this problem because no direct evidence shows that $ P(x)$ is a monic polynomial. And for your lemma, one of my classmates has given a beautiful solution. Thank you all the same.

rchlch wrote: Albanian Eagle wrote: There are stronger lemmas out there like http://www.mathlinks.ro/Forum/viewtopic.php?search_id=1576618391&t=148696 I think this lemma cannot be used in this problem because no direct evidence shows that $ P(x)$ is a monic polynomial. And for your lemma, one of my classmates has given a beautiful solution. Thank you all the same. It was just a reply to test20's post

My solution was too big(6 pages). however here is an outline:

I give this exam and i couldn't solve this problem in fact only one of students solved this problem, his main idea is : if a+b is square then a*x^2+b*x^2 is square too, so p(ax^2)+p(bx^2) is perfect square for all integer x so there exist a g(x) such: p(ax^2)+p(bx^2)=g(x)^2 if p(x)=(a_n)*x^n+.... then (a_n)*(a^n+b^n)=u^2 (g(x)=u*x^k+...) for all a,b (a+b=perfect square) let a=b=2 so (a_n)*2^(n+1)=u^2 and ... it's easy to see that p(x)=(k^2)*(x^2) or 2*(k^2), so we solve this hard problem

Theorem_ let $f$ be a integer polynomial.We have $f(a+tp^s)\equiv {}^{p{}^{s+1}}f(a)+tp^sf{}'(a)$such that $(t,p)=1$.So by above theorem we have for any integer polynomial $Q$ which has not any double root ,there are infinitely many prime $p$ which there exist some $n$ such that $p\mid Q(n)$ but $ Q(n)\not\equiv {}^p{}^{2}0$.now suppose $p(a)+p(x^2-a)=Q(x)$ .(step 1)if $Q$ has not any double root ,we have $p\mid Q(n)$ but $ Q(n)\not\equiv {}^p{}^{2}0$ a contraction.(step 2)if $Q$ has some double root, we have $Q(x)=R_{a}(x)T_{a}(x)^2$ such that $R_{a}(x)$ has not any double root .$Q(m)$ is a perfect square for any positive integer $m$ so $R_{a}(Y)$ is a perfect square for all $y> M$ and we have a contraction same way to step 1.

And how to solve the main problem?

anantmudgal09 wrote: and if $d$ is odd then we have $$\left((t^2-1)^{\frac{d-1}{2}}-1\right)^2<\left(\frac{g(t)}{tc}\right)^2<\left((t^2-1)^{\frac{d-1}{2}}\right)^2$$which is again a contradiction! Thus, we must have $d=1$. How can you get the left side?

anantmudgal09 wrote: Lemma 2. Let $f$ be a non constant polynomial with integer such that $\sqrt{f(n)}$ is an integer for all positive integers $n$. Then there exists a polynomial $g(x)$ with integer coefficients such that $f(x)=g(x)^2$. I learned another simple way to prove this lemma from lectures on winter camp in Korea around 2018. Proof) Think of $f(x+m)f(x)$ for some natural number $m$. If $m$ is sufficiently large, we can separate complex roots of $f(x)$ and $f(x+m)$ and therefore $f(x+m)$ and $f(x)$ is relatively prime. By assumption, $f(x+m)f(x)$ is even degree and the maximal coefficient is square. Therefore, $f(x+m)f(x)=h(x)^2$ for some $h(x) \in \mathbb{Z}[x]$. Since $f(x)$ and $f(x+m)$ is prime, you can easily see that $f(x)=g(x)^2$ for some $g(x) \in \mathbb{Z}[x]$. Same idea is used in Proposition mentioned in https://artofproblemsolving.com/community/u314211h1985879p14247495

Another astonishing proof for Lemma by my student. Proof) Let $f(x)=a_n x^n +....+a_0$. By assumption, $a_n >0$. [Case 1] $n$ is odd. Multiply the term $(a_n x +1)$. There are infinitely many $x$ such that $a_n x+1$ is perfect square. Therefore, infinitely many $x$ such that $(a_n x+1)f(x)$ is perfect square. However, there are also $x$ such that $a_n x +1$ is not a perfect square and contradiction. [Case 2] $n$ is even, but $a_n$ is not a perfect square. Multiply the term $(a_n x^2 +1)$. And same as above. Here we used the fact that pell equation $y^2 - a_n x^2 =1$ has infinitely many solution. Therefore, $n$ is even and $a_n$ is perfect square and $f(x)=g(x)^2$ for some $g(x) \in \mathbb{Z}[x]$.

Here is a smol bren solution. Write the polynomial,as $x^d.P(x)$, with $P(0)$ non zero.Assume $P$ non-constant.Then assuming,$P$ is not a square ,write it as a square times a bunch of irreducibles.Consider such a irreducible ,say $h(x)$,and then by Schur ,choose a very large prime factor of the polynomial $h(x^2)$.Then using Bezout,we can conclude that if $p|h(m^2)$,then $p$ does not divide any other irreducible factor of $P$ evaluated at $m^2$.Then,again using bezout but this time with $h'(x)$,we conclude that if $p$,is large enough ,then $p$ also doesn't divide $h'(m^2)$,thus from Hensel,we can uniquely lift the root corresponding to $m^2$ mod $p$ to mod $p^2$ .Due to this unique lift ,we can find such an $n$,such that $n \equiv m^2$ mod $p$ but $p^2$ does not divide $P(n)$.Thus we have that $v_p(P(n))$ is odd.Now choose a $b$ such that $v_p(b)=j$ is even and quite large.As $p$ is large (forgot to mention $p$ doesn't divide $P(0)$,so $p$ doesn't divide $P(b)$). Now,we use hensel's again.Firstly note that $n$ is a quadratic residue mod $p$.So by hensel's on the polynomial $x^2-n$,we see that the derivative is non zero mod $p$.Thus,we can find a solution to this poly mod $p^{j+1}$,such that $v_p(x^2-n)$ is exactly $j$.Thus we have found $b+n$ is a perfect square but $v_p(n^d.P(n)+b^d.P(b))$ is odd which is a contradiction.Thus,$P(x)$ is a perfect square. Using a very similar argument as above,we can prove that $d$ is even(Basically choosing $a,b$,such that $P(a)$ has a large $v_p$,which is obv even,except here we choose $b$ to have small odd $v_p$,and obv $p$ doesn't divide $P(b)$.$a+b$ being a perfect square is ensured by the very similar hensel argument as above). So we have that we can write $P(a)+P(b)$ as $a^{2d}Q(a)^2+b^{2d}Q(b)^2$.So if we fix $a$,we see that $a^dQ(a)$ is a part of infinitely many Pythagorean triples,which is impossible. Observing the left out cases(which are not that hard),we get our solutions.

As in #26, $f(ax^2)+f(bx^2)$ is always a square for a fixed pair $(a,b)$ with $a+b$ being a square, so $g(x)^2=f(ax^2)+f(bx^2)$ for some integer polynomial $g(x)$. In addition, we consider only the case $\deg(f) \geq 2$. Next, we consider the leading coefficient of this polynomial; it is of the form $T(a^n+b^n)$ ($T$ is the leading coefficient of $f$), which shall be a square. If $n$ is even, plug $(1,p^2-1),(1,p^2+2p)$ for some prime $p$ to see that $2T, T$ are QR's modulo $p$ for all primes $p$, so $2$ is a QR for all primes $p$, absurd, since $(\frac{2}{p})=(-1)^{\frac{p^2-1}{8}}$. Now we can finish the other case with $(2,2),(3,1)$ : $2^{n+1}T$ is a square, hence $T$ is a square, so $3^n+1=x^2$ is a square, so $3^n=(x-1)(x+1)$ and thus $x-1=1$ and $n=1$, contradiction.

I see pleny of solutions over here depending on this theorem about a polynomial being square too many times. I solved to problem using a totally different approach with pells equations, some estimations of the growth of some terms, and an unexpected use of Norms function at the end. I will write down the solution tomorrow.

Suppose $degP > 0$. If $P$ is constant so $2P(2)$ must be a square, so $P \equiv 2k^2$ for some integer $k$. Indeed all of these work. Also suppose that the leading coefficient of $P$ is positive. If it's negative then $P(2N^2)$ is negative for big $N$, but is must also be twice a perfect square, contradiction. Fix some positive integer $t$ such that the equation $b^2 - 2a^2=t$ has a solution. We know there are infinetely many big $t$'s satisfying this (perfect squares for instance). By pell's equation we know that, given one solution $b_0^2 - 2a_0^2$, we can find infinetely many solutions of the form $$b_n + a_n \sqrt2= (b_0 + a_0 \sqrt2)(3+2sqrt2)^n.$$Just so I'll write quicker, set $ r = 3 + 2 \sqrt2$, we'll use it at lot. Now we know that, as $2a_n^2 + 2a_n^2$ is the square of an integer, $2P(a_n^2)$ must be the square of an even integer, say, by definition, $4r_n^2$. So $P(a_n^2) = 2r_n^2$. We also know that $b_n^2 - t + t$ is a perfect square, so $P(b_n^2 - t) = s_n^2 - P(t)$, for some integer $s_n$. But, by definition, $b_n^2 - t = 2a_n^2$, so $2r_n^2$ and $s_n^2 - P(t)$ must be equal. So we have that $s_n^2 - 2r_n^2 = P(t)$. But this means that $s_n, r_n$ are pell's solutions for $x^2 - 2y^2 = P(t)$. This means that $$s_n + r_n \sqrt2 = (s_0 + r_0 \sqrt2)r^{t_n}$$for some minimal solution $(s_0,r_0)$ and some integer $t_n$. As there are only finitely many minimal solutions for pell's equation, by the pigeon hole principle one of them must appear infinetely many times, varying $n$. WLOG call it $(s_0,r_0)$. In other words, we can say that $$s_n = \frac{s_0 + r_0 \sqrt2}{2}r^{t_n} + \frac{s_0 - r_0 \sqrt2}{2}r^{-t_n}$$so $$s_n^2 = \big( \frac{s_0 + r_0 \sqrt2}{2} \big)^2 r^{2t_n} + \big( \frac{s_0 - r_0 \sqrt2}{2} \big)^2 r^{-2t_n} + 2\frac{s_0^2 - 2r_0^2}{4} = (1+o(1))\big( \frac{s_0 + r_0 \sqrt2}{2} \big)^2 r^{2t_n}$$So this is one estimate for $s_n^2$. Let $d = degP$ and $c$ the leading coefficient. Now we also know that $$s_n^2 = P(b_n^2 - t) + P(t) = (1+o(1))P(b_n^2) = (1+o(1))c.b_n^{2d}.$$As $$b_n = (1+o(1))\frac{b_0+a_0 \sqrt2}{2}r^n,$$$$s_n^2 = (1+o(1))c.\big( \frac{b_0+a_0 \sqrt2}{2} \big) ^{2d}r^{2nd}$$Therefore the ratio between the $2$ estimates converges to $1$. So $$lim_{n \to \infty} \frac{\big( \frac{s_0 + r_0 \sqrt2}{2} \big)^2 r^{2t_n}}{c.\big( \frac{b_0+a_0 \sqrt2}{2} \big) ^{2d}r^{2nd}} = 1.$$So $$lim_{n \to \infty} \frac{\big( \frac{s_0 + r_0 \sqrt2}{2} \big)^2}{c.\big( \frac{b_0+a_0 \sqrt2}{2} \big) ^{2d}} r^{2t_n - 2dn} = 1.$$So, a constant times an integer power of $r$ converges to $1$. Due to the fact the the sequence $C.r^m$ is discrete, if it converges to $1$, it's eventually $1$. So there exists an integer $q$ such that $$\frac{\big( \frac{s_0 + r_0 \sqrt2}{2} \big)^2}{c.\big( \frac{b_0+a_0 \sqrt2}{2} \big) ^{2d}} r^q = 1.$$Rearranging things and substituting $r$ back to $3+2 \sqrt2$, we have $$(s_0 + r_0 \sqrt2)^2 (3+2 \sqrt2)^t = c(b_0 + a_0 \sqrt2)^{2d} 2^{2d-2}$$Now we are gonna make use of the Norm function defined by $N(m + n \sqrt2) = m^2 - 2n^2$, where $m,n$ are rationals. One can easily prove that this function is well defined and is multiplicative. So we have $$(s_0^2 - 2r_0^2)^2 . 1^t = c^2(b_0^2 - 2a_0^2)^2 2^{4d-4}$$So $$P(t)^2 = c^2 . t^{2d} . 2^{4d-4}$$As the leading coefficient of $P$ is positive, $P$ is eventually positive, so we can take the squareroot of both sides to conclude that $$P(t) = c.t^d.2^{2d-2}$$But notice that this is true for infinetely many big integers $t$'s, so it must be true that $$P(x) = x^d.c.2^{2d-2}$$But remember that $c$ is the leading coefficient of $P$, so $c = c.2^{2d-2}$, so $2^{2d-2}=1$, so $d$ must be $1$, and $P(x) = cx$. Now, as $2P(2)$ is a square, so $4c$ is a square, so $c$ itself is a perfect square. Given that, clearly $a+b$ is a square if and only if ac+bc is a square. Therefore all solutions are $P(x) = k^2x$ and $ P(x) = 2k^2$, where $k$ is an arbitrary integer.

We use a few well-known theorems to solve. Theorem 1. A polynomial is a perfect square at every integer iff it is a perfect square in $\mathbb{Z}[x]$ Theorem 2. (Mihailescu) For $a,b,c,d>1$ being positive integers, the Diophantine $a^b-c^d=1$ has a unique solution, which is $(a,b,c,d)=(3,2,2,3)$. For any $x$, we have $2P(2x^2)$ is a perfect square and $P(x^2)+P(3x^2)$ is also a perfect square. So, from theorem 1 there are polynomials $A(x),B(x)\in\mathbb{Z}[x]$ such that \[2P(2x^2)=A(x)^2,\ \ P(x^2)+P(3x^2)=B(x)^2\]Let $k$ be the leading coefficient of $P$ and $d=\deg P>0$. Then we have $2^{d+1}k=u^2$ and $(3^d+1)k=v^2$ for some integers $u,v$. If $d$ is even then $k=2w^2$ for some $w$, which means $3^d+1=2y^2$ for some $y$, which is a contradiction $\pmod{3}$. So, $d$ is odd. But then $k$ is a perfect square from first equation, which means $3^d+1$ is a perfect square. From theorem 2, $d=1$ is forced. Finally, note that for $d=1$ only $P(x)=c^2x$ works for some $c$ and for $d=0$ only $P(x)=2c^2$ works. These are the only solutions.