Cycles of polynomials with integer coefficients

During work on the article “Scarcity of cycles for rational functions over a number field”, Jung Kyu Canci and I proved as a corollary that a rational function ${\phi:\mathbb{P}^1\rightarrow\mathbb{P}^1}$ defined over ${\mathbb{Q}}$ with everywhere good reduction has at most ${d+5}$ periodic points. As a special case, we remarked that a monic polynomial with integer coefficients has at most ${d+5}$ ${\mathbb{Q}}$-rational periodic points. It turns out that much better can be said, and that G. Baron proved in 1991 in an unpublished paper that such a polynomial has at most ${d+1}$ periodic points, including the point at infinity. I decided to translate the article from the original German, and bring it the mathematical community’s attention. I marked in red additions made by me. Any mistakes are probably due to my translation.

About integer polynomials with fixed points and two-cycles

Gerd Baron

Let ${P(x)}$ be an element in the polynomial ring ${R[x]}$, where ${R}$ is some commutative ring. For an element ${a\in{R}}$ one can define a sequence ${\left}$ with ${a_1 = a}$ and ${a_{n + 1} = P (a_n)}$, for ${n\geq{2}}$. A cycle is a finite sequence ${(a_1,...,a_n)}$ such that ${P(a_i)=a_{i+1}}$ for ${1\leq{i}\leq{n-1}}$ and ${P(a_n)=a_1}$. The length of a cycle ${(a_1,...,a_n)}$ is ${n}$. Over the ring ${R=\mathbb{Z}}$ we say that a cycle ${(a_1,...,a_n)}$ is integral if ${a_i\in\mathbb{Z}}$ for any ${1\leq{i}\leq{n}}$, and rational if ${a_i\in\mathbb{Q}}$ for any ${1\leq{i}\leq{n}}$.

W. Narkiewicz has shown that a polynomial ${P(x) \in \mathbb{Z}[x]}$ has no [integral] cycle of length more than two and conjectured also that [integral] cycles of length two can occur only if there is no fixed point. [In particular, since monic polynomials in ${\mathbb{Z}[x]}$ can only have integral cycles, one concludes that monic polynomials in ${\mathbb{Z}[x]}$ have rational cycles of length at most ${2}$.]

Question: Does there exist a polynomial ${P(x) \in \mathbb{Z}[x]}$, with a rational cycle of length ${>2}$?

For the sake of completeness, we give an overview of the proof of the result of Narkiewicz.

Theorem 1 Let ${P(x) \in \mathbb{Z}[x]}$ and ${a \in \mathbb{Z}}$, and define the sequence ${\left}$ with ${a_1 = a}$ and ${a_{n + 1} = P (a_n)}$. Then ${\left}$ is either (1) pairwise distinct, (2) eventually constant [i.e., ${a_n}$ = ${a_m}$ for all ${n>m}$, therefore, cycles of length 1, which are fixed points] or (3) finally alternating [i.e., ${a_{2m} \neq a_{2m + 1}}$, ${a_{2n + 1} = a_{2m + 1}}$, ${a_{2n}=a_{2m}}$ for all ${n> m}$, i.e., two-cycles].

Proof: ${a_{n+2} - a_{n+1} = P(a_{n + 1})-P(a_{n}) = (a_{n+1}-a_n)R_n}$ with ${R_n\in\mathbb{Z}}$. It follows by induction that ${a_{n + k + 1}-a_{n+k} = (a_{n + 1}-a_n)\prod{R_j}}$, where the product runs over all ${j}$ from ${n}$ to ${n + k-1}$.

1. If ${a_n = a_{n + k}}$ for a pair ${n,k}$, then ${\langle{a_n}\rangle}$ is eventually periodic.
2. In the special case ${k = 1}$ and ${a_{n+1} = a_n}$ the sequence is eventually constant.
3. If ${k> 1}$, then the following applies: ${a_{n+k+1}-a_{n + k} = a_{n+1}-a_n = a_{n+1}-a_n\prod{R_j}}$ where ${a_{n + 1}-a_n\neq{0}}$. So ${\prod R_j = 1}$ and ${R_j = \pm 1}$ for all relevant ${j}$. If all ${R_j = 1}$, then ${\sum (a_{n + j + 1} - a_{n+j}) = a_{n + k} - a_n = k(a_{n + 1}-a_n) = 0}$, a contradiction. So a ${R_j = -1}$ for some ${j}$, and ${a_{j + 2} - a_{j+1} = -(a_{j + 1} - a_{j}) = a_j - a_{j+1}}$, and therefore ${a_{j + 2} = a_j}$ and thus ${k = 2}$.

$\Box$

