Skip to content

Erdős problem 847

Let ANA \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

Browse retained paths and inspect the exact material available for this Problem.

1 retained statement2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

847.lean

Retained formal statement1 of 1

Let ANA \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 ANA\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 ℕ), InfiniteAErdos847.HasFew3APs A → ∃ n S, (∀ (i : Fin n), ThreeAPFree (S i)) ∧ A = ⋃ i, S i
SolvedStatement only, no proof

Search problems.science

Find a Problem, Result, source, or page