Skip to content

Erdős problem 13

If A⊆{1,...,N}A \subseteq \{1, ..., N\} is a set with no a,b,c∈Aa, b, c \in A such that a∣(b+c)a | (b+c) and a<min⁡(b,c)a < \min(b,c), then ∣A∣≤N/3+O(1)|A| \le N/3 + O(1). This has been solved by Bedert [Be23].

Sources

The source's own material, retained exactly.

2 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

13.lean

Retained formal statement2 of 2

A general version asks, for a fixed r∈Nr \in \mathbb{N}, if a set A⊆{1,...,N}A \subseteq \{1, ..., N\} has no a∈Aa \in A and b1,...,br∈Ab_1, ..., b_r \in A such that a∣(b1+...+br)a | (b_1 + ... + b_r) and a<min⁡(b1,...,br)a < \min(b_1, ..., b_r), then is it true that ∣A∣≤N/(r+1)+O(1)|A| \le N/(r+1) + O(1)?

FormalConjectures/ErdosProblems/13.leanErdos13.erdos_13.variants.general7 linesExact file
True ↔  ∀ (r : ℕ),    ∃ C,      ∀ (N : ℕ),        ∀ A ⊆ Finset.Icc 1 N,          (∀ a ∈ A, ∀ (b : Fin r → ℕ), (∀ (i : Fin r), b i ∈ A) → (∀ (i : Fin r), a < b i) → ¬a ∣ ∑ i, b i) →            ↑A.card ≤ ↑N / (↑r + 1) + C
OpenStatement only, no proof