<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\DeclareMathOperator{\lcm}{lcm}

\begin{document}

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

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}

\begin{center}
\vskip 1cm{\LARGE\bf
On (Almost) Realizable Subsequences \\
\vskip .1in
of Linearly Recurrent Sequences}
\vskip 1cm
\large
Florian~Luca\\
School of Mathematics\\
University of the Witwatersrand \\
1 Jan Smuts Avenue \\
Braamfontein 2050\\
Johannesburg \\
South Africa\\
and\\
Max Planck Institute for Software Systems\\
Saarland Information Campus E1 5\\
66123 Saarbr\"ucken \\
Germany\\
and\\
Centro de Ciencias Matem\'aticas UNAM\\
Morelia \\
M\'exico\\
\href{mailto:florian.luca@wits.ac.za}{\tt florian.luca@wits.ac.za}\\
\ \\
Thomas Ward\\
Department of Mathematical Sciences\\
Durham University\\
Durham DH1 3LE \\
England\\
\href{mailto:tbward@gmail.com}{\tt tbward@gmail.com}\\
\end{center}

\vskip .2 in


\begin{abstract}
We show that if~$(u_n)_{n\geq 1}$ is a simple linearly recurrent sequence of integers whose minimal recurrence of order~$k$ involves
only positive coefficients that has positive initial terms,
then~$(Mu_{n^s})_{n\geq 1}$ is the sequence of periodic point
counts for some map for a suitable positive
integer~$M$ and~$s$ any sufficiently large multiple
of~$k!$. This extends a result of Moss and Ward who proved the same result for
the Fibonacci sequence.
\end{abstract}

\section{Introduction}

A sequence of nonnegative integers~$(a_n)_{n\geq 1}$
is called \emph{realizable} if there is some set~$X$ and a
map~$T\colon X\to X$ such that
\begin{equation*}
a_n={\text{\rm Fix}}(T^n)=\#\{x\in X\mid T^n(x)=x\},
\end{equation*}
and is called \emph{almost realizable} if
it is realizable after multiplication by a positive
integer.

A simple example of realizability is the
shift map~$T\colon(x_n)_{n\in {\mathbb Z}}\mapsto (x_{n+1})_{n\in {\mathbb Z}}$
on the {\it golden mean} shift space
$$
X=\{{\bf x}=(x_n)_{n\in {\mathbb Z}}\in \{0,1\}^{\mathbb Z}
\mid(x_k,x_{k+1})\ne (1,1)~\text{for~all}~k\in\mathbb Z\}.
$$
This has
\begin{equation}\label{equationLucasExample}
{\text{\rm Fix}}(T^n)=\#\{{\bf x}\in X\mid T^n({\bf x})={\bf x}\}={\text{\rm Trace}}\left(\begin{matrix} 1 &amp; 1\\ 1 &amp; 0\end{matrix}\right)^n=L_n
\end{equation}
where~$(L_n)_{n\geq 1}=(1,3,4,7,\ldots)$ is the Lucas companion~\seqnum{A000204}
of the Fibonacci sequence;
we refer to Puri and Ward~\cite{MR1866354} for more on this example.

A simple example of almost realizability is given by~\seqnum{A000079},
namely the
sequence
\[
(2^{n-1})_{n\geq 1}=(1,2,4,\dots)
\]
of powers of~$2$. Clearly this is not realizable, since
a map~$T$ witnessing this would have the property that~${\rm{Fix}}(T)=1$,
and hence must have~${\rm{Fix}}(T^2)$ odd.
However the shift map as above on the
\emph{full~$2$-shift}~$X=\{0,1\}^{\mathbb{Z}}$
has~${\rm{Fix}}(T^n)=2^n$ for all~$n\geq 1$,
showing that the sequence becomes realizable after
multiplication by~$2$.
We refer to Moss and Ward~\cite{MT}
for this and other examples,
and the references therein for background on this concept.

Our purpose here is to show that for a large class
of linear recurrence sequences the subsequence
obtained by sampling along a sufficiently large
power of the index is almost realizable.

\section{Realizable subsequences}

