Newton, Fermat, and Exactly Realizable Sequences

Bau-Sen Du Institute of Mathematics

Academia Sinica Taipei 115 TAIWAN

mabsdu@sinica.edu.tw

Sen-Shan Huang and Ming-Chia Li

Department of Mathematics National Changhua University of Education

Changhua 500

TAIWAN

shunag@math.ncue.edu.tw
mcli@math.ncue.edu.tw

Abstract

In this note, we study intimate relations among the Newton, Fermat and exactly realizable sequences, which are derived from Newton’s identities, Fermat’s congruence identities, and numbers of periodic points for dynamical systems, respectively.

1 Introduction

Consider a set S of all sequences with complex numbers, let I be the subset of S consisting of sequences containing only integers, and let I_{+} be the subset of I containing only sequences with nonnegative integers. We shall define two operators

N : S → S and F : S → S, called Newton and Fermat operators, and we call each element of N(S) a Newton sequence and each element of F (S) a Fermat sequence; this terminology is motivated by Newton identities and by Fermat’s Little Theorem, details of which are given below. The key questions investigated in this note are as follows: What is N(I_{+})? What are N(I) and F (I)? What are the relations between various Newton and Fermat sequences?

In Theorem 2, we observe that N(I) = F (I); this was earlier obtained by us in [4] but here another proof is provided due to D. Zagier.

Further, we investigate sequences attached to some maps and their period-n points. Let M denote a set of some maps which will be specialized later. We shall construct a natural operator E : M → I_{+} and call each element of E(M) an exactly realizable sequence.

In Theorem 3, we show that E(M) = F (I_{+}) ⊂ N(I) and for any {a_{n}} ∈ E(M), we construct a formula for {c_{n}} ∈ I such that N({c_{n}}) = {a_{n}}. In Theorem 4, we show that N(I_{+}) ⊂ E(M) and N(I) is equal to the set of term-by-term differences of two elements in E(M). We also investigate when a Newton sequence is an exactly realizable sequence in a special case.

2 Newton’s Identities

In this note, we work entirely with sequences in ℂ, but one could work with more general fields. In particular, Newton’s identities below are valid in any field.

Newton’s identities were first stated by Newton in the 17th century. Since then there have appeared many proofs, including recent articles [8] and [9]. For reader’s convenience, we give a simple proof using formal power series based on [1, p. 212]; also refer to [3].

Theorem 1 (Newton’s identities). Let x^{k} − ∑_{j=0}^{k−1} c_{k−j}x^{j} be a polynomial in ℂ[x] with zeros λ_{j} for 1 ≤ j ≤ k and let a_{n} = ∑_{j=1}^{k} λ_{j}^{n} for n ≥ 1 and c_{n} = 0 for n > k. Then a_{n} = ∑_{j=1}^{n−1} a_{n−j}c_{j} + nc_{n} for all n ≥ 1.

Proof. By writing x^{k} − ∑_{j=0}^{k−1} c_{k−j}x^{j} = ∏_{j=1}^{k}(x − λ_{j}) and replacing x by 1/x, we obtain 1 − ∑_{j=1}^{k} c_{j}x^{j} = ∏_{j=1}^{k}(1 − λ_{j}x). Then the formal power series

∑_{n=1}^{∞} a_{n}x^{n} = ∑_{n=1}^{∞}(∑_{j=1}^{k} λ_{j}^{n})x^{n} = ∑_{j=1}^{k}(∑_{n=1}^{∞}(λ_{j}x)^{n}) = ∑_{j=1}^{k} \frac{λ_{j}x}{1 − λ_{j}x}

= −x \frac{\frac{d}{dx}(∏_{j=1}^{k}(1 − λ_{j}x))}{∏_{j=1}^{k}(1 − λ_{j}x)} = −x \frac{\frac{d}{dx}(1 − ∑_{j=1}^{k} c_{j}x^{j})}{1 − ∑_{j=1}^{k} c_{j}x^{j}}

