Nice to square you

Let $f(x)= x^3 + ax^2 + bx + c$ . Then, note that $f(x^2) - f(x)= x^6 + ax^4 + bx^2 + c - x^3 - ax^2 - bx - c$ $= x(x^5 + ax^3 - x^2 + (b-a)x^2 - bx)$ Let's try to factorize the quintic in the brackets. Note that the sum of the coefficients of the quintic is $1 + a - 1 + (b-a) - b= 0$ , implying $1$ is a root of the polynomial. Dividing it by $x-1$ , we find out $\frac{(x^5 + ax^3 - x^2 + (b-a)x^2 - bx)}{x-1}= x^4 + x^3 + (a+1)x^2 + ax + b$ Hence, we obtain $x(x^5 + ax^3 - x^2 + (b-a)x^2 - bx)= x(x-1)(x^4 + x^3 + (a+1)x^2 + ax + b)$ From the conditions in the question, we must have $x(x-1)(x^4 + x^3 + (a+1)x^2 + ax + b)= 0$ Note that $0$ and $1$ are two roots of the equation. Let's try to find the number of integer solutions to $g(x)= x^4 + x^3 + (a+1)x^2 + ax + b= 0$ . First, check that if we set $a=-4$ , $b= 0$ , we get $2$ and $-2$ as two roots.

Assume $g(x)$ has more than $2$ roots. Obviously it cannot have exactly $3$ roots, since if the fourth root weren't an integer, then the sum of the roots couldn't be an integer. Let's assume $g(x)$ has four integer roots. Let them be $p$ , $q$ , $r$ , and $s$ . From Vieta's relations, we obtain: $p+q+r+s= -1$ $pq + qr + rp + rs + qs + ps= a+1$ $pqr + qrs + prs + pqs= -a$ $pqrs= b$ Note that $p+q+r+s \equiv 1 \pmod{2}$ . Then, either one of them is odd, and the rest even, or one of them is even, and the rest odd.

Case $1$ Exactly one of $(p,q,r,s)$ is odd.
WLOG let $p \equiv 1 \pmod{2}$ , and $q,r,s \equiv 0 \pmod{2}$ . Then, note that $pqr + qrs + prs + pqs \equiv 1 \pmod{2}$ $\implies -a \equiv 1 \pmod{2} \implies a \equiv 1 \pmod{2}$ Again, we have $pq + qr + rp + rs + qs + ps \equiv 1 \pmod{2}$ $\implies a+1 \equiv 1 \pmod{2}$ However, both $a$ and $a+1$ cannot be $\equiv 1 \pmod{2}$ , a contradiction. Thus this case produces no result.

Case $2$ Exactly one of $(p,q,r,s)$ is even
WLOG let $p \equiv 0 \pmod{2}$ . Then, note that $pqr + qrs + prs + pqs \equiv 1 \pmod{2}$ $\implies -a \equiv 1 \pmod{2} \implies a \equiv 1 \pmod{2}$ Again, we have $pq + qr + rp + rs + qs + ps \equiv 1 \pmod{2}$ $\implies a+1 \equiv 1 \pmod{2}$ However, both $a$ and $a+1$ cannot be $\equiv 1 \pmod{2}$ , a contradiction. Thus this case produces no result either.

Thus $g(x)=0$ has at most $2$ integer roots. Thus, $f(x^2)-f(x)$ can have at most $4$ integer roots. It can be checked that $0, 1, 2, -2$ are roots of $f(x^2)-f(x)$ , where $f(x)= x^3 - 4x - 4$ . We thus conclude the maximum number of integers is $\boxed{4}$ .

Let $f(x) = x^3 + ax^2 + bx + c$ . We want to find maximum number of integer roots of: $f(x^2) - f(x) = x^6 + ax^4 - x^3 + (b-a)x^2 -bx$ $=x(x-1)(x^4 + x^3 + (a+1)x^2 + ax + b) = 0.$ Clearly, we see that 0 and 1 already satisfy $f(x^2) - f(x) = 0.$ The remaining factor $(x^4 + x^3 + (a+1)x^2 + ax + b) = 0$ , we prove below has at most two integer roots, which shall prove that the answer to the problem at hand is at most 4.

