On the maximal length of arithmetic progressions

Minzhi Zhao (Zhejiang University)
Huizeng Zhang (Hangzhou Normal University)


This paper is a continuation of a paper by Benjamini, Yadin and Zeitouni's on maximal arithmetic progressions in random subsets. In this paper the asymptotic distributions of the maximal arithmetic progressions and arithmetic progressions modulo $n$ relative to an independent Bernoulli sequence with parameter $p$ are given. The errors are estimated by using the Chen-Stein method. Then the almost sure limit behaviour of these statistics is discussed. Our work extends the previous results and gives an affirmative answer to the conjecture raised at the end of that paper.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-21

Publication Date: August 31, 2013

DOI: 10.1214/EJP.v18-2018


  • Alon, Noga; Spencer, Joel H. The probabilistic method. Third edition. With an appendix on the life and work of Paul Erdős. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, 2008. xviii+352 pp. ISBN: 978-0-470-17020-5 MR2437651
  • Arratia, R.; Goldstein, L.; Gordon, L. Two moments suffice for Poisson approximations: the Chen-Stein method. Ann. Probab. 17 (1989), no. 1, 9--25. MR0972770
  • An introduction to Stein's method. Lectures from the Meeting on Stein's Method and Applications: a Program in Honor of Charles Stein held at the National University of Singapore, Singapore, July 28–August 31, 2003. Edited by A. D. Barbour and Louis H. Y. Chen. Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore, 4. Singapore University Press, Singapore; World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2005. xii+225 pp. ISBN: 981-256-330-X MR2235447
  • Benjamini, Itai; Yadin, Ariel; Zeitouni, Ofer. Maximal arithmetic progressions in random subsets. Electron. Comm. Probab. 12 (2007), 365--376. MR2350574
  • Erdős, Paul; Rényi, Alfréd. On a new law of large numbers. J. Analyse Math. 23 1970 103--111. MR0272026
  • Erdős, P.; Révész, P. On the length of the longest head-run. Topics in information theory (Second Colloq., Keszthely, 1975), pp. 219--228. Colloq. Math. Soc. Janos Bolyai, Vol. 16, North-Holland, Amsterdam, 1977. MR0478304
  • Erdös, Paul; Turán, Paul. On Some Sequences of Integers. J. London Math. Soc. S1-11 no. 4, 261. MR1574918
  • Gordon, Louis; Schilling, Mark F.; Waterman, Michael S. An extreme value theory for long head runs. Probab. Theory Relat. Fields 72 (1986), no. 2, 279--287. MR0836278
  • Túri, József. Limit theorems for the longest run. Ann. Math. Inform. 36 (2009), 133--141. MR2580909
  • Kohayakawa, Yoshiharu; Łuczak, Tomasz; Rödl, Vojtěch. Arithmetic progressions of length three in subsets of a random set. Acta Arith. 75 (1996), no. 2, 133--163. MR1379396
  • Móri, Tamás F. The a.s. limit distribution of the longest head run. Canad. J. Math. 45 (1993), no. 6, 1245--1262. MR1247545
  • Roth, K. F. On certain sets of integers. J. London Math. Soc. 28, (1953). 104--109. MR0051853
  • Szemerédi, E. On sets of integers containing no $k$ elements in arithmetic progression. Collection of articles in memory of Juriĭ Vladimirovič Linnik. Acta Arith. 27 (1975), 199--245. MR0369312
  • Szemerédi, E.; Vu, V. H. Finite and infinite arithmetic progressions in sumsets. Ann. of Math. (2) 163 (2006), no. 1, 1--35. MR2195131
  • Tao, Terence. What is good mathematics? Bull. Amer. Math. Soc. (N.S.) 44 (2007), no. 4, 623--634. MR2338369

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.