= \frac{∑_{j=1}^{k} jc_{j}x^{j}}{1 − ∑_{j=1}^{k} c_{j}x^{j}}

and hence ∑_{n=1}^{∞} a_{n}x^{n} = (∑_{n=1}^{∞} a_{n}x^{n})(∑_{j=1}^{k} c_{j}x^{j}) + ∑_{j=1}^{k} jc_{j}x^{j}. By comparing coefficients and the assumption c_{j} = 0 for j > k, we have a_{n} = ∑_{j=1}^{n−1} a_{n−j}c_{j} + nc_{n} for all n ≥ 1.

Based on Newton’s identities, it is natural to give the following definition: for a sequence {c_{n}} in ℂ, the Newton sequence generated by {c_{n}} is defined to be {a_{n}} by a_{n} = ∑_{j=1}^{n−1} a_{n−j}c_{j} + nc_{n} inductively for n ≥ 1. In this case, we define the Newton operator N by N({c_{n}}) = {a_{n}}.

Fermat’s little theorem states that given an integer a, we have that p|a^{p} − a for all primes p. In order to state its generalization, we use the following terminology: for a sequence {b_{n}} in ℂ, the Fermat sequence generated by {b_{n}} is defined to be {a_{n}} by a_{n} = ∑_{m|n} mb_{m} for n ≥ 1; in this case, we define the Fermat operator F by F ({b_{n}}) = {a_{n}}. If {a^{n}} is an integral Fermat sequence generated by {b_{n}} and if p is any prime, then pb_{p} = a^{p} − a and hence b_{p} ∈ ℤ; this observation inspires the name Fermat Sequence. By the Möbius inversion formula (refer to [10]), we have that if {a_{n}} is the Fermat sequence generated by {b_{n}}, then nb_{n} = ∑_{m|n} μ(m)a_{n/m} and if, in addition, {b_{n}} is an integral sequence, then n| ∑_{m|n} μ(m)a_{n/m}, where μ is the Möbius function, i.e., μ(1) = 1, μ(m) = (−1)^{k} if m is a product of k distinct prime numbers, and μ(m) = 0 otherwise. (In [4], we called {a_{n}} a generalized Fermat sequence if a_{n} is an integer and n| ∑_{m|n} μ(m)a_{n/m} for every n ≥ 1; now it is the Fermat sequence generated by an integral sequence.)

Fermat sequences of the form {a^{n}} are related to both free Lie algebras and the number of irreducible polynomials over a given finite field. Indeed, let X be a finite set of cardinality a and let L_{X} be a free Lie algebra on X over some field 𝔽. For any given n ∈ ℕ let L_{X}^{n} be its nth homogeneous part and let ℓ_{a}(n) be the rank of L_{X}^{n}. Then

a^{n} = ∑_{m|n} mℓ_{a}(m) for all n ∈ ℕ

which shows that {a^{n}} is the Fermat sequence generated by {ℓ_{a}(n)} (See [12] and [7, Section 4 of Chapter 4]). Further, let 𝔽_{q} be a finite field with q elements and let N_{q}(n) be the number of monic irreducible polynomials in 𝔽_{q}[X] of degree n. Then

q^{n} = ∑_{m|n} mN_{q}(m).

Hence {q^{n}} is the Fermat sequence generated by {N_{q}(n)}.

In [4], we show that a sequence is a Newton sequence generated by integers if and only if it is a Fermat sequence generated by integers, by using symbolic dynamics. Here we give another proof using formal power series pointed out by Zagier [13] to us; also refer to [2].

Theorem 2. Let {a_{n}}, {b_{n}} and {c_{n}} be sequences in ℂ. Then

1. {a_{n}} is the Newton sequence generated by {c_{n}} if and only if

exp (− ∑_{n=1}^{∞} a_{n} \frac{x^{n}}{n} ) = 1 − ∑_{n=1}^{∞} c_{n}x^{n} as formal power series;

2. {a_{n}} is the Fermat sequence generated by {b_{n}} if and only if

