11

$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!

2'5 9'2
  • 54,717
Michael
  • 137

4 Answers4

3

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.

2'5 9'2
  • 54,717
  • Thank you, that's beautiful! I talked to the author of this problem today and she said that she'd miscounted something and the right task should be to prove that there are 8 such polynomials, not 10. However, all of them should have $deg(F)=3$ exactly and not lower. – Michael Dec 21 '13 at 20:03
  • 1
    Heh, my internet was down and I didn't know it. I rewrote this answer to make it more explicit; hope it still fits the bill. Now it's more clear why there should be at least 8, rather that 10. Note that there could theoretically be more solutions if there are two-cycles that step outside of ${1,-1,\sqrt{2},-\sqrt{2}}$. – 2'5 9'2 Dec 21 '13 at 22:55
  • Is this solution not a bit restrictive? $x=F(F(x))$ has (up to) 9 solutions, 3 of them are the fixed points of $F(x)=x$, the remaining are 3 pairs of 2 cycles. Among those 9, 4 are the given points, but it is not obvious that all of those 9 points should be chosen from that set. – Lutz Lehmann Dec 22 '13 at 11:21
  • For instance, $f(x)=\tfrac12x((\sqrt5-1)x^2-2\sqrt5)$ is a solution that has $\pm1$ in a cycle with $\mp\frac{\sqrt5+1}2$. – Lutz Lehmann Dec 22 '13 at 12:29
  • @LutzL I didn't claim this is all solutions; OP only asks for at least 8. Also, read the last sentence in my earlier comment to this answer. After OP's first comment to this answer, I'm pretty sure this was the intent of the problem's author. – 2'5 9'2 Dec 22 '13 at 17:29
  • Yes, it gets messy. I'm not sure if I overlooked your last system, this is the same I let Magma compute and try to find solutions for. Actually combined the enumeration of all solutions in the answers could already be complete. – Lutz Lehmann Dec 22 '13 at 18:09
1

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.

Igor Rivin
  • 25,994
  • 1
  • 19
  • 40
1

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
]
Lutz Lehmann
  • 126,666
1

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.

achille hui
  • 122,701