<commit_before>
\subsection{Renewal arrays, by Rogers}
\label{sec:back:to:the:basics:rogers}

\citeauthor{rogers:1977}, in \cite{rogers:1977}, proposes a theory
as a solution to the question left open by \citeauthor{shapiro:1976}, 
introducing the concept of \emph{renewal arrays}.

In order to understand his work, we formalize first the concept of $k$-fold
convolution of a sequence $\lbrace s_{i}\rbrace_{i\in\mathbb{N}}$ 
with itself and, second, the concept of \emph{renewal arrays}.
\\\\
Let $\lbrace \alpha_{i}\rbrace_{i\in\mathbb{N}}$ and 
$\lbrace \beta_{i}\rbrace_{i\in\mathbb{N}}$ be two sequences. Denote
with $\cdot$ the \emph{convolution} operator which consumes a pair
of sequences and produces a new sequence, written in \emph{infix} 
notation:
\begin{displaymath}
    \lbrace \alpha_{i}\rbrace_{i\in\mathbb{N}}\cdot
    \lbrace \beta_{i}\rbrace_{i\in\mathbb{N}} =
    \lbrace \theta_{i}\rbrace_{i\in\mathbb{N}}
\end{displaymath}
where sequence  $\lbrace \theta_{i}\rbrace_{i\in\mathbb{N}}$ satisfies:
\begin{displaymath}
    \theta_{n}=\sum_{j=0}^{n}{\alpha_{j}\beta_{n-j}}
\end{displaymath}

The $k$-fold convolution of a sequence $\lbrace \theta_{i}\rbrace_{i\in\mathbb{N}}$
\marginpar{$k$-fold convolution, precisely}
with itself, denoted with  $\lbrace \theta_{i}^{(k)}\rbrace_{i\in\mathbb{N}}$, is defined
recursively as:
\begin{displaymath}
    \lbrace\theta_{n}^{(k+1)}\rbrace= \lbrace\theta_{n}^{(k)}\rbrace\cdot
        \lbrace\theta_{n}\rbrace
\end{displaymath}
with boundary condition $\lbrace\theta_{n}^{(0)}\rbrace=(1,0,0,\ldots)$ so as:
\begin{displaymath}
    \lbrace\theta_{n}^{(1)}\rbrace= \lbrace\theta_{n}^{(0)}\rbrace\cdot
        \lbrace\theta_{n}\rbrace=
        \lbrace\theta_{n}+0\theta_{n-1}+\ldots+0\theta_{0}\rbrace=
        \lbrace\theta_{n}\rbrace
\end{displaymath}

Let $\vect{b}=\lbrace b_{i}\rbrace_{i\in\mathbb{N}}$ be a sequence. 
The \emph{renewal array} \marginpar{renewal arrays, precisely}
$\mathcal{B}=\lbrace b_{nm}\rbrace_{n,m\in\mathbb{N}}$
generated by sequence $\vect{b}$ is defined as follows:
\begin{displaymath}
    b_{nm}=b_{n-m}^{(m+1)} \quad\wedge\quad n < m\rightarrow b_{nm}=0