Realizable sequences can be characterized
in algebraic terms as follows. The sequence~$(a_n)_{n\geq 1}$
of non-negative integers is realizable
if and only if it satisfies the following two conditions:
\begin{itemize}
\item[(D)] $\displaystyle\sum_{d\mid n}\mu(n/d)a_d\equiv 0$
(mod~$n$) for all~$n\in{\mathbb N}$, and
\item[(S)] $\displaystyle\sum_{d\mid n} \mu(n/d)a_d\geq 0$ for all~$n\in {\mathbb N}$.
\end{itemize}
Here~$\mu$ denotes the classical M\"obius function.
We call~(D) the \emph{Dold condition} and~(S) the \emph{sign condition}.
The equivalence is clear, because the sum arising in~(D)
and in~(S) is the number of points that lie
on a closed orbit of minimal length~$n$ under iteration of
a map that witnesses realizability of~$(a_n)_{n\geq 1}$.

We write~$(F_n)_{n\geq 1}$
for~\seqnum{A000045},
namely the Fibonacci sequence~$(1,1,2,\dots)$.
Moss~\cite{pm} showed that~$(5F_{n^2})_{n\geq 1}$,
the sequence~\seqnum{A054783} multiplied by~$5$, is realizable.
Moss and Ward~\cite{MT} extended this
to show that~$(5F_{n^{2k}})_{n\geq 1}$, is realizable
for~$k\geq 1$
while~$(MF_{n^{2k+1}})$ is not realizable for any
choice of~$M=M_k\geq 1$ for any~$k\geq 0$. These arguments use
congruence properties specific to the Fibonacci sequence,
which makes one wonder to what extent such a result
can be extended to other linearly recurrent sequences.

Here we generalize the above result to simple linearly recurrent sequences
satisfying some positivity conditions. Our result is quite general, and its proof uses elementary algebraic number theory rather than congruences
specific to a given sequence.

