**Ramanujan graphs and error correcting codes**

Joint work with Tali Kaufman.

**1. Codes **

** 1.1. Definitions **

An -code is a -dimensional vectorsubspace of wher is the length of the code, is the distance of the code (in the Hamming metric).

**Notation**:

Good codes have tending to infinity, , .

**Notation**:

is called LDPC (low density parity check) if there exists a basis of formed of vectors of bounded -norm.

They are convenient, since checking that a word belongs to the code is fast.

Say is symmetric if -invariant where is a group acting transitively on .

is single orbit symmetric if there exists such that the -orbit of generates .

is highly symmetric if, in addition, is of bounded -norm. Of cours, highly symmetric implies LDPC.

** 1.2. Basic question **

**Problem [Kaufman-Wigderson]**: To what extent do symmetric LDPC attain the gold standards of linear distance and constant rate ?

Most common codes are symmetric under a cyclic group, but conjecturally, there should be no cyclic good codes.

**Berman**: true if is a product of small primes.

**Babai, Spilka, Stefankovic**: No cyclic LDPC codes.

**Kaufman-Wigderson**: Extend this to solvable groups of bounded derived length.

** 1.3. Our result **

Theorem 1 (Kaufman, Lubotzky)There exist highly symmetric good codes. They are strongly explicit.

**2. Cayley codes **

** 2.1. Definition **

Let be a finite group, . Let be a symmetric () generating set. Let denote the set of edges of . Let be a code. Upgrade it into a much large code by setting

Here, is the restriction of to the set of edges containing .

Theorem 2 (Kaufman, Wigderson)is a linear code with ,

where is the normalized second eignevalue of .

Corollary 3If and , we get good LDPC codes.

However, is not symmetric ( does not act transitively on edges).

** 2.2. Proof of Theorem \ref **

}

Inspired by Sipser and Spielman.

Counting equations gives rate.

The distance bound uses the mixing lemma.

Lemma 4 (Alon, Chung)The number of edges joining to is plus an error term controlled by expansion.

It follows that the support of cannot be too small, hence the average number of edges in the support sharting a vertex cannot be small (since we have a lower bound on .

** 2.3. How to make it symmetric ? **

Let be a group acting by automorphisms on . Let be the semi-direct product. Then acts on . Action is transitive if is a single -orbit. If is symmetric (resp. single orbit), so is .

** 2.4. Edge transitive Ramanujan graphs **

An -regular finite connected graph is Ramanujan if .

**[LPS, Margulis]**: exist for , a prime.

**[Morgenstern]**: exist for , a prime power.

Classical examples are not edge transitive.

Theorem 5 (Lubotzky, Samuels, Vishne 2005)For all prime power and with , let or , let be the non split torus of order in . Put

Then is an edge-transitive Ramanujan graph.

has order . It is the image in of acting by multiplication on , i.e. linearly on .

** 2.5. The small code **

Such graphs have normalized second eigenvalue . Therefore for , we need , . One single will do.

A modified BCH code does the job for . We use for an ideal in the ring of -polynomials mod , the ideal generated by a polynomial which divides . For , pick a primitive . Let be the least common multiple of all minimal polynomials of powers of up to -th power.

A trick due to van Lint allows to upgrade a cyclic code into a twice larger cyclic code with the same distance. Must solve with a prime power. turns out to be a solution.