exp (− ∑_{n=1}^{∞} a_{n} \frac{x^{n}}{n} ) = ∏_{n=1}^{∞}(1 − x^{n})^{b_{n}} as formal power series;

3. {a_{n}} is the Newton sequence generated by an integral sequence if and only if {a_{n}} is the Fermat sequence generated by an integral sequence. That is, N(I) = F (I), where I is the set of all integral sequences.

Proof. For convenience, we define formal power series A(x) = ∑_{n=1}^{∞} a_{n}x^{n}, C(x) = ∑_{n=1}^{∞} c_{n}x^{n}, F (x) = exp (− ∑_{n=1}^{∞} a_{n}x^{n}/n), and H(x) = ∏_{m=1}^{∞}(1 − x^{m})^{b_{m}}.

We prove item 1 as follows. By comparing coefficients and using the trivial fact A(x) = −x\frac{d}{dx} log F (x), we have that a_{n} = ∑_{j=1}^{n−1} a_{n−j}c_{j} + nc_{n} for all n ≥ 1 ⇔ A(x) = C(x)A(x) + xC′(x) ⇔ A(x) = x\frac{C′(x)}{1−C(x)} = −x\frac{d}{dx} log(1 − C(x)) ⇔ F (x) = 1 − C(x). (Observe that 1 = F (0) = 1 − C(0)).

We prove item 2 as follows. By rearranging terms of x^{n} and using the fact that H(x) = exp (− ∑_{m=1}^{∞} b_{m} ∑_{r=1}^{∞} x^{rm}/r), we have that a_{n} = ∑_{m|n} mb_{m} for all n ≥ 1 ⇔ F (x) = exp (− ∑_{m=1}^{∞} b_{m} ∑_{r=1}^{∞} x^{rm}/r) = H(x).

¿From the proof of items 1 and 2, {b_{n}} and {c_{n}} are both uniquely determined by {a_{n}} such that {a_{n}} is the Newton sequence generated by {c_{n}} and also the Fermat sequence generated by {b_{n}}. Then 1 − ∑_{n=1}^{∞} c_{n}x^{n} = F (x) = ∏_{n=1}^{∞}(1 − x^{n})^{b_{n}}. Therefore, item 3 follows since c_{n} ∈ ℤ for all n ≥ 1 ⇔ F (x) ∈ 1 + xℤ[x] ⇔ b_{n} ∈ ℤ for all n ≥ 1.

3 Connections with Dynamical Systems

In the following, we make a connection between the above number theoretical result with dynamical systems. Let f be a map from a set S into itself. For n ≥ 1, let f^{n} denote the composition of f with itself n times. A point x ∈ S is called a period-n point for f if f^{n}(x) = x and f^{j}(x) ≠ x for 1 ≤ j ≤ n − 1. Let Per_{n}(f) denote the set of all period-n points for f and let #Per_{n}(f) denote the cardinal number of Per_{n}(f) if Per_{n}(f) is finite. Let a be any period-n point for f. Then a, f(a), …, f^{n−1}(a) are distinct period-n points and hence n|#Per_{n}(f). Since #Per_{1}(f^{n}) = ∑_{m|n} #Per_{m}(f), the sequence {#Per_{1}(f^{n})} is the Fermat sequence generated by the sequence {#Per_{n}(f)/n}.

Following [5], we say that a nonnegative integral sequence {a_{n}} is exactly realizable if there is a map f from a set into itself such that #Per_{1}(f^{n}) = a_{n} for all n ≥ 1; in this case, we write E(f) = {a_{n}}. Let M be the set of maps f for which Per_{n}(f) is nonempty and finite, and let I_{+} be the set of all nonnegative integral sequences. Then E is an operator from M to I_{+}. Exact realizability can be characterized as follows.

Theorem 3. Let {a_{n}} be a sequence in ℂ. Then the following three items are equivalent:

1. {a_{n}} is exactly realizable;

2. there exists a nonnegative integral sequence {b_{n}} such that {a_{n}} is the Fermat sequence generated by {b_{n}}, that is, F ({b_{n}}) = {a_{n}};

