## Problem list, march 24th 2011

1. Harald Helfgott

I like solvable groups, in particular the following one, which models the general solvable case,

$\displaystyle \begin{array}{rcl} G=\{\begin{pmatrix} x & y \\ 0 & 1 \end{pmatrix}\,;\,x\in K^* ,\,y\in K\}. \end{array}$

where ${k}$ is a prime field.

Proposition 1 (special case of Gill, Helfgott 2010) Let ${A\subset G}$. Then either

$\displaystyle \begin{array}{rcl} |AAA|>|A|^{1+\delta} \end{array}$

with some absolute ${\delta}$, or ${A}$ is contained in a maximal torus, or ${A}$ is covered by ${k\ll |A|^{\epsilon}}$ right cosets of ${U}$, or

$\displaystyle \begin{array}{rcl} AAAAA=G. \end{array}$

Problem:

1. Let ${S}$ generate ${G}$, with ${|S|=2}$. Show that
$\displaystyle \begin{array}{rcl} diameter(Cay(G,S))\leq (\log |G|)^{O(1)}. \end{array}$
2. How do we navigate. I.e., how does one find a short path from e-any element to identity ?

We have the diameter bound for ${SL_2 (p)}$, but we do not know how to navigate deterministically. There is a randomized algorithm.

[Bukh, Helfgott, Kassabov] have some partial result, but we are close to give up now.

2. James Lee

Dvoretzky theorem. Revived in Szarek’s ICM address.

Theorem 2 Let ${X}$ be an ${n}$-dimensional Banach space. There is ${k}$-dimensional linear subspace ${Y\subset X}$ on which the induced norm is nearly Euclidean, with ${k}$ tending to infinity with ${n}$.

Vitaly Milman gave a randomized proof, he was later imitated a lot in Banach space geometry.

Definition 3

$\displaystyle \begin{array}{rcl} \Delta(X)=\max_{x\in X}\frac{\sqrt{n}|x|_2}{|x|_1}. \end{array}$

More or less simultaneously,

• Figiel, Lindenstrauss, Milman achieved ${/Delta(X)\leq 1+\epsilon}$ if ${dim(X)\geq C(\epsilon)n}$
• Kasin achieved ${/Delta(X)\leq 1+\epsilon}$ if ${dim(X)\geq C(\epsilon)n}$.

This has applications to compressed sensing, quantum computing.

Definition 4 Say that ${X}$ is ${(t\epsilon)}$-spread if for all ${x\in X}$,

$\displaystyle \begin{array}{rcl} |x_{\bar{S}}|_2 \geq |x|_2 , \end{array}$

for all sets ${S}$ of coordinates of size ${t}$.

Analogy with linear codes.

Proposition 5 Every subspace ${X}$ is ${\frac{n}{4\Delta(X)^2},\frac{1}{2\Delta(X)}}$-spread.

To get good subspaces ${X}$, consider kernel a random ${\pm 1}$ matrix.

Question: Derandomize ?

Known: [Guruswami, Lee, Wigderson 2008]: ${n^\epsilon}$ random bits. [Guruswami, Lee, Razborov 2008]: ${\Delta(X)=(\log n)^{\log\log\log n}}$.

Let ${G}$ be a random ${d}$-regular graph, ${L\subset {\mathbb R}^d}$ a random subspace of dimension ${\geq 0.99 d}$. Define

$\displaystyle \begin{array}{rcl} X(G,L)=\{x\in{\mathbb R}^E \,;\, \end{array}$

(compare Lubotzky’s talk).

Question: Is ${\Delta(X(G,L))}$ bounded ?

In many cases (compressed sensing, dimension reduction,…), the search for deterministic algorithms has led to better algorithms.

3. Anup Rao

The tree code, invented by Schulman.

Start with binary tree of depth ${n}$. Label edges with a constant size alphabet ${F_{2^\ell}}$. We want that for every vertices ${u}$ and ${v}$, Hamming distance of the words read along the two legs of the shortest path between ${u}$ and ${v}$ on tree is ${\geq k\delta}$. This gives a code of distance ${\delta}$.

Such a code is more powerful than error-correcting codes. It is useful in communication. Indeed,

We want an explicit construction of such a code. One approach is to use polynomials. Let ${P}$ be a degree ${n-1}$ polynomial on ${F_{2^\ell}}$. We want that for every polynomial ${q}$ of degree ${k on ${F_2}$, ${q(0)=1}$, the product ${pq}$ has ${\delta k}$ nonzero coefficients in terms of degree ${\leq k}$. The labelling is reconstructed from the coefficient of ${pq}$ for various polynomials ${q}$.

Question: Can one find such a polynomial ? And an algorithm that computes it in polynomial time ?

4. Parikshit Gopalan

Construction of pseudorandom generators for half spaces.

[Meka-Zuckerman] use seed size ${\log n +(\log\frac{1}{\epsilon})^2}$.

Question: Improve this.

Panigrahy proposed the following approach. Instead on the hypercube, work on the sphere. Put ${n}$ repelling point charges on the ${n}$-sphere. Compute a stable equilibrium. Is this ${\epsilon}$-uniformly distributed ? Want number of points be ${m=poly(n,\frac{1}{\epsilon})}$.

5. Zeev Dvir

Explicit construction of unbalanced bipartite expanders. Fix ${0<\alpha<1}$. Vertex sets ${A=[n]}$ and ${B=[n^{\alpha}]}$, with left degree ${\ell(\alpha)}$, such that for every subset ${S\subset A}$, ${|S|\leq \{ 0,1 \}^{1-\epsilon}}$, and edge expansion ${\geq 1+\epsilon}$.

There exists a (sum-product) construction, but is does not reduce right vertex size that much.

6. Alex Lubotzky

Gromov: is every hyperbolic group residually finite ?

I explain a strategy that relies on expansion for finite simple groups.

1. Adding long relations do not kill the group: it stays infinite and hyperbolic.
2. There exist hyperbolic groups which have Kazhdan’s property (T) and whose finite simple quotients must have ranks tending to infinity.

Given a family of finite simple groups ${G_i}$ with generators ${a_i}$, ${b_i}$ and ranks tending to infinity. Assume that it is a family of expanders.

Question: Prove that there exist finitely many very large words ${w_1 ,\ldots,w_{\ell}}$ such that for every ${i}$, there exists ${j}$ such ${w_j (a_i ,b_i)\not=1}$.

This would solve Gromov’s question. Indeed, adding relators ${w_1 ,\ldots,w_{\ell}}$ to a group having property (2) kills every finite simple non abelian quotient. Abelian quotients are easy to handle.

Comment by Breuillard: There is a similar problem for alternating group ${\mathfrak{A}_n}$.