Generalized Alon-Boppana Theorems and Error-Correcting Codes

Joel Friedman^{∗}  Jean-Pierre Tillich^{†}

May 27, 2002

Abstract

In this paper we describe several theorems that give lower bounds on the second eigenvalue of any quotient of a given size of a fixed graph, G. These theorems generalize Alon-Boppana type theorems, where G is a regular (infinite) tree.

When G is a hypercube, our theorems give minimum distance upper bounds on linear binary codes of a given size and information rate. Our bounds at best equal the current best bounds for codes, and only apply to linear codes. However, it is of interest to note that

(1) one very simple Alon-Boppana argument yields non-trivial code bound, and (2) our Alon-Boppana argument that equals a current best bound for codes has some hope of improvement.

We also improve the bound in sharpest known Alon-Boppana theorem (i.e., when G is a regular tree).

1 Introduction

The goal of this paper is to draw a connection between the “Alon-Boppana” bound, in the theory of expanders or graph eigenvalues, and asymptotic upper bounds for the minimum distance of an error-correcting code of a given rate.

∗Departments of Computer Science and Mathematics, University of British Columbia, Vancouver, BC V6T 1Z4 (V6T 1Z2 for Mathematics), CANADA. jf@cs.ubc.ca. Research supported in part by an NSERC grant.

†Inria Projet Codes, Domaine de Voluceau BP.105, 78153 FRANCE.

jean-pierre.tillich@inria.fr Research supported in part by France Telecom.

Recall that the Alon-Boppana bound is a lower bound on the second eigenvalue of finite d-regular graphs. In its basic form it says that the second largest eigenvalue of a d-regular graph is greater than 2\sqrt{d − 1} + o(1) as the number of vertices goes to infinity.

The connection with upper bounds on the minimum distance of a binary linear code is that the minimum distance of a binary linear code C can be expressed as a certain decreasing function of the second largest eigenvalue of a certain regular graph associated to C (this graph is generally called the coset graph of C^{⊥}; see Section 5). In other words any lower bound on the second eigenvalue of this graph translates into an upper bound on the minimum distance of the code. If we use the aforementioned Alon-Boppana directly then we only obtain a very weak upper bound on the minimum distance of the code.

However, when we know more about the geometry of the graph, such as for instance lower bounds on the number of cycles of a given length, then the Alon-Boppana lower bound can be strengthened considerably. We derive several lower bounds by different techniques. The first one is derived through lower bounds on the number of cycles of a given length, the second through comparison with Dirichlet eigenvalues. There is however a common underlying idea, namely the notion of a covering graph (see Section 3). In both cases, the relevant quantities (either the number of cycles or the Dirichlet eigenvalues) are bounded by the corresponding quantities of a cover graph. The crux of this approach is that the cover graph may have a simple structure (for instance, for the coset graph we may choose a Boolean hypercube), which enables us to estimate these quantities directly.

The second technique, when applied to the graph associated to the coset graph of a binary linear code, yields the first MRRW bound [MRRW77] in coding theory, which is the best known upper bound on the minimum distance for low rate codes. This bound was originally obtained with the “linear programming” approach. While our approach has elements in common with the classical “linear programming” approach, we believe our approach is easier to use and suggests more geometrically visualizable questions on the Boolean hypercube. This is because a simple “Alon-Boppana” argument easily gives an interesting coding bound (see Section 5), and we don’t know of an analogous argument based on the linear programming approach. Also, in an attempt to improve the “first MRRW bound” (of [MRRW77], as explained in Section 2) there arises a geometric question about what is the correct analogue for the hypercube of the classical Faber-Krahn inequality for domains in ℝ^{n} (see, e.g., [Fab23, Kra25, Cha84, Fri93]); if this analogue is “asymptotically different” (see Section 9), which is presently conceivable, then the first MRRW bound will be improved. We must admit, however, that at present we cannot improve but only duplicate the first MRRW bound with our methods; furthermore it is quite conceivable that any theorem obtained with our methods could be translated into a proof based only on the linear programming approach (it would be interesting to know if this were really true). But we reiterate that even if our approach is, in a sense, subsumed by the linear programming approach, the setting and geometric pictures suggested by our method seems to be easier to work with. Moreover, we also show how to obtain the linear programming bounds dealing only with the Hamming space through our approach, by changing slightly one of our Alon-Boppana bounds (see Section 9).

The consequences for the Alon-Boppana theorem in this paper is that we improve the best Alon-Boppana bound (of Friedman and Kahale, see [Fri93]) by a factor that depends on the graph’s size. This is done by generalizing the known Alon-Boppana bound techniques to give coding bounds, and realizing that the first MRRW bound improves this bound, in a sense, by a factor of two (somewhere). It is not hard to see where this factor of two can be recovered (see Section 9).

2 A basic fact for obtaining Alon-Boppana bounds

Let us first introduce some general notation concerning eigenvalues of (adjacency matrices of) graphs. Let G be a graph with |V_{G}| = n and adjacency matrix A_{G}. Recall that A_{G} is a n × n symmetric matrix, with entries a_{uv} indexed by the vertices of the graph, and a_{uv} = 1 iff u and v are adjacent in G, and a_{uv} = 0 otherwise. Since A_{G} is symmetric, it can be diagonalised in an orthonormal basis. Then we write

λ_{1}(G) ≥ λ_{2}(G) ≥ ⋯ ≥ λ_{n}(G)

for the eigenvalues of G’s adjacency matrix (written with their multiplicity). We denote by e_{1}, e_{2}, …, e_{n} the corresponding (orthonormal) basis of eigenvectors. We write ρ_{i} = ρ_{i}(G) for the i-th largest value that occurs among the |λ_{i}|; for example, the Perron-Frobenius theorem implies that ρ_{1} = λ_{1} and thus

ρ_{2} = ρ_{2}(G) = max(λ_{2}, −λ_{n}).

Estimating λ_{2} is of interest in studying expansion; however, some techniques only estimate ρ_{2} (and higher ρ_{i}).

Rayleigh principle gives us the following characterization of λ_{2}(G) (it is a straightforward consequence of the fact that e_{1}, e_{2}, …, e_{n} is an orthornormal basis)

λ_{2}(G) = max_{f⊥e_{1}} \frac{(A_{G}f, f)}{(f, f)}  (1)

If G is a regular graph, then e_{1} can be chosen to be \frac{1}{\sqrt{n}}1, where 1 is the all ones vector, and therefore by applying the previous equation we obtain