3. there exists a nonnegative integral sequence {d_{n}} such that {a_{n}} is the Newton sequence generated by an integral sequence {c_{n}} with for all n ≥ 1,

c_{n} = ∑_{k_{1}+2k_{2}+···+nk_{n}=n}(−1)^{k_{1}+k_{2}+···+k_{n}+1} (\begin{matrix}d_{1} \\ k_{1} \end{matrix}) (\begin{matrix}d_{2} \\ k_{2} \end{matrix}) ⋯ (\begin{matrix}d_{n} \\ k_{n} \end{matrix})

where (\begin{matrix}p \\ q \end{matrix}) denotes a binomial coefficient; that is, N(\{c_{n}\}) = \{a_{n}\}.

Moreover, if the above items hold then b_{n} = d_{n} for all n ≥ 1.

Proof. (1 ⇒ 2) Let f be a function such that #Per_{1}(f^{n}) = a_{n} for all n ≥ 1 and let b_{n} = #Per_{n}(f)/n for all n ≥ 1. Then {b_{n}} is nonnegative and integral, and a_{n} = ∑_{m|n} mb_{m} for all n ≥ 1.

(1 ⇐ 2) By permutation, we can define f : ℕ → ℕ by that the first b_{1} integers are period-1 points, the next 2b_{2} integers are period-2 points, the next 3b_{3} are period-3 points, and so on. Then mb_{m} = #Per_{m}(f) for all m ≥ 1 and hence a_{n} = ∑_{m|n} mb_{m} = #Per_{1}(f^{n}) for all n ≥ 1. Therefore, {a_{n}} is exactly realizable.

(2 ⇔ 3) By using item 3 of Theorem 2 and letting d_{n} = b_{n} for all n ≥ 1, it remains to verify the expressions of c_{n}’s. From items 1 and 2 of Theorem 2, we have 1 − ∑_{n=1}^{∞} c_{n}x^{n} = ∏_{n=1}^{∞}(1 − x^{n})^{d_{n}}. Equating the coefficients of x^{n} on both sides, we obtain the desired result.

The last statement of the theorem is a by-product from the proof of (2 ⇔ 3).

Let {a_{n}} be the Newton sequence generated by {c_{n}}. For exact realizability of {a_{n}}, it is not necessary that all of c_{n}’s are nonnegative. For example, the exactly realizable sequence {2, 2, 2, ⋯ }, which is derived from a map with only two period-1 points and no other periodic points, is the Newton sequence generated by {c_{n}} with c_{1} = 2, c_{2} = −1 and c_{n} = 0 for n ≥ 3. Nevertheless, the nonnegativeness of all c_{n}’s is sufficient for exact realizability of {a_{n}} as follows.

Theorem 4. The following properties hold.

1. Every Newton sequence generated by a nonnegative integral sequence is exactly realizable, that is, N(I_{+}) ⊂ E(M).

2. Every Newton sequence generated by an integral sequence is a term-by-term difference of two exactly realizable sequences, and vice versa.

Before proceeding with the proof, we recall some basic definitions in symbolic dynamics; refer to [6, 11]. A graph G consists of a countable (resp. finite) set S of states together with a finite set E of edges. Each edge e ∈ E has initial state i(e) and terminal state t(e). Let A = [A_{IJ}] be a countable (resp. finite) matrix with nonnegative integer entries. The graph of A is the graph G_{A} with state set S and with A_{IJ} distinct edges from edge set E with initial state I and terminal state J. The edge shift space Σ_{A} is the space of sequences of edges from E specified by

Σ_{A} = {e_{0}e_{1}e_{2} ⋯ |e_{j} ∈ E and t(e_{j}) = i(e_{j+1}) for all integers j ≥ 0}.

The shift map σ_{A} : Σ_{A} → Σ_{A} induced by A is defined to be

σ_{A}(e_{0}e_{1}e_{2}e_{3} ⋯) = e_{1}e_{2}e_{3} · · · .

Now we prove Theorem 4.