Claim : The polynomial $(x^4 + x^3 + (a+1)x^2 + ax + b)$ can have at most 2 integer roots.

Proof : Clearly there cannot be exactly 3 integer roots since the coefficients of the polynomial are integers, and thus the sum of all roots is an integer. Thus, it is enough to prove that not all four roots are integers. Suppose for sake of contradiction that $i,j,k,l$ are 4 integer roots of the above equation, then: $i + j+ k+l = -1$ $ij + ik + il + jk + jl + kl = (a+1)$ $ijk + ijl + ikl + jkl = (-a).$ Since $i + j + k+ l$ is odd- either 3 roots are odd and one even or 1 odd and 3 even. In the first case, say W.L.O.G that $i,j,k$ are odd and $l$ is even. But then, from the third equation this means that $a$ is odd, and from the second equation we get that $ij + jk + ik \equiv (a+1) (mod 2).$ Which means that $a+1$ is also odd which contradicts $a$ being odd. Similarly the second case of $j,k,l$ being even and $i$ being odd also leads to the same contradiction. Q.E.D. Hence, the answer can be at most 4.

But, consider the polynomial: $f(x) = x^3 -4x^2 - 4 .$ $0 , 1 , 2 , -2$ are four integers satisfying $f(n^2) = f(n).$ Thus, the answer is exactly 4.

Let $f(x) = x^3 + ax^2 + bx + c$ and

$g(n) = f(n^2) - f(n) = 0$

So, $g(n) = (n^6 + an^4 + bn^2 + c) - (n^3 + an^2 +bn + c)$

$= n^6 + an^4 - n^3 + (b-a)n^2 - bn$

$= n(n^5 + an^3 - n^2 + (b-a)n - b)$

So, we get one solutions as n=0

now consider the polynomial $h(n)=n^5 + an^3 - n^2 + (b-a)n - b$

Let k = b-a

Then $h(n)=n^5 + an^3 - n^2 + kn - b$

Now apply Descartes Rule Of Signs

Case 1: k>0

$h(n)$ has 3 sign changes so, maximum number of positive roots = 3

$h(-n)$ has 0 sign changes so, maximum number of negative roots = 0

Case 2: k<0

$h(n)$ has 1 sign change so, maximum number of positive roots = 1

$h(-n)$ has 2 sign changes so, maximum number of negative roots = 2

Therefore, we know that in the above equation, there will be maximum of 3 integer roots and atleast 2 imaginary roots.

Hence the maximum number of possible roots that is possible number of distinct integers that satisfy $f(n^2)=f(n)$ is 4

let the polynomial be f(x) = x^3+ax^2+bx+c (as it is monic integer polynomial coefficient of x^3 =1) (a,b,c are constant coefficients)

f(n^2) = n^6+an^4+bn^2+c

f(n) = n^3+an^2+bn+c

f(n^2) = f(n)

=> n^6+an^4+bn^2+c = n^3+an^2+bn+c

=> n^6 - n^3 + an^4 - an^2 + bn^2 - bn = 0

now this is a 6th order equation which has 6 roots but not all may be real or integers. we have to find out how many maximum integer real roots are possible.

=> n^3(n^3-1) + an^2(n^2-1) + bn(n-1) = 0

=> n(n-1) [ n^2(n^2+n+1) + an(n+1) + b ] = 0

=> n=0 and n=1 are confirmed roots of this equation

n^2(n^2+n+1) + an(n+1) + b = 0

i.e. n^4+n^3+n^2(a+1)+an+b = 0

this equation has 4 roots let them be P,Q,R,S

then P+Q+R+S = -(COEFFICIENT OF n^3 / COEFFICIENT OF n^4) = -1

which is clearly independent of values of a and b

let us take a = b then

n^2(n^2+n+1) + a(n^2+n) +a = 0

