*[Lecture scribed by Srivatsan Narayanan]*

**1. Fourier analytic proof of the first MRRW bound **

We develop a proof of the first MRRW (JPL) bound for binary *linear* codes based on a covering argument. Our main theorem (Theorem 1) states that the dual code has a small essential covering radius. From this, we conclude that the size of the dual code is large, and equivalently, the size of the code is small.

Theorem 1 (Dual codes have a small ”essential covering radius”)Let be a binary linear code of distance at least . Then,

Remark 1We say that a set has a covering radius at most if every point in is inside for some . Theorem 1 asserts that the dual code satisfies a relaxed version of the property: for large enough , at least a fraction of the points are inside for some . This is sufficient for establishing an asymptotic bound on the rate of the codes, as shown in Corollary 2.

Before we prove Theorem 1, we observe that it directly implies an asymptotic upper bound on the rate of codes.

Corollary 2Let be a binary linear code with distance at least . Then,

*Proof:* The covering condition (Equation 1) gives us that:

since the volume of each ball is exactly . But, the sizes of and are related as follows (see Exercise 1): . Combining the two observations, we directly obtain a bound on the code size:

To obtain the bound on the rate, we need to translate the above bounds to asymptotic notation. Writing ,

so that,

Taking logarithms, and noting that gives the claimed bound.

**Hint:** What is the relation between the dimensions of a code and its dual? How many points lie on a subspace of dimension ?

We now need to establish Theorem 1. But, at first we introduce some notation. Let denote the adjacency matrix of the boolean hypercube; that is, for , if and only if and differ in exactly one coordinate. We now extend the concept of maximum eigenvalue to a set .

Definition 3For , define its maximum eigenvalue to be

Proposition 4The maximum eigenvalue of the whole hypercube is .

In order to establish Theorem 1, we observe that ; that is, is really a translate of by . Now, we break the proof down into two parts. First, we show that for *any* with sufficiently large maximum eigenvalue, covers a significant (*i.e.,* ) fraction of the whole space. We then show that achieves the required maximum eigenvalue, even when is not too large.

Theorem 5Let be a binary linear code with block length and distance . Suppose has maximum eigenvalue . Then,

Theorem 6 (Hamming balls have a large maximum eigenvalue)

Now, our main theorem follows as a corollary of Theorems 5 and 6.

*Proof:* (**For Theorem 1**) We just need to pick an large enough such that

This is satisfied provided:

Neglecting terms, we get:

which is true for:

Remark 2We cannot hope to improve the above bound simply by employing a “better” choice for . Hamming balls are so-called “Faber-Krahn” minimizers for the Hamming cube. That is, of all sets with a given volume, Hamming balls have almost optimum value of the maximum eigenvalue: if , then .

**2. Proof of Theorem 5 **

We recall the following facts on Fourier transforms from the first installment of these notes. For ,

The Parseval identity says that for ,

Also, we have a natural correspondence between the Fourier transform of a code and its dual:

The following lemma is a direct consequence of Equation 2.

Lemma 7Let be a binary linear code with distance at least . Suppose that such that and . Then,

We are now equipped to prove the required claim. Let be a function with , such that

(In other words, is a function that maximizes .) Since the set is understood from the context, for notational ease, we simply set and .

The following exercises make many simplifying observations.

Exercise 3Prove the following statements.

Hint for part (3): For , equality holds. On the other hand, for , , and hence the inequality is trivially satisfied. (Note that all the terms in the left hand side are nonnegative.)

For , define by . Finally, define by:

Again, for convenience, we set to be . Note that . We will sketch the high-level idea of the proof. In order to lower bound the , we show that the must have a large support. We establish this by showing that is comparable to .

For this we will focus on the quantity and establish lower and upper bounds on it.

Before proving the above lemmata, we will show how to obtain Theorem 5 using them.

Corollary 10 ( has a large support)

*Proof:* The lower and upper bounds (Lemmata 8 and 9) together imply

On the other hand, note that is supported on . Therefore,

