$F$ is a polynomial, $\deg F = 3$, and $(x^2 - 1)(x^2 - 2) | F(F(x)) - x$. Prove that $F$ exists

$F$ is a polynomial, $\deg(F) = 3$, and $(x^2 - 1)(x^2 - 2) | F(F(x)) - x$. Prove that:

a) $F$ exists

b) There are at least 10 such polynomials

What I've tried to do:

$(x^2 - 1)(x^2 - 2) \mid F(F(x)) - x\implies \begin{cases}F(F(1)) = 1 \\ F(F(-1)) = -1 \\ F\left(F\left(\sqrt{2}\right)\right) = \sqrt{2}\\ F\left(F\left(-\sqrt{2}\right)\right) = -\sqrt{2}\end{cases} $

Then I tried to apply interpolation somehow but it didn't help.

Thanks in advance!

Solution 1:

I think a key is to think in terms of fixed points and cycles. You want an $F$ that either treats $\{1,-1,\sqrt{2},-\sqrt{2}\}$ as fixed points or as parts of two-cycles. Your implication $\implies$ is actually a two-way implication $\iff$. So if you can find a cubic polynomial that either fixes these four points or takes them through a two-cycle, you have such an $F$.

There are $10$ permutations of $\{1,-1,\sqrt{2},-\sqrt{2}\}$ that only involve fixed points and two-cycles. For each one, we can write down the corresponding system of four linear equations in $F$s coefficients. Each system has the same coefficient matrix, but different constant vector. For instance the system corresponding to $(1\leftrightarrow\sqrt{2},-1\leftrightarrow-\sqrt{2})$ is

$$\begin{aligned} A+B+C+D&=\sqrt{2}\\ -A+B-C+D&=-\sqrt{2}\\ 2\sqrt{2}A+2B+\sqrt{2}C+D&=1\\ -2\sqrt{2}A+2B-\sqrt{2}C+D&=-1\\ \end{aligned}$$

Or in matrix form, is $$\begin{aligned} \begin{bmatrix} 1&1&1&1\\ -1&1&-1&1\\ 2\sqrt{2}&2&\sqrt{2}&1\\ -2\sqrt{2}&2&-\sqrt{2}&1\\ \end{bmatrix} \begin{bmatrix}A\\B\\C\\D \end{bmatrix} &=\begin{bmatrix}\sqrt{2}\\-\sqrt{2}\\1\\-1\end{bmatrix}\\ M \begin{bmatrix}A\\B\\C\\D \end{bmatrix} &=\begin{bmatrix}\sqrt{2}\\-\sqrt{2}\\1\\-1\end{bmatrix}\\ \end{aligned}$$

and $M$ is the same for each permutation. It is worth our effort then to compute $$M^{-1}=\begin{bmatrix} -1/2&1/2 &\sqrt{2}/4&-\sqrt{2}/4\\ -1/2&-1/2&1/2&1/2\\ 1&-1&-\sqrt{2}/4&\sqrt{2}/4\\ 1&1&-1/2&-1/2 \end{bmatrix}$$

And so $$\begin{aligned} \begin{bmatrix}A\\B\\C\\D \end{bmatrix} &=\begin{bmatrix} -1/2&1/2 &\sqrt{2}/4&-\sqrt{2}/4\\ -1/2&-1/2&1/2&1/2\\ 1&-1&-\sqrt{2}/4&\sqrt{2}/4\\ 1&1&-1/2&-1/2 \end{bmatrix} \begin{bmatrix}\sqrt{2}\\-\sqrt{2}\\1\\-1\end{bmatrix}\\ &=\begin{bmatrix}-\sqrt{2}/2\\0\\3\sqrt{2}/2\\0 \end{bmatrix} \end{aligned}$$

If this is right, then $F(x)={-\frac{\sqrt{2}}{2}}x^3+\frac{3\sqrt{2}}{2}x$ works. Well, a CAS confirms that $F(F(x))-x$ factors as $1/4 (x-1) x (x+1) (x^2-2) (x^4-6 x^2+7)$.

You can get more solutions for $F$ using other permutations on $\{1,-1,\sqrt{2},-\sqrt{2}\}$ that only involve fixed points and two-cycles. However some of these will lead to $0$ for $A$, and not quite give a cubic $F$. For example, the identity permutation leads to $F(x)=x$ and $(1\leftrightarrow-1,\sqrt{2}\leftrightarrow-\sqrt{2})$ leads to $F(x)=-x$.

There are 10 permutations in $S_4$ using only fixed points and two-cycles; two of them certainly lead to degenerate "cubics" as cited above. At least one has now been confirmed to lead to a truly cubic $F$, and my guess would be that the same would happen for the remaining $7$. Thus this method provides 8 $F$s that work, plus two more that might count if degenerate cubics are allowed.

