Erdős Problem 847

References:

• erdosproblems.com/847
• [RRS24] Reiher, Christian and R"odl, Vojt\v ech and Sales, Marcelo, Colouring versus density in integers and {H}ales-{J}ewett cubes. J. Lond. Math. Soc. (2) (2024) arXiv:2311.08556

def Erdos847.HasFew3APs (A : Set ℕ) : Prop

HasFew3APs A means that $A \subset \mathbb{N}$ is a set for which there exists some $\epsilon > 0$ such that in any subset of $A$ of size $n$ there is a subset of size at least $\epsilon n$ which contains no three-term arithmetic progression.

Equations

• Erdos847.HasFew3APs A = ∃ ε > 0, ∀ B ⊆ A, Finite ↑B → ∃ C ⊆ B, ↑C.ncard ≥ ε * ↑B.ncard ∧ ThreeAPFree C

theorem Erdos847.erdos_847 : False ↔ ∀ (A : Set ℕ), Infinite ↑A → HasFew3APs A → ∃ (n : ℕ) (S : Fin n → Set ℕ), (∀ (i : Fin n), ThreeAPFree (S i)) ∧ A = ⋃ (i : Fin n), S i

Let $A \subset \mathbb{N}$ be an infinite set for which there exists some $\epsilon > 0$ such that in any subset of $A$ of size $n$ there is a subset of size at least $\epsilon n$ which contains no three-term arithmetic progression.

Is it true that $A$ is the union of a finite number of sets which contain no three-term arithmetic progression?

A negative answer was given by Reiher, Rödl, and Sales [RRS24], who proved that, for any $0<\mu<1/2$, there exists $A\subseteq \mathbb{N}$ such that every finite colouring of $A$ contains a three-term arithmetic progression, and yet every subset of $A$ of size $n$ contains a subset of size $\geq \mu n$ without a three-term arithmetic progression.