\documentclass[12pt,reqno]{amsart}

\usepackage{color}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
%\definecolor{webgreen}{rgb}{0,.5,0}
%\definecolor{webbrown}{rgb}{.6,0,0}
%\usepackage{psfig,epsf,latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\textheight}{8.7in}
\setlength{\topmargin}{0.0in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{
\underline{#1}}}

%\renewcommand{\subjclassname}{\textup{2000} Mathematics
%Subject Classification}

\newtheorem{theorem}{Theorem}[section]\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{hypothesis}[theorem]{Hypothesis}

\newtheorem{stheorem}{Theorem}
\newtheorem{slemma}{Lemma}
\newtheorem{scorollary}{Corollary}
\newtheorem{sproposition}{Proposition}

\theoremstyle{definition}

\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{claim}[theorem]{Claim}

\def\Per{\operatorname{Per}}
\def\trace{\operatorname{trace}}        %% matrix trace
\def\ftrace{\operatorname{T}}   %% field trace
\def\norm{\operatorname{N}}     %% field norm

\begin{document}


\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\title{Integer Sequences and Periodic Points}

\maketitle

% \subjclass{11G07, 37B40}

\bigskip

\centerline{\bf G. Everest$^1$, A. J. van der Poorten$^2$, Y. Puri$^1$, and T. Ward$^1$}

\bigskip

\begin{center}
$^1$ School of Mathematics, University of East Anglia, Norwich NR4 7TJ, United Kingdom \\
{\tt g.everest@uea.ac.uk},\ {\tt puri@hotmail.com},\ {\tt t.ward@uea.ac.uk}\\
\ \\
$^2$ ICS, Macquarie University, NSW 2109, Australia \\
{\tt alf@math.mq.edu.au}
\end{center}

\bigskip\bigskip

%\author{G. Everest}\email{g.everest@uea.ac.uk}
%\author{A. J. van der Poorten}\email{alf@math.mq.edu.au}
%\author{Y. Puri}\email{yash\underline{\ }puri@hotmail.com}
%\author{T. Ward}\email{t.ward@uea.ac.uk}
%\address{(EPW) School of Mathematics, University of East Anglia,
%Norwich NR4 7TJ, UK.}
%\address{(vdP) ICS, Macquarie University,
%NSW 2109, Australia.}
%\dedicatory{\today}

\begin{center}
{\bf Abstract.}  Arithmetic properties of integer sequences counting periodic points
are studied, and applied to the case of linear recurrence
sequences, Bernoulli numerators, and Bernoulli denominators.
\end{center}


\section{Introduction}

An existing dialogue between number theory and dynamical systems
is advanced.
A combinatorial device gives necessary and
sufficient conditions for a sequence of non-negative integers to
count the periodic points in a dynamical system. This is applied
to study linear recurrence sequences which count periodic points.
Instances where the $p$-parts of an integer
sequence themselves count periodic points are studied.
The Mersenne sequence
provides one example, and the denominators of the Bernoulli numbers
provide another.
The methods
give a dynamical interpretation of many classical congruences such
as Euler-Fermat for matrices, and suggest the same for the
classical Kummer congruences satisfied by the
Bernoulli numbers.

Let $X$ denote a set, and $T:X\rightarrow X$
a map. An element $x\in X$ is a periodic
point of period $n\in\mathbb N$ if it is fixed under $T^n$,
that is $T^n(x)=x$.
Let Per$_n(T)$ denote the set of points of period $n$ under $T$.
Following \cite{puri}, call a sequence $u=(u_n)_{n\ge1}$ of non-negative
integers realizable if there is a set $X$ and a map
$T:X\rightarrow X$ such that $u_n=\vert\Per_n(T)\vert$.

This subject is example-driven so we begin
our account with several of these. Throughout,
examples will be referenced as they appear in
the
\htmladdnormallink{Encyclopedia of Integer
Sequences}{http://www.research.att.com/~njas/sequences/}.

\begin{example}\label{examples}\begin{enumerate}
\item Let $M_n=2^n-1, n\ge1$ denote the $n$-th term of the Mersenne
sequence
\htmladdnormallink{A000225}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000225}.
This sequence is of interest in
number theory because it is conjectured to contain infinitely many
prime terms, and in dynamics because it
counts the periodic points
in the simplest expanding dynamical system.
Let 
$${\mathbb S}^1=\{z\in\mathbb C\mid\vert z\vert=1\}$$
denote the complex unit circle.
Then the map
$T:{\mathbb S}^1\rightarrow {\mathbb S}^1$, $T(z)=z^2$,
has $\vert\Per_n(T)\vert=M_n$.
\item Let $L_n$ denote
the $n$-th term of the Lucas sequence
\htmladdnormallink{A000204}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000204}.
Let $X$
denote the set of all doubly-infinite strings of $0$'s and $1$'s
in which every $0$ is followed by a $1$, and let $T:X\rightarrow X$ be
the left shift defined by $(Tx)_n=x_{n+1}$. Then
$\vert\Per_n(T)\vert=L_n$.
\item The Lehmer-Pierce sequences (generalizing the Mersenne sequence;
see \cite{MR2000e:11087}) also arise in counting periodic points.
Let $f(x)$ denote a monic, integral polynomial with degree $d\ge
1$ and roots $\alpha_1,\ldots ,\alpha_d$. Define
$$\Delta_n(f)=\prod_i\vert \alpha_i^n-1\vert,
$$
which is non-zero for $n\ge1$ under the assumption that
no $\alpha_i$ is a root of unity.
When $f(x)=x-2$, we obtain $\Delta_n(f)=M_n$. Sequences of the
form $\left(\Delta_n(f)\right)$ were studied by Pierce and Lehmer
with a view to understanding the special form of their factors, in
the hope of using them to produce large primes. One such, is sequence
\htmladdnormallink{A001945}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001945}
corresponding to $f(x)=x^3-x-1$. In dynamics they
arise as sequences of periodic points for toral endomorphisms: Let
$X=\mathbb T^d$ denote the $d$-dimensional additive torus.
The companion matrix $A_f$ of $f$ acts on $X$ by multiplication
mod $1$, $T(x)=A_fx$ mod $1$. It requires a little thought to
check that $\vert\Per_n(T)\vert=\Delta_n(f)$ under the same {\sl
ergodicity} condition that no $\alpha_i$ is a root of unity (see
\cite{MR2000e:11087}). Notice that the Lehmer-Pierce sequences are
the absolute values of integer sequences which could have mixed
signs.

The next two examples illuminate the same issue of signed sequences
whose absolute value counts periodic points.
\item The Jacobsthal-Lucas
sequence
\htmladdnormallink{A014551}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A014551}
$R_n=\vert(-2)^n-1\vert$ counts points of period $n$ for the map
$z\mapsto z^{-2}$ on ${\mathbb S}^1$.
\item The sequence $S_n=\vert
2^n+(-3)^n\vert$ counts periodic points in a certain continuous
automorphism of a $1$-dimensional solenoid, see \cite{MR99b:11089}
or \cite{MR90a:28031}.
\item For $a\ge 1$, the
shift map $T$ on $\{0,1,\dots,a-1\}^{\mathbb Z}$ has
$\vert\Per_n(T)\vert=a^n$.
\item If $B$ denotes a square matrix with non-negative integral
entries then $\left(\trace(B^n)\right)$ is
a realizable sequence.
To see this, let $G_B$ be
the labelled graph with adjacency matrix $B$ and $T_B$ the
edge-shift on the set of labels of infinite paths on $G_B$. Then
the number of points of period $n$ for this system is
$\trace(B^n)$ (see \cite{LM} for the details).
\end{enumerate}
\end{example}

