/- Copyright 2025 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Erdős Problem 3

References:

    erdosproblems.com/3

    [BlSi20] Bloom, Thomas F. and Sisask, Olof, Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions. arXiv:2007.03528 (2020).

    [Go01] Gowers, W. T., A new proof of Szemerédi's theorem. Geom. Funct. Anal. (2001), 465-588.

    [GrTa17] Green, Ben and Tao, Terence, New bounds for Szemerédi's theorem, III: a polylogarithmic bound for $r_4(N)$. Mathematika (2017).

    [KeMe23] Kelley, Zander and Meka, Raghu, Strong bounds for 3-progressions. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) (2023).

    [LSS24] Leng, James, Sah, Ashwin and Sawhney, Mehtaab, Improved bounds for Szemerédi's theorem. arXiv:2402.17995 (2024).

    [OAI26] OpenAI, Quasipolynomial Bounds for Arithmetic Progressions. OpenAI Math Release preprint (2026). https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Quasipolynomial-Bounds-for-Arithmetic-Progressions-September-23-2026/paper.pdf

@[expose] public sectionopen Asymptotics Filternamespace Erdos3

If $A \subset \mathbb{N}$ has $\sum_{n \in A}\frac 1 n = \infty$, then must $A$ contain arbitrarily long arithmetic progressions?

Yes. This was proved by an internal OpenAI model in September 2026 [OAI26]; see the linked Lean proof.

@[category research solved, question, AMS 11, formal_proof using lean4 at "https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/lean/OAI/Combinatorics/Progressions/Results/Conclusions.lean#L38"] theorem erdos_3 : ∀ A : Set ℕ, (¬ Summable fun a : A ↦ 1 / (a : ℝ)) → ∃ᶠ (k : ℕ) in Filter.atTop, ∃ S ⊆ A, S.IsAPOfLength k := ⊢ ∀ (A : Set ℕ), (¬Summable fun a ↦ 1 / ↑↑a) → ∃ᶠ (k : ℕ) in atTop, ∃ S ⊆ A, S.IsAPOfLength ↑k All goals completed! 🐙

$r_k(N)$ is the largest size of a subset of ${1, \dots, N}$ that does not contain a non-trivial $k$-term arithmetic progression.

noncomputable abbrev r := Set.IsAPOfLengthFree.maxCard

There are $\beta > 0$ and $c > 0$ such that $r_3(N) \ll N \exp(-c (\log N)^{\beta})$.

Proved by Kelley and Meka [KeMe23].

@[category research solved, AMS 11] theorem erdos_3.variants.kelley_meka : ∃ β > (0 : ℝ), ∃ c > (0 : ℝ), (fun N ↦ (r 3 N : ℝ)) ≪ fun N : ℕ ↦ (N : ℝ) * Real.exp (-c * Real.log N ^ β) := ⊢ ∃ β > 0, ∃ c > 0, (fun N ↦ ↑(r 3 N)) =O[atTop] fun N ↦ ↑N * Real.exp (-c * Real.log ↑N ^ β) All goals completed! 🐙

The case of $3$-term progressions: if $A \subset \mathbb{N}$ has $\sum_{n \in A}\frac 1 n = \infty$, then $A$ contains a non-trivial $3$-term arithmetic progression.

Proved by Bloom and Sisask [BlSi20].

@[category research solved, AMS 11, conditional formal_proof using lean4 at "https://github.com/wilsonwu-ai/sundai-erdos-3/blob/8a58287a16558bf1e708eaa2d0f7cba4c86566a3/lean/Erdos3ThreeCase.lean#L96-L97" assuming erdos_3.variants.kelley_meka] theorem erdos_3.variants.three : ∀ A : Set ℕ, (¬ Summable fun a : A ↦ 1 / (a : ℝ)) → ∃ S ⊆ A, S.IsAPOfLength 3 := ⊢ ∀ (A : Set ℕ), (¬Summable fun a ↦ 1 / ↑↑a) → ∃ S ⊆ A, S.IsAPOfLength 3 All goals completed! 🐙

There is $c > 0$ such that $r_4(N) \ll N (\log N)^{-c}$.

Proved by Green and Tao [GrTa17].

@[category research solved, AMS 11] theorem erdos_3.variants.green_tao : ∃ c > (0 : ℝ), (fun N ↦ (r 4 N : ℝ)) ≪ fun N : ℕ ↦ (N : ℝ) * Real.log N ^ (-c) := ⊢ ∃ c > 0, (fun N ↦ ↑(r 4 N)) =O[atTop] fun N ↦ ↑N * Real.log ↑N ^ (-c) All goals completed! 🐙

For every $k \geq 3$ there is $c_k > 0$ such that $r_k(N) \ll_k N (\log \log N)^{-c_k}$.

Proved by Gowers [Go01].

@[category research solved, AMS 11] theorem erdos_3.variants.gowers (k : ℕ) (hk : 3 ≤ k) : ∃ c > (0 : ℝ), (fun N ↦ (r k N : ℝ)) ≪ fun N : ℕ ↦ (N : ℝ) * Real.log (Real.log N) ^ (-c) := k:ℕhk:3 ≤ k⊢ ∃ c > 0, (fun N ↦ ↑(r k N)) =O[atTop] fun N ↦ ↑N * Real.log (Real.log ↑N) ^ (-c) All goals completed! 🐙

For every $k \geq 5$ there is $c_k > 0$ such that $r_k(N) \ll_k N \exp(-(\log \log N)^{c_k})$.

Proved by Leng, Sah and Sawhney [LSS24].

@[category research solved, AMS 11] theorem erdos_3.variants.leng_sah_sawhney (k : ℕ) (hk : 5 ≤ k) : ∃ c > (0 : ℝ), (fun N ↦ (r k N : ℝ)) ≪ fun N : ℕ ↦ (N : ℝ) * Real.exp (-Real.log (Real.log N) ^ c) := k:ℕhk:5 ≤ k⊢ ∃ c > 0, (fun N ↦ ↑(r k N)) =O[atTop] fun N ↦ ↑N * Real.exp (-Real.log (Real.log ↑N) ^ c) All goals completed! 🐙end Erdos3