\documentclass{slides} \usepackage{amssymb, amsmath, amscd, color, epsfig, russcorr, russlh} %,wasysym} %\usepackage[matrix,arrow]{xy} %\usepackage[table]{xcolor} %\usepackage[T1,T2A]{fontenc} \newcommand{\green}{\color[rgb]{0,0.4,0}} \newcommand{\purple}{\color[rgb]{0.4,0,0.4}} \newcommand{\red}{\color[rgb]{0.7,0,0}} \newcommand{\blue}{\color{blue}} \def\бф{\bf} \def\ем{\em} \def\ит{\it} \def\блуе{\blue} \def\пурпле{\purple} \def\ред{\red} \def\греен{\green} \def\невпаге{\newpage} \def\eqref#1{(\ref{#1})} \newcommand{\goth}{\mathfrak} \newcommand{\g}{{\frak g}} \newcommand{\arrow}{{\:\longrightarrow\:}} \newcommand{\Z}{{\Bbb Z}} \def\C{{\Bbb C}} \newcommand{\R}{{\Bbb R}} \newcommand{\Q}{{\Bbb Q}} \renewcommand{\H}{{\Bbb H}} \newcommand{\6}{\partial} \newcommand{\ver}{{\operatorname{\rm vert}}} \def\1{\sqrt{-1}\:} \newcommand{\restrict}[1]{{\left|_{{#1}}\right.}} \newcommand{\cntrct} % contraction with a vector field {\hspace{2pt}\raisebox{1pt}{\text{$\lrcorner$}}\hspace{2pt}} \def\Bbb#1{\mathbb #1} \newcommand{\calo}{{\cal O}} \newcommand{\cac}{{\cal C}} % Correcting TeX... %\let\oldtilde=\tilde %\renewcommand{\tilde}{\widetilde} \renewcommand{\bar}{\overline} \renewcommand{\phi}{\varphi} \renewcommand{\epsilon}{\varepsilon} \renewcommand{\geq}{\geqslant} \renewcommand{\leq}{\leqslant} % Operatornames \newcommand{\even}{{\rm even}} \newcommand{\ev}{{\rm even}} \newcommand{\odd}{{\rm odd}} \newcommand{\const}{{\sf const}} \newcommand{\fl}{{\rm fl}} \newcommand{\im}{\operatorname{\sf im}} \newcommand{\Zar}{{\operatorname{\sf Zar}}} \newcommand{\End}{\operatorname{End}} \newcommand{\Mat}{\operatorname{Mat}} \newcommand{\Sym}{\operatorname{Sym}} \newcommand{\Ham}{\operatorname{Ham}} \newcommand{\Tot}{\operatorname{Tot}} \newcommand{\Id}{\operatorname{Id}} \newcommand{\St}{\operatorname{St}} \newcommand{\id}{\operatorname{\text{\sf id}}} \newcommand{\Vol}{\operatorname{Vol}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\Aut}{\operatorname{Aut}} \newcommand{\Av}{\operatorname{\sf Av}} \newcommand{\Alt}{\operatorname{Alt}} \newcommand{\Iso}{\operatorname{Iso}} \newcommand{\Sec}{\operatorname{Sec}} \newcommand{\Can}{\operatorname{Can}} \newcommand{\Sing}{\operatorname{Sing}} \newcommand{\Spin}{\operatorname{Spin}} \newcommand{\codim}{\operatorname{codim}} \newcommand{\coim}{\operatorname{coim}} \newcommand{\Pic}{\operatorname{Pic}} \newcommand{\coker}{\operatorname{coker}} \newcommand{\slope}{\operatorname{slope}} \newcommand{\diam}{\operatorname{\sf diam}} \newcommand{\rk}{\operatorname{rk}} \newcommand{\Def}{\operatorname{Def}} \newcommand{\Ric}{\operatorname{Ric}} \newcommand{\Lie}{\operatorname{Lie}} \newcommand{\Tw}{\operatorname{Tw}} \newcommand{\Tr}{\operatorname{Tr}} \newcommand{\Spec}{\operatorname{Spec}} \newcommand{\Diff}{\operatorname{Diff}} \renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\inbfpare}[1]{{% \mbox{\tt (}\hspace{-5pt}\mbox{\tt (} #1 % \mbox{\tt )}\hspace{-5pt}\mbox{\tt )}% }} \newcommand{\comment}[1]{{}} \def\blacksquare{\hbox{\vrule width 10pt height 10pt depth 0pt}} \def\endproof{\blacksquare} \def\ендпрооф{\blacksquare} \def\shortdash{\mbox{\vrule width 4.5pt height 0.55ex depth -0.5ex}} \makeatletter %\@ifundefined{Bbb} % {\newcommand{\Bbb}[1]{{\mathbb #1}}}% %{}% {\edef\Bbb#1{{\Bbb #1}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Pagestyle % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \setlength\paperheight {10in}% \setlength\paperwidth {13.5in} \setlength{\textwidth}{0.8\paperwidth} \setlength{\textheight}{0.8\paperheight} \setlength{\pdfpageheight}{\paperheight} \setlength{\pdfpagewidth}{\paperwidth} \addtolength{\topmargin}{-20mm} \addtolength{\leftmargin}{-25mm} \addtolength{\rightmargin}{-25mm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Lemma, sublemma, corollary, proposition, theorem, % % definition,example defined there: % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\лемма}{% {\bf \green ЛЕММА:\ }} \newcommand{\утверждение}{% {\bf \green УТВЕРЖДЕНИЕ:\ }} \newcommand{\следствие}{% {\bf \green СЛЕДСТВИЕ:\ }} \newcommand{\теорема}{% {\bf \green ТЕОРЕМА:\ }} \newcommand{\гипотеза}{% {\bf \green ГИПОТЕЗА:\ }} \newcommand{\предложение}{% {\bf \green ПРЕДЛОЖЕНИЕ:\ }} \newcommand{\определение}{% {\bf \green ОПРЕДЕЛЕНИЕ:\ }} \newcommand{\пример}{% {\bf \green ПРИМЕР:\ }} \newcommand{\замечание}{% {\bf \green ЗАМЕЧАНИЕ:\ }} \newcommand{\вопрос}{% {\bf \green ВОПРОС:\ }} \newcommand{\упражнение}{% {\bf \green УПРАЖНЕНИЕ:\ }} \newcommand{\указание}{% {\bf \green УКАЗАНИЕ:\ }} \newcommand{\задача}{% {\bf \green ЗАДАЧА:\ }} \newcommand{\доказательство}{% {\bf \green ДОКАЗАТЕЛЬСТВО:\ }} \newcommand{\дшаг}{{\bf \green Доказательство. Шаг 1:\ }} \newcommand{\ps@verbit}{% \renewcommand{\@oddhead}{% \scriptsize {\it \small Свойство (Т), лекция 2 \hfil \tiny Миша Вербицкий}} \renewcommand{\@evenhead}{\@oddhead} \renewcommand{\@oddfoot}{\hfil\thepage\hfil} \renewcommand{\@evenfoot}{\@oddfoot}} \pagestyle{verbit} \begin{document} \setcounter{page}{1} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{center} {\Large\bf Свойство (Т) Каждана \\[15mm] \small лекция 2: экспандеры} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \\[14mm] {\small Миша Вербицкий } \\[10mm] \tiny 30 июля 2016 \\[20mm] {\tiny\bf Летняя математическая школа "Алгебра и геометрия VI"\\[2mm] 24 - 31 июля, 2016, ЯГПУ, Ярославль, Россия } \end{center} \newpage {\бф\блуе Решетки в группах Ли} \определение {\бф \блуе Группа Ли} есть гладкое многообразие, снабженное групповой структурой, таким образом, что групповые операции $x, y \arrow xy$ и $x\arrow x^{-1}$ суть гладкие отображения. \упражнение Пусть $G$ -- группа Ли, $\Gamma\subset G$ -- дискретная подгруппа, а $\Gamma \backslash G$ -- фактор по левому действию $\Gamma$. {\бф \ред Докажите, что $\Gamma \backslash G$ есть гладкое, хаусдорфово многообразие.} \определение В этих условиях, возьмем левую меру Хаара $\mu$ на $G$. Поскольку отображение $\pi:\; G\arrow \Gamma \backslash G$ -- накрытие, у каждой точки есть окрестность $U$, диффеоморфная шару, такая, что $\pi^{-1}(U)= \Gamma\cdot U$ есть объединение $|\Gamma|$ шаров, диффеоморфных $U$. Определим {\бф\блуе меру Хаара} $\mu_\Gamma$ на $\Gamma \backslash G$ формулой $\mu_\Gamma(U)= \mu(U_1)$, где $U_1$ есть любой из связных прообразов $U$, при условии, что $U_1$ диффеоморфен $U$. \замечание Это то же самое, что {\бф \пурпле определить $\mu_\Gamma$ дифференциальной формой $\eta$ такой, что $\pi^*\eta$ есть форма объема меры Хаара.} \определение Пусть $\Gamma\subset G$ -- дискретная подгруппа группы $G$. Она называется {\бф \блуе решеткой}, если она имеет {\бф \блуе конечный кообъем:} $\mu_\Gamma(\Gamma \backslash G)<\infty$, то есть фактор $G$ по $\Gamma$ имеет конечную меру Хаара. \newpage {\бф\блуе Фундаментальная область} \замечание {\бф \пурпле $\Gamma\subset G$ является решеткой $\Leftrightarrow$ фундаментальная область ее действия на $G$ имеет конечный объем.} \begin{center} \epsfig{file=fund-domain.png,width=0.5\linewidth}\\ {\it\small Фундаментальная область группы $SL(2, \Z)$ действующей на верхней полуплоскости дробно-линейными преобразованиями.} \end{center} \замечание Из этой картинки следует, что {\бф \ред $SL(2, \Z)$ есть решетка в $SL(2, \R)$.} Действительно, фундаментальная область $\Omega$ действия $\Gamma:=SL(2, \Z)$ в плоскости Лобачевского ${\Bbb H}^2=SL(2,\R)/S^1$, нарисованная на картинке, имеет конечный объем. Из этого следует, что фундаментальная область $\Gamma$ на $SL(2,\R)$ (расслоенная над $\Omega$ со слоем $S^1$) тоже имеет конечный объем. \newpage {\бф\блуе Теорема Бореля и Хариш-Чандры} \замечание Можно доказать, что $SL(n,\Z)$ имеет конечный кообъем в $SL(n,\R)$, пользуясь {\бф \блуе теоремой Минковского:} каждое центрально-симметричное выпуклое тело объема $2^n$ содержит точку решетки $\Z^n\subset \R^n$ объема 1. \утверждение Пусть $G$ -- группа Ли, содержащая решетку. {\бф \ред Тогда $G$ унимодулярна.} \доказательство {\бф \пурпле $x\in G$ действует справа на $\Gamma \backslash G$ и умножает меру Хаара на константу $\chi(x)$.} С другой стороны, $(R_x\mu_\Gamma)(\Gamma \backslash G)= \chi(x) \mu_\Gamma(\Gamma \backslash G)$. Поскольку объем многообразия инвариантен относительно диффеоморфизмов, $\chi(x)=1$. \ендпрооф %\замечание %В дальнейшем, все группы Ли предполагаются по умолчанию унимодулярными, %то есть {\бф \пурпле левые меры Хаара суть правые меры, и наоборот.} \теорема {\бф \блуе (Борель и Хариш-Чандра)}\\ Пусть $G\subset GL(n, \R)$ группа Ли, заданная набором полиномиальных уравнений с рациональными коэффициентами. Предположим, что не существует нетривиальных гомоморфизмов из $G$ в $GL(1, \R)$, определенных полиномами с рациональными коэффициентами. {\бф \ред Тогда группа $G_\Z= G\cap SL(n, \Z)$ является решеткой в $G$.} \newpage {\бф\блуе Арифметические решетки и теорема Маргулиса об арифметизации} \определение Пусть $G\subset GL(n)$ -- подгруппа, заданная системой полиномиальных уравнений над $k=\R$ или $k=\C$. Тогда $G$ называется {\бф \блуе алгебраической группой}. Дискретные подгруппы $\Gamma, \Gamma'\subset G$ называются {\бф \блуе соизмеримыми}, если $\Gamma\cap \Gamma'$ имеет конечный индекс в $\Gamma$ и в $\Gamma'$. {\бф \блуе Арифметическая решетка} в алгебраической группе $G$ есть решетка, которая соизмерима с $G\cap GL(n,\Z)$. %\определение %{\бф \блуе Комплексификация} %вещественной алгебраической группы есть группа над $\C$, заданная теми же %полиномиальными уравнениями. \определение Пусть $G$ -- полупростая группа Ли. Ee {\бф \блуе подгруппа Картана} есть максимальная абелева подгруппа $H$, нормализатор которой имеет размерность $\dim H$. Ее {\бф \блуе вещественный ранг} есть размерность фактора $H$ по максимальному компактному подтору. % Ее {\бф \блуе ранг} есть размерность %максимального компактного тора в $G$. {\бф \блуе $\R$-ранг} %вещественной алгебраической группы $G$ есть $\rк(G_\C)- r$, %где $\rк(G_\C)$ -- ранг ее компактификации, а $r$ -- размерность %максимального компактного тора в $G$. \теорема {\бф \блуе (теорема Маргулиса об арифметизации)}\\ Пусть $\Gamma\subset G$ -- решетка в простой алгебраической группе Ли $G$, с вещественным рангом $> 2$. {\бф \ред Тогда $\Gamma$ сопряжена арифметической решетке.} \newpage {\бф\блуе Унитарные представления} \определение \определение {\бф \блуе Топологическая группа} есть группа $G$, снабженная топологией, таким образом, что операции умножения и взятия обратного непрерывны. {\бф \пурпле Топология на $G$ предполагается метризуемой,} в частности -- хаусдорфовой. \определение {\бф \блуе Унитарное представление} группы $G$ есть гомоморфизм из $G$ в группу линейных изометрий гильбертова пространства $H$ такой, что функция $h \arrow g(h)$ непрерывна как функция $g$ для любого $h\in H$. \определение {\бф \блуе Неприводимое представление} есть представление $G$ в гильбертовом пространстве $H$ такое, что $H$ не содержит {\бф \блуе подпредставлений}, то есть замкнутых, $G$-инвариантных подпространств. \newpage {\бф\блуе Свойство Каждана (Т)} \определение Напомню, что {\бф\блуе диаметр} метрического пространства $M$ есть $\diam(M):= \sup_{x,y\in M} d(x,y)$ Пусть $H$ есть унитарное представление локально компактной группы $G$, а $\{\xi_i\}\subset H$ -- последовательность единичных векторов. Она называется {\бф \блуе почти инвариантной}, если для каждого компакта $K\subset G$, имеем $\lim_i\diam(K\xi_i)=0$ \определение Группа $G$ {\бф \блуе удовлетворяет свойству Каждана (Т)}, если любое унитарное представление $G$, содержащее почти инвариантные векторы, содержит $G$-инвариантный вектор. Основные теоремы из работы Каждана 1967 года. \теорема Пусть $G$ -- группа Ли, а $\Gamma\subset G$ -- решетка, то есть дискретная подгруппа конечного кообъема. Тогда {\бф \ред свойство Каждана (Т) для $G$ равносильно свойству (Т) для $\Gamma$.} (будет сегодня) \теорема {\бф \ред Группа $SL(n,\R)$ обладает свойством Каждана (Т) для каждого $n>2$ и не обладает им для $n=2$.} (завтра) %\замечание В более общей формулировке, теорема Каждана утверждает, что решетки ранга %$\geq 2$ обладают свойством (Т), следовательно, конечно-порождены. %Для решеток ранга $\geq 3$, это утверждение легко следует из %арифметизации Маргулиса, а для ранга 2 это единственное доказательство \newpage {\бф\блуе Свойство Каждана (Т) и почти инвариантные векторы} \определение Пусть $\tilde G$ -- множество классов эквивалентности унитарных представлений $G$, $\rho:\; G \arrow U(H)$ -- ее унитарное представление а $K\subset G$ какой-то компакт. Обозначим за $W(H, K,\epsilon)$ все представления $\rho:\; G \arrow U(H')$ такие, что для каких-то единичных векторов $v\in H, v'\in H'$, имеем $\sup_{g\in K} \left||g(v)-v| - |v'-g(v')|\right|<\epsilon$. Топология на $\tilde G$, заданная предбазой из всех $W(H, K,\epsilon)$, называется {\бф \блуе топология Фелла}. \замечание {\бф \ред Эта топология нехаусдорфова.} Действительно, {\бф \пурпле каждое подпредставление $H_1\subset H$ содержится в замыкании $H$.} \определение Локально компактная группа $G$ {\бф \блуе обладает свойством Каждана (Т)}, если любое представление $G$, в замыкании которого лежит тривиальное представление ${\Bbb I}_G$, содержит неподвижный вектор. \замечание Пусть $G$ получена счетным объединением компактов {\бф \блуе ("$\sigma$-компактна")}. {\бф \пурпле Тогда это равносильно определению через почти инвариантные векторы.} Действительно, пусть в замыкании представления $H$ лежит ${\Bbb I}_G$, а $...\subset K_i\subset K_{i+1} \subset ...$ -- последовательность компактов, исчерпывающая $G$, и содержащая 1. Обозначим за $\xi_i$ единичный вектор из $H$ такой, что $\diam (K_i \cdot \xi_i) < \frac 1 {2^i}$. Тогда $\{\xi_i\}$ -- почти инвариантные векторы. Наоборот, если есть почти инвариантные векторы $\{\xi_i\}\subset H$, соответствующие им функции $g\arrow |g(\xi_i)-\xi|$ сходятся к нулю на компактах. \newpage {\бф\блуе Проекции почти инвариантных векторов} {\бф \греен Предложение 1:} Пусть $G$ -- группа со свойством (Т), $H$ ее представление, а $\{\xi_i\}\subset H$ -- почти инвариантная последовательность. Рассмотрим ортогональную проекцию $\Pi_{inv}:\; H \arrow H^G$ на пространство $G$-инвариантов. {\бф \ред Тогда $\lim_i |\xi_i-\Pi_{inv}(\xi_i)|=0$.} \доказательство Вектор $a_i:=\xi_i-\Pi_{inv}(\xi_i)$ лежит в представлении, не имеющем почти инвариантных векторов, значит, существует $g\in G$ такой, что \[ \lim\sup_i |a_i|^{-1} |g(a_i)-a_i|>0. \ \ \ \ (*) \] В силу почти инвариантности, \[ \lim_i |g(\xi_i)-\xi_i|=0,\ \ \ \ (**) \] a $\xi_i = a_i + \text{$G$-инвариантный вектор}$. Сравнивая (*) и (**), получаем, что $\lim_i |a_i|=0$. \newpage {\бф\блуе Свойство Каждана (Т) для решеток (1)} \теорема Пусть $G$ -- группа Ли, а $\Gamma\subset G$ -- решетка, то есть дискретная подгруппа конечного кообъема. Тогда {\бф \ред свойство Каждана (Т) для $G$ равносильно свойству (Т) для $\Gamma$.} {\бф \греен Доказательство импликации "(Т) для $\Gamma$" $\Rightarrow$ "(Т) для $G$":}\\ Пусть $\{\xi_i\}$ -- почти инвариантные векторы в $H$. Обозначим за $H^\Gamma$ пространство $\Gamma$-инвариантных векторов. В силу Предложения 1, проекция $\Pi^\Gamma$ на $H^\Gamma$ удовлетворяет $\lim_i |\xi_i-\Pi_{inv}(\xi_i)|=0$: в $H^\Gamma$ существуют почти инвариантные векторы. Значит, достаточно доказать, что $H^\Gamma$ содержит $G$-инвариантные векторы, и {\бф \пурпле можно без ограничения общности предположить, что $\Gamma$ действует на $H$ тривиально.} {\бф \греен Шаг 2:} Обозначим за $\mu$ вероятностную меру на $G/\Gamma$, согласованную с мерой Хаара на $G$. Пусть $K\subset G$ -- компактное подмножество такое, что его образ в $G/\Gamma$ имеет меру $1-\epsilon$. Рассмотрим отображение $ G/\Gamma\arrow H$, переводящее $g$ в $g(\xi_i)$. Это непрерывная, ограниченная единицей функция на $G/\Gamma$, причем $\lim \sup_{g\in K} |g(\xi_i)-\xi_i|=0$. Из этого следует, что $\int_{g\in G/\Gamma} |g(\xi_i)-\xi_i|\mu< 2\epsilon$ для $i\gg0$. Обозначим за $\xi'$ усредненный вектор $\int_{g\in G/\Gamma} g(\xi_i)$, и пусть $\Xi:= \xi'|\xi'|^{-1}$. По построению, {\бф \пурпле $\Xi$ -- $G$-инвариантный вектор, который удовлетворяет $|\Xi|> 1-2\epsilon$. } \ендпрооф \newpage {\бф\блуе Индуцированные представления} \newcommand{\Ind}{\operatorname{Ind}} \определение Пусть $\Gamma\subset G$ дискретная подгруппа в $G$, а $V$ -- представление $\Gamma$. Рассмотрим локальную систему (оно же: плоское векторное расслоение, оно же: локально тривиальный пучок) ${\cal B}$ на $G/\Gamma$ со слоем $V$ с монодромией, определенной $\Gamma$. Сечения ${\cal B}$ суть функции $f:\; G \arrow V$ удовлетворяющие $f(\gamma g) = \gamma f(g)$ для любых $g\in G$, $\gamma\in \Gamma$. На таких функциях действует $G$ по формуле $g_1(f)(g):= f(g g^{-1}_1)$. Пространство $L^2$-интегрируемых сечений $f:\; G/\Gamma \arrow {\cal B}$, удовлетворяющих $f(\gamma g) = \gamma f(g)$, называется {\бф \блуе индуцированным представлением}, и обозначается как \\ $\Ind_\Gamma^G(V)$. \пример {\бф \пурпле Если $\Gamma$ тривиальна, а $V$ одномерно, то $\Ind_\Gamma^G(V)$ есть регулярное представление.} \замечание Пусть $\Gamma\subset G$ -- решетка в $G$, $\mu$ -- вероятностная мера на $G/\Gamma$, согласованная с мерой Хаара, а $v\in \Ind_\Gamma^G(V)$ -- $G$-инвариантный вектор, заданный отображением $G\arrow V$. Поскольку $v$ $\Gamma$-инвариантный, его можно рассматривать как отображение $v:\; G/\Gamma\arrow V$, которое инвариантно относительно действия $G$ на $V$-значных функциях на $G/\Gamma$. Значит, $\int_{g\in G/\Gamma} v(g)$ есть $\Gamma$-инвариантный вектор в $V$. {\бф \пурпле Мы построили биекцию между $\Gamma$-инвариантными векторами в $V$ и $G$-инвариантными векторами в $\Ind_\Gamma^G(V)$.} \newpage {\бф\блуе Свойство Каждана (Т) для решеток (2)} \теорема Пусть $G$ -- группа Ли, а $\Gamma\subset G$ -- решетка, то есть дискретная подгруппа конечного кообъема. Тогда {\бф \ред свойство Каждана (Т) для $G$ равносильно свойству (Т) для $\Gamma$.} {\бф \греен Доказательство импликации "(Т) для $\Gamma$" $\Leftarrow$ "(Т) для $G$":}\\ {\бф \греен Шаг 1:} Пусть $\{\xi_i\}$ -- почти инвариантные векторы в унитарном представлении $\Gamma$, обозначенном как $V$, $\mu$ -- вероятностная мера Хаара на $G/\Gamma$, а $O\subset G$ -- фундаментальная область действия $\Gamma$. Зафиксируем отображение $\psi_i:\; G=\bigcup_{\gamma\in \Gamma} \gamma(O)\arrow V$, переводящее $x\in \gamma(O)$ в $\gamma(\xi_i)$. По построению, $\psi_i \in \Ind_\Gamma^G(V)$, {\бф \греен Шаг 2:} Докажем, что $\psi_i$ -- почти инвариантные векторы. Рассмотрим компакт $K\subset G$, лежащий в $\bigcup_{j=1}^n \gamma_j(O)$. Обозначим за $K_0$ множество $\bigcup_{j=1}^n \gamma_j\subset \Gamma$. Поскольку $\diam K \cdot \psi_i = \diam K_0\cdot \xi_i$, {\бф \пурпле мы имеем $\lim_i(\diam K \cdot \psi_i) =0$, то есть $\{\psi_i\}$ почти инвариантны.} {\бф \греен Шаг 3:} Поскольку $G$ обладает свойством (Т), а $\Ind_\Gamma^G(V)$ содержит почти инвариантные векторы, $\Ind_\Gamma^G(V)$ содержит инвариантные векторы. {\бф \пурпле В силу предыдущего замечания, из этого следует, что $V$ содержит инвариантные векторы.} \ендпрооф \невпаге {\бф \блуе Константа Чигера} \определение Пусть $\Gamma$ это граф, а $K\subset \Gamma$ набор вершин. Обозначим за $\6K$ все вершины, соединенные с $K$, но не лежащие в $K$. Множество $\6K$ называется {\бф\блуе границей $K$}. {\бф \блуе Константа Чигера}, она же {\бф \блуе изопериметрическая константа} графа $\Gamma$ есть $h(\Gamma):=\min\frac{|\6K|}{|K|}$ по всем подмножествам вершин $K\subset \Gamma$ с $|K|\leq \frac 1 2 |\Gamma|$. \определение Граф называется {\бф \блуе $k$-регулярным}, если с каждой вершиной соединено ровно $k$ вершин. \определение {\бф \блуе $\epsilon$-экспандер} есть регулярный граф, удовлетворяющий $h(\Gamma) \geq \epsilon$. {\em A. N. Kolmogorov and Y. M. Barzdin, "On the realization of networks in three-dimensional space" in Selected Works of Kolmogorov, vol. 3, Kluwer, Dordrecht, 1993, 194-202. M. S. Pinsker, "On the complexity of a concentrator'', Proceedings of the Seventh International Teletraffic Congress (Stockholm, 1973), pp. 318/1-318/4, Paper No. 318. } \невпаге {\бф \блуе M. S. Pinsker} \begin{center} \epsfig{file=pinsker.jpg,width=0.35\linewidth}\\[4mm] {\small \it Марк Семенович Пинскер \\ (24 апреля 1925 - 23 декабря 2003) \\ 1976, Ленинград} \end{center} \невпаге {\бф \блуе Оператор смежности} Пусть $\Gamma$ -- граф, а $V(\Gamma)$ -- векторное пространство, свободно порожденное его вершинами. Мы будем рассматривать $V(\Gamma)$ как пространство функций на вершинах. На $V(\Gamma)$ определено скалярное произведение (сумма квадратов значений на всех вершинах). \определение {\бф \блуе Оператор смежности} графа $\Gamma$ переводит вектор $v\in V(\Gamma)$, соответствующий вершине $v$, в сумму всех вершин, связанных с $v$ ребрами. Соответствующая матрица называется {\бф \блуе матрицой смежности} графа. \замечание Основное применение графа-экспандера в том, что его матрица смежности перемешивающая, то есть соответствующий оператор (который может быть представлен как случайное блуждание по графу) {\бф \пурпле "очень быстро" приводит каждую функцию к постоянной.} \невпаге {\бф \блуе Спектральный зазор графа-экспандера} \замечание Пусть $\Gamma$ -- $k$-регулярный граф, а $A:\; V(\Gamma)\arrow V(\Gamma)$ его матрица смежности. Легко видеть, что $A$ -- самосопряженный оператор. Упорядочим его собственные значения по убыванию: $\lambda_1, \lambda_2, ..., \lambda_{|\Gamma|}$. {\бф \блуе Тогда $\lambda_1=k$, соответствующее собственное пространство -- константы, а $\lambda_2 < k$.} \определение {\бф \блуе Спектральный зазор} графа есть число $k-\lambda_2$. \теорема {\бф \блуе (неравенство Чигера для графа; Tanner, Alon, Milman)}\\ Пусть $\Gamma$ -- $k$-регулярный граф, а $h$ -- его константа Чигера. {\бф \ред Тогда \[ \frac{k-\lambda_2}2 \leq h \leq \sqrt{2k(k-\lambda_2)}.\]} \невпаге {\бф \блуе Оценка спектрального зазора} \замечание Поскольку $A$ самосопряжен, {\бф \пурпле собственные пространства, соответствующе $\lambda_i, i>0$, ортогональны постоянным функциям,} то есть их среднее равно 0. \замечание Довольно легко оценить константу Чигера графа в терминах спектрального зазора $k-\lambda_1$. Пусть $K\subset \Gamma$ -- набор вершин, а $f$ функция, принимающая на $K$ значение $\frac{1}{|K|}$, а на его дополнении значение $-\frac{1}{|\Gamma|-|K|}$. Поскольку $f$ ортогонально постоянной, $(A(f),f)\leq \lambda_2 |f|^2$. С другой стороны, вне $R:=\6K\cup \6(\Gamma\backslash K)$, $A(f)=kf$, что дает \[ (A(f),f) \geq k|f|^2- |R||K|^{-2}. \] Деля на $|f|^2=|K|^{-1}+(|\Gamma|-|K|)^{-1}$, получаем \[ \lambda_2 =\sup_{f\bot \const} (A(f),f) |f|^{-2}\geq k- |R||K|^{-2} |f|^{-2}\geq k- 2 |R||K|^{-1}\geq k - 2 h(\Gamma) \] Это дает первое из неравенств. Второе остается в качестве (трудного) упражнения. \невпаге {\бф \блуе Случайные графы} \определение Пусть $\Gamma$ -- множество из $n$ элементов. Мы соединяем каждую точку $\gamma$ с $k$ вершинами случайным образом (выбор каждой из точек $\Gamma$ равновероятен). Полученный граф называется {\бф \блуе случайный регулярный граф с $n$ вершинами и $k$ ребрами}. {\бф \греен Посчитаем вероятность того, что $\Gamma$ $\epsilon$-экспандер.} Пусть $K\subset \Gamma$ множество вершин с $|K|<1/2|\Gamma|$. Граф не является экспандером, если все соседи $K$ лежат в множестве $T$, состоящем из $\leq(1+\epsilon)|K|$ вершин. Вероятность того, что для всех вершин из $K$ концы всех ребер лежат в $T$, равна $\left(\frac{|T|}n\right)^{|K|}$. Мы получили такое \утверждение {\бф \ред Вероятность $\nu(n,k,\epsilon)$ того, что случайный граф с $n$ вершинами валентности $k$ не $\epsilon$-экспандер, есть $\sum_{K, T}\left(\frac{|T|}n\right)^{k|K|}$,} где суммирование происходит по всем $K\subset \Gamma$ с $|K|<1/2|\Gamma|$ и $T\subset \Gamma$ с $|T|\leq (1+\epsilon)|K|$. \невпаге {\бф \блуе Случайные графы (2)} \утверждение {\бф \ред Вероятность $\nu(n,k,\epsilon)$ того, что случайный граф не экспандер, есть $\sum_{K, T}\left(\frac{|T|}n\right)^{k|K|}$,} где суммирование происходит по всем $K\subset \Gamma$ с $|K|<1/2|\Gamma|$ и $T\subset \Gamma$ с $|T|\leq (1+\epsilon)|K|$. Это дает \[ \nu(n,k,\epsilon) \leq \sum_{i=1}^{n/2} C_{n}^{s} C_{n}^{(1+\epsilon)s} \left(\frac{(1+\epsilon)s}n\right)^{ks} \] оценим по формуле Стирлинга $C_{n}^{s} <\left(\frac{ne}{s}\right)^s$. Получим \begin{multline*} \nu(n,k,\epsilon) < \sum_{s=1}^{n/2} \left(\frac{ne}{s}\right)^s \left(\frac{ne}{{(1+\epsilon)s}}\right)^{(1+\epsilon)s} \left(\frac{(1+\epsilon)s}n\right)^{ks} = \\ = \sum_{s=1}^{n/2} \left[\left(\frac{ne}{s}\right)\left(\frac{ne}{(1+\epsilon)s}\right)^{(1+\epsilon)} \left(\frac{(1+\epsilon)s}n\right)^k\right]^s = \\ = \sum_{s=1}^{n/2} \left[\frac {e^{(2+\epsilon)}}{(1+\epsilon)^{1+\epsilon}} (1+\epsilon)^k \left(\frac{s}{n}\right)^{k-(2+\epsilon)}\right]^s = \ \sum_{s=1}^{n/2}\left[e^{(2+\epsilon)}(1+\epsilon)^{k-1-\epsilon}\left(\frac{s}{n}\right)^{k-2-\epsilon}\right]^s \end{multline*} \невпаге {\бф \блуе Случайные графы (3)} Вероятность $\nu(n,k,\epsilon)$ того, что случайный граф не экспандер: \[ \nu(n,k,\epsilon) \leq \sum_{s=1}^{n/2}\left[e^{(2+\epsilon)}(1+\epsilon)^{k-1-\epsilon}\left(\frac{s}{n}\right)^{k-2-\epsilon}\right]^s \] Поскольку $n\geq 2s$, выражение в квадратных скобках оценивается как \[ e^{(2+\epsilon)}(1+\epsilon)^{k-1-\epsilon}\left(\frac{s}{n}\right)^{k-2-\epsilon} \leq 2e^{(2+\epsilon)}\left(\frac{(1+\epsilon)}{2}\right)^{k} \] Для любого $\epsilon < 1$ и $k \gg 0$ это число меньше $1/2$, соответственно сумма в выражении для $\nu(n,k,\epsilon)$ меньше 1. \следствие {\бф \блуе (теорема Пинскера)} \\ Для каждого $\epsilon <1$, {\бф \ред случайный регулярный граф валентности $k > k(\epsilon)$ с положительной вероятностью есть граф-экспандер.} \newpage {\bf \blue Граф Кэли} \определение {\бф \блуе Набор образующих} группы $G$ есть множество элементов $S$, мультипликативно порождающих $G$. {\бф \ред В дальнейшем, мы будем всегда предполагать, что $s\in S \Leftrightarrow s^{-1}\in S$.} \определение Пусть $G$ -- группа, $\{s_i\}$ -- набор образующих. {\бф \блуе Граф Кэли} пары $(G, \{s_i\})$ есть граф, вершины которого -- элементы $G$, а ребра соединяют точки вида $g$ и $gs_i$. Полагая длину ребер графа равной 1, мы {\бф \ред определяем граф Кэли как метрическое пространство с внутренней метрикой.} \пример Граф Кэли для $\Z^n$ с обычным набором образующих есть кубическая решетка. \begin{center} \epsfig{file=Cayley_graph_Z^2.png,width=0.38\linewidth} \end{center} \newpage {\bf \blue Граф Кэли для свободной группы} \пример Граф Кэли для свободной группы -- регулярное дерево \begin{center} \epsfig{file=free-group-Cayley-2.png,width=0.45\linewidth}\\[5mm] {\ем \бф\small Граф Кэли свободной группы ${\Bbb F}_2$ с образующими $a$, $b$, $a^{-1}$, $b^{-1}$.} \end{center} \newpage {\bf \blue Граф Кэли для $\Z/2\Z * \Z/3\Z$} \begin{center} \epsfig{file=Kelli_graph_free_prod.png,width=0.6\linewidth}\\[5mm] {\ем \бф\small Граф Кэли для $\Z/2\Z * \Z/3\Z$.} \end{center} \newpage {\bf \blue Граф Кэли для группы $S^3$} \begin{center} \epsfig{file=trunspi.png,width=0.4\linewidth}\\[5mm] {\ем \бф\small Граф Кэли для $S^3$.} \end{center} Группа $S^3=\langle k, r\ |\ k^2=r^3=(kr)^3=1\rangle$ задается образующими $k$ (красная), $r$ (черная), и соотношениями $k^2=r^3=(kr)^3=1$. \newpage {\bf \blue Граф Кэли для группы $\langle k, r\ |\ k^2=r^3=(kr)^6=1\rangle$} \begin{center} \epsfig{file=trunhex.png,width=0.9\linewidth}\\[5mm] {\ем \бф\small Граф Кэли для группы, заданной образующими $k$ (красная), $r$ (черная), и соотношениями $k^2=r^3=(kr)^6=1$.} \end{center} \невпаге {\бф \блуе Константа Каждана} \newcommand{\Kaz}{\operatorname{Kaz}} \определение Пусть $G$ -- топологическая группа, а $S$ -- компактное подмножество $G$. {\бф \блуе Константа Каждана} $\Kaz(G,S)$ есть супремум $\epsilon$ таких, что для любого унитарного представления $G$, не содержащего $G$-инвариантных векторов, найдется $s\in S$ такое, что для любого единичного вектора $v$ имеет место $|s(v) -v| > \epsilon$. \замечание {\бф \пурпле Свойство Каждана (Т) равносильно тому, что \\ $\Kaz(G,S)>0$ для какого-то компакта $S\subset G$.} \невпаге {\бф \блуе Константа Каждана и экспандеры} \утверждение Пусть $G$ -- конечная группа, $\Sigma$ набор $k$ образующих, $\Gamma$ ее граф Кэли, а $h(\Gamma)$ -- константа Чигера. {\бф \ред Тогда существует положительные функции $f_1$ и $f_2:\; \R^{>0} \arrow \R^{>0}$ (не зависящие от $\Gamma$) такие, что $h(\Gamma) \geq f_1(\Kaz(\Gamma, \Sigma))$ и $\Kaz(\Gamma, \Sigma) \geq f_2(h(\Gamma))$.} \дшаг Пусть $H$ -- пространство функций $f:\; \Gamma\arrow \C$, среднее которых нулевое: $\sum_{s\in \Gamma} f(s)=0$. Оценка константы Каждана делается через спектральный зазор $k-\lambda_2$, определенный раньше. Для любой функции $f\in H$, имеем $A(F)=\sum_{s\in \Sigma} s(f)$, а коль скоро $|A(f)| \leq (k-\lambda_2)$ для любой единичной функции $f\in H$, имеем $(k-\lambda_2) |f| \leq |A(f)-f| \leq \sum |s(f)-f|$. {\бф \пурпле Значит, для какого-то $s\in \Sigma$, имеем $|s(f)-f|\geq k^{-1}(k-\lambda_2)|f|$, что дает $\Kaz(G,\Sigma) \geq k^{-1}(k-\lambda_2)$.} С другой стороны, число $k-\lambda_2$ оценивает $h(G)$, как объяснялось выше. \невпаге {\бф \блуе Константа Каждана и экспандеры (2)} \утверждение Пусть $G$ -- конечная группа, $\Sigma$ набор $k$ образующих, $\Gamma$ ее граф Кэли, а $h(\Gamma)$ -- константа Чигера. {\бф \ред Тогда существуют положительные функции $f_1$ и $f_2:\; \R^{>0} \arrow \R^{>0}$ (не зависящие от $\Gamma$) такие, что $h(\Gamma) \geq f_1(\Kaz(\Gamma, \Sigma))$ и $\Kaz(\Gamma, \Sigma) \geq f_2(h(\Gamma))$.} {\бф \греен Шаг 2:} Теперь оценим $h(G)$ через $\Kaz(G, \Sigma)$. Возьмем $K\subset \Gamma$, $|K|\leq 1/2 |\Gamma|$, и пусть $f\in H$ -- функция, принимающая на $K$ значение $\frac{1}{|K|}$, а на его дополнении значение $-\frac{1}{|\Gamma|-|K|}$. Тогда функция $f-s(f)$ зануляется вне $R:=\6K\cup\6(\Gamma\backslash K)$, и ограничена $2|K|^{-1}$ на $R$, что дает $\sqrt{2 |R|}|K|^{-1} \geq |f-s(f)|$. С другой стороны, \[ |f-s(f)||f|^{-1} \geq \Kaz(G,\Sigma) \] для подходящего $s\in \Sigma$. Поскольку $|f|\geq \sqrt {|K|^{-1}}$, имеем \[ \Kaz(G,\Sigma)\leq \sqrt{2 \frac{|R|}{|K|}} \leq 2\sqrt{h(G)}. \] \ендпрооф \невпаге {\бф \блуе Теорема Маргулиса} \теорема {\бф \блуе (Маргулис)} Пусть $G$ -- дискретная группа, обладающая свойством (Т), а $G_0\supset G_1 \supset ... $ -- монотонная последовательность подгрупп конечного индекса, такая, что $\bigcap G_i=\{e\}$. Выберем набор образующих в $G$, и пусть $\Gamma_i$ -- графы Кэли для $G/G_i$. {\бф \ред Тогда все $\Gamma_i$ суть графы-экспандеры для какого-то $\epsilon >0$.} \доказательство Пусть $\Sigma$ -- набор образующих для $G$. Поскольку все представления $G/G_i$ являются представлениями $G$, имеем $\Kaz(G, \Sigma) \leq \Kaz(G/G_i, \Sigma)$. Значит, $h(\Gamma_i)$ ограничивается снизу через $\Kaz(G, \Sigma)$ и $|\Sigma|$. \ендпрооф\\[-8mm] \begin{center} \epsfig{file=margulis.jpg,width=0.44\linewidth}\\[4mm] {\ем \small Григорий Александрович Маргулис (р. 24 февраля 1946, Москва)} \end{center} \end{document}