n^2(n^2+n+1) + a(n^2+n+1) = 0

(n^2 + a)*(n^2+n+1) = 0

now n^2+n+1 = (n+1/2)^2 + (3/4) > 0

then n^2 + a = 0 now n may be a real integer when a is a negative perfect square for example let k be an integer and a = -k^2

then n^2 + (-k^2) = 0

=> n = +k or n = -k

therefore n = 0,1,k,-k are 4 real integer roots possible

as complex roots always occurs in conjugate pairs other two roots are complex roots.

else if a not equal to b then equation n^2(n^2+n+1) + an(n+1) + b = 0 has 4 complex roots for any real values of a and b in which a is not equal to b.

therefore maximum of 4 integer real roots are possible.

Let $f(x)=x^3+ax^2+bx+c$ where $a,b,c$ are integers. Clearly, all $n$ must be roots of the polynomial $g(x)=f(x^2)-f(x)=x^6+ax^4-x^3+(b-a)x^2-bx.$ Since $n^2=n$ when $n=0, 1$ these two values will always satisfy the given equation and are thus roots of $g$ . This means $x(x-1)$ is a factor of $g$ , so dividing though we have $g/(x(x-1))=x^4+x^3+(a+1)x^2+ax+b.$ Our remaining values of $n$ must be roots of this polynomial.

I claim the polynomial can only have 2 integer roots. Suppose it has 3: $p,q,r.$ Then $(p^4+p^3+p^2)+(p^2+p)a+b=0$ (same for $q$ and $r$ .)

Now consider the $3 \times 3$ matrix $\left( \begin{array}{ccc} p^4+p^3+p^2 & p^2+p & 1 \\ q^4+q^3+q^2 & q^2+q & 1 \\ r^4+r^3+r^2 & r^2+r & 1 \end{array} \right)$ Two roots define $a, b$ . This means that for there to be three roots total, each row in the matrix must be a linear combination of the other two. Now, subtract the first row from the second and third rows. $\left( \begin{array}{ccc} A & B & 1 \\ C & D & 0 \\ E & F & 0 \end{array} \right)$ Where $A, B, C, D, E, F$ are integers and the rightmost values of the second and third rows are now 0. Now subtract the second row times $\frac{F}{D}$ from the third row, so we have $\left( \begin{array}{ccc} A & B & 1 \\ C & D & 0 \\ G & 0& 0 \end{array} \right)$ Here, each row must still be a linear combination of the other two. However, the matrix is rank 3 due to the three 0's in the bottom right corner, so none of rows can be linear combinations of the other two. This is a contradiction. Consequently, we can have most two roots for each set of $a,b$ .

It is easy to see that two roots is indeed possible. An example is $p=2, q=4$ which has $a=-22, b=104$ .

Thus, these two roots, along with our original roots of $0, 1$ yields a maximum number of $4$ distinct values for $n$ .

A general monic third degree polynomial is $f(x)=x^{3}+ax^{2}+bx+c$ where a,b,c are arbitrary constants. Consider $f(n)=f(n^{2}).$ This can be written as $n^{3}+an^{2}+bn=n^{6}+an^{4}+bn^{2}$ , as c is present on both sides of the equality. n=0 is one such integer that will satisfy this. Disregarding that we have:

1. $n^{2}+an+b=n^{5}+an^{3}+bn=n(n^{4}+an^{2}+b)$ Which implies that
2. $n=\frac{n^{2}+an+b}{n^{4}+an^{2}+b}$ if the denominator is not zero. If it is, then the numerator must be also as that is the only way to satisfy (1). Hence $n^{4}+an^{2}=n^{2}+an$ , where b cancels as it is present on both sides. As n is not zero, since we considered that earlier, we have
3. $n^{3}+an=n+a$ , which can be rearranged into a third order polynomial equal to zero. This has a max of three solutions n. Considering our rational equation (2) above, clearly there are no integer solutions greater than n=1, but n=1 is a solution of (3). Therefore the maximum number of solutions is 4! That is, n=0 and the three solutions of (3).