Fact 2.1 If G is a regular graph, and f ∈ ℝ^{n} is orthogonal to 1 then

λ_{2}(G) ≥ \frac{(A_{G}f, f)}{(f, f)}  (2)

This inequality is the key to obtain lower bounds on λ_{2}(G) : by choosing f appropriately we can relate λ_{2}(G) to other quantities of the graph. Notice that we can also apply the Rayleigh principle to A_{G}^{l} (or even sometimes to a well chosen polynomial applied to A_{G}), this yields for f ⊥ 1 and any positive odd integer l:

λ_{2}(G)^{l} ≥ \frac{(A_{G}^{l}f, f)}{(f, f)}  (3)

and in general for any positive integer l :

ρ_{2}(G)^{l} ≥ \frac{(A_{G}^{l}f, f)}{(f, f)}  (4)

In what follows we are going to apply these simple facts to several different choices of f. For all these choices we are going to control the term \frac{(A_{G}^{l}f,f)}{(f,f)} which appears on the righthand side through the notion of a cover graph.

3 Graphs and Covers

In this section we review the definition of graph covers. Until Section 10 we assume all graphs are simple, i.e. have no multiple edges or self-loops; this simplifies the discussion and notation. In Section 10 we give the definitions needed for general graphs; all theorems immediately carry over to general graphs.

By a simple graph we mean a graph with no multiple edges or self-loops; so we may think of a simple graph, G, as a pair (V_{G}, E_{G}) where E_{G} is a subset of the set of unordered pairs of V_{G}. Until Section 10 we understand a graph to mean a simple graph.

A morphism π: H → G of graphs is a map from V_{H} to V_{G} such that the natural map from E_{H} onto pairs in V_{G} has its image in E_{G}. π thus gives rise to a map from E_{H} to E_{G} which we also denote by π, assuming no confusion will arise.

A morphism π: H → G is called a covering map if for every edge e = {u, v} of G and every u′ ∈ V_{H} with π(u′) = u there is a unique v′ ∈ π^{−1}(v) such that {u′, v′} is an edge in E_{H}. We also say that in this case H is a cover of G.

Example 3.1 Let G be any finite graph. Then G has a universal cover, π: T → G, in that for any covering map ν: K → G there is a covering map^{1} μ: T → K such that π = ν ∘ μ. T is a tree. If G is d-regular, i.e. each row and column of A_{G} sums to d, then T is a d-regular tree (and any two d-regular trees are isomorphic).

Example 3.2 Let G be a connected Cayley graph on (𝔽_{2})^{k} of degree n, with generators c_{1}, …, c_{n}. This is a graph where we connect any x ∈ (𝔽_{2})^{k} to x+c_{i} for i ∈ {1, 2, …, n}. Let 𝔹^{n} be the Boolean n-hypercube, i.e. the Cayley graph on (𝔽_{2})^{n} with generators e_{1}, …, e_{n} where e_{i} is the i-th standard basis vector, i.e., e_{i} is 0 on each coordinate except the i-th, where it is 1. Consider the map π_{lin} : (𝔽_{2})^{n} → (𝔽_{2})^{k} which takes e_{i} (as above) to c_{i} and is extended by linearity. Then π_{lin} induces a covering map π: 𝔹^{n} → G.

4 Coding Theory

A code of length n is a subset C ⊂ (𝔽_{2})^{n}, where 𝔽_{2} = {0, 1} is the field with two elements. C is linear if it is a subspace of the vector space (𝔽_{2})^{n}. We endow (𝔽_{2})^{n} with the Hamming distance, i.e. for x, y ∈ (𝔽_{2})^{n}, d(x, y) is the number of coordinates on which x and y differ. The minimum distance of a code, C, is

1This covering map, μ, is uniquely defined if one works with “base-pointed graphs,”

i.e. graphs with a distiguished vertex.

d_{min}(C) = min{d(x, y) | x, y ∈ C, x ≠ y},

and its normalised minimum distance is

δ(C) = d_{min}(C)/n.

The information rate of a code is

R(C) = \frac{log_{2} |C|}{n}.

If C is a linear code then this is just (dim C)/n.

Let δ_{max} be the function

δ_{max}(R) = \overline{lim}_{n→∞} max\{δ(C) | R(C) ≥ R, C ⊂ (𝔽_{2})^{n}\}

and

R_{max}(δ) = \overline{lim}_{n→∞} max\{R(C) | δ(C) ≥ δ, C ⊂ (𝔽_{2})^{n}\}.

We are interested in estimating these functions.

To estimate δ_{max} is essentially the same as to estimate R_{max}, but a bit of care is required to make this precise.

Proposition 4.1 Let δ_{max}(α) ≤ f(α) for a continuous, strictly decreasing function, f, defined on an open interval. Then (f^{−1} is defined on the image of f and) R_{max}(δ) ≤ f^{−1}(δ).

Proof This is an easy (but mildly annoying) technicality; see appendix B.

□

We now state some classical bounds.

Theorem 4.2 R_{max}(δ) ≥ 1 − h(δ), where

h(θ) = −θ log_{2} θ − (1 − θ) log_{2}(1 − θ).

Proof See the asymptotic Gilbert-Varshamov bound in [vL99].

□

The best upper bound on R_{max} is given by the following

Theorem 4.3

R_{max}(δ) ≤ min_{u∈[0,1−2δ]} b(u, δ),  (5)

where

b(u, δ) = 1 + g(u^{2}) − g(u^{2} + 2δu + 2δ)

with

g(x) = h(\frac{1}{2} − \frac{\sqrt{1 − x}}{2}).

For δ ≥ 0.273 this bound is the same as

R_{max}(δ) ≤ b(1 − 2δ, δ) = h(1/2 − \sqrt{δ(1 − δ)}).  (6)

Proof See [MRRW77] (or [MS77] for the latter half of the theorem).

□

The inequality (5) is known as the “second MRRW” bound; (6) is known as the “first MRRW” bound.

Corollary 4.4 For small α we have

\frac{1}{2} − (1 + o(1))\sqrt{\frac{α}{2 log_{2} e}} ≤ δ_{max}(α) ≤ \frac{1}{2} − (1 + o(1))\sqrt{\frac{α}{log_{2}(1/α)}}.

5 Codes and Eigenvalues

In this section we recall how a graph can be associated to a linear code in such a way that the eigenvalues of the graph are in relationship with the codeword weights.