Corollary 2 A polynomial ${P(x) \in \mathbb{Z}[x]}$ can only have [integral] cycles of length ${2}$ (two-cycles) and ${1}$ (fixed points).

Next, we want to show that both can occur simultaneously and thus refute the conjecture by Narkiewicz.

Theorem 3 Let ${k, n}$ be natural numbers with ${2k and ${a_1, ..., a_k}$ pairwise distinct positive integers and ${R(x) \in \mathbb{Z}[x]}$ a (monic) polynomial. The (monic) polynomial ${P(x) = xR(x)\prod_{i=1}^k(x^2-a_i^2) -x}$ has the fixed point ${0}$, and the two-cycles ${(-a_i, a_i)}$, ${i\in\{1,...,k\}}$.

Corollary 4 For each ${k}$ with ${2k < n}$ there are monic polynomials in ${\mathbb{Z}[x]}$ of degree ${n}$ with ${k}$ two-cycles and a fixed point.

Theorem 5 Let ${k, n}$ be natural numbers with ${k < n}$ and ${a_1, ..., a_k}$ pairwise distinct integers other than zero and ${R(x) \in \mathbb{Z}[x]}$ a (monic) polynomial. Then the (monic) polynomial ${P(x) = xR (x) \prod_{i=1}^k (x-a_i) + x}$ has the fixed points ${0}$ and ${a_i}$, ${i\in\{1,...,k\}}$.

Corollary 6 For each ${k \leq n}$ there are monic polynomials in ${\mathbb{Z}[x]}$ of degree ${n}$ with ${k}$ fixed points.

Theorem 7 If a polynomial ${P(x) \in \mathbb{Z}[x]}$ has an [integral] two-cycle, then ${P(x)}$ has at most one fixed point.

Proof: Proof by contradiction. If ${P(x)}$ has the two-cycle ${(0, d)}$ and two distinct fixed points ${a,b}$ (in particular ${ab\neq{0}}$). Since ${P (a) = a, P (b) = b}$, the polynomial ${S(x) = P(x) -x}$ satisfies ${S(a) = S(b) = 0}$, and thus there exists a polynomial ${R(x)}$ such that ${S (x) = R(x) (x-a) (x-b)}$. Therefore ${P(x) = S(x) + x = R(x) (x-a) (x-b) + x}$. From ${P(0) = d = R(0)ab}$ it follows ${e = R (0) \neq 0, d = eab}$ and because ${0=P(d) = R(d)(d-a)(d-b) + d}$ also ${R(d)(eb-1)(ea-1) + e = 0}$. From the division chain ${e | R(d) | e}$ it therefore follows that ${ea-1 = \pm{1}}$ and ${eb-1 = \pm 1}$. Since ${ea\neq{0}}$ and ${eb\neq{0}}$ we get ${ea=eb=2}$ contradicting ${a\neq{b}}$. $\Box$

Theorem 8 If ${P(x) \in \mathbb{Z}[x]}$ has two [integral] two-cycles ${(a, b)}$ and ${(c, d)}$, then ${a + b = c + d}$.

Proof: Since ${P(a) = b}$ and ${P(b) = a}$ then the polynomial ${S(x) = P(x) + x - (a + b)}$ satisfies ${S(a) = S(b) = 0}$. Therefore there exists a polynomial ${R(x)}$ such that ${S(x) = R(x)(x-a)(x-b)}$. So ${P(x) = S(x) - x + a + b = R(x) (x-a) (x-b) - x + a + b}$. The polynomial ${Q(x) = P (P (x))}$ has the fixed points ${a, b, c, d}$. Because of the shape of ${P(x)}$, we get

$Q(x) = R (P (x)) (P (x)-a) (P (x) -b) - P (x) + a + b =$
$= R (P (x)) (R (x) (x-a) (x-b) -x + b) (R(x) (x-a) (x-b) -x + a)$
$\quad -R(x) (x-a) (x-b) + x.$

The polynomial ${Q_1 (x) = Q (x) -x}$ has the roots ${a, b, c, d}$. So ${Q_1 (x) = [R(P(x))(R(x)(x-a) -1)(R(x)(x-b) -1) -R (x)](x-a)(x-b)}$. From ${Q_1 (c) = 0}$ it follows that ${R(d)(R(c)(c-a) -1) (R(c) (c-b) -1) -R(c) = 0}$ and from ${Q_1(d) = 0}$ it follows that ${R(c)(R(d)(d-a) -1)(R(d)(d-b) -1)-R (d) = 0}$. With ${A = (R(c) (c-a) -1) (R(c) (c-b) -1) (R (d) (d-a) -1) (R (d) (d-b) -1)}$ we get ${R (d) (A-1) = R (c) (A-1) = 0}$. Thus, either both ${R(d)}$ and ${R(c)}$ are ${0}$, or ${A=1}$. From ${R (c) = R (d) = 0}$ follows ${P(c) = - c + a + b = d}$, and thus ${a + b = c + d}$ (remark that we only needed ${R(c)=0}$). If ${A = 1}$ we get ${R(c)(c-a) -1 = 1}$, etc. From ${R(c)(c-a) -1 = R(c)(c-b) -1}$ follows ${R(d)(d-a) -1 = R(d)(d-b) -1}$ and ${R(c)(a-b) = R(d)(a-b) = 0}$, so ${R(c) = R(d) = 0}$, a contradiction (as before). From ${R(c)(c-a) -1 \neq R(c)(c-b) -1}$ follows ${R (d) (d-a) -1 \neq R (d) (d-b) -1}$ and therefore each one of two expressions equal to ${-1}$. But it follows again that ${R (c) = R (d) = 0}$, a contradiction. $\Box$

Corollary 9 If ${P(x) \in \mathbb{Z}[x]}$ has the [integral] two-cycles ${(a_i,b_i)}$ (${1\leq{i}\leq{k}}$) with fixed ${c}$ such that ${a_i + b_i = c}$ for all ${1\leq{i}\leq{k}}$, then ${P(x)}$ is of the form ${ P (x) = R(x) \prod (x-a_i) (x-b_i) -x + c}$ where ${R(x) \in \mathbb{Z}[x]}$. ${P(x)}$ is monic iff ${R(x)}$ is monic.

Definition 10 Two polynomials ${P(x), Q(x) \in \mathbb{Z}[x] }$ are called equivalent [(over ${\mathbb{Z}}$)] if there exists ${f\in\mathbb{Z}}$, so that ${Q (x) = P (x + f) - f}$.

Corollary 11 If ${c}$ is even, i.e., ${(a_i + b_i) / 2 \in \mathbb{Z}[x]}$, then ${P(x)}$ is equivalent to ${R(x) \prod (x^2-\tilde{a}_i^2) -x}$ with the cycles ${(-\tilde{a}_i, \tilde{a}_i)}$, ${i\in\{1,...,k\}}$.

Proof: Take ${f=c/2}$. $\Box$

Theorem 12 If ${P(x)}$ has the [integral] two-cycle ${(a, b)}$ and the fixed point ${e}$, then ${2e = a + b}$.

Proof: Analogous to the proof of Theorem~8. $\Box$

Corollary 13 If ${P(x)}$ has the [integral] two-cycle ${(a, b)}$ with ${a + b}$ odd, then ${P(x)}$ has no [integral] fixed point.

Exactly one of the following cases occurs: (where ${P(x)}$ is monic exactly when ${R(x)}$ is monic).

• Let ${P(x)}$ have the fixed points ${a_i}$, ${i\in\{1,...,k\}}$, then ${P(x) = R(x) \prod (x-a_i) + x}$. If ${k>2}$, then ${P(x)}$ has no [integral] two-cycle.
• Let ${P(x)}$ have the ${k}$ [integral] two-cycles ${(a_i, b_i)}$, ${i\in\{1,...,k\}}$, then ${a_i + b_i = c}$ (fixed) and ${P(x) = R(x) \prod (x-a_i) (x-b_i) -x + c}$.
• If ${c}$ is even, then ${P(x)}$ is equivalent to ${Q(x) = R(x) \prod (x^2-d_i^2) -x}$ with the ${k}$ two-cycles ${(-d_i, d_i)}$, ${i\in\{1,...,k\}}$.
• If ${c}$ is odd, then ${P(x)}$ is equivalent to ${Q(x) = R(x) \prod (x^2 + x-d_i^2+d_i) -x}$ with the ${k}$ two-cycles ${(-d_i + 1, d_i)}$, ${i\in\{1,...,k\}}$.
• Let ${P(x)}$ have a fixed point ${c\in\mathbb{Z}}$ and ${k}$ [integral] two-cycles ${(a_i, b_i)}$,${i\in\{1,...,k\}}$, so that ${a_i + b_i = 2c}$, for ${i\in\{1,...,k\}}$, and ${P(x) = R(x)(x-c) \prod (x-a_i) (x-b_i) -x + 2c}$.
• ${P(x)}$ is equivalent to ${Q(x) = [R(x) \prod (x^2-d_i^2) -1]x}$ with the fixed point ${0}$ and the ${k}$ two-cycles ${(-di, di)}$.

Corollary 14 A polynomial ${P(x) \in \mathbb{Z}[x]}$ of degree ${d}$ has at most ${d}$ integral periodic points. A monic polynomial ${P(x) \in \mathbb{Z}[x]}$ of degree ${d}$ has at most ${d}$ rational periodic points.