# For what irreducible $f\in\mathbb{Q}[X]$ is this sequence periodic modulo $f$?

This is just an interesting problem I found in an old notebook of mine:

Given an irreducible $f\in\mathbb{Q}[X]$, is there a way to determine whether the sequence $(p_n)_{n=0}^{\infty}\subset \mathbb{Q}[X]$ given by: $$p_0=X$$ $$p_{n+1}=p_n^2-2$$ is periodic modulo $f$, without first having to determine the roots of $f$?

I've only found a way which involves finding the exact roots and that's nearly impossible for $\deg f\ge 5$.

The direct formula for $p_n$ might be useful: $$p_n=\left(\frac X2+\frac12\sqrt{X^2-4}\right)^{2^n}+\left(\frac{X}{2}-\frac12\sqrt{X^2-4}\right)^{2^n}$$

My method using the roots
For anyone interested, here's my method, which relies on finding the exact roots of $f$.

Given an irreducible polynomial $f\in\mathbb{Q}[X]$ with $f\neq X$ such that $(p_n)_{n=1}^{\infty}$ is periodic with period $d$, let $\alpha$ be a root of $f$ and define $(a_{n})_{n=1}^{\infty}$ by: $$a_n=p_n(\alpha)$$ We can also define $(a_{n})_{n=1}^{\infty}$ by: $$a_0=\alpha$$ $$a_{n+1}=a_n^2-2$$ and if we take $\beta$ with $\alpha=\beta+\beta^{-1}$, then it can easily be shown via induction that $$a_n=\beta^{2^n}+\beta^{-2^n}$$ Suppose $|\beta|\neq 1$. If $|\beta|<1$, exchange $\beta$ and $\beta^{-1}$, so we can be sure that $|\beta|>1$ and $|\beta^{-1}|<1$. It follows that: $$|\alpha|=\lim_{k\to\infty} |a_{kd}|=\lim_{k\to\infty}|\beta^{2^{kd}}+\beta^{-2^{kd}}|=\infty$$ Which is a contradiction. Therefore, $\beta=e^{i\gamma}$ for some $\gamma\in\mathbb{R}$ and: $$a_n=e^{i\gamma n}+e^{-i\gamma n}=2\cos(\gamma n)$$ Which is only periodic if $\gamma$ is a rational multiple of $2\pi$. The only $f$ we have't checked is $f=X$, but it is easily seen that $p_n\equiv 2\pmod X$ for all $n$. So $(p_n)_{n=1}^{\infty}$ can only be periodic modulo $f$ when all the roots of $f$ are of the form: $$2\cos\left(\frac{2\pi p}{q}\right)$$ for some $p/q\in\mathbb{Q}$.

On the other hand, if for some $p/q\in\mathbb{Q}$ we take $$\alpha:=2\cos\left(\frac{2\pi p}{q}\right)$$ Then we can define $(a_n)_{n=1}^{\infty}$ as before and show it's periodic, say with period $d$. For all $k,m$, we now have: $$p_k(\alpha)=p_{k+md}(\alpha)\implies (p_{k+md}-p_k)(\alpha)=0$$ and since for $m\neq 0$, we have $\deg p_k\neq \deg p_{k+md}$, it follows that $f^{\alpha}_{\mathbb{Q}}\mid p_{k+md}-p_k$.

This implies that all such $\alpha$ are algebraïc over $\mathbb{Q}$ and if a monic irreducible $f\in\mathbb{Q}[X]$ has just one root of the form $$2\cos\left(\frac{2\pi p}{q}\right)$$ then all of its roots are of this form (because it's a unity times $f^{\alpha}_{\mathbb{Q}}$, the sequence is periodic modulo $f^\alpha_{\mathbb{Q}}$ and can only be periodic if all roots are of this form.

Well, using the criterion you have found, you can just check whether $$f$$ is the minimal polynomial of $$2\cos\left(\frac{2\pi p}{q}\right)$$ for any $$p/q\in\mathbb{Q}$$. If $$p/q$$ is in lowest terms, then the Galois conjugates of $$2\cos\left(\frac{2\pi p}{q}\right)$$ are all the numbers of the form $$2\cos\left(\frac{2\pi p'}{q}\right)$$ where $$p'/q$$ is in lowest terms. Note that $$x+1/x=2\cos\left(\frac{2\pi p}{q}\right)$$ iff $$x=e^{\pm 2\pi i p/q}$$, so if $$f$$ is the minimal polynomial of $$2\cos\left(\frac{2\pi p}{q}\right)$$, then $$g(x)=x^{\deg f}f(x+1/x)$$ has exactly the primitive $$q$$th roots of unity as its roots, so it is the $$q$$th cyclotomic polynomial. Conversely, if $$g$$ is the $$q$$th cyclotomic polynomial, then we see that $$2\cos\left(\frac{2\pi p}{q}\right)$$ is a root of $$f$$.
So, a necessary and sufficient condition for your sequence to be periodic mod $$f$$ is for $$g$$ to be a cyclotomic polynomial. To test this, you can just compute the cyclotomic polynomials $$\Phi_q$$ for all the finitely many values of $$q$$ such that $$\varphi(q)=\deg g=2\deg f$$ (see Only finitely many $n$ such that $\phi(n) = m$ for how to find those finitely many values of $$q$$) and see whether any of them are equal to $$g$$.