Let C ⊂ (𝔽_{2})^{n} be a linear code with basis r_{1}, …, r_{k}. We form the generator matrix, M, over 𝔽_{2}, whose rows are the r_{i}’s; so M is an k × n matrix. Its columns, c_{1}, …, c_{n}, can each be viewed as an element of (𝔽_{2})^{k}.

Let G be the Cayley graph on (𝔽_{2})^{k} with generators c_{1}, …, c_{n} ^{2}. Apparently G may depend on the choice of the basis r_{1}, r_{2}, …, r_{k}. It turns out that G only depends on C. This can be seen by bringing in the dual code C^{⊥} of C, that is

2We shall assume (until Section 10) that no c_{i}’s vanish and the c_{i}’s are all distinct; if not, then G will have self-loops and/or multiple edges, and we technically need Section 10 before we can apply our theory.

C^{⊥} = {x ∈ (𝔽_{2})^{n} | x · c = 0 ∀c ∈ C}.

Consider the graph with vertices the cosets x + C^{⊥}, and two cosets being linked by an edge iff they are at Hamming distance 1. We claim that the Cayley graph defined before and this new graph are isomorphic, the isomorphism being given by the map π : x + C^{⊥} → Mx. Indeed, let two cosets x+C^{⊥} and y+C^{⊥} be linked by an edge. This means that there exists c ∈ C^{⊥} and i ∈ {1, …, n} such that x = y + c + e_{i} (where e_{i} is the i-th standard basis vector of 𝔽_{2}^{n}, i.e., e_{i} is 0 on each coordinate except the i-th, where it is 1), this implies that Mx = My + c_{i}. On the other hand if Mx = My + c_{i} then necessarily x and y + e_{i} differ only by an element of C^{⊥}.

We say that this graph is the coset graph of C^{⊥} or of the code^{3}, C. The following is a well-known folk theorem (see [DS91] and the reference there):

Theorem 5.1 Let λ_{1} ≥ λ_{2} ≥ ⋯ be the eigenvalues of the adjacency matrix of the coset graph of C^{⊥} arranged in non-increasing order. Then λ_{1} = n and λ_{2} = n − 2d_{min}(C). Moreover, the weights (i.e. distances to the zero code word) appearing in C are just the (n − λ_{i})/2 as i ranges from 1 to 2^{k}.

6 A Simple Generalized Alon-Boppana Theorem

In this section we give a very simple but rather weak generalized Alon-Boppana theorem and discuss its implications. Let G be a d-regular graph. We use the approach outlined in Section 2 to obtain a lower bound on λ_{2}(G) and ρ_{2}(G) and we choose f = χ_{u} − χ_{v} where χ denotes the characteristic function in (4). Notice that

(A_{G}^{l}χ_{u}, χ_{u}) = N_{l}(u), (A_{G}^{l}χ_{v}, χ_{v}) = N_{l}(v),

where N_{l}(v) denotes the number of walks of length l from v to itself. Moreover if u and v are at distance greater than l ≥ 0, then

(A_{G}^{l}χ_{u}, χ_{v}) = (A_{G}^{l}χ_{v}, χ_{u}) = 0.

3This is the graph of cosets of the hypercube modulo C^{⊥}, or of C^{⊥} cosets, but it is the graph of cosets one uses when working with C. Since we do not work with a code, C, and its dual, C^{⊥}, simultaneously (in this paper), no confusion will occur in referring to the graph as the coset graph of “the code.”

Hence

(A_{G}^{l}f, f) = N_{l}(u) + N_{l}(v)

Let N_{l} = N_{l}(G) denote the minimum of N_{l}(v) ranging over all vertices v of the graph. Of course, (f, f) = 2, and so

\frac{(A_{G}^{l}f, f)}{(f, f)} ≥ N_{l}(G).

By using (4) we now obtain

ρ(A_{G}) ≥ (N_{l})^{1/l};

The right-hand-side term can be estimated through a cover H of G for which the calculation of N_{l}(H) might be much simpler. Indeed the following is clear.

Fact 6.1 If π: H → G is a cover, then any H cycle about a vertex, v, gives rise to a unique G cycle about π(v). Hence for any positive integer l we have

N_{l}(G) ≥ N_{l}(H).

In other words we have proved the following.

Theorem 6.2 Let G be a d-regular graph that contains two vertices of distance > l and H be a cover of G. Then

ρ(A_{G}) ≥ (N_{l}(H))^{1/l};

furthermore, if l is odd then the above equation holds with ρ replaced by λ_{2}.

The last statement follows by using (3) instead of (4).

The above theorem is quite simple. Unfortunately, for some purposes, such as coding theory, we are interested in λ_{2}(A_{G}) and the cover graph H (which can be chosen to be a boolean hypercube) will be bipartite (i.e. N_{l}(H) = 0 for l odd). So we prove the following variant of the above theorem.

Theorem 6.3 Let π: H → G be a covering map. Let e_{1}, e_{2} be two edges of distance > l (i.e. the distance from any of e_{1}’s endpoints to any of e_{2}’s is greater than l). Then

ρ(A_{G}) ≥ (N_{l}(H) + N_{l−1}(H))^{1/l};

furthermore, if l is odd then the above equation holds with ρ replaced by λ_{2}.

Proof Let e_{i} = {u_{i}, v_{i}} and set

f = χ_{u_{1}} + χ_{v_{1}} − χ_{u_{2}} − χ_{v_{2}}.

We have that (A^{l}χ_{u_{1}}, χ_{v_{1}}) is at least N_{l−1}(H), since any walk of length l − 1 beginning and ending in u_{1} yields a walk from u_{1} to v_{1} with one additional step. Similar reasoning to that in the previous theorem then yields:

(A^{l}f, f) ≥ 4(N_{l}(H) + N_{l−1}(H)),

and, of course, (f, f) = 4. Similar reasoning as before now yields this theorem.

□

We state two corollaries of this simple theorem:

Corollary 6.4 Fix d. Then for any d-regular graph, G, on n vertices, we have ρ(G) ≥ 2\sqrt{d − 1} − o(1) as n → ∞.

This follows by taking H to be the universal cover of G (namely the infinite d-regular tree) and by noticing that any d-regular graph on n vertices has at least two vertices which are at distance ⌊log_{d−1} n⌋. The revelant computation can be found in [LPS88] for instance.

We get stronger bounds with regular graphs which admit a cover which has more closed walks than the d-regular infinite tree, and this is exactly what happens for the coset graph of a code of length n which admits the boolean hypercube as a cover (see Example 3.2)