using the Cauchy-Schwartz inequality.

Finally, Equations (3) and (4) together give the required bound:

For (as assumed in Theorem 5), this bound simplifies to

** 2.1. Lower bound on **

In this section, we prove Lemma 8. The proof is based on the spectral property of . Fix an . Then,

Therefore,

which gives the claim.

** 2.2. Upper bound on **

In this section, we prove Lemma 9. The proof is based on the properties of the Fourier transform of .

The following simple result is a crucial ingredient in calculating .

Lemma 11For and , define by . Then,

*Proof:* We have

where we make the substitution . Therefore,

Lemma 12 (Fourier transform of )

*Proof:* From Lemma 11, we know that . Therefore,

The full claim follows since .

Remark 3Lemma 12 can be directly obtained as follows. Note that

where represents the ‘convolution’ operation. It is a well known property that the Fourier transform of a convolution is the product of the Fourier transforms. Formally, for , we have . This establishes the claim.

Corollary 13Let be a binary linear code of distance at least . Suppose is such that and . Then, .

*Proof:* Since , it follows that . Therefore, from Lemma 12, .

Lemma 14 (Fourier transform of )For ,

*Proof:* We know that

Therefore,

where . It is easy to check that for , . Plugging this in the previous equation, we get

With these claims in place, we can establish an upper bound on .

using Corollary 13. We now complete the upper bound.

using .

**3. Lower bound on the maximum eigenvalue of Hamming balls **

We are interested in lower bounding the maximum eigenvalue of the Hamming ball , where for . We will restrict ourselves to an , such that depends on *only* on the weight of , and has support , for some . (For instance, we could choose .) Define as follows:

For convenience, we will denote by the evaluation of at any with weight . Let us now compute and respectively.

On the other hand,

Fix an of weight . Therefore, of the neighbors of , have a weight , and the remaining have a weight . Therefore,

Therefore,

For the values of and we are interested in, it is easy to see that

Combining Equations (6) and (5), we get

For , this gives the bound

**4. Some remarks and the second MRRW bound **

Though we proved the bound only for linear codes, the bound holds also for general codes, and in fact can be proved within the same Fourier analytic framework; see the final section of the paper by Navon and Samorodnitsky for the details.

The first MRRW bound can also be generalized to larger alphabets, giving the following statement.

Theorem 15 (First MRRW bound for larger alphabets)The rate of a -ary code of relative distance , , is at most

Below is a plot of the best bounds on the best possible rate as a function of relative distance we have seen so far for binary codes: the Gilbert-Varshamov lower bound , the Elias-Bassalygo bound , and the first MRRW bound .

Note that the first MRRW bound is weaker than the Elias-Bassalygo bound for smaller than about (in fact it is even weaker than the Hamming bound for ). There is a strenghtening of the bound, called the second MRRW bound, which uses the inequality

together with an upper bound on the size of constant-weight codes via Delsarte’s linear programming approach applied to the “Johnson” association scheme. We state the bound here without proof. This bound beats the Elias-Bassalygo bound for the entire range . The bound coincides with the first MRRW bound for . The second MRRW bound gives the best upper bound on for the entire range of and has not been improved upon in over three decades!

Theorem 16 (Second MRRW bound for binary codes)Let . The largest rate of a binary code of relative distance is at most where

The above bound encompasses the Hamming, Elias-Bassalygo, and first MRRW bounds.

Exercise 4

Verify that the choice in the the minimization in (7) yields the first MRRW bound.Verify that the choice in the minimization in (7) yields the Hamming bound.Verify that picking so that in the minimization in (7) yields the Elias-Bassalygo bound.

As far as I am aware the second MRRW bound only applies for binary codes and has not been extended to larger alphabets.

[…] https://errorcorrectingcodes.wordpress.com/2010/02/09/notes-5-2-proof-of-the-first-mrrw-bound/#more-1… and then “General Report on […]

Pingback by fourier, duals; weights | Peter's ruminations — August 13, 2011 @ 9:06 pm |