% $Header: /cvsroot/latex-beamer/latex-beamer/solutions/generic-talks/generic-ornate-15min-45min.en.tex,v 1.4 2004/10/07 20:53:08 tantau Exp $
% sizes tiny scriptsize footnotesize small normalsize large Large
% LARGE huge Huge
 %\documentclass[handout]{beamer}
\documentclass{beamer}
\usepackage{graphicx}
\usepackage{txfonts} % for \leftsquigarrow
% This file is a solution template for:

% - Giving a talk on some subject.
% - The talk is between 15min and 45min long.
% - Style is ornate.

\mode<presentation> % in this mode a series of slides reveals more and
                    % more, bit by bit. This is what you'd like for
                    % the slides you present.
% \mode<handout> % handout mode prints all the slowly-revealed parts
% on one slide. This provides a shorter output (maybe 15 slides
% instead of 75?) that is much easier and eco-friendlier for your
% preparation.
{
  \usetheme{Goettingen}
  % or ...

%  \setbeamercovered{transparent}
  % or whatever (possibly just delete it)
}

\usepackage[english]{babel}
% or whatever

\usepackage[latin1]{inputenc}
% or whatever

\usepackage{times}
\usepackage[T1]{fontenc}
% Or whatever. Note that the encoding and the font should match. If T1
% does not look nice, try deleting the line with the fontenc.
\newtheorem{proposition}{Proposition}
\newcommand{\Hom}{\mathop{\hbox {\rm Hom}}\nolimits}
\title %[Short Paper Title] % (optional, use only with long paper titles)
{Inflatable mathematics}
% \subtitle
% {Presentation Subtitle} % (optional)

\author[SRuff, DVogan] % (optional, use only with lots of authors)
{Susan Ruff  \and David Vogan}

\institute[Course 18] 

\date{18.821e \\ Halloween, 2016} % (optional)

\beamerdefaultoverlayspecification{<+->}

\begin{document}

\begin{frame}
  \titlepage % beamer generates this from the info above
\end{frame}

\begin{frame} % your choice whether this is helpful
  \frametitle{Outline} 
  \tableofcontents
  % You might wish to add the option [pausesections]
\end{frame}

% \section[shorttitle]{Longer more descriptive title}
% the short one may have to fit in a navigation bar on the side
\section[Introduction]{Building up from simple pieces}

\begin{frame}
  \frametitle{The stars of the show}
  \begin{itemize}
    \item[] \textbf{Camille Jordan} (1838--1922)\qquad
      \raisebox{-1cm}{\includegraphics[height=2.2cm]{s2m/Jordan_4.jpeg}}
      
      % see how easy it is to use graphics!
      
    \item[] \textbf{Hannibal Schubert} (1848--1911)\qquad
      \raisebox{-1cm}{\includegraphics[height=2.2cm]{s2m/Hannibal_Schubert.jpg}} 
  \item[] \textbf{Fran\c cois Bruhat} (1929--2007)\qquad 
    \raisebox{-1cm}{\includegraphics[height=2.2cm]{s2m/francois_bruhat.jpg}}
    
    \end{itemize}
\end{frame}




\begin{frame}
  \frametitle{The main idea}
 % \framesubtitle{Subtitles are optional.}
  % - A title should summarize the slide in an understandable fashion
  %   for anyone who does not follow everything on the slide itself.

  \begin{itemize}
    %items in a list are automatically added one slide at a time: this
    % is an easy way to control the flow of your presentation.
    
    % \item[]\vskip -\baselineskip % including this as your first item
    % means that the first slide is JUST the title, not the title and
    % the first item. Sometimes you want that, sometimes you don't.

  \item[] Begin with \alert{linear algebra}: solving systems of linear
  equations by Gaussian elimination.  
\item[] Idea: \alert{reduce number of coordinates by one.} 
\item[] Relate to \alert{geometry}: arranging lines and planes.
\item[] Idea: \alert{reduce to geometry of one dimension less.} 
\item[]\only<1-4>{\vskip 1.1cm\ \\}
%  \vskip -.3cm 
  \only<5->{\includegraphics[height=2cm]{s2m/s100.jpg}}\ \ 
  \only<6->{\includegraphics[height=2cm]{s2m/s75m25.jpg}}\ \ 
  \only<7->{\includegraphics[height=2cm]{s2m/s50m50.jpg}}\ \ 
  \only<8->{\includegraphics[height=2cm]{s2m/s25m75.jpg}}\ \ 
  \only<9->{\includegraphics[height=2cm]{s2m/m100.jpg}}\ \

  % if I had wanted these pictures on different lines, then \itemize
  % could have displayed them one slide at a time. Since they are all
  % on the same line, that would have been more complicated (still
  % possible!) with \itemize
  