I think to find all solutions to this problem, you could invoke a system of eight linear equations and then find under what conditions that system is consistent. We would allow each of $\{1,-1,\sqrt{2},-\sqrt{2}\}$ to go to arbitrary real numbers $\{m,n,p,q\}$ and then demand that they come back. (These equations will be linear in the coefficients of $F$, but not in $\{m,n,p,q\}$.)

$$\begin{aligned} \begin{bmatrix} 1&1&1&1\\ -1&1&-1&1\\ 2\sqrt{2}&2&\sqrt{2}&1\\ -2\sqrt{2}&2&-\sqrt{2}&1\\ m^3&m^2&m&1\\ n^3&n^2&n&1\\ p^3&p^2&p&1\\ q^3&q^2&q&1\\ \end{bmatrix} \begin{bmatrix}A\\B\\C\\D \end{bmatrix} &=\begin{bmatrix}m\\n\\p\\q\\1\\-1\\\sqrt{2}\\-\sqrt{2}\end{bmatrix}\\ \end{aligned}$$

You could continue to investigate this system and see what conditions on $\{m,n,p,q\}$ make the system consistent, and then see what solution sets for $\{A,B,C,D\}$ there are. That could get messy though since the equations are not linear in $\{m,n,p,q\}$.

The above system simplifies to $$\begin{aligned} \begin{bmatrix} m^3&m^2&m&1\\ n^3&n^2&n&1\\ p^3&p^2&p&1\\ q^3&q^2&q&1\\ \end{bmatrix} \begin{bmatrix} -1/2&1/2 &\sqrt{2}/4&-\sqrt{2}/4\\ -1/2&-1/2&1/2&1/2\\ 1&-1&-\sqrt{2}/4&\sqrt{2}/4\\ 1&1&-1/2&-1/2 \end{bmatrix} \begin{bmatrix}m\\n\\p\\q \end{bmatrix} &=\begin{bmatrix}1\\-1\\\sqrt{2}\\-\sqrt{2}\end{bmatrix}\\ \end{aligned}$$ $$\begin{aligned} \begin{bmatrix}A\\B\\C\\D \end{bmatrix} &=\begin{bmatrix} -1/2&1/2 &\sqrt{2}/4&-\sqrt{2}/4\\ -1/2&-1/2&1/2&1/2\\ 1&-1&-\sqrt{2}/4&\sqrt{2}/4\\ 1&1&-1/2&-1/2 \end{bmatrix}\begin{bmatrix}m\\n\\p\\q \end{bmatrix} \end{aligned}$$

So there is a system of quartic equations in $m,n,p,q$ that once solved, provides solutions for $A,B,C,D$.

Having four polynomial equations in four variables $m,n,p,q$, one would expect only a finite number of solutions. We've already accounted for $10$ solutions; it's possible that there are no more. Assuming these four equations have the appropriate algebraic independence, Bézout's Theorem says there are at most 64 complex solutions.

Solution 2:

If the coefficients are allowed to be over $\mathbb{C},$ since you have a system of four equations with four unknowns then elimination theory tells you that there should be a solution (In fact, at least sixteen solution), but somehow I don't think that this is the intended answer.

Solution 3:

Using the CAS Magma:

> A<a,b,c,d>:=PolynomialRing(Integers(),4);
> P<X>:=PolynomialRing(A);
> F:=((a*X+b)*X+c)*X+d; F;
    a*X^3 + b*X^2 + c*X + d
> F2:=Evaluate(F,F)-X; F2;
    a^4*X^9 + 3*a^3*b*X^8 + (3*a^3*c + 3*a^2*b^2)*X^7 
        + (3*a^3*d + 6*a^2*b*c + a^2*b + a*b^3)*X^6 + (6*a^2*b*d 
        + 3*a^2*c^2 + 3*a*b^2*c + 2*a*b^2)*X^5 + (6*a^2*c*d 
        + 3*a*b^2*d + 3*a*b*c^2 + 2*a*b*c + b^3)*X^4 
        + (3*a^2*d^2 + 6*a*b*c*d + 2*a*b*d + a*c^3 + a*c + 2*b^2*c)*X^3 
        + (3*a*b*d^2 + 3*a*c^2*d + 2*b^2*d + b*c^2 + b*c)*X^2 
        + (3*a*c*d^2 + 2*b*c*d + c^2 - 1)*X + a*d^3 + b*d^2 + c*d + d