Let~$(u_n)_{n\geq 1}$ be a linearly recurrent sequence
of integers of order~$k$. That is, it satisfies a recurrence relation of the form
$$
u_{n+k}=a_1u_{n+k-1}+\cdots+a_k u_{n}
$$
for all~$n\geq 1$,
where~$a_1,\ldots,a_k,u_1,\ldots,u_k$ are all integers
(this is a harmless assumption for
integer linear recurrences by
Fatou's lemma~\cite[p.~369]{MR1555035}). We assume that the recurrence is minimal, so in particular~$a_k\ne 0$.
We ask if there is a monomial~$f\in {\mathbb Z}[X]$ and a positive integer~$M$
with the property that~$(Mu_{f(n)})_{n\geq 1}$ satisfies~(D) and~(S).
Let
\begin{equation*}\label{eq:F}
F(X)=X^k-a_1X^{k-1}-\cdots-a_k
\end{equation*}
be
the \emph{minimal polynomial} of
the sequence~$(u_n)_{n\geq 1}$. For background and relevant properties of linearly recurrent sequences the reader is invited to consult the
monograph of Everest et al.~\cite{MR1990179}.
Let~${\mathbb K}$ be the splitting field of~$F$
and~${\mathcal O}_{\mathbb K}$ be
its ring of integers. Let~$\Delta({\mathbb K})$ be the discriminant
of~${\mathbb K}$ and let~$\Delta(F)$ be the discriminant of~$F$. Let~$G$ be the Galois
group of~${\mathbb K}$ over~${\mathbb Q}$,
let~$e(G)$ be the exponent of~$G$, and let~$N$ be the order of~$G$.

\begin{theorem}\label{thm:1}
Assume that~$F$ has only simple zeros.
\begin{itemize}
\item[{\rm{(i)}}] The sequence~$(Mu_{n^s})_{n\geq 1}$ satisfies~{\rm{(D)}}
if~$M$ is a positive integer which is a multiple of~$\lcm(\Delta({\mathbb K}), \Delta(F))$ and~$s\geq N$ is a multiple of~$e(G)$.
\item[{\rm{(ii)}}]  Assume in addition that~$a_i\geq 0$ for~$i=1,\ldots,k$
and~$a_k\ne 0$, that
$$
(a_1,\ldots,a_k)\ne (0,0,\ldots,1),
$$
and that~$u_i\geq 1$ for all~$i\in \{1,2,\ldots,k\}$.
Then the sequence~$(Mu_{n^s})_{n\geq 1}$ satisfies~{\rm(S)} whenever~$s=\ell e(G)$
where~$\ell\geq \ell_0$ is a sufficiently large
number which can be computed in terms of the sequence~$(u_n)_{n\geq 1}$.
\end{itemize}
\end{theorem}

The somewhat strange condition~(i) can be explained as follows.
The condition~$\Delta(F)\mid M$ is needed to ensure that
the summands involved in the Binet formula
for the general term of~$Mu_n$ are algebraic integers.
On the other hand, the additional conditions that~$\Delta({\mathbb K})\mid M$ together with the conditions on~$s$
are sufficient to ensure that the Dold condition~(D) is satisfied.
In particular, if~$F$ is irreducible, then~$\Delta({\mathbb K})\mid\Delta(F)$,
so it suffices that~$M$ is a multiple of~$\Delta(F)$.
This is not the case for reducible polynomials as the example
$$
F(X)=(X^2-2)(X^3-5)
$$
shows.
In this case~${\mathbb K}={\mathbb Q}({\sqrt{2}}, {\sqrt[3]{5}},{\sqrt{-3}})$ has~$\Delta(F)=-2^3\cdot 3^3\cdot 5^2\cdot 17^2$,
which is not a multiple of~$\Delta({\mathbb K})=2^{18} 3^{14} 5^8$.

\begin{remark}
\leavevmode
\begin{itemize}
\item[(a)] We have to exclude
a periodic sequence of period~$k\geq 2$ and minimal polynomial~$X^k-1$,
since for it the theorem is not true in general. Indeed,
consider the simplest case when~$k$ is prime. Then condition~(S)
requires that~$u_{k^{s}}-u_1\geq 0$.
On the other hand, since~$k^s\equiv k$ (mod~$k$),
we must have~$u_k\geq u_1$.
It follows that~$u_1,\ldots,u_k$ cannot be chosen to be
arbitrary positive integers.

\item[(b)] We
require the minimal polynomial to only have simple roots,
for otherwise~(D) may be false.
For example, the sequence
defined by~$u_n=n$ for all~$n\geq 1$
satisfies the linear recurrence~$u_{n+2}=2u_{n+1}-u_n$
with minimal polynomial~$(X-1)^2$.
Then condition~(D) for~$(Mu_{n^s})$
implies that for a prime~$p$ we must
have~$p\mid M(p^s-1)$,
and for given positive integers~$M$ and~$s$
this can only hold for the finitely many primes~$p$
dividing~$M$. Hence, for the above sequence, the Dold quotients
\begin{equation*}
\frac{1}{n}\sum_{d\mid n} \mu(n/d)a_d
\end{equation*}
for~$n\geq1$
are rational numbers whose denominators are
divisible by arbitrarily large primes.
Similar arguments are used
by Puri and Ward~\cite[Lem.~2.4]{MR1873399}
to show
that if~$(f(n))_{n\geq 1}$ is realizable
with~$f\in\mathbb{Z}[X]$,
then~$f$ is a constant.

\item[(c)] A different (arguably more natural)
question is to ask when a linear recurrence sequence
itself satisfies~(D) without
multiplication by a factor or passing to a subsequence.
Minton~\cite{MR3195758} showed
that---up to a finite multiplying factor---this
is possible if and only if the sequence is a linear
combination of traces of powers of algebraic numbers.
From this perspective~\eqref{equationLucasExample} is a
manifestation of the fact that the only linearly
recurrent sequences satisfying the Fibonacci
recurrence~$u_{n+2}=u_{n+1}+u_n$ for~$n\geq 1$ which have
this property must have~$u_2=3u_1$ (and hence
must be multiples of the Lucas sequence),
a special case shown earlier by
Puri and Ward~\cite{MR1866354}
using congruences specific to the Fibonacci
sequence.
\end{itemize}
\end{remark}

Returning to the Fibonacci sequence
where this phenomena was first observed,
the sequence~$(F_{n})_{n\geq 1}$
has~$k=2$,~$a_1=a_2=1$,~$F_1=F_2=1&gt;0$,
and minimal polynomial~$F(X)=X^2-X-1$.
Further,~${\mathbb K}={\mathbb Q}[{\sqrt{5}}]$.
Thus,~$\Delta(F)=\Delta({\mathbb K})=5$
and~$G={\mathbb Z}/2{\mathbb Z}$ so
$e(G)=N=2$. Thus,~$s=2$ satisfies that~$s$ is a multiple of~$e(G)$ and~$s\geq N$.
We shall justify the claim that in this case we can take~$\ell_0=1$, recovering
the result of Moss and Ward~\cite{MT} precisely. In fact,
we prove it in a more general setting.
Let~$(F_n^{(k)})_{n\geq-(k-2)}$ be
the~$k$-generalized Fibonacci sequence
satisfying the recurrence
relation~$F_{n+k}^{(k)}=F_{n+k-1}^{(k)}+\cdots+F_n^{(k)}$
for~$n\geq 2-k$
with initial values~$F_i^{(k)}=0$ for~$i=2-k,~3-k,\ldots,-1,~0$ and~$F_1^{(k)}=1$. Wolfram~\cite{MR1622060} conjectured that~$G=S_k$ is
the full symmetric group on~$k$ letters,
and this is known to be so when~$k$ is even,
when~$k$ is small, or
when~$k$ is prime. These claims are shown in
work of Martin~\cite{MR2043329}, for example.
We therefore take~$N_k:=k!$; this is a multiple of~$e(G)$ and at least as large as~$N$.

\begin{theorem}
\label{thm:2}
For~$k\geq 2$
we can take~$s=N_k\ell$ for any~$\ell\geq 1$
for the~$k$-generalized
Fibonacci sequence~$(F_{n}^{(k)})_{n\geq 1-(k-2)}$.
\end{theorem}

Moss and Ward~\cite{MT} propose the following conjecture
at the end of their paper.

\begin{conjecture}\label{Conj}
Let~$P,~Q\in {\mathbb Z}$
and let~$u_{n+2}=Pu_{n+1}-Qu_n$ for~$n\geq 1$,
with initial conditions~$u_0=0,~u_1=1$. Then~$((P^2-4Q)u_{n^2})_{n\geq 1}$
satisfies~{\rm{(D)}}.
\end{conjecture}

This almost follows from Theorem~\ref{thm:1},
except that there are some additional hypotheses
like the fact that the recurrence must be of minimal
order~$k=2$ and that~$(P,Q)\ne (0,-1)$, in order to apply the theorem.
We therefore supply a proof of the following result.

\begin{theorem}
\label{thm:3}\label{conj}
Conjecture~\ref{Conj} holds.
\end{theorem}

\section{Proofs of theorems}

\begin{proof}[Proof of Theorem~\ref{thm:1}]
To start with, let
$$
F(X)=\prod_{i=1}^k (X-\lambda_i),
$$
so that we have the (generalized) Binet formula
$$
u_n=\sum_{i=1}^k c_i\lambda_i^{n-1}
$$
for all~$n\geq 1$
for coefficients~$c_1,\ldots,c_k$
determined from~$u_1,\ldots,u_k$
by solving a linear system of~$k$ equations in~$k$ unknowns
whose matrix is Vandermonde on~$\lambda_1,\ldots,\lambda_k$.
We write~${\mathbb K}:={\mathbb Q}(\lambda_1,\ldots,\lambda_k)$.
Then~$c_1,\ldots,c_k$ are algebraic numbers in~${\mathbb K}$
having
the Vandermonde determinant~${\sqrt{\Delta(F)}}$
(for a certain determination of the square root)
as a common denominator
in the sense that~${\sqrt{\Delta(F)}}c_i$
is an algebraic integer for each~$i=1,\ldots,k$. Note that~$Mc_i$ is a multiple of the algebraic integer~${\sqrt{\Delta({\mathbb K})}}$, which is an algebraic integer in~${\mathcal O}_{\mathbb K}$.

We next turn to the Dold condition.
We say that a sequence of algebraic
integers~$(v_n)_{n\geq 1}$ satisfies the
\emph{algebraic Dold condition} if~(D)
is satisfied as algebraic integers. That is, if
$$
\frac{1}{n}\sum_{d\mid n} \mu(n/d)v_d
$$
is an algebraic integer
for all~$n\geq 1$.
Our strategy is to find~$s$
such that~$(\sqrt{\Delta({\mathbb K})}\lambda_i^{n^s-1})_{n\geq 1}$ satisfies the algebraic
Dold condition for~$i=1,\ldots,k$.
Since linear combinations with algebraic integer
coefficients of sequences which satisfy
the algebraic Dold condition also satisfy the
algebraic Dold condition, this allows us
to deduce that
$$
M\frac{{\sqrt{\Delta({\mathbb K})}}}{n} \sum_{d\mid n} \mu(n/d)u_{d^s}=M\sum_{i=1}^k c_i\frac{{\sqrt{\Delta({\mathbb K})}}}{n}\sum_{d\mid n} \mu(n/d)\lambda_i^{d^s-1}
$$
is both a rational number and an algebraic integer, so an integer,
verifying~(D).

Fix~$\lambda:=\lambda_i$ for some~$i=1,\ldots,k$.
We need to find out when
\begin{equation}\label{eq:algDoldargument1}
\frac{\sqrt{\Delta({\mathbb K})}}{n} \sum_{d\mid n} \mu(n/d) \lambda^{d^s-1}
=
\frac{{\sqrt{\Delta({\mathbb K})}}}{n} \sum_{d\mid n} \mu(d) \lambda^{(n/d)^s-1}
\end{equation}
is an algebraic integer
in~${\mathcal O}_{\mathbb K}$ for all~$n\geq 1$.
We write~$m:=\prod_{p\mid n} p={\text{\rm rad}}(n)$ for the radical of~$n$.
Changing the order of summation to
complementary divisors as shown and
restricting to squarefree numbers
in the summation on the
right-hand side (as the M\"obius function
vanishes on all other terms), the numerator
in~\eqref{eq:algDoldargument1} is
\begin{equation*}\label{eq:algDoldargument2}
S:={\sqrt{\Delta({\mathbb K})}}\sum_{d\mid m} \mu(d) \lambda^{(n/d)^s-1}.
\end{equation*}
Clearly~$S$ is an algebraic integer,
so we may assume that~$n$ (and hence~$m$) exceeds~$1$.
Let~$p$ be a prime divisor of~$n$ and let~$w$ be the exact exponent of~$p$ in~$n$,
written~$p^w\| n$.
Writing as usual~$\omega(n)$ for the number
of distinct prime divisors of~$n$,~$m$
has~$2^{\omega(n)}$ divisors, half of which
are multiples of~$p$ and half of which are not.
Thus the above sum can be grouped into~$2^{\omega(n)-1}$
pairs indexed~$(d,p)$, where~$d$ is a divisor of~$\frac{m}{p}$,
giving
\begin{align*}
S &amp; =  {\sqrt{\Delta({\mathbb K})}}\sum_{d\mid\frac{m}{p}} \left(\mu(d) \lambda^{(n/d)^s-1}+\mu(pd) \lambda^{(n/(dp))^s-1}\right)\\
&amp; =  {\sqrt{\Delta({\mathbb K})}}\sum_{d\mid\frac{m}{p}}\pm \lambda^{(n/(pd))^s-1}\left(\lambda^{(n/pd)^s(p^s-1)}-1\right).
\end{align*}
Thus,
it is sufficient to show that if~$p^w\| n$, then~$\frac{S}{p^w}$ is an algebraic integer. We let~$\pi$ be a prime ideal divisor of~$N$
in~${\mathbb K}$ with~$\pi^e\| p$ and~$N_{{\mathbb K}/{\mathbb Q}}(\pi)=p^f$. We put
\begin{align*}
A_d&amp;:=\lambda^{(n/dp)^s}
\intertext{and}
B_d&amp;:=\lambda^{(n/pd)^s(p^s-1)}-1,
\end{align*}
and observe that our aim is to find a condition for~$s$ divisible by~$e(G)$ such that one would have
$$
\nu_{\pi}({\sqrt{\Delta({\mathbb K})}}A_dB_d)\geq ew.
$$
Here,~$\nu_{\pi}(\alpha)$ is the exponent of the prime ideal~$\pi$ in the factorization of~$\alpha{\mathcal O}_{\mathbb K}$.
Observe that the different theorem implies that
$$
\nu_{\pi}(\Delta({\mathbb K}))\geq fe(e-1)\geq e(e-1).
$$

Consider first the case~$\pi\mid\lambda$.
In this case~$\nu_{\pi}(B_d)=0$ and
$$
\nu_{\pi}(A_d)\geq \left(\frac{n}{pd}\right)^s\geq p^{s(w-1)}\geq 2^{s(w-1)}.
$$
We need to check that
$$
2^{s(w-1)}+e(e-1)/2\geq ew.
$$
This is clear when~$w=1$,
since then the inequality to be proved becomes
\begin{equation*}
1+e(e-1)/2\geq e
\end{equation*}
which holds for all~$e\geq 1$.
This is also clear when~$e=1$ since in that case
it is implied by~$2^{s(w-1)}\geq 2^{w-1}\geq w$.
Finally, if~$e\geq 2,~w\geq 2$, then~$s\geq N\geq e\geq 2$,
so~$sw\geq 4$. Since~$w-1\geq w/2$, it suffices to show
that~$2^{sw/2}\geq sw$, which is equivalent to~$2^{sw}\geq (sw)^2$,
which holds since~$sw\geq 4$.

We next consider the case~$\pi\!\nmid\!\lambda$.
In this case,~$\nu_{\pi}(A_d)=0$. Write~$(n/pd)^s=\alpha p^{s(w-1)}$, and~$p^s-1=\beta(p^f-1)$, where~$\pi\nmid \alpha\beta$. This last formula holds since~$f\mid e(G)\mid s$.
The analogue of Euler's theorem for number fields implies
\begin{equation}
\label{eq:Euler}
\lambda^{p^f-1}\equiv 1\pmod {\pi}.
\end{equation}
By induction on~$j\geq 0$, we prove that
\begin{equation}
\label{eq:Euler1}
\lambda^{p^j(p^f-1)}\equiv 1\pmod {\pi^{j+1}}.
\end{equation}
Indeed, the case~$j=0$ is just \eqref{eq:Euler}. Assuming congruence \eqref{eq:Euler1} is satisfied for~$j\geq 0$, we write
$$
\lambda^{p^j(p^f-1)}=1+\gamma
$$
for some~$\gamma\in \pi^{j+1}$
and raise it to power~$p$ to get
\begin{align*}
\lambda^{p^{j+1}(p^f-1)}
&amp;=
(1+\gamma)^{p}\\
&amp;=
1+\sum_{k=1}^{p-1} \binom{p}{k}\gamma^k+\gamma^{p}\\
&amp;\equiv
1\pmod {\pi\gamma}\\
&amp;\equiv
1\pmod {\pi^{j+2}},
\end{align*}
proving the induction step. Evaluating this at~$j=s(w-1)$, we get
$$
\lambda^{p^{s(w-1)}(p^f-1)}\equiv 1\pmod {\pi^{s(w-1)+1}}.
$$
Raising the above congruence to the power~$\alpha\beta$, we deduce that
$$
\nu_{\pi}(B_d)\geq s(w-1)+1.
$$
So, it suffices to verify that
$$
s(w-1)+1+e(e-1)/2\geq ew.
$$
This is clear if~$w=1$ since then the left--hand side is~$1+e(e-1)/2\geq e$. It is also clear if~$e=1$, since then the left--hand side is~$s(w-1)+1\geq (w-1)+1=w$.
Thus, we assume that~$e\geq 2$ and~$w\geq 2$. Since~${\mathbb K}$ is Galois,
we have that~$e\mid N$ and~$s\geq N$. If~$s\geq 2e$, then it suffices to show that
$$
2e(w-1)+1\geq ew.
$$
This is equivalent to~$ew-2e+1\geq 0$, which holds since~$w\geq 2$.
Finally, if~$2e&gt;s\geq N$, we have that~$e&gt;N/2$ and~$e$ is a divisor of~$N$ so,
in fact~$s=e=N$. So, we need to show that
$$
N(w-1)+1+N(N-1)/2\geq Nw,
$$
which is equivalent to~$1+N(N-1)/2\geq N$, which obviously holds for any~$N\geq 2$
(note that~$N\geq 2$ since we are in the case~$e\geq 2$).

We still need to deal with the sign condition~(S), for
which we use the following observation from
Puri's thesis~\cite{Pu}:
It is sufficient
to show that~$u_{(2n)^s}\geq n u_{n^s}$
for all~$n\geq 1$.
To see this, let~$\lambda$ be a real root
larger than~$1$ of~$F(X)=0$.
This exists by the intermediate
value theorem, since the hypotheses on
the coefficients~$a_1,\dots,a_k$ show that~$F(1)&lt;0$, and~$F(x)\to\infty$
as~$x\to\infty$.
Note that~$u_n\geq \lambda^{n-k}$ always holds,
again by the hypotheses on the coefficients.
Indeed, it holds for~$n=1,\ldots,j$
because in this range~$u_j\geq 1\geq \lambda^{j-k}$,
and so it holds for all~$n\geq 1$ by induction
since~$a_i\geq 0$ for~$i=1,\ldots,k$.
Moreover,~$u_n\leq \lambda^{n+n_0}$
for
\begin{equation*}
n_0\geq\log\max\{u_1,\ldots,u_k\}/\log \lambda.
\end{equation*}
Again this inequality holds for~$n=1,\ldots,k$,
so it will hold for all~$n\geq 1$
by induction.
Armed with these estimates, we now need to show that
$$
\lambda^{(2n)^s-k}\geq n\lambda^{n^s+n_0}
$$
or, equivalently, that
\begin{equation}
\label{eq:n0}
n^s(2^s-1)\geq k+n_0+\frac{\log n}{\log\lambda}.
\end{equation}
To see this, first let~$n_1\geq 2(n_0+k)$
satisfy~$\frac{\log n}{\log\lambda}\leq\frac{n}{2}$
for~$n\geq n_1$.
Then for~$n\geq n_1$
we have~$k+n_0\leq\frac{n_1}{2}\leq\frac{n}{2}$,
so the right-hand side of~\eqref{eq:n0} is
at most~$n$.
It follows that~\eqref{eq:n0} holds, since~$n(2^s-1)\geq n$
is clear.
For~$1\le n\leq n_1$
the right-hand side is at most~$n_0+k+\frac{\log n_1}{\log\lambda}$
and the left-hand side is at least~$2^s-1\geq 2^{e(G)\ell}-1$ and this is larger
than~$n_0+k+\frac{\log n_1}{\log\lambda}$
once~$\ell\geq\ell_0$. Thus in all cases
if~$s$ is a sufficiently large multiple of~$e(G)$,
then the sign condition~(S) holds.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:2}]
For the particular case of the~$k$-generalized Fibonacci sequence,
it is well-known that the associated
minimal polynomial
$$
F^{(k)}(X)=X^k-X^{k-1}-\cdots-1
$$
has simple zeros by work of Miles~\cite{MR123521}, and
that the largest real zero~$\lambda^{(k)}$
is increasing in~$k\geq 2$ and has~$\lambda^{(k)}\to2$
as~$k\to\infty$.
In particular,
writing
$$
\lambda=\lambda^{(k)}\geq\lambda^{(2)}=\frac{1+\sqrt{5}}{2}
$$
we have~$F_k^{(k)}&lt;2^k&lt;\lambda^{2k}$, so we can take~$n_0=2k$
in the notation of the sign condition step.
Thus the condition is that~$n_1\geq 2(n_0+k)=6k$
must be such that~$\frac{\log n}{\log\lambda}\leq\frac{n}{2}$
for~$n\geq n_1$,
which is a consequence of~$6\log n\leq n$, which
certainly
holds for~$n\geq 10k\geq 20$. So we are able to take~$n_1=10k$.
Consequently, for~$n\leq n_1$, the right-hand
side in~\eqref{eq:n0} is at most~$10k$ and the left-hand side
is at least~$n^s(2^s-1)\geq n^{N_k}(2^{N_k}-1)\geq 10k$
for all~$n\geq 1$ and~$k\ge~3$
where~$N_k=k!$. For~$k=2$,
the above inequality
fails for~$n=1,2$, but in these
cases~$F_{(2n)^2}\geq F_4=3&gt; 2F_2$ holds anyway.
Hence, we can take~$\ell_0=1$ for any~$k\geq 2$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:3}]

