Computer Science Mathematics
Computer Science-2021.gz:143286
Computer Science
6f8d03a65a314b9fc66d7c2e704687fd958532a7
On codes decoding a constant fraction of errors on the BSC

Using techniques and results from Kudekar et al. we strengthen the bounds on the weight distribution of linear codes achieving capacity on the BEC, which were shown by the first author. In particular, we show that for any doubly transitive binary linear code $C \subseteq \{0,1\}^n$ of rate $0<R<1$ with weight distribution $\left(a_0,...,a_n\right)$ holds $a_i \le 2^{o(n)} \cdot (1-R)^{-2 \ln 2 \cdot \min\{i, n-i\}}$. For doubly transitive codes with minimal distance at least $\Omega\left(n^c\right)$, $0<c \le 1$, the error factor of $2^{o(n)}$ in this bound can be removed at the cost of replacing $1-R$ with a smaller constant $a = a(R,c)<1- R$. Moreover, in the special case of Reed-Muller codes, due to the additional symmetries of these codes, this error factor can be removed at essentially no cost. This implies that for any doubly transitive code $C$ of rate $R$ with minimal distance at least $\Omega\left(n^c\right)$, there exists a positive constant $p = p(R,c)$ such that $C$ decodes errors on $\mathrm{BSC}(p)$ with high probability if $p<p(R,c)$. For doubly transitive codes of a sufficiently low rate (smaller than some absolute constant) the requirement on the minimal distance can be omitted, and hence this critical probability $p(R)$ depends only on $R$. Furthermore, $p(R) \rightarrow \frac12$ as $R \rightarrow 0$. In particular, a Reed-Muller code $C$ of rate $R$ decodes errors on $\mathrm{BSC}(p)$ with high probability if \[ R ~<~ 1 - \big(4p(1-p)\big)^{\frac{1}{4 \ln 2}}, \] answering a question of Abbe, Hazla, and Nachum.


Introduction
The paper [10] gave bounds on the weight distribution of linear codes achieving capacity on the binary erasure channel (BEC). In particular it was shown ( [10], Proposition 1.6) that a binary linear code C of rate R with weight distribution (a 0 , ..., a n ) achieving capacity on the BEC under block-MAP decoding holds The results of [8] imply that these bounds hold, in particular, for binary Reed-Muller codes.
In this paper we strengthen the bounds above in two ways. We note that this improvement comes from taking a closer look at the results and the methods of [8].
First, we show the bounds in [10] to hold for codes achieving capacity on the BEC under bit-MAP decoding. The results of [8] then imply that these bounds hold for any doubly transitive binary linear code.

Proposition 1.1:
Let C be a doubly transitive binary linear code of rate R. Let (a 0 , ..., a n ) be the weight distribution of C. For 0 ≤ i ≤ n, let i * = min{i, n − i}. Let θ = R 2 ln 2 .
• For all 0 ≤ i ≤ n holds In particular, the second of these bounds implies that the weight distribution of a doubly transitive binary linear code of rate R is essentially upper-bounded by that of a random code of the same rate in the band of weights of width R 2 ln 2 around n 2 . (Cf. [7], where similar behavior was inferred for codes with large dual distance.) Next, we observe that these bounds can be made more precise 1 for codes whose minimal distance is somewhat large, depending on the rate of the code. We focus on the first bound, since it seems to be more relevant for the performance of a code on the BSC.

Proposition 1.3:
We use the notation from Proposition 1.1.
• Let C be a binary Reed-Muller code of positive rate 0 < R < 1. There exists R * such that |R * − R| ≤ o n (1) and such that for all 0 ≤ i ≤ n holds • Let 0 < R < 1 and let 0 < c ≤ 1 be constants. Let C be a doubly transitive binary linear code of rate R and minimal distance Ω (n c ). Then there exists a constant a = a(R, c) < 1 − R, such that for all 0 ≤ i ≤ n holds • Moreover, there exists an absolute constant R 0 > 0 so that if R ≤ R 0 and if C is a doubly transitive binary linear code of rate R, there exists a constant a = a(R) ≥ 1 − R Ω(1) , such that the inequality above holds for all 0 ≤ i ≤ n.

