Maximum size of sets with no element dividing another-elements subset sum
Follow the latest progress by email.
How large can A⊂{1,…,N} be if no member divides any nonempty subset sum of the other members? A known construction gives the exponent 1/5, leaving a matching upper-bound problem.
Why it matters and what counts as progress
Why it matters: A matching exponent determines the extremal size of sets avoiding a divisibility relation with all other-member subset sums.
What counts as progress: Prove the maximum is N^(1/5+o(1)), sharpen the lower-order factors or determine an exact extremal family.
How the problem developed
- 6 Apr 1999 · Problem and bound [1]
Paul Erdős, Vsevolod Lev, Gérard Rauzy, Csaba Sándor and András Sárközy Studied the greedy construction and subset-sum divisibility problem, recording an upper bound of order N¹ᐟ² for the maximum size.
- 18 Oct 2024 · Related bound [2]
Pham and Zakharov Proved the sharp N¹ᐟ⁴⁺ᵒ⁽¹⁾ bound for non-averaging sets, which also gives an upper bound for the narrower non-dividing family.
- 24 Jul 2026 · Claimed proof [3]
Theofil Xeff, with GPT-5.6 Sol credited for the central idea Posted a claimed N¹ᐟ⁵⁺ᵒ⁽¹⁾ asymptotic for Erdős Problem 131 with a Lean development.
AI contribution
A Projective Approach to Non-Dividing Sets
For subsets of {1,…,N} in which no element divides a nonempty subset sum of the others, Xeff proves the maximum size is N^(1/5+o(1)). The new upper bound matches the known lower exponent.
Sources
- Paul Erdős, Vsevolod Lev, Gérard Rauzy, Csaba Sándor and András Sárközy, Greedy algorithm, arithmetic progressions, subset sums and divisibility
- Pham and Zakharov, Non-averaging sets and their extremal size
- Erdős Problems, Problem 131 proof claim by Theofil Xeff
- Xeff, Erdős Problem 131
- Erdős 131 Lean formalization
Website timeline
Publication dates and editorial changes.