First consider the case~$Q=0$.
In this
degenerate case we may take two approaches
(for non-negative~$P$ at any rate), and we include both to
illustrate the two points of view. If~$P=0$ then
the only realizable sequence is the zero sequence,
so we assume that~$P\geq 1$.

\bigskip
\noindent{{\bf{Arithmetic proof:}}}
We have~$u_n=P^{n-1}$, so~$c_1=1/P$
in Binet's formula and~$\lambda=P$.
Going through the proof of Theorem~\ref{thm:1},
we see that we need~$P\mid M$ to deal with the denominator of~$c_1$.
Next, in case~$p$ does not divide~$P$, we are in the case
of~$\pi\!\nmid\!\lambda$, and then~$p^w\mid S$
whenever~$p^w\mid n$. In the case of~$\pi\mid\lambda$
above, we have that
if~$p\mid P$, then~$e=N=1$. We saw in the proof of Theorem~\ref{thm:1}
for this case that if~$p\mid P$ and~$w\geq 2$, then~$\nu_p(A_d)\geq 2^{w-1}&gt;w$, whereas for~$w=1$,
we have~$\nu_p(A_d)\geq 1=w.$ So, in fact we even
see that~$(|P|u_{n^2})_{n\geq 1}$
satisfies the Dold condition in this case, and we do not need the factor~$P^2$.

