Erdős Problem #131
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Let \(A\) be a subset of the first \(N\) positive integers. Say \(A\) is non-dividing if no element \(a\in A\) divides the sum of any nonempty set of distinct elements of \(A\setminus\{a\}\). Define \(F(N)\) to be the maximum size of such a set.
Erdős asked for the correct growth rate, and specifically whether
This is a lower-growth question about the largest valid set, not the existence of any particular small construction. The “nonempty” condition prevents the empty subset sum zero from making the definition vacuous, because every positive integer divides zero.
A small example
The set \(A=\{2,3\}\) is non-dividing: \(2\) does not divide \(3\), and \(3\) does not divide \(2\). By contrast, \(\{2,3,5\}\) fails because \(5\) divides the sum \(2+3=5\). One must check sums of subsets, not merely divisibility of pairs of chosen elements.
A non-dividing set is non-averaging: if an element \(a\) equalled the average of \(t\) other distinct chosen elements, their sum would be \(ta\) and hence divisible by \(a\), contradicting the hypothesis. The converse need not hold because divisibility can occur with quotient different from the subset size.
What is known
The proposed square-root lower growth is DISPROVED; the true order of \(F(N)\) remains OPEN. Erdős, Lev, Rauzy, Sándor and Sárközy showed
and gave lower constructions of order at least \(N^{1/5}\), discussed in their 1999 work. The stronger 2024 theorem of Huy Tuan Pham and Dmitrii Zakharov, Sharp bound for the Erdős–Straus non-averaging set problem, proves that every non-averaging subset of \(\{1,\ldots,N\}\) has size at most \(N^{1/4+o(1)}\). Since every non-dividing set is non-averaging, we obtain
This rules out \(F(N)>N^{1/2-o(1)}\) for large \(N\). However, an upper bound \(N^{1/4+o(1)}\) does not prove matching lower constructions for the more restrictive non-dividing property.
The maintained Erdős #131, edited September 2025, explicitly distinguishes these conclusions. It retains the umbrella “estimate \(F(N)\)” problem as OPEN, while identifying the proposed square-root subquestion as answered negatively.
GCL's current state
The pinned and maintained catalogue status for the umbrella problem is OPEN; the original source issue is #1400. The 2024 primary preprint's exponent is checked at abstract level, but the complete structural proof has not been reproduced.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded task is to enumerate subsets of \(\{1,\ldots,12\}\) and compare two exact predicates: non-dividing and non-averaging. Acceptance: \(\{2,3\}\) passes, \(\{2,3,5\}\) fails, and every set satisfying non-dividing also satisfies non-averaging. Provide at least one explicit set illustrating that the reverse logical implication is not being assumed. Stop at finite semantics, not an asymptotic theorem.
Sources and claim boundaries
- Pham and Zakharov, arXiv:2410.14624, primary 2024 upper bound for non-averaging sets.
- Maintained Erdős #131, original Erdős–Lev–Rauzy–Sándor–Sárközy results and status.
- Original GCL issue #1400.
No new exponent, complete structural-proof certification, or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1400 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.