Corollary 1.4:
• Let C be a binary Reed-Muller code of positive rate 0 < R < 1. Then C decodes errors on BSC(p) with high probability (more precisely, a family of such codes {C n } n with lim sup n R (C n ) ≤ R, attains vanishing error probability on BSC(p) as n → ∞) if • Let 0 < R < 1 and let 0 < c ≤ 1 be constants. Let C be a doubly transitive binary linear code of rate R and minimal distance Ω (n c ). Then C decodes errors on BSC(p) with high probability if where a = a(R, c) is the constant from the second claim of Proposition 1.3.
• Let R 0 be the constant from the second claim of Proposition 1.3. Let R ≤ R 0 and let C be a doubly transitive binary linear code of rate R. Then C decodes errors on BSC(p) with high probability if where a = a(R) ≥ 1 − R Ω(1) is the constant from the third claim of Proposition 1.3. In particular, p → 1 2 as R → 0.
The first claim of this corollary answers a question from [1] (see also the discussion there). The third claim of the corollary says that any doubly transitive binary linear code of a sufficiently small rate performs well on the BSC.
A well-known conjecture in information theory states that Reed-Muller codes achieve capacity on the BSC. This conjecture would be true if the RHS of the inequality in the first claim of this corollary would be replaced  We refer freely to the notation in [8] and in [10]. Let C be a linear code of rate R. Let r(·) = r C (·) denote the rank function of the binary matroid defined by C. That is, r C (T ) is the rank of the column submatrix of a generating matrix of C which contains columns indexed by T .
The proof of the proposition is based on the following observation.

Proof:
By the Margulis-Russo formula, we have that . Note also that given that R = S \ i is the set of the coordinates which are not erased by the channel, we can recover the i-th bit iff r(S) = r(S \ i). Hence, denoting by P b,i (p) the erasure probability for bit i in C on BEC(p) (as in [8]) with noise p = 1 − λ, we have that Recall that (see [8]) we have ph i (p) = P b,i (p). Hence, Theorem 12 in [8] states that a doubly transitive code C achieves capacity on the BEC under bit-MAP decoding. This is observed to be equivalent to the fact that, assuming the rate of C is R, the average EXIT function h has a sharp threshold at 1 − R. This means that for We can now conclude the proof of Proposition 1.1. Since µ C (λ) = λn − E S∼λ r C (S), and since µ C (R) = o(n), Proposition 1.3 and Lemma 1.4 in [10] imply the second claim of the proposition precisely in the way they imply the claim of Proposition 1.6 in [10]. Next, observe that if C is doubly transitive, then so is C ⊥ . Hence the argument above applies to C ⊥ , and we have that µ C ⊥ (1 − R) = o(n). We now proceed in the same way to derive the first claim of the proposition.

