Analysis of points and lines (TCC)


In a nutshell

A near pencil

Time slot: Fridays, 2-4pm (except 24th October and 21st November, additional Wednesday 19th November!)
Starting: 17th October 2014
Ending: 12th December 2014
Level: graduate course (in the Taught Course Centre)
Prerequisites: some basic Fourier analysis, linear algebra and probability
Office hours: to be confirmed
 


Synopsis |  Syllabus | Organisation | Assessment | Bibliography


Synopsis

How well distributed can a set of n points in the plane be? How many incidences can there be between a finite set of points and lines in the plane? Does a dense subset of the set of words of length n over an alphabet of size k always contain a combinatorial line?

This course deals with these and other fundamental questions about points and lines that arise in a variety of different settings. The problems studied are elegant and relatively easily accessible, and the techniques range from harmonic analysis through relatively elementary algebraic and probabilistic arguments to hands-on but often ingenious combinatorics. As such it should be suitable for any graduate student with an interest in discrete mathematics, analysis, number theory and discrete geometry.

We shall begin by proving van der Waerden's classical theorem on the existence of monochromatic arithmetic progressions, as well as the Hales-Jewett theorem on combinatorial lines in high-dimensional spaces. The latter has recently claimed a fair amount of attention, its density version having been successfully proved by a polymath project.

In the second part of the course we shall see a number of classical results in discrepancy theory, which deals with how far from equidistributed a finite set of points in Euclidean space can be. This is a very rich subject which has many applications throughout mathematics, and beautifully combines analytic, algebraic and combinatorial methods.

Next we study the incidence theory of points in lines in Euclidean space as well as over finite fields, currently a hot topic in arithmetic combinatorics. It has important implications for Erdős' and Szemerédi's famous sum-product conjecture, which remains open to this day and asserts, roughly speaking, that the real line does not contain any approximate (finite) subfields.

The final quarter of the course will be dedicated to some applications of the aforementioned results in theoretical computer science, specifically the subfield of communication complexity. Please rest assured that no prior knowledge or affinity for computers is required for the enjoyment of this part!

The prerequisites are minimal. We shall need the fundamental notions of (discrete) Fourier analysis as well as basic concepts from linear algebra and discrete probability.

Note that there is no overlap in material with the course I taught last year, so students who took 'Introduction to additive combinatorics' in 2013 can get credit for this course.

Feel free to contact me at julia.wolf at bristol.ac.uk with any questions prior to the start of term.

Return to top


Syllabus

The following syllabus is tentative and subject to change.

Date ContentRecommended exercises
17/10/2014 Incidence geometry and the sum-product problem1.5, 1.6, 1.7, 1.12
31/10/2014 Incidence geometry and the sum-product problem1.13, 1.17, 1.25, 1.26
07/11/2014 Euclidean and finite-field Kakeya phenomena2.5, 2.10, 2.13, 2.15
14/11/2014 More Kakeya and the Sylvester-Gallai theorem2.18, 2.20, 2.22, 3.4
19/11/2014 Variants of the Sylvester-Gallai theorem
Note unusual day: Wednesday 2-4pm!
3.5, 3.6, 3.16
28/11/2014 Combinatorial discrepancy4.3, 4.10
05/12/2014 More combinatorial discrepancy4.14, 4.15, 4.19
12/12/2014 Geometric discrepancy4.23, 4.30, 4.32

Return to top


Organisation

I will be visiting all of the nodes (Oxford, Warwick, Bath and London) in the autumn, so office hours can be arranged locally according to demand. Please watch this space for times that I will be available, and email me if you would like to meet.

Oxford Thursday, 18th December 2014
Warwick Tuesday, 11th November 2014

Return to top


Assessment

At the end of the course, participants will choose from a list of original research articles and write up an exposition of the chosen result. This exposition should place the result in the context of what has been discussed in the course, and should be sufficiently detailed for other course participants to be able to follow the main steps of the argument. The completion of the short weekly problem sets is optional but strongly encouraged.

Return to top


Bibliography

The following reading material may be helpful to course participants. You may also wish to consult my personal roadmap for interesting surveys and original research articles in this general area.

[AB] S. Arora and B. Barak: Computational Complexity
Cambridge University Press, 2009.
Princeton webpage
[C] B. Chazelle: The Discrepancy Method
Cambridge University Press, 2002.
Princeton webpage
[TV] T. Tao: Sum-product estimates, expanders and exponential sums
Blog at https://terrytao.wordpress.com, 2007.
blog post
[TV] T. Tao and V. Vu: Additive Combinatorics
Cambridge University Press, 2006.
google books

Return to top

This page was last updated 15th December 2014.