Upper tail large deviations for arithmetic progressions in a random set

Bhaswar B. Bhattacharya, Shirshendu Ganguly, Xuancheng Shao, Yufei Zhao

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


Let Xk denote the number of k-term arithmetic progressions in a random subset of Z/NZ or {1,..., N} where every element is included independently with probability p. We determine the asymptotics of log P(Xk ≥ (1 + δ)EXk ) (also known as the large deviation rate) where p → 0 with p ≥ Nck for some constant ck > 0, which answers a question of Chatterjee and Dembo. The proofs rely on the recent nonlinear large deviation principle of Eldan, which improved on earlier results of Chatterjee and Dembo. Our results complement those of Warnke, who used completely different methods to estimate, for the full range of p, the large deviation rate up to a constant factor.

Original languageEnglish
Pages (from-to)167-213
Number of pages47
JournalInternational Mathematics Research Notices
Issue number1
StatePublished - 2020

Bibliographical note

Publisher Copyright:
© The Author(s) 2018. Published by Oxford University Press. All rights reserved.

ASJC Scopus subject areas

  • Mathematics (all)


Dive into the research topics of 'Upper tail large deviations for arithmetic progressions in a random set'. Together they form a unique fingerprint.

Cite this