/-
Copyright 2026 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 FormalConjecturesUtilErdős Problem 787
References:
[Be25] Beker, A., The Erdős-Moser sum-free set problem via improved bounds for $k$-configurations. arXiv:2501.10203 (2025).
[Ch71] Choi, S. L. G., On a combinatorial problem in number theory. Proc. London Math. Soc. (3) (1971), 629-642.
[Er65] Erdős, P., Extremal problems in number theory. Proc. Sympos. Pure Math., Vol. VIII (1965), 181-189. PDF
[Er73] Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138. PDF
[Ru05] Ruzsa, Imre Z., Sum-avoiding subsets. Ramanujan J. (2005), 77-82.
[Sa21] Sanders, Tom, The Erdős-Moser sum-free set problem. Canad. J. Math. (2021), 63-107.
@[expose] public sectionopen Filter Asymptoticsnamespace Erdos787
g G n is the largest m such that every set A of n elements of G has a subset B with
$\lvert B\rvert \geq m$ and $b_1 + b_2 \notin A$ for all distinct $b_1, b_2 \in B$
[Er65, p. 187]. The problem takes G = ℝ.
The condition on B is Disjoint B.restrictedSumset A. For G = ℝ or G = ℤ, the set of such
m contains 0 and is bounded by n, so sSup is its maximum, not a junk value.
noncomputable def g (G : Type*) [Add G] [DecidableEq G] (n : ℕ) : ℕ :=
sSup {m : ℕ | ∀ A : Finset G, A.card = n →
∃ B ⊆ A, m ≤ B.card ∧ Disjoint B.restrictedSumset A}
Disjoint B.restrictedSumset A says that $b_1 + b_2 \notin A$ for all distinct
$b_1, b_2 \in B$.
G:Type u_1inst✝¹:Add Ginst✝:DecidableEq GA:Finset GB:Finset G⊢ (∀ ⦃a : G⦄, a ∈ Finset.image (fun p ↦ p.1 + p.2) B.offDiag → a ∉ A) ↔ ∀ b₁ ∈ B, ∀ b₂ ∈ B, b₁ ≠ b₂ → b₁ + b₂ ∉ A
constructor mp G:Type u_1inst✝¹:Add Ginst✝:DecidableEq GA:Finset GB:Finset G⊢ (∀ ⦃a : G⦄, a ∈ Finset.image (fun p ↦ p.1 + p.2) B.offDiag → a ∉ A) → ∀ b₁ ∈ B, ∀ b₂ ∈ B, b₁ ≠ b₂ → b₁ + b₂ ∉ Ampr G:Type u_1inst✝¹:Add Ginst✝:DecidableEq GA:Finset GB:Finset G⊢ (∀ b₁ ∈ B, ∀ b₂ ∈ B, b₁ ≠ b₂ → b₁ + b₂ ∉ A) → ∀ ⦃a : G⦄, a ∈ Finset.image (fun p ↦ p.1 + p.2) B.offDiag → a ∉ A
· mp G:Type u_1inst✝¹:Add Ginst✝:DecidableEq GA:Finset GB:Finset G⊢ (∀ ⦃a : G⦄, a ∈ Finset.image (fun p ↦ p.1 + p.2) B.offDiag → a ∉ A) → ∀ b₁ ∈ B, ∀ b₂ ∈ B, b₁ ≠ b₂ → b₁ + b₂ ∉ A intro h b₁ hb₁ b₂ hb₂ hne hmem mp G:Type u_1inst✝¹:Add Ginst✝:DecidableEq GA:Finset GB:Finset Gh:∀ ⦃a : G⦄, a ∈ Finset.image (fun p ↦ p.1 + p.2) B.offDiag → a ∉ Ab₁:Ghb₁:b₁ ∈ Bb₂:Ghb₂:b₂ ∈ Bhne:b₁ ≠ b₂hmem:b₁ + b₂ ∈ A⊢ False
have hmem' : b₁ + b₂ ∈ Finset.image (fun p : G × G => p.1 + p.2) B.offDiag :=
Finset.mem_image.2 ⟨(b₁, b₂), Finset.mem_offDiag.2 ⟨hb₁, hb₂, hne⟩, rfl⟩ mp G:Type u_1inst✝¹:Add Ginst✝:DecidableEq GA:Finset GB:Finset Gh:∀ ⦃a : G⦄, a ∈ Finset.image (fun p ↦ p.1 + p.2) B.offDiag → a ∉ Ab₁:Ghb₁:b₁ ∈ Bb₂:Ghb₂:b₂ ∈ Bhne:b₁ ≠ b₂hmem:b₁ + b₂ ∈ Ahmem':b₁ + b₂ ∈ Finset.image (fun p ↦ p.1 + p.2) B.offDiag⊢ False
exact h hmem' hmem All goals completed! 🐙
· mpr G:Type u_1inst✝¹:Add Ginst✝:DecidableEq GA:Finset GB:Finset G⊢ (∀ b₁ ∈ B, ∀ b₂ ∈ B, b₁ ≠ b₂ → b₁ + b₂ ∉ A) → ∀ ⦃a : G⦄, a ∈ Finset.image (fun p ↦ p.1 + p.2) B.offDiag → a ∉ A intro h x hx hxA mpr G:Type u_1inst✝¹:Add Ginst✝:DecidableEq GA:Finset GB:Finset Gh:∀ b₁ ∈ B, ∀ b₂ ∈ B, b₁ ≠ b₂ → b₁ + b₂ ∉ Ax:Ghx:x ∈ Finset.image (fun p ↦ p.1 + p.2) B.offDiaghxA:x ∈ A⊢ False
obtain ⟨⟨b₁, b₂⟩, hp, rfl⟩ := Finset.mem_image.1 hx mpr G:Type u_1inst✝¹:Add Ginst✝:DecidableEq GA:Finset GB:Finset Gh:∀ b₁ ∈ B, ∀ b₂ ∈ B, b₁ ≠ b₂ → b₁ + b₂ ∉ Ab₁:Gb₂:Ghp:(b₁, b₂) ∈ B.offDiaghx:(b₁, b₂).1 + (b₁, b₂).2 ∈ Finset.image (fun p ↦ p.1 + p.2) B.offDiaghxA:(b₁, b₂).1 + (b₁, b₂).2 ∈ A⊢ False
obtain ⟨hb₁, hb₂, hne⟩ := Finset.mem_offDiag.1 hp mpr G:Type u_1inst✝¹:Add Ginst✝:DecidableEq GA:Finset GB:Finset Gh:∀ b₁ ∈ B, ∀ b₂ ∈ B, b₁ ≠ b₂ → b₁ + b₂ ∉ Ab₁:Gb₂:Ghp:(b₁, b₂) ∈ B.offDiaghx:(b₁, b₂).1 + (b₁, b₂).2 ∈ Finset.image (fun p ↦ p.1 + p.2) B.offDiaghxA:(b₁, b₂).1 + (b₁, b₂).2 ∈ Ahb₁:(b₁, b₂).1 ∈ Bhb₂:(b₁, b₂).2 ∈ Bhne:(b₁, b₂).1 ≠ (b₁, b₂).2⊢ False
exact h b₁ hb₁ b₂ hb₂ hne hxA All goals completed! 🐙
If every set of n reals has a subset B of size at least m with
Disjoint B.restrictedSumset A, then m ≤ g ℝ n.
@[category API, AMS 5 11]
theorem le_g {n m : ℕ} (h : ∀ A : Finset ℝ, A.card = n →
∃ B ⊆ A, m ≤ B.card ∧ Disjoint B.restrictedSumset A) : m ≤ g ℝ n := by n:ℕm:ℕh:∀ (A : Finset ℝ), A.card = n → ∃ B ⊆ A, m ≤ B.card ∧ Disjoint B.restrictedSumset A⊢ m ≤ g ℝ n
refine le_csSup (bddAbove_def.2 ⟨n, fun m' hm' => ?_⟩) h n:ℕm:ℕh:∀ (A : Finset ℝ), A.card = n → ∃ B ⊆ A, m ≤ B.card ∧ Disjoint B.restrictedSumset Am':ℕhm':m' ∈ {m | ∀ (A : Finset ℝ), A.card = n → ∃ B ⊆ A, m ≤ B.card ∧ Disjoint B.restrictedSumset A}⊢ m' ≤ n
have hm'' : ∀ A : Finset ℝ, A.card = n →
∃ B ⊆ A, m' ≤ B.card ∧ Disjoint B.restrictedSumset A := hm' n:ℕm:ℕh:∀ (A : Finset ℝ), A.card = n → ∃ B ⊆ A, m ≤ B.card ∧ Disjoint B.restrictedSumset Am':ℕhm':m' ∈ {m | ∀ (A : Finset ℝ), A.card = n → ∃ B ⊆ A, m ≤ B.card ∧ Disjoint B.restrictedSumset A}hm'':∀ (A : Finset ℝ), A.card = n → ∃ B ⊆ A, m' ≤ B.card ∧ Disjoint B.restrictedSumset A⊢ m' ≤ n
obtain ⟨A, hA⟩ := Infinite.exists_subset_card_eq ℝ n n:ℕm:ℕh:∀ (A : Finset ℝ), A.card = n → ∃ B ⊆ A, m ≤ B.card ∧ Disjoint B.restrictedSumset Am':ℕhm':m' ∈ {m | ∀ (A : Finset ℝ), A.card = n → ∃ B ⊆ A, m ≤ B.card ∧ Disjoint B.restrictedSumset A}hm'':∀ (A : Finset ℝ), A.card = n → ∃ B ⊆ A, m' ≤ B.card ∧ Disjoint B.restrictedSumset AA:Finset ℝhA:A.card = n⊢ m' ≤ n
obtain ⟨B, hBA, hmB, -⟩ := hm'' A hA n:ℕm:ℕh:∀ (A : Finset ℝ), A.card = n → ∃ B ⊆ A, m ≤ B.card ∧ Disjoint B.restrictedSumset Am':ℕhm':m' ∈ {m | ∀ (A : Finset ℝ), A.card = n → ∃ B ⊆ A, m ≤ B.card ∧ Disjoint B.restrictedSumset A}hm'':∀ (A : Finset ℝ), A.card = n → ∃ B ⊆ A, m' ≤ B.card ∧ Disjoint B.restrictedSumset AA:Finset ℝhA:A.card = nB:Finset ℝhBA:B ⊆ AhmB:m' ≤ B.card⊢ m' ≤ n
exact hmB.trans ((Finset.card_le_card hBA).trans_eq hA) All goals completed! 🐙def erdos_787.answer : ℕ → ℝ := sorryLet $g(n)$ be maximal such that given any set $A\subset \mathbb{R}$ with $\lvert A\rvert=n$ there exists some $B\subseteq A$ of size $\lvert B\rvert\geq g(n)$ such that $b_1+b_2\not\in A$ for all $b_1\neq b_2\in B$.
Estimate $g(n)$.
@[category research open, question value, AMS 5 11]
theorem erdos_787 : (fun n ↦ (g ℝ n : ℝ)) =Θ[atTop] erdos_787.answer := by ⊢ (fun n ↦ ↑(g ℝ n)) =Θ[atTop] erdos_787.answer
sorry All goals completed! 🐙This function was considered by Erdős and Moser. Choi observed that, without loss of generality, one can assume that $A\subset \mathbb{Z}$.
Here this means that sets of integers give the same value $g(n)$ as sets of reals.
@[category research solved, AMS 5 11]
theorem erdos_787.variants.integers (n : ℕ) : g ℤ n = g ℝ n := by n:ℕ⊢ g ℤ n = g ℝ n
sorry All goals completed! 🐙Klarner proved $g(n) \gg \log n$ (indeed, a greedy construction suffices).
@[category research solved, AMS 5 11]
theorem erdos_787.variants.klarner :
∃ c > (0 : ℝ), ∀ᶠ n : ℕ in atTop, c * Real.log n ≤ (g ℝ n : ℝ) := by ⊢ ∃ c > 0, ∀ᶠ (n : ℕ) in atTop, c * Real.log ↑n ≤ ↑(g ℝ n)
sorry All goals completed! 🐙Choi [Ch71] proved $g(n) \ll n^{2/5+o(1)}$.
Here this means that $g(n) \leq n^{2/5+\varepsilon}$ for every $\varepsilon > 0$ and all large $n$, as in [Er73, p. 130].
@[category research solved, AMS 5 11]
theorem erdos_787.variants.choi :
∀ ε > (0 : ℝ), ∀ᶠ n : ℕ in atTop, (g ℝ n : ℝ) ≤ (n : ℝ) ^ (2 / 5 + ε) := by ⊢ ∀ ε > 0, ∀ᶠ (n : ℕ) in atTop, ↑(g ℝ n) ≤ ↑n ^ (2 / 5 + ε)
sorry All goals completed! 🐙The current best bounds known are $$(\log n)^{1+c} \ll g(n) \ll \exp(\sqrt{\log n})$$ for some constant $c>0$, the lower bound due to Sanders [Sa21] and the upper bound due to Ruzsa [Ru05].
This is the lower bound.
@[category research solved, AMS 5 11]
theorem erdos_787.variants.sanders :
∃ c > (0 : ℝ), ∀ᶠ n : ℕ in atTop, Real.log n ^ (1 + c) ≤ (g ℝ n : ℝ) := by ⊢ ∃ c > 0, ∀ᶠ (n : ℕ) in atTop, Real.log ↑n ^ (1 + c) ≤ ↑(g ℝ n)
sorry All goals completed! 🐙The current best bounds known are $$(\log n)^{1+c} \ll g(n) \ll \exp(\sqrt{\log n})$$ for some constant $c>0$, the lower bound due to Sanders [Sa21] and the upper bound due to Ruzsa [Ru05].
This is the upper bound. [Ru05] proves it in the form $\exp(O(\sqrt{\log n}))$, which is the form stated here.
@[category research solved, AMS 5 11]
theorem erdos_787.variants.ruzsa :
∃ C > (0 : ℝ), ∀ᶠ n : ℕ in atTop, (g ℝ n : ℝ) ≤ Real.exp (C * Real.sqrt (Real.log n)) := by ⊢ ∃ C > 0, ∀ᶠ (n : ℕ) in atTop, ↑(g ℝ n) ≤ Real.exp (C * √(Real.log ↑n))
sorry All goals completed! 🐙Beker [Be25] has proved $$(\log n)^{1+\tfrac{1}{68}+o(1)} \ll g(n).$$
Here this means that $g(n) \geq (\log n)^{1+c}$ for every $c < 1/68$ and all large $n$ [Be25, Theorem 1.2].
@[category research solved, AMS 5 11]
theorem erdos_787.variants.beker :
∀ c : ℝ, 0 < c → c < 1 / 68 → ∀ᶠ n : ℕ in atTop, Real.log n ^ (1 + c) ≤ (g ℝ n : ℝ) := by ⊢ ∀ (c : ℝ), 0 < c → c < 1 / 68 → ∀ᶠ (n : ℕ) in atTop, Real.log ↑n ^ (1 + c) ≤ ↑(g ℝ n)
sorry All goals completed! 🐙end Erdos787