Corollary 6.5 Let C be a binary linear code of length n of rate ≤ R. The normalised minimum distance of C, δ, satisfies δ ≤ f(R), where f is a function that satisfies:

f(R) = \frac{1}{2} − C(1 + o(1))\sqrt{\frac{R}{log_{2} R}}

when R tends to 0, with C = 1/\sqrt{4e}.

The bound of [MRRW77] yields the same corollary but with C = 1. The calculation which lead to this theorem are in Appendix A.

7 Projecting out constants

In this section we introduce a technique that will strengthen essentially all of our Alon-Boppana theorems, including the ones in the previous section and the more refined theorems to come.

In the previous section we created functions, f, for which (A^{l}f, f) could be bounded; the idea was to concentrate f at a few vertices. Since it is important that f be orthogonal to 1, the all ones vector, we took f to have as many positive values as negative values, taking the values of different sign to be far apart (a distance > l). However, we may alternatively take f to be all positive, provided that we then remove f’s component in the direction of 1. This is the same as taking f to be concentrated and positive, subtracting the same (small) negative value at every other vertex.

The idea of choosing an arbitrary f and “projecting out the constant component” will be used repeatedly in this paper. Here is this technique applied to Theorem 6.2.

Theorem 7.1 Let π: H → G be a covering map. Let G be a d-regular graph, and let l be a value such that

N_{l}(H) ≥ d^{l}/|V_{G}|.

Then

ρ(A_{G}) ≥ (N_{l}(H) − \frac{d^{l}}{|V_{G}|})^{1/l};

furthermore, if l is odd then the above equation holds with ρ replaced by λ_{2}.

Proof Fix any v ∈ V_{G} and set f = χ_{v}. Then f̃ = f −1/|V_{G}| is orthogonal to 1. We have

(A^{l}f̃, f̃) = (A^{l}f, f) − (A^{l}1/|V_{G}|,1/|V_{G}|) ≥ N_{l}(H) − d^{l}/|V_{G}|,

and

(f̃, f̃) = (f, f) − (1/|V_{G}|,1/|V_{G}|) ≤ 1.

The reasoning used at the end of Theorem 6.2 now applies here, and we conclude the theorem.

□

We may also obtain the following variant of Theorem 6.3.

Theorem 7.2 Let π: H → G be a covering map with G a d-regular graph, and let l be a value such that

N_{l}(H) + N_{l−1}(H) ≥ 2d^{l}/|V_{G}|.

Then

ρ(A_{G}) ≥ (N_{l}(H) + N_{l−1}(H) − \frac{2d^{l}}{|V_{G}|})^{1/l};

furthermore, if l is odd then the above equation holds with ρ replaced by λ_{2}.

Proof Fix any edge, e = {u, v}, and let f = χ_{u} + χ_{v} and f̃ = f − 21/|V_{G}|. As before, f̃ is orthogonal to 1, and we have

(A^{l}f̃, f̃) = (A^{l}f, f) − 4(A^{l}1/|V_{G}|,1/|V_{G}|) ≥ 2N_{l}(H) + 2N_{l−1}(H) − 4d^{l}/|V_{G}|

and

(f̃, f̃) ≤ 2.

We argue as before.

□

Using this theorem we improve Corollary 6.5 by a factor of 2, as follows; see Appendix A for the proof.

Corollary 7.3 In Corollary 6.5, we may take C = 1/\sqrt{2e}.

8 Eigenfunction Pushing Techniques

Let us now apply (2) to functions of the form f̃ = f − c1 (where c is chosen such that f̃ is orthogonal to 1) where f is a function supported on a subset U of vertices of the graph (this means that f is equal to 0 outside of U). We easily obtain the following.

Proposition 8.1 Let f be supported on a set, U. Let G be d-regular. Then

λ_{2}(G) ≥ \frac{(A_{G}f, f)}{(f, f)} − \frac{d|U|}{|V_{G}|}.

Proof Let f̃ = f − c1 where c = (f,1)/|V_{G}|; then f̃ is orthogonal to 1, and so

λ_{2}(G) ≥ \frac{(A_{G}f̃, f̃)}{(f̃, f̃)}.  (7)

Since

(f,1)^{2} = (f, χ_{U})^{2} ≤ (f, f)(χ_{U}, χ_{U}) = (f, f)|U|,

we have

(A_{G}f̃, f̃) = (A_{G}f, f) − dc^{2}|V_{G}| ≤ (A_{G}f, f) − d(f, f)|U|/|V_{G}|.

Combining this with the fact that (f̃, f̃) ≤ (f, f) (since f̃ is a projection of f onto the subspace orthogonal to 1) and with the inequality (7), finishes the proposition.

□

To optimize this inequality we have to find for a given subset of vertices U the function f which maximizes the ratio \frac{(A_{G}f,f)}{(f,f)}. This maximum is known as a Dirichlet eigenvalue. We define for a graph G and a subset of vertices W ⊂ V_{G},

λ_{1,Dir}(W) = max_{f∈C_{0}(W)} \frac{(Af, f)}{(f, f)},

where we write C_{0}(W) for those functions supported in W. It is easy to check that the maximum is attained for a non-negative function (this is a simple consequence of the Perron-Froebenius theorem, see also [Fri93]). The f achieving the above maximum is called the first Dirichlet eigenfunction of A; this f is known to satisfy Af = λf for λ = λ_{1,Dir}(W) (see [Fri93]).

Then it makes sense to find the subset W of a given size which maximizes this eigenvalue, this leads us to define for a > 0, FK_{G}(a), the Faber-Krahn maximum of size a as

FK_{G}(a) = max_{|W |≤a} λ_{1,Dir}(W);

the W achieving this maximum is the Faber-Krahn maximizer of size a.

The nice thing about this quantity is that it has a lower bound in terms of the Faber-Krahn maximum for the same size of a cover graph, that is

Theorem 8.2 Let H be a cover of G. Then

FK_{H}(a) ≤ FK_{G}(a).

To prove this fact we need a lemma and a definition. For a covering map π: H → G and f : V_{H} → ℝ, we define the push forward, π_{∗}f, a function on V_{G}, whenever H is finite, via

(π_{∗}f)(v) = ∑_{π(w)=v} f(w).

Lemma 8.3 Let f ∈ C(V_{H}) and let π: H → G be a covering map. Assume H is finite. If f ≥ 0 everywhere, then also π_{∗}f ≥ 0. If A_{H}f ≥ λf everywhere, for some real λ, then also A_{G}π_{∗}f ≥ λπ_{∗}f. If f is supported in W, then π_{∗}f is supported in π(W).