The sequences above are realizable by continuous
maps of compact spaces; it turns out that any realizable sequence
is in fact realizable by such a map.

It is natural to ask what is required of a sequence in order that
it be realizable. For example, could the Fibonacci sequence 
\htmladdnormallink{A000045}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000045},
the
more illustrious cousin of the Lucas sequence, be realized in this
way? The answer is no, and a simple proof will follow in
Section \ref{comdyn}. In fact a sequence of non-negative integers satisfying
the Fibonacci recurrence is realizable if and only if it is a
non-negative integer multiple of the Lucas sequence (see
\cite{puri}, \cite{puri-ward},
\cite{puri-ward-2} and Theorem \ref{binaryrec} below).
However, we will see
in Theorem \ref{bernoulliandmersenne} that in a
precise sense, the Fibonacci sequence is semi-realizable.

\section{Statements of Results}\label{statements}

If $u=\left(u_n\right)$ is any sequence of integers, then
it is reasonable to ask if the sequence $\vert u\vert=\left(\vert
u_n\vert\right)$ of absolute values is realizable. For example,
the sequence $(1,-3,4,-7,\ldots)$ is a signed linear recurrence
sequence whose absolute values are realizable. A
signed sequence $u$ will also be called
realizable if $|u|$ is realizable.

Theorem~\ref{binaryrec} recasts \cite[Theorem~2.5]{puri-ward},
concerning realizable binary
linear recurrence sequences, in a form that generalizes.
The definitions are standard but they will be recalled later.
Recall that the $\mathbb C$-space of all solutions of a
binary recurrence relation has dimension 2. The {\sl realizable
subspace} is the subspace spanned by the realizable solutions.
Thus, for the Fibonacci recurrence, the realizable subspace has
dimension 1 and is spanned by the Lucas sequence.

\begin{theorem}\label{binaryrec}
Let $\Delta$ denote the discriminant of the
characteristic polynomial
associated to a non-degenerate binary recurrence relation.
Then the realizable
subspace has\begin{enumerate}
\item dimension $0$ if $\Delta <0$,
\item dimension $1$ if $\Delta=0$ or $\Delta > 0$
and non-square,
\item dimension $2$ if $\Delta >0$ is a square.
\end{enumerate}
\end{theorem}

\begin{example}\label{rank2}(cf. \cite[Example~2.6(2)]{puri-ward})
As an example of the third
condition, consider the recurrence relation
\begin{equation}\label{mersennerelation}
u_{n+2}=3u_{n+1}-2u_n,
\end{equation}
which is satisfied by the Mersenne sequence.
The recurrence sequences $a2^n+b$ with $a,b\in\mathbb N$
all satisfy (\ref{mersennerelation}) and are realizable ---
see Corollary \ref{sumandtimes}.
\end{example}

Theorem~\ref{binaryrec} is proved in
\cite{puri-ward} using essentially quadratic
methods --- but it surely has a generalization to higher
degree, characterizing the realizable subspace in terms of the
factorization of the characteristic polynomial of the recurrence. The second
theorem is a partial result in that direction, giving a
restriction on the dimension of the realizable subspace under the
assumption that the characteristic polynomial
has a dominant root.

\begin{theorem}\label{rankrestriction}Let $f$ denote the
characteristic polynomial of a non-degenerate linear recurrence
sequence with integer coefficients. If $f$ is separable,
with $\ell$ irreducible
factors
and a dominant root then the dimension of the
realizable subspace cannot exceed $\ell$. If $f(0)\neq 0$ 
then equality holds if either
the dominant
root is not less than the sum of the absolute values of
the other roots or
the dominant root
is strictly greater than the sum of the absolute values of
its conjugates.
\end{theorem}

