Notes of Alex Lubotzky’s talk

Ramanujan graphs and error correcting codes

Joint work with Tali Kaufman.

1. Codes

1.1. Definitions

An {(n,k,d)}-code is a {k}-dimensional vectorsubspace {C} of {{\mathbb Z}_2^X} wher {n=|X|} is the length of the code, {d} is the distance of the code (in the Hamming metric).


\displaystyle  \begin{array}{rcl}  r(C)=\frac{k}{n}~\textrm{(rate)},\quad \delta(C)=\frac{d}{n}~\textrm{(normalized distance)}. \end{array}

Good codes have {n} tending to infinity, {r(c)}, {\delta(c)\geq\epsilon>0}.


\displaystyle  \begin{array}{rcl}  C^{\bot}=\{w\in{\mathbb Z}_2^X \,;\,w\cdot v=0\,\forall v\in C\}. \end{array}

{C} is called LDPC (low density parity check) if there exists a basis of {C^{\bot}} formed of vectors of bounded {\ell_1}-norm.

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

Say {C} is symmetric if {H}-invariant where {H} is a group acting transitively on {C}.

{C} is single orbit symmetric if there exists {w\in C^{\bot}} such that the {H}-orbit of {w} generates {C^{\bot}}.

{C} is highly symmetric if, in addition, {w} is of bounded {\ell_1}-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 {n} 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 {G} be a finite group, {m=|G|}. Let {S} be a symmetric ({S=S^{-1}}) generating set. Let {E} denote the set of edges of {Cay(G,S)}. Let {B\subset {\mathbb Z}_2^S} be a code. Upgrade it into a much large code by setting

\displaystyle  \begin{array}{rcl}  C(G,S,B)=\{f\in {\mathbb Z}_2^E \,;\, \forall g\in G,\,f_g \in B\}. \end{array}

Here, {f_g} is the restriction of {f} to the set of edges containing {g}.

Theorem 2 (Kaufman, Wigderson) {C(G,S,B)} is a linear code with {n=\frac{|G||S|}{2}},

\displaystyle  \begin{array}{rcl}  r(C)\geq 2r(B)-1, \quad \delta(C)\geq (\frac{\delta(B)-\lambda}{1-\lambda})^2 , \end{array}

where {\lambda=\frac{\lambda_1}{|S|}} is the normalized second eignevalue of {Cay(G,S)}.

Corollary 3 If {r(B)>\frac{1}{2}} and {\delta(B)>\lambda}, we get good LDPC codes.

However, {C(G,S,B)} is not symmetric ({G} 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 {S} to {T} is {\frac{1}{d}|S||T|} plus an error term controlled by expansion.

It follows that the support of {f\in C(G,S,B)} 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 {\delta(B)}.

2.3. How to make it symmetric ?

Let {T} be a group acting by automorphisms on {G}. Let {H=G\times T} be the semi-direct product. Then {H} acts on {Cay(G,S)}. Action is transitive if {S} is a single {T}-orbit. If {B} is symmetric (resp. single orbit), so is {C(G,S,B)}.

2.4. Edge transitive Ramanujan graphs

An {r}-regular finite connected graph is Ramanujan if {\lambda_1 \leq 2\sqrt{r-1}}.

[LPS, Margulis]: exist for {r=q+1}, {q} a prime.

[Morgenstern]: exist for {r=q+1}, {q} a prime power.

Classical examples are not edge transitive.

Theorem 5 (Lubotzky, Samuels, Vishne 2005) For all prime power {q} and {\alpha\in{\mathbb N}} with {q^{\alpha}>17}, let {G=PSL_2 (q^{\alpha})} or {G=PSL_2 (q^{\alpha})}, let {T} be the non split torus of order {q+1} in {G=PGL_2 (q^{\alpha})}. Put

\displaystyle  \begin{array}{rcl}  S=\{t\tau t^{-1}\,;\,t\in T\}. \end{array}

Then {Cay(G,S)} is an edge-transitive Ramanujan graph.

{T} has order {q+1}. It is the image in {PGL_2 (q)} of {F_{q^2}^*} acting by multiplication on {F_{q^2}}, i.e. linearly on {F_{q}^2}.

2.5. The small code

Such graphs have normalized second eigenvalue {\lambda\sim\frac{1}{\sqrt{q}}}. Therefore for {B}, we need {r(B)>\frac{1}{2}}, {\delta(B)>\frac{2\sqrt{q}}{q+1})}. One single {q} will do.

A modified BCH code does the job for {q=4093}. We use for {B} an ideal in the ring {R} of {{\mathbb Z}_2}-polynomials mod {x^n -1}, the ideal generated by a polynomial {h} which divides {x^n -1}. For {n=2^m -1}, pick a primitive {w\in F_{2^m}}. Let {h_r} be the least common multiple of all minimal polynomials of powers of {w} up to {r}-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 {2(2^m -1)=q+1} with {q} a prime power. {q=2^{11}-3} turns out to be a solution.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s