Proof The first part (the non-negativity statement) is clear. The second part follows from the fact that π is a local isomorphism. The third part is also clear.

□

We are ready now to prove Theorem 8.2. Proof of Theorem 8.2 Let FK_{H}(a) = λ = λ_{1,Dir}(W) be the minimizing eigenvalue with |W | = a, and let f be the corresponding eigenfunction. Then π_{∗}f satisfies A_{G}(π_{∗}f) ≥ λπ_{∗}f and π_{∗}f is non-negative and supported on π(W), so

λ_{1,Dir}(π(W)) ≥ \frac{(A_{G}π_{∗}f, π_{∗}f)}{(π_{∗}f, π_{∗}f)} ≥ \frac{(λπ_{∗}f, π_{∗}f)}{(π_{∗}f, π_{∗}f)} ≥ λ.

Furthermore π(W) is a set of size ≤ a. Hence

FK_{G}(a) ≥ λ = FK_{H}(a).
□

Putting Proposition 8.1 and Theorem 8.2 together we obtain

Theorem 8.4 Let G be a d-regular graph, and H be a cover of G. Then

λ_{2}(A_{G}) ≥ FK_{H}(a) − \frac{da}{|V_{G}|}.

For an application to coding theory we observe:

Proposition 8.5 Let H be the n-dimensional hypercube. Then for α ∈ (0, 1) fixed we have FK_{H}(2^{αn}) ≥ 2\sqrt{γ(1 − γ)}n + o(n), where α = H_{2}(γ).

Proof We take a ball of size roughly 2^{αn}. For the details see appendix C.

□

Notice that we could also give a simple bound of FK_{H}(2^{αn}) ≥ αn by taking the characteristic function of a subcube of dimension αn.

A corollary is the first MRRW bound.

Corollary 8.6 For any δ ∈ (0, 1) we have

R_{max}(δ) ≤ h(1/2 − \sqrt{δ(1 − δ)}).

Proof Fix an α ∈ (0, 1) and a code C of information rate ≥ α and a corresponding covering map π: H → G We apply Theorem 8.4 with a = 2^{αn}/ log n. We conclude

λ_{2}(A_{G}) ≥ 2\sqrt{γ(1 − γ)} + o_{n}(1)

where α = h(γ). Hence

δ ≤ 1/2 − \sqrt{γ(1 − γ)},

and so

γ ≤ 1/2 − \sqrt{δ(1 − δ)}

and the corollary follows.

□

Remark 8.7 Notice that a (sub)cube of dimension αn has largest adjacency eigenvalue αn. This implies that FK_{H}(2^{αn}) ≥ αn. This gives the weak corollary that α_{max}(δ) ≤ (1 − δ)/2, which agrees asymptotically with the Plotkin and Griesmer bounds of coding theory (see [vL99]).

Remark 8.8 The approach which was used in this section borrows some ideas from [Nil91, Fri93]. Assume that G has a cover graph H. If f_{H} is a non-negative “approximate eigenfunction” on H, we can try to form “versions” of it, f_{G}, on a quotient, G, with similar properties. In this section we have formed our version on G by “summing over fibres” (this was the push forward function defined above); this is a similar technique to that used by Nilli (see [Nil91]), later refined by Friedman and Kahale (see [Fri93])^{4}. Our improvement on this technique was obtained by “projecting out the constants,” meaning that we project out the 1 component from f_{G} rather than setting up f_{G} (or f_{H}) with a matching non-positive component to make it orthogonal to 1 (as done by Nilli, Friedman, and Kahale).

9 A Stronger Alon-Boppana Bound

9.1 A Simple Improvement

In this subsection we give an example of a more general generalized Alon-Boppana bound. Namely, the following theorem and corollary strengthen Proposition 8.1.

Theorem 9.1 Let G be a d-regular graph and let p be any real-valued function defined on the eigenvalues of A_{G}. Then

(f, f) max_{i≥2} p(λ_{i}) ≥ (p(A_{G})f, f) − p(d)(f,1)^{2}/|V_{G}|,

The theorem follows immediately from the spectral decomposition on A_{G} as applied to f.

Corollary 9.2 If in addition to the hypothesis in the above theorem we have f is supported in U, then

(f, f) max_{i≥2} p(λ_{i}) ≥ (p(A_{G})f, f) − p(d)(f, f)|U|/|V_{G}|.

The special case p(x) = x was the bound used in the previous section. When G has a cover which is distance regular, then there is a very natural choice of polynomials in the corollary which enables to have some control on the term (p(A_{G})f, f) when f = χ_{v} for any vertex v of G. Indeed, let H be a distance regular cover of G. Let D denote the diameter of H. Then there are D + 1 polynomials P_{0}, P_{1}, P_{2}, …, P_{D} (see [BCN89]) such that P_{i}(A_{H}) is the adjacency matrix of the graph with the same vertices as H and two vertices are joined by an edge iff they are at distance i in H. In such a setting for any Q = ∑_{i=0}^{D} β_{i}P_{i} where the β_{i}’s are nonnegative we have that (Q(A_{G})χ_{v}, χ_{v}) ≥ (Q(A_{H})χ_{v}, χ_{v}). Notice now that (Q(A_{H})χ_{v}, χ_{v}) = β_{0} and therefore

4Actually, the previous technique (of Nilli, Friedman, and Kahale) takes radial functions on G given by the radial function on H that gives the first Dirichlet eigenfunction of a ball in H of a given radius. The technique used here “pushed down” the eigenfunction on H to G by summing over the fibres, i.e. for each vertex, v ∈ V_{G} we sum the eigenfunction over π^{−1}(v). This may be better suited in certain situations, e.g. when the graphs are not regular.

(Q(A_{G})χ_{v}, χ_{v}) ≥ β_{0}.  (8)

The coset graphs associated to a binary linear code of length n that we consider in this article have a common cover which is distance regular namely the boolean cube 𝔹^{n}. An application of the aforementioned remark leads to the Delsarte linear programming bound in coding theory as explained in the following subsection.

9.2 Connections with the Delsarte Approach

Let us first quickly review the linear programming approach for obtaining upper bounds on the minimum distance of a code (see [MS77, vL99] for more details). For a code C ∈ (𝔽_{2})^{n}, we consider the distance distribution of the code, i.e. the B_{i}’s for i = 0, …, n, where B_{i} denotes the average number of codewords of distance i to a fixed codeword, that is B_{i}=^{def} \frac{1}{|C|} |\{(x, y); x ∈ C, y ∈ C, d(x, y) = i\}|. The linear programming bound is based on the inequality