It is not clear if there is an exact result but the
deep result of Kim, Ormes and Roush \cite{kor} on
the Spectral Conjecture of Boyle and Handelman \cite{bh}
gives a checkable criterion for a given linear recurrence sequence
to be realized {\sl by an irreducible subshift of finite type}.
\begin{example}\label{tribonacci}
Consider the sequences which satisfy the Tribonacci relation
\begin{equation}\label{trib}
u_{n+3}=u_{n+2}+u_{n+1}+u_n.
\end{equation}
The sequence
\htmladdnormallink{A001644}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001644}
satisfies (\ref{trib}) and is
realizable, since it is the sequence
$\left(\trace(A_f^n)\right)$, where
$A_f$ is the companion matrix to $f(x)=x^3-x^2-x-1$.
Theorem~\ref{rankrestriction} says that
any realizable sequence which satisfies (\ref{trib}) is a multiple
of this one.
\end{example}

%\begin{example} If $u$ is a ternary linear recurrence
%relation with a pair of complex conjugate dominant roots, then
%$\vert u\vert$ is not realizable by an argument
%similar to the one given
%in the proof of Theorem~\ref{binaryrec}.
%\end{example}

\begin{example} Suppose $g$ denotes a polynomial with
$\ell-1$ distinct irreducible factors (possibly repeated).
For an integer $K,$  consider the linear
recurrence relation
with characteristic polynomial
$$f(x)=(x-K)g(x).$$
For all sufficiently large $K,$  $f$ has
$\ell$ distinct irreducible factors and the realizable
subspace has dimension $\ell$.
\end{example}

The third theorem consists of a triple of examples. Given a
sequence $u$ and a prime $p$, write $[u_n]_p$ for the
$p$-part of $u_n$. Notice that $[u]_p$ is always
non-negative. A sequence $u$ is {\sl locally
realizable at p} if $[u]_p$ is itself
realizable, and is {\sl everywhere locally
realizable} if it is locally realizable at $p$ for all primes
$p$. If a sequence is everywhere locally realizable and non-negative
then
it is realizable by Corollary~\ref{sumandtimes} below. Moss has shown
\cite{pm} that the converse is true for any endomorphism of a locally
nilpotent group.

Consider the Bernoulli numbers $B$,
defined by the relation
$$
\frac{t}{e^t-1}=\sum_{n=0}^{\infty}B_n\frac{t^n}{n!};
$$
$B_n\in \mathbb Q$ for all $n$, and $B_n=0$ for all odd
$n>1$.

\begin{theorem}\label{bernoulliandmersenne}
Any Lehmer--Pierce sequence
is everywhere locally realizable, and hence
realizable. The Fibonacci sequence is locally
realizable at primes $\equiv \pm 1$ modulo 5.
Let $b_n$ denote the denominator of $B_{2n}$ for $n\ge 1$. Then
$b=(b_n)$ is everywhere locally realizable, and hence realizable.
\end{theorem}

The sequence $b$ is
\htmladdnormallink{A002445}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002445},
a much-studied sequence.
The maps in Theorem~\ref{bernoulliandmersenne} are
endomorphisms of groups.
Theorem~\ref{bernoulliandmersenne} and Lemma~\ref{puriwardlemma} suggest a
dynamical interpretation of composite versions of the classical
Kummer congruences; see Section~\ref{bernoullisect} below.

\section{Combinatorics of periodic points}\label{comdyn}

As pointed out in \cite[Example~2.2(1)]{puri-ward},
the Fibonacci sequence is
not realizable. No map can have 1 fixed point and 2 points of
period 3 --- the image under the map of the non-fixed point of
period 3 would have to be a distinct non-fixed point of period 3,
and there are no others. More generally, for any prime $p$, the
number of non-fixed points of period $p$ must be divisible by $p$
because their orbits occur in cycles of length $p$. From
this kind of reasoning, the following
characterization emerges (see \cite[Lemma~2.1]{puri-ward}).

\begin{lemma}\label{puriwardlemma} Let $u$ be
a sequence of non-negative integers, and let $u*\mu$ denote the
Dirichlet convolution of $u$ with the M\"obius function $\mu$.
Then $u$ is realizable if and only if $(u*\mu)_n\equiv 0$ mod $n$
and $(u*\mu)_n\ge 0$ for all $n\ge 1$.
\end{lemma}

\begin{corollary}\label{sumandtimes}
The sum and product of two realizable sequences are both
realizable.
\end{corollary}

\begin{proof} This may be seen either using elementary properties of the
Dirichlet convolution or using the realizing maps: if $u$ and $v$
are realizable, then the Cartesian product of the realizing maps
realizes $\left(u_nv_n\right)$, while the disjoint union realizes
$\left(u_n+v_n\right)$. \end{proof}

Notice that if $n=p^r$, for a prime $p$ and $r>0$ an integer,
Lemma \ref{puriwardlemma} requires that
\begin{equation}\label{lookslikeef}
u_{p^r}\equiv u_{p^{r-1}} \mod p^r
\end{equation}
for any realizable sequence $u$.

\begin{corollary}\label{eulerfermat}
Let $a$ denote a positive integer and let $p$ and $r$ be as above.
Then
$$a^{p^r}\equiv a^{p^{r-1}} \mod p^r.
$$
\end{corollary}

\begin{proof}
This is the statement of the Euler-Fermat Theorem; a dynamical
proof applies (\ref{lookslikeef}) to Example~\ref{examples}(6).
\end{proof}