\end{displaymath}
For the sake of clarity, let $n\in\mathbb{N}$, then
% the following set should be helpful if subscript index change `n-m'
% hasn't be done in the definition of Renewal array 
%let $S_{m}=\mathbb{N}\setminus\lbrace0,\ldots,m-1\rbrace$, then 
the following is the sequence on the very first column, where $m=0$:
\begin{displaymath}
    \lbrace b_{n0}\rbrace
        =\lbrace b_{n}^{(1)}\rbrace
        =\lbrace b_{n}\rbrace
\end{displaymath}
the following is the sequence on the second column, where $m=1$:
\begin{displaymath}
    \lbrace b_{n1}\rbrace
        =\lbrace b_{n-1}^{(2)}\rbrace
        =\left\lbrace \sum_{j=0}^{n-1}{b_{j}b_{n-j}}\right\rbrace
\end{displaymath}
the following is the sequence on the third column, where $m=2$:
\begin{displaymath}
    \lbrace b_{n2}\rbrace
        =\lbrace b_{n-2}^{(3)}\rbrace
        =\left\lbrace \sum_{i+j+l=n-2}{b_{i}b_{j}b_{l}}\right\rbrace
\end{displaymath}
and so on. Choose a column index $m\in\mathbb{N}$ and 
let $B$ a \ac{fps} over sequence $\vect{b}$.
Denote with $B^{(m)}$ a \ac{fps} over the \emph{renewal array} 
$\lbrace b_{nm} \rbrace_{n,m\in\mathbb{N}}$, defined by sequence $\vect{b}$, 
such that:
\begin{displaymath}
    B^{(m)}(t) = \sum_{n\geq m}{b_{nm}t^{n-m}}
\end{displaymath}
the following relation exists between functions $B$ and $B^{(m)}$:
\begin{displaymath}
    B^{(m)}(t) = B(t)^{m+1}
\end{displaymath}
Consider a sequence\marginpar{$A$-sequence, informally}
$\vect{a}=\lbrace a_{n} \rbrace_{n\in\mathbb{n}}$ and let $A$ be
a \ac{fps} over $\vect{a}$.
\begin{displaymath}
    A\left(t\,B(t)\right) 
        = \sum_{r\geq 0}{a_{r}\left(t\,B(t)\right)^{r}}
        = \sum_{r\geq 0}{a_{r}B(t)^{r}t^{r}}
        = \sum_{r\geq 0}{a_{r}B^{(r-1)}(t)t^{r}}
\end{displaymath}
by definition of $B^{(r-1)}$ rewrite:
\begin{displaymath}
    \sum_{r\geq 0}{a_{r}B^{(r-1)}(t)t^{r}}
        =\sum_{r\geq 0}{a_{r}\left(\sum_{n\geq r-1}{b_{n,r-1}t^{n-r+1}}\right)t^{r}}
        =\sum_{r\geq 0}{\sum_{n\geq r-1}{a_{r}b_{n,r-1}t^{n+1}}}
\end{displaymath}
now we tabulate sums respect index $r$:
\begin{displaymath}
    \begin{split}
        r=0 &\rightarrow \sum_{n\geq -1}{a_{0}b_{n,-1}t^{n+1}}\\
        r=1 &\rightarrow \sum_{n\geq 0}{a_{1}b_{n,0}t^{n+1}}\\
        r=2 &\rightarrow \sum_{n\geq 1}{a_{2}b_{n,1}t^{n+1}}\\
        &\ldots\\
        r=k+1 &\rightarrow \sum_{n\geq k}{a_{k+1}b_{n,k}t^{n+1}}\\
        &\ldots\\
    \end{split}
\end{displaymath}
therefore extracting coefficient of $t^{n+1}$ yields:
\begin{displaymath}
    [t^{n+1}]A(t\,B(t))=\sum_{k\geq 0}{a_{k}\,b_{n,k-1}}
\end{displaymath}
if function $A$ satisfies $B(t)=A(t\,B(t))$, which is the same to say:
\begin{displaymath}
    b_{n+1}=\sum_{k\geq 0}{a_{k}\,b_{n,k-1}}
\end{displaymath}
then\marginpar{$A$-sequence, precisely}, sequence $\vect{a}$ 
is the $A$-sequence for the \emph{renewal array}
$\lbrace b_{nk}\rbrace_{n,k\in\mathbb{N}}$, generated by
sequence $\vect{b}$.


Consider a sequence\marginpar{$A$-sequence, informally}
$\vect{a}=\lbrace a_{n} \rbrace_{n\in\mathbb{n}}$ and let $A$ be
a \ac{fps} over $\vect{a}$.
\begin{displaymath}
    A\left((t\,B(t))^{s}\right) 
        = \sum_{r\geq 0}{a_{r}\left(t\,B(t)\right)^{r+s}}
        = \sum_{r\geq 0}{a_{r}B(t)^{r+s}t^{r+s}}
        = \sum_{r\geq 0}{a_{r}B^{(r+s-1)}(t)t^{r+s}}
\end{displaymath}
by definition of $B^{(r-1)}$ rewrite:
\begin{displaymath}
    \sum_{r\geq 0}{a_{r}B^{(r+s-1)}(t)t^{r+s}}
        =\sum_{r\geq 0}{a_{r}\sum_{n\geq r+s-1}{b_{n,r+s-1}t^{n+1}}}
        =\sum_{r\geq 0}{\sum_{n\geq r+s-1}{a_{r}b_{n,r+s-1}t^{n+1}}}
\end{displaymath}
now we tabulate sums respect index $r$:
\begin{displaymath}
    \begin{split}
        r=0 &\rightarrow \sum_{n\geq s-1}{a_{0}b_{n,s-1}t^{n+1}}\\
        r=1 &\rightarrow \sum_{n\geq s}{a_{1}b_{n,s}t^{n+1}}\\
        r=2 &\rightarrow \sum_{n\geq s+1}{a_{2}b_{n,s+1}t^{n+1}}\\
        &\ldots\\
        r=k+1 &\rightarrow \sum_{n\geq s+k}{a_{k+1}b_{n,s+k}t^{n+1}}\\
        &\ldots\\
    \end{split}
\end{displaymath}
therefore extracting coefficient of $t^{n+1}$ yields:
\begin{displaymath}
    [t^{n+1}]A(t\,B(t))=\sum_{k\geq 0}{a_{k}\,b_{n,s+k-1}}
\end{displaymath}
if function $A$ satisfies $B(t)^{s}=A((t\,B(t))^{s})$, which is the same to say:
\begin{displaymath}
    b_{n+s,s-1}=\sum_{k\geq 0}{a_{k}\,b_{n,s+k-1}}
\end{displaymath}
then\marginpar{$A$-sequence, precisely}, sequence $\vect{a}$ 
is the $A$-sequence for the \emph{renewal array}
$\lbrace b_{nk}\rbrace_{n,k\in\mathbb{N}}$, generated by
sequence $\vect{b}$.

















<commit_msg>Fix Rogers stuff about Renewal arrays, trying to make things clearer.<commit_after>
\subsection{Renewal arrays, by Rogers}
\label{sec:back:to:the:basics:rogers}

\citeauthor{rogers:1977}, in \cite{rogers:1977}, proposes a theory
as a solution to the question left open by \citeauthor{shapiro:1976}, 
introducing the concept of \emph{renewal arrays}.

In order to understand his work, we formalize first the concept of $k$-fold
convolution of a sequence $\lbrace s_{i}\rbrace_{i\in\mathbb{N}}$ 
with itself and, second, the concept of \emph{renewal arrays}.
\\\\
Let $\lbrace \alpha_{i}\rbrace_{i\in\mathbb{N}}$ and 
$\lbrace \beta_{i}\rbrace_{i\in\mathbb{N}}$ be two sequences. Denote
with $\cdot$ the \emph{convolution} operator which consumes a pair
of sequences and produces a new sequence, written in \emph{infix} 
notation:
\begin{displaymath}
    \lbrace \alpha_{i}\rbrace_{i\in\mathbb{N}}\cdot
    \lbrace \beta_{i}\rbrace_{i\in\mathbb{N}} =
    \lbrace \theta_{i}\rbrace_{i\in\mathbb{N}}
\end{displaymath}
where sequence  $\lbrace \theta_{i}\rbrace_{i\in\mathbb{N}}$ satisfies:
\begin{displaymath}
    \theta_{n}=\sum_{j=0}^{n}{\alpha_{j}\beta_{n-j}}
\end{displaymath}

The $k$-fold convolution of a sequence $\lbrace \theta_{i}\rbrace_{i\in\mathbb{N}}$
\marginpar{$k$-fold convolution, precisely}
with itself, denoted with  $\lbrace \theta_{i}^{(k)}\rbrace_{i\in\mathbb{N}}$, is defined
recursively as:
\begin{displaymath}
    \lbrace\theta_{n}^{(k+1)}\rbrace= \lbrace\theta_{n}^{(k)}\rbrace\cdot
        \lbrace\theta_{n}\rbrace
\end{displaymath}
with boundary condition $\lbrace\theta_{n}^{(0)}\rbrace=(1,0,0,\ldots)$ so as:
\begin{displaymath}
    \lbrace\theta_{n}^{(1)}\rbrace= \lbrace\theta_{n}^{(0)}\rbrace\cdot
        \lbrace\theta_{n}\rbrace=
        \lbrace\theta_{n}+0\theta_{n-1}+\ldots+0\theta_{0}\rbrace=
        \lbrace\theta_{n}\rbrace
\end{displaymath}

Let $\vect{b}=\lbrace b_{i}\rbrace_{i\in\mathbb{N}}$ be a sequence. 
The \emph{renewal array} \marginpar{renewal arrays, precisely}
$\mathcal{B}=\lbrace b_{nm}\rbrace_{n,m\in\mathbb{N}}$
generated by sequence $\vect{b}$ is defined as follows:
\begin{displaymath}
    b_{nm}=b_{n-m}^{(m+1)} \quad\wedge\quad n < m\rightarrow b_{nm}=0
\end{displaymath}
For the sake of clarity, let $n\in\mathbb{N}$, then
% the following set should be helpful if subscript index change `n-m'
% hasn't be done in the definition of Renewal array 
%let $S_{m}=\mathbb{N}\setminus\lbrace0,\ldots,m-1\rbrace$, then 
the following is the sequence on the very first column, where $m=0$:
\begin{displaymath}
    \lbrace b_{n0}\rbrace
        =\lbrace b_{n}^{(1)}\rbrace
        =\lbrace b_{n}\rbrace