∑_{i=0}^{n} B_{i}K_{k}(i) ≥ 0

for k ∈ {0, 1, …, n}, where K_{k} is a Krawtchouk polynomial of degree k :

K_{k}(x)=^{def} ∑_{j=0}^{k}(−1)^{j}\binom{x}{j}\binom{n − x}{k − j},

with \binom{x}{j}=^{def} \frac{x(x−1)...(x−j+1)}{j!}. This yields linear inequalities which should be satisfied by the B_{i}’s. By maximizing the sum of the B_{i}’s (which is equal to the size of the code) which satisfy these inequalities we obtain a linear programming problem for which an upper bound can be found by duality. This duality result can be written as (see [vL99] Theorem 5.3.5)

Theorem 9.3 Let β(x) = 1 + ∑_{k=1}^{n} β_{k}K_{k}(x) be any polynomial with β_{k} ≥ 0 (1 ≤ k ≤ n) such that β(j) ≤ 0 for j = d, d + 1, …, n then any code of minimum distance ≥ d and length n has cardinality at most β(0).

Finding interesting choices for β turns out to be a nontrivial task, however the first MRRW bound can be obtained by a direct application of this theorem by choosing β appropriately (see [vL99]).

We now claim that this theorem is a simple consequence of Corollary 9.2, provided we restrict to linear codes. Indeed, if we let P_{k} =^{def}K_{k}((n − x)/2), then P_{k}(A_{𝔹^{n}}) is nothing but the adjacency matrix of the graph with vertices belonging to 𝔽_{2}^{n} and two vertices being adjacent iff they are at Hamming distance k. This follows immediately from classical results about the Hamming association scheme (see for instance Chapter 21 in [MS77]). Therefore by using the remark which follows Corollary 9.2 for any polynomial Q(x) = 1 + ∑_{k=1}^{n} β_{k}P_{k}(x) = 1 + ∑_{k=1}^{n} β_{k}K_{k}((n − x)/2) with β_{k} ≥ 0 we have that for any vertex of the coset graph G of a binary linear code of length n :

(Q(A_{G})χ_{v}, χ_{v}) ≥ 1.  (9)

Notice now that by Theorem 5.1 P_{k}(λ_{i}) = K_{k}(j) for some integer j ∈ [d_{min}(C), n] for any eigenvalue of the adjacency matrix of G different from n. Therefore Q(λ_{i}) = 1 + ∑_{k=1}^{n} β_{k}K_{k}(j). This implies that

(χ_{v}, χ_{v}) max{Q(λ_{i})|2 ≤ i ≤ |V_{G}|} ≤ 0  (10)

if Q has been chosen such that 1 + ∑_{k=1}^{n} β_{k}K_{k}(j) ≤ 0 for any integer j ∈ [d_{min}(C), n] (since this implies that Q(λ_{i}) ≤ 0 for i ∈ {2, …, |V_{G}|}). We eventually obtain by using Corollary 9.2 with f = χ_{v} and by putting inequalities (10) and (9) together that

0 ≥ 1 − \frac{1 + ∑_{k=1}^{n} β_{k}P_{k}(0)}{|C|}

since Q(n) = 1 + ∑_{k=1}^{n} β_{k}P_{k}(0) by Theorem 5.1 and |V_{G}| = |C|. This proves Theorem 9.3.

10 General Graph Theory

In this section we review some basic terminology and notions needed to generalize covering theory to graphs with multiple edges and/or self-loops.

10.1 Directed Graphs

By a directed graph we mean a pair of sets, G = (V_{G}, E_{G}), with an identification of E_{G} as a multi-set of V_{G} × V_{G}. In other words, G comes with an incidence map i_{G}: E_{G} → V_{G} × V_{G}. We write i, E, V for i_{G}, E_{G}, V_{G} if no confusion can result. If i(e) = (u, v) we say that e is of type (u, v) or that e orginates in u and terminates in v or that e’s tail is u and e’s head is v; in any case we will write e ∼ (u, v); if no multiple edges occur, i.e. if i is injective, then we may unambiguously write e = (u, v).

A walk is an alternating sequence of vertices and edges such that when …, v, e, … occurs in the sequence, e’s tail is v, and similarly with the order of v, e reversed (with “head” replacing “tail”). The adjacency matrix, A_{G}, of a graph, G, is the square matrix indexed on V_{G} whose u, v-th entry counts how many edges have type u, v. For a positive integer, k, the u, v-th entry of (A_{G})^{k} counts how many directed walks there are from u to v of length k. All this makes sense if V_{G} or E_{G} is infinite, although the entries of A_{G} or (A_{G})^{k} may not be finite.

A morphism π: H → G of directed graphs is a collection of maps π_{V} : V_{H} → V_{G} and π_{E}: E_{H} → E_{G} that commutes with the incidence relations (i.e., i_{G} ∘ π_{E} = (π_{V} × π_{V}) ∘ i_{H}). We often drop the subscripts from π_{V} , π_{E} if no confusion can result.

For a morphism of directed graphs, π: H → G, it is possible to give a number of equivalent definitions for π to be a covering map; all definitions amout to π being a local isomorphism in some sense. One definition is that for every vertex, v ∈ V_{G}, w ∈ π^{−1}(v), and every edge e ∈ E_{G} with tail v, there is exactly one f ∈ π^{−1}(e) whose tail is w, and similarly with “head” replacing “tail.” Another possibility is to define the geometric realization of a graph (as in [Fri93]); then a covering map is a covering map in the topological sense.

10.2 Graphs

By an undirected graph or simply a graph we mean a directed graph, G, with an involution^{5} ι on E_{G} that reverses heads and tails; in other words, G’s edges are paired, e ∼ (u, v) with an edge ι(e) ∼ (v, u), where e may be paired with itself^{6} if u = v.

5For ι to be an involution means that ι ∘ ι is the identity.

A morphism of graphs is one of the underlying directed graphs that commutes with the ι’s. A covering maps, adjacency matrices, and walks in graphs are just the same of the underlying directed graphs.

It is now simple to see that all the theorems of this paper could as well have been stated for graphs that may have self-loops or multiple edges.

11 Concluding Remarks

One of the most exciting questions to us is to find the Faber-Krahn maximizer and maximum of the hypercube. One can find examples^{7} of very small or large balls that are not the Faber-Krahn minimizers.

