text:
\begin{document}

\begin{frontmatter}

\title{List decoding of Convolutional Codes over integer residue rings}

\author{Julia Lieb, Diego Napp and Raquel Pinto}

\address{Julia Lieb: Department of Mathematics, University of Zurich, Switzerland, e-mail: julia.lieb@math.uzh.ch.}

\address{Diego Napp: Department of Mathematics, University of Alicante, Spain, e-mail: diego.napp@ua.es\\

}

\address{Raquel Pinto: CIDMA - Center for Research and Development in Mathematics and Applications, Department of Mathematics, University of Aveiro, Portugal, e-mail: raquel@ua.pt

}

\begin{abstract}
A convolutional code $\C$ over $\ZZ[D]$ is a $\ZZ[D]$-submodule of $\ZZN[D]$ where $\ZZ[D]$ stands for the ring of polynomials with coefficients in $\ZZ$. In this paper, we study the list decoding problem of these codes when the transmission is performed over an erasure channel, that is, we study how much information one can recover from a  codeword $w\in \C$ when some of its coefficients have been erased. We do that using the $p$-adic expansion of $w$ and particular representations of the parity-check polynomial matrix of the code. From these matrix polynomial representations we recursively select certain equations that $w$ must satisfy and have only coefficients in the field $p^{r-1}\ZZ$. We exploit the natural block Toeplitz structure of the sliding parity-check matrix to derive a step by step methodology to obtain a list of possible codewords for a given corrupted codeword $w$, that is, a list with the closest codewords to $w$.
\end{abstract}

\begin{keyword}

Convolutional codes, finite rings, erasure channel

\end{keyword}

\end{frontmatter}

\section{Introduction}

Convolutional codes form a fundamental class of linear codes that are widely used in applications (see  also the related notion of sequential cellular automata \cite{CaFu17}) . They are typically described by means of a generator matrix, which is a polynomial matrix with coefficients in a finite field or a finite ring, depending on the application. Yet, the mathematical theory of convolutional codes over finite fields is much developed and has produced many sophisticated classes of codes. On the other hand, very little is known about concrete optimal constructions of convolutional codes over finite rings. In any case, the decoding of these codes is, in general, not easy. Probably the most prominent decoding algorithm is the Viterbi algorithm but its use is limited as its complexity grows exponentially with the size of the memory of the code. However, in \cite{to12} it was shown that the decoding of convolutional codes over finite fields requires only linear algebra when they are used over the erasure channel, \ie, when the positions of the errors are known. Despite the fact that convolutional codes that possess optimal erasure correcting capabilities require large finite fields, the results in \cite{to12} allow to implement these codes in many practical situations and therefore attracted the interest of many researchers, see for instance \cite{ma15a} and references therein.

Following this thread of research and aiming to extend these results over finite fields to the context of finite rings, we consider in this paper convolutional codes $\C$ over $\ZZ[D]$ and study the erasure correcting capabilities of these codes over the erasure channel. Convolutional codes over $\ZZ [D]$ were introduced by Massey et al. in \cite{massey89} and recently several relevant results were presented \cite{Interlando97,NaPiTo17,OuNaPiTo19,el13}.

In particular, our goal is to retrieve as much information as possible from the received corrupted vector. The decoder proposed in this work is a maximum likelihood algebraic decoder and follows succinctly two main steps. Firstly, it searches for unique decoding, \ie, when there exists a unique most likely word, then, the decoder outputs such a word. When this is not possible the algorithm performs a list decoding algorithm, \ie, it computes a complete list of the most likely codewords for a given corrupted codeword.

For this problem, we shall use the parity-check matrix $H(D)$ of $\C$ in a particular form. Then, the number of independent columns of specific submatrices of $H(D)$ will determine the size of the list of possible codewords in the algorithm. Considering the erasures as unknowns to-be-determined, the decoding  problem treated here amounts to solving a system of linear equations over $\ZZ$. The idea we used in this work is to multiply a selected subset of these equations by a power of $p$ in such a way that we obtain equations with coefficients in  the field $p^{r-1}\ZZ$, isomorphic to $\mathbb{Z}_{p}$, and therefore we can easily compute the unknowns. Once we know  some of the coefficients we can select another set of equations and apply the same ideas to these equations to recover another set of erased symbols. In this way we develop a systematic recursive procedure to recover all possible erasures that could have occurred. This, in turn, provides with a list with the closest codewords to the received information vector.

The outline of this paper is as follows. In Section 2, we present basic results on convolutional codes over the finite ring $\ZZ$, in particular about their parity-check matrices, which are important for decoding over the erasure channel. In Section 3, we present our erasure decoding algorithm for convolutional codes over $\ZZ$ and illustrate it with an example. Finally, we conclude with analyzing the complexity of our algorithm in Section 4.

\section{Preliminary results}

In this section we present the elementary background required in the paper. Let $\ZZD$ denote the ring of polynomials with coefficients in $\ZZ$ and let $\mathcal{A} =\{0,1,2, \dots, p-1\}$ be the set of \textbf{digits}. We say that $v(D)$ has \textbf{order} $s$, denoted by ord$(v(D))=s$, if $p^{s-1}v(D) \neq 0$ and $p^{s-1}v(D) \in p^{r-1}\ZZ^\ell[D]$. Every element in $v(D)\in \ZZ^\ell[D] $ admits a unique $p$-adic expansion as $v(D)= a_0(D) + a_1(D) p + \cdots + a_{r-1}(D)p^{r-1}$, with $a_i(D)\in \mathcal{A}[D]$, ord$(a_i(D))=r-1$ and $i=0,1,\dots, r-1$. We shall extensively use that $p^{r-1}\ZZ$ is isomorphic to the field $\Z_p$ in our algorithms.

\begin{Def} \cite{QuNaPiTo17,fo70,el13}
A {\bf convolutional code $\mathcal{C}$} of length $n$ is a $\ZZ[D]$-submodule of  $\ZZN[D]$. A polynomial matrix $ G(D) \in \ZZ^{k \times n}[D]$ such that
\begin{eqnarray*}
{\mathcal C} & =  \left\{ G(D)^T u(D) \in \ZZN[D] :\, u(D) \in \Z^{ k}_{p^r}[D]\right\}
\end{eqnarray*}
is called {\bf generator matrix} of the code.
\end{Def}

A polynomial matrix $H(D)$ is a {\bf parity-check matrix} (or
syndrome former) of a convolutional code $\C$ if $\C= \KER_{\mathbb Z_{p^r}[D] } H(D)$, \ie ,
for every $w(D)\in \ZZN[D]$,

\begin{equation}\label{eq:01}
w(D) \in \C \Leftrightarrow H(D)w(D)=0.
\end{equation}

\begin{Def}
Let $R$ be a ring with identity and $U(D)\in R[D]^{n\times n}$. Then $U(D)$ is called {\bf unimodular} if there exists $V(D)\in R[D]^{n\times n}$ such that $U(D)V(D)=V(D)U(D)=I_n$.
\end{Def}

For any matrix $A$ with entries in $\mathbb Z_{p^r}$ or $\mathbb Z_{p^r}[D]$, we denote by $[A]_p$ the (componentwise) projection of $A$ into $\mathbb Z_p$.

\begin{Lem}\cite{ku07}\label{1}
Let $U(D)\in\mathbb Z_{p^r}[D]^{n\times n}$. Then $U(D)$ is unimodular (over $\mathbb Z_{p^r}[D]$) if and only if $[U(D)]_p$ is unimodular (over $\mathbb Z_p[D]$).
\end{Lem}

\begin{Def}
Let $\mathbb F$ be a finite field.
A polynomial matrix $P(D)\in\mathbb F[D]^{k\times n}$ with $k\leq n$ is {\bf left
prime} if in all factorizations
$P(D) = \Delta(D)\bar{P}(D)$ with $\Delta(D)\in\mathbb F[D]^{k\times k}$ and $\bar{P}(D)\in\mathbb F[D]^{k\times n}$,
the left factor $\Delta(D)$ is unimodular.
\end{Def}

\begin{Lem}\label{2}\cite{ka80}
Let $P(D)\in\mathbb Z_p[D]^{k\times n}$ with $k\leq n$. Then, the following conditions are equivalent:
\begin{itemize}
\item[(i)]$P(D)$ is left prime.
\item[(ii)]There exists $N(D)\in\mathbb Z_p[D]^{(n-k)\times k}$ such that $\begin{pmatrix}P(D)\\ N(D)\end{pmatrix}$ is unimodular.
\item[(iii)] $u(D)P(D)\in\mathbb Z^n_{p^r}[D]\Rightarrow u(D)\in\mathbb Z^k_{p^r}[D]$, for all $u(D)\in\mathbb Z^k_{p^r}(D)$, where $\mathbb Z_{p^r}(D)$ denotes the ring of rational functions with coefficients in $\mathbb Z_{p^r}$.
\end{itemize}
\end{Lem}

The next result follows immediately from Lemma \ref{1} and Lemma \ref{2}.

\begin{Cor}\label{cor}
Let $P(D)\in\mathbb Z_{p^r}[D]^{k\times n}$ with $k\leq n$. Then $[P(D)]_p$ is left prime over $\mathbb Z_p[D]$ if and only if there exists $N(D)\in\mathbb Z_{p^r}[D]^{(n-k)\times k}$ such that $\begin{pmatrix}P(D)\\ N(D)\end{pmatrix}$ is unimodular.
\end{Cor}

If $\C$ is a convolutional code that admits a parity-check matrix, then a parity-check matrix of $\C$ can be constructed as follows (for more details see \cite{OuNaPiTo19}): Let $\hat{G}(D)\in\mathbb Z_{p^r}[D]^{\hat{k}\times n}$ be a generator matrix of $\mathcal{C}$ and consider $$\hat{\C}=\{\hat{G}(D)^\top u(D):\ u(D)\in\mathbb Z_{p^r}((D))^{\hat{k}}\}$$
where $\ZZ((D))$ denotes the \index{Ring of Laurent series over $\ZZ$}{\bf ring of Laurent series} over $\ZZ$, \ie, the set of elements of the form
$$
a(D) = \sum_{i=-\infty}^{+\infty}{a_iD^i}
$$
where the coefficients $a_i$ are in $\ZZ$ and only finitely coefficients with negative indices may
be nonzero. Note that $\C=\hat{\C}\cap\mathbb Z_{p^r}[D]^n$. Then, there exists
\begin{align}\label{*}
G(D)=\left[
       \begin{array}{c}
         G_0(D) \\
        pG_1(D) \\
        \vdots \\
       p^{r-1}G_{r-1}(D)
       \end{array}
    \right],\ G_i(D)\in\mathbb Z_{p^r}[D]^{k_i\times n}\ \text{for}\ i=0,\hdots,r-1
\end{align}
with $\mathcal{G}=\left[\begin{matrix}G_0(D)\\ G_1(D)\\ \vdots\\ G_{r-1}(D)\end{matrix}\right]_p$ full row rank over $\mathbb Z_p[D]$ such that
$$\hat{\C}=\{G(D)^\top u(D):\ u(D)\in\mathbb Z_{p^r}((D))^k\},$$
where $k=k_0+k_1+\cdots+k_{r-1}$. A procedure to obtain $G(D)$ in this particular form is described in \cite[Theorem 1]{OuNaPiTo19}.
A parity-check matrix of $\hat{C}$ can be determined as follows Consider the generator matrix $G(D)$ defined in \eqref{*} and let $N(D)\in\mathbb Z_{p^r}[D]^{(n-k)\times n}$ such that
such that
$$\begin{pmatrix}
G_0(D)\\G_1(D)\\ \vdots\\G_{r-1}\\N(D)
\end{pmatrix}$$
is unimodular. Then, there exists $H_i(D)\in\mathbb Z_{p^r}[D]^{l_i\times n}$ where $l_0=n-k$ and $l_i=k_{r-i}$, $i=1,2,\hdots,r-1$, and $L(D)\in\mathbb Z_{p^r}[D]^{k_0\times n}$ such that
\begin{align}\label{b}
\begin{pmatrix}
L(D)\\ H_{r-1}(D)\\H_{r-2}(D)\\ \vdots\\H_1(D)\\ H_0(D)
\end{pmatrix}
[G_0(D)^\top\ G_1(D)^\top\ \hdots\ G_{r-1}(D)^\top\ N(D)^\top]=P(D)
\end{align}
for some
$$P(D)=\left[\begin{matrix}
\gamma_1(D) & & &\\ & \gamma_2(D) & & \\ & & \ddots &\\ & & & \gamma_n(D)
\end{matrix}\right],
$$
where $\gamma_i(D)$ are nonzero polynomials in $\mathbb Z_{p^r}[D]$. Then,
 $$H(D)=\left[
       \begin{array}{c}
         H_0(D) \\
        pH_1(D) \\
        \vdots \\
       p^{r-1}H_{r-1}(D)
       \end{array}
    \right],\ H_i(D)\in\mathbb Z_{p^r}[D]^{l_i\times n},\ l_i=k_{r-i},\ \text{for}\ i=1,\hdots,r-1,\ l_0=n-k$$
with $\mathcal{H}=\left[\begin{matrix}H_0(D)\\ H_1(D)\\ \vdots\\ H_{r-1}(D)\end{matrix}\right]_p$ full row rank over $\mathbb Z_p[D]$, such that
$$
w(D)\in \hat{\C} \Leftrightarrow H(D)w(D)=0.
$$

More details can be found in \cite{OuNaPiTo19}. Then,
$$\hat{\C}=\{w(D)\in\mathbb Z_{p^r}((D))^n:\ H(D)w(D)=0\},$$
and consequently,
$$\C=\KER_{\mathbb Z_{p^r}[D]} H(D),$$
which means that $H(D)$ is a parity-check matrix of $\C$.

However, not all convolutional codes admit a parity-check matrix as the following example shows.

\begin{Ex}\label{ce}
Let $G(D)=\left[\begin{matrix}1+D & 1+D & 1+D\\ 3 & 3 & 0\end{matrix}\right]\in\mathbb Z_9[D]^{2\times 3}$ and $\C$ be the convolutional code with generator matrix $G(D)$. Let us assume that $\C$ admits a parity-check matrix $H(D)$. Then, since $w(D)=[1+D\ \ 1+D\ \ 1+D]^\top\in\C$, it follows that $H(D)w(D)=0$. Then, $(1+D)H(D)\begin{pmatrix} 1\\ 1\\ 1\end{pmatrix}=0$ and therefore, $H(D)\begin{pmatrix} 1\\ 1\\ 1\end{pmatrix}=0$. This means that $\begin{pmatrix} 1\\ 1\\ 1\end{pmatrix}\in\C$, which is not true.
\end{Ex}

However, in the case that a convolutional code does not admit a parity-check matrix, the procedure above constructs a matrix $H(D)$ such that $\C\subset \KER_{\mathbb Z_{p^r}[D]} H(D)$ because $\C\subset\hat{\C}$.

If a convolutional code $\C$ admits a parity-check matrix, it is called {\bf observable} or {\bf non-catastrophic}. The characterization of the non-catastrophic convolutional codes over $\mathbb Z_{p^r}[D]$ is still an open problem. However, for a certain class of convolutional codes, the following lemma characterizes the non-catastrophic codes.

\begin{Lem}\label{3}
Let $\C$ be a convolutional code of length $n$ that admits a generator matrix $G(D)$ of the form
\begin{align}G(D)=\left[
       \begin{array}{c}
         G_0(D) \\
        pG_1(D) \\
        \vdots \\
       p^{r-1}G_{r-1}(D)
       \end{array}
    \right],\ G_i(D)\in\mathbb Z_{p^r}[D]^{k_i\times n}\ \text{for}\ i=0,\hdots,r-1
