Mathematical Sciences Research Institute

Home » Workshop » Schedules » A regularity lemma for definable sets over finite fields, and expanding polynomials

A regularity lemma for definable sets over finite fields, and expanding polynomials

Introductory Workshop: Model Theory, Arithmetic Geometry and Number Theory February 03, 2014 - February 07, 2014

February 06, 2014 (04:00 PM PST - 05:00 PM PST)
Speaker(s): Terence Tao (University of California, Los Angeles)
Location: MSRI: Simons Auditorium
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC


Szemeredi's regularity lemma provides a structural description of arbitrary large dense graphs; roughly speaking, it decomposes any such graphs into a bounded number of pieces, most of which behave "pseudorandomly". While this lemma applies to arbitrary graphs, the dependence on constants can be terrible, and there can also exist "bad" components which are not pseudorandom. However, these defects can sometimes be removed if further assumptions are placed on the original graph. We present an "algebraic regularity lemma" which covers the case when the graph is definable (with bounded complexity) over a finite field of large characteristic. By combining the model-theoretic classification of definable sets in this setting with an ultraproduct argument (to transfer to the characteristic zero setting) combined with algebraic geometry tools (such as the etale fundamental group) and the Lang-Weil inequality, we are able to get much better control on the pseudorandomness and definability properties of the components, and also can exclude the existence of bad components. As an application of this lemma, we classify the polynomials over finite fields of large characteristic which are "expanding" in a combinatorial sense.

20084?type=thumb Tao notes 1.58 MB application/pdf Download
Video/Audio Files


H.264 Video v1258.mp4 324 MB video/mp4 rtsp://videos.msri.org/data/000/019/891/original/v1258.mp4 Download
Buy the DVD

If none of the options work for you, you can always buy the DVD of this lecture. The videos are sold at cost for $20USD (shipping included). Please Click Here to send an email to MSRI to purchase the DVD.

See more of our Streaming videos on our main VMath - Streaming Video page.