Spring 2017

Large Deviations for Arithmetic Progressions

Monday, April 10th, 2017 2:00 pm3:00 pm

Add to Calendar

We determine the asymptotics of the log-probability that the number of k-term arithmetic progressions in a random subset of integers exceeds its expectation by a constant factor. This is the arithmetic analog of subgraph counts in a random graph. The solution uses nonlinear large deviation principles developed by Chatterjee and Dembo, and, more recently, by Eldan. 
I will highlight some open problems in additive combinatorics that we encountered in our work, namely concerning the "complexity" of the dual functions of AP-counts. These problems seem to extend beyond the current reach of higher-order Fourier analysis.