Line Decoding
Definition 1. (Linear Code) Given an \mathbb{F}-vector space K, a \lbrack K,n,k\rbrack-linear code is a subspace C \subseteq K^{n} of dimension k. Define the Hamming weight \begin{aligned} \operatorname{w}:K^{n} & \rightarrow {\mathbb{N}} \end{aligned}
\operatorname{w}({\mathbf{u}}) = |\left\{ i \in \lbrack n\rbrack:{\mathbf{u}}_{i} \neq 0_{K} \right\}|
and distance \operatorname{d}({\mathbf{u}},{\mathbf{v}}) = \operatorname{w}({\mathbf{u}} - {\mathbf{v}}), then the minimum distance d of C is
d = \min\limits_{\substack{ {\mathbf{u}},{\mathbf{v}} \in C \\ {\mathbf{u}} \neq {\mathbf{v}} }}\operatorname{d}({\mathbf{u}},{\mathbf{v}}).
Define the decoding list and list bound at decoding radius e as
\begin{aligned} \operatorname{L}(e,{\mathbf{u}}) & = \left\{ {\mathbf{c}} \in C:\operatorname{d}({\mathbf{c}},{\mathbf{u}}) \leq e \right\} \\ \operatorname{L}(e) & = \max\limits_{{\mathbf{u}} \in K^{n}}|\operatorname{L}(e,{\mathbf{u}})|. \end{aligned}
Note that if C is a code then the direct product C^{2} = C \times C is to, we call this the pair code of C.
Any sufficiently frequent pattern of nearby codewords must contain a large subset lying on one affine code line.
Definition 2. (Line Decodability) C is (e, a, b) line-decodable iff, for every {\mathbf{u}}_{0},{\mathbf{u}}_{1} \in K^{n} and every map {\mathbf{c}}:{\mathbb{F}} \rightarrow C,
|\left\{ \alpha \in {\mathbb{F}}:{\mathbf{c}}(\alpha) \in \operatorname{L}(e,{\mathbf{u}}_{0} + \alpha{\mathbf{u}}_{1}) \right\}| \geq a
implies that there exist {\mathbf{c}}_{0},{\mathbf{c}}_{1} \in C such that
|\left\{ \alpha \in {\mathbb{F}}:{\mathbf{c}}(\alpha) \in \operatorname{L}(e,{\mathbf{u}}_{0} + \alpha{\mathbf{u}}_{1}) \land {\mathbf{c}}(\alpha) = {\mathbf{c}}_{0} + \alpha{\mathbf{c}}_{1} \right\}| \geq b.
This directly gives a mutual correlation error bound
\begin{aligned} \varepsilon_{\text{MCA}}\left( C,\frac{e}{n} \right) & \leq \frac{a}{|{\mathbb{F}}|} & \text{for }b & \geq n + 1. \end{aligned}
Definition 3. (m-List Linearity Error) Let m \geq 1, let C \subseteq {\mathbb{F}}^{n} be a linear code, and let its tuple code be C^{m} \subseteq \left( {\mathbb{F}}^{m} \right)^{n} equipped with Hamming weight on the alphabet {\mathbb{F}}^{m}.
For {\mathbf{u}} \in \left( {\mathbb{F}}^{m} \right)^{n} define the m-list linearity error (LLE) set and bound as
\begin{aligned} \operatorname{LLE}_{m}(e,{\mathbf{u}}) & = \left\{ \lbrack{\mathbf{α}}\rbrack \in {\mathbb{P}}^{m - 1}({\mathbb{F}}):{\mathbf{α}}^{\top}\operatorname{L}_{C^{m}}(e,{\mathbf{u}}) \neq \operatorname{L}_{C}\left( e,{\mathbf{α}}^{\top}{\mathbf{u}} \right) \right\}, \\ \operatorname{LLE}_{m}(e) & = \max\limits_{\mathbf{u}}|\operatorname{LLE}_{m}(e,{\mathbf{u}})|. \end{aligned}
Here {\mathbf{α}}^{\top} acts coordinatewise on \left( {\mathbb{F}}^{m} \right)^{n} and pointwise on sets. Repesentative independence follows from linearity of C and invariance of Hamming distance under nonzero scaling.
Theorem 4. (\operatorname{LLE}_{2} to line decoding) Let C \subseteq {\mathbb{F}}^{n} be a linear code, then for every decoding radius e,
\begin{aligned} B & \geq \operatorname{LLE}_{2}(e) & L & \geq \operatorname{L}(C^{2},e), & b & \geq 1 \end{aligned}
the code C is \left( e,B + (b - 1)L + 1,b \right) line decodable.
Proof. Fix a received pair {\mathbf{u}} \in \left( {\mathbb{F}}^{2} \right)^{n} and a map c:{\mathbb{F}} \rightarrow C selecting one codeword for every challenge. Let
S ≔ \left\{ z \in {\mathbb{F}}:c(z) \in \operatorname{L}_{C}\left( e,(1,z)^{\top}{\mathbf{u}} \right) \right\}
and suppose
|S| \geq B + (b - 1)L + 1.
Define the exceptional challenges
E ≔ \left\{ z \in {\mathbb{F}}:\left\lbrack (1,z) \right\rbrack \in \operatorname{LLE}_{2}(e,{\mathbf{u}}) \right\}.
Since the map z \mapsto \left\lbrack (1,z) \right\rbrack is injective,
|E| \leq \left| {\operatorname{LLE}_{2}(e,{\mathbf{u}})} \right| \leq \operatorname{LLE}_{2}(e) \leq B.
Therefore
\left| {S \smallsetminus E} \right| \geq (b - 1)L + 1.
For every z \in S \smallsetminus E, the direction \left\lbrack (1,z) \right\rbrack is not a list-linearity error. Hence
(1,z)^{\top}\operatorname{L}_{C^{2}}(e,{\mathbf{u}}) = \operatorname{L}_{C}\left( e,(1,z)^{\top}{\mathbf{u}} \right).
Since c(z) belongs to the list on the right, there exists p_{z} \in \operatorname{L}_{C^{2}}(e,{\mathbf{u}}) such that (1,z)^{\top}p_{z} = c(z).
The pair list has size at most L. Thus at least (b - 1)L + 1 challenges are assigned to at most L pair-codewords. By the pigeonhole principle, there exists
p = \left( p_{0},p_{1} \right) \in \operatorname{L}_{C^{2}}\left( e,\mathbf{u} \right)
such that
c(z) = (1,z)^{\top}p = p_{0} + zp_{1}
for at least b values z \in S \smallsetminus E.
Since p \in C^{2}, both p_{0} and p_{1} belong to C. All these challenges also belong to S, so the corresponding selected codewords are close to the received line.
Therefore C is \left( e,B + (b - 1)L + 1,b \right) line decodable.
As a corrolary, for a \lbrack{\mathbb{F}},n,k\rbrack-linear code C we have
\varepsilon_{\text{MCA }}(C,e) \leq \frac{\operatorname{LLE}_{C,2}(e) + n\operatorname{L}_{C^{2}}(e) + 1}{|{\mathbb{F}}|}.
