Ramanujan graphs and error correcting codes
Joint work with Tali Kaufman.
An -code is a -dimensional vectorsubspace of wher is the length of the code, is the distance of the code (in the Hamming metric).
Good codes have tending to infinity, , .
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
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 .
Corollary 3 If 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.