\bigskip
\noindent{\bf{Dynamical proof for positive~$P$:}}
Here~$(Pu_n)_{n\geq 1}$
is the sequence~$(P,P^2,\dots)$,
which we identify as~$({\text{\rm Fix}}(T^n))_{n\geq 1}$,
where~$T\colon X\to X$ is the shift map
on the {full~$P$-shift}.
Taking the union of~$P$ disjoint copies of
this system produces a map~$S$ with
\[
({\text{\rm Fix}}(S^n))_{n\geq 1}
=(P^2,P^3,P^4,\dots).
\]
It follows that~$(P^2u_n)_{n\geq 1}$
is realizable, and in particular satisfies~(D).
On the other hand, sampling along a monomial subsequence
always preserves
realizability,
so~$(P^2u_{n^2})$ is also realizable.
Work of Jaidee, Moss, and
Ward~\cite{MR4002553} shows that no other polynomials have this property.

We next turn to the case~$(P,Q)=(0,-1)$.
This is an excluded case of
Theorem~\ref{thm:1}. In this case,~$u_n=0$
if~$n$ is even and~$u_n=1$ if~$n$ is odd.
So, in~(D), the sum~$S$ is zero if~$n$ is odd.
Further, in the sum~$S$, for every prime~$p$ dividing~$m$,
the amounts~$(n/d)^2$ and~$(n/(pd))^2$ are both even or both
odd, so this difference is zero
unless~$p=2$ and one of~$(n/d)^2$ and~$(n/(2d))^2$
is even and the other is odd.
But the only chance for this to happen is when~$2\| n$,
and in this last case the prime~$2$ from the denominator of the Dold ratio can be absorbed into~$|\Delta(F)|=|P^2-4Q|=4$.

