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.