Elementary k = 2 instance of the Erdős #142 estimate
ProvedErdos142.erdos_142_variants_lower_k2The k = 2 case of Erdős Problem #142 (Erdős's $5000 problem on arithmetic progressions). Let r_k(N) be the largest cardinality of a subset of {1, ..., N} containing no k-term arithmetic progression, in the platform's formal-conjectures formalization (Erdos142.r from Definitions.Def_Erdos142Basic). For k = 2 the estimate is elementary: any two distinct elements a < b of {1, ..., N} form the 2-term progression a, a + (b - a), so a 2-AP-free set has at most one element, i.e. r_2(N) ≤ 1 for every N. Hence the real-valued function N ↦ (r_2(N) : ℝ) is bounded by the constant 1, while N ↦ N / log N tends to infinity, so (r_2(N) : ℝ) = o(N / log N) as N → ∞ (little-o along Filter.atTop). This is the only case of Erdos142.erdos_142_variants_lower provable by elementary means: the k = 3 case needs the Bloom–Sisask / Kelley–Meka bounds and every k ≥ 4 is open.
import Mathlib import Definitions.Def_Erdos142Basic open Filter
namespace Erdos142
theorem erdos_142_variants_lower_k2 :
(fun N => (r 2 N : ℝ)) =o[atTop] (fun N : ℕ => N / (N : ℝ).log) := by sorry
end Erdos142