Question 11.1 Given γ ∈ (0, 1/2) is

\underline{lim}_{n→∞} FK_{𝔹^{n}}(2^{H_{2}(γ)})/n = 2\sqrt{γ(1 − γ)},

i.e. are balls asymptotically maximizers for the hypercube?

If the answer is no, then according to the method of Corollary 8.6, we have an improvement to the first MRRW bound.

A Calculations for Coding Theory

In this section we derive some simple combinatorial bounds needed in our discussion of coding theory bounds.

Throughout this section we write f(n) ≈ g(n) if (log f(n))/(log g(n)) → 1 as n → ∞ (for example, n ≈ 2n but n ≉ n^{2}).

6This gives rise to “half-loops,” which are edges paired with themselves, and “wholeloops” in the languauge of [Fri93]. For example, a whole-loop contributes 2 to an entry on the diagonal of the adjacency matrix, whereas a half-loop contributes 1.

7For example, in the 3-hypercube, the 2-dimensional subcube has eigenvalue 2, which is greater than that of a ball of the same size, namely \sqrt{3}. Similarly for the 3-dimensional ball in the 7-hypercube. Also the n/2 − \sqrt{n} radius ball has eigenvalue n − 4 (since n/2 − \sqrt{n} is the first zero of the second Krawtchouk polynomial), and the (n − 4) dimensional subcube is smaller; so by monotonicity (see [Fri93]) the ball here can also be beaten.

Lemma A.1 If ρ ∈ (0, 1/2] is fixed, and if any integer n > 0 we set r = r(n) = ⌊ρn⌋, then

|B_{r}| ≈ \binom{n}{r} ≈ 2^{nh(ρ)},

where |B_{r}| is the size of the ball of radius r in the n-hypercube, and where

h(θ) = −θ log_{2} θ − (1 − θ) log_{2}(1 − θ).

Proof This is a very standard application of Stirling’s formula; see, for example, [vL99].

□

Lemma A.2 Let α ∈ (0, 1) be fixed. For any integer n > 0 set k to be the even integer equal either to ⌊αn⌋ or to ⌊αn⌋ + 1. Then

N_{k}(𝔹^{n}) ≈ 2^{h(β_{0})n−n}n^{k}(1 − 2β_{0})^{k},

where β_{0} is the unique solution in (0, 1/2) to the following equation

(1 − 2β_{0}) log(β_{0}^{−1} − 1) = 2α.  (11)

Proof Since A_{𝔹^{n}} has eigenvalues n − 2i with multiplicity \binom{n}{i}, we have

N_{k}(𝔹^{n}) = \frac{1}{2^{n}} ∑_{i=0}^{n} \binom{n}{i}|n − 2i|^{k}.

It follows that setting B_{i} = \binom{n}{i}(n − 2i)^{k}, we see that

\frac{N_{k}(𝔹^{n})}{n + 1} ≤ max_{i=0,...,n/2} \frac{B_{i}}{2^{n}} ≤ N_{k}(𝔹^{n}).

To find the i maximizing B_{i}, we write

\frac{B_{i+1}}{B_{i}} = (\frac{n − i}{i + 1})(\frac{n − 2(i + 1)}{n − 2i})^{k} = (\frac{n − i}{i + 1})e^{k log_{e}(1−2/(n−2i))}.

Set β = β_{n} = i_{0}/n where i_{0} is the (an) i ≤ n/2 maximizing B_{i}. Since B_{i_{0}+1} < B_{i_{0}} we have

(\frac{1 − β}{β} + O(n^{−1}))e^{\frac{−2α}{1−2β} +O(n^{−1})} < 1.

Hence

\frac{1 − β}{β} < e^{\frac{2α}{1−2β}} + O(n^{−1}).

Similarly B_{i_{0}−1} < B_{i_{0}}, and the reverse inequality holds. Taking logarithms we conclude that

log(β^{−1} − 1)(1 − 2β) = 2α,

where β is the lim sup and lim inf of β_{n}. But differentiation shows that

f(β) = log(β^{−1} − 1)(1 − 2β)

has f′(β) = −2 log(β^{−1} −1)−(1−2β)/(β −β^{2}) which is < 0 for β ∈ (0, 1/2). It follows that there is a unique β_{0} ∈ (0, 1/2) that satisfies equation (11), and this β_{0} is the limit of β_{n}.

□

Corollary A.3 For α, n, k as above we have

N_{k}(𝔹^{n}) ≈ n^{k}(\frac{α + ω(α)}{e})^{k/2},

where ω(α) is a function of α with ω(α) = O(α^{3/2}) as α → 0.

Proof For β = 1/2 − ϵ with ϵ small we have

log(β^{−1}−1)(1−2β) = log(\frac{1/2 + ϵ}{1/2 − ϵ})2ϵ = 2ϵ log(1+4ϵ+O(ϵ^{2})) = 8ϵ^{2}+O(ϵ^{3}).

Hence for α small we have

2α = 8ϵ^{2} + O(ϵ^{3}) or \sqrt{α/4} = ϵ + O(ϵ^{2}) = ϵ + O(α).

Differentiation shows that

h′(x) = log_{2}(x^{−1} − 1), h′′(x) = \frac{− log_{2} e}{x − x^{2}}.

So h′(1/2) = 0 and h′′(1/2) = −4 log_{2} e, and

h(1/2 − ϵ) = 1 − 2(log_{2} e)ϵ^{2} + O(ϵ^{3}).

It follows that

2^{−n}2^{nh(β)}(n − 2β)^{k} ≈ 2^{−n(2 log_{2} e)ϵ^{2}+O(nϵ^{3})}n^{k}(1 − 2ϵ)^{k}
≈ e^{−2n(α/4+O(α^{3/2}))}n^{αn}(2\sqrt{α/4} + O(α))^{αn}

