How do I find the roots of an iterated polynomial which is "solvable".

Question

Let $p(x)$ be a quadratic polynomial. $p(x) = x$ has 2 solutions, $p(p(x)) = x$ has 4 solutions and $p(p(p(p(x)))) = x$ has 16 solutions, four of which solve $p(p(x)) = x$.

Dividing $p(p(p(p(x))))-x$ by $p(p(x))-x$, we get an order 12 polynomial $Q(x)$, with a solvable Galois group, roughly equal to $(Z_4+Z_4+Z_4)\times(S_3)$.

The Galois group is only a small subgroup of $S_{12}$, because if $x_1$ is a solution then $x_2=p(x_1)$ is also a solution and the allowed permutations must preserve this. There are three $4$-cycles, which can be permuted (the $S_3$) and each $4$-cycle can be cycled (the $Z_4$'s).

Although $Q(x)$ is solvable, I find it extremely difficult to find the roots.

Answer 1

By a transformation of the form $ x\mapsto a x + b$ we can assume $p(x)=x^2+c$. Since we are interested in numbers that solve $Q(x)=0$ ALL polynomial operations are to be done mod $Q(x)$, thus all polynomials will be order 11 or less. Let $z_1, z_2=p(z_1), z_3=p(z_2), z_4=p(z_3)$ be one of the 3 four cycles. Our approach is to find polynomials that are invariant under cycles. Galois theory tells us that since there are 3 4 cycles these invariants will obey cubic equations with coefficients that are polynomials in c. I chose to solve for the following:

$t_0 = z_1+z_2+z_3+z_4$,

$t_1 = z_1+ i z_2-z_3-i z_4$,

$t_2 = z_1-z_2+z_3-z_4$,

$t_3 = z_1- i z_2-z_3+i z_4$,

Under cycles $t_0 \mapsto t_0$, $t_1 \mapsto -i t_1$, $t_2 \mapsto -t_2$ and $t_3 \mapsto i t_3$. Thus the following are invariant under cycles:

$R_0=t_0$, $R_1= t_1 ^ 4$, $R_2 = t_2 ^2 $ and $R_3= t_3 ^ 4$ .

The general method to find an equation for an invariant R, is to express it as a polynomial in x, with $Q(x)=0$, i.e. $t_0(x) = x+p(x)+p^2(x)+p^3(x)$ , etc. We then consider the equation $0=R^3+a R^2 + b R +d$ mod $Q$. Due to the magic of Galois theory, this equation has a solution, even though the polynomials are order 11. The resulting equations are complicated, but the process is straightforward. Using Mathematica, I was able to find the following:

$R_0$ obeys $R^3 + (4 c + 3) R + 4 = 0$ mod $Q$. The other equations are much mor complicated, so I will give the a, b and d coefficients.

For $R_1$ ,

$a=2 (45 + (8 - 96 i) c + 16 c^2)$,

$b = (1425 - 1200 i) + (720 - 3840 i) c - (3616 + 4864 i) c^2 - (1792 + 6144 i) c^3 - 1792 c^4$ and

$d=4 ((-1 - 2 i) + 4 c)^3 ((-1 + 2 i) + 4 c) (5 + 4 c)^2 $

For $R_2$,

$a= 2 (-3 + 4 c$,

$b = 9 - 40 c + 16 c^2$ and

$d = -4 (5 - 8 c + 16 c^2)$

Finally for $R_3$,

$a= 2 (45 + (8 + 96 i) c + 16 c^2)$,

$b=(1425 + 1200 i) + (720 + 3840 i) c - (3616 - 4864 i) c^2 - (1792 - 6144 i) c^3 - 1792 c^4$ and

$d = 4 ((-1 - 2 i) + 4 c) ((-1 + 2 i) + 4 c)^3 (5 + 4 c)^2$

These equations checked out numerically for c=0.5.

One remaining problem is that there are 3 solutions for $t_0$, 12 solutions for $t_1$ and $t_3$ and 6 for $t_2$, and to solve for a z, $Q(z)=0$ one needs a set of compatible t's. Not all combinations work and I have no means other than trial and error to find valid combinations.

Answer 2

wlog assume $p(x)=x^2+c$, similar to @tippy2tina,

Let $y_i,z_i$ be such that $p(p(y_i)) = z_i$ and $p(p(z_i)) = y_i$. Then both $y_i,z_i$ are roots of $p(p(p(p(x)))) = x$.

We need:

$p(p(y_i)) = (y_i^2+c)^2 + c = z_i$

$p(p(z_i)) = (z_i^2+c)^2 + c = y_i$

$(y_i^2+c)^2-(z_i^2+c)^2 = z_i - y_i$

$(y_i^2+z_i^2+2c)(y_i^2-z_i^2) = z_i - y_i$

$(y_i^2+z_i^2+2c)(y_i+z_i) = -1$

Assume $z_i$ is fixed and try solving the above cubic equation and we get $y_i = f(z_i)$. I am hoping you will get more solutions than what you started with.

Try also some relations between $y_i$ and $z_i$:

For example: Let $z_i = i y_i$, we get:

$(y_i^2+z_i^2+2c)(y_i+z_i) = -1 \implies y_i = \frac{-1}{(2c)(1+i)}$.

The above solution satisfies $(y_i^2+c)^2-z_i = (z_i^2+c)^2-y_i$. But does not satisfy, $(y_i^2+c)^2-z_i = -c$ for all possible $c$.

See if you can make nice choices like $z_i = ay_i+b$ for $a,b$ real and get the solution.