3

I'm trying to solve a problem right now. I'm not sure if I am on the right track or not, but if I am, this is the subproblem I am stuck on right now.

Let $f(x) = x^2 - 2$ and $g_n(x) = (f \circ^n f)(x) - x$; for example, $$g_3(x) = f(f(f(x))) - x = 2 - x - 16x^2 + 20x^4 - 8x^6 + x^8.$$

a) If $p(x)$ is a divisor of $g_n(x)$ in $\mathbb{Q}[x]$, is $p(x)$ also a divisor of $g_{kn}(x)$? Based on small numerical evidence, this seems true. For example, it seems like $(x - 2)$ and $(x + 1)$ divide all $g_n(x)$, and $(x^2 + x - 1)$ divides $g_n(x)$ for even indices, at least for small $n$. But I'm not sure how to prove it if it is even true.

b) For larger $n$, say $n = 500$, is there a fast way of determining how many irreducibles divide $g_n$, and the degree of irreducibles. For example, for $$g_4(x) = (x - 2) (x + 1) (x^2 + x - 1) (x^4 - x^3 - 4 x^2 + 4 x + 1) (x^8 + x^7 - 7 x^6 - 6 x^5 + 15 x^4 + 10 x^3 - 10 x^2 - 4 x + 1),$$ is there a way to determine, without actually factoring $g_4$, that there are five irreducible factors of $g_4$, having degrees 1, 1, 2, 4, and 8 respectively?

EDIT:

Part (a) is answered below. Part (b) is reasked (with more context) here.

byhill
  • 75

1 Answers1

2

The answer to your first question is yes.

We first apply the substitution $h(x)=(f\circ^nf)(x)$, which reduces the question to $p(x)|h(x)-x\iff p(x)|(h\circ^nh)(x)-x$.

Now, let's work modulo $p(x)$.

By our assumption, $h(x)\equiv x\pmod{p(x)}$.

We know that $h(x)\equiv g(x)\pmod{p(x)}\Rightarrow (h(x))^n\equiv (g(x))^n\pmod{p(x)}$. This is because if we write $h(x)$ as $p(x)q(x)+g(x)$, then $(h(x))^n=(p(x))^n(q(x))^n+n(p(x))^{n-1}(q(x))^{n-1}+\cdots+np(x)q(x)(g(x))^{n-1}+(g(x))^n$. All the terms before $(g(x))^n$ are divisible by $p(x)$, so $(h(x))^n\equiv (g(x))^n$.

From this, we know that $(h(x))^n\equiv x^n\pmod{p(x)}$. Then, $h(h(x))\equiv h(x)\equiv x\pmod{p(x)}$ (because $h(x)$ is just the sum of various $x^n$ times a coefficient). Hence, $p(x)|h(h(x))-x$.

We can apply induction to show that $(h\circ^nh)(x)\equiv h(x)\equiv x\pmod{p(x)}\iff p(x)|(h\circ^nh)(x)-x$.

Kyan Cheung
  • 3,184