Four‐term progression free sets with three‐term progressions in all large subsets. Issue 4 (16th August 2021)

• Record Type: Journal Article
• Authors: Pohoata, Cosmin; Roche‐Newton, Oliver
• Is Part Of: Random structures & algorithms. Volume 60:Issue 4(2022)
• Page Start: 749
• Page End: 770
• Publication Date: 2021-08-16
• Subjects: arithmetic progressions -- containers -- Roth's theorem; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21042
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: This paper is mainly concerned with sets which do not contain four‐term arithmetic progressions, but are still very rich in three‐term arithmetic progressions, in the sense that all sufficiently large subsets contain at least one such progression. We prove that there exists a positive constant c and a set A ⊂ 𝔽 q n which does not contain a four‐term arithmetic progression, with the property that for every subset A ′ ⊂ A with | A ′ | ≥ | A | 1 − c, A ′ contains a nontrivial three term arithmetic progression. We derive this from a more general quantitative Roth‐type theorem in random subsets of 𝔽 q n, which improves a result of Kohayakawa–Łuczak–Rödl/Tao–Vu. We also discuss a similar phenomenon over the integers. Finally, we include another application of our methods, showing that for sets in 𝔽 q n or ℤ the property of "having nontrivial three‐term progressions in all large subsets" is almost entirely uncorrelated with the property of "having large additive energy."