Prove2Me
Navigate
MissionsFormalpediaUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Exact greatest-integer semantics of f(n)f(n)f(n)

Proved
Erdos788.f_isGreatestIntegerGuarantee

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

combinatoricserdos-problemsformalization

For every n∈Nn\in\mathbb Nn∈N, the integer f(n)f(n)f(n) has the universal guarantee from Erdős Problem 788, and it is maximal among all integer thresholds with that guarantee:

IntegerGuarantees⁡(n,f(n))and∀t∈Z,  IntegerGuarantees⁡(n,t)⟹t≤f(n).\operatorname{IntegerGuarantees}(n,f(n)) \quad\text{and}\quad \forall t\in\mathbb Z,\; \operatorname{IntegerGuarantees}(n,t)\Longrightarrow t\le f(n).IntegerGuarantees(n,f(n))and∀t∈Z,IntegerGuarantees(n,t)⟹t≤f(n).

Thus the bounded natural-number construction used to define fff recovers the exact “greatest integer” quantifier order in the original problem, including negative candidate thresholds and the edge case n=0n=0n=0.

Preamble
import Definitions.Def_erdos788_problem
Formal statement
namespace Erdos788

/-- `f n` is exactly the greatest integer having the universal guarantee in
the original finite problem. -/
theorem f_isGreatestIntegerGuarantee (n : ℕ) :
    IntegerGuarantees n (f n) ∧
      ∀ t : ℤ, IntegerGuarantees n t → t ≤ f n := by sorry

end Erdos788
Source
Shouqiao Wang, Erdős Problem 788 formalization, Definitions.lean, lines 92–96: https://github.com/ShouqiaoW/erdos/blob/61325b10bbdc29f4fb5e0618b414b9f2189333ad/788/lean/Erdos788/Definitions.lean#L92-L96.
Read-back

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

For every natural number nnn, including n=0n=0n=0, set 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}. For a natural number kkk, let Gn(k)G_n(k)Gn​(k) mean that for every finite set B⊆JnB\subseteq J_nB⊆Jn​, there exists a finite set C⊆InC\subseteq I_nC⊆In​ such that c+c′∉Bc+c'\notin Bc+c′∈/B for every two distinct elements c,c′∈Cc,c'\in Cc,c′∈C, and k≤∣B∣+∣C∣k\le |B|+|C|k≤∣B∣+∣C∣. The integer f(n)f(n)f(n) is the integer coercion of the bounded-search value that returns the greatest natural number k≤∣Jn∣+∣In∣k\le |J_n|+|I_n|k≤∣Jn​∣+∣In​∣ satisfying Gn(k)G_n(k)Gn​(k), with value 000 if no such kkk exists. The theorem asserts both that, for every finite B⊆JnB\subseteq J_nB⊆Jn​, there is a finite C⊆InC\subseteq I_nC⊆In​ with no sum of two distinct members of CCC belonging to BBB and with f(n)≤∣B∣+∣C∣f(n)\le |B|+|C|f(n)≤∣B∣+∣C∣ after the cardinality is regarded as an integer, and that every integer ttt—including negative integers—with this same universal property satisfies t≤f(n)t\le f(n)t≤f(n). Thus the asserted maximality is among all integer thresholds, although f(n)f(n)f(n) itself is nonnegative by definition. In the included case n=0n=0n=0, both intervals are empty, so the only possible BBB and admissible CCC are empty and the guarantee reduces to t≤0t\le 0t≤0.

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