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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.