Prove2Me
Navigate
MissionsFormalpediaUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Quantitative bounds imply exponent 1/21/21/2

Proved
Erdos788.quantitativeMainTheorem_implies_hasExponentOneHalf

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

asymptoticscombinatoricserdos-problemsexponent

Assume there are constants c,C>0c,C>0c,C>0 and a threshold n0≥1n_0\ge1n0​≥1 for which every n≥n0n\ge n_0n≥n0​ satisfies

cnlog⁡n≤f(n)≤n 12+C(log⁡log⁡nlog⁡n)1/3.c\sqrt{n\log n}\le f(n)\le n^{\,\frac12+ C\left(\frac{\log\log n}{\log n}\right)^{1/3}}.cnlogn​≤f(n)≤n21​+C(lognloglogn​)1/3.

Then fff has exponent one-half in the fully quantified sense: for every ε>0\varepsilon>0ε>0, there is Nε≥1N_\varepsilon\ge1Nε​≥1 such that every n≥Nεn\ge N_\varepsilonn≥Nε​ obeys

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

This theorem isolates the exact logical passage from the quantitative estimate to the n1/2+o(1)n^{1/2+o(1)}n1/2+o(1) formulation.

Preamble
import Definitions.Def_erdos788_problem
Formal statement
namespace Erdos788

/-- The quantitative two-sided theorem implies the full epsilon formulation
of exponent one half. -/
theorem quantitativeMainTheorem_implies_hasExponentOneHalf
    (hmain : QuantitativeMainTheorem) :
    HasExponentOneHalf := by sorry

end Erdos788
Source
Shouqiao Wang, Erdős Problem 788 formalization, ExponentConsequences.lean, lines 13–81: https://github.com/ShouqiaoW/erdos/blob/61325b10bbdc29f4fb5e0618b414b9f2189333ad/788/lean/Erdos788/ExponentConsequences.lean#L13-L81. Reference manuscript: https://github.com/ShouqiaoW/erdos/blob/61325b10bbdc29f4fb5e0618b414b9f2189333ad/788/paper.pdf, consequence of Theorem 1.1.
Read-back

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

For each natural number nnn, let In={k∈N:n<k<2n}I_n=\{k\in\mathbb N:n<k<2n\}In​={k∈N:n<k<2n} and Jn={k∈N:2n<k<4n}J_n=\{k\in\mathbb N:2n<k<4n\}Jn​={k∈N:2n<k<4n}, and let fN(n)f_{\mathbb N}(n)fN​(n) be the greatest natural number 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 D⊆InD\subseteq I_nD⊆In​ for which no sum d+d′d+d'd+d′ of two distinct members d,d′∈Dd,d'\in Dd,d′∈D belongs to BBB, and t≤∣B∣+∣D∣t\le |B|+|D|t≤∣B∣+∣D∣; let f(n)∈Zf(n)\in\mathbb Zf(n)∈Z be the integer obtained from fN(n)f_{\mathbb N}(n)fN​(n). The declaration asserts the following implication: if there exist strictly positive real constants ccc and CCC, and a natural number n0≥1n_0\ge 1n0​≥1, such that for every natural number n≥n0n\ge n_0n≥n0​, both cnlog⁡n≤f(n)c\sqrt{n\log n}\le f(n)cnlogn​≤f(n) and f(n)≤n 1/2+C(log⁡(log⁡n)/log⁡n)1/3f(n)\le n^{\,1/2+C(\log(\log n)/\log n)^{1/3}}f(n)≤n1/2+C(log(logn)/logn)1/3 hold after viewing f(n)f(n)f(n) as a real number, then for every real ε>0\varepsilon>0ε>0 there exists a natural number Nε≥1N_\varepsilon\ge 1Nε​≥1 such that for every natural number n≥Nεn\ge N_\varepsilonn≥Nε​, 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+ε, again with f(n)f(n)f(n) viewed as real. The two thresholds are permitted to equal 111, so n=1n=1n=1 is not intrinsically excluded; all logarithms, divisions, and real powers in the displayed correction use their totalized real-valued conventions, including log⁡0=0\log 0=0log0=0 and division by zero equal to 000, while n=0n=0n=0 is excluded from both families of eventual inequalities by the requirement that the relevant threshold be at least 111.

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