/- 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 FormalConjecturesUtil

Erdős Problem 131

References:

    erdosproblems.com/131

    [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 Erdos131

A 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 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 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) (N:ℕA:Finset ℕhA:A ⊆ Finset.Icc 1 Nhnd:NonDividing A⊢ A ∈ Finset.filter NonDividing (Finset.Icc 1 N).powerset All goals completed! 🐙)

Trivial upper bound: $F(N) \le N$.

@[category API, AMS 11] theorem F_le (N : ℕ) : F N ≤ N := N:ℕ⊢ F N ≤ N N:ℕA:Finset ℕhA:A ⊆ Finset.Icc 1 Nh:A.card = F N⊢ F N ≤ N 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)) hnd

Trivial lower bound: for $N \ge 1$, the singleton ${N}$ is non-dividing, so $1 \le F(N)$.

N:ℕhN:1 ≤ Nh:{N}.card ≤ F N⊢ 1 ≤ F N 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) := ⊢ ∃ f, Tendsto f atTop (𝓝 0) ∧ ∀ᶠ (N : ℕ) in atTop, ↑(F N) ≤ ↑N ^ (1 / 4 + f N) 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 := N:ℕ⊢ ↑(F N) < 3 * √↑N + 1 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).

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 All goals completed! 🐙end Erdos131