Proof. First we prove item 1. Let {a_{n}} be the Newton sequence generated by a nonnegative integral sequence {c_{n}}. Define a countable matrix A = [A_{IJ}] with countable states S = ℕ by A_{IJ} to be c_{J} if I = 1 and J ≥ 1, one if I = J + 1 and J ≥ 1, and zero otherwise. Let σ_{A} be the shift map induced by A. Then a_{n} = trace(A^{n}) = #Per_{1}(σ_{A}^{n}) for all n ≥ 1. Therefore {a_{n}} is exactly realizable.

Next we prove the forward part of item 2. Let {a_{n}} be the Newton sequence generated by an integral sequence \{c_{n}\}. Setting b_{n} = \frac{1}{n} ∑_{m|n} μ(m)a_{n/m} for all n ≥ 1, Theorem 2 implies that {a_{n}} is a Fermat sequence generated by {b_{n}} and each b_{n} is an integer. Let b_{n}^{+} = max(b_{n}, 0) and b_{n}^{−} = max(−b_{n}, 0) for n ≥ 1. Then b_{n}^{+} ≥ 0, b_{n}^{−} ≥ 0 and b_{n} = b_{n}^{+} − b_{n}^{−} for all n ≥ 1. Setting a_{n}^{+} = ∑_{m|n} mb_{m}^{+} and a_{n}^{−} = ∑_{m|n} mb_{m}^{−}, it follows from Theorem 3 that {a_{n}^{+}} and {a_{n}^{−}} are both exactly realizable sequences. Moreover, a_{n} = ∑_{m|n} mb_{m} = ∑_{m|n} m(b_{m}^{+} − b_{m}^{−}) = a_{n}^{+} − a_{n}^{−} for all n ≥ 1.

Finally we prove the backward part of item 2. By Theorem 3, we have that every exactly realizable sequence is the Fermat sequence generated by a nonnegative integral sequence. It is obvious that the term-by-term difference of two Fermat sequences is a Fermat sequence. These facts, together with item 3 of Theorem 2, imply the desired result.

4 Formal Power Series

Combining the theorems above, we have the following result on formal power series.

Corollary 5. Let {b_{n}} and {c_{n}} be two sequences in ℂ such that 1−∑_{n=1}^{∞} c_{n}x^{n} = ∏_{n=1}^{∞}(1− x^{n})^{b_{n}} as formal power series. If {c_{n}} is a nonnegative integral sequence then so is {b_{n}}.

Proof. Let {a_{n}} be the Newton sequence generated by {c_{n}}. By items 1 and 2 of Theorem 2, the sequence {a_{n}} is the Fermat sequence generated by {b_{n}}. By item 1 of Theorem 4, the sequence {a_{n}} is exactly realizable such that a_{n} = #Per_{1}(f^{n}) for some map f. Therefore, we have that b_{n} = ∑_{m|n} μ(m)a_{n/m} = #Per_{n}(f)/n ≥ 0 for all n ≥ 1.

Finally, we give a criterion of exact realizability for the Newton sequence generated by {c_{n}} with c_{n} = 0 for all n ≥ 3.

Corollary 6. Let {a_{n}} be the Newton sequence generated by a sequence {c_{n}} with c_{n} = 0 for all n ≥ 3. Then {a_{n}} is exactly realizable if and only if c_{1} and c_{2} are both integers with c_{1} ≥ 0 and c_{2} ≥ −c_{1}^{2}/4.

Proof. First we prove the “if” part. If c_{1} is even, we define a matrix A = [\begin{matrix}c_{1}/2 & c_{1}^{2}/4 + c_{2} \\ 1 & c_{1}/2 \end{matrix}].

Then A is a nonnegative integral matrix and a_{n} = trace(A^{n}) = #Per_{1}(σ_{A}^{n}), where σ_{A} is the shift map induced by A (see the proof of Theorem 4 with two states). Therefore, {a_{n}} is exactly realizable. Similarly, if c_{1} is odd, then c_{2} ≥ −c_{1}^{2}/4 + 1/4 because c_{2} is an integer, and