This kind of observation --- that periodic
points in full shifts give simple proofs of many elementary
congruences --- is folklore; indeed the paper \cite{!!!} gives a
rather complicated proof of Euler--Fermat using a dynamical
system.

Lemma~\ref{puriwardlemma} does more with no additional effort. The
following is a generalization of the Euler-Fermat Theorem for
integral matrices which will be used in the proof of Theorem~\ref{binaryrec}.

\begin{corollary}\label{matrixeulerfermat}
Let $A$ denote a square matrix with integer entries and let $p$
and $r$ be as above. Then
$$
\trace(A^{p^r})\equiv\trace(A^{p^{r-1}}) \mod p^r.
$$
\end{corollary}
\begin{proof}
It is sufficient to assume $A$ has non-negative entries, since any
matrix has such a representative mod $p^r$. The result follows
at once from Example~\ref{examples}(7).
\end{proof}

We now state the consequences of Lemma \ref{puriwardlemma} in
their most general form for matrix traces.

\begin{corollary}\label{matrixcong}
Let $A$ denote a square matrix with integer entries and let $A_n$
denote the sequence $\trace(A^n)$. Then for all $n\ge 1$
$$\sum_{d|n}A_d\mu(n/d) \equiv 0 \mod n.
$$
\end{corollary}

\section{Proofs}

Before the proof of Theorem \ref{binaryrec}, we begin with some
notation (for a lively account of the general properties of linear
recurrence sequences, see \cite{MR92k:11011}). Let
$u$ be a binary recurrence sequence. This means that
$u_1$ and $u_2$ are given as initial values, with all subsequent terms
defined by a recurrence relation
\begin{equation}\label{recrel}
u_{n+2}=Bu_{n+1}-Cu_n.
\end{equation}
The polynomial $f(x)=x^2-Bx+C$ is the {\sl characteristic
polynomial} of the recurrence relation. Write
$$A_f=\left(\begin{matrix}0&1\\ -C&B\end{matrix}\right)
$$
for the companion matrix of $f$. The zeros $\alpha_1$ and
$\alpha_2$ of $f$, are the {\sl characteristic roots} of the
recurrence relation. The sequence is non-degenerate if
$\alpha_1/\alpha_2$ is not a root of unity. The {\sl discriminant}
of the recurrence relation is $\Delta = B^2-4C$.
The general solution of the recurrence relation is
$u_n=(\gamma_1+\gamma_2n)\alpha_1^n$ if
$\Delta=0$, and
$u_n=\gamma_1\alpha_1^n+\gamma_2\alpha_2^n$ if $\Delta\neq0$.

\medskip

\noindent{\sc Proof of Theorem \ref{binaryrec}.}
Assume first that $\Delta=0$, and let $p$ denote any prime which
does not divide $\alpha_1$ or $\gamma_2$. Then the congruence 
(\ref{lookslikeef}) is violated at $n=p$ unless
$\gamma_2=0$. In that case, $\vert\gamma_1\alpha_1^n\vert$ is
realizable and the space this generates is 1-dimensional.

If $\Delta>0$ is a square, then the roots are rationals and,
plainly, must be integers. We claim that for any integers
$\gamma_1$ and $\gamma_2$, the sequence $\vert\gamma_1\alpha_1^n
+\gamma_2\alpha_2^n\vert$ is realizable. In fact (up to
multiplying and adding full shifts) this sequence counts the periodic
points for an automorphism on a one-dimensional solenoid, see
\cite{MR2000e:11087} or \cite{MR90a:28031}.

The two cases where $\Delta\neq 0$ is not a square are similar.
Write $\alpha=s+t\sqrt {\Delta}$, with $s,t \in \mathbb Q$, 
for one of the roots of $f$ and
let $K=\mathbb Q(\alpha)$ denote the quadratic number field
generated by $\alpha$. Write $\ftrace_{K\vert \mathbb
Q}:K\rightarrow \mathbb Q$ for the usual field trace. The general
integral solution to the recurrence is $u_n=\ftrace_{K\vert
\mathbb Q}((a+b\sqrt {\Delta})\alpha^n)$, where $a$ and $b$ are
both integers or both half-odd integers. Write
$v_n=\ftrace_{K\vert \mathbb Q}(a\alpha^n)$ and
$w_n=\ftrace_{K\vert \mathbb Q}(b\sqrt {\Delta}\alpha^n)$. Now
$v_n=a\trace(A_f^n)$, where $A_f$ denotes the companion matrix of
$f$. Hence it satisfies $v_p\equiv v_1$ mod $p$ for all primes $p$
by Corollary \ref{matrixeulerfermat}.

Let $p$ denote any inert prime for $K$. The residue field is
isomorphic to the field $\mathbb F_{p^2}$. Moreover, the
non-trivial field isomorphism restricts to the Frobenius at the
finite field level. Reducing mod $p$ gives the congruence
$$\sqrt {\Delta}\alpha^p-\sqrt {\Delta}\alpha
\equiv \sqrt {\Delta}\alpha-\sqrt{\Delta}\alpha^p \mod p.
$$
Thus $w_p\equiv -w_1$ mod $p$ for all inert primes $p$. On the
other hand, $v_p\equiv v_1$ mod $p$ for all inert primes $p$.

If $\vert u_n\vert$ is realizable then $\vert u_p \vert \equiv
\vert u_1\vert$ mod $p$ by (\ref{lookslikeef}). If
$u_p\equiv -u_1$ mod $p$ for infinitely many primes $p$ then
$v_p+w_p\equiv v_1-w_1\equiv -v_1-w_1$ mod $p$. We deduce that
$p\vert v_1$ for infinitely primes and hence $v_1=2as=0$. We
cannot have $s=0$ by the non-degeneracy, so $a=0$. If $u_p\equiv
u_1$ mod $p$ then, by a similar argument, we deduce that $bt=0$.
We cannot have $t=0$ again, by the non-degeneracy so $b=0$. This
proves that when $\Delta \neq 0$ is not a square, the realizable
subspace must have rank less than 2.