\end{displaymath}
the following is the sequence on the second column, where $m=1$:
\begin{displaymath}
    \lbrace b_{n1}\rbrace
        =\lbrace b_{n-1}^{(2)}\rbrace
        =\left\lbrace \sum_{j=0}^{n-1}{b_{j}b_{n-1-j}}\right\rbrace
\end{displaymath}
the following is the sequence on the third column, where $m=2$:
\begin{displaymath}
    \lbrace b_{n2}\rbrace
        =\lbrace b_{n-2}^{(3)}\rbrace
        =\left\lbrace \sum_{i+j+l=n-2}{b_{i}b_{j}b_{l}}\right\rbrace
\end{displaymath}
and, in general, the following is the sequence on column $m\in\mathbb{N}$:
\begin{displaymath}
    \lbrace b_{nm}\rbrace
        =\lbrace b_{n-m}^{(m+1)}\rbrace
        =\left\lbrace \sum_{i_{1}+i_{2}+\ldots+i_{m+1} =n-m}
            {b_{i_{1}}b_{i_{2}}\cdots b_{i_{m+1}}}\right\rbrace
\end{displaymath}
Choose a column index $m\in\mathbb{N}$ and let $B$ a \ac{fps} over sequence $\vect{b}$.
Denote with $B^{(m)}$ a \ac{fps} over the \emph{renewal array} 
$\lbrace b_{nm} \rbrace_{n,m\in\mathbb{N}}$, defined by sequence $\vect{b}$, 
such that:
\begin{displaymath}
    B^{(m)}(t) = \sum_{n\geq m}{b_{nm}t^{n-m}}