\end{align}
such that
\begin{align}
\mathcal{G}=\left[\begin{matrix}G_0(D)\\ G_1(D)\\ \vdots\\ G_{r-1}(D)\end{matrix}\right]_p
\end{align}
is full row rank over $\mathbb Z_p[D]$. Then, $\C$ admits a parity-check matrix if and only if $\mathcal{G}$ is left prime over $\mathbb Z_p[D]$.
\end{Lem}

\begin{proof}
Take $k=k_0+k_1+\cdots+k_{r-1}$ and let us assume that $G(D)$ is such that $\mathcal{G}$ is left prime over $\mathbb Z_p[D]$. Then, by Corollary \ref{cor}, there exists $N(D)\in\mathbb Z_{p^r}[D]^{(n-k)\times n}$ such that
$$\begin{pmatrix}
G_0(D)\\G_1(D)\\ \vdots\\G_{r-1}\\N(D)
\end{pmatrix}$$
is unimodular. Then
\begin{align}\label{b}
\begin{pmatrix}
L(D)\\ H_{r-1}(D)\\H_{r-2}(D)\\ \vdots\\H_1(D)\\ H_0(D)
\end{pmatrix}
[G_0(D)^\top\ G_1(D)^\top\ \hdots\ G_{r-1}(D)^\top\ N(D)^\top]=I
\end{align}
for some $H_i(D)\in\mathbb Z_{p^r}[D]^{l_i\times n}$ where $l_0=n-k$ and $l_i=k_{r-i}$, $i=1,2,\hdots,r-1$, and $L(D)\in\mathbb Z_{p^r}[D]^{k_0\times n}$. Let us define
\begin{align*}
H(D)=\begin{pmatrix}
H_0(D)\\ pH_1(D)\\ \vdots\\ p^{r-1}H_{r-1}(D).
\end{pmatrix}
\end{align*}
By Corollary \ref{cor} we have that
\begin{align*}
\mathcal{H}=\left[\begin{matrix}H_0(D)\\H_1(D)\\ \vdots\\H_{r-1}(D)\end{matrix}\right]_p
\end{align*}
is left prime over $\mathbb Z_p[D]$. Expression \eqref{b} also implies that
\begin{align}\label{s}
H(D)G(D)^\top=0.
\end{align}
Let us prove that $\mathcal{C}=\KER_{\mathbb Z_{p^r}[D]} H(D)$. Expression \eqref{s} shows that $\mathcal{C}\subset\KER_{\mathbb Z_{p^r}[D]} H(D)$. To prove the other inclusion, let us consider that $w(D)\in\KER_{\mathbb Z_{p^r}[D]} H(D)$, i.e., $w(D)\in \mathbb Z_{p^r}[D]$ is such that
$$\begin{pmatrix}
H_0(D)\\ pH_1(D)\\ \vdots\\ p^{r-1}H_{r-1}(D)
\end{pmatrix}w(D)=0.$$
Then
$$H_i(D)w(D)=p^{r-i}v_i(D)$$
for some $v_i(D)\in\mathbb Z_{p^r}[D]^{l_i}$, $i=0,1,\hdots,r-1$. Since, by \eqref{b},
$$w(D)=[G_0(D)^\top\ G_1(D)^\top\ \cdots\ G_{r-1}(D)^\top\ N(D)^\top]\left[\begin{matrix}L(D)\\ H_{r-1}(D)\\H_{r-2}(D)\\ \vdots\\H_1(D)\\H_0(D)\end{matrix}\right]w(D),$$
it follows that $$w(D)=[G_0(D)^\top\ G_1(D)^\top\ \cdots\ G_{r-1}(D)^\top\ N(D)^\top]\left[\begin{matrix}L(D)w(d)\\ pv_{r-1}(D)\\p^2v_{r-2}(D)\\ \vdots\\p^{r-1}v_1(D)\\0\end{matrix}\right]=G(D)^\top\left[\begin{matrix}L(D)w(D)\\ v_{r-1}(D)\\v_{r-2}(D)\\ \vdots\\v_1(D)\end{matrix}\right],$$
which means that $w(D)\in\mathcal{C}$. Thus, we conclude that $\mathcal{C}=\KER_{\mathbb Z_{p^r}[D]} H(D)$, \ie, $\mathcal{C}$ admits a parity-check matrix.\\
To show the converse, let us assume that $\C$ has a parity-check matrix $H(D)$ and let $\bar{w}(D)\in\mathbb Z^n_{p}[D]$  be such that
$$\bar{w}(D)=\mathcal{G}^\top\bar{u}(D),$$
for some $\bar{u}(D)\in\mathbb Z^k_{p}(D)$. Then,
$$p^{r-1}w(D)=\mathcal{G}^\top p^{r-1}u(D),$$
where $w(D)\in\mathbb Z^n_{p^r}[D]$ and $u(D)\in\mathbb Z^k_{p^r}(D)$ are such that $[w(D)]_p=\bar{w}(D)$ and $[u(D)]_p=\bar{u}(D)$. Therfore,
$$p^{r-1}w(D)=G(D)^\top u_1(D)$$
where
$$p^{r-1}u(D)=\left[\begin{matrix}
I_{k_0} & & &\\ & pI_{k_1} & &\\ & & \ddots &\\ & & & p^{r-1}I_{k_{r-1}}
\end{matrix}\right]u_1(D).
$$
Consequently,
$$H(D)p^{r-1}w(D)=H(D)G(D)^\top u_1(D)=0,$$
which means that $p^{r-1}w(D)\in\C$. Therfore $u_1(D)\in\mathbb Z^k_{p^r}[D]$ and hence, $\bar{u}(D)\in\mathbb Z^k_{p^r}[D]$. Thus, we conclude by Lemma \ref{2} that $\mathcal{G}$ is left prime over $\mathbb Z_p[D]$.

\end{proof}

It is well-known that kernel representations are useful to detect errors introduced during transmission. If a word $w(D)$ is received
after channel transmission, the existence of errors is checked by simple multiplication by $H(D)$: if $H(D)w(D)=0$, it is assumed that
no errors occurred. As Example \ref{ce} and Lemma \ref{3} show, not all convolutional codes defined in $\mathbb Z_{p^r}[D]$ admit a parity-check matrix.
Nevertheless we showed that there always exists a matrix $H(D)$ such that $\C \subset \ker H(D)$, and then we still can make use of $H(D)$ to decode when the transmission occurs over the erasure channel. For simplicity, we will also call this matrix a parity-check matrix of $\C$. In an erasure channel a codeword can only have erasures (\ie, we know the positions of the part of the codeword that is missing or erased) but no errors occur.
In fact, if one considers the erasures as indeterminates, $H(D)w(D)=0$ give rise to a system of linear equations.
Solving this system amounts to decoding the received word $w(D)$, as we explain in detail in the next section.

The associated {\bf truncated sliding parity-check matrix} of $H(D)= \displaystyle \sum_{i=0}^{\nu} H^i D^i,
$ is
\begin{equation}\label{eq:033}
H^c_ j=\left[
\begin{array}{cccc}
H^0 & & & \\
H^1 & H^0 & & \\
\vdots & & \ddots & \\
 H^j & H^{j-1} & \cdots & H^0
\end{array}
\right]
\end{equation}
with  $H^j=0$ for $j>\nu$. As any codeword $w(D)$ of $\C$ satisfies $H(D)w(D)=0$, if $w(D)=\sum_{i \in \mathbb N_0} w^i D^i$, we have that, for all $j\geq 0$, $  \sum_{i=0}^{j} H^i w^{j-i}=0$, \ie,
\begin{equation}\label{eq:00}
\left[
\begin{array}{cccc}
H^0 & & & \\
H^1 & H^0 & & \\
\vdots & & \ddots & \\
 H^j & H^{j-1} & \cdots & H^0
\end{array}
\right]
\left[
\begin{array}{c}
w^0  \\
w^1 \\
\vdots  \\
w^j
\end{array}
\right]
=0.
\end{equation}

Two of the main notions of minimum distance of convolutional codes are the free distance and the column distance. Given $w(D)=\sum_{i \in \mathbb N_0} w^i D^i$, we define its \textbf{Hamming weight} as
$$ \wt(w(D)) = \sum_{j \in \mathbb{N}} \wt(w^j)$$
where $\wt(w^j)$ is the number of nonzero elements of $w^j$.

Given an $ (n,k) $ convolutional code $ \mathcal{C} \subseteq \ZZ^n[D] $, we define its \textbf{free distance} as
\begin{equation*}
d_{free}(\mathcal{C}) = \min \{ \wt(w(D)) \ : \ w(D) \in \mathcal{C} \textrm{ and } w(D) \neq 0 \} .
\end{equation*}

The free distance gives the correction capability of a convolutional code when considering whole codewords. In other words, there is no maximum degree $ j $ for a codeword considered by the free distance. In this work we shall focus on the sliding-window erasure correction capabilities of $\C$ within a time interval and this will be determined by the {\bf $j$-th column distance} of $\C$, for $j\in\mathbb N_0$, which is defined as follows.
\begin{eqnarray}\label{eq:CD}
  \nonumber  \mbox{$d^c_j$}(\mathcal{C}) &=&   \min \{ \wt((w^0, w^1, \ldots, w^j)) \ : \ \sum_{i \in \mathbb{N}_0} w^i D^i \in \mathcal{C}, w^0 \neq 0 \} \\
 & \stackrel{*}{=} & \left\lbrace \wt((w^0, w^1, \ldots, w^j)) \ : \ (w^0, w^1, \ldots, w^j) \text{ satisfies (\ref{eq:00}) and } w^0 \neq 0 \right\rbrace
\end{eqnarray}
where the equality $ * $ holds for convolutional codes that have a parity-check matrix. Next, we present two preliminary results.

\begin{Lem}\cite{mcdonald84}\label{lem:mccoy}
  Let $Ax=b$ with $A \in \ZZ^{a \times s}$ and $b \in \ZZ^{a}$ be a linear system of equations in $x$. Suppose this system has a solution. Then, the solution is unique if and only if  $[A]_p$ is full column rank or equivalently, if the McCoy \footnote{The McCoy rank of a matrix is the largest size of a minor that is an invertible element in the ring, $\mathcal{A}\setminus \{0\}$ in our case.} rank of $A$ is $s$.
\end{Lem}

Note that, opposed to the field case,  a set of vectors in $\ZZ$ can be linearly dependent but none of them is in the $\ZZ$-span of the others. The following result states the erasure correcting capability of a convolutional code in terms of its column distance.

\begin{Lem}\label{lem:column_dist}
Let $\C=\KER_{\mathbb Z_{p^r}[D]} H(D)$ and $j\in \mathbb{N}$. The following statements are equivalent:

\begin{enumerate}
  \item the column distance $d^c_j(\C)=d$;

  \item if $ (w^0, w^1, \ldots, w^j) $ contains up to $d-1$ erasures then $w^0$ can be recovered and there exist $d$ erasures that make it impossible to recover $w^0$.
  \item all sets of $d-1$ columns of $H_j^c$ that contain at least one of the first $n$ columns of $H_j^c$ are linearly independent and there exists a set of $d$ columns  of $H_j^c$ that contains at least one of the first $n$ columns of $H_j^c$ and is linearly dependent;
\end{enumerate}
If these equivalent statements hold, then the following holds:
\begin{itemize}
  \item[(4)] none of the first $n$ columns of $[H_j^c]_p $ is contained in the $\Z_p$-span of any other $d-2$ columns of $[H_j^c]_p$.
\end{itemize}

\end{Lem}

\begin{proof}
The equivalence of 1., 2. and 3. can be shown exactly in the same way as for finite fields (see \cite{gl03}). The last statement $(4)$ follows from the fact that if we have a linear combination of columns of $[H_j^c]_p $ in $\Z_p$, we readily obtain a linear combinations of $H_j^c$ over $\ZZ$ (just multiply the coefficients of the linear combination from $\Z_p$ by $p^{r-1}$).

\end{proof}

We notice that statement $(4)$ of Lemma \ref{lem:column_dist} does not imply the others as we show in the following example.
\begin{Ex}
  Consider $\C= \KER_{\Z_9[D]} H(D)$ over $\mathbb{Z}_{9}$ where $H(D)=H^0 + H^1 D$ with
  $$
  H^0=\left(
        \begin{array}{ccc}
          1 & 0 & 3 \\
          0 & 1 & 3 \\
        \end{array}
      \right) \text{ and }
   H^1=\left(
        \begin{array}{ccc}
          0 & 1 & 1 \\
          1 & 0 & 1 \\
        \end{array}
      \right) .
  $$
Then, none of the first 3 columns of $[H^c_1]_3$ is a linear combination of $1=3-2$ of the remaining columns of $[H^c_1]_3$. Hence, $(4)$ is fulfilled for $d=3$. However, it is easy to see that
 $d^c_1(\mathcal{C})= 2$ (consider the truncated codeword $(w^0,w^1)= (003 \ 002)$), i.e., the first statement of Lemma \ref{lem:column_dist} is not fulfilled for $d=3$.
\end{Ex}

\section{A decoding algorithm for erasures}\label{decoding_algorithm}

In this section we state the problem using the notation presented in the previous section and then propose an efficient decoding algorithm to solve it. More concretely, we aim to recover erasures that may occur during the transmission of the information over an erasure channel using convolutional codes $\C\subset\ZZND$. We derive a constructive step by step decoding algorithm to compute a minimal list with the closest codewords to the received vector. This is equivalent to solving a certain system of linear equations in $\ZZ$.

Suppose that $w(D)=\sum_{i \in \mathbb N_0} w^i D^i \in \C$ is sent and assume that we have correctly received all coefficients up to an instant $i-1$ and some of the components of $w^i$ are erased. The decoder tries to recover  $w^i$ up to a given instant $i+T$ and if this is not possible it outputs a list with the closest vectors at time instant $i+T$. The parameter $T$ is called the delay constraint and represents the maximum delay the receiver can tolerate to retrieve $w^i$, see \cite{ba15b,Martinian2007}. For the sake of simplicity it will be assumed that $T\leq \nu$, where $\nu$ is the degree of the parity-check matrix $H(D)$ of $\C$. The system of equations that involve $w^i$ up to time instant $i+T$ is

\begin{eqnarray}\label{eq0}
  \left[
  \begin{matrix}
    H^{\nu} &  H^{\nu-1} &  \cdots & H^{0}  & & \\
    & H^{\nu} &  H^{\nu-1} &  \cdots & H^{0}  & & \\
    & & \ddots  & \vdots & \vdots & \ddots & \\

  &  &  &  H^{\nu} &  H^{\nu-1} &  \cdots & H^{0}   \\
  \end{matrix}\right]
  \left[
  \begin{matrix}
    w^{i-\nu } \\
    w^{i-\nu +1} \\
    \vdots \\
    w^i \\
    \vdots \\
    w^{i+T}
  \end{matrix}
  \right]={0}.
\end{eqnarray}

We can take the columns of the matrix in (\ref{eq0}) that correspond to the coefficients of the erased elements to be the coefficients of a new system. With the remaining columns we can compute the independent terms, denoted by $ b^i$.

We regard the erasures as to-be-determined variables and denote for $i\in\mathbb N_0$ by $\widetilde w^i$ the subvector of $w^i$ that corresponds to the positions of the erasures. Similarly, denote by $\widetilde H^j_{i}$ the matrix consisting of the columns of $H^j$ with indices corresponding to the erased positions in $w^i$.
Then, we obtain the following system of linear equations

\begin{equation}\label{eq:03}
\left[
\begin{array}{cccc}
\widetilde H^0_{i} & & & \\
\widetilde H^{1}_{i} & \widetilde H^0_{i+1} & & \\
\vdots & & \ddots & \\
\widetilde H^T_{i} & \widetilde H^{T-1}_{i+1} & \cdots & \widetilde H^0_{i+T}
\end{array}
\right]
\left[
\begin{array}{c}
\widetilde w^{i}  \\
\widetilde w^{i+1} \\
\vdots  \\
\widetilde w^{i+T}
\end{array}
\right]=
\left[
\begin{array}{c}
 b^i  \\
 b^{i+1} \\
\vdots  \\
 b^{i+T}
\end{array}
\right].
\end{equation}

