Problem 131

Let $F(N)$ be the maximal size of $A\subseteq\{1,\ldots,N\}$ such that no $a\in A$ divides the sum of any distinct elements of $A\backslash\{a\}$ . Estimate $F(N)$ . In particular, is it true that

F(N) > N^{1/2-o(1)}?

Source: erdosproblems.com/131

Number theory

Wiki page

Status

ClaimedAnswered

A full solution has been claimed but not yet accepted. Settled in another form, for example when its parts resolve differently or the question is open-ended.

Open on the site, for the estimate; the label OPEN attaches to it. The displayed question is answered no: every non-dividing set is non-averaging (if $a$ were the average of a nonempty $B\subseteq A\setminus\{a\}$ then $a$ would divide the sum of $B$ ), so Pham and Zakharov's Theorem 1, the largest non-averaging subset of $\{1,\ldots,N\}$ has $N^{1/4+o(1)}$ elements (Geom. Funct. Anal. 2025, refereed), gives $F(N)\le N^{1/4+o(1)}$ , and $F(N)>N^{1/2-o(1)}$ fails for large $N$ ; this is recorded as an accepted partial claim on the Pham--Zakharov claim page (2024). The estimate carries one pending full claim, $F(N)=N^{1/5+o(1)}$ , submitted to the site's proof-claim tab on 24 July 2026 and recorded on the Xeff claim page (2026), unexamined by the site and unreviewed; the frontmatter standing claimed derives from it and certifies nothing. In the literature the order of $F(N)$ is open between the constructions and that bound: Straus's $F(N)>\exp((1+o(1))\sqrt{2\log N/\log2})$ (1975, p. 309), the bound $F(N)\gg N^{1/5}$ , which the 1999 paper deduces (p. 128) from Straus's transfer theorem and Bosznay's non-averaging sets and which [Er97b] (pp. 230--231) credits to a Budapest student without printing a construction, and $F(N)\le N^{1/4+o(1)}$ ; the 1999 paper's explicit $F(N)<3N^{1/2}+1$ (Corollary 2, p. 128) is superseded. The two 1999 bounds are recorded as an accepted partial claim on the 1999 claim page (Erdos Lev Rauzy Sandor Sarkozy, 1999).

PhZa24: Pham, H. T. and Zakharov, D., Sharp bound for the Erdős--Straus non-averaging set problem. Geom. Funct. Anal. 35 (2025), no. 6, 1712--1738, DOI 10.1007/s00039-025-00728-8; arXiv:2410.14624v2 (10 September 2025; the journal text not compared); Theorem 1, p. 2. Library home: Pham and Zakharov 2024.
ELRSS99: Erdős, P., Lev, V., Rauzy, G., Sándor, C. and Sárközy, A., Greedy algorithm, arithmetic progressions, subset sums and divisibility. Discrete Math. 200 (1999), no. 1--3, 119--135, DOI 10.1016/S0012-365X(98)00385-9. Property Q (non-dividing sets) and $Q(n)$ , p. 127; Theorem 2, Corollary 1 and Corollary 2, $Q(n)<3\sqrt n+1$ , p. 128; the deduction $Q(n)\gg n^{1/5}$ from Straus and Bosznay, p. 128; the guess $Q(n)>n^{1/2-\varepsilon}$ , p. 129. Library home: Erdős 1999; result pages Corollary 2 and the bound of p. 128.
Bo89: Bosznay, Á. P., On the lower estimation of non-averaging sets. Acta Math. Hungar. 53 (1989), no. 1--2, 155--157, DOI 10.1007/BF02170066; the Theorem, $f(n)>c_6n^{1/4}$ for all large $n$ , printed p. 155, and its proof, pp. 155--156. [ELRSS99]'s reference [3], the $\alpha=\frac14$ of its p. 128 deduction. Library home: Bosznay 1989; result page Theorem.
Er75b: Erdős, P., Problems and results in combinatorial number theory. Journées Arithmétiques de Bordeaux (1974), Astérisque 24--25 (1975), 295--310; item (vi) on printed p. 309. Library home: Erdős 1975.
Er97b: Erdős, P., Some old and new problems in various branches of combinatorics. Discrete Math. 165/166 (1997), 227--231, DOI 10.1016/S0012-365X(96)00173-2; item 10, printed pp. 230--231 (PDF pp. 4--5 of the publisher's open-archive file at that DOI): the problem, the easy bound $f(n)<cn^{1/2}$ , the attribution of $f(n)>cn^{1/5}$ to a Budapest student and the question $f(n)>n^{1/2-\varepsilon}$ ; the site cites p. 230 for a construction by Csaba, and no construction is printed. Library home: Erdős 1997; result page Item 10.
Gu04: Guy, R. K., Unsolved Problems in Number Theory, 3rd ed., Problem Books in Mathematics, Springer, New York (2004), xviii+437 pp. Section C16 "Nonaveraging sets. Nondividing sets.", printed p. 198: "Erdős originally asked for the maximum number, $k(x)$ , of integers in $[0,x]$ so that no one divides the sum of any others. Such nondividing sets are obviously nonaveraging, so $k(x)\le f(x)$ . Straus showed that $k(x)\ge\max\{f(x/f(x)),f(\sqrt x)\}$ "; the library card's row for this problem cites the same passage. Library home: Guy 2004.
OEIS: Wasserman, D., Sequence A068063, The On-Line Encyclopedia of Integer Sequences (2002; entry last modified 30 October 2025, server time), with a table of $F(N)$ for $N\le100$ by C. Sievers.

Problem 131

Status

Proof claims

Discussion