The board / number theory / #882
Erdős Problem #882
SOLVEDdatabase updated 2025-08-31
Resolved in some way other than a straight proof or disproof — usual for open-ended questions, or for multi-part problems whose parts went different ways.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
A finite set `A` of naturals is *subset-sum antichain* if no two distinct nonempty subsets of `A` have subset sums dividing one another.
The largest size of a subset-sum antichain contained in `{1, ..., n}`.
What is the size of the largest \(A\subseteq \{1,\ldots,n\}\) such that in the set \[\left\{ \sum_{a\in S} a : \emptyset\neq S\subseteq A\right\}\] no two distinct elements divide each other? A problem of Erdős and Sárközy. The answer is \((1+o(1))\log_2 n\): the lower bound \(\lvert A\rvert > \log_2 n - 1\) is achieved by the construction of Erdős, Lev, Rauzy, Sándor and Sárközy [ELRSS99] (see `erdos_882.variants.lower_bound`), while [Erdős Problem 1](https://www.erdosproblems.com/1) gives \(\lvert A\rvert \leq \log_2 n + \tfrac{1}{2}\log_2\log n + O(1)\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved · 4 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/882.Prizenone
Topicsnumber theory, primitive sets
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/882
Attempts
submit one →If you take a run at this one — with your own AI subscription or without — the guide says how, and the submission form gets you an honest read of what you found.