Hence, the problem of decoding is equivalent to solving the system of linear equations described in (\ref{eq:03}).

For this algorithm we consider a parity-check matrix $H(D)$ of the form

\begin{equation}\label{eq:standard_form}
H(D)=\left[
\begin{array}{c}
H_0(D)  \\
pH_1 (D) \\
\vdots  \\
p^{r-1}H_{r-1}(D)
\end{array}
\right] \text{ with } \left[
\begin{array}{c}
H_0(D)  \\
H_1 (D) \\
\vdots  \\
H_{r-1}(D)
\end{array}
\right] \text{ full row rank. }
\end{equation}

Hence, it readily follows that one can rewrite (\ref{eq:03}), after appropriate row permutations, as

\begin{equation}\label{eq:04}
\left[
\begin{array}{cccc}
\widetilde  H^0_{i,0} & & & \\
p \widetilde  H^0_{i,1} & & & \\
\vdots & & & \\
p^{r-1} \widetilde H^0_{i,r-1} & & & \\
\widetilde H^1_{i,0} & \widetilde H^0_{i+1,0} & & \\
p\widetilde  H^1_{i,1} & p\widetilde  H^0_{i+1,1} & & \\
\vdots & \vdots & & \\
p^{r-1}\widetilde  H^1_{i,r-1} & p^{r-1}\widetilde  H^0_{i+1,r-1} & & \\
\vdots & & \ddots & \\
\widetilde  H^T_{i,0} & \widetilde  H^{T-1}_{i+1,0} & \cdots & \widetilde  H^0_{i+T,0} \\
p \widetilde  H^T_{i,1} & p \widetilde  H^{T-1}_{i+1,1} & \cdots & p \widetilde  H^0_{i+T,1} \\
\vdots & \vdots & & \vdots \\
p^{r-1} \widetilde  H^T_{i,r-1} & p^{r-1} \widetilde  H^{T-1}_{i+1,r-1} & \cdots & p^{r-1} \widetilde  H^0_{i+T,r-1}
\end{array}
\right]
\left[
\begin{array}{c}
\widetilde w^{i}  \\
\widetilde w^{i+1} \\
\vdots  \\
\widetilde w^{i+T}
\end{array}
\right]=
\left[
\begin{array}{c}
 b^i_0 \\
p b^i_1 \\
\vdots \\
p^{r-1}b^i_{r-1} \\
 b^{i+1}_0 \\
p b^{i+1}_1 \\
\vdots \\
p^{r-1}b^{i+1}_{r-1} \\
\vdots  \\
 b^{i+T}_0 \\
p b^{i+T}_1 \\
\vdots \\
p^{r-1}b^{i+T}_{r-1} \\
\end{array}
\right],
\end{equation}
with the property that the rows of the matrices $\widetilde H^0_{i,t}, [\widetilde H^1_{i,t} \; \widetilde H^0_{i+1,t}], \dots, [\widetilde H^T_{i,t} \;\widetilde H^{T-1}_{i+1,t} \cdots \widetilde H^0_{i+T,t}]$ have  order $r$
, for $t=0,1, \dots, r-1$. Note that the number of nonzero rows of each block in the decomposition (\ref{eq:04}) will depend on the erasure pattern.\\
Denote by $e_s$ the size of $\widetilde w^s$, for $s\in \{i, i+1, \dots, i+T  \}$. \\

\textbf{List decoding}:\\
We aim to compute all possible solutions of (\ref{eq:04}). To this end we define the following matrix for all $0 \leq t \leq r-1$,

\begin{equation}\label{eq:06}
\widetilde{ \mathcal{H}}^c_t= \left[
\begin{array}{cccc}
\widetilde  H^0_{i,0} & & & \\
 \widetilde  H^0_{i,1} & & & \\
\vdots & & & \\
 \widetilde H^0_{i,r-t-1} & & & \\
\widetilde H^1_{i,0} & \widetilde H^0_{i+1,0} & & \\
\widetilde  H^1_{i,1} & \widetilde  H^0_{i+1,1} & & \\
\vdots & \vdots & & \\
\widetilde  H^1_{i,r-t-1} & \widetilde  H^0_{i+1,r-t-1} & & \\
\vdots & & \ddots & \\
\widetilde  H^T_{i,0} & \widetilde  H^{T-1}_{i+1,0} & \cdots & \widetilde  H^0_{i+T,0} \\
\widetilde  H^T_{i,1} &  \widetilde  H^{T-1}_{i+1,1} & \cdots &  \widetilde  H^0_{i+T,1} \\
\vdots & \vdots & & \vdots \\
\widetilde  H^T_{i,r-t-1} & \widetilde  H^{T-1}_{i+1,r-t-1} & \cdots & \widetilde  H^0_{i+T,r-t-1}
\end{array}
\right],
\end{equation}

and write

\begin{equation}\label{eq:adic_w}
\left[
\begin{array}{c}
\widetilde w^i  \\
\widetilde w^{i+1} \\
\vdots  \\
\widetilde w^{i+T}
\end{array}
\right]=\left[
\begin{array}{c}
 w^{i}_0  \\
w^{i+1}_0 \\
\vdots  \\
w^{i+T}_0
\end{array}
\right]+p \left[
\begin{array}{c}
 w^{i}_1  \\
 w^{i+1}_1 \\
\vdots  \\
w^{i+T}_1
\end{array}
\right]+\cdots+p^{r-1}\left[
\begin{array}{c}
 w^{i}_{r-1}  \\
 w^{i+1}_{r-1} \\
\vdots  \\
 w^{i+T}_{r-1}
\end{array}
\right],
\end{equation}
where $w^j_{t}$ has entries in $\mathcal{A}_{p}=\{0,1,\dots,p-1\}$, for all $j\in\{i,i+1,\dots,i+T\}$ and $t\in \{0,1,\dots,r-1\}$. We aim at computing the maximum number of coefficients $w^j_{t}$ in (\ref{eq:adic_w}).

\begin{description}
  \item[{\bf \underline{Step 1}}:] Find the solution $(\widehat w^{i}_0, \widehat w^{i+1}_0, \dots , \widehat w^{i+T}_0)$ of the system
\begin{align}\label{eq:10}
\left[
\begin{array}{cccc}
\widetilde H^0_{i,0} & & & \\
\widetilde H^0_{i,1} & & & \\
\vdots & & & \\
\widetilde H^0_{i,r-1} & & & \\
\widetilde H^1_{i,0} & \widetilde H^0_{i+1,0} & & \\
\widetilde H^1_{i,1} & \widetilde H^0_{i+1,1} & & \\
\vdots & \vdots & & \\
\widetilde H^1_{i,r-1} & \widetilde H^0_{i+1,r-1} & & \\
\vdots & & \ddots & \\
\widetilde H^T_{i,0} & \widetilde H^{T-1}_{i+1,0} & \cdots & \widetilde H^0_{i+T,0} \\
\widetilde H^T_{i,1} & \widetilde H^{T-1}_{i+1,1} & \cdots & \widetilde H^0_{i+T,1} \\
\vdots & \vdots & & \vdots \\
\widetilde H^T_{i,r-1} & \widetilde H^{T-1}_{i+1,r-1} & \cdots & \widetilde H^0_{i+T,r-1}
\end{array}
\right]_p
\left[
\begin{array}{c}
\widehat w^i_0  \\
\widehat w^{i+1}_0 \\
\vdots  \\
\widehat w^{i+T}_0
\end{array}
\right]=
\left[
\begin{array}{c}
 b^i_0 \\
 b^{i}_1 \\
\vdots \\
b^i_{r-1} \\
 b^{i+1}_0 \\
 b^{i+1}_1 \\
\vdots \\
b^{i+1}_{r-1} \\
\vdots  \\
 b^{i+T}_0 \\
 b^{i+T}_1 \\
\vdots \\
b^{i+T}_{r-1} \\
\end{array}
\right]_{p},
\end{align}
\begin{equation*}
\hspace*{-4.5cm} \underbrace{\hspace*{5.5cm}}_{ [\widetilde{\mathcal{H}}^c_0]_p}
\end{equation*}
over the field $\Z_p$. Let $e= \sum_{s=i}^{i+T}e_s$. Then, the ``integer" part of the set of solutions, \ie, \ the vector $\left[
\begin{array}{c}
 w^{i}_0  \\
w^{i+1}_0 \\
\vdots  \\
w^{i+T}_0
\end{array}
\right]$ in (\ref{eq:adic_w}), is given by:
\[
 \cal S_\text{$0$} = \left \{
 \left[
\begin{array}{c}
w^i_0  \\
w^{i+1}_0 \\
\vdots  \\
w^{i+T}_0
\end{array}
\right] \in \mathcal{A}^\text{$e$} \ : \  \left[
\begin{array}{c}
w^i_0  \\
w^{i+1}_0 \\
\vdots  \\
w^{i+T}_0
\end{array}
\right]_{\text{$p$}}=\left[
\begin{array}{c}
\widehat w^i_0  \\
\widehat w^{i+1}_0 \\
\vdots  \\
\widehat w^{i+T}_0
\end{array}
\right]  \text{ with  } \left[
\begin{array}{c}
\widehat w^i_0  \\
\widehat w^{i+1}_0 \\
\vdots  \\
\widehat w^{i+T}_0
\end{array}
\right]  \text{ satisfying (\ref{eq:10})  }
\right \}.
\]

It is straightforward to see that the size of $\cal S_\text{$0$}$ is given by
$$
|\mathcal{S}_0| = p^{e- \rank [\widetilde{ \mathcal{H}}^c_0]_p}.
$$

To compute the remaining vectors, if necessary, in the $p$-adic decomposition of (\ref{eq:adic_w}) we recursively apply the following algorithm in the next step.

  \item[{\bf \underline{Step 2}}:] Let $b_{s,0}^{j}=b_s^j$, $j=i,i+1,\dots,i+T$, $s=0,1, \dots, r-1$.

  For $t=1, \dots,r-1$ do
  \begin{enumerate}
    \item For $j=i,i+1,\dots,i+T$, consider the solutions $\left[
\begin{array}{c}
w^i_{t-1}  \\
w^{i+1}_{t-1} \\
\vdots  \\
w^{i+T}_{t-1}
\end{array}
\right]\in S_{t-1}$ and define
    \begin{align*}
\begin{bmatrix}
\widehat{b}^j_{0,t} \\
\widehat{b}^j_{1,t} \\
\vdots\\
\widehat{b}^j_{r-t-1,t}
\end{bmatrix}
& =
\begin{bmatrix}
p^{t-1}b^j_{0,t-1} \\
p^{t}{b}^j_{1,t-1} \\
\vdots\\
p^{r-2}{b}^j_{r-t-1,t-1}
\end{bmatrix}-

\begin{bmatrix}
p^{t-1}\widetilde H^{j-i}_{i,0} & \cdots & p^{t-1}\widetilde H^0_{j,0} \\
p^{t}\widetilde H^{j-i}_{i,1} & \cdots & p^{t}\widetilde H^0_{j,1} \\
\vdots & \vdots & \vdots \\
p^{r-2}\widetilde H^{j-i}_{i,r-t-1} & \cdots & p^{r-2}\widetilde H^0_{j,r-t-1}
\end{bmatrix}
\left[
\begin{array}{c}
w^i_{t-1}  \\
w^{i+1}_{t-1} \\
\vdots  \\
w^{j}_{t-1}
\end{array}
\right]
 \end{align*}

    \item For $j=i,i+1,\dots,i+T$, and $\ell=0,1,\dots, r-t-1$, compute \emph{one} $b_{\ell,t}^{i}$ such that
\begin{align*}
\widehat{b}_{\ell,t}^{j}=p^{t+\ell}b_{\ell,t}^{j}
\end{align*}
    \item Solve the system of linear equations
\begin{align}\label{eq:11}
[\widetilde{ \mathcal{H}}^c_t]_p
\left[
\begin{array}{c}
\widehat w^i_t  \\
\widehat w^{i+1}_t \\
\vdots  \\
\widehat w^{i+T}_t
\end{array}
\right]=
\left[
\begin{array}{c}
 b^i_{t,0} \\
 b^i_{t,1} \\
\vdots \\
b^0_{t,r-t-1} \\
 b^{i+1}_{t,0} \\
 b^{i+1}_{t,1} \\
\vdots \\
b^{i+1}_{t,r-t-1} \\
\vdots  \\
 b^{i+T}_{t,0} \\
 b^{i+T}_{t,1} \\
\vdots \\
b^{i+T}_{t,r-t-1} \\
\end{array}
\right]_{p},
\end{align}
over $\Z_p$ and let
\[
 \cal S_\text{$t$} = \left \{
 \left[
\begin{array}{c}
w^i_t  \\
w^{i+1}_t \\
\vdots  \\
w^{i+T}_t
\end{array}
\right]  \ : \  \left[
\begin{array}{c}
w^i_t  \\
w^{i+1}_t \\
\vdots  \\
w^{i+T}_t
\end{array}
\right]_{\text{$p$}}=\left[
\begin{array}{c}
\widehat w^i_t  \\
\widehat w^{i+1}_t \\
\vdots  \\
\widehat w^{i+T}_t
\end{array}
\right]  \text{ with  } \left[
\begin{array}{c}
\widehat w^i_t  \\
\widehat w^{i+1}_t \\
\vdots  \\
\widehat w^{i+T}_t
\end{array}
\right]  \text{ satisfying (\ref{eq:11})  }
\right \}.
\]
\end{enumerate}
\end{description}

\underline{{\em Output data}}:

$$
 \left \{
\left[
\begin{array}{c}
 w^i_0  \\
w^{i+1}_0 \\
\vdots  \\
w^{i+T}_0
\end{array}
\right]+p \left[
\begin{array}{c}
 w^{i}_1  \\
 w^{i+1}_1 \\
\vdots  \\
w^{i+T}_1
\end{array}
\right]+\cdots+p^{r-1}\left[
\begin{array}{c}
 w^i_{r-1}  \\
 w^{i+1}_{r-1} \\
\vdots  \\
 w^{i+T}_{r-1}
\end{array}
\right] \ : \ \left[
\begin{array}{c}
w^i_t  \\
w^{i+1}_t \\
\vdots  \\
w^{i+T}_t
\end{array}
\right] \in S_t, \ t=0,1,\dots ,r-1 \right \}.
$$

The size of the list decoding is
$$
\displaystyle \prod^{r-1}_{t=0} |S_t|.
$$
where each $|S_t|$ is given by
\begin{equation}\label{eq:13}
|S_t|= p^{e-  \rank [\widetilde{ \mathcal{H}}^c_t]_p}
\end{equation}

Note that Steps 1 and 2 deal with systems of linear equations over fields. The fact that these steps yield the set of all solution follows from \cite[Theorem 3]{Elif_Marisa_Raquel_Diego}.

