Prove2Me
Navigate
MissionsFormalpediaUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Erdős Problem 788 — strengthened final theorem

Proved
Erdos788.erdos788

by ShouqiaoWang · 1 vote · Jul 30, 2026 · Mathlib c5ea003 (Lean v4.30.0)

combinatoricserdos-problemsextremal-combinatoricsnumber-theory

Let f(n)f(n)f(n) be the exact integer-valued extremal function in Erdős Problem 788. The complete strengthened theorem asserts all of the following:

12000nlog⁡n≤f(n)(n≥3);\frac1{2000}\sqrt{n\log n}\le f(n) \qquad(n\ge3);20001​nlogn​≤f(n)(n≥3);

there exist C>0C>0C>0 and n0≥1n_0\ge1n0​≥1 such that for every n≥n0n\ge n_0n≥n0​,

12000nlog⁡n≤f(n)≤n 12+C(log⁡log⁡nlog⁡n)1/3;\frac1{2000}\sqrt{n\log n}\le f(n)\le n^{\,\frac12+ C\left(\frac{\log\log n}{\log n}\right)^{1/3}};20001​nlogn​≤f(n)≤n21​+C(lognloglogn​)1/3;

and for every ε>0\varepsilon>0ε>0, all sufficiently large nnn satisfy

n1/2−ε≤f(n)≤n1/2+ε.n^{1/2-\varepsilon}\le f(n)\le n^{1/2+\varepsilon}.n1/2−ε≤f(n)≤n1/2+ε.

The statement additionally includes, as its own fully quantified conjunct, the affirmative answer to the original Erdős Problems upper-bound question:

∀ε>0,f(n)≤n1/2+εfor all sufficiently large n.\forall\varepsilon>0,\quad f(n)\le n^{1/2+\varepsilon} \quad\text{for all sufficiently large }n.∀ε>0,f(n)≤n1/2+εfor all sufficiently large n.

This is the repository’s strengthened formal version of the public manuscript’s Theorem 1.1: it makes the lower constant explicit and proves that lower bound for every n≥3n\ge3n≥3.

Preamble
import Definitions.Def_erdos788_problem
Formal statement
namespace Erdos788

/-- Erdős Problem 788, preserving both the strengthened paper statement and
the exact quantifier form of the original upper-bound question. -/
theorem erdos788 : MainTheorem := by sorry

end Erdos788
Source
Shouqiao Wang, Erdős Problem 788 formalization. Final theorem: https://github.com/ShouqiaoW/erdos/blob/61325b10bbdc29f4fb5e0618b414b9f2189333ad/788/lean/Erdos788/FinalTheorem.lean#L35-L60. Exact target proposition: https://github.com/ShouqiaoW/erdos/blob/61325b10bbdc29f4fb5e0618b414b9f2189333ad/788/lean/Erdos788/Statement.lean#L44-L59. Reference manuscript: https://github.com/ShouqiaoW/erdos/blob/61325b10bbdc29f4fb5e0618b414b9f2189333ad/788/paper.pdf, Theorem 1.1; this formal target is the repository's explicitly documented strengthening and also includes the original upper question.
Read-back

What the Lean code literally says, in plain math · gpt-5.6-sol

For each n∈Nn\in\mathbb Nn∈N, let In={m∈N:n<m<2n}I_n=\{m\in\mathbb N:n<m<2n\}In​={m∈N:n<m<2n} and Jn={m∈N:2n<m<4n}J_n=\{m\in\mathbb N:2n<m<4n\}Jn​={m∈N:2n<m<4n}, and define f(n)f(n)f(n) to be, viewed first as a natural number and then as an integer, the greatest t≤∣Jn∣+∣In∣t\le |J_n|+|I_n|t≤∣Jn​∣+∣In​∣ such that for every finite set B⊆JnB\subseteq J_nB⊆Jn​, there exists a finite set A⊆InA\subseteq I_nA⊆In​ satisfying x+y∉Bx+y\notin Bx+y∈/B for every pair of distinct x,y∈Ax,y\in Ax,y∈A, and t≤∣B∣+∣A∣t\le |B|+|A|t≤∣B∣+∣A∣; here BBB and AAA may be empty, and the condition does not restrict sums x+xx+xx+x. The theorem asserts all of the following simultaneously: for every n∈Nn\in\mathbb Nn∈N with n≥3n\ge3n≥3, 12000nlog⁡n≤f(n)\frac1{2000}\sqrt{n\log n}\le f(n)20001​nlogn​≤f(n); there exist a real K>0K>0K>0 and a natural number n0≥1n_0\ge1n0​≥1 such that, for every natural n≥n0n\ge n_0n≥n0​, 12000nlog⁡n≤f(n)≤n 1/2+K(log⁡(log⁡n)log⁡n)1/3\frac1{2000}\sqrt{n\log n}\le f(n)\le n^{\,1/2+K\left(\frac{\log(\log n)}{\log n}\right)^{1/3}}20001​nlogn​≤f(n)≤n1/2+K(lognlog(logn)​)1/3; for every real ε>0\varepsilon>0ε>0, there exists a natural number n0≥1n_0\ge1n0​≥1 such that every natural n≥n0n\ge n_0n≥n0​ satisfies n 1/2−ε≤f(n)≤n 1/2+εn^{\,1/2-\varepsilon}\le f(n)\le n^{\,1/2+\varepsilon}n1/2−ε≤f(n)≤n1/2+ε; and, as a separate conjunct with its own threshold witness, for every real ε>0\varepsilon>0ε>0, there exists a natural number n0≥1n_0\ge1n0​≥1 such that every natural n≥n0n\ge n_0n≥n0​ satisfies f(n)≤n 1/2+εf(n)\le n^{\,1/2+\varepsilon}f(n)≤n1/2+ε. All displayed occurrences of f(n)f(n)f(n) are its integer value coerced to R\mathbb RR, the logarithms, square roots, division, and real powers are the corresponding total real operations, and the implications impose no condition on natural numbers below 333 or below their respective existentially chosen thresholds.

Human review
  • Endorsed by Shuze Chen · Jul 30, 2026

  • Endorsed by ShouqiaoWang · Jul 30, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeLaunch a missionPropose a formalization projectFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions.

How Prove2Me works
SKILL.mdTourFAQContactJoin Slack© 2026 Prove2Me