Proof of Proposition 1.3
We start with the first claim of the proposition. Let C be a Reed-Muller code of rate 0 < R < 1. By [2], see also the proof of Theorem 17 in [8], we have that for the average EXIT function h of a Reed-Muller code holds, for some absolute constant c and for any p bounded away from 0 and 1 that dh dp ≥ c log(n) log log(n) · h(1 − h).
Let u(λ) = 1 − h(1 − λ), and let K be a shorthand for c log(n) log log(n). Then, since h is increasing, so is u, and we have u ′ ≥ Ku(1 − u). Recall that Reed-Muller codes are 2-transitive.
Since u is continuous in λ we have, by the sharp threshold of u at R, that for some R * with |R * − R| ≤ o n (1) holds u (R * ) = 1/2, which also implies that 0 ≤ u(λ) ≤ 1/2 for 0 ≤ λ ≤ R * . Hence in the interval [0, Hence, by Gronwalls's inequality [6], we have that for t > 0 holds Since u is increasing, this implies that We can now conclude the proof. Let C be a Reed-Muller code of rate R. Then C ⊥ is a Reed-Muller code of rate 1 − R, and hence by the preceding argument applied to C ⊥ , we have that Let (a 0 , ..., a n ) be the distance distribution of C. Recalling that he minimal distance of C is Ω ( √ n), and applying Proposition 1.3 and Lemma 1.4 in [10], we have that for any 0 ≤ i ≤ n holds We pass to the second claim of the proposition. We proceed as above, using the same notation. Let C be a doubly transitive code of rate 0 < R < 1 and let 0 < c ≤ 1 be a given constant. By [5,9], see also Section 3.1 in [8], we have that . By Gronwall's inequality, this means that u R 2 ≤ n −t , for some absolute constant t = t(R) > 0.
Similarly to [8], we now use the fact that h(p) is a measure w.r.t. the product measure µ p of an increasing set Ω in {0, 1} n−1 . Equivalently, u(λ) is the measure w.r.t. the product measure µ λ of an increasing set Ω * in {0, 1} n−1 , where Ω * = x ∈ {0, 1} n−1 , x ⊕ 1 ∈ Ω c (here Ω c is the complement of Ω). We can now apply e.g., Lemma 2.7 in [4], to obtain that for any b > 1 holds This means that if b > 1−c t , for any λ ≤ R 2 b holds u(λ) ≤ o n c−1 , which means that We can now conclude the proof of the second claim of the proposition, similarly to the above, by applying the preceding argument to C ⊥ , and by using the fact that the minimal distance of We pass to the third claim of the proposition. Let R 0 be a sufficiently small constant, and let R ≤ R 0 . We proceed as in the discussion above, using the same notation, but work directly with C ⊥ . The function u = u C ⊥ has a sharp threshold at 1 − R, implying in particular Next we choose (with forethought) R 1 = (R * ) e −8 , and consider the function u on the interval Choosing R to be sufficiently small, we can ensure that R 1 is small enough to guarantee that for λ ∈ I holds u ′ ≥ 1 Then f (0) = 1 2 and for t ∈ [0,

t). Hence, by
Gronwalls's inequality, we have This means that u (R 1 ) ≤ 1 2 n −2 , and since u is increasing, we have u(λ) ≤ 1 2 n −2 for all λ ≤ R 1 . We can now conclude the proof of the third claim of the proposition, similarly to the above.

Proof of Corollary 1.4
Both claims of the corollary follow immediately from Proposition 1.3 and from the following technical lemma. (This lemma is probably well-known, so we relegate its proof to the Appendix.) Lemma 2.2: Let C be a linear code with weight distribution (a 0 , ..., a n ) and assume that a i ≤ c i for some constant c > 1. Assume also that the minimal distance of C is at least ω (log(n)). Then for error p such that 4p(1 − p) < 1 c 2 , C corrects errors in BSC(p) with high probability.

Proof of Lemma 2.2
The probability of error using C in BSC(p) is the same as the probability that a non-zero word in C would be at least as close as zero to the noise vector (assuming w.l.o.g. that zero was transmitted). Let z denote the noise vector. It is closer to x ∈ C it than to zero iff it chooses at least |x|/2 coordinates in the support of x. By Sanov's theorem ( [3]) the probability of this happening is (writing Y for a binomial random variable Y ∼ Bin(|x|, p), and D 1 2 ||p for the Kullback-Leibler divergence between 1 2 , 1 2 and (p, 1 − p)): Pr Y ≥ |x| 2 ≤ (|x| + 1) 2 · 2 −|x|D( 1 2 ||p) = (|x| + 1) 2 · (4p(1 − p)) |x| 2 .
Let P be the probability of error. Denoting by d the minimal distance of C, and using the assumptions of the lemma, we have, via the union bound, that