A working seminar on the topics of Expander Graphs and on Point counting (MATH 667), Winter 2010


Instructors: Profs. Henri Darmon and Eyal Goren.

Time: Fridays from 8:30 to 10:00 in BH 920.

This working seminar has as one of its goals to provide students with preparation
for some of the workshops in the scope of the thematic semester at the CRM
"Number Theory as Experimental and Applied Science"
(see www.crm.umontreal.ca/NT2010/ for details.)

Goren will take responsibility of the seminar during the months of January and February.
This part of the seminar will be devoted to topics in expander graphs, using the
paper by Hoory, Linial and Wigderson (Bull. AMS, 43 (2006)) as our main text.
The requirement from the students is to present a 2 hour lecture on a topic selected
together with the instructor and to participate in the weekly meetings.

Darmon will take responsibility of the seminar during the months of March and April.
This part of the seminar will be devoted to point counting on algebraic varieties
in positive characteristic and the machinery that goes into it.

Part 2: Point counting and p-adic cohomology

The goal of this part of the course will be to go over at least part of the following references, with the goal of preparing ourselves for the CRM workshop on point counting that will be held at the end of April.

1) R. Schoof, Counting points on elliptic curves over finite fields.
Particularly the last section, which focuses on Schoof's polynomial time algorithm based on l-adic cohomology.

2) B. Edixhoven, Point counting after Kedlaya.
This is a nice introduction to the circle of ideas related to point counting on curves using p-adic cohomology.

3) A. Chambert-Loir, Compter (rapidement) le nombre de solutions d'\'equations dans les corps finis.
A beautifully written survey of the subject. Highly recommended!

Anyone who is interested in giving a presentation related to the material above is encouraged to get in touch with me (H. Darmon).

Schedule of lectures

Friday, March 5. I will give an overview of the seminar and start to line up some volunteers.

Friday, March 12. There will be no seminar because of the workshop on Graph Theory at the CRM.

Friday, March 19, at 8:30 AM. Note on the time: Please note that from now on the seminar will meet at 8:30 AM. I apologise for the confusion about the starting time last week!! Please note that there is always a small chance (if the metros are running more slowly than usual) that I could only make it a short time after 8:30, but certainly we will not start after 8:40.

The program: I will discuss p-adic point counting algorithms for elliptic curves based on the theory of the canonical lift, following the article

An extension of Satoh's algorithm and its implementation, by Mireille Fouquet, Pierrick Gaudry, and Robert Harley.

This article can be downloaded from here.
Any seminar participant who is interested in covering this article with me should contact me.

An exercise based on my first lecture At the end of the first lecture, I gave a cohomological proof (by calculating the trace of Frobenius on deRham cohomology) of the fact the number of points of an elliptic curve E over a finite field Fq of odd characteristic is equal to the q-1st coefficient in the polynomial f(x)(q-1/2), where y2 =f(x) is a defining equation for the curve. To test your understanding of this theorem, try extending the statement (and the cohomological proof, as well as the lowbrow proof!) to the case of a hyperelliptic curve y2=f(x) of genus g, where f is a polynomial of degree 2g+1.

Friday, March 26, at 8:30 AM.
Note that this lecture will be at the CRM, in room 4336.
Darmon. Satoh's algorithm, cont'd.

Friday, April 2, at 8:30 AM.
Aurel Page, Schoof's algorithm.

Friday, April 9, at 8:30 AM.
Francesc Castella, Kedlaya's algorithm.

Friday, April 16, at 8:30 AM.
Note that this lecture will be at the CRM, in room 4336.
Adam Logan, Kedlaya's algorithm, cont'd.