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<a_k\right>} 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<a_k\right>} with {a_1 = a} and {a_{n + 1} = P (a_n)}. Then {\left<a_k\right>} 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 <n} 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s