The remaining cases~$(P,Q)\ne (P,0),~(0,-1)$ follow from Theorem~\ref{thm:1}
on noticing that
\begin{equation}
\Delta(F)=P^2-4Q
\end{equation}
is a multiple of~$\Delta({\mathbb K})$.
\end{proof}

\section{Acknowledgments}

We thank the referee for a careful reading of our manuscript and for comments and suggestions that improved the quality of the final version of our paper.

\begin{thebibliography}{10}

\bibitem{MR1990179}
G. Everest, A. van~der Poorten, I. Shparlinski, and T. Ward, {\em
  Recurrence Sequences}, Vol.\ 104 of {\em Mathematical Surveys and Monographs},
  American Mathematical Society, 2003.

\bibitem{MR1555035}
P.~Fatou, S{\'e}ries trigonom{\'e}triques et s{\'e}ries de {Taylor}, {\em Acta
  Math.} {\bf 30} (1906), 335--400.

\bibitem{MR4002553}
S. Jaidee, P. Moss, and T. Ward, Time-changes preserving zeta
  functions, {\em Proc. Amer. Math. Soc.} {\bf 147} (2019), 4425--4438.

\bibitem{MR2043329}
P.~A. Martin, The {Galois} group of {{\(x^{n}-x^{n-1}-\cdots-x-1\)}}, {\em
  J. Pure Appl. Algebra} {\bf 190} (2004), 213--223.

