Skip to content

Erdős problem 847

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

Sources

The source's own material, retained exactly.

1 retained statement36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

847.lean

Retained formal statement1 of 1

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

Is it true that AA 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<μ<1/20<\mu<1/2, there exists A⊆NA\subseteq \mathbb{N} such that every finite colouring of AA contains a three-term arithmetic progression, and yet every subset of AA of size nn contains a subset of size ≥μn\geq \mu n without a three-term arithmetic progression.

FormalConjectures/ErdosProblems/847.leanErdos847.erdos_8471 lineExact file
False ↔ ∀ (A : Set ℕ), Infinite ↑A → Erdos847.HasFew3APs A → ∃ n S, (∀ (i : Fin n), ThreeAPFree (S i)) ∧ A = ⋃ i, S i
SolvedStatement only, no proof