Estimate the maximum size of a non-dividing subset of {1,...,N} (Erdős #131)
Statement
For $N\ge 1$, let $F(N)$ be the maximum size of a set $A\subseteq\{1,\ldots,N\}$ that is 'non-dividing': no element $a\in A$ divides the sum of any (nonempty) subset of distinct elements of $A\setminus\{a\}$. Estimate the order of growth of $F(N)$. (Erdős's original question was whether $$F(N) > N^{1/2-o(1)}.$$)
Acceptance. FULLY RESOLVES: determine the order of growth of $F(N)$ — establish matching bounds pinning the exponent $\theta=\lim \log F(N)/\log N$ (or prove no clean exponent exists) — with a complete proof; a machine-checkable (Lean/Coq) proof is preferred, else a full written proof. ADVANCES (each independently checkable): (i) improve the lower bound by exhibiting, for infinitely many $N$, an explicit non-dividing set $A\subseteq\{1,\ldots,N\}$ with $|A|$ asymptotically larger than the best construction stated in the background (currently $\gg N^{1/5}$), delivering the construction and a certificate that it is non-dividing (checkable via a subset-sum-mod-$a$ dynamic program for each $a$); (ii) improve the upper bound strictly below the best bound stated in the background ($N^{1/4+o(1)}$), with proof; (iii) extend OEIS A068063 with exact values of $F(N)$ for new $N$, delivering the search program and an exhaustiveness certificate. Deliver the proof file, or the explicit construction plus non-dividing certificate, or the search code plus verified new values.
Background
Posed by Erdős [Er75b, p.309] and repeated in [Er97b, p.230]; also problem C16 in Guy's 'Unsolved Problems in Number Theory' [Gu04]. Listed as open on erdosproblems.com/131 (fetched 2026-07-13, status 'open', tagged 'number theory'). The term 'non-dividing' is due to Erdős, Lev, Rauzy, Sándor and Sárközy [ELRSS99], who proved the upper bound $F(N) < 3N^{1/2}+1$. For lower bounds, Erdős first believed $F(N) < (\log N)^{O(1)}$, but Straus proved $F(N) > \exp\big((\sqrt{2/\log 2}+o(1))\sqrt{\log N}\big)$; Erdős later credited Csaba (and [ELRSS99]) with a construction giving $F(N) \gg N^{1/5}$. The decisive link is that every non-dividing set is non-averaging (no element is an average of distinct others), so the non-averaging bound of Pham and Zakharov [PhZa24] yields $F(N) \le N^{1/4+o(1)}$. This already answers Erdős's original question in the NEGATIVE — $F(N) > N^{1/2-o(1)}$ is false — but the true growth rate is unknown, trapped between $N^{1/5}$ and $N^{1/4+o(1)}$. Compare Erdős #13 (erdosproblems.com/13) and the non-averaging problem Erdős #186 (erdosproblems.com/186). No Erdős prize is recorded. Attacker's tool: exhaustive and heuristic search over $\{1,\ldots,N\}$ (extending OEIS A068063) to compute $F(N)$ exactly for small $N$, and, more importantly, to design explicit non-dividing (equivalently non-averaging) constructions pushing the lower exponent above $1/5$; note that a candidate finite set can be certified non-dividing in polynomial time via a subset-sum-mod-$a$ dynamic program for each $a\in A$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #131 (T. F. Bloom) | website |
| REF-02 | OEIS A068063 — maximum size of a non-dividing subset of {1,...,n} | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.