\bibitem{MR123521}
E.~P. Miles, Generalized {Fibonacci} numbers and associated matrices, {\em Amer. Math. Monthly} {\bf 67} (1960), 745--752.

\bibitem{MR3195758}
G.~T. Minton, Linear recurrence sequences satisfying congruence
  conditions, {\em Proc. Amer. Math. Soc.} {\bf 142} (2014), 2337--2352.

\bibitem{pm}
P. Moss, {\em The Arithmetic of Realizable Sequences}, PhD thesis,
  University of East Anglia, 2003.

\bibitem{MT}
P. Moss and T. Ward, Fibonacci along even powers is (almost) realizable,
  {\em Fibonacci Quart.} {\bf 60} (2022), 40--47.

\bibitem{Pu}
Y. Puri, {\em Arithmetic of Numbers of Periodic Points}, PhD thesis,
  University of East Anglia, 2001.

\bibitem{MR1873399}
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, {\em J.
  Integer Sequences} {\bf 4} (2001), 
  \href{https://cs.uwaterloo.ca/journals/JIS/VOL4/WARD/short.html}{Article 01.2.1}.

\bibitem{MR1866354}
Y. Puri and T. Ward, A dynamical property unique to the {Lucas} sequence,
  {\em Fibonacci Quart.} {\bf 39} (2001), 398--402.

\bibitem{MR1622060}
D.~A. Wolfram, Solving generalized {Fibonacci} recurrences, {\em Fibonacci Quart.}
  {\bf 36} (1998), 129--145.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}: Primary 37P35; Secondary 11B50.

\noindent \emph{Keywords:} linear recurrence sequence, periodic point, Dold congruence.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences 
\seqnum{A000045},
\seqnum{A000073},
\seqnum{A000079},
\seqnum{A000204}, and
\seqnum{A054783}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  March 24 2023;
revised version received  May 4 2023.
Published in {\it Journal of Integer Sequences}, May 5 2023.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                







</pre></body></html>