\end{displaymath}
the following relation exists between functions $B$ and $B^{(m)}$:
\begin{displaymath}
    B^{(m)}(t) = B(t)^{m+1}
\end{displaymath}
Consider a sequence\marginpar{$A$-sequence, informally}
$\vect{a}=\lbrace a_{n} \rbrace_{n\in\mathbb{n}}$ and let $A$ be
a \ac{fps} over $\vect{a}$.
\begin{displaymath}
    A\left(t\,B(t)\right) 
        = \sum_{r\geq 0}{a_{r}\left(t\,B(t)\right)^{r}}
        = \sum_{r\geq 0}{a_{r}B(t)^{r}t^{r}}
        = \sum_{r\geq 0}{a_{r}B^{(r-1)}(t)t^{r}}
\end{displaymath}
by definition of $B^{(r-1)}$ rewrite:
\begin{displaymath}
    \sum_{r\geq 0}{a_{r}B^{(r-1)}(t)t^{r}}
        =\sum_{r\geq 0}{a_{r}\left(\sum_{n\geq r-1}{b_{n,r-1}t^{n-r+1}}\right)t^{r}}
        =\sum_{r\geq 0}{\sum_{n\geq r-1}{a_{r}b_{n,r-1}t^{n+1}}}
\end{displaymath}
now we tabulate sums respect index $r$:
\begin{displaymath}
    \begin{split}
        r=0 &\rightarrow \sum_{n\geq -1}{a_{0}b_{n,-1}t^{n+1}}\\
        r=1 &\rightarrow \sum_{n\geq 0}{a_{1}b_{n,0}t^{n+1}}\\
        r=2 &\rightarrow \sum_{n\geq 1}{a_{2}b_{n,1}t^{n+1}}\\
        &\ldots\\
        r=k+1 &\rightarrow \sum_{n\geq k}{a_{k+1}b_{n,k}t^{n+1}}\\
        &\ldots\\
    \end{split}
