/-
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 131
References:
[ELRSS99] Erdős, P. and Lev, V. and Rauzy, G. and Sándor, C. and Sárközy, A., Greedy algorithm, arithmetic progressions, subset sums and divisibility. Discrete Math. (1999), 119-135.
[PhZa24] Pham, H. T. and Zakharov, D., Sharp bound for the Erdős–Straus non-averaging set problem. arXiv:2410.14624 (2024).
@[expose] public sectionopen Filter Topologynamespace Erdos131A finite set $A$ of naturals is non-dividing if no $a \in A$ divides the sum of the elements of any nonempty subset $S \subseteq A \setminus {a}$.
def NonDividing (A : Finset ℕ) : Prop :=
∀ a ∈ A, ∀ S ⊆ A.erase a, S.Nonempty → ¬ a ∣ ∑ x ∈ S, xinstance (A : Finset ℕ) : Decidable (NonDividing A) := A:Finset ℕ⊢ Decidable (NonDividing A)
A:Finset ℕ⊢ Decidable (∀ a ∈ A, ∀ S ⊆ A.erase a, S.Nonempty → ¬a ∣ ∑ x ∈ S, x); All goals completed! 🐙$F(N)$ is the maximal size of a non-dividing subset of ${1, \dots, N}$.
def F (N : ℕ) : ℕ :=
(((Finset.Icc 1 N).powerset).filter NonDividing).sup Finset.card$F(N)$ is attained: some non-dividing $A \subseteq {1, \dots, N}$ has exactly $F(N)$ elements.
N:ℕA:Finset ℕhA:A ∈ Finset.filter NonDividing (Finset.Icc 1 N).powerseth:(Finset.filter NonDividing (Finset.Icc 1 N).powerset).sup Finset.card = A.card⊢ ∃ A ⊆ Finset.Icc 1 N, NonDividing A ∧ A.card = F N
simp only [Finset.mem_filter, Finset.mem_powerset] at hA N:ℕA:Finset ℕh:(Finset.filter NonDividing (Finset.Icc 1 N).powerset).sup Finset.card = A.cardhA:A ⊆ Finset.Icc 1 N ∧ NonDividing A⊢ ∃ A ⊆ Finset.Icc 1 N, NonDividing A ∧ A.card = F N
exact ⟨A, hA.1, hA.2, h.symm⟩ All goals completed! 🐙Every non-dividing $A \subseteq {1, \dots, N}$ has at most $F(N)$ elements.
@[category API, AMS 11]
theorem card_le_F {N : ℕ} {A : Finset ℕ} (hA : A ⊆ Finset.Icc 1 N) (hnd : NonDividing A) :
A.card ≤ F N :=
Finset.le_sup (f := Finset.card) (by N:ℕA:Finset ℕhA:A ⊆ Finset.Icc 1 Nhnd:NonDividing A⊢ A ∈ Finset.filter NonDividing (Finset.Icc 1 N).powerset simp [hA, hnd] All goals completed! 🐙)Trivial upper bound: $F(N) \le N$.
@[category API, AMS 11]
theorem F_le (N : ℕ) : F N ≤ N := by N:ℕ⊢ F N ≤ N
obtain ⟨A, hA, -, h⟩ := exists_card_eq_F N N:ℕA:Finset ℕhA:A ⊆ Finset.Icc 1 Nh:A.card = F N⊢ F N ≤ N
simpa [← h] using Finset.card_le_card hA All goals completed! 🐙$F$ is monotone.
@[category API, AMS 11]
theorem F_mono : Monotone F := fun _ _ hMN =>
let ⟨_, hA, hnd, h⟩ := exists_card_eq_F _
h ▸ card_le_F (hA.trans (Finset.Icc_subset_Icc_right hMN)) hndTrivial lower bound: for $N \ge 1$, the singleton ${N}$ is non-dividing, so $1 \le F(N)$.
@[category API, AMS 11]
theorem one_le_F {N : ℕ} (hN : 1 ≤ N) : 1 ≤ F N := by N:ℕhN:1 ≤ N⊢ 1 ≤ F N
have h := card_le_F (N := N) (A := {N}) (by N:ℕhN:1 ≤ N⊢ {N} ⊆ Finset.Icc 1 N N:ℕhN:1 ≤ Nh:{N}.card ≤ F N⊢ 1 ≤ F N simp [hN] All goals completed! 🐙 N:ℕhN:1 ≤ Nh:{N}.card ≤ F N⊢ 1 ≤ F N) (by N:ℕhN:1 ≤ N⊢ NonDividing {N} N:ℕhN:1 ≤ Nh:{N}.card ≤ F N⊢ 1 ≤ F N
intro a ha S hS hne N:ℕhN:1 ≤ Na:ℕha:a ∈ {N}S:Finset ℕhS:S ⊆ {N}.erase ahne:S.Nonempty⊢ ¬a ∣ ∑ x ∈ S, x N:ℕhN:1 ≤ Nh:{N}.card ≤ F N⊢ 1 ≤ F N
have : S = ∅ := by N:ℕhN:1 ≤ N⊢ NonDividing {N} N:ℕhN:1 ≤ Na:ℕha:a ∈ {N}S:Finset ℕhS:S ⊆ {N}.erase ahne:S.Nonemptythis:S = ∅⊢ ¬a ∣ ∑ x ∈ S, x N:ℕhN:1 ≤ Nh:{N}.card ≤ F N⊢ 1 ≤ F N simpa [Finset.mem_singleton.1 ha] using hS N:ℕhN:1 ≤ Na:ℕha:a ∈ {N}S:Finset ℕhS:S ⊆ {N}.erase ahne:S.Nonemptythis:S = ∅⊢ ¬a ∣ ∑ x ∈ S, x N:ℕhN:1 ≤ Nh:{N}.card ≤ F N⊢ 1 ≤ F N N:ℕhN:1 ≤ Na:ℕha:a ∈ {N}S:Finset ℕhS:S ⊆ {N}.erase ahne:S.Nonemptythis:S = ∅⊢ ¬a ∣ ∑ x ∈ S, x N:ℕhN:1 ≤ Nh:{N}.card ≤ F N⊢ 1 ≤ F N
simp [this] at hne All goals completed! 🐙 N:ℕhN:1 ≤ Nh:{N}.card ≤ F N⊢ 1 ≤ F N) N:ℕhN:1 ≤ Nh:{N}.card ≤ F N⊢ 1 ≤ F N
simpa using h All goals completed! 🐙Every non-dividing set is non-averaging. Pham and Zakharov [PhZa24] proved that a non-averaging subset of ${1, \dots, N}$ has size at most $N^{1/4 + o(1)}$, so $F(N) \le N^{1/4 + o(1)}$.
@[category research solved, AMS 11]
theorem erdos_131.variants.pham_zakharov :
∃ f : ℕ → ℝ, Tendsto f atTop (𝓝 0) ∧
∀ᶠ N : ℕ in atTop, (F N : ℝ) ≤ (N : ℝ) ^ ((1 : ℝ) / 4 + f N) := by ⊢ ∃ f, Tendsto f atTop (𝓝 0) ∧ ∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + f N)
sorry All goals completed! 🐙Erdős, Lev, Rauzy, Sándor and Sárközy [ELRSS99] proved $F(N) < 3 N^{1/2} + 1$.
@[category research solved, AMS 11]
theorem erdos_131.variants.elrss (N : ℕ) : (F N : ℝ) < 3 * Real.sqrt N + 1 := by N:ℕ⊢ ↑(F N) < 3 * √↑N + 1
sorry All goals completed! 🐙Let $F(N)$ be the maximal size of $A \subseteq {1, \dots, N}$ such that no $a \in A$ divides the sum of any distinct elements of $A \setminus {a}$. Is it true that $F(N) > N^{1/2 - o(1)}$?
The answer is no, by the bound of Pham and Zakharov [PhZa24]
(erdos_131.variants.pham_zakharov).
@[category research solved, question, AMS 11]
theorem erdos_131 :
¬ ∃ f : ℕ → ℝ, Tendsto f atTop (𝓝 0) ∧
∀ᶠ N : ℕ in atTop, (N : ℝ) ^ ((1 : ℝ) / 2 - f N) < (F N : ℝ) := by ⊢ ¬∃ f, Tendsto f atTop (𝓝 0) ∧ ∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)
rintro ⟨f, hf, hlow⟩ f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)⊢ False
obtain ⟨g, hg, hup⟩ := erdos_131.variants.pham_zakharov f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)⊢ False
have hf' : ∀ᶠ N : ℕ in atTop, f N < 1 / 8 := hf.eventually (gt_mem_nhds (by f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)⊢ 0 < 1 / 8 f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)hf':∀ᶠ (N : ℕ) in atTop, f N < 1 / 8⊢ False norm_num All goals completed! 🐙 f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)hf':∀ᶠ (N : ℕ) in atTop, f N < 1 / 8⊢ False)) f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)hf':∀ᶠ (N : ℕ) in atTop, f N < 1 / 8⊢ False
have hg' : ∀ᶠ N : ℕ in atTop, g N < 1 / 8 := hg.eventually (gt_mem_nhds (by f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)hf':∀ᶠ (N : ℕ) in atTop, f N < 1 / 8⊢ 0 < 1 / 8 f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)hf':∀ᶠ (N : ℕ) in atTop, f N < 1 / 8hg':∀ᶠ (N : ℕ) in atTop, g N < 1 / 8⊢ False norm_num All goals completed! 🐙 f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)hf':∀ᶠ (N : ℕ) in atTop, f N < 1 / 8hg':∀ᶠ (N : ℕ) in atTop, g N < 1 / 8⊢ False)) f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)hf':∀ᶠ (N : ℕ) in atTop, f N < 1 / 8hg':∀ᶠ (N : ℕ) in atTop, g N < 1 / 8⊢ False
obtain ⟨N, hN1, h1, h2, h3, h4⟩ :=
((eventually_ge_atTop 1).and (hlow.and (hup.and (hf'.and hg')))).exists f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)hf':∀ᶠ (N : ℕ) in atTop, f N < 1 / 8hg':∀ᶠ (N : ℕ) in atTop, g N < 1 / 8N:ℕhN1:1 ≤ Nh1:↑N ^ (1 / 2 - f N) < ↑(F N)h2:↑(F N) ≤ ↑N ^ (1 / 4 + g N)h3:f N < 1 / 8h4:g N < 1 / 8⊢ False
have hle : (N : ℝ) ^ ((1 : ℝ) / 4 + g N) ≤ (N : ℝ) ^ ((1 : ℝ) / 2 - f N) :=
Real.rpow_le_rpow_of_exponent_le (by f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)hf':∀ᶠ (N : ℕ) in atTop, f N < 1 / 8hg':∀ᶠ (N : ℕ) in atTop, g N < 1 / 8N:ℕhN1:1 ≤ Nh1:↑N ^ (1 / 2 - f N) < ↑(F N)h2:↑(F N) ≤ ↑N ^ (1 / 4 + g N)h3:f N < 1 / 8h4:g N < 1 / 8⊢ 1 ≤ ↑N f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)hf':∀ᶠ (N : ℕ) in atTop, f N < 1 / 8hg':∀ᶠ (N : ℕ) in atTop, g N < 1 / 8N:ℕhN1:1 ≤ Nh1:↑N ^ (1 / 2 - f N) < ↑(F N)h2:↑(F N) ≤ ↑N ^ (1 / 4 + g N)h3:f N < 1 / 8h4:g N < 1 / 8hle:↑N ^ (1 / 4 + g N) ≤ ↑N ^ (1 / 2 - f N)⊢ False exact_mod_cast hN1 All goals completed! 🐙 f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)hf':∀ᶠ (N : ℕ) in atTop, f N < 1 / 8hg':∀ᶠ (N : ℕ) in atTop, g N < 1 / 8N:ℕhN1:1 ≤ Nh1:↑N ^ (1 / 2 - f N) < ↑(F N)h2:↑(F N) ≤ ↑N ^ (1 / 4 + g N)h3:f N < 1 / 8h4:g N < 1 / 8hle:↑N ^ (1 / 4 + g N) ≤ ↑N ^ (1 / 2 - f N)⊢ False) (by f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)hf':∀ᶠ (N : ℕ) in atTop, f N < 1 / 8hg':∀ᶠ (N : ℕ) in atTop, g N < 1 / 8N:ℕhN1:1 ≤ Nh1:↑N ^ (1 / 2 - f N) < ↑(F N)h2:↑(F N) ≤ ↑N ^ (1 / 4 + g N)h3:f N < 1 / 8h4:g N < 1 / 8⊢ 1 / 4 + g N ≤ 1 / 2 - f N f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)hf':∀ᶠ (N : ℕ) in atTop, f N < 1 / 8hg':∀ᶠ (N : ℕ) in atTop, g N < 1 / 8N:ℕhN1:1 ≤ Nh1:↑N ^ (1 / 2 - f N) < ↑(F N)h2:↑(F N) ≤ ↑N ^ (1 / 4 + g N)h3:f N < 1 / 8h4:g N < 1 / 8hle:↑N ^ (1 / 4 + g N) ≤ ↑N ^ (1 / 2 - f N)⊢ False linarith All goals completed! 🐙 f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)hf':∀ᶠ (N : ℕ) in atTop, f N < 1 / 8hg':∀ᶠ (N : ℕ) in atTop, g N < 1 / 8N:ℕhN1:1 ≤ Nh1:↑N ^ (1 / 2 - f N) < ↑(F N)h2:↑(F N) ≤ ↑N ^ (1 / 4 + g N)h3:f N < 1 / 8h4:g N < 1 / 8hle:↑N ^ (1 / 4 + g N) ≤ ↑N ^ (1 / 2 - f N)⊢ False) f:ℕ → ℝhf:Tendsto f atTop (𝓝 0)hlow:∀ᶠ (N : ℕ) in atTop, ↑N ^ (1 / 2 - f N) < ↑(F N)g:ℕ → ℝhg:Tendsto g atTop (𝓝 0)hup:∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + g N)hf':∀ᶠ (N : ℕ) in atTop, f N < 1 / 8hg':∀ᶠ (N : ℕ) in atTop, g N < 1 / 8N:ℕhN1:1 ≤ Nh1:↑N ^ (1 / 2 - f N) < ↑(F N)h2:↑(F N) ≤ ↑N ^ (1 / 4 + g N)h3:f N < 1 / 8h4:g N < 1 / 8hle:↑N ^ (1 / 4 + g N) ≤ ↑N ^ (1 / 2 - f N)⊢ False
linarith All goals completed! 🐙end Erdos131