Suppose firstly that $\Delta>0$. We will prove that the rank is
precisely 1. In this case, there is a dominant root. If this root
is positive then all the terms of $u_n$ are positive. If the
dominant term is negative then the sequence of absolute values
agrees with the sequence obtained by replacing $\alpha$ by
$-\alpha$ and the dominant root is now positive. In the recurrence
relation (\ref{recrel}) $C=\norm_{K\vert \mathbb Q}(\alpha)$, the
field norm, and $B= \ftrace_{K\vert \mathbb Q}(\alpha)$. We are
assuming $B>0$. If $C<0$ then the sequence $u_n=\trace (A_f^n)$
is realizable using Example~\ref{examples}(7), because the matrix $A_f$
has non-negative entries.
If $C>0$ the matrix $A_f$ may be conjugated to
a matrix with non-negative entries (this leaves
the sequence of traces invariant). To see this, let $E$ denote the
matrix
$$E=\left(\begin{matrix}1&0\\k&1\end{matrix}\right).
$$
Then
$$E^{-1}A_fE=\left(\begin{matrix}k&1\\Bk-k^2-C&B-k\end{matrix}\right).
$$
If $B$ is even, take $k=B/2$. Then the lower entries in
$E^{-1}A_fE$ are $(B^2-4C)/4=\Delta/4>0$ and $B/2>0$. If $B$ is
odd, take $k=(B+1)/2$. Then the lower entries are $(B^2-1-4C)/4=
(\Delta-1)/4\geq 0$ and $(B-1)/2\ge0$. In both cases we have
conjugated $A_f$ to a matrix with non-negative entries.

Finally, we must show that when $\Delta<0$, both sequences $v_n$
and $w_n$ are not realizable in absolute value. Assume $a\neq 0$,
and then note that $v_1=2as\neq0$ by the non-degeneracy
assumption. For all primes $p$ we have $v_p\equiv v_1$ by the
remark above. Since the roots $\alpha_1$ and $\alpha_2$ are
complex conjugates, $\vert\alpha_1\vert=\vert\alpha_2\vert$. Let
$\beta=\frac{1}{2\pi}\arg(\alpha_1/\alpha_2)$; $\beta$ is
irrational by the non-degeneracy assumption. The sequence of
fractional parts of $p\beta$, with $p$ running through the primes,
is dense in $(0,1)$ (this was proved by Vinogradov \cite{vino};
see \cite{vaughan} for a modern treatment). It follows that there
are infinitely many primes $p$ for which $v_pv_1<0$. Therefore, if
$\vert v_n\vert$ is realizable then it satisfies $v_p\equiv v_1$
mod $p$ and $-v_p \equiv v_1$ mod $p$ for infinitely many primes.
We deduce that $v_1=0$ which is a contradiction. With $w_n$ we may
argue in a similar way to obtain a contradiction to $w_1 \neq 0$.
If $\vert w_n\vert$ is realizable then Lemma \ref{puriwardlemma}
says $\vert w_{p^2}\vert \equiv \vert w_p \vert \equiv \vert w_1
\vert$ for all primes $p$. Arguing as before, $w_{p^2}\equiv w_1$
for both split and inert primes. However, the sequence
$\{p^2\beta\}$, $p$ running over the primes, is dense in $(0,1)$.
(Again, this is due to Vinogradov in \cite{vino} or see
\cite{ghosh} for a modern treatment. The general case of
$\{F(p)\}$, where $F$ is a polynomial can be found in
\cite{harman}.) We deduce that $w_{p^2}w_1<0$ for infinitely many
primes. This means $w_{p^2}\equiv w_1$ mod $p$ and $w_{p^2}\equiv
- w_1$ mod $p$ infinitely often. This forces $w_1=0$ --- a
contradiction.
\medskip

\noindent{\sc Proof of Theorem \ref{rankrestriction}.}
Let $d$ denote the degree of $f$. In the first place
we assume $\ell=1$, thus $f$ is irreducible.
The irreducibility of $f$ implies
that the rational solutions of the recurrence are given by
$u_n=\ftrace_{K\vert \mathbb Q}(\gamma \alpha^n)$, where
$K=\mathbb Q(\alpha)$, and $\gamma \in K$. We write $\gamma_i,
\alpha_i, i=1,\dots ,d$ for the algebraic conjugates of $\gamma$
and $\alpha$. The dominant root hypothesis says, after
re-labelling, $\vert\alpha_1\vert> \vert \alpha_i\vert$ for
$i=2,\dots ,d$. We will show that if $u$ is realizable then
$\gamma \in \mathbb Q$.

Let $p$ denote any inert prime. If $p$ is sufficiently large, the
dominant root hypothesis guarantees that $u_p,\dots,u_{p^{d}}$
will all have the same sign. Using Lemma \ref{puriwardlemma}
several times, we deduce that
$$
u_p\equiv u_{p^2}\equiv \dots \equiv
u_{p^{d}} \equiv \pm u_1 \mod p.
$$
Therefore $u_p+\dots +u_{p^{d}}\equiv \pm du_1$ mod $p$,
the sign depending upon the sign of $u_1$. However,
$$u_p+\dots +u_{p^{d}} \equiv
\ftrace_{K\vert \mathbb Q}(\gamma)\ftrace_{K\vert \mathbb
Q}(\alpha) \mod p.
$$
We deduce a fundamental congruence
$$\ftrace_{K\vert \mathbb Q}(\gamma)\ftrace_{K\vert \mathbb Q}(\alpha)
\equiv \pm d\ftrace_{K\vert \mathbb Q}(\gamma \alpha) \mod
p.
$$
Since this holds for infinitely many primes $p$, the congruence is
actually an equality,
\begin{equation}\label{fundeq}
\ftrace_{K\vert \mathbb Q}(\gamma)\ftrace_{K\vert \mathbb
Q}(\alpha) = \pm d\ftrace_{K\vert \mathbb Q}(\gamma \alpha).
\end{equation}

