-
Notifications
You must be signed in to change notification settings - Fork 0
/
thesis.tex
301 lines (246 loc) · 12.4 KB
/
thesis.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
\documentclass [11pt, proquest] {thesis}[2015/03/03]
\setcounter{tocdepth}{1} % Print the chapter and sections to the toc
\include{macros}
%\usepackage{fullpage}
\usepackage{hyperref}
\usepackage{microtype}
\usepackage{mathtools}
\usepackage[usenames,dvipsnames]{color}
\usepackage[pdftex]{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{url}
%\usepackage{thmtools}
%\usepackage{thm-restate}
\includeonly{
chapters/1_introduction,
chapters/2_outline_and_results,
chapters/3_background,
chapters/4_main_theorem,
chapters/5_zero_sums,
chapters/6_remarks_future_work,
}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\qedb}{\hfill $\blacksquare$}
\newcommand{\nrm}[1]{\left\|#1\right\|}
\newcommand{\pr}{^{\prime}}
\newcommand{\Les}{L_E(s)}
\newcommand{\Lams}{\Lambda_E(s)}
\newcommand{\Lfs}{L(f,s)}
\newcommand{\ldLes}{\frac{L_E\pr}{L_E}(s)}
\newcommand{\ldLfs}{\frac{L_f\pr}{L_f}(s)}
\newcommand{\ldLe}[1]{\frac{L_E\pr}{L_E}\left(#1\right)}
\newcommand{\ldLf}[1]{\frac{L_f\pr}{L_f}\left(#1\right)}
\newcommand{\ldLam}[1]{\frac{\Lambda_E\pr}{\Lambda_E}\left(#1\right)}
\newcommand{\ldatzero}{\frac{L\pr(E,0)}{L(E,0)}}
\newcommand{\xbar}{\overline{x}}
\newcommand{\ybar}{\overline{y}}
\newcommand{\AGM}{\text{AGM}}
\newcommand{\conj}[1]{\overline{#1}}
\newcommand{\EQ}{E(\QQ)}
\newcommand{\EFp}{E(\Fp)}
\newcommand{\Ensfpe}{E_{\text{ns}}(\FF_{p^e})}
\newcommand{\softO}{\tilde{O}}
\newcommand{\en}[1]{\lVert #1 \rVert}
\DeclareMathOperator{\Li}{Li}
\DeclareMathOperator{\sinc}{sinc}
\usepackage{alltt} %
\newenvironment{demo}
{\begin{alltt}\leftskip3em
\def\\{\ttfamily\char`\\}%
\def\{{\ttfamily\char`\{}%
\def\}{\ttfamily\char`\}}}
{\end{alltt}}
\newtheorem{innercustomthm}{Theorem}
\newenvironment{quotedtheorem}[1]
{\renewcommand\theinnercustomthm{#1}\innercustomthm}
{\endinnercustomthm}
\newtheorem{innercustomcor}{Corollary}
\newenvironment{quotedcorollary}[1]
{\renewcommand\theinnercustomcor{#1}\innercustomcor}
{\endinnercustomcor}
\newtheorem{innercustomconj}{Conjecture}
\newenvironment{quotedconjecture}[1]
{\renewcommand\theinnercustomconj{#1}\innercustomconj}
{\endinnercustomconj}
% metafont font. If logo not available, use the second form
%
% \font\mffont=logosl10 scaled\magstep1
\let\mffont=\sf
% --- end-of-sample-stuff ---
\begin{document}
% ========== Preliminary pages
\prelimpages
%
% ----- copyright and title pages
%
\Title{The Zeros of Elliptic Curve $L$-functions: \\
Analytic Algorithms with Explicit Time Complexity}
\Author{Simon Spicer}
\Year{2015}
\Program{UW Mathematics}
\Chair{William Stein}{Professor}{Mathematics}
\Signature{Ralph Greenberg}
\Signature{Neal Koblitz}
\Signature{Bernard Deconinck, GSR}
\copyrightpage
% \titlepage
% --- sample stuff only -----
% unusual footnote not found in a real thesis
% You just use the \titlepage as commented out above
{\Degreetext{A dissertation submitted in partial fulfillment \\of the requirements for the degree of}
\def\thefootnote{\fnsymbol{footnote}}
\let\footnoterule\relax
\titlepage
}
\setcounter{footnote}{0}
% --- end-of-sample-stuff ---
%
% ----- signature and quoteslip are gone
%
%
% ----- abstract
%
\setcounter{page}{-1}
\abstract{%
Elliptic curves are central objects of study in modern-day algebraic number theory. The problem of how to determine the rank of a rational elliptic curve is a difficult one, and at the time of the writing of this thesis an unconditional general method for doing so is not known. \\
It has been known for decades that contingent on the Birch and Swinnerton-Dyer Conjecture, an algorithm to compute rank exists, but this algorithm has unknown time complexity. In the first part of this thesis we prove that, assuming standard conjectures, an {\it effective} algorithm exists to compute rank with time complexity that is polynomial in the curve's conductor. This method involves evaluating the $L$-function of the curve in question, and as such is practical for curves with conductors up to $\sim 10^{16}$ on current computer architecture. \\
The second part of this work addresses the question of what can be done when the conductor is too large for the above method to be practical. To this end we exhibit an analytic method to bound rank from above that doesn't rely on directly evaluating an elliptic curve's $L$-function, and as such can be used on curves with very large conductors. Because this method involves sums over the imaginary parts of the zeros of an elliptic curve $L$-function, we also include results concerning the locations thereof, and an exposition of related quantities.
}
\chapter*{Preface}
I have attempted to emphasize accessibility and readability throughout this work. Specifically, no knowledge beyond standard graduate-level complex analysis and algebra is assumed, and advanced knowledge of number theoretic topics is {\it not} required. As such, I hope that the results in this dissertation are accessible to a wide audience, even those at the advanced undergraduate level. Chapter 1 was written specifically to be a gentle introduction to the subject matter of this thesis. \\
For the expert I recommend skipping straight to Chapter 2, wherein the main results are stated. Proofs for these results can be found in Chapters 4 and 5 (from 5.2 onwards). \\
Finally, a note on conjecture dependencies. Many of the results in this work are contingent on the validity of three of the major open conjectures in number theory: the Birch and Swinnerton-Dyer conjecture (BSD), the Generalized Riemann Hypothesis (GRH) and the ABC conjecture (ABC). For ease of exposition, instead of stating explicitly in a result which of the above conjectures are assumed, we will list the three-letter initial of each assumed conjecture after the heading of each result. For example, the following result:
\begin{proposition}[BSD]
A rational elliptic curve with odd parity has a point of infinite order.
\end{proposition}
means that this proposition follows under the assumption that BSD is true.
%
% ----- contents & etc.
%
\tableofcontents
%\listoffigures
%\listoftables % I have no tables
%%
%% ----- glossary
%%
%\chapter*{Glossary} % starred form omits the `chapter x'
%\addcontentsline{toc}{chapter}{Glossary}
%\thispagestyle{plain}
%%
%\begin{glossary}
%\item[argument] replacement text which customizes a \LaTeX\ macro for
%each particular usage.
%\item[back-up] a copy of a file to be used when catastrophe strikes
%the original. People who make no back-ups deserve
%no sympathy.
%\item[control sequence] the normal form of a command to \LaTeX.
%\item[delimiter] something, often a character, that indicates
%the beginning and ending of an argument.
%More generally, a delimiter is a field separator.
%\item[document class] a file of macros that tailors \LaTeX\ for
%a particular document. The macros described by this thesis
%constitute a document class.
%\item[document option] a macro or file of macros
%that further modifies \LaTeX\ for
%a particular document. The option {\tt[chapternotes]}
%constitutes a document option.
%\item[figure] illustrated material, including graphs,
%diagrams, drawings and photographs.
%\item[font] a character set (the alphabet plus digits
%and special symbols) of a particular size and style. A couple of fonts
%used in this thesis are twelve point roman and {\sl twelve point roman
%slanted}.
%\item[footnote] a note placed at the bottom of a page, end of a chapter,
%or end of a thesis that comments on or cites a reference
%for a designated part of the text.
%\item[formatter] (as opposed to a word-processor) arranges printed
%material according to instructions embedded in the text.
%A word-processor, on the other hand, is normally controlled
%by keyboard strokes that move text about on a display.
%\item[\LaTeX] simply the ultimate in computerized typesetting.
%\item[macro] a complex control sequence composed of
%other control sequences.
%\item[pica] an archaic unit of length. One pica is twelve points and
%six picas is about an inch.
%\item[point] a unit of length. 72.27 points equals one inch.
%\item[roman] a conventional printing typestyle using serifs.
%the decorations on the ends of letter strokes.
%This thesis is set in roman type.
%\item[rule] a straight printed line; e.g., \hrulefill.
%\item[serif] the decoration at the ends of letter strokes.
%\item[table] information placed in a columnar arrangement.
%\item[thesis] either a master's thesis or a doctoral dissertation.
%This document also refers to itself as a thesis, although it
%really is not one.
%
%\end{glossary}
%
% ----- acknowledgments
%
\acknowledgments{
By no means did I produce this dissertation in a vacuum. Many individuals have provided critical contributions over the course of my studies, and I am thankful to all of them. However, some I must mention specifically. Sincere thanks must be given to my advisor William Stein, who for many years has provided the patient mentorship and guidance needed to make this dissertation a reality; thank you too to the other members of my dissertation reading committee: Ralph Greenberg, Neal Koblitz and Bernard Deconinck. I would also like to extend a heartfelt thanks to the University of Washington department of Mathematics as a whole, and to the graduate student coordinator Brooke Miller in particular, for supporting me throughout my studies at UW. \\
Beyond this, a number of mathematicians have given valuable advice. I am grateful for the correspondence with Barry Mazur on the explicit formula for elliptic curves, which was my entry point into the whole topic of elliptic curve $L$-functions; moreover I thank Peter Sarnak for his input on low-lying zeros of elliptic curve $L$-functions, and helping spur the formulation of the central idea of this thesis. John Cremona and Noam Elkies gave sage insight on the topics of the real period and regulator respectively. And I am grateful to John Voight, who used an early version of my rank estimation code and highlighted some significant bugs. And thanks must be given to Wei Ho, Jen Balakrishnan, Jamie Weigandt and Nathan Kaplan for putting up with my less-than-expert attempts to compute the ranks of large databases of elliptic curves. \\
And last but not least, a huge thank you to my wife Kimberly for her constant unwavering support throughout.
}
%
% ----- dedication
%
\dedication{\begin{center}To Kimberly and Bram, who comprise two thirds of the Spicer Theorem.\end{center}}
%
% end of the preliminary pages
%
% ========== Text pages
%
\textpages
% ========== Chapter 1
\chapter{Introduction}
\input{chapters/1_introduction}
% ========== Chapter 2
\chapter{Problem Outline and Major Results}\label{sec:outline_results}
\input{chapters/2_outline_and_results}
% ========== Chapter 3
\chapter{Notation, Definitions and Background}\label{sec:defs_background}
\input{chapters/3_background}
% ========== Chapter 4
\chapter{An Algorithm to Compute Rank}\label{chap:main_theorem}
\input{chapters/4_main_theorem}
% ========== Chapter 5
\chapter{Zero Sums}
\input{chapters/5_zero_sums}
% ========== Chapter 6
\chapter{Remarks and Future Work}
\input{chapters/6_remarks_future_work}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\printendnotes
%
% ========== Bibliography
%
\nocite{*} % include everything in the thesis.bib file
\bibliographystyle{acm}
\bibliography{bibliography}
%
% ========== Appendices
%
\appendix
\raggedbottom\sloppy
% ========== Appendix A
\chapter{Code Repo and Blog Posts}
The analytic rank estimation code mentioned in this thesis is hosted on GitHub, and is accessible to all free of charge under the GNU General Public License.
\begin{itemize}
\item The repo can be found at
\begin{description}
\item[] \verb%https://github.com/haikona/GSoC_2014%
\end{description}
The relevant Sage Trac ticket is
\begin{description}
\item[]\verb%http://trac.sagemath.org/ticket/16773%
\end{description}
\item Moreover, as it was being written the code was blogged about extensively; the posts on various aspects of the code's functionality can be found at
\begin{description}
\item[] \verb%http://mathandhats.blogspot.com/%
\end{description}
\end{itemize}
\vita{Simon Spicer was born and raised in Johannesburg, South Africa, but has spent the past six years in Seattle pursuing his mathematics PhD at the University of Washington. At the time of completing this thesis he and his wife Kimberly have just welcomed their first child, Bramwell, into the world. In his spare time Simon enjoys writing code, piloting airplanes and attempting to teach his family Afrikaans.}
\end{document}