At first glance the values n=0 and n=1 are obvious. Then considering the cubic to be x^3 + ax^2 + bx +c and applying f(n)=f(n^2) we get: n^3 + an^2 + bn = n^6 + an^4 + bn^2. Now 0 is a possible soln. After that dividing by n we get n^2 + an + b = n^5 + an^3 + bn Rearranging we get, (n-1) (n^2 + b + (n^2 + a)(n)(n+1))=0 Now either n-1=0 in which case n=1 or the other factor is zero. If the other factor is zero then both (n^2 + b)=0 and (n^2 + a)(n)(n+1)=0 From the first we get n=(-b)^0.5 assuming b is negative and from second part we get n=-1 or n=(-a)^0.5 since n is not equal to 0. THEREFORE the four values of n are 1 0 -1 and (-a)^0.5 or (-b)^0.5 assuming a = b and both a and b are negative.

Clearly for n = 0 and 1, the condition holds true for ANY monic integer degree three polynomial.

If we drew a horizontal line and a monic integer cubic, there would be at most three points of intersection. In order to maximize the possible number of distinct n that we could have, the cubic would produce the same values for $n, n^2,$ and $n^4$ since $f(n) = f(n^2) = f(n^4).$

Thus the cubic would be in the form $f(x) = (x - n)(x - n^2)(x - n^4) + c.$

Then the possible n that would work would $0, 1, n,$ and $n^2$ giving us 4 possible distict integers n.

Let f(x) = x^3 + ax^2 + bx + c. f(n^2) = n^6 + an^4 + bn^2 + c. f(n) = n^3 + an^2 + bn +c. Equating both,c gets cancel out and after further simplification we get, n^4 + n^3 + n^2(1+a) + an +b = 0. As this is a bi-quadratic monic equation there will be four roots and hence the maximum number of values of n.

Suppose the polynomial is:

$f(x)=x^3-ax^2+bx-c$ (a,b,c are integers)

Let us find how much the polynomial tells us.Let it has $3$ integer roots ( $\neq 0,1$ ) as $\alpha, \beta, \gamma$ . Then,

$f(\alpha)=f(\beta)=f(\gamma)=0$

Now,since $\alpha, \beta, \gamma$ are integers, $f(x)$ is an integer polynomial,we can get at most two pairs of integer roots such that one is the square of the other.One pair will not hold this.

Say, $\beta=\alpha^2$ .Now either $\gamma$ has to be $\alpha^2$ or $\alpha^4$ to be square of one of the other two roots.Say $\gamma=\alpha^4$ .

Then,

$a=\alpha+\alpha^2+\alpha^4$

$b=\alpha*\alpha^2+\alpha^2*\alpha^4+\alpha*\alpha^4=\alpha^3+\alpha^5+\alpha^6$

$c=\alpha*\alpha^2*\alpha^4=\alpha^7$

Such $f(x)$ can be found for any $\alpha$ ( $\neq 0,1$ ),& hence from here we have 2 pairs of integers such that $f(n)=f(n^2)$ ,applying $n=\alpha$ & $n=\alpha^2$ .

Consider the condition again. It is true also if $n^2=n$ or, $n(n-1)=0$ . Thus, $n=0$ or $1$ .These also satisfy the conditions.

Thus we get a total of 4 such pairs,as required.

Let's write the unexpanded form of the polynomial: $(x-a)(x-a^{2})(x-a^{4})+C$ where $C$ is an arbitrary constant. Because $a^{4}$ is $a^{2}$ squared, and $a^{2}$ is simply $a$ squared, we already have two cases that will make the equation equal to $C$ . Remember, this is the case because if we set any of the binomials equal to zero, then $x$ solves out to be the negative constant (Vieta's Formulas?). Anyways, that's two out of the way. Now let's try to find some more. Let's ignore the actual function for a second. We know that if $n=n^{2}$ , then no matter what, they'll evaluate to the same thing! The solutions for that are one and zero, which add two more possible answers. Thus, the answer is $2+2=\boxed{4}$ .