Applied Math 206

Fall 2009

The purpose of these essays is for you to study some topic beyond the syllabus in depth, and understand it well enough to be able to explain it in your own words. The essay should contain a significant amount of prose, which explains the motivation for the material, highlights the main ideas, and gives intuition for the mathematics. Of course, this prose should be supporting a mathematical development, with precise definitions and statements of results. You need not include proofs of all lemmas and theorems; selectively decide which to include or sketch according to how informative and important they are. Further originality beyond the exposition is of course welcome too. This may come in the form of examples, new proofs of some lemmas, or even some small new results. Be sure to clearly identify anything that is new! In order to ensure that you present things in your own words (and really understand the material), I recommend that you study the source material carefully, but then try to write your essay without looking at the source material (only consulting it when you get stuck).

Each AM206 student will give a presentation on *one *of her/his essay topics during reading period. These are a chance for you to share something interesting you have learned with the rest of the class. Since the presentations are relatively short, you need to be even more selective about what to include; avoid the temptation to squeeze in too much material. If the audience leaves with one memorable idea or concept and an interest to learn more about the subject, you will have succeeded. Again due to the short time, you are encouraged to use slides/powerpoint (but again avoid the temptation to fill them with too much math). You may choose either your first or second essay topic for the presentation. The exact length and scheduling of the presentations will be done closer to the end of term.

- Essay 1 due date: Monday, November 2
- Essay 2 due date: Monday, December 7
- Presentations: Monday, December 7 and Wednesday, December 9.
- Length: 7-8 pages each (though anything in the 5-10 page range is acceptable)
- Target audience: your fellow AM206 students - i.e. a mathematically mature reader, but with no specific expertise in algebra beyond what we cover in AM106/206.
- Typesetting your essays in LaTeX is highly recommended. (For Windows, I recommend using the programs Miktex and Winedt.)
- All references you use should be listed at the end of the essay, and you should clearly distinguish material/exposition from the references from that which is original.

Below is a list of suggested topics with some suggested references, which will be updated periodically. You should feel free to suggest your own topic, e.g. one that relates to your own interests or research. If you do, you *must *discuss the topic and the references you plan to use with Salil for approval *no later than 1 week before the essay is due.*

- Classification of Finite Abelian Groups
- Gallian Chapter 11
- We will state but not prove this in lecture

- The Sylow Theorems
- Gallian Chapter 24

- Classification of Finite Simple Groups
- Gallian Chapter 25.
- Solomon, Ron. On finite simple groups and their classification.
*Notices Amer. Math. Soc.*42 (1995), no. 2, 231--239.

- Symmetry Groups, with applications to chemistry or physics.
- Gallian Chapters 27-28 and the references therein.
- The articles by White mentioned in Chapter 2 and by Watson in Chater 27 may be good starting points for the applications.
- M. Tinkam. Group Theory and Quantum Mechanics. Dover, 2003.

- Applications of Group Theory to Counting
- Gallian Chapter 29 and the references therein
- Computer scientists may also be interested in the article Computational Polya Theory by Mark Jerrum.

- Representation Theory (of Finite Groups)
- Chapter in
*Algebra*by Michael Artin. - J.P. Serre. Linear Representations of Finite Groups, Springer-Verlag, New York, 1977.

- Chapter in
- Fourier Analysis on Finite Abelian Groups, with applications to random walks, computer science, and more.
- A. Terras. Fourier analysis on finite groups and applications and the references therein.
- R. de Wolf. A Brief Introduction to Fourier Analysis on the Boolean Cube and the references therein.

- Daniel Stefankovic. Fourier Transforms in Computer Science. Master's Thesis, University of Chicago, Department of Computer Science, TR-2002-03 and the references therein.

- Barrington's Theorem: equivalence of log-depth circuits and constant-width branching programs
(via multiplication in S_5)
- already covered on Problem Set 3.
- Barrington, David A. Bounded-width polynomial-size branching programs recognize exactly those languages in ${\rm NC}\sp 1$. Journal of Computer & System Sciences. 38 (1989), no. 1, 150--164. 68Q15 (68Q25)

- Computational Group Theory
- Akos Seress. Computational Group Theory. and the references therein.
- Akos Seress. Permutation Group Algorithms.

- Solving the Rubik's Cube.
- David Joyner. Adventures in Group Theory.

- Integer Multiplication in Nearly Linear Time.
- Section in Donald Knuth. The Art of Computer Programming, Vol 2: Seminumerical Algorithms.
- Martin Furer. Faster Integer Multiplication. SIAM J. Comput. Volume 39, Issue 3, pp. 979-1005 (2009).
- Anindya De, Piyush P Kurur, Chandan Saha, Ramprasad Saptharishi. Fast Integer Multiplication using Modular Arithmetic. http://arxiv.org/abs/0801.1416v3.
- This material may require background on rings and fields.

- Primality Testing
(and other number-theoretic algorithms)
- Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in P. Annals of Mathematics 160(2): 781-793, 2004.
- Henri Cohen. A course in computational algebraic number theory.
- May require background on rings and fields.

- Galois Theory
- Gallian Ch. 32

- Algorithms for factoring polynomials over finite fields.
- J. von zur Gathen and D. Panario. Factoring polynomials over finite fields: A survey. J. Symb. Comput., 31(1/2):3–17, 2001.
- E. Kaltofen. Polynomial factorization: a success story. In J. Rafael Sendra, editor, ISSAC, pages 3–4. ACM, 2003.
- J. von zur Gathen. Who was who in polynomial factorization. In Barry M. Trager, editor, ISSAC, page 2. ACM, 2006.
- R. Lidl, H. Niederreiter. Introduction to finite fields and their applications.
- and the references therein

- Algebraic coding theory and list-decoding algorithms
- Gallian Ch. 31
- V. Guruswami. Error Correction up to the Information-Theoretic Limit. Communications of the ACM 52 (3), pp. 87-95.
- R. Lidl, H. Niederreiter. Introduction to finite fields and their applications.
- and the references therein

- Cryptography from ideal lattices
- D. Micciancio. Generalized compact knapsaks, cyclic lattices and efficient one-way functions. In
*Post Quantum Cryptography*, D.J. Bernstein; J. Buchmann; E. Dahmen (eds.), pp. 147-191, Springer (February 2009). - C. Gentry. Fully homomorphic encryption using ideal lattices. Proceedings of the 41st Annual ACM symposium on Theory of Computing, pp. 169-178, 2009

- D. Micciancio. Generalized compact knapsaks, cyclic lattices and efficient one-way functions. In
- Grobner Bases (main tool for doing computations with ideals in multivariate polynomial rings)
- Brad Lutes. A Survey of Grobner Bases and Their Applications, Departmental Report, Texas Tech University, 2004.
- and the references therein

- Understanding ruler-compass constructions using field extensions
- Gallian Ch. 23
- Chapter in
*Algebra*by Michael Artin.

- Elliptic Curve Cryptography
- L. Washington. Elliptic curves : number theory and cryptography. Chapman & Hall/CRC, c2003.
- D. Hankerson, A. Menezes, S. Vanstone. Guide to Elliptic Curve Cryptography, Springer, 2004