> Quotrem(F2,(X^2-1)*(X^2-2));
     a^4*X^5 + 3*a^3*b*X^4 + (3*a^4 + 3*a^3*c + 3*a^2*b^2)*X^3 
         + (9*a^3*b + 3*a^3*d + 6*a^2*b*c + a^2*b + a*b^3)*X^2 
         + (7*a^4 + 9*a^3*c + 9*a^2*b^2 + 6*a^2*b*d + 3*a^2*c^2 
         + 3*a*b^2*c + 2*a*b^2)*X + 21*a^3*b + 9*a^3*d + 18*a^2*b*c 
         + 3*a^2*b + 6*a^2*c*d + 3*a*b^3 + 3*a*b^2*d + 3*a*b*c^2
         + 2*a*b*c + b^3
    (15*a^4 + 21*a^3*c + 21*a^2*b^2 + 18*a^2*b*d + 9*a^2*c^2 
         + 3*a^2*d^2 + 9*a*b^2*c + 6*a*b^2 + 6*a*b*c*d + 2*a*b*d 
         + a*c^3 + a*c + 2*b^2*c)*X^3 
       + (45*a^3*b + 21*a^3*d + 42*a^2*b*c + 7*a^2*b + 18*a^2*c*d 
         + 7*a*b^3 + 9*a*b^2*d + 9*a*b*c^2 + 6*a*b*c + 3*a*b*d^2 
         + 3*a*c^2*d + 3*b^3 + 2*b^2*d + b*c^2 + b*c)*X^2 
       + (-14*a^4 - 18*a^3*c - 18*a^2*b^2 - 12*a^2*b*d - 6*a^2*c^2 
         - 6*a*b^2*c - 4*a*b^2 + 3*a*c*d^2 + 2*b*c*d + c^2 - 1)*X 
       - 42*a^3*b - 18*a^3*d - 36*a^2*b*c - 6*a^2*b - 12*a^2*c*d 
         - 6*a*b^3 - 6*a*b^2*d - 6*a*b*c^2 - 4*a*b*c + a*d^3 - 2*b^3 
         + b*d^2 + c*d + d

The last part describes the remainder that has to be set to zero, giving four equations in the four parameters. Now to solve it ... there must be a more clever way.

Using a bit more tricks, the irreducible components of the solution set have the equation systems, with the first two leading to trivial linear solutions, and the last two seemingly identical up to sign changes:

[
    a,
    b,
    c + 1
],
[
    a,
    b,
    c + 1,
    d
],
[
    a + 1/3*c,
    b,
    c^2 - 9/2,
    d
],
[

    a + 1/2*c + 1/2,
    b,
    c^2 - 5,
    d
],
[
    a + c + 1,
    b,
    c^2 + 3*c + 5/2,
    d
],
[
    a + 81600/208187*d^5 + 133428/208187*d^4 - 443850/208187*d^3 - 997520/208187*d^2 + 997530/208187*d + 37068/208187,
    b - 13856/208187*d^5 - 51068/208187*d^4 + 14136/208187*d^3 + 268986/208187*d^2 + 318018/208187*d + 19178/208187,
    c - 135160/208187*d^5 - 192840/208187*d^4 + 799474/208187*d^3 + 1537966/208187*d^2 - 2034978/208187*d + 89231/208187,
    d^6 - 9*d^4 - 5*d^3 + 281/8*d^2 - 31/4*d - 17/8
],
[
    a - 81600/208187*d^5 + 133428/208187*d^4 + 443850/208187*d^3 - 997520/208187*d^2 - 997530/208187*d + 37068/208187,
    b - 13856/208187*d^5 + 51068/208187*d^4 + 14136/208187*d^3 - 268986/208187*d^2 + 318018/208187*d - 19178/208187,
    c + 135160/208187*d^5 - 192840/208187*d^4 - 799474/208187*d^3 + 1537966/208187*d^2 + 2034978/208187*d + 89231/208187,
    d^6 - 9*d^4 + 5*d^3 + 281/8*d^2 + 31/4*d - 17/8
]

Solution 4:

This is a partial answer.

Let $K(x)$ be the factor $\frac{F(F(x))-x}{(x^2-1)(x^2-2)}$. One can simplify the search significantly by restricting our search of $F(x)$ to be an odd polynomial in $x$, i.e.

$$F(x) = (ax^2 - b)x,\quad\text{ with }\; a \ne 0$$

There are already 4 pairs of real solutions given by

$$(a,b) = \begin{cases} \pm (2, 3),\\ \pm (\frac{\sqrt{5}-1}{2}, \sqrt{5} ),\\ \pm (\frac{\sqrt{5}+1}{2}, \sqrt{5} ),\\ \pm (\frac{1}{\sqrt{2}}, \frac{3}{\sqrt{2}} ) \end{cases} \quad\longrightarrow\quad \frac{K(x)}{x} = \begin{cases} 16 x^4- 24x^2+4\\ \\\frac12\left[ (7-3\sqrt{5})x^4 - (9-3\sqrt{5})x^2 + 4\right]\\ \\\frac12\left[ (7+3\sqrt{5})x^4 - (9+3\sqrt{5})x^2 + 4\right]\\ \\\frac14\left[ x^4 - 6x^2 + 7\right] \end{cases} $$ If one allow complex coefficients for $F(x)$, there are 4 more complex solutions and we are done. $$(a,b) = \pm (\frac{1+i}{2}, \frac{3+i}{2}) \quad\text{ and }\quad \pm (\frac{1-i}{2}, \frac{3-i}{2})$$

If $F(x)$ need to be real, then I don't have any good idea how to get the remaining two real solutions easily.