\begin{Ex}
Let $\mathcal{C}\subset\mathbb Z_8[D]$ be the convolutional code with parity-check matrix $H(D)=H^0+H^1D+H^2D^2\in\mathbb Z_8[D]$ where $$H^0=\left[\begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 2 & 0 & 2\\ 4 & 4 & 0 & 4 & 4\end{array}\right],\ H^1=\left[\begin{array}{ccccc} 1 & 2 & 0 &0 & 0 \\ 0 & 0 & 0 & 2 & 4\\ 4 & 0 & 4 & 4 & 0\end{array}\right],\ H^2=\left[\begin{array}{ccccc} 3 & 5 & 7 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2\\ 0 & 0 & 0 & 4 & 0\end{array}\right].$$
It is easy to check that $w(D)=w^0+w^1D+w^2D^2+w^3D^3$ with
$$w^0=[5,5,0,6,0],\ \ w^1=[6,6,4,3,6],\ \ w^2=[2,1,1,2,0],\ \ w^3=[2,6,4,0,0]$$
is a codeword of $\mathcal{C}$. Assume that one receives $$w^0=[5,w^{0,1},w^{0,2},6,w^{0,3}], w^1=[6,6,4,w^{1,1},6], w^2=[2,1,w^{2,1}, w^{2,2}, w^{2,3}], w^3=[2,w^{3,1},4,0,0]$$ where $w^{0,1},w^{0,2},w^{0,3},w^{1,1},w^{2,1},w^{2,2},w^{2,3},w^{3,1}$ are erasures. Let the delay constraint for the decoding be $T=2$. To firstly recover $w^0$ we start our list decoding algorithm. One has
$$\widetilde{ \mathcal{H}}_0^c=\left[\begin{array}{ccccccc} 1 & 1 & 1 & 0 & 0 &0 & 0\\
 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0 & 0\\ 2 & 0 & 0 & 1 & 0 & 0 & 0\\0 & 0 & 1 & 0 & 0  &0 & 0\\ 0 & 1& 0 & 1 & 0 & 0 & 0\\ 5 & 7 & 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 & 1 &0 & 1\\ 0 & 0 & 0 & 1 & 0 & 1 & 1\end{array}\right]\qquad\text{and}\qquad[\widetilde{ \mathcal{H}}_0^c]_2=\left[\begin{array}{ccccccc} 1 & 1 & 1 & 0 & 0 &0 & 0\\
 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0\\0 & 0 & 1 & 0 & 0  &0 & 0\\ 0 & 1& 0 & 1 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 & 1 &0 & 1\\ 0 & 0 & 0 & 1 & 0 & 1 & 1\end{array}\right].$$
We write $w^{i,j}=w_{0}^{i,j}+2w_{1}^{i,j}+4w_{2}^{i,j}$ for $i=0,\hdots , 3$ and $j\in\{1,2,3\}$.
Solving the linear system
$$[\widetilde{ \mathcal{H}}_0^c]_2\cdot[w^{0,1}_{0}, w^{0,2}_{0},w^{0,3}_{0},w^{1,1}_{0},w^{2,1}_{0},w^{2,2}_{0},w^{2,3}_{0}]^{\top}=
[5,0,1,5,0,1,4,0,1]^{\top}_2=[1,0,1,1,0,1,0,0,1]^{\top}$$

over $\mathbb Z_2$ gives the (unique) solution
$$[w^{0,1}_{0}, w^{0,2}_{0},w^{0,3}_{0},w^{1,1}_{0},w^{2,1}_{0},w^{2,2}_{0},w^{2,3}_{0}]=
[1,0,0,1,1,0,0],$$ i.e., $S_0=\{[1,0,0,1,1,0,0]\}$. Note that $|S_0|=p^{e-  \rank [\widetilde{ \mathcal{H}}^c_0]_p}=p^{7-7}=1$.\\
Then, in step 2.1 and step 2.2 of the algorithm, one computes
\begin{eqnarray*}
\begin{pmatrix}
\widehat{b}_{0,1}^0\\ \widehat{b}_{1,1}^0
\end{pmatrix}=\begin{pmatrix}5\\0\end{pmatrix}-\left[\begin{array}{ccc} 1& 1 & 1\\ 0 & 2 & 2\end{array}\right]\begin{pmatrix}1\\0\\0\end{pmatrix}=
\begin{pmatrix}4\\0\end{pmatrix} \quad&\Rightarrow\ \begin{pmatrix} b_{0,1}^0\\ b_{1,1}^0 \end{pmatrix}=
\begin{pmatrix}2\\0\end{pmatrix}\\
\widehat{b}_{0,1}^1=5-\left[\begin{array}{cccc} 2&  0 & 0 & 1\end{array}\right]\begin{pmatrix}1\\0\\0\\1\end{pmatrix}=
\begin{pmatrix}4\\0\end{pmatrix} \quad&\Rightarrow\  b_{0,1}^1 =
1\\
\begin{pmatrix}
\widehat{b}_{0,1}^2\\ \widehat{b}_{1,1}^2
\end{pmatrix}=\begin{pmatrix}4\\0\end{pmatrix}-\left[\begin{array}{ccccccc} 5& 7 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 2 & 2 & 2 & 0 & 2\end{array}\right]\begin{pmatrix}1\\0\\0\\1\\1\\0\\0\end{pmatrix}=
\begin{pmatrix}6\\4\end{pmatrix} \quad&\Rightarrow\ \begin{pmatrix} b_{0,1}^2\\ b_{1,1}^2 \end{pmatrix}=
\begin{pmatrix}3\\1\end{pmatrix}\
\end{eqnarray*}
Afterwards, according to step 2.3, one has to solve the system of linear equations
$$\left[\begin{array}{ccccccc} 1 & 1 & 1 & 0 & 0 &0 & 0\\
 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 & 1 &0 & 1\end{array}\right]\begin{pmatrix}w^{0,1}_{1}\\ w^{0,2}_1\\w^{0,3}_{1}\\w^{1,1}_{1}\\w^{2,1}_{1}\\w^{2,2}_{1}\\w^{2,3}_{1}
 \end{pmatrix}=\begin{pmatrix}0\\0\\1\\1\\1\end{pmatrix}$$
 over $\mathbb Z_2$, which yields $$[w^{0,1}_{1}, w^{0,2}_1, w^{0,3}_{1}, w^{1,1}_{1}, w^{2,1}_{1}, w^{2,2}_{1}, w^{2,3}_{1}]=[0,c_1,
 c_1,1,c_1+c_2,1,c_2]$$ with free parameters $c_1,c_2\in\mathbb Z_2$, i.e., $$S_1=\{[0,c_1,c_1,1,c_1+c_2,1,c_2],\ c_1,c_2\in\mathcal{A}_2\}$$ with $|S_1|=p^{7-\rank [\widetilde{ \mathcal{H}}^c_1]_p}=p^2=4$.\\
 In the last iteration, one computes
 \begin{eqnarray*}
\widehat{b}_{0,2}^0=2\cdot 2-2\cdot\left[\begin{array}{ccc} 1& 1 & 1\end{array}\right]\begin{pmatrix}0\\c_1\\c_1\end{pmatrix}=
4-4c_1\quad&\Rightarrow\ b_{0,2}^0 =1-c_1\\
\widehat{b}_{0,2}^1=2\cdot 1-2\cdot\left[\begin{array}{cccc} 2&  0 & 0 & 1\end{array}\right]\begin{pmatrix}0\\c_1\\c_1\\1\end{pmatrix}=0\quad&\Rightarrow\  b_{0,2}^1 =0\\
\widehat{b}_{0,2}^2=2\cdot 3-2\cdot\left[\begin{array}{ccccccc} 5& 7 & 0 & 0 & 1 & 1 & 1 \end{array}\right]\begin{pmatrix}0\\c_1\\c_1\\1\\c_1+c_2\\1\\c_2\end{pmatrix}=
4-4c_2 \quad&\Rightarrow\ b_{0,2}^2=1-c_2
\end{eqnarray*}
and afterwards solves the system of linear equations
$$\left[\begin{array}{ccccccc} 1 & 1 & 1 & 0 & 0 &0 & 0\\
 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 1 & 1 & 1\\ \end{array}\right]\begin{pmatrix}w^{0,1}_{2}\\ w^{0,2}_{2}\\w^{0,3}_{2}\\w^{1,1}_{2}\\w^{2,1}_{2}\\w^{2,2}_{2}\\w^{2,3}_{2}
 \end{pmatrix}=\begin{pmatrix}1-c_1\\0\\1-c_2\end{pmatrix}$$
 over $\mathbb Z_2$, which yields
\begin{align*}
 &[w^{0,1}_{2}, w^{0,2}_{2}, w^{0,3}_{2}, w^{1,1}_{2}, w^{2,1}_{2}, w^{2,2}_{2}, w^{2,3}_{2}]\\
&= [1+c_2+c_3+c_4+c_5+c_6,c_3,c_1+c_2+c_4+c_5+c_6,0,c_4,c_5,c_6]
\end{align*}
  with free parameters $c_3,c_4, c_5,c_6\in\mathbb Z_2$, i.e.
  $$S_2=\{[1+c_2+c_3+c_4+c_5+c_6,c_3,c_1+c_2+c_4+c_5+c_6,0,c_4,c_5,c_6],\ c_3,c_4, c_5,c_6\in\mathcal{A}_2\}.$$
with $|S_2|=p^{7-\rank [\widetilde{ \mathcal{H}}^c_2]_p}=p^4=16$.\\
In summary, all solutions for the erased positions are given by
$$\begin{pmatrix}w^{0,1}\\ w^{0,2}\\w^{0,3}\\w^{1,1}\\w^{2,1}\\w^{2,2}\\w^{2,3}
 \end{pmatrix}=\begin{pmatrix}1\\0\\0\\1\\1\\0\\0\end{pmatrix}+
 2\begin{pmatrix}0\\c_1\\c_1\\1\\c_1+c_2\\1\\c_2\end{pmatrix}+4\begin{pmatrix}1+c_2+c_3+c_4+c_5+c_6\\c_3\\
 c_1+c_2+c_4+c_5+c_6\\0\\c_4\\c_5\\c_6\end{pmatrix}$$
with $c_1,c_2,c_3,c_4,c_5,c_6\in\mathcal{A}_2$, i.e., $$|S|=p^{0+2+4}=p^6=64.$$
 Note that for $c_1=c_2=c_3=c_3=c_4=c_5=c_6=0$, one gets the solution that leads to the original codeword we started with. Because of the constraint $T=2$, the vector $w^3$ is not recovered yet. However, since all other erasures are recovered, the remaining erasure $w^{3,1}$ can now easily be recovered.
\end{Ex}

Of course the smaller the size of the output the better. Obviously, this holds if $\rank [\widetilde{ \mathcal{H}}^c_t]_p$ is maximal.

\section{Complexity Analysis}

In this section, we briefly want to analyze the complexity of the presented decoding algorithm. As we work with the projections of elements from the finite ring $\mathbb Z_{p^r}$ in the finite field $\mathbb Z_p$, we can state the computational effort in terms of the number of necessary field operations in $\mathbb Z_p$.

\begin{Thm}
Denote by $e$ the maximal number of erasures that occur in a window of size $(T+1)n$. The number of necessary field operations in $\mathbb Z_p$ for our list decoding algorithm is
\begin{eqnarray*}O(re^2((n-k)(T+1))^{0.8}) &  \text{if}\ e\leq (n-k)(T+1)\\ O(re^{0.8}((n-k)(T+1))^{2}) & \text{if}\ e> (n-k)(T+1).\end{eqnarray*}
\end{Thm}

\begin{proof}
The step of the algorithm that is relevant for the complexity of the whole algorithm is to solve the system of linear equations in \eqref{eq:11}. This linear system has at most $(n-k)(T+1)$ equations and at most $e$ unknowns. It follows from \cite{st} that the number of field operations that is needed to do that is
\begin{eqnarray*}O(e^2((n-k)(T+1))^{0.8}) & \text{if}\ e\leq (n-k)(T+1)\\ O(e^{0.8}((n-k)(T+1))^{2}) & \text{if}\ e> (n-k)(T+1).\end{eqnarray*}

The theorem follows from the fact that we have to solve \eqref{eq:11} for $t=0,\hdots,r-1$, what gives us the factor $r$.
\end{proof}

\section*{Acknowledgements}
Julia Lieb acknowledges the support of the German Research Foundation grant LI 3101/1-1 and of the Swiss National Science Foundation grant n. 188430.  Diego Napp is partially supported by Ministerio de Ciencia e Innovación via the grant with ref. PID2019-108668GB-I00.
Raquel Pinto is supported by The Center for Research and Development
in Mathematics and Applications (CIDMA) through the Portuguese
Foundation for Science and Technology
(FCT - Funda\c{c}\~{a}o para a Ci\^{e}ncia e a Tecnologia),
references UIDB/04106/2020 and UIDP/04106/2020.

\bibliographystyle{plain}

\bibliography{biblio_com_tudo}

\end{document}

config: arxiv


TITLE: Show that $d(E,F) > 0$ - Is $E \times F$ is a compact set here?
QUESTION [2 upvotes]: Let $d(E,F)=\inf\{|z-w| : z \in E, w \in F\}$ where $E \subset
 \mathbb{C}$ is compact and $F \subset \mathbb{C}$ is closed such that
  $E \cap F = \emptyset$. Show that $d(E,F) > 0$; namely, $\mathbb{C}$ is a normed
  vector space.

It remains only to show that the minimum is in $\{|z-w| : z \in E, w \in F\}$. I think I can use the continuous function $|\cdot| : E \times F \to \mathbb{R}$ to show that $Im(f) = \{|z-w| : z \in E, w \in F\}$ is also compact.
Question : Is $E \times F$ a compact set here? Otherwise, how can I show that the minimum is in $\{|z-w| : z \in E, w \in F\}$?

REPLY [3 votes]: In a metric space $(X,d)$, the function $d:X\times X\to \Bbb R$ is notoriously continuous. Given a fixed non-empty subset $F\subseteq X$, the function \begin{align}&d(\bullet, F):X\to \Bbb R\\ &d(x,F)=\inf\,\{d(x,y)\,:\, y\in F\}\end{align} is continuous as well. By definition $d(E,F)=\inf\,\{x\in E\, :\, d(x,F)\}$, which, in your case, is actually a $\min$ because $E$ is compact.
Hence, there exists $\overline x\in E$ such that $d(\overline x,F)=d(E,F)$.
Hence, by definition of $d(\bullet, F)$, there is a sequence $\{y_n\}_{n\in\Bbb N}\subseteq F$ such that $d(\overline x, y_n)\searrow d(E,F)$.
Now, we use the fact that $X=\Bbb C$ and $d(x,y)=\lvert x-y\rvert$. The sequence $\{y_n\}_{n\in\Bbb N}$ is contained in the closed ball $H=E(\overline x,d(\overline x,y_1))$, centered in $\overline x$ with radius $d(\overline x,y_1)$. $H$ is closed and bounded, therefore sequentially compact. Therefore, $\{y_n\}_{n\in\Bbb N}$ has a convergent subsequence $y_{n_k}\to \overline y$.
It follows that $d(\overline x,\overline y)=\lim\limits_{k\to\infty}d\left(\overline x,y_{n_k}\right)=d(E,F)$. Since $F$ is closed, $\overline y\in F$.


TITLE: How to find eigenvalues and eigenvectors of Laplace operator?
QUESTION [2 upvotes]: I have a Laplace operator,
$$
L = \frac{\partial^{2}}{\partial x^{2}} + \frac{\partial^{2}}{\partial y^{2}},
$$
in polynomial space $ p(x, y)$.
How to find its eigenvectors and eigenvalues? I think, that eigenvalues is equal to zero.

REPLY [2 votes]: It would be hard to explain it all here, but using complex analysis you can show that the polynomials whose Laplacian are zero are exactly the polynomials that can be written as the real part of a complex polynomial, i.e. $f(x,y) = {\rm Re}(\sum_{i = 0}^n a_iz^i)$ for some complex numbers $a_0,...,a_n$. So for example $x^2 - y^2 = {\rm Re}(z^2)$ and $xy = {\rm Re}(-{iz^2 \over 2})$ work.
As benmachine mentioned, there are no nonzero eigenvalues.


TITLE: Why is $\sum\left(\left\lfloor\frac{x}{p}\right\rfloor+\left\lfloor\frac{x}{p^2}\right\rfloor+\dots\right)\log p=\sum\frac{x}{p}\log p+O(x)$?
QUESTION [3 upvotes]: Why is $\sum\limits_{\substack{p:\text{prime}\\p\le x\\}}\left(\left\lfloor\frac{x}{p}\right\rfloor+\left\lfloor\frac{x}{p^2}\right\rfloor+\dots\right)\log p=\sum\limits_{\substack{p:\text{prime}\\p\le x\\}}\frac{x}{p}\log p+O(x)$ ?

