{"id":2962,"date":"2011-10-29T21:17:26","date_gmt":"2011-10-29T19:17:26","guid":{"rendered":"https:\/\/wpethzprd.ethz.ch\/kowalski\/?p=2962"},"modified":"2024-02-20T13:40:36","modified_gmt":"2024-02-20T11:40:36","slug":"explicit-multiplicative-combinatorics","status":"publish","type":"post","link":"https:\/\/blogs.ethz.ch\/kowalski\/2011\/10\/29\/explicit-multiplicative-combinatorics\/","title":{"rendered":"Explicit multiplicative combinatorics"},"content":{"rendered":"

One of the goals of my course on expanders<\/a> is to (try to) get an explicit spectral gap for the Cayley graphs of $latex \\mathrm{SL}_2(\\mathbf{F}_p)$, for $latex p$ prime, with respect to the generating set
\n$latex S_p=\\{u,u^{-1}, v,v^{-1}\\}$
\nwhere
\n$latex u=\\begin{pmatrix} 1& 3\\\\ 0&1\\end{pmatrix},\\quad\\quad v=\\begin{pmatrix} 1&0\\\\3&1\\end{pmatrix}$
\n(which corresponds to the reduction modulo $latex p$ of the Cayley graph of the “Lubotzky group” $latex L$, generated in $latex \\mathrm{SL}_2(\\mathbf{Z})$ by the “same” matrices.)<\/p>\n

The first thing to do in order to obtain an explicit estimate is to get an explicit form of the relation between “pairs of sets with large multiplicative energy” and “cosets of a common approximate group” — indeed, this is a crucial point in the first step of the argument discovered by Bourgain and Gamburd<\/a> to derive expansion for some Cayley graphs from a classification of approximate subgroups (or more directly, of sets with “small tripling”, a classification which had been produced by Helfgott<\/a> for $latex \\mathrm{SL}_2(\\mathbf{F}_p)$).<\/p>\n

To explain this, recall that if $latex A, B\\subset G$ are subsets of a finite group $latex G$, the normalized multiplicative energy<\/i> $latex e(A,B)$ is defined by
\n$latex e(A,B)=|\\{(x_1,y_1,x_2,y_2)\\in A^2\\times B^2\\,\\mid\\, x_1y_1=x_2y_2\\}|\/(|A||B|)^{3\/2}.$
\nIt is easy to show that $latex e(A,B)\\leq 1$, and it is a pleasant exercise to prove that the extreme case $latex e(A,B)=1$ occurs if and only if there exists a subgroup $latex H$ of $latex G$ and elements $latex x$, $latex y$ of $latex G$ such that
\n$latex A=xH,\\quad\\quad B=Hy.$<\/p>\n

The Bourgain-Gamburd argument depends on understanding sets $latex A$ and $latex B$ such that
\n$latex e(A,B)\\geq |G|^{-\\varepsilon}$
\nfor some (small) $latex \\varepsilon>0$.
\nThis can now be done, in some cases, by first proving an “approximate” version of the characterization of the extreme $latex e(A,B)=1$, and then classifying the resulting “approximate” objects. The second step is much more involved, and I won’t talk about it here, but the first can be done in full generality. The standard texts explaining this are the book of Tao and Vu<\/a> and a paper of Tao<\/a> (which contains more details than the summary in the book.) <\/p>\n

It is clear from reading the proofs that they are “effective”, but these sources do not give explicit inequalities. So I did the exercise of going through the arguments to get actual constants, inputing the recent explicit results of Petridis<\/a> to get better control on product sets than the corresponding argument in Tao’s paper. After three or four rounds of checks, I get the following: if
\n$latex e(A,B)\\geq \\frac{1}{\\alpha},$
\nthen there exist a $latex \\beta$-approximate subgroup $latex H$ of $latex G$ and elements $latex x$, $latex y\\in G$,
\nsuch that
\n$latex |H|\\leq \\beta_2|A|,\\quad\\quad |A\\cap xH|\\geq \\beta_1^{-1}|A|,\\quad\\quad |B\\cap Hy|\\geq \\beta_1^{-1}|B|,$
\nwhere
\n$latex \\beta\\leq 2^{14257}\\alpha^{6330},\\quad\\quad \\beta_1\\leq 2^{14667}\\alpha^{6553},\\quad\\quad \\beta_2\\leq 2^{283}\\alpha^{126},$
\n(and a $latex \\beta$-approximate subgroup is defined to be a symmetric subset, containing the identity, such that $latex H\\cdot H\\subset X\\cdot H$ for some subset of size $latex |X|\\leq \\beta$.)<\/p>\n

For the moment, I’ve only typed a very condensed note<\/a> spelling this out, which is found on my page of unpublished notes; I admit that I had some fun devising an arrow notation to simplify keeping track of the relation and sizes between the sets involved… <\/p>\n

All this will be incorporated in my lectures notes on expanders<\/a>, and then expanded later to a full proof so that the latter are self-contained. I will also attempt to improve these constants, which are not very promising when I think of what the spectral gap will become in the end…<\/p>\n","protected":false},"excerpt":{"rendered":"

One of the goals of my course on expanders is to (try to) get an explicit spectral gap for the Cayley graphs of $latex \\mathrm{SL}_2(\\mathbf{F}_p)$, for $latex p$ prime, with respect to the generating set $latex S_p=\\{u,u^{-1}, v,v^{-1}\\}$ where $latex u=\\begin{pmatrix} 1& 3\\\\ 0&1\\end{pmatrix},\\quad\\quad v=\\begin{pmatrix} 1&0\\\\3&1\\end{pmatrix}$ (which corresponds to the reduction modulo $latex p$ of … Continue reading Explicit multiplicative combinatorics<\/span><\/a><\/p>\n","protected":false},"author":625,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-2962","post","type-post","status-publish","format-standard","hentry","category-blogroll"],"_links":{"self":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/2962","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/users\/625"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/comments?post=2962"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/2962\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/media?parent=2962"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/categories?post=2962"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/tags?post=2962"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}