\end{displaymath}
therefore extracting coefficient of $t^{n+1}$ yields:
\begin{displaymath}
    [t^{n+1}]A(t\,B(t))=\sum_{k\geq 0}{a_{k}\,b_{n,k-1}}
\end{displaymath}
if function $A$ satisfies $B(t)=A(t\,B(t))$, which is the same to say:
\begin{displaymath}
    b_{n+1}=\sum_{k\geq 0}{a_{k}\,b_{n,k-1}}
\end{displaymath}
then\marginpar{$A$-sequence, precisely}, sequence $\vect{a}$ 
is the $A$-sequence for the \emph{renewal array}
$\lbrace b_{nk}\rbrace_{n,k\in\mathbb{N}}$, generated by
sequence $\vect{b}$.

% the following is wrong since the composition yield `rs' not `r+s'.
\iftrue
Allow us to generalize a little further. Choose 
$s\in\mathbb{N}\setminus\lbrace0\rbrace$ and consider the following:
\begin{displaymath}
    (t\,B(t))^{s-1}\,A\left(t\,B(t)\right) 
        = \sum_{r\geq 0}{a_{r}B(t)^{r+s-1}t^{r+s-1}}
        = \sum_{r\geq 0}{a_{r}B^{(r+s-2)}(t)t^{r+s-1}}
\end{displaymath}
by definition of $B^{(r+s-2)}$ rewrite:
\begin{displaymath}
    \sum_{r\geq 0}{a_{r}B^{(r+s-2)}(t)t^{r+s-1}}
        =\sum_{r\geq 0}{a_{r}\sum_{n\geq r+s-2}{b_{n,r+s-2}t^{n+1}}}
\end{displaymath}
finally:
\begin{displaymath}
    =\sum_{r\geq 0}{\sum_{n\geq r+s-2}{a_{r}b_{n,r+s-2}t^{n+1}}}
\end{displaymath}
now we tabulate sums respect index $r$, as done in the previous derivation:
\begin{displaymath}
    \begin{split}
        r=0 &\rightarrow \sum_{n\geq s-2}{a_{0}b_{n,s-2}t^{n+1}}\\
        r=1 &\rightarrow \sum_{n\geq s-1}{a_{1}b_{n,s-1}t^{n+1}}\\
        r=2 &\rightarrow \sum_{n\geq s}{a_{2}b_{n,s}t^{n+1}}\\
        r=3 &\rightarrow \sum_{n\geq s+1}{a_{3}b_{n,s+1}t^{n+1}}\\
        &\ldots\\
        r=k+2 &\rightarrow \sum_{n\geq s+k}{a_{k+2}b_{n,s+k}t^{n+1}}\\
        &\ldots\\
    \end{split}
\end{displaymath}
therefore extracting coefficient of $t^{n+1}$ yields:
\begin{displaymath}
    [t^{n+1}](t\,B(t))^{s-1}A(t\,B(t))=\sum_{k\geq 0}{a_{k}\,b_{n,s+k-2}}
\end{displaymath}
if function $A$ satisfies $B(t)^{s}=(t\,B(t))^{s-1}A(t\,B(t))$, 
    which is the same to say:
\begin{displaymath}
    \sum_{i_{1}+\ldots+i_{s}=n+1}{b_{i_{1}}\cdots b_{i_{s}}}
        =b_{n+1}^{(s)}
        =b_{n+s,s-1}
        =\sum_{k\geq 0}{a_{k}\,b_{n,s+k-2}}
\end{displaymath}
then\marginpar{$A$-sequence, generally}, sequence $\vect{a}$ 
is the (\emph{generalized}) $A$-sequence for the \emph{renewal array}
$\lbrace b_{nk}\rbrace_{n,k\in\mathbb{N}}$, generated by sequence $\vect{b}$.
\fi

















{'fraction_non_alphanumeric': 0.22801628687763412, 'fraction_numerical': 0.019001357239802844, 'mean_word_length': 3.961020552799433, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5102376', 'n_tokens_mistral': 5825, 'n_tokens_neox': 5535, 'n_words': 1118}