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