hence \{a_{n}\} is exactly realizable with respect to σ_{A}, where A = [\begin{matrix}(c_{1} + 1)/2 & (c_{1}^{2} − 1)/4 + c_{2} \\ 1 & (c_{1} − 1)/2 \end{matrix}].

Next we prove the “only if” part. Since {a_{n}} is exactly realizable, c_{1} = a_{1} ≥ 0 is an integer, c_{2} = (a_{2} − a_{1})/2 − c_{1}(c_{1} − 1)/2 is an integer, and a_{n} = trace(A^{n}) ≥ 0 for all n ≥ 1, where A = [\begin{matrix}c_{1}/2 & c_{1}^{2}/4 + c_{2} \\ 1 & c_{1}/2 \end{matrix}]. Suppose, on the contrary, that c_{2} = −c_{1}^{2}/4 − α for some α > 0. Let B = [\begin{matrix}c_{1}/2 & −\sqrt{α} \\ \sqrt{α} & c_{1}/2 \end{matrix}]. Then B has the same characteristic polynomial as A and hence a_{n} = trace(A^{n}) = trace(B^{n}) for all n ≥ 1. Let r = \sqrt{c_{1}^{2}/4 + α} and pick 0 < θ ≤ π/2 so that r cos θ = c_{1}/2 and r sin θ = \sqrt{α}. Then B^{n} = [\begin{matrix}r^{n} cos nθ & −r^{n} sin nθ \\ r^{n} sin nθ & r^{n} cos nθ \end{matrix}] and a_{n} = 2r^{n} cos nθ for all n ≥ 1. This contradicts that a_{n} ≥ 0 for all n ≥ 1. Therefore, c_{2} ≥ −c_{1}^{2}/4.

Acknowledgments: We would like to thank Professor D. Zagier for his invaluable suggestions which lead to the formulation of Theorem 2 and are also grateful to the referee for helpful suggestions which have improved the presentation of this note.

References

[1] E. Berlekamp, Algebraic Coding Theory, MacGraw Hill Book Co., New York, 1968.

[2] L. Carlitz, Note on a paper of Dieudonne, Proc. Amer. Math. Soc. 9 (1958), 32–33.

[3] B.-S. Du, The linearizations of cyclic permutations have rational zeta functions, Bull. Austral. Math. Soc. 62 (2000), 287–295.

[4] B.-S. Du, S.-S. Huang, and M.-C. Li, Genralized Fermat, double Fermat and Newton sequences, J. Number Theory 98 (2003), 172–183.

[5] G. Everest, A. J. van der Poorten, Y. Puri, and T. Ward, Integer sequences and periodic points, J. Integer Seq. 5 (2002), Article 02.2.3, 10 pp.

[6] B. P. Kitchens, Symbolic Dynamics: One-sided, Two-sided and Countable State Markov Shifts, Springer-Verlag, Berlin, 1998.

[7] R. Lidl and H. Niederreiter, Finite Fields, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge, 1997.

[8] D. G. Mead, Newton’s identities, Amer. Math. Monthly 99 (1992), 749–751.

[9] J. Mináč, Newton’s identities once again, Amer. Math. Monthly 110 (2003), 232–234.

[10] I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers, fifth ed., Wiley, New York, 1991.

[11] C. Robinson, Dynamical Systems: Stability, Symbolic Dynamics, and Chaos, 2nd ed., Studies in Advanced Mathematics, CRC Press, Boca Raton, FL, 1999.

[12] J.-P. Serre, Lie Algebra and Lie Groups, Lectures given at Harvard University, 1964, W.A.Benjamin, Inc., New York-Amsterdam, 1965.

[13] D. Zagier, private communication by email, 2003.

2000 Mathematics Subject Classification: Primary 11B83; Secondary 11B50, 37B10 . Keywords: Newton sequence, Fermat sequence, exactly realizable sequence, symbolic dynamics.

Received June 1 2004; revised version received October 20 2004. Published in Journal of Integer Sequences, January 12 2005.

Return to Journal of Integer Sequences home page.