It is from here Proposition $4.3$. That the left sum is equal to $\sum\limits_{n\le x}\log n$ is clear, follows from a previous result but the $2$nd equality, I don't get

REPLY [1 votes]: We have $$\left\lfloor \frac{x}{p}\right\rfloor =\frac{x}{p}+O\left(1\right)
 $$ then $$\sum_{p\leq x}\left\lfloor \frac{x}{p}\right\rfloor \log\left(p\right)=\sum_{p\leq x}\frac{x}{p}\log\left(p\right)+O\left(\sum_{p\leq x}\log\left(p\right)\right)
 $$ and for each $l\geq2
 $ we have $$\sum_{p\leq x}\left\lfloor \frac{x}{p^{l}}\right\rfloor \log\left(p\right)\ll x\sum_{p\leq x}\frac{\log\left(p\right)}{p^{l}}\leq x\sum_{p\geq1}\frac{\log\left(p\right)}{p^{l}}\ll x
 $$ because the series $\sum_{p\geq1}\frac{\log\left(p\right)}{p^{l}}
 $ is convergent, then $$\sum_{p\leq x}\left(\left\lfloor \frac{x}{p}\right\rfloor +\left\lfloor \frac{x}{p^{2}}\right\rfloor +\dots\right)\log\left(p\right)=\sum_{p\leq x}\frac{x}{p}\log\left(p\right)+O\left(\sum_{p\leq x}\log\left(p\right)\right)+O\left(x\right)
 $$ but we know that $$\theta\left(x\right)=\sum_{p\leq x}\log\left(p\right)\ll x
 $$ then $$\sum_{p\leq x}\left(\left\lfloor \frac{x}{p}\right\rfloor +\left\lfloor \frac{x}{p^{2}}\right\rfloor +\dots\right)\log\left(p\right)=\sum_{p\leq x}\frac{x}{p}\log\left(p\right)+O\left(x\right).
 $$


text:
\begin{document}
\title{Asymptotic completeness in a class of massless relativistic quantum field theories}

