## 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).

Notation:

$\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}$.

Notation:

$\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.

Advertisements

## 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 http://www.math.ens.fr/metric2011/
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.