\item[] \vskip .3cm \only<10->{Use same idea for more complicated geometry.}

\end{itemize}
\end{frame}

\section[Gaussian elimination]{Ideas from linear algebra}

\begin{frame}
  \frametitle{Gaussian elimination: easy cases}
  \begin{itemize}
  \item[] System of three equations in three unknowns is

    % this is one big system of equations, with different pieces
    % written in different cells of the matrix. I uncovered the ones I
    % wanted on the slides I wanted.
    
    \begin{equation*} \begin{matrix} 
        a_{11}x_1 &\uncover<1,4->{+}& \uncover<1,4->{a_{12}x_2}
        &\uncover<1>{+}& \uncover<1>{a_{13}x_3} &=& c_1 \\ 
        \uncover<1,3->{a_{21}\uncover<5->{'}x_1} &\uncover<1,3-4>{+}&
        \uncover<1-4>{a_{22}x_2} 
        &\uncover<1>{+}& 
        \uncover<1>{a_{23}x_3} &=& c_2\uncover<5->{'} \\ 
        \uncover<1,3->{a_{31}x_1} &\uncover<1,3->{+}&
        \uncover<1,3->{a_{32}x_2} &\uncover<1,3->{+}& a_{33}x_3 &=& c_3 \\
      \end{matrix} \end{equation*}
    {\small I'll assume always the system has just one solution.}
    \item[] Easiest case is diagonal system: \alert{divide each equation by a
      constant} to solve.
    \item[] Next easiest is lower triangular: \alert{add multiples of some
      eqns to later ones} to make diagonal.
  \item[] Suppose lower triangular EXCEPT one coefficient $a_{12} \ne
    0$. \alert{Add multiple of 1st eqn to second} to get\dots
  \item[] This system is nearly lower triangular, except
    that the first two equations are interchanged.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Gaussian elimination: typical case}
  \begin{itemize}
  \item[] ``Typical'' system of equations in three unknowns is
    \begin{equation*} \begin{matrix} 
        a_{11}x_1 &+& a_{12}x_2  &+& a_{13}x_3 &=& c_1 \\ 
        a_{21}\uncover<2->{'}x_1 &+& a_{22}\uncover<2->{'}x_2  &\uncover<1>{+}& 
        \uncover<1>{a_{23}x_3} &=& c_2\uncover<2->{'} \\ 
        a_{31}\uncover<2->{'}\uncover<3->{'}x_1 &\uncover<1-2>{+}&
        \uncover<1-2>{a_{32}\uncover<2->{'}x_2} &\uncover<1>{+}&
        \uncover<1>{a_{33}x_3} &=& c_3\uncover<2->{'}\uncover<3->{'} \\
      \end{matrix} \end{equation*}
    where ``typically'' $a_{13} \ne 0$. \alert{Add multiple of 1st equation to
      each later eqn} to get\dots
    \item[] Now ``typically'' $a_{22}' \ne 0$. \alert{Add multiple of
        2nd eqn to last} to get\dots
    \item[] Again this last system is nearly lower triangular, except
      that order of the three eqns is reversed.
\item[] To say what happens in general, use matrix notation \alert{$A{\mathbf
    x} = \mathbf{c}$}. Here $A = (a_{ij})$ is $n\times n$ coeff matrix,
  and ${\mathbf x} = (x_j)$ is the column vector of $n$ unknowns.
  \end{itemize}
\end{frame}

% I include this slide just to show how a theorem can be displayed

\begin{frame}
  \frametitle{Theorem for Gaussian elimination}
  \begin{theorem}
  \begin{itemize}
  \item[] Suppose $A$ is an invertible $n\times n$
    matrix, and ${\mathbf c}$ is an $n$-tuple of constants. Consider
    the system of $n$ equations in $n$ unknowns
    $$A{\mathbf x} = {\mathbf c}.$$
  \item[]   Using the two operations
    \begin{enumerate}
    \item dividing an equation by a non-zero constant, and
    \item adding a multiple of one equation to a later one,
    \end{enumerate}
  \item[] we can transform this system into a new one
    $$A'{\mathbf x} = {\mathbf c'}.$$
  \item[] The new system, after reordering the equations, is lower
    triangular. 
  \end{itemize}
  \end{theorem}

\end{frame}

\section[Calculating with(out) Schubert varieties]{Calculating
  with(out) Schubert varieties} 
\begin{frame}
\frametitle{Mathematics on a need-to-know basis}
\begin{itemize}
\item[] To compute with Schubert varieties, need only
  \alert{arrangement of blue and red arrows}, describing how small
  Schubert varieties are inflated:
\item[] \footnotesize
$$\begin{matrix}
&&  (321) && \\%[.3cm]
&{\color{blue}\nearrow} &&{\color{red} \nwarrow} &\\%[.2cm] 
(312) &&&& (231) \\%[.3cm]
{\color{red}\uparrow} &&&& {\color{blue}\uparrow} \\%[.2cm]
 (213) && &&(132) \\%[.2cm]
&{\color{blue}\nwarrow} &&{\color{red}\nearrow} &\\%[.2cm]
&& (123) && \\
\end{matrix}$$
\item[]\small Permutations recorded which rows had
  pivots in Gaussian elimination. Now they're just
  symbols.
\item[] \small Rules for making diagram:
\begin{enumerate}
\item \small One entry for each permutation of $\{1, 2, 3\}$.
\item \small Exchange $1\ldots 2$: blue arrow up.
\item \small Exchange $2\ldots 3$: red arrow up.
\end{enumerate}
\end{itemize}
\end{frame}

% In the next frame I imported a picture made by some graph software

\begin{frame}
\frametitle{As many dimensions as you want}
\begin{tabular}{lc}
\begin{minipage}{5cm}
\begin{itemize}
\item[] \small Rules in $n$ dimensions:
\begin{enumerate}
\item  \footnotesize One entry for each permutation of $\{1, 2,\ldots, n\}$.
\item  \footnotesize Exchange $i \ldots i+1$: arrow up of color $i$.
\end{enumerate}
\item[] \small \alert{Counting problems in this picture}
  $\leftrightsquigarrow$ \alert{geometry of Schubert varieties.}
\item[] \small There are \alert{lots} of counting games to play\dots 
\end{itemize}
\end{minipage}&
\begin{minipage}{4cm}
\includegraphics[width=4cm]{s2m/S4.jpg}
\end{minipage}\end{tabular}
\begin{itemize}
\item[] \footnotesize height of a permutation $=$ \#$\{$ pairs $(i,j)$ out
  of order $\}$. 
\item[] \footnotesize \#$\{$permutations at height $d\} =$ coefficient of $x^d$
  in polynomial 
\vskip -.3cm $$(1)(1+x)(1+x+x^2)\cdots(1+x+\cdots x^{n-1}).$$
\item[] \footnotesize \#$\{$ascending paths bottom to top$\} =$
\vskip -.3cm $$\scriptstyle{{\binom{n}{2}}!}/1^{n-1}3^{n-2}5^{n-2}
\cdots(2n-5)^2(2n-3) \qquad\qquad \text{\footnotesize\alert{Stanley's
    formula}}$$
\item[] \footnotesize (Formula says 16 ascending paths bottom to top in
  this picture.) 
\end{itemize}
\end{frame}

% Next slide shows a giant picture, then zooms in on part of it

\begin{frame}
\frametitle{More complicated groups}
\small
\begin{itemize}
\item[] Picture just described (with $n!$ vertices) is for invertible
  $n\times n$ matrices. This is the basic example of a \alert{real
    reductive Lie group}.  Mathematicians and physicists look at lots
  of other reductive groups.

\only<1> {\vskip 3.2cm \  }
\only<2>{\includegraphics[width=9cm]{s2m/so55.jpg}}
\only<3->{\vskip .15cm\includegraphics*[trim={24cm 10cm 24cm
      10cm},clip,width=9cm]{s2m/so55.jpg}
  
\centerline{\color{blue}\footnotesize closeup view}}
\item<4->[] Each reductive group has a finite diagram describing how
its big Schubert varieties are ``inflated'' from smaller ones. This one is
for a $45$-dimensional group called $SO(5,5)$.
\item<5->[] For this group there are 251 Schubert varieties, but each
  arrow still means \alert{replace points by circles}.
\end{itemize}
\end{frame}


\section[An addiction to silicon]{An addiction to silicon}
\begin{frame}
\frametitle{Forming the {\em Atlas} group}
\small
\begin{itemize}
\item[] Between 1980 and 2000, increasingly
  sophisticated computer programs calculated special kinds of 
  Kazhdan-Lusztig polynomials; none dealt with the
  complications attached to general real reductive groups.
\item[] In 2001, \alert{Jeff Adams} at University of Maryland decided
  computers and mathematics had advanced far enough to
  begin interesting work in that direction. 
\item[] Adams formed a research group \alert{\em Atlas of Lie groups and
    representations}, aimed in part at producing software to
  make old mathematics widely accessible, and to
  find new mathematics.
\item[] A first goal was to calculate Kazhdan-Lusztig
  polynomials for real reductive groups.
\end{itemize}
\end{frame}

% Here's a frame with a big photo appearing partway through

\begin{frame}
\frametitle{How do you make a computer do that?}
\small
\begin{itemize} % \item[]\vskip -\baselineskip
\item<1-> \vskip -.3cm In June 2002, {\color{red} Jeff Adams} asked
  {\color{blue} Fokko du Cloux}.
\item<2-> \vskip -.1cm In November 2005, Fokko finished the program.
\item<3->[] \vskip -.1cm \footnotesize Wasn't that easy?
\end{itemize}
\only<-3>{\vskip 5cm \ }
\only<4->{\hskip .75cm \includegraphics[width=7.5cm]{s2m/fokkojeff.pdf}}
\begin{itemize}
\item<5-> In 2006, Jeff Adams proposed to calculate
  KL polynomials for the $248$-dimensional {\em exceptional Lie
    group} $E_8$.
\end{itemize}
\end{frame}

% here's a frame with a big table, rows of the table uncovered one
% slide at a time

\begin{frame}
\frametitle{What's the computer have to do?}
\vskip -.5cm
\begin{tabular}{c|c}
\uncover<1->{{\color{blue}TASK}&
  {\hfill\color{green}COMPUTER RQMT\hfill} \\ \hline
\hphantom{\hskip 3cm} & \hphantom{\hskip 4cm} \\[-.3cm]}
\uncover<2->{\parbox{3cm}{\scriptsize Make graph: 453,060 
    nodes, 8 edges at each} & \parbox{4cm}{{\color{green}250M RAM,}
    {\color{black}10 minutes} \\ {\color{black}\tiny (latest software: thirty seconds)}} \\[.3cm]
    \hline \\[-.3cm]}
\uncover<3->{\parbox{3cm}{\scriptsize List primitive pairs of vertices:
    6,083,626,944} & \small {\color{green}450M RAM}{\color{black}, few seconds} \\[.2cm]
  \hline \\[-.3cm]} 
\uncover<4->{\parbox{3cm}{\scriptsize Calculate polynomial for each
    primitive pair}
  & \parbox{2.5cm}{\color{black}\tiny Fetch few kB from memory, few thousand
    integer ops} {\color{black}$\times$\small{6 billion}}\\[.2cm] \hline \\[-.3cm]} % 150 pol x 12
                                % terms/pol x 4 bytes/term
\uncover<5->{\parbox{3cm}{\scriptsize Look for polynomial in store, add if
    it's new} 
  & {\color{green}\parbox{5.5cm}{$\scriptstyle \begin{matrix} 4 &\times& 20
      &\times & ?? \\
      \frac{\text{bytes}}{\text{coef}} &&
      \frac{\text{coefs}}{\text{poly}} &&
      \scriptstyle \text{\footnotesize polys} \end{matrix}$
    RAM}}\\[.4cm] \hline \\[-.3cm]} 
\uncover<6->{\parbox{3cm}{\scriptsize Write number for poly in
    table} & {\color{green}25G RAM}\\[.2cm] \hline}
\end{tabular}
\vskip 0cm
\uncover<7->{\centerline{Big unknown: number of
 distinct polynomials.} } 
\uncover<8->{\centerline{Hoped {\color{blue}400 million polys}
  $\rightsquigarrow$ {\color{green}75G total RAM.}}}  
\uncover<9->{\centerline{Feared {\color{blue}1 billion}
  $\rightsquigarrow$ {\color{green}150G total RAM.}}}
\end{frame}

\end{document}