\author{
{\bf Wojciech Dybalski\footnote{Supported by the DFG grant SP181/25-1.}}\\
Zentrum Mathematik, Technische Universit\"at M\"unchen,\\
D-85747 Garching, Germany\\
E-mail: {\tt dybalski@ma.tum.de}
\and
{\bf Yoh Tanimoto\footnote{Supported in part by the ERC Advanced Grant 227458
OACFT ``Operator Algebras and Conformal Field Theory''.}}\\
Dipartimento di Matematica, Universit\`a di Roma ``Tor
Vergata''\\ Via della Ricerca Scientifica, 1 - I--00133 Roma, Italy.\\
E-mail: {\tt tanimoto@mat.uniroma2.it}}
\date{}
\maketitle

\abstract{This paper presents the first examples of massless relativistic quantum field
theories which are interacting and asymptotically complete. These two-dimensional  theories
are obtained  by an application of a deformation procedure, introduced recently by Grosse and Lechner, to
chiral conformal quantum field theories. The resulting models may not be strictly local,
but they contain observables localized in spacelike wedges. It is shown that the
scattering theory for waves in two dimensions, due to Buchholz, is still valid under these weaker assumptions.
The concepts of interaction and asymptotic completeness, provided by this theory, are adopted
in the present investigation. }

\section{Introduction}
The interpretation of quantum field theories in terms of particles is a long-standing fundamental
problem \cite{Ha58, Ru62, LSZ55, CD82}.
The  last two decades  witnessed significant progress on this issue, both on the side of structural analysis
\cite{Bu90, Po04.1, Po04.2, Dy05, Dy09} and in the study of concrete models \cite{Sp97,DG99, FGS04, Le08}.
By combining  methods of algebraic quantum field theory \cite{Ha} with insights from the form-factor program \cite{SW00,BFK06},
the first  examples of local, relativistic quantum field theories,
which are interacting and asymptotically complete, have been constructed in \cite{Le08}  .
As this class contains only massive models, the question of asymptotic completeness in the
presence of massless particles is open to date in the local, relativistic framework. This
can be partly attributed to the infamous \emph{infrared problem}, which hinders rigorous construction and analysis
of interacting massless theories by traditional methods (see however \cite{CRW85, BFM04,ZZ92}). It is therefore remarkable that more
recent constructive tools, developed in \cite{BLS10}, give rise to massless models which are asymptotically complete and
interacting.  We exhibit such theories in the present work.

We recall that a new class of  relativistic quantum field theories, including both massive and massless models,
has been  obtained recently by a certain deformation procedure akin to the Rieffel  deformation \cite{GL08,BS08,BLS10,DLM10}.
These theories are wedge-local i.e. observables can be localized
in (unbounded)  wedge-shaped regions extending in spacelike directions. In the massive case  this
remnant of locality suffices for a canonical construction of the two-body scattering matrix, as shown
in \cite{BBS01}. Exploiting this fact, it was demonstrated in \cite{GL08,BS08} that the deformed theory
is interacting even if the original theory is not. As in general only two-body scattering states are available,
it may seem that the problem of asymptotic completeness cannot be  addressed in the framework of wedge-local theories.
However, in the case of two-dimensional massless theories such a conclusion would be pre-mature, as we demonstrate in this  paper.

Our first task is to provide a scattering theory for such models.
We recall that for \emph{local} two-dimensional theories of massless excitations a scattering theory
was  developed in \cite{Bu75}. The basic building blocks of this construction are the subspaces $\hil_+$
and $\hil_-$ in the physical Hilbert space $\hil$, corresponding to the right and left branch of
the lightcone in momentum space. These subspaces carry representations of the Poincar\'e group
which are in general highly reducible. Thus vectors $\Psi_{\pm}\in \hil_{\pm}$ do not describe
particles in the Wigner sense, but rather composite objects, called in \cite{Bu75} 'waves'.
In view of their dispersionless motion, a composition of several waves traveling in the
same direction (say elements of  $\hil_+$), gives rise to another wave from $\hil_+$. Thus it suffices
to consider scattering states $\Psi_+\pout\Psi_-$ (resp. $\Psi_+\pin\Psi_-$) which describe
two waves traveling in the opposite directions in the remote future (resp. past). They span the subspaces
$\hil^{\tout}$ (resp. $\hil^{\tin}$) of the outgoing (resp. incoming) states.
The scattering operator $S:\hil^{\tout}\to \hil^{\tin}$ can be defined as an isometry mapping $\Psi_+\pout\Psi_-$ into $\Psi_+\pin\Psi_-$.
If $\hil^{\tout}=\hil^{\tin}=\hil$, then we say that the theory is asymptotically complete.
As we will show,  there exists a large class of non-interacting massless theories  in two-dimensional spacetime which have this property: it includes all chiral conformal quantum field theories.

In the light of the above discussion, it is not surprising that the scattering theory  from \cite{Bu75} can be generalized to the wedge-local context. Indeed, observables localized in two opposite spacelike wedges suffice to separate two waves traveling in opposite directions. We demonstrate
this fact in Section~\ref{scattering} after some introductory remarks on wedge-local quantum
field theories. In Section~\ref{deformation} we express the scattering matrix $S_{\ka}$ of the
deformed theory (with a deformation parameter $\ka$), by the scattering matrix $S$ of the original one. We obtain
\beq
S_{\ka}=e^{i\ka M^2}S,
\eeq
where $M$ is the mass operator. Hence, similarly as in the massive case,  the deformed theory is interacting, even  if the original theory is not. Moreover, the property of asymptotic completeness  is preserved by the deformation procedure. Thus, as we show in Section~\ref{chiral}, deformations of chiral conformal field theories give rise to wedge-local theories which are interacting and asymptotically complete.  We summarize our results in Section~\ref{conclusions}, where also some open questions are discussed.

\section{Scattering theory}\label{scattering}

A convenient framework for the study of  wedge-local theories is provided  by the concept of a Borchers triple \cite{Bo92}. We recall that a Borchers triple $(\mcR,U,\Om)$, (relative to the wedge $\mcW=\{\, x=(x^0,x^1)\in \real^2\,|\, x^1\geq |x^0|\,\}$),
consists of:

\begin{enumerate}

\item[(a)] a von Neumann algebra $\mcR\subset B(\hil)$,

\item[(b)] a strongly continuous unitary representation $U$ of $\real^2$ on $\hil$,
whose spectrum $\spec\, U$ is contained in the closed forward lightcone
$V_+=\{\, p=(p^0,p^1)\in\real^2\,|\, p^0\geq |p^1| \,\}$ and which satisfies $\al_x(\mcR)\subset \mcR$,
for $x\in \mcW$, where $\al_x(\,\cdot\,)=U(x)\,\cdot\,U(x)^{-1}$,

\item[(c)] a unit vector $\Om\in\hil$ which is invariant under the action of $U$ and is
cyclic and separating for $\mcR$. It will be called the vacuum vector.

\end{enumerate}

One interprets $\mfa(\mcW):=\mcR$ as the algebra of all observables localized
in the wedge $\mcW$. In view of (c), one can apply to $(\mcR,\Om)$ the Tomita-Takesaki theory and we denote by $(\Delta,J)$ the modular operator and the conjugation. As shown in \cite{Bo92}, with the help of the modular
objects one can construct an (anti-)unitary representation $\la\to \ti U(\la)$ of the proper Poincar\'e group $\mcP_+$
which extends the original representation of translations. In particular, $J$ implements the spacetime reflection i.e.
\beq
JU(x)J=U(-x), \quad x\in\real^2. \label{inversion}
\eeq
Thus with any wedge $\la \mcW$ one can associate the algebra of observables $\mfa(\la\mcW)=\ti U(\la)\mcR \ti U(\la)^{-1}$.
Since,  by the Tomita-Takesaki theory, $J\mcR J=\mcR'$, the resulting net is
wedge-local i.e $\mfa((\la\mcW)')=\mfa(\la\mcW)'$, where $(\la\mcW)'$ is the causal complement of $\la\mcW$ and a prime over an algebra denotes the commutant. Hence this net  gives rise to a (two-dimensional) wedge-local, relativistic quantum field theory. See \cite{Bo92, Fl98} for proofs of the above statements and \cite{BLS10} for a more detailed overview.

Let $(H,P)$ be the generators of $U$ i.e. $U(x^0,x^1)=e^{iHx^0-iPx^1}$.
We set $\hil_{\pm}=\ker\, (H\mp P)$ and denote by $P_{\pm}$ the corresponding projections.
We assume that  $\hil_+\cap\hil_-=[c\Om]$ i.e. $\Om$ is the  unique (up to a phase) unit vector
which is invariant under translations. This
implies that $\hil_+\cap[c\Om]^\bot$ is orthogonal to $\hil_-\cap[c\Om]^\bot$.
We assume that the latter two subspaces are non-trivial, to ensure that the theory contains massless excitations.
Let us now describe briefly their collision theory. The construction follows closely  \cite{Bu75}.

For any $F\in B(\hil)$ and $x\in\real^2$ we denote $F(x):=\al_x(F)$ and define the sequences of operators
\beq
F_{\pm}(h_T)=\int dt\,h_T(t)F(t_{\pm})\textrm{ with } t_{\pm}=(t,\pm t),
\eeq
where $h_T(t)=|T|^{-\eps}h(|T|^{-\eps}(t-T))$, $0<\eps<1$ and $h\in C_0^{\infty}(\real)$ is a non-negative, symmetric  function
s.t. $\int dt\, h(t)=1$. With the help of these approximating sequences we construct the asymptotic fields corresponding to the wedge~$\mcW$.

\bel\label{right-wedge-lemma} Let $F\in \mcR$.  Then the limits
\beqa
\Phi_+^{\tout}(F):=\underset{T\to\infty}{\slim}\textrm{ }F_{+}(h_T), \quad
\Phi_-^{\tin}(F):=\underset{T\to-\infty}{\slim}\textrm{ }F_{-}(h_T),\label{minus-in}
\eeqa
exist and are elements of $\mcR$. They depend only on the respective vectors $\Phi_+^{\tout}(F)\Om=P_+F\Om$, $\Phi_-^{\tin}(F)\Om=P_-F\Om$ and  satisfy
\begin{enumerate}
\item[(a)] $\Phi_+^{\tout}(F)\hil_+\subset\hil_+, \quad\Phi_-^{\tin}(F)\hil_-\subset\hil_-$,

\item[(b)] $\al_x(\Phi_+^{\tout}(F))=\Phi_+^{\tout}(\al_x(F)),\quad \al_x(\Phi_-^{\tin}(F))=\Phi_-^{\tin}(\al_x(F))$ for $x\in\mcW$.

\end{enumerate}
\eel

\proof Let us consider the first limit in (\ref{minus-in}).
Since there holds the estimate $\|F_{+}(h_T)\|\leq \|F\|\int dt\, |h(t)|$, it suffices to show the convergence
on the dense set of vectors $R'\Om$. First,  using the mean ergodic theorem, one checks that
\beq
\underset{T\to\infty}{\slim}\textrm{ }F_{+}(h_T)\Om=P_+F\Om. \label{ergodic}
\eeq
In view of part (b) of the definition of the Borchers triple and the fact that $t_+\in\mcW$, we obtain that $F_{+}(h_T)\in\mcR$ for  $T$
sufficiently large. Hence, for any $F'\in R'$,
\beq
\underset{T\to\infty}{\slim}\textrm{ }F_{+}(h_T)F'\Om=F'P_+F\Om,
\eeq
which proves the convergence. Since $\mcR$ is a von Neumann algebra, the limit $\Phi_+^{\tout}(F)$ is an element of $\mcR$.
Since $\Om$ is separating for $\mcR$,  this operator depends only on $\Phi_+^{\tout}(F)\Om=P_+F\Om$.

The second part of (\ref{minus-in}) is proven analogously. Property (a) follows by an application of the mean ergodic theorem,
similarly as in (\ref{ergodic}). Property (b) is obvious from the definitions of $\Phi_+^{\tout}$, $\Phi_-^{\tin}$. \qed\\

Let us now define the asymptotic fields corresponding to the wedge $\mcW'$.
Keeping in mind that $J\mcR'J=\mcR$, we set for any  $F'\in\mcR'$
\beq
\Phi_+^{\tin}(F'):=J\Phi_+^{\tout}(JF'J)J, \quad \Phi_-^{\tout}(F'):=J\Phi_-^{\tin}(JF'J)J.
\eeq
Making use of formula~(\ref{inversion}),
we easily obtain the following counterpart of  Lemma~\ref{right-wedge-lemma}.

\bel \label{left-wedge-lemma} Let $F'\in \mcR'$.  Then
\beqa
\Phi_+^{\tin}(F')=\underset{T\to-\infty}{\slim}\textrm{ }F'_{+}(h_T), \quad
\Phi_-^{\tout}(F')=\underset{T\to\infty}{\slim}\textrm{ }F'_{-}(h_T).\label{minus-in-in}
\eeqa
These operators depend only on the respective vectors $\Phi_+^{\tin}(F')\Om=P_+F'\Om$, $\Phi_-^{\tout}(F')\Om=P_-F'\Om$ and  satisfy
\begin{enumerate}
\item[(a)] $\Phi_+^{\tin}(F')\hil_+\subset\hil_+, \quad\Phi_-^{\tout}(F')\hil_-\subset\hil_-$,

\item[(b)] $\al_{x}(\Phi_+^{\tin}(F'))\!\!=\!\!\Phi_+^{\tin}(\al_{x}(F')),\quad \al_{x}(\Phi_-^{\tout}(F'))\!\!=\!\!\Phi_-^{\tout}(\al_{x}(F'))$ for $x\in\mcW'$.

\end{enumerate}

\eel

Let us now proceed to the construction of scattering states.
Clustering properties of the asymptotic fields are of importance here. Proceeding as in \cite{Bu75}, we note that for any $F,G\in\mcR$, $F',G'\in\mcR'$ there holds
\beqa
& & \!\!\!\!\!\!\!\!(\Phi_+^{\tout}(F)\Phi_-^{\tout}(F')\Om| \Phi_+^{\tout}(G)\Phi_-^{\tout}(G')\Om)\non\\
& &\ph{444444444444}=(\Phi_+^{\tout}(G)^*\Phi_+^{\tout}(F)\Om|\Phi_-^{\tout}(F')^*\Phi_-^{\tout}(G')\Om)\non\\
 & &\ph{444444444444}=(\Phi_+^{\tout}(F)\Om|\Phi_+^{\tout}(G)\Om)(\Phi_-^{\tout}(F')\Om|\Phi_-^{\tout}(G')\Om), \label{clustering-property}
\eeqa
where in the last step we made use of Lemma~\ref{right-wedge-lemma}~(a), Lemma~\ref{left-wedge-lemma}~(a) and of the fact that $\hil_+\cap [c\Om]^{\bot}$ is orthogonal to $\hil_-\cap[c\Om]^{\bot}$.

Now for any $\Psi_+\in\hil_+$, (resp. $\Psi_-\in\hil_-$) we choose, with the help of property (c) of the Borchers triple, a sequence
$\{F_n\}_{n\in\nat}$ of elements of $\mcR$ (resp. a sequence $\{F_n'\}_{n\in\nat}$ of elements of $\mcR'$) s.t.
$\underset{n\to\infty}{\slim}\textrm{ }P_+F_n\Om=\Psi_+$ (resp.  $\underset{n\to\infty}{\slim}\textrm{ }P_+F_n'\Om=\Psi_-$).
By relation~(\ref{clustering-property}), the limit
\beq
\Psi_+\pout \Psi_-:=\underset{n\to\infty}{\slim}\textrm{ }\Phi_+^{\tout}(F_{n})\Phi_-^{\tout}(F'_{n})\Om \label{limiting}
\eeq
exists and does not depend on the choice of the sequences within the above restrictions. We will call it
the outgoing scattering state. Next, we define the incoming scattering states as follows
\beq
\Psi_+\pin\Psi_-:=J((J\Psi_+)\pout (J\Psi_-)). \label{incoming}
\eeq
This definition is meaningful, since relation~(\ref{inversion}) gives $J\hil_+\subset\hil_+$ and $J\hil_-\subset \hil_-$. It is easily seen, that for suitable sequences $\{G_n\}_{n\in\nat}$ (resp. $\{G'_n\}_{n\in\nat}$) of elements of $\mcR$ (resp. of $\mcR'$), there holds
\beq
\Psi_+\pin\Psi_-=\underset{n\to\infty}{\slim}\textrm{ }\Phi_+^{\tin}(G'_{n})\Phi_-^{\tin}(G_{n})\Om, \label{in-limiting}
\eeq
similarly as in (\ref{limiting}).  The states constructed above have the following basic properties which justify their interpretation as scattering states:

\bel\label{lemma-three} For any $\Psi_\pm,\Psi_\pm'\in\hil_\pm$
\begin{enumerate}
\item[(a)] $(\Psi_+\pout \Psi_-,\Psi'_+\pout \Psi'_-)=(\Psi_+,\Psi'_+)(\Psi_-,\Psi'_-)$,
\item[(b)] $U(x)(\Psi_+\pout \Psi_-)=(U(x)\Psi_+)\pout (U(x)\Psi_-)$, for $x\in\real^2$.
\end{enumerate}
Analogous relations hold for  the incoming scattering states.
\eel

\proof Part (a) follows immediately from relation~(\ref{clustering-property}). As for part (b), for
any $x\in\real^2$ we can choose such $y\in\mcW$ and $y'\in\mcW'$ that $x+y\in \mcW$ and $x+y'\in \mcW'$.
We choose a sequence $\{F_n\}_{n\in\nat}$ of elements of $\mcR$ and $\{F_n'\}_{n\in\nat}$ of elements of $\mcR'$ s.t. $\underset{n\to\infty}{\slim}\textrm{ }P_+F_n(y)\Om=\Psi_+$ and $\underset{n\to\infty}{\slim}\textrm{ }P_-F_n'(y')\Om=\Psi_-$. Then
\beqa
U(x)(\Psi_+\pout \Psi_-)&=&\underset{n\to\infty}{\slim}\textrm{ }
\al_x(\Phi_+^{\tout}(F_{n}(y)))\al_x(\Phi_-^{\tout}(F'_{n}(y')))\Om\non\\
&=&\underset{n\to\infty}{\slim}\textrm{ }\al_{x+y}(\Phi_+^{\tout}(F_{n}))\al_{x+y'}(\Phi_-^{\tout}(F'_{n}))\Om\non\\
&=&\underset{n\to\infty}{\slim}\textrm{ }\Phi_+^{\tout}(F_{n}(x+y) )\Phi_-^{\tout}(F'_{n}(x+y'))\Om,
\eeqa
where we applied Lemma~\ref{right-wedge-lemma}~(b) and Lemma~\ref{left-wedge-lemma}~(b) in the second and third step.
We note that the last state on the r.h.s. above
is just $(U(x)\Psi_+)\pout (U(x)\Psi_-)$, completing the proof of (b).
The statement concerning the incoming states follows immediately from the properties of the outgoing states and from definition~(\ref{incoming}). \qed\\

After this preparation, we introduce the scattering subspaces
\beq
\hil^{\tin}=\hil_+\pin\hil_- \textrm{ and } \hil^{\tout}=\hil_+\pout \hil_-,
\eeq
which are spanned by the respective scattering states. In view of Lemma~\ref{lemma-three}, they
are canonically isomorphic to the tensor product $\hil_+\otimes\hil_-$. Similarly as in \cite{Bu75},
we define the scattering operator
$S: \hil^{\tout}\to\hil^{\tin}$, extending by linearity the following
relation:
\beq
S(\Psi_+\pout \Psi_-)=\Psi_+\pin\Psi_-. \label{scattering-matrix}
\eeq
By Lemma~\ref{lemma-three} this map is an isometry and it is invariant under translations. If
$S$ differs from (a constant multiple of) the identity transformation on $\hil^{\tin}$, then we say
that the theory is interacting. If $\hil^{\tin}=\hil^{\tout}=\hil$, then we say that the theory is asymptotically complete.
In the next two sections we exhibit a class of theories which
satisfy these two properties.

To conclude this section, we point out that the asymptotic fields form new Borchers triples,
which are non-interacting and asymptotically complete.
In view of Lemma~\ref{right-wedge-lemma}~(a) and Lemma~\ref{left-wedge-lemma}~(a),  we can define the following von Neumann algebras acting on $\hil^{\tas}:=\hil_{+}\otimes\hil_-$:
\beqa
\mcR^{\te{as}}&:=&\{\Phi_{+}^{\tout}(F)|_{\hil_{+}}\otimes \Phi_{-}^{\tin}(G)|_{\hil_{-}}  \,|\, F, G\in\mcR\, \}'',\label{first-asymptotic}\\
(\mcR')^{\te{as}}&:=&\{\Phi_+^{\tin}(F')|_{\hil_{+}}\otimes \Phi_-^{\tout}(G')|_{\hil_{-}}    \,|\,
F', G'\in\mcR' \, \}''. \label{second-asymptotic}
\eeqa
Moreover, we set $U^{\te{as}}(x)=U(x)|_{\hil_+}\otimes U(x)|_{\hil_-}$ and $\Om^{\te{as}}=\Om\otimes\Om$.
Clearly, there holds
\beq
\spec\, U^{\te{as}}=\spec\,U|_{\hil_+}+\spec\,U|_{\hil_-}\subset V_+.
\eeq
and $\Om^{\te{as}}$ is the  unique (up to a phase) unit vector which is invariant under the action of $U^{\tas}$.
Since $\Om^{\te{as}}$ is cyclic for  $\mcR^{\te{as}}$
and $(\mcR')^{\te{as}}$, and $(\mcR')^{\te{as}}\subset (\mcR^{\te{as}})'$, we obtain
that  $(\mcR^{\te{as}}, U^{\te{as}}, \Om^{\te{as}})$
is a Borchers triple w.r.t. $\mcW$. We call it the asymptotic Borchers triple of $(R,U,\Om)$.
It has the following properties:

\bep\label{asymptotic-BT} The Borchers triple $(\mcR^{\te{as}}, U^{\te{as}}, \Om^{\te{as}})$ defined above
gives rise to an asymptotically complete and non-interacting wedge-local quantum field theory.
Moreover, $\spec\,U^{\te{as}}=V_+$.
\eep

\proof Making use of the fact that $(\mcR')^{\te{as}}\subset (\mcR^{\te{as}})'$, we obtain the equalities
\beqa
& &\Phi_{+}^{\tout}(\Phi_{+}^{\tout}(F)|_{\hil_{+}}\otimes I )\Om^{\te{as}}=P_+F\Om\otimes\Om,\\
& &\Phi_{-}^{\tout}(I\otimes\Phi_{-}^{\tout}(F')|_{\hil_{-}} )\Om^{\te{as}}=\Om\otimes P_-F'\Om,
\eeqa
valid for any $F\in\mcR$, $F'\in\mcR'$. Thus we  conclude that $\hil^{\tas}_{+}\supset \hil_+\otimes [c\Om]$
and $\hil^{\tas}_{-}\supset  [c\Om]\otimes \hil_-$. Let $\Psi_{\pm}\in\hil_{\pm}$ and let
$\{F_n\}_{n\in\nat}$ (resp. $\{F_n'\}_{n\in\nat}$) be a sequence of elements of $\mcR$ (resp. $\mcR'$)
s.t.  $\underset{n\to\infty}\slim\, P_+F_n\Om=\Psi_+$ (resp. $\underset{n\to\infty}\slim\, P_-F_n'\Om=\Psi_-$).
Then we get
\beqa
& &(\Psi_+\otimes\Om)\pout (\Om\otimes\Psi_-)\non\\
& &=\slim_n\Phi_{+}^{\tout}(\Phi_{+}^{\tout}(F_n)|_{\hil_{+}}\otimes I )
\Phi_{-}^{\tout}(I\otimes\Phi_{-}^{\tout}(F'_n)|_{\hil_{-}} )\Om^{\te{as}}\non\\
& &=\Psi_+\otimes\Psi_-. \label{asymptotic-outgoing}
\eeqa
By an analogous argument, we verify that
\beq
(\Psi_+\otimes\Om)\pin (\Om\otimes\Psi_-)=\Psi_+\otimes\Psi_-. \label{asymptotic-incoming}
\eeq
We infer from equalities (\ref{asymptotic-outgoing}) and (\ref{asymptotic-incoming}) that $(\hil^{\tas})^{\tout}=(\hil^{\tas})^{\tin}=\hil^{\tas}$  (i.e. asymptotic completeness holds)
and $S=I$ (i.e. the theory is non-interacting).

To justify the statement concerning the spectrum of $U^{\tas}$, we recall that $\hil_+\cap[c\Om]^{\bot}$
and $\hil_-\cap [c\Om]^{\bot}$ are assumed to be non-trivial. Consequently,  $\spec\, U|_{\hil_+}$ and
$\spec\, U|_{\hil_-}$ have some non-zero elements. From the existence of the unitary representation of
the Poincar\'e group $\ti U$, associated with the triple $(\mcR, U,\Om)$, we conclude that these
two spectra coincide with the right and left branch of the lightcone, respectively.  Since
$\spec\, (U|_{\hil_+}\otimes U|_{\hil_-})=\spec\, U|_{\hil_+}+\spec\, U|_{\hil_-}$, the statement
follows. \qed

\section{Deformations and interaction}\label{deformation}

In the previous section we showed that for any Borchers triple in two-dimensional spacetime
(with a unique vacuum state) we can canonically construct the scattering operator $S$ which
describes collisions of massless particles (or rather 'waves').
In this section we consider a class of deformations of Borchers triples, introduced in \cite{BLS10},
and study their effect on the scattering operator.
Similarly as in the massive case \cite{GL08,BS08}, the deformed theory turns out to be interacting, even if the original one is not. Moreover, we show that the property of asymptotic completeness is preserved under these deformations.

Let us recall briefly the deformation procedure of \cite{BLS10}.
Let $(\mcR, U, \Om)$ be a Borchers triple w.r.t. the wedge $\mcW$. We denote by $\mcR^\infty$ the subset of
elements of $\mcR$ which are smooth under the action of $\al$ in the norm topology.
(It is easy to see that $\mcR^{\infty}$ is a  dense subalgebra of $\mcR$ in the strong operator topology).
Let $\mcD$ be the dense domain of vectors which are smooth w.r.t. to
the action of $U$. Then, as shown in \cite{BLS10}, one can define for any $F\in\mcR^{\infty}$,
and a matrix $Q$, antisymmetric w.r.t. the Minkowski scalar product $(x,y)\to xy$, the warped convolution
\beq
F_Q=\int dE(x)\,\al_{Qx}(F)
:=\lim_{\eps\searrow 0}(2\pi)^{-2}\int d^2x\, d^2y\, f(\eps x,\eps y) e^{-ixy}\al_{Qx}(F)U(y) \label{warped}
\eeq
where $dE$ is the spectral measure of $U$ and $f\in S(\real^2\times\real^2)$ is s.t. $f(0,0)=1$.
The limit exists in the strong sense on vectors from $\mcD$ and is independent of the function $f$
within the above restrictions. We set
\beq
\mcR_{Q}:=\{\, F_Q\,|\, F\in\mcR^{\infty}\,\}''.
\eeq
Let us now restrict attention to the following family of  matrices
\beqa
Q_{\ka}=\left(\begin{array}{cc} 0 & \ka \\
 \ka & 0 \end{array} \right),
\eeqa
where $\ka>0$, and recall a result from \cite{BLS10}:

\bet\label{BLS-theorem} If $(\mcR, U, \Om)$ is a Borchers triple w.r.t. $\mcW$, then
$(\mcR_{Q_{\ka}}, U, \Om)$ is also a Borchers triple w.r.t. $\mcW$. Moreover,
$(\mcR')_{-{Q}_{\ka}}\subset (\mcR_{Q_{\ka}})'$.
\eet

Our goal is to  express the scattering operator
$S_{\ka}$ of the deformed theory $(\mcR_{Q_{\ka}}, U, \Om )$ by the scattering operator $S$ of the original
theory $(\mcR, U, \Om)$.  To this end, we prove the  following fact.

 \bet\label{states-deformations} For any $\Psi_{\pm}\in\hil_{\pm}$  the following relations hold:
 \beqa
 & &\Psi_+\kpout \Psi_-=e^{-i\h\ka (H^2-P^2)}(\Psi_+\pout \Psi_-),\label{out}\\
 & &\Psi_+\kpin \Psi_-=e^{i\h\ka (H^2-P^2)}(\Psi_+\pin \Psi_-), \label{in}
 \eeqa
 where on the l.h.s. (resp. r.h.s.) there appear the scattering states of the deformed (resp. undeformed) theory.
  \eet

\proof Let us first prove relation (\ref{out}).
 To this end, we pick $F\in\mcR^\infty$,
 $F'\in(\mcR')^{\infty}$.  We set $\Psi_+=P_+F\Om=P_+F_{\Q}\Om$ and $\Psi_-=P_-F'\Om=P_-F'_{-\Q}\Om$,
 where we exploited the translational invariance of the state $\Om$.
 Since $F_{\Q}\in\mcR_{\Q}$ and, by Theorem~\ref{BLS-theorem}, $F'_{-\Q}\in(\mcR_{\Q})'$, the outgoing state of
 the deformed theory is given by
\begin{align}
\Psi_+\kpout \Psi_-
 =\lim_{T\to\infty}F_{\Q,+}(h_T)F'_{-\Q,-}(h_T)\Om
 =\lim_{T\to\infty}F_{\Q,+}(h_T)F'_{-}(h_T)\Om\non\\
=\lim_{T\to\infty}\lim_{\eps\searrow 0}(2\pi)^{-2}\int d^2x\, d^2y\, f(\eps x,\eps y) e^{-ixy}\al_{Qx}(F_{+}(h_T))F'_-(h_T)(y)\Om, \label{deformed-outgoing}
\end{align}
where in the last step we made use of the fact that $F'_-(h_T)\Om\in\mcD$, and that
$\Om$ is invariant under translations. To exchange the order of the limits, we use methods from the proof of Lemma 2.1 of \cite{BLS10}:
We note that for each polynomial $(x,y)\to L(x,y)$, there exists a polynomial $(x,y)\to K(x,y)$
s.t
\beq
L(x,y)e^{-ixy}=K(-\pa_x,-\pa_y)e^{-ixy}.
\eeq
We choose $L$ so that $L^{-1}$ and its derivatives are absolutely integrable. Denoting temporarily
$\Psi_T(x,y):=\al_{Qx}(F_{+}(h_T))F'_-(h_T)(y)\Om$,
we obtain
\beqa
& &\ph{44}\lim_{\eps\searrow 0}(2\pi)^{-2}\int d^2x\, d^2y\, f(\eps x,\eps y) e^{-ixy} \Psi_T(x,y)  \non\\
& &=\lim_{\eps\searrow 0}(2\pi)^{-2}\int d^2x\, d^2y\,  e^{-ixy}K(\pa_x,\pa_y)f(\eps x,\eps y) L(x,y)^{-1}\Psi_T(x,y)\non\\
& &\ph{444444444}=(2\pi)^{-2}\int d^2x\, d^2y\,  e^{-ixy}K(\pa_x,\pa_y) L(x,y)^{-1}\Psi_T(x,y),
\label{mollifiers}
\eeqa
where in the first step we integrated by parts and in the second step we applied
the dominated convergence theorem. To obtain the last expression, we used the fact that
derivatives of $(x,y)\to f(\eps x, \eps y)$ contain powers of $\eps$ and thus vanish
in the limit. Substituting this expression to formula~(\ref{deformed-outgoing}) and making use again of
the dominated convergence theorem,  we arrive at
\beqa
\Psi_+\kpout \Psi_-\ph{44444444444444444444444444444444444444444444444444}\non\\
=(2\pi)^{-2}\int d^2x\, d^2y\,  e^{-ixy}K(\pa_x,\pa_y) L(x,y)^{-1}
(U(Qx)\Psi_+)\pout (U(y)\Psi_-). \label{deformed-outgoing-state}
\eeqa
To interchange the limit $T\to\infty$ with the action of the derivatives, we exploited the fact that for any
$F_1\in\mcR^{\infty}$, $\mu\in\{0,1\}$, the derivative $\pa_{x^{\mu}}F_1:= (\pa_{x^{\mu}}F_1(x))|_{x=0}$
is an element of $\mcR^{\infty}$ and $\Phi_+^{\tout}(\pa_{x^{\mu}}F_1)(x)=\pa_{x^{\mu}}\Phi_+^{\tout}(F_1)(x)$. This  equality (as well as its counterpart for $\Phi_-^{\tout}$) follows immediately from the norm continuity of the respective map.

To analyze expression~(\ref{deformed-outgoing-state}), we will exploit some special features of massless theories
in two dimensions. First, we recall that $(H-P)\Psi_+=0$, and therefore
 \beqa
 U(\Q x)\Psi_+=e^{i\ka(Hx^1-Px^0)}\Psi_+
 =e^{-i\h\ka (H+P)(x^0-x^1)}\Psi_+.
 \eeqa
 Similarly, since $(H+P)\Psi_-=0$, we obtain
 \beq
 U(y)\Psi_-=e^{i\h(H-P)(y^0+y^1)}\Psi_-.
 \eeq
 Hence, exploiting the equalities $(H\pm P)\Psi_{\mp}=0$ and Lemma~\ref{lemma-three}~(b), we get
 \beqa
 (U(Qx)\Psi_+)\pout (U(y)\Psi_-)&=&e^{-\frac{i}{2}\ka (H+P)(x^0-x^1)}e^{\frac{i}{2}(H-P)(y^0+y^1)}(\Psi_+\pout\Psi_-)\non\\
 &=&U(v(x,y))(\Psi_+\pout\Psi_-),
 \eeqa
 where $v(x,y)=(\h(y^0+y^1-\ka x^0+\ka x^1), \h(y^0+y^1+\ka x^0-\ka x^1))$.
 We substitute this expression to formula (\ref{deformed-outgoing-state}), obtaining
 \beqa
 (\Psi_+\kpout \Psi_-) \ph{4444444444444444444444444444444444444444444444}\non\\
=(2\pi)^{-2}\int d^2x\, d^2y\,  e^{-ixy}K(\pa_x,\pa_y) L(x,y)^{-1}
  U(v(x,y))  (\Psi_+\pout\Psi_-)\non\\
=\int\bigg(\lim_{\eps\searrow 0}(2\pi)^{-2}\int d^2x\, d^2y\,  e^{-ixy}f(\eps x,\eps y)
  e^{ip v(x,y)}\bigg) dE(p)(\Psi_+\pout\Psi_-). \label{long-formula}
 \eeqa
 Here in the second step we expressed $U(v(\cdot,\cdot))$ as a spectral integral
 and used the Fubini theorem to exchange the order of integration.
 Then  we reversed the steps which led to formula~(\ref{mollifiers}). Now we
 analyze the function in the bracket above. Setting $p^{\pm}=\h(p^0\pm p^1)$, we get
 \begin{align}
  & (2\pi)^{-2}\int d^2x\, d^2y\,  e^{-ixy}f(\eps x,\eps y)e^{ip v(x,y)}\non\\
 =&(2\pi)^{-2}\int d^2x\, d^2y\,
 f(\eps(x^0,x^1),\eps(y^0,y^1))
 e^{-i(\ka p^++y^0)x^0}e^{i(\ka p^++y^1)x^1}
 e^{ip^-(y^0+y^1)}\non\\
 =&(2\pi)^{-1}\int\, d^2y\, \eps^{-2}\hat f( -\eps^{-1} (\ka p^++y^0,\ka p^++y^1),
 \eps(y^0,y^1))
 e^{ip^-(y^0+y^1)}\non\\
 =&(2\pi)^{-1}\int\, d^2y\, \hat f( -(y^0,y^1),\eps(\eps y^0-\ka p^+,\eps y^1-\ka p^+))
 e^{ip^-((y^0+y^1)\eps-2\ka p^+)}.\ph{4444}
 \end{align}
 Here $\hat f$ denotes the Fourier transform of $f$ w.r.t. the $x$ variable
 and in the last step we exploited the change of variables:
 $(y^0,y^1)\to \big(\eps y^0-\ka p^+,\eps y^1-\ka p^+\big)$.
 Making use of the dominated convergence theorem, we  perform the limit
 $\eps\searrow 0$, obtaining
 \beq
 \lim_{\eps\searrow 0}(2\pi)^{-2}\int d^2x\, d^2y\,  e^{-ixy}f(\eps x,\eps y)e^{ip v(x,y)}
 =e^{-i\h\ka ((p^0)^2-(p^1)^2)}.
 \eeq
 In view of formula~(\ref{long-formula}), this completes the proof of (\ref{out}) for  dense sets of vectors $\Psi_{\pm}\in\hil_{\pm}$.
 For arbitrary $\Psi_{\pm}$ the statement follows by the limiting procedure~(\ref{limiting}).

 The statement~(\ref{in}) concerning the incoming states can be shown using formula~(\ref{in-limiting}) and
an obvious modification of the above argument. We obtain it however more directly, using
formula~(\ref{out}) and definition~(\ref{incoming}):
\beqa
\Psi_+\kpin \Psi_-=J((J\Psi_+)\kpout (J\Psi_-))&=&J\big(e^{-\frac{i}{2}\ka (H^2-P^2)}( (J\Psi_+)\pout (J\Psi_-) ) \big)\non\\
&=&e^{\frac{i}{2}\ka (H^2-P^2)}( \Psi_+\pin \Psi_-).
\eeqa
Here in the last step we made use of the fact, shown in \cite{BLS10}, that the modular objects of the deformed and undeformed theory
coincide. We also exploited the relation $Jg(H,P)J= g(H,P)^*$, valid for any bounded, measurable function $g$, which follows from formula (\ref{inversion}). \qed\\

We immediately obtain the following corollary:

\bec\label{corollary} Let $S$  be the scattering operator of $(\mcR, U, \Om)$ and let $S_{\ka}$ be the scattering operator
of $(\mcR_{Q_{\ka}}, U, \Om)$. Then
\beq
S_{\ka}=e^{i\ka (H^2-P^2)}S. \label{correction}
\eeq
In particular, if the original theory is asymptotically complete and non-interacting,
and $\spec\,U=V_+$,  then the deformed theory is asymptotically complete
and interacting.

\eec

\proof Making use of Theorem~\ref{states-deformations}  and of the invariance of the scattering operator under translations, we obtain
\beqa
S_{\ka}(\Psi_+\kpout \Psi_-)&=&\Psi_+\kpin \Psi_-\non\\
&=&e^{i\h\ka (H^2-P^2)}(\Psi_+\pin \Psi_-)\non\\
&=&e^{i\h\ka (H^2-P^2)}S(\Psi_+\pout \Psi_-)\non\\
&=&e^{i\ka (H^2-P^2)}S(\Psi_+\kpout \Psi_-).
\eeqa
This proves formula~(\ref{correction}). The property of asymptotic completeness is preserved under the deformation,
since $e^{i\ka (H^2-P^2)}$ is a unitary. If $\hil^{\tout}=\hil$, $S=I$ and $\spec\,U=V_+$ then  $e^{i\ka (H^2-P^2)}$ is not a constant multiple of identity on $\hil^{\tout}$ i.e.  the deformed theory is interacting.  \qed\\

We have shown in Proposition~\ref{asymptotic-BT} that any Borchers triple $(\mcR,U,\Om)$ with a unique vacuum vector $\Om$ and non-trivial single-particle subspaces $\hil_+\cap [c\Om]^{\bot}$,
$\hil_-\cap [c\Om]^{\bot}$, gives
rise to an asymptotic Borchers triple $(\mcR^{\tas}, U^{\tas}, \Om^{\tas})$ which is asymptotically complete, non-interacting and s.t. $\spec\, U^{\tas}=V_+$. Hence, in view of the above corollary, the deformation of $(\mcR^{\tas}, U^{\tas}, \Om^{\tas})$ gives rise to an interacting, asymptotically complete theory.

 Interestingly, there exists a large class of Borchers triples which are unitarily equivalent to their asymptotic Borchers triples (in the sense of \cite{BLS10}). They give rise to interacting theories with a complete particle interpretation by a direct application of the deformation procedure. In the next section we show that the Borchers triples associated with  chiral conformal field theories belong to this class.

\section{Asymptotic completeness of chiral nets }\label{chiral}

In this section we consider a specific class of Borchers triples resulting from chiral nets.
We will show that such  triples are asymptotically complete, what is at first sight
surprising in view of the rich family of superselection sectors in chiral conformal field theory \cite{GF}.
We recall, however, that in the present case particles (or rather 'waves') are composite objects, i.e. they
may transform reducibly under the action of the Poincar\'e group.
Consequently, they may contain (pairs of) excitations from other sectors.

We start from the definition of a local net on $\real$, denoted by $(\ha\A, \ha U, \ha \Om)$.
It consists  of
\begin{itemize}
\item[(a)] a map $\real\supset \mcI\to\ha\A(\mcI)\subset B(\ha\hil)$, from open, bounded intervals
to von~Neumann algebras on  $\ha\hil$ s.t.
\beqa
& &\ha\A(\mcI)\subset \ha\A(\mcJ) \textrm{ for  } \mcI\subset \mcJ, \label{locality-condition} \\
& &[ \ha\A(\mcI),\ha\A(\mcJ)]=0 \textrm{ for } \mcI\cap \mcJ=\phi;
\eeqa

\item[(b)] a unitary representation $\real\ni s\to \ha U(s)$ s.t.
\beqa
& &\te{sp\,} \ha U\subset \real_+,\\
& &\ha U(s)\ha\A(\mcI) \ha U(s)^{-1}= \ha\A(\mcI+s)\, \textrm{ for } s\in \real;
\eeqa
\item[(c)] a unique (up to a phase)  unit vector $\ha\Om$, invariant under the action of $\ha U$, which is
cyclic  for any local algebra $\ha\A(\mcI)$.

\end{itemize}

We remark, that there are many examples of local  nets on $\RR$. They arise, in particular, from conformal field theories on $S^1$
(see e.g. \cite{BMT, KL} for concrete examples). Given a theory on $S^1$ one obtains a net on the compactified real line by means of the  Cayley transform. Its restriction to the real line gives rise to a local net on $\RR$ with properties specified above.

Let $(\ha\A_1, \ha U_1, \ha\Om_1)$ and $(\ha\A_2,\ha U_2,\ha\Om_2)$ be two local nets on $\RR$,  and let $\ha\hil_1$, $\ha\hil_2$ be the respective Hilbert spaces.
We identify the two real lines with the lightlines $x+t=0$ and $x-t=0$
in $\RR^2$. To construct a local net  on $\RR^2$, acting on
the tensor product space $\H = \ha\H_1\otimes \ha\H_2$, we first specify the unitary representation of translations:
\beq
{U}(x):=\ha U_1\left(\frac{1}{\sqrt{2}}(x^0-x^1)\right)\otimes \ha U_2\left(\frac{1}{\sqrt{2}}(x^0+x^1)\right).
\label{unitary-representation}
\eeq
Let $\al_{x}(\,\cdot\,):=U(x)\,\,\cdot\,\, U(x)^*$ be the corresponding group of translation
automorphisms and let $\al^{(1/2)}_{x}(\,\cdot\, ):=\ha U_{1/2}(x)\,\,\cdot\,\,\ha U_{1/2}(x)^*$.  Then there holds
\beq
\alpha_{x}(A_1\otimes A_2) = \alpha^{(1)}_{\frac{1}{\sqrt{2}}(x^0-x^1)}(A_1)
\otimes \alpha^{(2)}_{\frac{1}{\sqrt{2}}(x^0+x^1)}(A_2), \quad A_1\in\ha\A_1,\, A_2\in\ha\A_2. \label{automorphisms}
\eeq
Any double cone in $\RR^2$ can be written as a product of two intervals on lightlines
$\mcI_1\times \mcI_2$. We define the corresponding local algebra  by $\B( \mcI_1\times \mcI_2) := \ha\A_1(\mcI_1)\otimes\ha\A_2(\mcI_2)$.
Setting $\Om=\hat\Om_1\otimes \hat\Om_2$, we obtain a triple $(\B, U,\Om)$, which we call a chiral net on $\RR^2$.  Defining
\beq
\mcR:=\bigvee_{ \mcI_1\times \mcI_2\subset \mcW}\B( \mcI_1\times \mcI_2), \label{mcR-def}
\eeq
we arrive at a Borchers triple $(\mcR,U,\Om)$ associated with $(\B, U,\Om)$.

We will show that this Borchers triple is unitarily equivalent to its asymptotic Borchers triple $(\mcR^{\tas},U^{\tas},\Om^{\tas})$ and therefore, by Proposition~\ref{asymptotic-BT}, asymptotically complete and non-interacting. To this end, we determine the asymptotic fields in the following proposition:

\bep\label{chiral-asymptotics} For any $A_1\in \ha\A_1(\mcI_1)$, $A_2\in\ha\A_2(\mcI_2)$ there holds
\beqa
\Phi_+^{\tout/\tin}(A_1\otimes A_2)&=&A_1\otimes (\ha\Om_2|A_2\ha\Om_2)I,\\
\Phi_-^{\tout/\tin}(A_1\otimes A_2)&=&(\ha\Om_1|A_1\ha\Om_1)I\otimes A_2.
\eeqa
(In the case of $\Phi_+^{\tout}$ and $\Phi_-^{\tin}$ it is assumed that $\mcI_1\times\mcI_2\subset\mcW$.
In the remaining cases $\mcI_1\times\mcI_2\subset\mcW'$).
\eep

\proof We consider only $\Phi_+^{\tout}$, as the remaining cases are analogous. From its definition and formula~(\ref{automorphisms}),  we obtain
\beq
\Phi_+^{\tout}(A_1\otimes A_2)=\underset{T\to\infty}{\slim}\textrm{ }A_1\otimes \int dt\, h_T(t)\al_{\sqrt{2}t}^{(2)}(A_2).
\eeq
We denote $A_2(h_T):=\int dt\, h_T(t)\al_{\sqrt{2}t}^{(2)}(A_2)$. This sequence has the following properties:
\beqa
\underset{T\to\infty}{\slim}\textrm{ }A_2(h_T)\ha\Om_2&=&(\ha\Om_2|A_2\ha\Om_2)\ha\Om_2, \label{auxiliary-one}\\
\lim_{T\to\infty}\|[A_2(h_T), A]\|&=&0, \textrm{ for any } A\in\ha\A_2(\mcI), \label{auxiliary-two}
\eeqa
where $\mcI$ is an arbitrary open, bounded interval.
The first identity above follows from the mean ergodic theorem and the fact that $\ha\Om_2$ is the only vector invariant under the action of $\ha U_2$. The second equality is a consequence of the locality property~(\ref{locality-condition}). Now since $[\ha\A_2(\mcI)\ha\Om_2]=\ha\hil_2$,
we obtain from relations~(\ref{auxiliary-one}), (\ref{auxiliary-two})
\beq
\underset{T\to\infty}{\slim}\textrm{ }A_2(h_T)=(\ha\Om_2|A_2\ha\Om_2)I.
\eeq
This completes the proof. \qed\\

Now we can easily prove the main result of this section:

\bet Any Borchers triple $(\mcR,U,\Om)$ associated with a chiral net on $\RR^2$
is unitarily equivalent to its asymptotic Borchers triple $(\mcR^{\tas},U^{\tas},\Om^{\tas})$.
More precisely, there exists a unitary map $W:\hil^{\tas}\to \hil$ s.t. $W \mcR^{\tas}=\mcR W$,
$WU^{\tas}(x)=U(x)W$ and $W\Om^{\tas}=\Om$.
\eet

\proof  By cyclicity of  $\Om$ under the action of $\mcR$ and the mean ergodic
theorem (cf. formula~(\ref{ergodic})), there holds
\beq
\hil_{\pm}=[\,\Phi_{\pm}^{\tout}(F)\Om\,|\, F\in \mcR\,].
\eeq
Thus, applying  Proposition~\ref{chiral-asymptotics}, and exploiting the cyclicity of $\ha\Om_{1}$, $\ha\Om_2$ under
the action of the respective local algebras, we obtain
\beqa
& &\hil_+=\ha\hil_1\otimes [c\ha\Om_2], \\
& &\hil_-=[c\ha\Om_1]\otimes \ha\hil_2.
\eeqa
Recalling that $\hil^{\tas}=\hil_+\otimes\hil_-$ and $\hil=\ha\hil_1\otimes\ha\hil_2$,
 we define a unitary map $W: \hil^{\tas}\to \hil$, extending by linearity the relation
\beqa
W((\Psi_1\otimes\ha\Om_2)\otimes (\ha\Om_1\otimes\Psi_2))=\Psi_1\otimes\Psi_2, \quad \Psi_1\in\ha\hil_1, \Psi_2\in\ha\hil_2.
\eeqa
It is readily verified  that
\beqa
& &WU^{\tas}(x)=U(x)W, \\
& &W\Om^{\tas}=\Om,\\
& &W\{\Phi_+^{\tout}(A_1\otimes A_2)|_{\hil_+}\otimes\Phi_-^{\tin}(B_1\otimes B_2)|_{\hil_-}\}\non\\
& &\ph{4444444444444444}=     (\ha\Om_1|B_1\ha\Om_1) (\ha\Om_2|A_2\ha\Om_2) \{A_1\otimes B_2\}W,    \label{W}
\eeqa
where  $A_1\otimes A_2$, $B_1\otimes B_2$ comply with the assumptions of
Proposition~\ref{chiral-asymptotics}.   By definition~(\ref{mcR-def}), the
elements in the curly bracket on the r.h.s. of (\ref{W}) generate $\mcR$.
Making use of this fact and of the identities
 $\Phi_{+}^{\tout}(F)|_{\hil_{+}}=P_{+}F|_{\hil_{+}}$,
 $\Phi_{-}^{\tin}(F)|_{\hil_{-}}=P_{-}F|_{\hil_{-}}$, where  $F\in\mcR$,
we obtain that the double commutant of the set of elements in the curly bracket
on the l.h.s. of  (\ref{W}) coincides with $\mcR^{\tas}$. Hence  $W\mcR^{\tas} =\mcR W$, which concludes the proof. \qed\\

In view of the above theorem, we obtain from Proposition~\ref{asymptotic-BT}:

\bec Any Borchers triple $(\mcR, U,\Om)$, associated with a chiral net, gives rise to an asymptotically complete, non-interacting theory.  Moreover, $\spec\, U=V_+$.
\eec

Hence, by Corollary~\ref{corollary}, deformations of such Borchers triples give rise to asymptotically complete, interacting theories.

\section{Concluding remarks}\label{conclusions}

In this paper we applied the deformation method, developed in \cite{BLS10},
to two-dimensional  massless theories. We have shown that the deformation procedure
not only introduces interaction, as expected from the massive case \cite{GL08, BS08},
 but also preserves the property of asymptotic completeness. By deforming chiral conformal field theories,
 we obtained a  large class of wedge-local theories, which are interacting and asymptotically complete.
As the resulting scattering matrices  are Lorentz invariant, one can hope for the
existence of local observables in these models. We recall that  negative results, concerning this issue, have so far been  established only in spacetimes of  dimension larger than two \cite{BLS10}.

A large part of our investigation was devoted to scattering of massless particles ('waves') in two-dimensional
wedge-local theories.
It turned out that the scattering theory developed in \cite{Bu75} for
local nets of observables generalizes naturally to the wedge-local framework: To construct the two-body scattering matrix, it suffices to know the Borchers triple. It is an interesting open problem, if this fact remains true for scattering of massless particles
in spacetimes of higher dimension. We recall that for local nets of observables  scattering theory of massless excitations
is well understood in the physical spacetime \cite{Bu77}.

\vspace{1cm}

\noindent\bf Acknowledgements. \rm
The authors would like to thank Prof.$\!$ D.$\!$ Buchholz, Dr.$\!$ G.$\!$ Lechner and
D.$\!$ Cadamuro for interesting discussions. Moreover, W.D. gratefully acknowledges
 hospitality of the Erwin Schr\"odinger International Institute for Mathematical Physics in Vienna during the
final stages of this work.


TITLE: Calculate in how many different ways can rotated square
QUESTION [5 upvotes]: We put a square $3 \text{ x } 3$ from $9$ square tiles in two types:  or  which can be freely rotated (we allow also symmetries). Calculate in how many different ways you can do that if we identify such systems that one goes to the other with some rotation or symmetry of big square.

My solution:
I am going to use polya counting theory https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem
$$\begin{array}{|c|c|c|c||c|c|}
\hline
&G \in G &  \text{How many}& \text{Id x }\\ \hline
a) &\text{id} & 1 & x_{1}^{9} \\ \hline
b) &\text{90 degree rotation} & 2 & x_1 \cdot x_4^{2} \\ \hline
c) &\text{180 degree rotation }  &  1 & x_1 \cdot x_2^{4}\\ \hline
d) &\text{ diagonal symmetry}  &  2 & x_{1}^{3} \cdot x_2^{3}\\ \hline
e) &\text{centres symmetry }  &  2 & x_1^3 \cdot x_2^{3}\\ \hline
\end{array}$$
We must include our tiles:
a) Here freely, so we have $6$ types: $6^9$
b)

For each $4$-element cycle we choose whether the first will be:

The rest for him is clearly designated:

 The middle one can't be adjusted to fit all $4$ rotations, so: $0$
c) Middle:  and the rest of the cycles as in b): $2\cdot 6^4$
 d) In the middle in $6$ ways, the rest as in b): $6^3 \cdot 6^3=6^6$
e) $6^6$ as in d)
Solution: $$\frac{1}{8} \cdot (2\cdot 6^6 + 2\cdot 6^6 +2\cdot 6^4+0+6^9)$$
Is my solution correct?

REPLY [1 votes]: Let the small square with 1 shaded triangle be called A and the one with 2 shaded triangles be called B. We shall apply Burnside's Lemma to the group of symmetries of the large square acting on the $6^9$ patterns.
The identity fixes all $6^9$ patterns.
The rotations of 90 and 270 cannot fix the centre square and so fix no patterns.
The rotation of 180 fixes the centre square if and only if it is the square B. We can then have  2 choices for this square. The other 8 squares are in pairs where we have a free choice for one of each pair and therefore the total number of patterns is $2\cdot6^4$.
The two reflections in a diagonal cannot fix a corner square and so fix no patterns.
Finally consider a reflection in a horizontal line. (The result for the reflection in a vertical line will be similar.) The central row of squares must each consist of a square B or a square A in just two of its orientations. The remaining six squares are in pairs where we have a free choice for one of each pair and therefore the total number of patterns is $4^3.6^3$.
The solution is $\frac{1}{8} \cdot (6^9+2\cdot 6^4 + 2\cdot 4^3\cdot6^3)$.


TITLE: Some notation regarding "::"
QUESTION [2 upvotes]: I'm reading through some geometry proofs, and I can see something like
$AB^2:PM\times EB::BC^2\ :CD\times PQ$
So I understand that $A:B$ is equivalent to $\frac{A}{B}$, but what does the $::$ mean?

REPLY [3 votes]: HINT
$$ A:B :: C:D \equiv \implies \dfrac{A}{B} = \dfrac{C}{D} $$
The notation is called proportion.

$A$ is to $B$ as $C$ is to $D$.

REPLY [1 votes]: Assuming it says $CD \times PQ$ instead of $CD \times : PQ$, I believe the above statement is equivalent to
\begin{align*}
\frac{AB^2}{PM \times EB} = \frac{BC^2}{CD \times PQ}
\end{align*}


TITLE: Evaluating an infinite series using contour integral
QUESTION [3 upvotes]: This is a problem from Ph.D qualifying exam of complex analysis.
Determine the value of $\sum_{n=1}^{\infty} \frac{(-1)^n}{n^2}$ by integrating $f(z) = \frac{\pi \csc \pi z }{z^2} $ on an appropriante domain of the complex plane.
My attempt: I already found that for any positive integer $n$, $f$ has a simple pole on $z=n$ and the residue of $f$ on $z=n$ is $\frac{(-1)^n}{n^2}$. Therefore, I think that setting an appropriate contour containing the poles from $z=1$ to $z=n$ and evaluating the contour integral will be helpful. However, I have trouble finding such contour. Does anyone have ideas?
Any advice or hint will be helpful! Thanks!

REPLY [2 votes]: $$\frac{\pi\csc\pi z}{z^2}=\frac\pi{z^2}\frac1{\sin\pi z}=\frac\pi{z^2}\cdot\frac1{\pi z-\frac{\pi^3z^3}6+\ldots}=\frac1{z^3}\cdot\frac1{1-\frac{\pi^2z^2}6+\ldots}=$$
$$=\frac1{z^3}\cdot\frac1{1-\frac{\pi^2z^2}6\left(1-\frac{\pi^2z^2}{20}+\ldots\right)}=$$
$$=\frac1{z^3}\left(1+\frac{\pi^2z^2}6\left(1-\frac{\pi^2z^2}{20}+\ldots\right)+\frac{\pi^4z^4}{36}\left(1-\frac{\pi^2z^2}{20}+\ldots\right)^2+\ldots\right)=$$
$$=\frac1{z^3}\left(1+\frac{\pi^2z^2}6-\left(\frac1{120}+\frac1{36}\right)\pi^3z^4+\ldots\right)$$
and thus the residue of the function at $\;z=0\;$, a pole of degree three, is $\;\frac{\pi^2}6\;$ . For the simple poles at $\;z=n\,,\,\,0\neq n\in\Bbb Z\;$ , you already found the residue: $\;\frac{(-1)^n}{n^2}\;$ .
Let us now try the rectangular contour which is the perimeter of
$$R_m:=\left\{(x,y)\in\Bbb R^2\cong\Bbb C\;|\;x=\pm\left(m+\frac12\right)\,,\,y=\pm m\right\}$$
Please do observe the perimeter $\;\partial R_m=: C_m\;$ does not cross through any of the function's pole and thus the complex integral $\;\oint_{C_m}f(z)dz\;$ is well defined , and:
$$\oint_{C_m}f(z)dz=\sum_{\text{poles within}\,C_m}Res(f)=\frac{\pi^2}6+2\sum_{k=1}^m\frac{(-1)^k}{k^2}$$
( the $\;2\;$ before the series is because of the positive and negative poles, as the residue at $\;n\;$ equals the residue at $\;-n\;$) Now just take the limit when $\;m\to\infty\;$ , taking into account that that the integral equals zero at the limit (This is a delicate point though not particularly difficult to prove. Anyway, it seems to be you don't need this, but you can read from page 9 on in the paper http://www.supermath.info/InfiniteSeriesandtheResidueTheorem.pdf)


TITLE: Sparse subset of $\mathbb{N}$ with a summation property
QUESTION [1 upvotes]: For $A\subseteq \mathbb{N}$ and an integer $k\geq 1$ we set $S_A(k) = \{B\subseteq A: B\text{ is finite and } \sum_{b\in B} b = k\}.$
We say that a set $A\subseteq \mathbb{N}$ is sparse if $$\text{lim inf}_{n\to\infty}\frac{|A\cap\{1,\ldots,n\}|}{n} = 0.$$
Is there a sparse set $A\subseteq \mathbb{N}$ such that for every $n\in\mathbb{N}$ there is an integer $z\in \mathbb{N}$ such that $$|S_A(z)| \geq n?$$

REPLY [2 votes]: Summarizing the commentary of Will Brian and myself, there is a notion of IP set (https://en.m.wikipedia.org/wiki/IP_set) (edit: Will says "has your summation property", which I misinterpreted to mean the following ) which has the property that Dominic points out: for every positive integer $n$ there is a member (in fact an infinite subset of them) $z_n$ of the IP set which is the sum in at least $n$ different ways of the members of the base set $A$ which generates the IP set.
Dominic wants a thin or sparse set $A$ to build an IP set. The Fibonacci sequence F provides an example of a sparse $A$ with Dominic's property, as every sufficiently large member of F itself has multiple representations as sums of Fibonacci numbers.  However F is not an IP set ( as an infinite IP set has a partial closure property: given a in the IP set there are infinitely many b in the IP set with a+b also in the IP set). Will mentions the example of base 10 numbers having only ones or zeros in their decimal expansion as a sparse IP set.
One can make A, S(A), and further iterations of S on A simultaneously sparse with a modification of the following technique: let A have 1, and for each positive integer n, throw in c=100^{100^n} and c-a for all a put in at an earlier stage. Then A and S(A) have small but widely separated dense clumps of integers, and one can arrange further iterates to be sparse.
Gerhard "And That Ends The Commentary" Paseman, 2017.04.24.