\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{amsthm}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf Newton, Fermat, and Exactly Realizable Sequences}
\vskip 1cm
\large
Bau-Sen Du \\
Institute of Mathematics \\
Academia Sinica \\
Taipei 115 \\
TAIWAN \\
\href{mailto:mabsdu@sinica.edu.tw}{\tt mabsdu@sinica.edu.tw} \\
\ \\
Sen-Shan Huang and Ming-Chia Li \\
Department of Mathematics \\
National Changhua University of Education\\
Changhua 500 \\
TAIWAN \\
\href{mailto:shunag@math.ncue.edu.tw}{\tt shunag@math.ncue.edu.tw} \\
\href{mailto:mcli@math.ncue.edu.tw}{\tt mcli@math.ncue.edu.tw} \\
\end{center}
\vskip .2in
\begin{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.
\end{abstract}
\vskip .2in
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
% \usepackage{amsthm,amsmath,amssymb,amscd,verbatim}
%\textwidth=15.5cm
%\textheight=24cm
%\addtolength{\topmargin}{-3.5pc}
%\addtolength{\oddsidemargin}{-2.5pc}%{-7pc} for 10pt
%\setlength{\evensidemargin}{\oddsidemargin}
%\input amssym.def
%\newtheorem{definition}{Definition}
%\renewcommand{\thedefinition}{}
%\newtheorem{theorem}[definition]{Theorem}
%\renewcommand{\thetheorem}{}
%\newtheorem{corollary}[definition]{Corollary}
%\newtheorem{lemma}[definition]{Lemma}
%\newtheorem{proposition}[definition]{Proposition}
%\newtheorem{method}{Method}
%\newtheorem{application}{Application}
%\newtheorem{notation}{Notation}
%\newtheorem{fact}{Fact}
%\newtheorem{remark}[definition]{Remark}
%\newtheorem{example}{Example}
%\newtheorem{problem}{Problem}
%\newtheorem{question}{Question}
%\newtheorem{note}{Note}
%\newtheorem{exercise}{Exercise}
%\newtheorem{recall}{Recall}
%\input{latex2etheoremstyle}
\section{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
\begin{equation*}
N:S\to S\mbox{ and }F:S\to S,
\end{equation*} 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~\cite{DuHuangLi2003}
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 \to I_+$ and call each element of $E(M)$ an exactly realizable sequence.
In Theorem~3, we show that $E(M)=F(I_+)\subset N(I)$ and for any $\{a_n\}\in E(M)$, we construct a
formula for $\{c_n\}\in I$ such that $N(\{c_n\})=\{a_n\}$. In Theorem~4, we show that
$N(I_+)\subset 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.
\section{Newton's Identities}
In this note,
we work entirely with sequences in ${\mathbb C}$, 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 \cite{Mead1992} and \cite{Minac2003}. For reader's
convenience, we give a simple proof using formal power series based on \cite[p.
212]{Berlekamp1968}; also refer to~\cite{Du2000bams}.
\begin{theorem}[Newton's identities]\label{Newton}
Let $x^k-\sum_{j=0}^{k-1}c_{k-j}x^j$ be a polynomial in ${\mathbb C} [x]$ with zeros $\lambda_j$
for $ 1\leq j\leq k$ and let $a_n=\sum_{j=1}^k \lambda_j^n$ for $n\geq 1$ and $c_n=0$ for $n>k$.
Then $a_n=\sum_{j=1}^{n-1} a_{n-j}c_j +nc_n$ for all $n\geq 1$.
\end{theorem}
\begin{proof}
By writing $x^k- \sum_{j=0}^{k-1} c_{k-j} x^j = \prod_{j=1}^k (x - \lambda_j)$ and replacing $x$
by $1/x$, we obtain $1 - \sum_{j=1}^k c_j x^j = \prod_{j=1}^k (1 - \lambda_jx)$. Then the formal
power series
\begin{align*}
\sum_{n=1}^\infty a_nx^n &=\sum_{n=1}^\infty \biggl(\sum_{j=1}^k \lambda_j^n \biggr) x^n =
\sum_{j=1}^k \biggl(
\sum_{n=1}^\infty (\lambda_jx)^n \biggr)= \sum_{j=1}^k \frac
{\lambda_jx}{1 - \lambda_jx} \\
&=-x \frac {\frac d{dx} \biggl( \prod_{j=1}^k (1-\lambda_jx) \biggr)}{ \prod_{j=1}^k
(1-\lambda_jx)} =-x \frac {\frac d{dx} \biggl( 1 - \sum_{j=1}^k c_j x^j \biggr)}{ 1 -
\sum_{j=1}^k c_j x^j} \\
&=\frac {\sum_{j=1}^k jc_j x^j}{ 1 - \sum_{j=1}^k c_j x^j}
\end{align*}
and hence $\sum_{n=1}^\infty a_nx^n=(\sum_{n=1}^\infty a_nx^n)(\sum_{j=1}^k c_j x^j)+\sum_{j=1}^k
jc_j x^j.$ By comparing coefficients and the assumption $c_j=0$ for $j>k$, we have $a_n=
\sum_{j=1}^{n-1} a_{n-j}c_j +nc_n$ for all $n\geq 1$.
\end{proof}
Based on Newton's identities, it is natural to give the following definition: for a sequence
$\{c_n\}$ in ${\mathbb C}$, the {\em Newton sequence} generated by $\{c_n\}$ is defined to be
$\{a_n\}$ by $a_n=\sum_{j=1}^{n-1} a_{n-j}c_j +nc_n$ inductively for $n\geq 1$. In this case, we
define the {\em Newton operator N} by $N(\{c_n\})=\{a_n\}$.
{\em 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 ${\mathbb C}$, the {\em Fermat sequence} generated by $\{b_n\}$ is defined to be
$\{a_n\}$ by $a_n=\sum_{m|n}mb_m$ for $n\geq 1$; in this case, we define the {\em 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 $p b_p=a^p-a$ and hence $b_p\in{\mathbb Z}$; this observation
inspires the name \textit{Fermat Sequence}. By the M\"{o}bius inversion formula (refer
to~\cite{NivenZuckermanMontgomery1991}), we have that if $\{a_n\}$ is the Fermat sequence generated
by $\{b_n\}$, then $nb_n=\sum_{m|n}\mu(m)a_{n/m}$ and if, in addition, $\{b_n\}$ is an integral
sequence, then $n|\sum_{m|n}\mu(m)a_{n/m}$, where $\mu$ is the M\"{o}bius function, i.e.,
$\mu(1)=1$, $\mu(m)=(-1)^k$ if $m$ is a product of $k$ distinct prime numbers, and $\mu(m)=0$
otherwise. (In \cite{DuHuangLi2003}, we called $\{a_n\}$ a {\em generalized Fermat sequence} if
$a_n$ is an integer and $n|\sum_{m|n}\mu(m)a_{n/m}$ for every $n\geq 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 ${\mathbb F}$. For any given
$n\in{\mathbb N}$ let $L_X^n$ be its $n$th homogeneous part and let $\ell_a(n)$ be the rank of
$L_X^n$. Then
\begin{equation*}
a^n=\sum_{m|n}m\ell_a(m)\mbox{ for all }n\in{\mathbb N}
\end{equation*}
which shows that
%\begin{equation*}
$\{a^n\}\mbox{ is the Fermat sequence generated by }
\{\ell_a(n)\}$
%\end{equation*}
(See \cite{Serre1965} and \cite[Section 4 of Chapter 4]{LidlNiederreiter1997}). Further, let
${\mathbb F}_q$ be a finite field with $q$ elements and let $N_q(n)$ be the number of monic
irreducible polynomials in ${\mathbb F}_q[X]$ of degree $n$. Then
\begin{equation*}
q^n=\sum_{m|n}m N_q(m).
\end{equation*}
Hence $\{q^n\}$ is the Fermat sequence generated by $\{N_q(n)\}$.
In \cite{DuHuangLi2003}, 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~\cite{Zagier2003} to us; also refer
to~\cite{Carlitz1958}.
\begin{theorem}\label{NewtonFermat}
Let $\{a_n\}, \{b_n\}$ and $\{c_n\}$ be sequences in ${\mathbb C}$. Then
\begin{enumerate}
\item $\{a_n\}$ is the Newton sequence generated by $\{c_n\}$ if and only if
$$\exp \left(-\sum_{n=1}^\infty a_n\frac{x^n}{n}\right)=1-\sum_{n=1}^\infty
c_nx^n\quad \text{as formal power series};$$ \item $\{a_n\}$ is the Fermat sequence generated by
$\{b_n\}$ if and only if
$$\exp \left(-\sum_{n=1}^\infty a_n\frac{x^n}{n}\right)=\prod_{n=1}^\infty
(1-x^n)^{b_n}\quad \text{as formal power series};
$$
\item $\{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.
\end{enumerate}
\end{theorem}
\begin{proof}
For convenience, we define formal power series $A(x)=\sum_{n=1}^\infty a_nx^n$,
$C(x)=\sum_{n=1}^\infty c_nx^n$, $F(x)=\exp \left(-\sum_{n=1}^\infty a_n{x^n}/{n}\right)$, and
$H(x)=\prod_{m=1}^\infty (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=\sum_{j=1}^{n-1} a_{n-j}c_j +nc_n$ for all $n\geq
1$ $\Leftrightarrow$ $A(x)=C(x)A(x)+xC^\prime(x)$ $\Leftrightarrow$
$A(x)=x\frac{C^\prime(x)}{1-C(x)}=-x\frac{d}{dx}\log(1-C(x))$ $\Leftrightarrow$ $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\left(-\sum_{m=1}^\infty b_m\sum_{r=1}^\infty {x^{rm}}/{r}\right)$, we have that
$a_n=\sum_{m|n}mb_m$ for all $n\geq 1$ $\Leftrightarrow$ $F(x)=\exp\left(-\sum_{m=1}^\infty
b_m\sum_{r=1}^\infty {x^{rm}}/{r}\right)=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-\sum_{n=1}^\infty c_nx^n=F(x)=\prod_{n=1}^\infty (1-x^n)^{b_n}.$
Therefore, item 3 follows since $c_n\in {\mathbb Z}$ for all $n\geq 1$ $\Leftrightarrow$ $F(x)\in
1+x{\mathbb Z}[x]$ $\Leftrightarrow$ $b_n\in {\mathbb Z}$ for all $n\geq 1$.
\end{proof}
\section{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\geq 1$, let $f^n$ denote the
composition of $f$ with itself $n$ times. A point $x\in S$ is called a {\em period-$n$ point} for
$f$ if $f^n(x)=x$ and $f^j(x)\neq x$ for $1\leq j\leq n-1$. Let $\text{\rm Per}_n(f)$ denote the
set of all period-$n$ points for $f$ and let $\#\text{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),\ldots,
f^{n-1}(a)$ are distinct period-$n$ points and hence $n|\#\text{Per}_n(f)$. Since
$\#\text{Per}_1(f^n)=\sum_{m|n}\#\text{Per}_m(f)$, the sequence $\{\#\text{Per}_1(f^n)\}$ is the
Fermat sequence generated by the sequence $\{\#\text{Per}_n(f)/n\}$.
Following~\cite{EverestPoortenPuriWard2002}, we say that a nonnegative integral sequence $\{a_n\}$
is {\em exactly realizable} if there is a map $f$ from a set into itself such that
$\#\text{Per}_1(f^n)=a_n$ for all $n\geq 1$; in this case, we write $E(f)=\{a_n\}$. Let $M$ be the
set of maps $f$ for which $\text{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.
\begin{theorem}\label{exact}
Let $\{a_n\}$ be a sequence in ${\mathbb C}$. Then the following three items are equivalent:
\begin{enumerate}
\item $\{a_n\}$ is exactly realizable;
\item 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\}$;
\item 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\geq 1$,
$$c_n=\sum_{k_1+2k_2+\cdots+nk_n=n}(-1)^{k_1+k_2+\cdots+k_n+1}\
\left(\begin{matrix}d_1 \\k_1\end{matrix}\right)\left(\begin{matrix}d_2
\\k_2\end{matrix}\right)\cdots
\left(\begin{matrix}d_n \\k_n\end{matrix}\right)
$$ where $\left(\begin{matrix}p \\ q\end{matrix}\right)$ denotes a binomial
coefficient; that is, $N(\{c_n\})=\{a_n\}$.
\end{enumerate}
Moreover, if the above items hold then $b_n=d_n$ for all $n\geq 1$.
\end{theorem}
\begin{proof}
$(1 \Rightarrow 2)$ Let $f$ be a function such that $\#\text{Per}_1(f^n)=a_n$ for all $n\geq 1$
and let $b_n=\#\text{Per}_n(f)/n$ for all $n\geq 1$. Then $\{b_n\}$ is nonnegative and integral,
and $a_n=\sum_{m|n}mb_m$ for all $n\geq 1$.
$(1 \Leftarrow 2)$ By permutation, we can define $f: {\mathbb N}\to {\mathbb N}$ 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=\#\text{Per}_m(f)$ for all $m\geq 1$ and hence
$a_n=\sum_{m|n}mb_m=\#\text{Per}_1(f^n)$ for all $n\geq 1$. Therefore, $\{a_n\}$ is exactly
realizable.
$(2 \Leftrightarrow 3)$ By using item 3 of Theorem~\ref{NewtonFermat} and letting $d_n=b_n$ for all
$n\geq 1$, it remains to verify the expressions of $c_n$'s. From items 1 and 2 of
Theorem~\ref{NewtonFermat}, we have $1-\sum_{n=1}^\infty c_nx^n=\prod_{n=1}^\infty (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 \Leftrightarrow 3)$.
\end{proof}
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, \cdots\}$, 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\geq 3$. Nevertheless, the nonnegativeness of all $c_n$'s is sufficient for exact
realizability of $\{a_n\}$ as follows.
\begin{theorem}\label{NewtonExact}The following properties hold.
\begin{enumerate}
\item Every Newton sequence generated by a nonnegative integral sequence is exactly realizable,
that is, $N(I_+)\subset E(M)$. \item Every Newton sequence generated by an integral sequence is a
term-by-term difference of two exactly realizable sequences, and vice versa.
\end{enumerate}
\end{theorem}
Before proceeding with the proof, we recall some basic definitions in symbolic dynamics; refer to
\cite{Kitchens1998, Robinson1999}. A {graph} $G$ consists of a countable (resp. finite) set ${S}$
of states together with a finite set ${E}$ of edges. Each edge $e\in 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 {\em
edge shift space} $\Sigma_A$ is the space of sequences of edges from $E$ specified by
$$\Sigma_A=\{e_0e_1e_2\cdots| e_j\in E \text{ and } t(e_j)=i(e_{j+1})
\text{ for all integers } j\geq 0\}.$$ The {\em shift map} $\sigma_A:\Sigma_A\to \Sigma_A$ induced
by $A$ is defined to be
$$\sigma_A(e_0e_1e_2e_3\cdots)=e_1e_2e_3\cdots.$$
Now we prove Theorem~\ref{NewtonExact}.
\begin{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={\mathbb N}$ by
$A_{IJ}$ to be $c_J$ if $I=1$ and $J\geq 1$, one if $I=J+1$ and $J\geq 1$, and zero otherwise. Let
$\sigma_{A}$ be the shift map induced by $A$. Then
$a_n=\text{trace}(A^n)=\#\text{Per}_1(\sigma^n_A)$ for all $n\geq 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}\sum_{m|n}\mu(m)a_{n/m}$ for all $n\geq 1$,
Theorem~\ref{NewtonFermat} 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\geq 1$. Then
$b_n^+\geq 0$, $b_n^-\geq 0$ and $b_n=b_n^+-b_n^-$ for all $n\geq 1$. Setting
$a_n^+=\sum_{m|n}mb_m^+$ and $a_n^-=\sum_{m|n}mb_m^-$, it follows from Theorem~\ref{exact} that
$\{a_n^+\}$ and $\{a_n^-\}$ are both exactly realizable sequences. Moreover,
$a_n=\sum_{m|n}mb_m=\sum_{m|n}m(b_m^+-b_m^-)=a_n^+-a_n^-$ for all $n\geq 1$.
Finally we prove the backward part of item 2. By Theorem~\ref{exact}, 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~\ref{NewtonFermat}, imply the desired result.
\end{proof}
\section{Formal Power Series}
Combining the theorems above,
we have the following result on formal power series.
\begin{corollary}\label{Cnonnegative}
Let $\{b_n\}$ and $\{c_n\}$ be two sequences in ${\mathbb C}$ such that $1-\sum_{n=1}^\infty
c_nx^n=\prod_{n=1}^\infty(1-x^n)^{b_n}$ as formal power series. If $\{c_n\}$ is a nonnegative
integral sequence then so is $\{b_n\}$.
\end{corollary}
\begin{proof}
Let $\{a_n\}$ be the Newton sequence generated by $\{c_n\}$. By items 1 and 2 of
Theorem~\ref{NewtonFermat}, the sequence $\{a_n\}$ is the Fermat sequence generated by $\{b_n\}$.
By item 1 of Theorem~\ref{NewtonExact}, the sequence $\{a_n\}$ is exactly realizable such that
$a_n=\#\text{Per}_1(f^n)$ for some map $f$. Therefore, we have that
$b_n=\sum_{m|n}\mu(m)a_{n/m}=\#\text{Per}_n(f)/n\geq 0$ for all $n\geq 1$.
\end{proof}
Finally, we give a criterion of exact realizability for the Newton sequence generated by $\{c_n\}$
with $c_n=0$ for all $n\geq 3$.
\begin{corollary}\label{sharp}
Let $\{a_n\}$ be the Newton sequence generated by a sequence $\{c_n\}$ with $c_n=0$ for all $n\geq
3$. Then $\{a_n\}$ is exactly realizable if and only if $c_1$ and $c_2$ are both integers with
$c_1\geq 0$ and $c_2\geq -c_1^2/4$.
\end{corollary}
\begin{proof}
First we prove the ``if" part. If $c_1$ is even, we define a matrix
$A=\begin{bmatrix}c_1/2&c_1^2/4+c_2\\ 1 & c_1/2\end{bmatrix}$. Then $A$ is a nonnegative integral
matrix and $a_n=\text{trace}(A^n)=\#\text{Per}_1(\sigma_A^n)$, where $\sigma_A$ is the shift map
induced by $A$ (see the proof of Theorem~\ref{NewtonExact} with two states). Therefore, $\{a_n\}$
is exactly realizable. Similarly, if $c_1$ is odd, then $c_2\geq -c_1^2/4+1/4$ because $c_2$ is an
integer, and hence $\{a_n\}$ is exactly realizable with respect to $\sigma_A$, where
$A=\begin{bmatrix}(c_1+1)/2&(c_1^2-1)/4+c_2\\ 1 &(c_1-1)/2\end{bmatrix}$.
Next we prove the ``only if" part. Since $\{a_n\}$ is exactly realizable, $c_1=a_1\geq 0$ is an
integer, $c_2=(a_2-a_1)/2-c_1(c_1-1)/2$ is an integer, and $a_n=\text{trace}(A^n)\geq 0$ for all
$n\geq 1$, where $A=\begin{bmatrix}c_1/2&c_1^2/4+c_2\\ 1 & c_1/2\end{bmatrix}$. Suppose, on the
contrary, that $c_2=-c_1^2/4-\alpha$ for some $\alpha>0$. Let
$B=\begin{bmatrix}c_1/2&-\sqrt{\alpha}\\ \sqrt{\alpha} & c_1/2\end{bmatrix}$. Then $B$ has the same
characteristic polynomial as $A$ and hence $a_n=\text{trace}(A^n)=\text{trace}(B^n)$ for all $n\geq
1$. Let $r=\sqrt{c_1^2/4+\alpha}$ and pick $0<\theta\leq \pi/2$ so that $r\cos\theta=c_1/2$ and
$r\sin\theta=\sqrt{\alpha}$. Then $B^{n}=\begin{bmatrix}r^n\cos n\theta&-r^n\sin n\theta\\ r^n\sin
n\theta & r^n\cos n\theta\end{bmatrix}$ and $a_{n}=2r^n\cos n\theta$ for all $n\geq 1$. This
contradicts that $a_n\geq 0$ for all $n\geq 1$. Therefore, $c_2\geq -c_1^2/4$.
\end{proof}
\bigskip
\noindent {\em{Acknowledgments:}} We would like to thank Professor D. Zagier for his invaluable
suggestions which lead to the formulation of Theorem \ref{NewtonFermat} and are also grateful to
the referee for helpful suggestions which have improved the presentation of this note.
\begin{thebibliography}{99}
\bibitem{Berlekamp1968}
E.~Berlekamp, \textit{Algebraic {C}oding {T}heory}, MacGraw Hill Book Co., New
York, 1968.
\bibitem{Carlitz1958}
L.~Carlitz, Note on a paper of Dieudonne, \textit{Proc. Amer. Math. Soc.}
\textbf{9} (1958), 32--33.
\bibitem{Du2000bams}
B.-S. Du, The linearizations of cyclic permutations have rational zeta
functions, \textit{Bull. Austral. Math. Soc.} \textbf{62} (2000),
287--295.
\bibitem{DuHuangLi2003}
B.-S. Du, S.-S. Huang, and M.-C. Li, Genralized Fermat, double Fermat
and Newton sequences, \textit{J. Number Theory} \textbf{98} (2003),
172--183.
\bibitem{EverestPoortenPuriWard2002}
G.~Everest, A.~J. van~der Poorten, Y.~Puri, and T.~Ward,
\href{../../VOL5/Ward/ward2.html}{Integer sequences and periodic points},
\textit{J. Integer Seq.} \textbf{5} (2002), Article 02.2.3, 10 pp.
\bibitem{Kitchens1998}
B.~P. Kitchens, \textit{{S}ymbolic {D}ynamics: {O}ne-sided, {T}wo-sided and
{C}ountable {S}tate {M}arkov {S}hifts}, Springer-Verlag, Berlin, 1998.
\bibitem{LidlNiederreiter1997} R. Lidl and H. Niederreiter, \textit{Finite Fields}, 2nd ed.,
Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge,
1997.
\bibitem{Mead1992}
D.~G. Mead, Newton's identities, \textit{Amer. Math. Monthly} \textbf{99} (1992),
749--751.
\bibitem{Minac2003}
J.~Min\'a\v{c}, Newton's identities once again, \textit{Amer. Math. Monthly}
\textbf{110} (2003), 232--234.
\bibitem {NivenZuckermanMontgomery1991}
I. Niven, H. S. Zuckerman, and H. L. Montgomery, \textit{An Introduction to the Theory of Numbers},
fifth ed., Wiley, New York, 1991.
\bibitem{Robinson1999}
C.~Robinson, \textit{Dynamical {S}ystems: {S}tability, {S}ymbolic {D}ynamics, and
{C}haos}, 2nd ed., Studies in Advanced Mathematics, CRC Press, Boca
Raton,
FL, 1999.
\bibitem{Serre1965} J.-P. Serre, \textit{Lie Algebra and Lie Groups}, Lectures given at Harvard
University, 1964, W.A.Benjamin, Inc., New York-Amsterdam, 1965.
\bibitem{Zagier2003}
D.~Zagier, private communication by email, 2003.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11B83; Secondary 11B50, 37B10 .
\noindent \emph{Keywords: }
Newton sequence, Fermat sequence, exactly realizable sequence,
symbolic dynamics.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received June 1 2004;
revised version received October 20 2004.
Published in {\it Journal of Integer Sequences}, January 12 2005.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in
\end{document}