\documentclass[ignorenonframetext]{beamer}
%\documentclass[class=amsart]{beamer}
%% Beamer Declarations
\mode{
\usepackage{beamerbasearticle}
\usepackage{fullpage}
\usepackage{pgf}
\usepackage{hyperref}
}
\mode{
% \usepackage[bars]{beamerthemetree}
\usetheme{default}
\useinnertheme{default}
\useoutertheme{infolines}
%\usecolortheme{beetle}
\usecolortheme{rose}
\usecolortheme{dolphin}
% \setbeamercolor{example text}{fg=green}
% \beamertemplatetransparentcovereddynamic
% \beamertemplateballitem
}
%% LaTeX Packages
%\usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps,pgfshade}
\usepackage{graphicx}
%\usepackage{longtable}
\usepackage{calc}
\usepackage{amsmath,amssymb}
\usepackage[english]{babel}
\usepackage{setspace}
%\usepackage{dev}
%% LaTeX Definitions
%\newcounter{countup}
\DeclareMathOperator{\bbF}{{\mathbb F}}
\DeclareMathOperator{\Id}{{\mathrm Id}}
\DeclareMathOperator{\Trace}{{\mathrm Trace}}
% Document information
\date[ISW 2008]{Institute Seminar Week, 6th March 2008}
\title{What is Reciprocity?}
\subtitle{{\small (an introduction to Langlands' vision)}}
\author[Kapil Paranjape]{Kapil Hari Paranjape}
\institute[IMSc]{The Institute of Mathematical Sciences}
\subject{Institute Seminar Week}
\begin{document}
\onehalfspacing
%@modernhindi
\frame{\maketitle}
\section{Introduction}
\begin{frame}{The Truth about Mathematicians}
\begin{center}
Mathematicians are \emph{lazy} people.
\end{center}
\pause
{\em
They would rather use time thinking about {\em how} to make a calculation
simpler, \only<2>{\dots}\pause than waste time actually doing the calculation.
}
\pause
\begin{center}
Good Mathematicians \emph{still} manage to get the job done.
\end{center}
\pause
{\em
In other words, they {\em actually} carry out the simpler procedure
to complete the calculations.
}
\pause
\begin{center}
Mathematical philosophers get \emph{others} to do the hard work.
\end{center}
\pause
They chalk out a programme to carry out all kinds of calculations very
quickly \only<7>{\dots}\pause and let others carry out this programme.
%As they say in Hindi
%\pause
%\begin{center}
% %\dn
% samajhdaar ko ishaara kaafi hai!
%\end{center}
\end{frame}
To illustrate the point here is my version of how Gauss discovered
quadratic reciprocity.
We can add, subtract and multiply integers \em{modulo} a number
$N$. This means that after each operation we take the remainder after
division by $N$. We call this arithmetic on the set $\{0,\dots,
N-1\}$ modulo $N$. When $N$ is a \em{prime}, Euclid's algorithm
provides a way to divide by a non-zero element of this set as well;
i.~e.\ in modern terminology, this is a field. Note that the capital letter
($N$) has been used to remind us that we are interested in the situation
when $N$ is large.
\begin{frame}{Arithmetic Modulo $N$}
\begin{itemize}
\item The set $\bbF_N=\{0,\dots,N-1\}$ carries the usual arithmetic
operations; addition, multiplication and subtraction.
\pause
\item Method: Apply the ``usual'' operation and then take the remainder
after division by $N$.
\pause
\alert<3>{\emph{Negative numbers give positive remainders!}}
\pause
\item When $N$ is prime. This is a field.
\pause
\emph{Euclid's algorithm provides a way to divide by a non-zero
element of this set.}
If $a b + k N = 1$ then $ab=1$ modulo $N$.
\end{itemize}
\end{frame}
\begin{frame}[fragile]{How large is $N$?}
For the rest of this talk $N$ will be a \emph{large} prime.
\begin{quote}
\pause
\verb|? N=prime(random(1000000000))|\\
\pause
\verb|N=726377293|\\
% \pause
%\verb|? isprime(N,2)|\\
% \verb|1|
\end{quote}
\pause
For most humans this is probably large enough!
\pause
If you are as fast as a Xeon processor you can take about 300 more
digits.\pause\ So take $N$ as
\begin{quote}
\verb|1495145408827625078292664907290148913964441697228976|\\
\verb|4445366358595008337533666363448445244767319428213864|\\
\verb|1842496975368703352911650953541829107677855943186814|\\
\verb|2223164587340540087754181159128253617165405682750216|\\
\verb|1712347287973437514175773829454091516732839564970608|\\
\verb|0984751898535619484306219840829692491753915601587|
\end{quote}
\pause \alert{It \emph{is} a prime!}
\end{frame}
\begin{frame}{Squares modulo $N$}
Elements of $\bbF_N$ like 1, 4, 9 and 16 are squares modulo $N$.
\pause
However, there \emph{could be} other squares modulo $N$. For example,
\pause
\[ 5 = 6^2 - 31 \]
so 5 is a square modulo 31.
\pause
Even when $N$ is large there are some uniformities. For example,
\begin{center}
If $N=4M+1$ then $-1$ is a square modulo $N$.
\end{center}
\pause
How do we decide whether 5 is a square modulo 726377293?
\end{frame}
\begin{frame}{A ``bad'' solution}
We get a ``quick and dirty'' solution based on some
observations.
\begin{itemize}
\pause
\item The collection $\bbF_N^{*}=\{1,\dots,N-1\}$ forms a {\em cyclic}
group under multiplication modulo $N$.
\pause
\item If 5 is a square, then its order can be at most $(N-1)/2$.
\pause
\item We can calculate $5^{(N-1)/2}$ modulo $N$
and check whether it is 1 or not.
\end{itemize}
\pause
However, we also observe that this method is too painful.
\pause\medskip
In particular, it involves calculations with big numbers like 726377293!
\end{frame}
%To do this we write
%\[
% (726377293-1)/2 = (100101010000001011111000111100000)_{2}
%\]
%Set $a=5$ and $b=1$. Start reading the above bit sequence from
%the left, each time you see a 1 you multiply $b$ by $a$; and on each
%turn you square $a$. Of course, to keep things small we always replace
%$a$ and $b$ by their remainders on division by 726377293. After the
%last step $b$ will contain the value of 1 if and only if 5 is a
%square modulo 726377293.
\section{Quadratic Reciprocity}
\begin{frame}{Enter Carl Friedrich Gauss}
We already know that Gauss found a lazy way to add numbers
from 1 to 100.\pause\ So he was a good mathematician! Q.E.D.
\medskip
\pause
Gauss asked himself whether there is a way to decide whether 5 is a
square modulo large primes $N$, \pause while calculating with ``small'' numbers
of the order of 5 \pause rather than large numbers of the order of $N$.
\medskip
\pause Gauss' law of Quadratic Reciprocity is his answer.
\medskip
\pause The royal road to quadratic reciprocity goes via
\emph{cyclotomic numbers}.\\
(Which is poetic name for the roots of unity.)
\end{frame}
\subsection{Some Observations}
We can write the square root of 5 in terms of the fifth root of 1.
\begin{frame}{An observation about fifth roots of unity}
Let $\xi$ denote a fifth root of 1.
\pause Then $\xi$ satisfies the equation.
\[
\xi^4+ \xi^3 + \xi^2 + \xi + 1 = 0
\]
\pause
Putting $\eta=\xi+\xi^4$, we get
\[
\eta^2 = (\xi+\xi^4)^2 = \xi^2 + \xi^3 + 2 =
1 - (\xi+\xi^4) = 1 - \eta
\]
\pause
In other words
\[ (1+2\eta)^2 = 1 + 4\eta + 4\eta^2 = 1 + 4 = 5 \]
\pause
\alert{So $(1+2\eta)$ is \emph{a} square root of 5.}
\end{frame}
Now an important property of calculations modulo $N$ is that
$(x+y)^N=x^N+y^N$ (recall that $N$ is a prime) so that the operation
of taking the $N$-th power is a field automorphism which is nowadays
called the Frobenius operator. The solutions of $T^N=T$ modulo
$N$ are precisely the integers $\{0, 1,\dots, N-1\}$; thus to find
out whether $5$ is a square modulo $N$ it is enough to check whether
$\eta^N=\eta$. This doesn't seem to make the problem easier!
\begin{frame}{The Frobenius automorphism}
When $N$ is a prime, the binomial theorem says that
\[
(x+y)^N = x^N + y^N ~\text{modulo $N$}
\]
\pause
We can also apply this to {\em matrices} $x$ and $y$
as long as $xy=yx$.
\pause
Moreover, if $x$ is a matrix with entries in $\bbF_N$, then
\[
x^N=x ~\text{modulo}~ N \text{~if and only if~} x=k\Id
\]
i.~e.\ $x$ is a diagonal matrix with $k\in\bbF_N$.
\end{frame}
\begin{frame}{Matrices solve equations}
Any equation can be solved using matrices and vice versa.
\pause
Solutions of the equation
\[
T^n + a_1 T^{N-1} + \dots a_n = 0
\]
\pause
are represented as the matrix
\[
M_f =
\begin{pmatrix}
0 & 1 & 0 & \dots & 0 \\
0 & 0 & 1 & \dots & 0 \\
\vdots & \vdots & \vdots & \ddots & 0 \\
-a_n & -a_{n-1} & -a_{n-2} & \dots & -a_1
\end{pmatrix}
\]
\pause
So henceforth when we write a solution of an equation we mean
the corresponding matrix!
\end{frame}
\begin{frame}{The fifth root of unity as a matrix}
For example, the fifth root of unity can be represented by the matrix
\[
\xi = \begin{pmatrix}
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
-1 & -1 & -1 & -1
\end{pmatrix}
\]
In particular, we can check whether $\eta=\xi+\xi^4$ is a scalar
matrix modulo $N$ by checking whether $\eta^N=\eta$.
\end{frame}
Moreover, checking how the Frobenius (taking $N$-th powers) operates
on $\xi$ is easy since the latter is a fifth root of 1.
\frame{
\frametitle{Easy calculation}
Since $726377293$ is 3 modulo 5 we have
\pause
\[
\xi^{726377293} = \xi^3
\]
\pause
Moreover,
\[
(\xi^4)^{726377293} = (\xi^3)^4 = \xi^2
\]
\pause
Hence we see that
\[
\eta^{726377293} = \xi^3 + \xi^2 = 1 - \eta
~\text{modulo 726377293}
\]
\pause
In other words, $\eta$ is not an integer modulo 726377293.
It follows that 5 is \alert{not a square} modulo 726377293.
}
It is clear how to make this into an ``engine'' to check whether 5 is
a square modulo $N$ even for very large primes $N$.
\frame{
\frametitle{All $N$ at once}
If $N$ reduces to 1 or 4 modulo 5 \pause
\begin{flushright}then 5 \em{is} a square modulo $N$.\end{flushright}
\pause
if $N$ reduces to 2 or 3 modulo 5 \pause
\begin{flushright}then 5 \em{is not} a square modulo $N$.\end{flushright}
\pause
\medskip
\alert{It's that simple!}
}
Just for comparison here is the painful calculation that we skipped
earlier!
\begin{frame}[fragile]
\frametitle{Painful Calculation}
\begin{verbatim}
? N=726377293
N = 726377293
? t=(N-1)/2;a=Mod(5,N);b=Mod(1,N);sp=" ";
? while(t,printp(t,sp,a,sp,b);if(t\%2,b=a*b);\
a=a^2;t=divrem(t,2)[1]);printp(t,sp,a,sp,b)
\end{verbatim}
\pause
{\tt
%\begin{longtable}{rrr}
\begin{tabular}{rrr}
363188646 & (5 mod N) & (1 mod N)\\
181594323 & (25 mod N) & (1 mod N)\\
90797161 & (625 mod N) & (25 mod N)\\
%\end{tabular}
%\pause
\multicolumn{3}{c}{\rm \dots (24 lines elided!)}\\
%{\rm \dots (24 lines!)}\\
%\pause
%\begin{tabular}{rrr}
2 & (116419545 mod N) & (62288545 mod N) \\
1 & (229055375 mod N) & (62288545 mod N) \\
0 & (15956006 mod N) & (N-1 mod N)
\end{tabular}
%\end{longtable}
}
\pause
This method \alert{is} too painful.
\end{frame}
This is why it is ``reciprocity''; a problem regarding the properties
of 5 modulo $N$ has been reduced to properties of $N$ modulo 5. I
think this term \em{reciprocity} is misleading since it leads one to
believe that the ``second'' 5 is the same as the ``first'' 5.
To understand this consider the problem of checking whether 7 is a
square modulo some large prime $N$.
\frame{
\frametitle{When is 7 a square modulo $N$?}
We note that
\[
\left((\tau + \tau^{-1}) + (\tau^3 + \tau^{-3}) + (\tau^9 +
\tau^{-9})\right)^2 = 7
\]
where $\tau$ is a 28-th root of unity.%\only<2>{\footnotemark}
%\onslide+<2>{\footnote{(Note: Such formulas are not
%``magic''; they are consequences of the theory of groups)}}
%\pause
%ootnotetext[1]{(Note: Such formulas are not
%magic''; they are consequences of the theory of groups)}
%\pause[3]
\pause
Thus $\tau\mapsto\tau^k$ takes $\sqrt{7}$ to itself if and only if
$k$ is
\begin{quote}
$1$ or $27=28-1$, or\\
3 or $25=28-3$, or\\
9 or $19=28-9$ modulo 28.
\end{quote}
\pause
Thus, $7$ is a square modulo $N$ if and only if $N$ is congruent
to 1, 3, 9, 19, 25 or 27 modulo 28.
}
\section{Abelian Extensions}
The underlying conceptual idea here can be stated as follows:
\begin{frame}
\frametitle{Conceptual statment of Quadratic reciprocity}
\begin{quote}
The problem of studying the solutions of
$T^2-a=0$ modulo a large prime $N$
\pause
\begin{center}
is {\em equivalent} to
\end{center}
\pause
the problem of studying the $N$-th power map acting
on the $b$-th roots of unity\pause,
where $b$ is somehow derived from $a$.
\end{quote}
\pause
{\small Actually $b$ is either $a$ or $4a$ depending on whether $a$ is 1 or 3
modulo 4.}
\end{frame}
The important point is that the $N$-th power map is a well-understood
operation on a well-understood group; the multiplicative group.
We can ask whether a similar situation exists for other equations.
\begin{frame}
\frametitle{The Theorem of Kronecker and Weber}
Indeed, there is a class $A$ of algebraic equations $f(T)=0$ such
that
\begin{quote}
The problem of studying the equation $f(T)=0$
modulo a large prime $N$
\begin{center} is equivalent to \end{center}
the problem of
studying the behaviour of the $N$-th power map acting on the
$b$-th roots of unity\pause, where $b$ is (somehow) derived from the
coefficients of $f(T)$.
\end{quote}
\pause
{\small The class $A$ is called the class of \em{abelian} equations and $b$
is called the \em{conductor} of the equation $f(T)$.}
\end{frame}
Another things mathematicians do is to ``generalise''. So we ask
whether we can do something similar for \em{all} equations or even
systems of equations in many variables.
\begin{frame}
\frametitle{The Importance of Linear Algebra}
The reason why studying the $N$-th power map on the roots of unity is
easy can be explained as follows. \pause
\begin{quote}
\alert<2>{The $N$-th power map permutes the roots of unity}
\end{quote}
\pause
By suitable representation of the $b$-th roots of unity as as matrix
$X_b$, we see that the $N$-th power map is given by
\[
X_b \mapsto T_N X_b T_N^{-1}
\]
where $T_N$ is just a cyclic permutation matrix.
\pause\medskip
{\bf Question}: Can we find a similar $T_N$ for other problems?
\end{frame}
%First of all some algebra. Given any polynomial equation $f(T)=0$ of
%degree $d$ we have seen that there is a natural $d\times d$ matrix
%$M_f$ with rational coefficients such
%that $f$ is its minimal polynomial.
%\frame{
%\frametitle{The Galois Group}
%To an equation $f(T)=0$ we associated \hyperlink{matrix}{a matrix}
%$M_f$.
%\pause
%Let $G$ be the group
%\[ \{ A \mid AM_fA^{-1} = P_A(M_f) \} \]
%(for some polynomial $P_A(T)$ depending on $A$)
%
%\pause
%$\tilde{G}=G/\text{scalars}$ is called the \emph{Galois group} of the
%equation $f(T)=0$. \pause It is a finite group of order at most $\deg(f)$.
%
%\pause
%Let us assume that $f(T)$ is normal; i.~e.\ $\tilde{G}=\deg(f)$.
%}
%\frame{
%\frametitle{The Frobenius element}
%For each large prime $N$ \hypertarget{exists1}{there is an element} $T_N$ of $G$ which
%represents the Frobenius element modulo $N$.
%In particular, $T_N$ is a
%scalar matrix if and only if $f(T)$ splits into linear factors modulo
%$N$; i.~e. one can find all roots of $f(T)=0$ among integers modulo
%$N$. If we pick the $T_N$ carefully to avoid the unnecessary scalar,
%then the number of roots modulo $N$ is just the trace of $T_N$.
%}
\section{Weil Conjectures}
The work of Weil, Grothendieck, Deligne and many others shows that
this generalises as follows.
\begin{frame}[fragile]{The Trace formula of Weil and Grothendieck}
Given a system $S$ of
algebraic equations in any number of variables:
\begin{enumerate}
\pause
\item there is a finite collection of vector spaces $H^i(S)$; one
for each $i$ between 0 and $2\dim(S)$.
\pause
\item for each large prime $N$, there
is an automorphism $T_{i,N}$ of
$H^i(S)$.
\end{enumerate}
\pause The number of solutions of $S$ modulo $N$ is given by the
simple formula
\pause\alert{
\[
\#S(\bbF_N) = \sum_{k=0}^{2\dim(S)} (-1)^k \Trace(T_{k,N})
\]
}
\pause
{\small Since we will study each $k$ separately in what follows. I
will drop the subscript $k$ hereon.}
\end{frame}
So in each case the key problem is the determination of the traces of
some matrices $T_N$; that sounds easy enough!
\begin{frame}{It's too easy!}
\begin{center}``Determine the trace of a matrix $T_N$.''\end{center}
\pause
Sounds easy enough! What's the catch?
\pause\bigskip
\alert{The Catch}:
The phrase ``there exists a matrix $T_N$'' says nothing
about how to \emph{construct} it!
\end{frame}
We have reduced The problem in both the above descriptions is in
the phrase ``there exists a $T_N$''. At this point we have not said
anything about how one can construct $T_N$ (or calculate its trace).
\section{Langlands' Philosphy}
To get a handle on the $T_N$ we need to have some generalisation of
the cyclotomic character. (``Cyclotomic'' is a beautiful name for
the roots of unity.) This is where Langlands comes in and shows how
to construct a sufficiently large collection of such systems (of
matrices indexed by primes) so that all the problems we have been
considering so far would be subsumed in this collection.
To solve our original problem, all we have to do is to look in
Langlands' list and our question would already have been solved!
Later refinements to Langlands program also show how one can narrow
down this search.
Let us try to understand the idea of Langlands.
\begin{frame}
\frametitle{Langlands' Philosophy}
\begin{enumerate}
\pause
\item We expect the $T_N$'s to have a nice distribution so that the
$L$-function
\[ L(\{T_N\},s) = \prod_N \det\left( 1 - T_N N^{-s} \right)^{-1} \]
should have nice analytic properties.
\pause
\item The theory of ``Automorphic representations'' gives a
large list of such collections $\{T_N\}$ with nice analytic
properties.
\end{enumerate}
\pause
{\bf Question}: Wouldn't it be nice if the second list contained the
first?
\pause Since it would be \emph{nice} --- so we conjecture it to be
so!
\pause \alert{Actually, there is a bit more evidence than that!}
\end{frame}
One should remark that this does not complete the generalisation of
Gauss' quadratic reciprocity from a computational perspective.
\begin{frame}{Are we there yet?}
The construction of automorphic representations is
\alert<1>{analytic}\only<1>{\dots}\pause,
and analysis does not generally yield exact formulae.
\pause\alert<3>{But we want integers!}
\pause\bigskip
\alert{Solution}
(Proposed in collaboration with Dinakar Ramakrishnan.)
\pause
Construct canonical algebraic problems $S_{\pi}$ for
each (or enough) automorphic representations.
\pause\bigskip
\alert{Idea}
$S_{\pi}$ generalise the role played ``roots of unity'' in
Kronecker-Weber.
\pause\bigskip
We have constructed examples of $S_{\pi}$ for a number of cases and
proposed some candidate classes.
\end{frame}
The
problem is that the definition and construction of automorphic
representations is analytic. Thus it may still not be easy to compute
the traces of $T_N$ even if we know the precise automorphic
representation that we are looking for. One way to get around this is
to construct ``canonical'' representatives $S_{\pi}$ for each
automorphic representation $\pi$. The algebraic problems $S_{\pi}$
(like the case of roots of unity) would be sufficiently special that
one could hope to get a handle on solving the problem directly in
that case. In joint work with Dinakar Ramakrishnan, we propose such
candidate representatives for some automorphic representations $\pi$.
\section{Elliptic Curves}
One interesting case where Langlands programme has been carried out
but where the original reciprocity problem has no complete solution
is the case of elliptic curves.
\begin{frame}{A small step for Langlands $\dots$ }
Elliptic curves $E$ are given by an equation of the form
\[ y^2 = x^3 + ax +b \]
\pause
In this case, $T_{0,N}=1$ and $T_{2,N}$ is also easy
\pause\medskip
So we study $T_N=T_{1,N}$ which is a $2\times 2$ matrix.
\pause Let $a_N=\Trace(T_N)$.
\pause\medskip
Wiles and Taylor showed that
\[
L(E,s) = L(\{T_N\},s)
= \prod_{N} \left(1 - a_N N^{-s} + N^{1-2s}\right)^{-1}
\]
\emph{is} the zeta function of a modular form $f$ of level
$\Delta(a,b)$. \pause (\emph{Fermat's Last Theorem was an insignificant consequence!})
%\end{frame}
%\begin{frame}
%\frametitle{Reciprocity for $GL(2)$?}
\pause
There are only finitely many modular forms of a given level.
\pause
So given the level and a few coefficients one can determine a
{\em unique} modular form $f_E$.
\pause\medskip
{\bf Question}: Can one improve on Schoof's algorithm by using this to
compute $a_N$ for large $N$? \pause\raggedleft\dots\alert{Can one make the giant leap?}
\end{frame}
\end{document}