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