CoCalc Public Fileswww / simuw06 / notes / notes.texOpen in CoCalc with one click!
Author: William A. Stein
1
\documentclass{article}
2
\include{macros}
3
\newcommand{\url}[1]{\begin{center}{\tt #1}\end{center}}
4
\newcommand{\code}[1]{{\blue\tt #1}}
5
\usepackage{graphicx}
6
\usepackage{color}
7
\usepackage{pstricks}
8
\title{The Congruent Number Problem:\\A Thousand Year Old Unsolved Problem}
9
\author{William Stein ({\tt http://modular.math.washington.edu})}
10
\date{SIMUW 2006}
11
12
\newcommand{\computation}{{\blue\sc\underline{Computation}:} }
13
\newcommand{\theory} {{\blue\sc\underline{Theory}:} }
14
\newcommand{\research}{{\blue\sc\underline{Research}:} }
15
\renewcommand{\sage}{{\blue\SAGE\xspace}}
16
17
\begin{document}
18
\maketitle
19
20
\begin{abstract}
21
One of the oldest unsolved problems in mathematics is to determine
22
the {\em congruent numbers}: {\em Give a way to decide whether or
23
not an integer is the area of a right triangle with rational side
24
lengths.} For example, 6 is the area of the right triangle with
25
side lengths 3, 4, and 5. But 1 is not a congruent number. What
26
about 2006? This workshop will take us from ancient algebra to a
27
major modern conjecture in number theory that has a million dollar
28
bounty: the Birch and Swinnerton-Dyer Conjecture.
29
\end{abstract}\vspace{-7ex}
30
31
\begin{center}
32
\includegraphics[width=0.7\textwidth]{graphics/tri}\vspace{-7ex}
33
\end{center}
34
The first few congruent numbers:
35
{\tiny\noindent{}5, 6, 7, 13, 14, 15, 20, 21, 22, 23, 24, 28, 29, 30, 31, 34,
36
37, 38, 39, 41, 45, 46, 47, 52, 53, 54, 55, 56, 60, 61, 62, 63, 65,
37
69, 70, 71, 77, 78, 79, 80, 84, 85, 86, 87, 88, 92, 93, 94, 95, 96,
38
101, 102, 103, 109, 110, 111, 112, 116, 117, 118, 119, 120, 124,
39
125, 126, 127, 133, 134, 135, 136, 137, 138, 141, 142, 143, 145,
40
148, 149, 150, 151, 152, 154, 156, 157, 158, 159, 161, 164, 165,
41
166, 167, 173, 174, 175, 180, 181, 182, 183, 184, 188, 189, 190,
42
191, 194, 197, 198, 199, 205, 206, 207, 208, 210, 212, 213, 214,
43
215, 216, 219, 220, 221, 222, 223, 224, 226, 229, 230, 231, 237,
44
238, 239, 240, 244, 245, 246, 247, 248, 252, 253, 254, 255, 257,
45
260, 261, 262, 263, 265, 269, 270, 271, 276, 277, 278, 279, 280,
46
284, 285, 286, 287, 291, 293, 294, 295, 299, 301, 302, 303, 306,
47
308, 309, 310, 311, 312, 313, 316, 317, 318, 319, 320, 323, 325,
48
326, 327, 330, 333, 334, 335, 336, 340, 341, 342, 343, 344, 348,
49
349, 350, 351, 352, 353, 357, 358, 359, 365, 366, 367, 368, 369,
50
371, 372, 373, 374, 375, 376, 380, 381, 382, 383, 384, 386, 389,
51
390, 391, 395, 397, 398, 399, 404, 405, 406, 407, 408, 410, 412,
52
413, 414, 415, 421, 422, 423, 426, 429, 430, 431, 434, 436, 437,
53
438, 439, 440, 442, 444, 445, 446, 447, 448, 453, 454, 455, 457,
54
461, 462, 463, 464, 465, 468, 469, 470, 471, 472, 476, 477, 478,
55
479, 480, 485, 486, 487, 493, 494, 495, 496, \ldots,
56
1974, 1975, 1976, 1980, 1981, 1982, 1983, 1984, 1989, 1990, 1991, 1995, 1997, 1998,
57
1999, 2000, 2004, 2005, 2006, 2007, 2008, 2009,\ldots }
58
59
\tableofcontents
60
61
\newpage
62
\noindent{\bf Goals:}
63
\begin{itemize}
64
\item Learn about a major open problem in number
65
theory.
66
\item Learn to use \sage{} to draw plots and do
67
computations.
68
\item Learn about elliptic curves: groups, public-key
69
cryptography, the BSD conjecture.
70
\end{itemize}
71
72
73
\section{Rational Right Triangles}
74
\begin{enumerate}
75
\item Statement of the congruent number problem.
76
\item Explain what ``enumerate means''.
77
\item Explain how to enumerate all right triangles with integer side
78
lengths -- Pythagorean triples: draw graph of circle; draw line;
79
find other point of intersection; write it as $(x,y)$ with
80
$x,y$ in terms of $t$.
81
\item SAGE tutorial:
82
\begin{enumerate}
83
\item What is SAGE?
84
\item SAGE website.
85
\item SAGE notebook: everyone create a worksheet.
86
\end{enumerate}
87
\end{enumerate}
88
\begin{itemize}
89
\item \computation
90
\begin{itemize}
91
\item Computer lab orientation.
92
\item Introduction to \sage.
93
\item Write a program to enumerate rational numbers (make table).
94
\item Write a program to enumerate Pythagorean triples (make table).
95
\item Write a program that enumerates rational right
96
triangles (make table).
97
\item Write a program that enumerates congruent numbers (make table).
98
\item Draw plots of numerous rational right triangles (use the {\tt polygon}
99
command in \sage).
100
\end{itemize}
101
\item \theory{}
102
\begin{itemize}
103
\item Give a way to enumerate all rational numbers.
104
\item Give a way to enumerate all rational right triangles.
105
\item Prove that $n$ is a congruent number if and only if $nk^2$ is
106
a congruent number for any positive integer $k$.
107
\item Give a way to enumerate all congruent numbers.
108
I.e., a procedure that outputs only congruent numbers and
109
will eventually output any given congruent number.
110
\item Give an explicit parametrization of all rational solutions
111
$(x,y)$ to the equation $5x^2 - y^2 = 4$.
112
\item Give an example of an equation $ax^2 + by^2=1$ with
113
$a,b\in\Q$ and $a,b>0$ that has no rational solutions $(x,y)$.
114
\end{itemize}
115
116
\item \research{}
117
\begin{itemize}
118
\item Generalize the enumeration method from above to
119
a method to find all rational solutions to any equation
120
$ax^2+by^2 = c$, when you're given one solution $P=(x,y)$.
121
\item Use the internet to try to figure out what the ``local-to-global
122
principle for binary quadratic forms'' is. Give examples that
123
illustrate it.
124
\item {\bf\red Open problem:} Consider an equation $y^2 = f(x)$ with $f$ a
125
polynomial of degree $5$.
126
It is a very deep theorem (of Fields Medalist Gerd Faltings) that
127
there are only finitely many rational solutions $(x,y)\in\Q^2$
128
of $y^2 = f(x)$. It is an open problem to give an algorithm that
129
takes as input $f$ and outputs all the solutions to $y^2=f(x)$. This
130
is currently a very active area of research.
131
132
\end{itemize}
133
134
\end{itemize}
135
136
\section{Congruent Numbers and Elliptic Curves}
137
Today's workshop is about the connection between congruent
138
numbers and elliptic curves.
139
\begin{enumerate}
140
\item Daily crashing of the SAGE Notebook.
141
\item The Simuw SAGE Notebooks: login/password, graphics, tab completion,
142
using mathematica/maple/etc from it.
143
\item Why are they called ``congruent numbers''? Connection between
144
congruent numbers and ``congruences'' modulo $n$.
145
\item 10-minute break.
146
\item Definition of elliptic curve.
147
\item Connection between congruent numbers and elliptic curves.
148
\end{enumerate}
149
150
\begin{itemize}
151
\item \computation
152
\begin{itemize}
153
\item Find the point on an elliptic curve corresponding
154
to the $(3,4,5)$-triangle.
155
\item Find the point on an elliptic curve corresponding
156
to a rational right triangle with area $2006$.
157
\item Download a table from workshop website of the congruent
158
numbers up to $1000$, and look for patterns, e.g., reduce the
159
congruent numbers modulo $8$, etc., and see if you notice
160
anything.
161
\item Find a rational number $x$ such that $x-6, x, x+6$ are all perfect squares.
162
\item Find a rational number $x$ such that $x-2006, x, x+2006$ are all perfect squares.
163
\item Let $n$ be the year you were born. Is it possible to
164
find a rational number $x$ such that $x-n, x, x+n$ are all perfect
165
squares?
166
%Write a function (using a computer) that takes as input a
167
% congruent number $n$ and outputs three rational numbers
168
% $a,b,c$ such that $a,b,c$ are all squares of rational
169
% numbers, and $b = a+n$, $c = b+n$, i.e., $a,b,c$ are
170
% ``congruent modulo~$n$''.
171
\end{itemize}
172
\item \theory{}
173
\begin{itemize}
174
\item Prove that if $n$ is a congruent number then there exists a
175
rational number $x$ such that
176
$x-n$, $x$, and $x+n$ are all perfect squares of rational numbers.
177
178
{\small [[Hint: Let $X<Y<Z$ be sides of a rational right
179
triangle with area $n$. Let $x = (Z/2)^2$.]]}
180
\item Suppose $n$ is an integer and there exists a rational
181
number $x$ such that $n-x$, $n$, and $n+x$ are all perfect squares.
182
Prove that $n$ is a congruent number.
183
{\small [[Hint: from Koblitz's book (see page 4 of scan on website).
184
Let $X = \sqrt{x+n} - \sqrt{x-n}$,
185
$Y = \sqrt{x+n} + \sqrt{x-n}$,
186
$Z = 2\sqrt{x}$. Then $X,Y,Z$ are the sides of a right
187
triangle and are all rational, and the triangle has
188
area $n$.]]}
189
190
\item Think about problems with a similar feel:
191
\begin{enumerate}
192
\item Which integers are the
193
area of a square with rational side lengths?
194
\item Which integers are the
195
perimeter of a square with rational side lengths?
196
\item Which integers are the
197
area of a rectangle with rational side lengths?
198
\end{enumerate}
199
\item
200
Let~$n$ be a rational number. Prove that there is a bijection between
201
$$
202
A = \left\{(a,b,c) \in \Q^3 \,:\, \frac{ab}{2} = n,\, a^2 + b^2 = c^2\right\}
203
$$
204
and
205
$$
206
B = \left\{(x,y) \in \Q^2 \,:\, y^2 = x^3 - n^2 x, \,\,\text{\rm with } y \neq 0\right\}
207
$$
208
given explicitly by the maps
209
$$
210
f(a,b,c) = \left(-\frac{nb}{a+c},\,\, \frac{2n^2}{a+c}\right)
211
$$
212
and
213
$$
214
g(x,y) = \left(\frac{n^2-x^2}{y},\,\,
215
-\frac{2xn}{y},\,\, \frac{n^2+x^2}{y}\right).
216
$$
217
218
%\item Find a linear change of variables that gives
219
%a one-to-one correspondence between points on
220
%$ny^2 = x^3 + ax^2 +
221
222
\end{itemize}
223
\item \research{}
224
\begin{itemize}
225
\item Try to say something about which integers are the perimeter of a
226
right triangle with rational side lengths. Try to convert this
227
question to a question about solutions to equations.
228
\item Be creative and come up with similar problems, e.g., which
229
integers are the area of an equilateral triangle with rational side
230
lengths, etc., some very hard, and convert each to a diophantine
231
equation.
232
\item Go to
233
\begin{verbatim}
234
http://www.msri.org/publications/ln/msri/2000/introant/
235
yui/1/index.html
236
\end{verbatim}
237
and read about another difficult generalization
238
of the congruent number problem (this was a talk at a serious
239
professional research conference, so don't be annoyed if
240
you don't understand much of it).
241
\end{itemize}
242
\end{itemize}
243
244
\begin{center}
245
%\includegraphics[width=1.1\textwidth, height=0.5\textheight]{graphics/elliptic_curves.png}
246
\mbox{\hspace{-8.5em}\includegraphics[bb=0 0 500 500]{graphics/elliptic_curves.png}}
247
\end{center}
248
For fun -- the above are a bunch of elliptic curves, along
249
with their {\bf ``Cremona labels''}.
250
251
\newpage
252
253
\section{Congruent Numbers and Elliptic Curves: II}
254
\begin{enumerate}
255
\item {\bf\blue The Bijection Revisited Conceptually:} (75 minutes)
256
\begin{enumerate}
257
\item (2 minute) Definition of {\em congruent number}.
258
\item (2 minute) Definition of {\em elliptic curve}.
259
\item (40 minutes) {\em Bijection} between points and congruent triangles: revisited.
260
In particular, here is a {\red conceptual way} to think about it.
261
The set of rational right triangles with area $n$ is
262
the same as the set of simultaneous solutions to the
263
system of equations
264
$$
265
a^2 + b^2 = c^2, \qquad \frac{ab}{2} = n.
266
$$
267
This is the intersection of two quadratic surfaces in $3$-space,
268
hence a curve. That curve turns out, after an appropriate
269
change of variables, to be the elliptic curve $y^2 = x^3 - n^2 x$.
270
Exercise: ...6 steps... (Solution presentation: 30 minute).
271
\end{enumerate}
272
273
\item {\bf\blue Break:} (10 minute).
274
275
\item {\bf\blue Perimeter:} (15 minute) Discuss the problem of which integers are the
276
perimeter of a right triangle with rational side lengths.
277
Again, the set of such triangles for a given $m$ is the
278
set of simultaneous solutions to 2 equations:
279
$$
280
a^2 + b^2 = c^2, \qquad a+b+c = m.
281
$$
282
This is the intersection of a quadratic surface and a plane,
283
hence a quadratic curve.
284
(Exercise -- 15 minutes trying
285
this further; presentation of solution.)
286
287
%\item {\bf\blue Graphing Elliptic Curves} (20 minutes):
288
%Show how to use SAGE to define and graph elliptic curves.
289
%(Exercise -- experiment for 20 minutes doing this; presentations.)
290
291
\item {\bf\blue Generating New Points on Elliptic Curves from Other Points}
292
(30 minutes):
293
Explain how it works. Show how to use SAGE to do it.
294
(Exercise -- 30 minutes doing this (and getting new triangles); presentations.)
295
\end{enumerate}
296
297
\begin{itemize}
298
\item \computation
299
300
\begin{itemize}
301
\item Find a triangle with perimeter $6$. Hint: rescale
302
the $3,4,5$ triangle. How does rescaling change the perimeter?
303
304
\item Find four distinct right triangles with area $6$.
305
306
% \item Draw graphs using SAGE of the set of real solutions to several
307
% elliptic curve equations, e.g., $y^2=x^3+1$, $y^2=x^3-3x+1$, and
308
% $y^2=x^3-x$.
309
%\begin{verbatim}
310
%sage: E = EllipticCurve([-3, 1])
311
%sage: print E
312
%Elliptic Curve defined by y^2 = x^3 - 3*x +1 over Rational Field
313
%sage: show(plot(E))
314
%\end{verbatim}
315
316
\item Let $E$ be the elliptic curve defined by
317
$y^2 = x^3 - 36x$,
318
and let $P=$
319
Compute $P, 2P, 3P, 4P$
320
by enter $E$ and $P$ into \sage{} and compute the given sums.
321
Trying computing lots of other points too.
322
\begin{verbatim}
323
sage: E = EllipticCurve([-36,0])
324
sage: P = E([...])
325
sage: 2*P
326
\end{verbatim}
327
\end{itemize}
328
329
\item \theory{}
330
\begin{itemize}
331
\item Fix an integer $n$. Show that the rational right triangles
332
with area $n$ are in bijection
333
with the solutions to $y^2=x^3-n^2x$ with $y\neq 0$ as follows:
334
\begin{enumerate}
335
\item Think purely conceptually (don't write anything down!):
336
\begin{enumerate}
337
\item Imagine the surface
338
$$
339
a^2 + b^2 = c^2
340
$$ in three-dimensional space.
341
\item Next imagine the surface
342
$$
343
\frac{ab}{2} = n
344
$$ in three-dimensional space.
345
\item Finally, imagine the intersection of those two surfaces.
346
You should be visualizing a curve in three dimensional space.
347
\end{enumerate}
348
349
\item Solve for $a$ in the equation $ab/2 = n$ and substitute
350
it into $a^2 + b^2 = c^2$ to obtain an equation of the curve
351
you visualized in three space in the previous problem.
352
You should be able to put this curve in the form
353
$$
354
4n^2 + X^4 = Y^2.
355
$$
356
(You'll have to let $X$ and $Y$ equal something involving
357
$a$ and $b$.)
358
\item Replace $X$ by $y_1$ and $Y$ by $x_1+y_1^2$ in the
359
equation for your curve. Simplify and get another curve
360
(but in the variables $x_1$ and $y_1$):
361
$$
362
4n^2 = x_1^2 + 2 y_1^2 x_1
363
$$
364
You should be able to do all this by hand. But if you want
365
to use a computer, here's an example of how in SAGE:
366
\begin{verbatim}
367
sage: X = gp('X'); Y = gp('Y'); x_1 = gp('x_1')
368
sage: y_1 = gp('y_1'); n = gp('n')
369
sage: print (Y^2).subst(Y,x_1+y_1^2).subst(X, y_1)
370
sage: print (4*n^2 + X^4).subst(Y,x_1+y_1^2).subst(X, y_1)
371
x_1^2 + 2*y_1^2*x_1 + y_1^4
372
y_1^4 + 4*n^2
373
\end{verbatim}
374
(In SAGE the command {\tt gp('stuff')} makes a formal variable,
375
and {\tt subst} allows you to do formal substitutions.)
376
\item Multiply both sides of the equation you obtain by $x_1$,
377
then replace $x_1$ by $x_2$ and $y_1$ by $y_2/x_2$, to obtain:
378
$$
379
4n^2 x_2 = x_2^3 + 2y_2^2.
380
$$
381
382
\item Do a few additional manipulations to finally obtain
383
the equation
384
$$
385
y^2 = x^3 - n^2x.
386
$$
387
\item If you combine everything you've done so far you get a bijection
388
from yesterday (you do not have to show this). Moreover, you can
389
now go back and forth between solutions to $ y^2 = x^3 - n^2x $ and
390
rational right triangles with area $n$. For example, try this with
391
$n=6$.
392
\begin{enumerate}
393
\item Show that the point on the cubic $y^2 = x^3 - 36x$
394
that corresponds to the $3,4,5$
395
triangle is $(-3,9)$.
396
\item Use \sage{} to find another point $Q$ on $y^2 = x^3 - 36x$.
397
\item Find the triangle corresponding to $Q$. Verify that it
398
really does have area $6$.
399
400
\end{enumerate}
401
\end{enumerate}
402
403
\end{itemize}
404
405
\item \research{}
406
\begin{itemize}
407
\item Say something about
408
perimeters of rational right triangles. Convert this question to
409
a question about solutions to some equation (as bove). Solve this other
410
equation. Give a systematic way to enumerate all rational right
411
triangles with given perimeter.
412
\end{itemize}
413
414
% \begin{itemize}
415
% \item Let $F(x,y)$ be a polynomial in two variables.
416
% We call each of the summands $x^i y^j$ appearing in $F$
417
% a {\em monomial}, and say it has degree $i+j$. The {\em degree} of
418
% $F$ is the largest degree of any monomial appear in $F$.
419
% The {\em homogenization} $G$ of $F$ is the polynomial in $x,y,z$
420
% got by multiplying each monomial appearing in $F$ by the power of $z$
421
% so that the degree of every monomial in $G$ is the same as the degree
422
% of $F$, e.g., the homogenization of $F = x^3 - 3 y^2 + 17x$ is
423
% $G = x^3 -3 y^2z + 17 xz^2$.
424
425
% \begin{enumerate}
426
% \item What is the degree of $x^3 + y^3 +1$? What is the
427
% degree of $x^3y^2 + xy - y^5$? What is the degree of $x^2y^2 + x^3 + 1$?
428
% \item What is the homogenization of $y^2 = x^3 - x$?
429
% What is the homogenization of $x^2y^2 + x^3 + 1$?
430
% What is the homogenization of $y^2 + y = x^3 + x^2 - 2x$?
431
% What is the homogenization of $y^2 = x^3 $?
432
%\end{enumerate}
433
% \end{itemize}
434
% \item \research{}
435
% \begin{itemize}
436
% \item "Rank" of elliptic curves (average, maximal)
437
% \item What about the points with $x=0$?
438
% \item What about when cubic has a double root
439
% (multiplicative or additive group).
440
% \end{itemize}
441
\end{itemize}
442
443
444
445
446
447
\newpage
448
\section{Elliptic Curve Groups}
449
\begin{enumerate}
450
\item (15 minutes) Presentation -- Perimeters of right triangles?
451
Patterns in congruent numbers modulo~$8$?
452
\item (30 minutes) Definition of a {\blue \em group}.
453
\begin{definition}
454
An {\red \bf abelian group}
455
is a set $X$ equipped with a binary operation $+$
456
and an element $0\in X$ such that for all $a,b,c \in X$,
457
\begin{enumerate}
458
\item (closure) $a+b \in X$,
459
\item (identity) $0 + a = a + 0 = a$,
460
\item (associativity) $a + (b + c) = (a + b) + c$,
461
\item (inverses) for every $a$ in $X$ there is $d$ such that $a+d = 0$,
462
\item (commutativity) $a + b = b + a$.
463
\end{enumerate}
464
\end{definition}
465
466
{\bf Examples:}
467
\begin{enumerate}
468
\item The {\red\bf integers} $\Z = \{0,-1,1,-2,2,-3,3,\ldots\}$ under addition.
469
\item The {\red\bf rational numbers} $\Q$ under addition.
470
\item The {\red\bf integers} $\{0,1,\ldots, n-1\}$ under {\red\bf addition
471
modulo $n$}.
472
\item Let $p$ be a prime. The {\red\bf integers} $\{1,\ldots, p-1\}$
473
under {\red\bf multiplication modulo $p$}.
474
This is called {\red $\F_p^*$}.
475
\end{enumerate}
476
477
478
\item (15 minutes) Experiment with some abelian groups in \sage.
479
480
\item (10 minutes) Break.
481
482
\newpage
483
\item (20 minutes) Definition of elliptic curve groups.
484
485
\begin{definition}
486
Fix integers $a$ and $b$.
487
Let {\red $E(\Q)$} be the set of solutions to $y^2 = x^3 + a x + b$
488
along with one ``extra point'' which we call $\cO$ which is
489
the additive $0$ element. This is an
490
abelian group (note: the associative law takes a {\em lot} of work to prove!).
491
\end{definition}
492
493
494
\item (30 minutes) Participants: Graph elliptic curves.
495
Then {\bf\blue derive an algebraic formula} (by hand) for the
496
group operation.
497
498
\item (15 minutes) Elliptic curves modulo $p$.
499
Fix integers $a$ and $b$ and a prime $p$.
500
Let {\red $E(\F_p)$} be the set of solutions to $y^2 \con x^3 + a x + b\pmod{p}$
501
with $0\leq x < p$ and $0\leq y < p$ along with a formal extra
502
point $\cO$. This group is central in both cryptography (in making
503
{\em and} cracking cryptosystems) and the Birch and Swinnerton-Dyer
504
conjecture! I will explain how in both cases next week.
505
506
\item (15 minutes) Participants:
507
Graph and compute with some elliptic curves modulo $p$.
508
509
\end{enumerate}
510
511
\newpage
512
\subsection{Elliptic Curves over $\Q$}
513
\begin{itemize}
514
\item \computation
515
\begin{itemize}
516
\item Play around with each of the above groups in \sage.
517
Here are examples of how to compute with each of the
518
groups listed above in \sage{} to get you started.
519
Be creative and experiment!
520
\begin{verbatim}
521
sage: ZZ
522
Integer Ring
523
sage: a = ZZ(5); b = ZZ(7); a+b
524
12
525
526
sage: QQ
527
Rational Field
528
sage: QQ(3/4) + QQ(2/3)
529
17/12
530
531
sage: R = IntegerModRing(12)
532
sage: print R
533
Ring of integers modulo 12
534
sage: R(7) + R(8)
535
3
536
537
sage: R = FiniteField(7)
538
sage: print R
539
Finite Field of size 7
540
sage: R(4)*R(5)
541
6
542
\end{verbatim}
543
544
\item Compute with elliptic curves over $\Q$. Here
545
is an example to get you started.
546
\begin{verbatim}
547
sage: E = EllipticCurve([-36,0])
548
sage: E
549
Elliptic Curve defined by y^2 = x^3 - 36*x over Rational Field
550
sage: P = E([-3,9]) # or use E.gens(proof=False)
551
sage: P + P
552
(25/4 : -35/8 : 1)
553
\end{verbatim}
554
555
556
\item Draw some graphs of elliptic curves (using the new program
557
I just wrote!). Here
558
is an example to get you started:
559
\begin{verbatim}
560
sage: E = EllipticCurve([-36,0])
561
sage: P = plot(E,rgbcolor=(0,0,1))
562
sage: pnt = E([-3,9])
563
sage: pnt2 = 2*pnt
564
sage: c1 = point(pnt, pointsize=100)
565
sage: c2 = point(pnt2, rgbcolor=(1,0,0), pointsize=100)
566
sage: show(P + c1 + c2)
567
\end{verbatim}
568
%\item
569
%Write a program that outputs 20 rational right triangles
570
%with area $6$. Plot some of these.
571
\end{itemize}
572
\item \theory{}
573
\begin{itemize}
574
%\item The group has a point $(x,y)$ with $y\neq 0$ if and only if $n$ is
575
%a congruent number.
576
%\item Geometric proof that composition law is associative
577
%[for people who love geometry -- [[copy the argument from Silverman-Tate
578
%here]]]
579
\item
580
Let $E$ be an elliptic curve
581
given by an equation $y^2=x^3+ax+b$.
582
Prove that the following steps can be used to compute
583
$+$ on $E$: Given $P_1, P_2$,
584
this algorithm computes the third point $R=P_1+P_2$.
585
\begin{enumerate}
586
\item{}[Is $P_i=\O$?] If $P_1=\O$ set $R=P_2$ or if $P_2=\O$ set $R=P_1$
587
and terminate. Otherwise write $(x_i,y_i)=P_i$.
588
\item{}[Negatives] If $x_1 = x_2$ and $y_1 = -y_2$, set $R=\O$ and terminate.
589
\item{}[Compute $\lambda$]\label{alg:grouplaw_3}
590
Set $\ds \lambda = \begin{cases}
591
(3x_1^2+a)/(2y_1) & \text{if }P_1 = P_2,\\
592
(y_1-y_2)/(x_1-x_2) & \text{otherwise.}
593
\end{cases}$\\
594
\item{}[Compute Sum]\label{alg:grouplaw_4} Then
595
$R = \ds \left(\lambda^2 -x_1 - x_2, -\lambda x_3 - \nu\right)$,
596
where $\nu = y_1 - \lambda x_1$ and $x_3=\lambda^2 -x_1 - x_2$
597
is the $x$-coordinate of $R$.
598
\end{enumerate}
599
\end{itemize}
600
\item \research{}
601
\begin{itemize}
602
\item Using the Internet find two web pages that define abelian
603
groups. Understand the definitions (perhaps by copying them down
604
onto a piece of paper). Do they agree with the definition
605
that I gave above?
606
%\item It is true that if $n$ is a congruent number, there are infinitely
607
% many distinct rational right triangles with area $n$.
608
\end{itemize}
609
610
\end{itemize}
611
612
613
\subsection{Elliptic Curves Modulo $p$}
614
Definition, arithmetic, point enumeration,
615
elliptic curve cryptography (discrete log problem; diffie-hellman).
616
617
\begin{itemize}
618
\item \computation
619
\begin{itemize}
620
\item Compute with elliptic curves modulo a prime $p$. Here
621
is an example to get you started.
622
\begin{verbatim}
623
sage: E = EllipticCurve(FiniteField(43), [-36,0])
624
sage: E
625
Elliptic Curve defined by y^2 = x^3 + 7*x over Finite Field of size 43
626
sage: P = E([-3,9])
627
sage: P + P
628
(17 : 1 : 1)
629
\end{verbatim}
630
\item Graph some elliptic curves modulo $p$:
631
\begin{verbatim}
632
sage: E = EllipticCurve(FiniteField(13), [-36,0])
633
sage: P = plot(E,rgbcolor=(0,0,1),pointsize=100)
634
sage: P.show(dpi=200)
635
\end{verbatim}
636
\end{itemize}
637
638
% \begin{itemize} \item draw graphs of the groups (set of all points)
639
% \item compute group law explicitly (and graph the cycle get
640
% by adding one point over and over).
641
% \item number of points over $\F_p$ for lots of $p$ (the Sato-Tate
642
% distribution).
643
% \item Hasse bound (proof beyond scope, but statement is easy, and numerical
644
% evidence is too).
645
% \end{itemize}
646
\item \theory{}
647
\begin{itemize}
648
\item Given $P$ and a positive integer $n$, it is fairly
649
straightforward to compute $nP = P + P + \cdots + P$. Given
650
$P$ and $Q$ where you know that $Q=nP$ for some $n$ (even
651
though you don't know $n!$), invent a way to find $n$ (it
652
doesn't have to be fast).
653
\end{itemize}
654
% \item \research{}
655
% \begin{itemize}
656
% \item Discrete log problem.
657
% \item Diffie-hellman and El Gammal cryptosystem -- see Sandor's talks later.
658
% \end{itemize}
659
\end{itemize}
660
661
662
\newpage
663
\section{The Birch and Swinnerton-Dyer Conjecture (Monday)}
664
\begin{center}
665
\includegraphics[bb=0 0 550 300 height=13em, width=25em]{graphics/swinnerton_dyer-count.png}
666
\end{center}
667
\begin{enumerate}
668
\item (15 minutes) Congruent number problem; connected
669
to elliptic curves; we need to understand when elliptic curves
670
have points on them.
671
\item (15 minutes) Daily crashing of the SAGE Notebook -- some
672
improvements I made over the weekend: computing \code{E.points()}
673
for $E$ an elliptic curve modulo~$p$ is now very fast; the Notebook
674
interface is generally more robust and much easier to interrupt;
675
\code{foo??} gives source code even for functions you enter or in
676
cong.sage if you do \code{attach cong.sage}; can write, e.g.,
677
\code{plot(..., hue=...)} instead of \code{plot(...,
678
rgbcolor=hue(...))}. So please, right now, {\red try hard to
679
``crash'' your personal SAGE Notebook}, i.e., get it in an
680
unresponsive state. Don't worry, I can easily restart all of them.
681
\item {\blue\bf The Conjecture}.
682
The Birch and Swinnerton-Dyer conjecture was made in the 1960s
683
based on numerical computations carried out on EDSAC:
684
\includegraphics[bb=0 0 300 180]{graphics/edsac.png}
685
686
Let $n$ be a positive square-free integer. This means
687
that no perfect square divides $n$.
688
Let $E_n$ be the elliptic curve $$E_n: \quad y^2 = x^3 - n^2x.$$
689
If $n$ is odd, let $N = 32n^2$, and if $n$
690
is even, let $N=16n^2$. The number $N$ is called
691
the {\blue\em conductor of $E_n$}.
692
693
For any prime $p\nmid 2n$,
694
let
695
$$
696
a_p = p + 1 - \#E_n(\F_p),
697
$$
698
where $\#E_n(\F_p)$ is the number of points on the elliptic curve
699
$E_n$ viewed modulo $p$.
700
If $p\mid 2n$, let $a_p = 0$.
701
If $m, r$ are coprime integers, let $a_{mr} = a_m a_r$.
702
If $p\nmid 2n$ let $a_{p^r} = a_{p^{r-1}} a_p - p a_{p^{r-2}}$,
703
and if $p\mid 2n$ let $a_{p^r} = 0$.
704
Finally, let
705
$$
706
L(E_n,1) = \begin{cases}
707
0 & \text{if $n\con 5,6,7\pmod{8}$}\\
708
\ds 2 \cdot \sum_{k=1}^{\infty} \frac{a_k}{k} \cdot e^{-2\pi k/\sqrt{N}} & \text{otherwise}.
709
\end{cases}
710
$$
711
\begin{conjecture}[Birch and Swinnerton-Dyer]\mbox{}\vspace{-4ex}\\
712
\begin{center}
713
We have $L(E_n,1) = 0$ if and only if $E_n(\Q)$ is infinite.
714
\end{center}
715
\end{conjecture}
716
(Stated in a special cases.)
717
718
This is a {\em\red major open problem} in number theory. {\em If
719
I don't solve this problem, I hope one of you does!}
720
721
\begin{proof}[Heuristic ``Proof'']
722
(This is a {\em\red\bf fake} ``proof''.)
723
If $E_n(\Q)$ is infinite then the numbers $\#E_n(\F_p)$ will
724
tend to be {\em\large big}, since you get lots of elements
725
of $E_n(\F_p)$ by reducing the elements of $E_n(\Q)$
726
modulo $p$. Thus $a_p = p+1 - \#E_n(\F_p)$ will tend
727
to be {\em small}. One can prove that $L(E_n,1)\geq 0$,
728
so if the $a_p$ are small, that will ``cause'' the
729
sum that defines $L(E_n,1)$ to be small, i.e., $0$.
730
Conversely if $L(E_n,1)=0$, then the $E_n(\F_p)$ are big,
731
and the points have to come from somewhere so $E_n(\Q)$
732
is big.
733
\end{proof}
734
735
\begin{theorem}[Kolyvagin et al.]
736
If $E_n(\Q)$ is infinite then $L(E_n,1)=0$.
737
\end{theorem}
738
This is one direction in the conjecture, and the
739
proof is {\em very very difficult}. Put another way,
740
this theorem says that if $L(E_n,1)\neq 0$, then $E_n(\Q)$ is finite.
741
742
743
As the notation suggests, $L(E_n,1)$ is the value
744
of a function at $1$. I will not define the general
745
function, but here are some plots of $L(E_n,s)$ for
746
various $n$:
747
\par
748
749
{\hspace{-6em}\noindent$n=1$\includegraphics[bb=0 0 180 150]{graphics/lser1.png}
750
$n=6$\includegraphics[bb=0 0 180 150]{graphics/lser6.png}}
751
752
{\hspace{-6em}$n=34$\includegraphics[bb=0 0 180 150]{graphics/lser34.png}
753
$n=4199$\includegraphics[bb=0 0 180 150]{graphics/lser4199.png}}
754
755
I made them using code like
756
\begin{verbatim}
757
E = EllipticCurve([-6^2,0])
758
L = E.Lseries_dokchitser()
759
P = plot(L,0.5,1.5, plot_points=50, plot_division=50,
760
rgbcolor=(0,0,1), thickness=2)
761
\end{verbatim}
762
763
764
\item Participants -- do the following for $n=1$ and $n=34$:
765
\begin{enumerate}
766
\item Write down $E_n$.
767
\item Find the conductor $N$ of $E_n$.
768
\item Compute (by hand/with computer) $a_1, a_2, a_3, a_4$, and $a_5$.
769
Check your answer with \sage (use {\tt E.an(m)} to compute $a_m$).
770
The point here is to spend some time understanding the
771
definition of $a_m$.
772
\item Compute the first $5$ terms in the sum
773
that defines $L(E_n,1)$.
774
775
(You should find that for
776
$n=34$ we have $L(E_{34},1)=0$, whereas for $n=1$ we
777
have $L(E_{1},1)\neq 0$.)
778
\begin{verbatim}
779
sage: E = EllipticCurve([-1^2,0])
780
sage: E.Lseries(1)
781
0.65551438857302990
782
783
sage: E = EllipticCurve([-34^2,0])
784
sage: E.Lseries(1)
785
-0.0000000000000000... (the nonzeros at the end are just errors/noise)
786
\end{verbatim}
787
788
\item The following SAGE program can be used to compute the
789
sum that defines $L(E_n,1)$ using any number of terms.
790
\begin{verbatim}
791
def L(n, prec):
792
E = EllipticCurve([-n^2,0])
793
v = E.anlist(prec)
794
N = E.conductor()
795
sqrtN = sqrt(N)
796
lval = 2*sum(v[n]/n*exp(-2*pi*n/sqrtN) for n in range(1,prec))
797
return lval
798
\end{verbatim}
799
Note: This function is in {\tt cong.sage}. Just type
800
\code{attach cong.sage} if you haven't already and it
801
will magically be available. Then you can enter
802
\code{L?} for help and \code{L??} for source code.
803
\end{enumerate}
804
805
806
807
\item Participants -- Prove using SAGE calculations and the BSD
808
conjecture that none of $1,2,3,4$ are congruent numbers.
809
\item Participants -- Try to find patterns, any at all,
810
in the numbers $$p+1-\#E_n(\F_p)$$
811
for the congruent number curves $y^2 = x^3 - n^2x$.
812
E.g., fix $n=1$ and compute these numbers for
813
primes up to some bound:
814
\begin{verbatim}
815
E = EllipticCurve([-1,0])
816
for p in primes(2,100):
817
print p, E.ap(p)
818
\end{verbatim}
819
\end{enumerate}
820
\begin{itemize}
821
\item \computation
822
\begin{itemize}
823
\item This \sage code
824
draws the plot below. Try different curves, ranges of primes, etc.
825
\begin{verbatim}
826
n = 6
827
def pl(p):
828
return plot(EllipticCurve(GF(p),[-n^2,0]), rgbcolor=hue(0.7))
829
830
P = [pl(p) for p in primes(5,100) if n%p != 0]
831
Q = [[P[4*i+j] for j in range(4)] for i in range(len(P)/4)]
832
show(graphics_array(Q))
833
# show(graphics_array(Q), axes=False) # if you don't want axes
834
\end{verbatim}
835
{\hspace{-10.5em}\includegraphics[bb=0 0 450 350]{graphics/points_mod_p.png}}
836
837
%\item Verify using \sage that $N_p = p+1$ for $p\con 3\pmod{4}$ with
838
%$p<1000$, where $N_p$ is the number of points on $y^2 = x^3 - x$
839
%over $\F_p$. (Helpful hint to get you going below.)
840
%\begin{verbatim}
841
%for p in primes(20):
842
% print p, E.Np(p)
843
%\end{verbatim}
844
845
\item Make a table of values $L(E_n,1)$ for each integer $n< 50$.
846
How does this compare to the table of congruent numbers $n<50$.
847
[Here's how to {\em approximately} compute $L(E,1)$ in SAGE:]
848
849
\item In this problem $n$ {\em always} denotes a squarefree
850
positive integer $n$ (i.e., no perfect squares divide $n$).
851
\begin{enumerate}
852
\item If $n\con 5,6,7\pmod{8}$ then does
853
the Birch and Swinnerton-Dyer conjecture imply that
854
$n$ is a congruent number?
855
\item Are there {\em any} integers $n \con 3\pmod{8}$ with $n$ a
856
congruent number?
857
\begin{verbatim}
858
EllipticCurve([-1,0]).Lseries(1)
859
\end{verbatim}
860
\end{enumerate}
861
\end{itemize}
862
863
\item \theory{}
864
\begin{itemize}
865
%\item Prove that $N_p = p+1$ for $p\con 3\pmod{4}$.
866
\item What is the relationship between the
867
$a_p$ for $E_1$ and $E_6$? Make a conjecture based
868
on numerical evidence. Note: you can compute
869
$a_p$ using {\tt E.ap(p)}, e.g.,
870
\begin{verbatim}
871
E = EllipticCurve([-1,0])
872
for p in primes(10):
873
print p, E.ap(p)
874
\end{verbatim}
875
Can you say anything about the relation between the
876
$a_p$ for $E_1$ and for $E_n$ for general $n$?
877
\end{itemize}
878
879
\item \research{}
880
\begin{itemize}
881
\item Find Andrew Wiles's paper on the Birch and Swinnerton-Dyer
882
conjecture at the Clay Math Institute web site
883
\url{http://www.claymath.org/millennium/} and read as much of it
884
as you can. One of their pages says:
885
\begin{quote}
886
``Mathematicians have always been fascinated by the problem of describing all solutions in whole numbers $x,y,z$ to algebraic equations like
887
$$
888
x^2 + y^2 = z^2.
889
$$
890
891
Euclid gave the complete solution for that equation, but for more
892
complicated equations this becomes extremely difficult. Indeed, in
893
1970 Yu. V. Matiyasevich showed that Hilbert's tenth problem is
894
unsolvable, i.e., there is no general method for determining when such
895
equations have a solution in whole numbers. But in special cases one
896
can hope to say something. When the solutions are the points of an
897
abelian variety, the Birch and Swinnerton-Dyer conjecture asserts that
898
the size of the group of rational points is related to the behavior of
899
an associated zeta function $L(s)$ near the point $s=1$. In
900
particular {\em\blue this amazing conjecture asserts that if $L(1)$ is equal
901
to $0$, then there are an infinite number of rational points
902
(solutions), and conversely, if $L(1)$ is not equal to 0, then
903
there is only a finite number of such points.}''
904
905
\end{quote}
906
907
\item Noam Elkies web page
908
\url{http://www.math.harvard.edu/\~{ }elkies/compnt.html}
909
has the most extensive data I've seen about congruent numbers.
910
Check it out!
911
912
\item EDSAC -- search for information online about the
913
EDSAC computer.
914
\end{itemize}
915
\end{itemize}
916
917
\newpage
918
\section{Square Triangles and Fermat's Last Theorem (Wed morning)}
919
920
The numbers $1$, $2$, $3$, and $4$ are not congruent numbers. In
921
particular, $1$ is not. I.e., there is not rational right triangle
922
whose area is a perfect square, i.e., there are no ``square
923
triangles''.
924
925
\begin{enumerate}
926
\item (60 minutes) Watch the Fermat's Last Theorem movie.
927
\item (10 minutes) Move to computer lab / break.
928
\item (10 minutes) Recall that we ``know'' $1$ is not a congruent
929
number from Monday, since $L(E_1, 1) = 0.65551\ldots \neq 0$. But that
930
uses a deep theorem (the proof by Kolyvagin of one direction
931
of the Birch and Swinnerton-Dyer conjecture).
932
\item (70 minutes) Prove Fermat's Last Theorem for $n=4$, and use this
933
to deduce that $1$ is not a congruent number.
934
\end{enumerate}
935
936
\begin{itemize}
937
\item \computation
938
\begin{itemize}
939
\item Via a direct computer search, show there are no right triangles
940
with area $1$ and rational side lengths $(a,b,c)$ (with $c$ the
941
hypotenuse) with the number of digits of the numerators and
942
denominators of $a$, $b$, $c$ all $<100$ in absolute value.
943
\item Look for solutions to $y^2=x^3-x$ with both $x,y$ rational and
944
$y\neq 0$. Fail to find any.
945
\end{itemize}
946
\item \theory{} You {\em\red definitely} want to work together on these
947
problems, even possibly dividing up into groups and assigning parts
948
to different groups, and also having people search online for help
949
(which is allowed). Make solving all these nicely a community
950
effort. [Credit: This sequence of problems was originally written
951
by the Baur Bektemirov (the first ever winner
952
of the International Math Olympiad gold medal from Kazakhstan),
953
while he was a freshman at Harvard working with me.]
954
\begin{enumerate}
955
\item\label{ex:pythag} Suppose $a$, $b$, $c$ are relatively prime
956
integers with $a^2+b^2=c^2$. Then there exist integers $x$ and $y$
957
with $x>y$ such that $c=x^2+y^2$ and either $a=x^2-y^2$, $b=2xy$ or
958
$a=2xy$, $b=x^2-y^2$. Hint: Recall what we did on day 1
959
where we parametrized Pythagorean triples $a,b,c$:
960
\begin{center}
961
\mbox{\hspace{-8em}\includegraphics[bb=0 0 400 250 width=0.8\textwidth]{graphics/pythag.png}}
962
\end{center}
963
964
965
\item\label{ex:flt4} Fermat's Last Theorem for exponent $4$ asserts
966
that any solution to the equation $x^4+y^4=z^4$ with $x,y,z\in\Z$
967
satisfies $xyz=0$. Prove Fermat's Last
968
Theorem for exponent $4$, as follows.
969
\begin{enumerate}
970
\item Show that if the equation $x^2+y^4=z^4$ has no integer
971
solutions with $xyz\neq 0$, then Fermat's Last Theorem for exponent~$4$
972
is true. (Note -- the power of $x$ is $2$.)
973
\item Prove that $x^2+y^4=z^4$ has no integer solutions with $xyz\neq 0$
974
as follows.
975
Suppose $n^2+k^4=m^4$ is a solution with $m>0$ minimal amongst
976
all solutions. Show that there exists a solution with $m$ smaller
977
using the previous exercise above (consider two cases).
978
\end{enumerate}
979
980
\item Prove that 1 is not a congruent number by showing that
981
the cubic curve $y^2=x^3-x$ has no rational solutions
982
except $(0,\pm 1)$ and $(0,0)$:
983
\begin{enumerate}
984
\item Write $y=\frac{p}{q}$ and $x=\frac{r}{s}$, where $p,q,r,s$ are
985
all positive integers and $\gcd(p,q)=\gcd(r,s)=1$. Prove that $s\mid
986
q$, so $q=sk$ for some $k\in\Z$.
987
\item Prove that $s=k^2$, and substitute to see that
988
$p^2=r^3-rk^4$.
989
\item Prove that $r$ is a perfect square by supposing
990
that there is a prime~$\ell$ such that $\ord_{\ell}(r)$ is
991
odd and analyzing $\ord_{\ell}$ of both sides of
992
$p^2=r^3-rk^4$.
993
\item Write $r=m^2$, and substitute to
994
see that $p^2=m^6-m^2k^4$. Prove that $m\mid p$.
995
\item Divide through by $m^2$ and deduce a contradiction to the
996
previous exercise.
997
\end{enumerate}
998
999
\end{enumerate}
1000
\end{itemize}
1001
1002
1003
\newpage
1004
\section{An Elementary Criterion (Thursday)}
1005
1006
\begin{enumerate}
1007
\item ($<1$ hour) -- Student presentations: proof of FLT for exponent 4 and
1008
no square triangles.
1009
\item (10 minutes) -- break
1010
\item (30 minutes) -- statement of Tunnell's criterion.
1011
Let $$\Theta(q) = 1 + 2\sum_{m\geq 1} q^{m^2} =
1012
1 + 2q + 2q^{4} + 2q^{9} + \cdots.$$
1013
Let
1014
$$f_1 = \Theta(q)\cdot (2\Theta(q^{32}) - \Theta(q^8))\cdot \Theta(q^2)$$
1015
and
1016
$$f_2 = \Theta(q) \cdot (2\Theta(q^{32}) - \Theta(q^8))\cdot \Theta(q^4).$$
1017
\begin{theorem}[Waldspurger, Tunnell]\label{thm:tunnell}
1018
Suppose $n$ is a squarefree integer. If $n$ is odd
1019
then $L(E_n,1)=0$ if and only if the $n$th coefficient
1020
of $f_1$ is $0$. If $n$ is even then $L(E_n,1)=0$
1021
if and only if the $\frac{n}{2}$th coefficient of $f_2$ is $0$.
1022
\end{theorem}
1023
This is a {\bf\blue very deep theorem}. It allows us to determine
1024
whether or not $L(E_n,1)=0$.
1025
The Birch and Swinnerton-Dyer conjecture (which is not
1026
a theorem) then asserts that $L(E_n,1)=0$ if and only if $n$
1027
is a congruent number. Thus once enough of the
1028
Birch and Swinnerton-Dyer conjecture is proved, we'll have
1029
an elementary way to decide whether or not a (squarefree)
1030
integer $n$ is a congruent number. Namely,
1031
if $n$ is odd then (conjecturally) $n$ is a congruent number
1032
if and only if
1033
$$\#\left\{x,y,z\in\Z \,:\, 2x^2 + y^2 + 32z^2 = n\right\}
1034
= \frac{1}{2} \#\left\{x,y,z\in\Z \,:\, 2x^2 + y^2 + 8z^2 = n\right\}.
1035
$$
1036
Simiarly,
1037
if $n$ is even then (conjecturally) $n$ is a congruent number
1038
if and only if
1039
$$\#\left\{x,y,z\in\Z \,:\, 4x^2 + y^2 + 32z^2 = \frac{n}{2}\right\}
1040
= \frac{1}{2} \#\left\{x,y,z\in\Z \,:\, 4x^2 + y^2 + 8z^2 = n\right\}.
1041
$$
1042
1043
1044
\item (30 minutes) -- exercises with Tunnell's criterion.
1045
\begin{enumerate}
1046
\item Come up with a method to explicitly list
1047
each of the above sets.
1048
1049
\item Prove that the elementary criterion (involving cardinality of
1050
sets) implies that none of $n=1,2,3,4$ are congruent numbers.
1051
1052
\item Prove that the elementary criterion (involving cardinality of
1053
sets) implies that $n=5,6,7$ are congruent numbers. Then find
1054
a right triangle with area $5$.
1055
1056
\item Verify with \sage that Theorem~\ref{thm:tunnell} (appears to)
1057
hold for $n<20$. Hint: The command
1058
\begin{verbatim}
1059
f1, f2 = tunnell_forms(30)
1060
\end{verbatim}
1061
computes the $f_1$ and $f_2$ defined above, and e.g., \code{f1[3]}
1062
returns the coefficient of $q^3$.
1063
1064
\item {\bf Question (Nathan Ryan):} Is it possible to decide whether
1065
or not a prime number $p$ is a (conjectural) congruent number in
1066
time polynomial in the number of digits of $p$? I.e., if $p$ has a
1067
hundred digits is there any hope we could tell whether or not $p$ is
1068
(conjecturally) a congruent number i a reasonable amount of time?
1069
[[{\bf\red WARNING: This is an unsolved problem, as far as I
1070
know.}]]
1071
\end{enumerate}
1072
1073
\end{enumerate}
1074
1075
1076
1077
\newpage
1078
\section{Square Triangles Revisited}
1079
Since there was so much trouble with the proof of Fermat for exponent
1080
$4$, let's revisit it. First, Fermat's proof:
1081
\begin{quote}
1082
``if the area of a rational right triangle were a square, then
1083
there would also be a smaller one with the same property, and so on,
1084
which is impossible.''
1085
\end{quote}
1086
OK, that wasn't so helpful.
1087
Anyway, we did everything on Thursday except 2b, i.e.,
1088
suppose that $n^2 + k^4 = m^4$ is a solution in positive
1089
integers to the equation $x^2 + y^4 = z^4$ with $m>0$
1090
minimal among all possible solutions. Show that there is a
1091
a smaller solution, hence deduce a contradiction.
1092
\begin{enumerate}
1093
\item Case 1: If $n$ is even then there exist integers $x,y\geq 0$
1094
(with $x>y$) such that
1095
$$n = 2xy\qquad k^2 = x^2 - y^2 \qquad m^2 = x^2 + y^2.$$
1096
Then
1097
$$
1098
(mk)^2 = x^4 - y^4,
1099
$$
1100
from which we obtain a smaller solution.
1101
1102
\item Case 2: Next assume $n$ is odd. The trick is to proceed as
1103
above, but to apply exercise 1 again to the Pythagorean triple $m^2
1104
= x^2 + y^2$ and note that various numbers are perfect squares. We
1105
give full details below.
1106
1107
There are integers $x,y$ with $x>y$ such that
1108
$$n = x^2 - y^2\qquad k^2 = 2xy \qquad m^2 = x^2 + y^2.$$
1109
1110
Since $2xy=k^2$ is a perfect square we can write
1111
either $x=u^2$, $y=2v^2$ or $x=2u^2$, $y=v^2$ for integers
1112
$u,v$.
1113
1114
\begin{enumerate}
1115
\item Case: We have $x=u^2, y=2v^2$, i.e., $y$ is even and
1116
$x$ is odd (note that $x$ must be odd if $y$ is even
1117
since $n=x^2-y^2$ is odd).
1118
Since $m^2 = x^2 + y^2$ is itself a Pythagorean
1119
triple with $x$ odd, we can again apply exercise 1 to find coprime
1120
integers $a,b$ such that
1121
$$
1122
x = a^2 - b^2\qquad y = 2ab\qquad z = a^2 + b^2.
1123
$$
1124
Then $2v^2 = y = 2ab$, so since $a,b$ are coprime we have
1125
$a = d^2$, $b=e^2$ for integers $d,e$.
1126
Since $x=u^2$ and $x=a^2-b^2$, we have
1127
$$
1128
u^2 = d^4 - b^4,
1129
$$
1130
which yields a smaller solution to $x^2 + y^4 = z^4$.
1131
\item Case: We have $x=2u^2, y=v^2$, i.e., $y$ is odd and
1132
$x$ is even (note that $y$ must be odd if $x$ is even
1133
since $n=x^2-y^2$ is odd).
1134
Since $m^2 = x^2 + y^2$ is itself a Pythagorean
1135
triple with $y$ odd, we can again apply exercise 1 to find coprime
1136
integers $a,b$ such that
1137
$$
1138
y = a^2 - b^2\qquad x = 2ab\qquad z = a^2 + b^2.
1139
$$
1140
Then $2u^2 = x = 2ab$, so since $a,b$ are coprime and
1141
have square product we have
1142
$a = d^2$, $b=e^2$ for integers $d,e$.
1143
Since $y=v^2$ and $y=a^2-b^2$, we have
1144
$$
1145
v^2 = d^4 - b^4,
1146
$$
1147
which yields a smaller solution to $x^2 + y^4 = z^4$.
1148
1149
\end{enumerate}
1150
1151
\end{enumerate}
1152
1153
1154
\newpage
1155
\section{An Elliptic Curve Cryptography (ECC) Tutorial}
1156
Elliptic curves are useful far beyond the fact that they shed a huge
1157
amount of light on the congruent number problem. For example, many
1158
people (probably you!) use them on a daily basis, since they are used
1159
to make some of the best public-key cryptosystems (= methods for
1160
sending secret data).
1161
1162
1163
I think the Wikipedea opening description of Elliptic curve
1164
cryptography is OK (no comment about the rest of the article):
1165
\begin{quote}
1166
Elliptic curve cryptography (ECC) is an approach to public-key
1167
cryptography based on the algebraic structure of elliptic curves
1168
over finite fields. The use of elliptic curves in cryptography was
1169
suggested independently by Neal Koblitz [1] and Victor S. Miller [2]
1170
in 1985.
1171
1172
Elliptic curves are also used in several integer factorization
1173
algorithms that have applications in cryptography, such as, for
1174
instance, Lenstra elliptic curve factorization, but this use of
1175
elliptic curves is not usually referred to as "elliptic curve
1176
cryptography."
1177
1178
[...] As for other popular public key cryptosystems, no mathematical
1179
proof of difficulty has been published for ECC as of 2006. However,
1180
the U.S. National Security Agency has endorsed ECC technology by
1181
including it in its Suite B set of recommended algorithms. Although
1182
the RSA patent has expired, there are patents in force covering some
1183
aspects of ECC.
1184
\end{quote}
1185
Note: Neal Koblitz is a math professor here at UW. He wrote the book
1186
on the congruent number problem (I scanned some of it for the
1187
website). You might see him around this summer, since he's teaching a
1188
summer school class.
1189
\begin{center}
1190
\includegraphics[bb=0 0 75 100]{graphics/koblitz.png}
1191
\end{center}
1192
1193
{\bf \blue Basic Problem:} {\em How can people or computers send
1194
secret messages to each other without having to send out passwords
1195
ahead of time? How did mathematicians put the guys with briefcases
1196
handcuffed to their hands out of business?}
1197
1198
Sandor Kovacs will go into great detail about this question in
1199
his course, and you might view today as a preview of some of what
1200
he'll do, with the bonus that today you get to try it out on a
1201
computer. Today I'll just give you the chance to {\em understand and
1202
play with} one example that addresses this basic problem.
1203
1204
\subsection{Elliptic Curves Modulo $p$}
1205
Let $p$ be a prime number. Consider an equation
1206
$y^2 = x^3 + ax + b$ with
1207
$$a,b \in \F_p = \{0,1,\ldots, p-1\} \qquad\text{(integers modulo $p$)}$$
1208
such that the cubic $x^3 + ax + b$ has distinct roots.
1209
The group of points on $E$ modulo $p$ is
1210
$$
1211
E(\F_p) = \{(x,y)\in \F_p \times \F_p : y^2 = x^3 +ax + b\} \union \{\cO\}.
1212
$$
1213
1214
{\bf Exercise:} Make up several ``random'' elliptic curves over
1215
various random $\F_p$'s in \sage (so {\em not} related to the
1216
congruent number problem!). List their points. Plot them. Do a
1217
little arithmetic with them. Here is some code to get you
1218
started.\vspace{1ex}
1219
1220
\noindent{}Finding a random prime $<1000$:
1221
\begin{verbatim}
1222
sage: next_prime(randrange(1000))
1223
137
1224
\end{verbatim}
1225
Making up a random curve:
1226
\begin{verbatim}
1227
sage: p = 137
1228
sage: F = FiniteField(p)
1229
sage: E = EllipticCurve(F, [F.random_element(), F.random_element()])
1230
sage: print E
1231
Elliptic Curve defined by y^2 = x^3 + 45*x + 43 over Finite Field of size 137
1232
\end{verbatim}
1233
List all points:
1234
\begin{verbatim}
1235
sage: E.points()
1236
[(0 : 1 : 0), (51 : 90 : 1), (57 : 92 : 1), (90 : 34 : 1), ...
1237
\end{verbatim}
1238
Make a plot:
1239
\begin{verbatim}
1240
sage: show(plot(E, hue=.9))
1241
\end{verbatim}
1242
Do some arithmetic:
1243
\begin{verbatim}
1244
sage: P = E.points()[1] # first point listed above
1245
sage: P
1246
(51 : 90 : 1)
1247
sage: P + P
1248
(57 : 92 : 1)
1249
sage: 10*P
1250
(131 : 105 : 1)
1251
sage: 9393*P
1252
(129 : 26 : 1)
1253
\end{verbatim}
1254
1255
1256
\subsection{Computing $nQ$ }
1257
Recall from yesterday that computers can compute $a^m \pmod{n}$ very
1258
quickly, even if $m$ is {\bf huge}. They do this by writing $n$
1259
in binary and doing a few squares and multiplies. Likewise,
1260
we can compute $nQ$ quickly when $Q$ is a point on an elliptic
1261
curve modulo $p$. Try it out!
1262
\begin{verbatim}
1263
sage: p = 137
1264
sage: F = FiniteField(p)
1265
sage: E = EllipticCurve(F, [F.random_element(), F.random_element()])
1266
sage: P = E.random_element()
1267
sage: print P
1268
(96 : 94 : 1)
1269
1270
sage: time 102000823098320*P
1271
(86 : 60 : 1)
1272
CPU time: 0.12 s, Wall time: 0.13 s
1273
1274
sage: show(plot(P) + plot(102000823098320*P,rgbcolor=(1,0,0)))
1275
[[a plot]]
1276
\end{verbatim}
1277
Now try with an elliptic curve over a huge field.
1278
\begin{verbatim}
1279
sage: p = next_prime(randrange(10^40))
1280
sage: print p
1281
sage: F = FiniteField(p)
1282
sage: E = EllipticCurve(F, [F.random_element(), F.random_element()])
1283
sage: P = E.random_element()
1284
sage: print P
1285
554146695875703931136550843186162763121
1286
(493257625218361211096484901389666856690 :
1287
286863248034562484128552069228984577311 :
1288
1)
1289
\end{verbatim}
1290
Then multiply...
1291
\begin{verbatim}
1292
sage: time 909238403284092384209482038402*P
1293
(151371634043111300277840422027192273952 :
1294
333732213371771487412281506530764174375 :
1295
1)
1296
CPU time: 0.20 s, Wall time: 0.21 s
1297
\end{verbatim}
1298
1299
\subsection{Diffie-Hellman -- a way to create a shared secret}
1300
The Diffie-Hellman key exchange was the first ever public-key
1301
cryptosystem. We will try it out on a elliptic curve here
1302
(note: it can also be used directly in $\F_p^* = \{1,\ldots, p-1\}$,
1303
as you will learn in Sandor's course).
1304
1305
Public key cryptography involves three ``people'':
1306
\begin{itemize}
1307
\item Person 1 -- traditionally named Alice
1308
\item Person 2 -- traditionally named Bob
1309
\item Person 3 -- traditionally called The Adversary
1310
\end{itemize}
1311
1312
\begin{enumerate}
1313
\item Break up into groups of (at least) 3. Choose at least person to
1314
be Alice\footnote{Even a guy could be ``Alice'', e.g., there is a
1315
guy named Alice Cooper from Phoenix, AZ.}, at least one to be
1316
Bob\footnote{Are there any famous women named Bob?}, and one to be
1317
the Adversary. Each person should have a computer terminal open to
1318
their SIMUW SAGE notebook. Open a common SAGE worksheet that all
1319
three of you can see and use to post messages (by refreshing the
1320
page). I'll explain how to do this.
1321
1322
\item In this exercise Alice and Bob will agree on a secret key
1323
by sending message {\em in full view} of everybody else. Of course,
1324
what they do at there computers gets kept secret -- only the messages
1325
are public (in particular, Adversary should not look at the crypto
1326
worksheets of Alice and Bob).
1327
1328
\item Alice: Choose a random prime $p$ and create a random
1329
elliptic curve modulo $p$, then choose a random point on this
1330
elliptic curve.
1331
\begin{verbatim}
1332
sage: load cong.sage # defines random_elliptic_curve command
1333
sage: E = random_elliptic_curve(next_prime(randrange(1000)))
1334
sage: print E
1335
Elliptic Curve defined by y^2 = x^3 + 508*x + 42 over Finite Field of size 577
1336
\end{verbatim}
1337
1338
\begin{verbatim}
1339
sage: P = E.random_element()
1340
sage: P
1341
(386 : 331 : 1)
1342
\end{verbatim}
1343
Finally, Alice has to tell everybody the random elliptic curve
1344
and the random point in such a way that Bob can define it
1345
on his computer. In the above example, just report that
1346
the prime is $47$, that the curve is \code{EllipticCurve([36,3])},
1347
and the point is $(5,4)$.
1348
1349
\item Bob: Choose a random integer $b$ (up to about $p$ in size)
1350
and compute $bP$ and tell everyone.
1351
\begin{verbatim}
1352
sage: b = randrange(1000); b
1353
549
1354
\end{verbatim}
1355
1356
\begin{verbatim}
1357
sage: b*P
1358
(472 : 340 : 1)
1359
\end{verbatim}
1360
1361
Announce $(83,362)$ to the world. But keep b secret.
1362
1363
\item Alice: Do the same thing as Bob, but with your own
1364
integer $a$.
1365
\begin{verbatim}
1366
sage: a = randrange(1000); a
1367
779
1368
1369
sage: a*P
1370
(54 : 426 : 1)
1371
\end{verbatim}
1372
1373
\item Now for the key exchange. At this point everybody
1374
should know $E$, $P$, $aP$ and $bP$. Only Alice knows
1375
$a$ and only Bob knows $b$. Alice computes $a(bP)$ and
1376
Bob computes $b(aP)$. The Adversary, not knowing $a$
1377
or $b$, sits there frustrated. Meanwhile Alice and Bob
1378
have agreed on a shared secret.
1379
\begin{verbatim}
1380
sage: b*(a*P)
1381
(260 : 99 : 1)
1382
1383
sage: a*(b*P)
1384
(260 : 99 : 1)
1385
\end{verbatim}
1386
1387
\item Nonetheless, since the numbers are so small, the
1388
adversary {\em can} figure out $a$. E.g.,
1389
\begin{verbatim}
1390
Q = P
1391
aP = E([54, 426])
1392
for n in range(1,1000):
1393
if Q == aP:
1394
print n
1395
break
1396
else:
1397
Q = Q + P
1398
\end{verbatim}
1399
NOTE: There are better methods than the above simplistic
1400
brute force approach. But even the better methods aren't
1401
very good.
1402
1403
\item Go through each of the above steps, but with a much
1404
larger prime $p$, e.g., with 40 digits (basically just
1405
change all the $1000$'s above to $10^{40}$'s). Note that
1406
it isn't noticeably slower. The only difference is
1407
that the Adversary's job is {\em \bf \red \large much harder}.
1408
\end{enumerate}
1409
1410
Once you have a shared secret, you can use it to encrypt a message in
1411
various ways, many very complicated. A very simple way is to simply
1412
add (modulo $10$ each digit of the shared secret key to the digits of
1413
your ``message'' (which we encode as a number).
1414
1415
\subsection{A serious cryptosystem that was deployed: MS-DRM}
1416
There is another famous elliptic curve cryptosystem
1417
that involves elliptic curves. Read about it in detail
1418
in Section 6.4.2 of my book, which is at \\
1419
{\tt http://modular.math.washington.edu/ent}.
1420
1421
%\subsection{Encoding a message as a list of points on a curve}
1422
%It is also possible to actually encode messages as points on
1423
1424
1425
1426
\end{document}
1427
1428