\documentclass[landscape]{slides}

\usepackage{graphicx}
\usepackage{amsfonts,amssymb,amsbsy,amsmath,amscd,amstext,amsthm}
\usepackage{amsmath,relsize}
\usepackage{graphicx}
\usepackage{float}
\usepackage{epsfig}
\usepackage{pdflscape}
%\textwidth 12.5cm
%\textheight 19cm

\frenchspacing \sloppy
\newcommand {\Q}  {{\mathbb Q}}
\newcommand {\Z}  {{\mathbb Z}}

\newcommand {\C}  {{\mathbb C}}
\newcommand {\D}  {{\mathbb D}}
\newcommand {\R}  {{\mathbb R}}
\newcommand {\PP}  {{\mathbb P}}
%\newcommand {\N}  {{\mathbb N}}
\newcommand {\NN}  {{\mathbb N}}
\newcommand {\GG}  {{\mathbb G}}
\newcommand {\FF}  {{\mathbb F}}
\newcommand {\KK}  {{\mathbb K}}
\newcommand {\BB}  {{\mathfrak B}}
\newcommand {\E}  {{\mathbb E}}
\newcommand {\F}  {{\mathbb F}}
\newcommand {\K}  {{\mathbb K}}
\newcommand {\LL}  {\mathcal{L}}
\newcommand {\V}  {{\mathbb V}}
\newcommand {\All}   {\displaystyle\mathop{\mathlarger{\mathlarger{\mathlarger{\forall}}}}}
\newcommand {\Exists}   {\displaystyle\mathop{\mathlarger{\mathlarger{\mathlarger{\exists}}}}}
\newcommand {\Min}   {\displaystyle\mathop{\min}}
\newcommand {\Floor}[2]{\left\lfloor\frac{#1}{#2}\right\rfloor}
\newcommand {\Remainder}[2]{\left\{\frac{#1}{#2}\right\}}
\newcommand {\abs}[1]{\left|{#1}\right|}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\Nz}{{\mathbb{N}}}
\newcommand {\CRe}[1]{Re\left({#1}\right)}
\newcommand {\CIm}[1]{Im\left({#1}\right)}
\newcommand {\AND}{{\mbox{ }and\mbox{ }}}
\newcommand {\OR}{{\mbox{ }or\mbox{ }}}
\newcommand {\TAU}{\mathlarger{\mathlarger{\mathlarger{\tau}}}}
\newcommand {\Pnt}[3]{\left(#1,#2\right)_{#3}}
\newcommand {\ArrowBoth}[2]{\xRightarrow[#1]{#2}}
\newcommand {\ArrowTop}[1]{\overset{#1}\Rightarrow}
\newcommand {\ArrowBottom}[1]{\underset{#1}\Rightarrow}
\newcommand {\ArrowBottomStar}[1]{\xRightarrow[#1]{*}}
\newcommand {\ArrowBrunotte}[1]{\xRightarrow[#1]{\TAU}}
\newcommand {\ArrowBrunotteStar}[1]{\xRightarrow[#1]{\TAU *}}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}{Corollary}
\begin{document}

\begin{center}
  {\Huge Nearly linear recursive\\[1ex] sequences, especially SRS}\\
   \vspace{1.5cm}
  {\large  Attila Peth\H{o}\\
  University of Debrecen, Hungary}\\
  \vspace{0.8cm}
  Based on a joint works with Shigeki Akiyama, Tsukuba, Japan\\ Jan-Hendrik Evertse, Leiden, The Netherlands, J\"org Thuswaldner and Mario Weitzer, Leoben, Austria

\vspace{0.8cm}

Numeration 2017, \\
Rome, June 6, 2017. \vspace{1.5cm}


\end{center}


\newpage

{\Large 1. Introduction}\\[1ex]

Let $A_0,\dots,A_{d-1}\in \C$.  Let $(a_n)$ be a sequence of complex numbers and define the error sequence $(e_n)$ by the initial terms $e_0=\dots= e_{d-1} = 0$ and
by the equations
$$
e_{n+d} = a_{n+d} +A_{d-1}a_{n+d-1} + \dots + A_0a_n
$$
for $n\ge 0$. We call $(a_n)$ a {\it nearly linear recursive sequence},
in shortcut nlrs, if the sequence $(|e_n|)$ is bounded.

Homogenous and inhomogenous linear recursive sequences, and srs are examples for nlrs.

\newpage

Two aspects:\\[1ex]
1) (Masculine) $(a_n)$ is given, find $A_0,\dots,A_{d-1}\in \C$ and $(e_n)$. Classify the nlrs's. Topic of the first part.\\[1ex]
2) (Feminine) $A_0,\dots,A_{d-1}\in \C$ and $(e_n)$ or a rule for the generation of $(e_n)$ is given. Find all $(a_n)$ satisfying these requirements. Topic of the second part.\\

Let $a_n=1$ and $b_n = 2^n$ for all $n$. $e_{n+1} = a_{n+1} + 0\cdot a_{n}= 1$ as well as $0 =e_{n+1}= a_{n+1}-2a_n$ show that $(a_n), (b_n)$ are nlrs, but they have different "characteristic" polynomials.

Both $(a_n), (b_n)$ satisfy the recursion $0 = a_{n+2} -3 a_{n+1}+ 2 a_n$.
\newpage
{\Large 2. Characteristic polynomial of nlrs}\\[1ex]

Let $(a_n)$ be a nlrs. The set of polynomials $\sum_{j=0}^l B_j x^j \in  \C[x]$
such that the sequence $(\sum_{j=0}^l B_ja_{n+j})$ is bounded is an ideal of $\C[x]$ called {\it the ideal } of $(a_n$). There is a unique, monic polynomial generating the ideal of $(a_n)$, called {\it the characteristic polynomial} of $(a_n)$.


The characteristic polynomial of a linear recurrence sequence (lrs) $(a_n)$ may be different from the characteristic polynomial of $(a_n)$ when viewed as an nlrs.

\newpage

\begin{lemma} Suppose $(a_n)$ is an nlrs with characteristic polynomial $P(x)$. Then\\[0.5ex]
(i) the roots of $P(x)$ all have modulus $\ge 1$.\\
(ii) Assume further that $a_n = O(n)$ holds. Then the roots of $P(x)$ all lie on the unit circle.
\end{lemma}

\newpage
{\Large 3. The Binet-like formula for nlrs}\\[1ex]

Define the function
$$
c(z) = \sum_{j=1}^{\infty} e_{d+j-1} z^{-j}.
$$
Since $(e_n)$ is bounded, $c(z)$ is convergent for all complex $z$
with $|z|>1$.

Denote $(\hat{a}_n)$ the lrs having the initial terms
$\hat{a}_0=\dots = \hat{a}_{d-2}= 0, \hat{a}_{d-1} =1$
and satisfying the recursion
\begin{equation} \label{lrek}
\hat{a}_{n+d} +A_{d-1}\hat{a}_{n+d-1} + \dots + A_0\hat{a}_n =0.
\end{equation}
The lrs $(\tilde{a}_n)$ is defined by the same recursion (\ref{lrek})
with the initial terms $\tilde{a}_j = a_j\ (j=0, \dots, d-1)$.

\newpage

Denote
$$
P(x) = x^d + A_{d-1}x^{d-1}+\dots+ A_0
$$
the common characteristic polynomial of $(\hat{a}_n), (\tilde{a}_n)$ and of $(a_n)$.
Assume that $P(x)$ has $d$ distinct roots $\alpha_1,\dots, \alpha_d$. Then there exists uniquely defined complex numbers $\hat{g}_j, j=1,\dots,d$ with
\begin{equation} \label{Binet}
\hat{a}_n = \hat{g}_1 \alpha_1^n + \dots +\hat{g}_d \alpha_d^n
\end{equation}
for all $n$.

\newpage
%{\small
\begin{theorem} \label{Binet_t}
Assume that the zeroes of $P(x)$ are ordered as $$|\alpha_1|\ge \dots \ge |\alpha_{r_1}|> 1 = |\alpha_{r_1+1}| =\dots =|\alpha_{r_1+r_2}|,\; r_1+r_2=d.$$
Denote by $\tilde{g}_j,\hat{g}_j$ the (constant) coefficients of $\alpha_j^n, j=1,\dots,d$ in the expression \eqref{Binet} of $\tilde{a}_n$ and $\hat{a}_n$ respectively. Then

{\bf (i)} if $r_1>0$ and $r_2=0$ then
$$
a_n = (\tilde{g}_1+\hat{g}_1 c(\alpha_1)) \alpha_1^n + \dots + (\tilde{g}_{r_1}+\hat{g}_{r_1} c(\alpha_{r_1})) \alpha_{r_1}^n +O(1),
$$
{\bf (ii)} if $r_1>0$ and $r_2>0$ then
$$
a_n = (\tilde{g}_1+\hat{g}_1 c(\alpha_1)) \alpha_1^n + \dots + (\tilde{g}_{r_1}+\hat{g}_{r_1} c(\alpha_{r_1})) \alpha_{r_1}^n +O(n),
$$
and in both cases $(\tilde{g}_j+\hat{g}_j c(\alpha_j)) \not=0, j=1\dots,r_1$.\\
{\bf (iii)}  if $r_1=0$ and $r_2>0$ then
$$
a_n = O(n),
$$
\end{theorem}%}


\newpage
{\Large 4. On the growth of nlrs}\\[1ex]

\begin{theorem} \label{growth}
Assume that $r\ge 2$.\\
{\bf (i)} Let $\eta_1,\dots,\eta_r$ be any pairwise distinct
complex numbers lying on the unit circle, and $\gamma_1,\dots,\gamma_r$
any non-zero complex numbers.
Then there exists a constant $d_1>0$ such that
    \begin{equation}\label{eqi}
    |\gamma_1\eta_1^n + \dots + \gamma_r\eta_r^n|> d_1
    \end{equation}
holds for infinitely many positive integers $n$.\\
{\bf (ii)} Let $\eta_1,\dots,\eta_r$ be any pairwise distinct complex numbers lying on the unit circle such that at least one of $\eta_j/\eta_r$, $1\le j <r$ is not a root of unity.
Let $\gamma_1,\dots ,\gamma_{r-1}\not= 0$ complex numbers.
Then for all $d_2>1$ there exists $\gamma_r$ such that the inequality
    \begin{equation}\label{eqii}
    |\gamma_1\eta_1^n + \dots + \gamma_r\eta_r^n|< d_2^{-n}
    \end{equation}
holds for infinitely many positive integers $n$.
\end{theorem}


\newpage
Theorem \ref{growth} implies that general
linear recursive sequences may have surprising big fluctuation.\\

\begin{cor}
  Let $r\ge 2$ be an integer and $d>1$ be a real number.
There exists a non zero
lrs $u_n$ of degree $r$
such that $|u_n| \gg d^n$ for infinitely many $n$ and $|u_n| \ll d^{-n}$ for infinitely many $n$.
\end{cor}

A consequence of the p-adic Subspace Theorem:
if $\gamma_1,\dots ,\gamma_r$, $\eta_1,\dots,\eta_{r}$ are all algebraic, non-zero and $\eta_j/\eta_r$ is not a root of unity for at least one $1\le j < r$, then
$$
|\gamma_1\eta_1^n+\dots +\gamma_r\eta_r^n| \ll d^{-n}
$$
holds for every $d>1$ for
only finitely many positive integers $n$.

\newpage
The Skolem-Mahler Lech theorem asserts that if $(a_n)$ is a lrs, then the set of $n$
with $a_n=0$ is either finite or contains an infinite arithmetic progression.
We show that there is no analogue for nlrs.\\

\begin{theorem} \label{nlrs_common}
There exist nlrs with integer terms $(a_n)$ such that $\limsup (a_n)= \infty$, but having infinitely many zero terms. Moreover the set of indices of the zero terms does not contain infinite arithmetic progressions.
\end{theorem}

\vspace{.5cm}

Let $P(x)=x^2+A_1x+A_2\in \Z[x]$ with roots $\alpha, \bar{\alpha}$ such that $|\alpha|= |\bar{\alpha}|>1$, and $\alpha/\bar{\alpha}$ is not a root of unity. Denote $p>3, p\equiv -1 \pmod 4$ an odd prime. Setting $A_1=1, A_2=\frac{p+1}{4}$ we get such polynomials.

Choosing $d_2=2$ there exists by Theorem \ref{growth} (ii) a complex number $\gamma$ such that if $a_{1,n} = \alpha^n + \gamma \bar{\alpha}^n, n=0,1,\dots$  then
$$
  |a_{1,n}| < 2^{-n}
$$
holds for infinitely many $n$. If $a_{1,n}\in \R$ for all $n$ then let $a_{2,n}=a_{1,n}$, otherwise let
$$
a_{2,n} = a_{1,n} + \bar{a}_{1,n} = (1+\bar{\gamma})\alpha^n + (1+\gamma)\bar{\alpha}^n.
$$
Plainly the sequence $(a_{2,n})$ contains only real numbers, it satisfies the recursion
\begin{equation}\label{sorozat1}
a_{2,n+2}+A_1 a_{2,n+1} + A_2a_{2,n} =0, \; n=0,1,\dots
\end{equation}
and there are infinitely many $n$ such that $|a_{2,n}|< 2^{-(n-1)}$. Further we have $\limsup a_{2,n} = \infty$ by Theorem \ref{growth} (i).

For a real number $x$ let $\lfloor x \rceil := [x+1/2]$. With this notation let
$$
a_n =  \lfloor a_{2,n} \rceil,\; n=0,1,\dots
$$
and $e_{2,n} = a_{2,n} - a_n$. Then $(a_n)$ is a sequence of integers and as $|e_{2,n}|\le 1/2$ we have $\limsup a_n = \infty$. Moreover, for those $n>2$ with $|a_{2,n}|< 2^{-(n-1)}$ we have $a_n=0$, i.e. $(a_n)$ has infinitely many zero terms.

Finally it is easy to prove that $(a_n)$ is a nlrs such that the set of indices of its zero terms does not contain infinite arithmetic progressions.

\newpage

Now we compare  the nlrs $(a_n)$ and its corresponding lrs analogue $(\tilde{a}_n)$. Although $a_n=\tilde{a}_n$ for $0\le n<d$,  the difference can not be bounded under a mild condition:\\

\begin{cor}
\label{Diff}
Under the same assumptions as in Theorem \ref{Binet_t} set
$$
R= \{\alpha_i\ | \ i=1,\dots,r_1 \text{ and } c(\alpha_i)\neq 0\}.
$$
Assume that $R\not=\emptyset$. If among the elements of $R$ there is
exactly one of maximal modulus, then $\lim_{n\to\infty}
|a_n-\tilde{a}_n|=\infty$, otherwise $\limsup_{n\to\infty}
|a_n-\tilde{a}_n|=\infty$.

\end{cor}

\newpage

The last corollary deals with shift radix systems $s_n$, which satisfy
$$
e_{n+d} = s_{n+d} + r_{d-1}s_{n+d-1}+\dots+r_0s_n,
$$
with $r_0,\dots,r_{d-1}\in \R, s_n\in \Z, e_n\in [0,1)$.\\

\begin{cor}
\label{Diff3}
If the dominating root of the characteristic polynomial of the nlrs $(s_n)$ is real, greater than one and not an algebraic integer, then the sequence $(s_n-\tilde{s}_n)$ diverges.
\end{cor}

\newpage
{\Large 5. Common values of nlrs}\\[1ex]

Common values of lrs's with algebraic terms are quite well investigated. Thanks to the theory of $S$-unit equations, Laurent (1989) characterized those sequences, which may have infinitely many common terms. These results are not effective.

If the characteristic polynomials of the sequences have dominating simple roots, which are multiplicatively independent then Mignotte (1978) gave an effective upper bound for the index
of possible common values. In the above mentioned results the Binet formula plays central role.

\newpage
The next result implies that the situation for nlrs is quite different from that of lrs.\\

\begin{theorem}
Let $\alpha ,\beta>1$ be multiplicatively independent real numbers.
Then there exist nlrs $(a_n)$, $(b_n)$ with integer terms,
having characteristic polynomials
with dominating roots $\alpha ,\beta$, respectively, such that
there are infinitely many pairs of non-negative
integers $(k,m)$ with $a_k=b_m$. This set of pairs $(k,m)$ has finite intersection
with every rational line.
\end{theorem}

\newpage
Something remains true from the diophantine theory of lrs.\\


\begin{theorem}
  Let $(a_n)$ be an nlrs. Assume that its characteristic polynomial is separable,
and has a dominant root $\alpha$ with $|\alpha |>1$.
Then the equation
\begin{equation} \label{egy11}
a_k = a_m
\end{equation}
has only finitely many solutions with $k\not= m$.
\end{theorem}

\newpage
{\Large 6. On bounded nlrs}\\

\begin{theorem}
\label{TBoundedSeq}
Let $d\in\NN$ and $\beta_1,\ldots,\beta_d\in\C$ such that $\abs{\beta_1}\leq\cdots\leq\abs{\beta_r}<1<\abs{\beta_{r+1}}\leq\cdots\leq\abs{\beta_d}$. Furthermore, let $(a_n)_{n\in\Nz},(e_n)_{n\in\Nz}\in\C^{\Nz}$ with $\abs{e_n}\leq E$ for all $n\in\Nz$, such that
\begin{align}
\label{ESeqC}
a_{n+d}+p_{d-1}a_{n+d-1}+\cdots+p_0a_n=e_n
\end{align}
for all $n\in\Nz$, where $\prod_{j=1}^{d}(x-\beta_j)=x^d+p_{d-1}x^{d-1}+\cdots+p_1x+p_0$. \\
$\bullet$ If $r=d$, or\\
$\bullet$ if $r<d$ and $(a_n)_{n\in\Nz}$ is bounded,
then for each $\varepsilon>0$ there is $n_0\in\mathbb{N}$ such that
$$
\abs{a_n}<\frac{E}{\prod_{j=1}^d\abs{1-\abs{\beta_j}}} +\varepsilon
$$
for $n \ge n_0$.
\end{theorem}

\newpage

{\Large 7. Bounded orbits of expansive srs}\\

If ${\bf r} = (p_0,\dots,p_{d-1}) \in \R^d$ and ${\bf a} =(a_0,\dots,a_{d-1})\in \Z^d$ and 
$\tau_{\bf r}^n({\bf a})=(a_n,\dots,a_{n+d-1})$ then
$$
a_{n+d}+p_{d-1}a_{n+d-1}+\cdots+p_0a_n=e_n
$$
with $e_n\in [0,1)$, i.e. $(a_n)$ is an nlrs associated to the srs $\tau_{\bf r}$. For such sequences Theorem \ref{TBoundedSeq} implies

\newpage
\begin{cor} \label{Cor23}
Assume that the sequence of integers $(a_n)_{n\in\Nz}$ is associated to the srs $\tau_{\bf r}$. Order $\beta_1,\ldots,\beta_d$ as in Theorem \ref{TBoundedSeq}. Then,
\begin{itemize}
\item[(i)] if $r=d$, or
\item[(ii)] if $r<d$ and $(a_n)_{n\in\Nz}$ is bounded,
\end{itemize}
then $(a_n)_{n\in\Nz}$ is ultimately periodic and
$$
\abs{a_n}\le \frac{1}{\prod_{j=1}^d\abs{1-\abs{\beta_j}}}
$$
holds for all elements of the cycle.

\end{cor}

\newpage

{\Large 7. Bounded orbits of expansive $2$-dim. srs}\\

For all ${\bf r}=(r_0,r_1)\in \R^2$ the zero sequence is an orbit of the srs $\tau_{\bf r}$. It is called trivial. If $x^2+r_1x+r_0$ is expansive then by Theorem \ref{Binet_t} the orbits of $\tau_{\bf r}$ grow exponentially. In some cases there are bounded non-trivial orbits as well. \\[0.5ex]
$\bullet$ If $-2\le r_0+r_1<-1$ then $(1)$,\\[0.5ex]
$\bullet$ if $-1\le r_0+r_1<0$ then $(-1)$, \\[0.5ex]
$\bullet$ if $r_0-r_1=1$ then $(1,-1)$, \\[0.5ex]
$\bullet$ if $-2<r_0\leq-1$ and $-1< r_1\leq0$ then $(0,-1)$, and\\[0.5ex]
$\bullet$ if $-1\leq r_0<0$ and $0\leq r_1<1$ then $(0,1)$ \\[0.5ex]
are non-trivial orbits.

\begin{center}\vbox{
\includegraphics[width=0.5\textwidth]{overview.pdf}
%\caption{Overview}
}\end{center}

\begin{theorem}
If $r_1>r_0+1$ or $r_1< -r_0-2$ or $r_0>\frac32 + \sqrt{2}$ and ${\bf r} =(r_0,r_1)$ does not lie in one of the boxes $-2<r_0\leq-1,-1< r_1\leq0$ and $-1\leq r_0<0, 0\leq r_1<1$, then $\tau_{\bf r}$ has no non-trivial orbit.
\end{theorem}

\begin{center}\vbox to\vsize{\vss\vbox to1.15\vsize{\includegraphics[height=18.8cm]{D2SternBlue.png}}
 % \includegraphics{D2SternBlue.png}\\[2ex]
 % The orbit of $\tau_{\small (1,1.1)}(25,462)$. Its length is $7555$.
}\end{center}

\newpage
\end{document}