≈ e^{−αn/2}e^{O(α^{3/2}n}(n\sqrt{α})^{αn}(1 + (\sqrt{α}))^{αn} ≈ n^{k}(α/e)^{k/2}(1 + O(\sqrt{α}))^{k/2},

and the proposition is finished.

□

Proof of Corollary 6.5: Let G be the coset graph of C^{⊥}. Consider the largest odd integer, k, for which

∑_{i=0}^{k+2} \binom{n}{i} ≥ 2^{αn}.  (12)

It follows that there are two points in G of distance ≥ k + 3, and hence two edges of distance ≥ k + 1. By Theorem 6.3, we have

λ_{2}(A_{G}) ≥ (N_{k−1}(𝔹^{n}))^{1/k}.

But by equation (12) and Lemma A.1 we have

2^{nh(k/n)+O(1)} ≈ 2^{αn},

and thus

k/n = h^{−1}(α) + o_{n}(1)

(where o_{n}(1) denotes a function that tends to zero as n → ∞). Since h^{−1}(α) = α/ log_{2}(1/α) + O(α) for α small, Corollary A.3 then implies that

λ_{2}/n ≥ \sqrt{\frac{α}{e log_{2}(1/α)}} + ω(α) + o_{n}(1),

where ω(α) = O(\sqrt{α}). Now we use the fact that the minimum distance is (n − λ_{2})/2.

□

Proof of Corollary 7.3: Let k be as in the previous proof, except that k is the largest odd integer such that

N_{k+1}(𝔹^{n}) ≥ n^{k}/|V_{G}|.

Then taking k-th roots and dividing by n yields that k = nγ + o(n) where

\sqrt{γ/e} + ω(γ) = 2^{−α/γ}

where ω(γ) = O(γ) for γ small. Hence

γ = \frac{2α}{log_{2}(1/α)} + O(α),

for α small. Now we follow as in the proceeding proof, except that here γ = k/n is, to first order, twice what it was in the previous proof; this factor of two changes the C from 1/\sqrt{4e} to 1/\sqrt{2e} here.

□

B A Calculus Proposition

In this section we prove Proposition 4.1.

Let f be defined at α_{0}, and set δ_{0} = f(α_{0}). It suffices to show that α_{max}(δ_{0}) ≤ α_{0}.

For any ϵ > 0 near 0, fix an η > 0. If

α_{max}(f(α_{0} + ϵ) + η) > α_{0} + ϵ,  (13)

then there are codes C_{i} of length n_{i} → ∞ as i → ∞ such that δ_{C_{i}} ≥ f(α_{0} + ϵ) + η and

\overline{lim}_{i→∞} α_{C_{i}} > α_{0} + ϵ.

By passing to a subsequence we can assume that α_{C_{i}} > α_{0} + ϵ for all i. But then δ_{max} exceeds f (by at least η) at the value α_{0} + ϵ, which is impossible. So inequality (13) is impossible, meaning that

α_{max}(f(α_{0} + ϵ) + η) ≤ α_{0} + ϵ.

Now let η = η(ϵ) = δ_{0} − f(α_{0} + ϵ) and let ϵ → 0. We conclude α_{max}(δ_{0}) ≤ α_{0}, and we are done.

C The First Eigenvalue of a Ball and Related Calculations

In this appendix we prove Proposition 8.5.

Since the size of the ball of radius nγ in 𝔹^{n} is ≈ 2^{nh(γ)}, we need only show that the ball of radius nγ has first eigenvalue at least

2n\sqrt{γ(1 − γ)} + o(n).

Let 0 denote the origin in (𝔽_{2})^{n}, which is a vertex of 𝔹^{n}; the weight, |v|, of a vertex, v, of 𝔹^{n} is its distance from 0, or the number of nonzero coordinates it has. Consider those functions, f, on 𝔹^{n} that depend only on the weight of the vertex. For such an f, let f_{nrm}, the normalization of f, be the function on [0..n] such that

f_{nrm}(i) = f(v) / \sqrt{\binom{n}{i}} for any v with |v| = i.

Then it is easy (and completely standard) to see that

(A_{G}f)_{nrm}(i) = \sqrt{i(n − i + 1)} f_{nrm}(i − 1) + \sqrt{(i + 1)(n − i)} f_{nrm}(i + 1),

for all i (the coefficient of the right-hand-side vanishes for f_{nrm} at the values −1 and n+1). So under normalization the operator A_{G} becomes a symmetric tridiagonal operator Ã whose i − 1, i entry is \sqrt{i(n − i + 1)}. It follows that if i ∈ [γn − ω(n), γn], where ω(n) is any function that is o(n), then the i − 1, i entry is

n\sqrt{γ(1 − γ)} + o(n).

Hence, by monotonicity (see, e.g., [Fri93]), the first Dirichlet eigenvalue of the ball of radius nγ is at least that of the path of length ω(n) + 1 times

n\sqrt{γ(1 − γ)} + o(n).

But this path’s eigenvalue is well-known to be 2 cos(π/ω(n)), giving us a lower bound on the ball’s eigenvalue of

2n\sqrt{γ(1 − γ)} + o(n),

provided that ω(n) grows faster than \sqrt{n} (e.g., we may take ω(n) = n^{3/4}).

□

References

[BCN89] A.E. Brouwer, A.M. Cohen, and A. Neumaier. Distance regular graphs. Springer Verlag, Berlin, 1989.

[Cha84] Isaac Chavel. Eigenvalues in Riemannian geometry. Academic Press Inc., Orlando, Fla., 1984. Including a chapter by Burton Randol, With an appendix by Jozef Dodziuk.

[DS91] Charles Delorme and Patrick Solé. Diameter, covering index, covering radius and eigenvalues. European J. Combin., 12(2):95– 108, 1991.

[Fab23] C. Faber. Beweiss, dass unter allen homogenen Membrane von gleicher Spannung die Kreisförmige den tiefsten Grundton gibt. Sitzungsber.–Bayer. Akad. Wiss., Math.-Phys. Munich, pages 169–172, 1923.

[Fri93] Joel Friedman. Some geometric aspects of graphs and their eigenfunctions. Duke Math. J., 69(3):487–525, 1993.

[Kra25] E. Krahn. Über eine von Rayleigh formulierte Minimaleigenschaft des Kreises. Math. Ann., 94:97–100, 1925.

[LPS88] A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261–277, 1988.

[MRRW77] Robert J. McEliece, Eugene R. Rodemich, Howard Rumsey, Jr., and Lloyd R. Welch. New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities. IEEE Trans. Information Theory, IT-23(2):157–166, 1977.

[MS77] F. J. MacWilliams and N. J. A. Sloane. The theory of errorcorrecting codes., volume I,II. North-Holland Publishing Co., Amsterdam, 1977. North-Holland Mathematical Library, Vol. 16.

[Nil91] A. Nilli. On the second eigenvalue of a graph. Discrete Math., 91(2):207–210, 1991.

[vL99] J. H. van Lint. Introduction to coding theory. Springer-Verlag, Berlin, third edition, 1999.