The next step comes with the observation that if $u_n$ is
realizable then $u_{rn}$ is realizable for every $r\ge 1$. Thus
equation (\ref{fundeq}) now reads
\begin{equation}\label{genfundeq}
\ftrace_{K\vert \mathbb Q}(\gamma)\ftrace_{K\vert \mathbb
Q}(\alpha^r) = \pm d\ftrace_{K\vert \mathbb Q}(\gamma \alpha^r).
\end{equation}
Dividing equation (\ref{genfundeq}) by
$\alpha_1^r$ and letting $r\rightarrow \infty$ we obtain the
equation
$$\ftrace_{K\vert \mathbb Q}(\gamma)= \pm
d\gamma_1.
$$
This means that one conjugate of $\gamma$ is rational and hence
$\gamma$ is rational.

The end of the proof in the case $\ell=1$ can be re-worked in
a way that makes it more amenable to generalization. The trace
is a $\mathbb Q$-linear map on $K$ so its kernel has rank $d-1$.
Thus every element $\gamma$ of $K$ can be written $q+\gamma_0$
where $q\in \mathbb Q$ and $\ftrace_{K\vert \mathbb Q}(\gamma_0)=0$.
Noting that $\ftrace_{K\vert \mathbb Q}(q)=dq$ and cancelling
$d$, this simply means equation (\ref{genfundeq}) can be written
$$u_r=\pm
q\ftrace_{K\vert \mathbb Q}(\alpha^r),
$$
for all $r\ge 1$ confirming that the realizable subspace has
rank $\le 1$.

The general case is similar. Each of the irreducible factors
of $f$ generates a number field $K_j, j=1,\dots ,\ell$ of degree
$d_j=[K_j:\mathbb Q]$. The solutions
of the recurrence look like
$$u_n=\sum_{j=1}^{\ell}\ftrace_{K_j\vert \mathbb Q}(\gamma_j\alpha_j^n),
$$
where each $\gamma_j \in K_j$.
Let $L$ denote the compositum of the $K_j$. Using the inert primes
of $L$ and noting that each is inert in each $K_j$, we deduce an
equation
\begin{equation}\label{gengenfundeq}
\sum_{j=1}^{\ell}\frac{d}{d_j}
\ftrace_{K_j\vert \mathbb Q}(\gamma_j)
\ftrace_{K_j\vert \mathbb Q}(\alpha_j)
=\pm d
\sum_{j=1}^{\ell}\ftrace_{K_j\vert \mathbb Q}(\gamma_j\alpha_j).
\end{equation}
As before, replace $\alpha_j$ by $\alpha_j^r$, and cancel $d$ so that
$$u_r=\pm
\sum_{j=1}^{\ell}\frac{1}{d_j}
\ftrace_{K_j\vert \mathbb Q}(\gamma_j)
\ftrace_{K_j\vert \mathbb Q}(\alpha_j^r)
$$
Each $\gamma_j$ can be written $\gamma_j=q_j+\gamma_{0j}$,
where $\ftrace_{K_j\vert \mathbb Q}(\gamma_{0j})=0$. Noting
that $\ftrace_{K_j\vert \mathbb Q}(q_j)=d_jq_j$
we deduce
that
$$u_r=\pm
\sum_{j=1}^{\ell}q_j
\ftrace_{K_j\vert \mathbb Q}(\alpha_j^r)
$$
which proves that the realizable subspace has rank $\le\ell$.

Finally, show that equality holds
in the two cases stated. 
Write $u_n^{(j)}=\ftrace_{K_j\vert \mathbb Q}(\alpha_j^n)$,
which is not identically zero because no $\alpha_j=0$.
Each sequence $u_n^{(j)}$                                           
satisfies the
congruence part of Lemma \ref{puriwardlemma} and hence
any $\mathbb Z$-linear combination also satisfies the congruence.
This is because $u_n^{(j)}$
is identical to $\trace(A_{f_j}^n)$, where $A_{f_j}$
denotes the companion matrix for $f_j$ - hence
we can invoke
Corollary \ref{matrixcong}. To obtain $l$ linearly
independent realizable sequences, suppose $\alpha_1$
is the dominant root and take $u_n^{(1)}$ together
with $u_n^{(1)}+u_n^{(j)}$ for $j=2,\ldots , l$.
The non-negativity part of
Lemma \ref{puriwardlemma} follows from the condition on the
dominant root. For the second case, a similar argument
shows that for sufficiently large $M>0$,
the independent            
sequences $u_n^{(1)}$
and $Mu_n^{(1)}+u_n^{(j)}$ are realizable.
\medskip

\noindent{\sc Proof of Theorem \ref{bernoulliandmersenne}.}
\label{bernoullisect}
It is sufficient to construct
local maps $T_p:X_p\rightarrow X_p$ for each prime $p$.
Then Corollary \ref{sumandtimes} guarantees a global
realization by defining
$$T=\prod _pT_p \mbox{ on } X=\prod _pX_p.
$$
If the maps $T_p$ are group endomorphisms then the map $T$ is
a group endomorphism.

