Four‐term progression free sets with three‐term progressions in all large subsets

DOI10.1002/RSA.21042MaRDI QIDQ6074701zbMATH OpenOpenAlexFDO

Authors Cosmin Pohoata, Oliver Roche-Newton

Publication date 12 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.08457

zbMATH Keywords

arithmetic progressionscontainersRoth's theorem

Mathematics Subject Classification ID

Hypergraphs (05C65) Additive bases, including sumsets (11B13) Arithmetic progressions (11B25) Arithmetic combinatorics; higher degree uniformity (11B30) Other combinatorial number theory (11B75)

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 $Asubsetmathbb{F}_q^n$ which does not contain a four-term arithmetic progression, with the property that for every subset $A^{\prime }subsetA$ with $|A^{\prime }|geq|A{|}^{1-c}$, $A^{\prime }$ contains a nontrivial three term arithmetic progression. We derive this from a more general quantitative Roth-type theorem in random subsets of $mathbb{F}_q^n$, which improves a result of Kohayakawa-Luczak-R"odl/Tao-Vu. We also discuss a similar phenomenon over the integers, where we show that for all $epsilon>0$, and all sufficiently large $NinmathbbN$, there exists a four-term progression-free set $A$ of size $N$ with the property that for every subset $A^{\prime }subsetA$ with $|A^{\prime }|ggfrac1(logN{)}^{1-epsilon}cdotN$ contains a nontrivial three term arithmetic progression. Finally, we include another application of our methods, showing that for sets in $mathbb{F}_q^n$ or $mathbbZ$ the property of "having nontrivial three-term progressions in all large subsets" is almost entirely uncorrelated with the property of "having large additive energy".

Recommendations

• Three-term arithmetic progressions in subsets of \(\mathbf{F}_q^\infty\) of large Fourier dimension
• Arithmetic progressions of length three in subsets of a random set
• On subsets of \(\mathbb F_q^n\) containing no \(k\)-term progressions
• On the distribution of three-term arithmetic progressions in sparse subsets of F_p^n
• Sets without k‐term progressions can have many shorter progressions

Cites work

• A new proof of Roth’s theorem on arithmetic progressions
• A new proof of Szemerédi's theorem for arithmetic progressions of length four
• A note on Elkin's improvement of Behrend's construction
• A quantitative improvement for Roth's theorem on arithmetic progressions: Table 1.
• A set of squares without arithmetic progressions
• A tight bound for Green's arithmetic triangle removal lemma in vector spaces
• Additive combinatorics
• Arithmetic progressions in sets of small doubling
• Arithmetic progressions of length three in subsets of a random set
• Combinatorial theorems in sparse random sets
• Hypergraph containers
• Independent sets in hypergraphs
• Linear problems in combinatorial number theory
• On Certain Sets of Integers
• On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression
• On sets of integers containing k elements in arithmetic progression
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• On the number of points in general position in the plane
• Progression-free sets in \(\mathbb{Z}_4^n\) are exponentially small
• Sets without k‐term progressions can have many shorter progressions
• The number of subsets of integers with no k-term arithmetic progression
• Three-term arithmetic progressions and sumsets

Cited in

(8)

• Poissonian correlations of higher orders
• Arcs in \(\mathbb{F}_q^2\)
• A uniform set with fewer than expected arithmetic progressions of length 4
• On the distribution of three-term arithmetic progressions in sparse subsets of F_p^n
• New bounds for Szemerédi's theorem, I: progressions of length 4 in finite field geometries
• Three-term arithmetic progressions in subsets of \(\mathbf{F}_q^\infty\) of large Fourier dimension
• Sets avoiding six-term arithmetic progressions in \(\mathbb{Z}_6^n\) are exponentially small
• Counting arcs in \(\mathbb{F}_q^2\)

This page was built for publication: Four‐term progression free sets with three‐term progressions in all large subsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074701)