189-346 / 377B: Number Theory
Projects
The following gives a list of possible
topics for your number theory project.
You are also free to come up with your own choice
of topic related to the course.
Your write-up should be about 10-15 pages in length. It is OK,
albeit not required, to
include computer programs and the outcomes of numerical experiments in your
project. The projects are meant to be carried out individually, not in teams,
although you are free (in fact, encouraged) to discuss what you are working on
with your classmates.
You should choose a project topic, and let me know what it is,
before the week of the Spring
break at the end of February. To avoid duplications, I will be
posting
your choices on the web, as they are made.
Project topics will be assigned on a first-come, first serve basis:
I expect that some of the more popular topics will be chosen
first, so it is in your interest to make a fast decision!
A Chapter of Scharlau-Opolka:
Euler: Thomas Ng
Gauss: Roderick Mackenzie
You may pick one of the chapters
(between ch. 2 and ch. 8) in the
book by Scharlau and Opolka and write a project on the mathematician
that is featured in that chapter, giving more details to flesh out the
mathematics alluded to in the text.
The Miller-Rabin primality test:
Kevin Shustack
Explain the Miller-Rabin primality test and Miller's analysis of its complexity, based on the (generalized) Riemann hypothesis.
References:
Miller, Gary L. Riemann's hypothesis and tests for primality.
Working papers presented at
the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N.M.,
1975).
J. Comput. System Sci. 13 (1976), no. 3, 300--317.
Carl Pomerance, Recent developments in primality testing, Mathematical
Intelligencer 3, no. 3 (1981) 97-105.
The Agrawal-Kayal-Saxena primality test.
A few years ago Manindra Agrawal, Neeraj Kayal and Nitin Saxena
achieved a major breakthrough by showing that a number N can be tested for
primality in time proportional to a polynomial in $\log(N)$.
References
Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in P.
Annals of Mathematics 160(2): 781-793, 2004.
(Or, you can dowload the original paper directly.)
Lenstra's factorization algorithm based on elliptic
curves over finite fields.
Reference:
Lenstra, H. W., Jr.
Factoring integers with elliptic curves. Ann. of Math. (2) 126
(1987), no. 3, 649--673.
Elliptic curve cryptosystems.
Chosen by Dieter Fishbein
Reference.
Koblitz, Neal.
A course in number theory and cryptography. Second edition. Graduate
Texts in Mathematics, 114. Springer-Verlag, New York, 1994.
Shor's factorization algorithm based on "quantum computers".
Chosen by David Thibodeau and Santiago Batista.
Recently
a probabilistic algorithm was discovered for factoring integers in
polynomial time on a quantum computer, a computing device which uses
elementary particles to store information and exploits the peculiar
properties of these particles (as described by quantum mechanics)
to achieve a fast factorization algorithm. This discovery has caused alot of
excitement among number theorists, theoretical computer scientists, and
physicists, and represents a remarkable confluence of the three subjects.
This would be a good topic for someone who already has some
background in physics (and the rudiments of quantum mechanics in particular).
Reference:
Peter Shor,
Polynomial-Time Algorithms for Prime Factorization
and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing
Volume 26, Number 5
pp. 1484-1509.
Dirichlet's Theorem on primes in arithmetic progressions.
Michael Brown.
Reference.
Serre, J.-P.
A course in arithmetic. Translated from the French. Graduate Texts in
Mathematics, No. 7. Springer-Verlag, New York-Heidelberg, 1973.
The prime number theorem.
Spencer Frei
Reference.
Davenport, Harold.
Multiplicative number theory. Second edition. Revised by Hugh L.
Montgomery. Graduate Texts in Mathematics, 74.
Springer-Verlag, New York-Berlin, 1980.
Continued fractions and ergodic theory.
Alex Cowan
Reference.
Khintchine, A. Ya. Continued fractions.
Translated by Peter Wynn. P. Noordhoff, Ltd.,
Euler's calculation of zeta(2k) and its developments.
Antony Della Vecchia
References
Dunham, William. Journey through genius.
The great theorems of mathematics. Penguin
Books, New York, 1991.
Koblitz, Neal. p-adic numbers, p-adic analysis, and
zeta-functions. Second edition. Graduate
Texts in Mathematics, 58. Springer-Verlag, New York-Berlin, 1984.
Iwasawa, Kenkichi. Lectures on p-adic L-functions. Annals of Mathematics
Studies, No. 74. Princeton University Press, Princeton, N.J.; University
of Tokyo Press, Tokyo, 1972.
The irrationality of zeta(3).
Alexis Bracken
Reference.
van der Poorten, Alfred. A proof that Euler missed... Apery's
proof of the irrationality
of zeta(3).
An informal report. Math. Intelligencer 1
(1978/79), no. 4, 195--203.
Groningen 1963.
The theory of partitions.
Thomas Ng
Reference.
Andrews, George E. The theory
of partitions. Reprint of the 1976 original. Cambridge
Mathematical Library. Cambridge
University Press, Cambridge, 1998.
Schoof's algorithm for counting the number of points on an elliptic
curve over a finite field.
Reference.
Schoof, Rene. Elliptic curves over finite fields
and the computation of square roots mod
p. Math. Comp. 44 (1985), no. 170, 483--494.
Computing the zeroes of the Riemann zeta-function.
Reference.
Turing, Alan. M.
Some calculations of the Riemann zeta-function. Proc. London Math. Soc.
(3) 3, (1953). 99--117.
Odlyzko, Andrew M. Analytic computations in number theory. Mathematics
of Computation 1943--1993: a half-century of computational
mathematics (Vancouver, BC, 1993),
451--463, Proc. Sympos. Appl. Math., 48,
Amer. Math. Soc., Providence, RI, 1994.
p-adic numbers.
Abel Beyene
References.
Koblitz, Neal p-adic numbers, p-adic analysis, and
zeta-functions. Second edition. Graduate
Texts in Mathematics, 58. Springer-Verlag, New York-Berlin, 1984.
Gouvea, Fernando Q. p-adic numbers. An introduction. Second
edition. Universitext.
Springer-Verlag, Berlin, 1997.
Cubic and biquadratic reciprocity.
Jamie Klassen
References.
Ireland, Kenneth; Rosen, Michael. A classical introduction to
modern number theory. Second edition. Graduate Texts in Mathematics, 84.
Springer-Verlag, New York, 1990.