As motivation, consider
the Mersenne sequence.
For each prime $p$, let
$\mathbb U_p\subset\mathbb S^1$ denote the group of all
$p$th power roots of unity. Define the local endomorphism
$S_p:x\mapsto x^2$ on $\mathbb U_p$. Then $\vert\Per_n(S_p)
\vert=[2^n-1]_p$ so $S_p$
gives a local realization of the Mersenne sequence.
Using the same method of proof, we can easily verify the
claim about the Fibonacci sequence. Let $F_n$ denote the
$n$-th term and let
$X$ denote the group of all $p$-th power roots of 1. This
is naturally a $\mathbb Z_p$-module. Let $u$ denote the
golden-mean, thought of as lying in $\mathbb Z_p$ by
the congruence property on $p$.  Then the map
$x\mapsto x^{-u^2}$ has precisely
$[F_n]_p$ points of period $p$.

An alternative proof in the Mersenne case
uses the $S$-integer dynamical
systems from \cite{MR99b:11089}: for each prime $p$, define
$T_p$ to be the automorphism dual to $x\mapsto 2x$
on $\mathbb Z_{(p)}$ (the localization at $p$).
Then by \cite{MR99b:11089},
$$
\vert\Per_n(T_p)\vert=\prod_{q\le\infty;q\neq p}
\vert 2^n-1\vert_q=[2^n-1]_p
$$
by the product formula.
This approach gives a convenient proof for Lehmer-Pierce
sequences in general.
We may assume that the polynomial $f$ is irreducible;
let $K=\mathbb Q(\xi)$ for some zero of $f$.
Then for each prime $p$, let $S$ comprise all places of
$K$ expect those lying above $p$, and let $T_p$ be the
$S$-integer map dual to $x\mapsto \xi x$ on the ring
of $S$-integers in $K$.
Then by the product formula
$$
\vert\Per_n(T_p)\vert=\Big(\prod_{v\vert p}\vert\xi^n-1\vert_v
\Big)^{-1}=\left[\Delta_n(f)\right]_p
$$
as required.

For the Bernoulli denominators,
define
$X_p =\mathbb F_p=
\mathbb Z/p\mathbb Z$. For $p=2$ define $T_p$ to
be the identity. For $p>2$, let $g_p$ denote an
element of (multiplicative) order $(p-1)/2$.
Define $T_p:X_p\rightarrow
X_p$ to be the endomorphism $T_p(x)=g_px$ mod $p$. Plainly
$\vert$Per$_n(T_p)\vert=p$ if and only if $p-1\vert 2n$;
for all other $n$, $\vert$Per$_n(T_p)\vert=1$. The Clausen
von Staudt Theorem (\cite{MR81i:10002}, \cite{koblitz}) states
that
$$B_{2n}+\sum\frac{1}{p}\in \mathbb Z,
$$
where the sum ranges over primes $p$ for which $p-1\vert 2n$. Thus
$\vert$Per$_n(T_p)\vert= \max\{1,\vert B_{2n}\vert _p\}$ and
this shows the local realizability of the Bernoulli denominators.

\section{Epilogue}
A result similar to the one in Theorem \ref{bernoulliandmersenne} 
for the Fibonacci sequence can be proved
for any binary linear recurrence sequence, using the primes
which split in the corresponding quadratic field.

Using the same ideas as in the proof of Theorem \ref{bernoulliandmersenne}
one can prove that the
sequence
\htmladdnormallink{A006953}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006953},
the denominators of $B_{2n}/2n$, is everywhere
locally realizable.
A much more subtle result, due to
Moss \cite{pm},
is that
the sequence
\htmladdnormallink{A001067}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001067},
the numerators of $B_{2n}/2n$, is a realizable sequence
that is not locally realizable exactly at the
irregular primes
\htmladdnormallink{A000928}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000928}.
Taking these remarks together with
$n=p^r$ in Lemma~\ref{puriwardlemma}, suggests a dynamical
interpretation of the Kummer congruences. These are
stated now, for a proof see \cite{koblitz}.

\begin{theorem}\label{kummercongruences}
If $p$ denotes a prime and $p-1$ does not divide $n$ then $n\equiv
n'$ mod $(p-1)p^r$ implies
$$(1-p^{n-1})\frac{B_n}{n}\equiv (1-p^{n'-1})\frac{B_{n'}}{n'}
\mod p^{r+1}.
$$
\end{theorem}

Finally, experimental evidence suggests the sequence
\htmladdnormallink{A006863}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006863},
the denominators of $B_{2n}/4n$ forms a realizable sequence
that is not locally realizable at the primes
$2,3,5,7,11,13$ but seems to be locally realizable for all
large primes.

\section{Acknowledgments}


The second author acknowledges
the support of EPSRC visiting fellowship award GR/R70200.
The third author acknowledges the support of
EPSRC postgraduate award 96001638.


\begin{thebibliography}{10}

\bibitem{bh}
M. Boyle and D. Handelman.
\newblock The spectra of nonnegative matrices via symbolic
dynamics.
\newblock {\em\htmladdnormallink{Ann. of Math.}{http://www.math.princeton.edu/~annals/}} (2), {\bf 133}, 249--316 (1991);
MR~92d:58057.

\bibitem{!!!}
Humberton Carillo Calvet and Jos{\'e} Ram{\'o}n Guzm{\'a}n.
\newblock A dynamical systems proof of Euler's
generalization of the little theorem of Fermat.
\newblock {\em Aportaciones Mat. Comun. }, {\bf25}, 199--202, 1999.
\newblock XXXI National Congress of the Mexican Mathematical
Society; MR~2001i:11005.

\bibitem{MR99b:11089}
Vijay Chothi, Graham Everest and Thomas Ward.
\newblock $S$-integer dynamical systems: periodic points.
\newblock{\em\htmladdnormallink{J. Reine Angew. Math.}{http://www.deGruyter.de/journals/crelle/}},
{\bf 489}, 99-132 (1997); MR~99b:11089.

\bibitem{MR2000e:11087}
Graham Everest and Thomas Ward.
\newblock{\em\htmladdnormallink{Heights of polynomials and entropy in algebraic dynamics}{http://www.mth.uea.ac.uk/heights/}},
\newblock Springer-Verlag London Ltd., London, 1999; MR~2000e:11087.

\bibitem{ghosh}
A. Ghosh.
\newblock{The distribution of $\alpha p^2$ modulo one}
\newblock{\em\htmladdnormallink{Proc. London Math. Soc.}{http://www.uk.cambridge.org/journals/plm/}} (3) {\bf42}, 225-269 (1981); MR~82j:10067.

\bibitem{MR81i:10002}
G.~H. Hardy and E.~M. Wright.
\newblock{\em An Introduction to the Theory of Numbers}.
\newblock The Clarendon Press Oxford University Press, New York, fifth edition,
1979; MR~81i:10002.

\bibitem{harman}
G. Harman.
\newblock{Trigonometric sums over primes I}
\newblock{\em Mathematika}, {\bf28}, 249-254 (1981); MR~83j:10045.

\bibitem{kor}
Ki Hang Kim, Nicholas S. Ormes and Fred W. Roush.
\newblock {The spectra of nonnegative integer matrices
via formal power series}.
\newblock{\em\htmladdnormallink{J. Amer. Math. Soc.}{http://www.ams.org/jams/}}, {\bf13}, 773--806 (2000); MR~2001g:15013.

\bibitem{koblitz}
Neal Koblitz.
\newblock{\em $p$-adic Numbers, $p$-adic Analysis, and
Zeta-Functions}.
\newblock Springer-Verlag, New York, 1977; MR~57\#5964.

\bibitem{MR90a:28031}
D.~A. Lind and T.~Ward.
\newblock Automorphisms of solenoids and $p$-adic entropy.
\newblock{\em\htmladdnormallink{Ergodic Theory Dynamical Systems}{http://uk.cambridge.org/journals/ets/}}, {\bf8}(3), 411--419, 1988;
MR~90a:28031.

\bibitem{LM}
Douglas Lind and Brian Marcus.
\newblock{\em
\htmladdnormallink{An {I}ntroduction to {S}ymbolic {D}ynamics and {C}oding}{http://www.math.washington.edu/SymbolicDynamics/}}.
\newblock{Cambridge University Press}, Cambridge, 1995;
MR~97a:58050.

\bibitem{pm}
Patrick Moss
\newblock{\em The Arithmetic of Realizable Sequences}
\newblock{PhD Thesis, University of East Anglia}, 2003.

\bibitem{puri}
Y.~Puri.
\newblock{\em
\htmladdnormallink{Arithmetic of Numbers of {P}eriodic Points}{http://www.mth.uea.ac.uk/admissions/graduate/theses/yash_puri/outline.pdf}}.
PhD. thesis, Univ. East Anglia, (2001),
www.mth.uea.ac.uk/admissions/graduate/phds.html

\bibitem{puri-ward}
Y.~Puri and T.~Ward.
\newblock{Arithmetic and growth of periodic orbits}
\newblock{\em\htmladdnormallink{Journal of Integer Sequences}{http://www.math.uwaterloo.ca/JIS/}}, {\bf 4}, 01.2.1 (2001); MR~2002i:11026.

\bibitem{puri-ward-2}
Y.~Puri and T.~Ward.
\newblock{A dynamical property unique to the Lucas sequence}
\newblock{\em\htmladdnormallink{Fibonnaci Quarterly}{http://www.sdstate.edu/~wcsc/http/fibhome.html}}, {\bf 39}(5), 398-402 (2001). 

\bibitem{MR92k:11011}
A. J. van der Poorten.
\newblock Some facts that should be better known, especially about
rational functions.
\newblock{\em Number theory and applications
(Banff, AB, 1988)}, {497--528} (1989). {Kluwer Acad. Publ.},
{Dordrecht}; MR~92k:11011.

\bibitem{oes}
N. J. A. Sloane
\newblock{\em\htmladdnormallink{The On-Line Encyclopedia of Integer Sequences}{http://www.research.att.com/~njas/sequences/}};
MR~95b:05001.

\bibitem{vaughan}
R. Vaughan.
\newblock On the distribution of $p\alpha$ modulo one
\newblock {\em Mathematika}, {\bf 24}, 135-141 (1977);
MR~57\#12423.

\bibitem{vino}
I. M. Vinogradov.
\newblock{A new estimation of a trigonometric sum
involving primes}
\newblock{\em Bull. Acad. Sc. URSS Ser. Math.}, {\bf2}, 1--13 (1938).

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: 11G07, 37B40 .\ \

\noindent \emph{Keywords:  periodic points, dynamical systems, linear recurrences,
Bernoulli numbers, realizable sequences}


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A000225},
\seqnum{A000204},
\seqnum{A001945},
\seqnum{A000045},
\seqnum{A001644},
\seqnum{A002445},
\seqnum{A006953},
\seqnum{A001067},
\seqnum{A000928}.)


\vspace*{+.1in}
\noindent
Received October 18, 2002;
revised version received  November 12, 2002.
Published in {\it Journal of Integer Sequences} November 13, 2002.
\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.

\vskip .1in


\end{document}

.