Problem 186

Let $F(N)$ be the maximal size of $A\subseteq \{1,\ldots,N\}$ which is 'non-averaging', so that no $n\in A$ is the arithmetic mean of at least two elements in $A$ . What is the order of growth of $F(N)$ ?

Source: erdosproblems.com/186

Additive combinatorics

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

Solved: $F(N)=N^{1/4+o(1)}$ . The upper bound $F(N)\le N^{1/4+o(1)}$ is Theorem 1 of Pham and Zakharov (Geom. Funct. Anal. 35 (2025), 1712--1738, refereed); the matching lower bound $F(N)\gg N^{1/4}$ is Bosznay's Theorem (Acta Math. Hungar. 53 (1989), 155--157, refereed), proved by the construction $iq^3+i(i+1)/2$ , $1\le i\le q-1$ , which the introductions of [PhZa24] and [CFP23] also reproduce. The order of growth is thereby determined up to the $o(1)$ in the exponent, which is what the site's SOLVED label, its label for a resolution that is neither a proof nor a disproof, records; the exact order beyond the exponent is not known. The claim pages are Pham and Zakharov (the full determination, accepted on the refereed publication and the site's adoption) and Bosznay (the lower bound, partial, accepted on the refereed publication and the credit the site and the later papers give it); neither rests on a review by this project.

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 (published online 3 December 2025, per its Crossref record); arXiv:2410.14624 (v1 18 October 2024; v2 10 September 2025, 20 pp.). Theorem 1, p. 2 of arXiv v2. Library home: Pham and Zakharov 2024; result page Theorem 1.
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, printed p. 155, and its proof, pp. 155--156. Library home: Bosznay 1989; result page Theorem. The same construction is recalled in [PhZa24], p. 1, and [CFP23], p. 4.
CFP23: Conlon, D., Fox, J. and Pham, H. T., Homogeneous structures in subset sums and non-averaging sets. arXiv:2311.01416v1 (2 November 2023), 34 pp.; the search found no later version and no journal record. Theorem 1.6, p. 5. Library home: Conlon, Fox and Pham 2023; result page Theorem 1.6.
ErSa90: Erdős, P. and Sárközy, A., On a problem of Straus. Disorder in physical systems, Oxford Univ. Press (1990), 55--66. Not held; its bound is quoted from [PhZa24], p. 2, and [CFP23], p. 4.
Er73: Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Fort Collins, 1971), North-Holland (1973), 117--138; Section 1, printed p. 118. Library home: Erdos 1973.
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), printed p. 309. Library home: Erdős 1975.
Er77c: Erdős, P., Problems and results on combinatorial number theory. III. Number theory day (Rockefeller Univ., 1976), Lecture Notes in Math. 626, Springer (1977), 43--72; printed p. 45. Library home: Erdos 1977.
ErGr79: Erdős, P. and Graham, R. L., Old and new problems and results in combinatorial number theory: van der Waerden's theorem and related topics. Enseign. Math. (2) 25 (1979), 325--344; printed p. 334. Library home: Erdős and Graham 1979.
Er80: Erdős, P., A survey of problems in combinatorial number theory. Ann. Discrete Math. 6 (1980), 89--115; printed p. 110. Library home: Erdos 1980.
ErGr80: Erdős, P. and Graham, R. L., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28, Université de Genève (1980); printed p. 18. Library home: Erdős and Graham 1980.
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: a nonaveraging set $0\le a_1<\cdots<a_n\le x$ "was defined by Erdős & Straus by the property that no $a_i$ shall be the arithmetic mean of any subset of $A$ with more than one element", $f(x)$ its maximum size, the bounds $\frac14\log x+O(1)<\log f(x)<\frac12(\log x+\log\ln x)+O(1)$ with logarithms to base 2, attributed to "Erdős & Straus and others cited below" without proof, the conjecture " $f(x)=\exp(c\sqrt{\ln x})=o(x^\epsilon)$ ", the nondividing sets of Problem 131 with $k(x)\le f(x)$ , and Abbott's $l(n)>n^{1/13-\epsilon}$ for the largest nonaveraging subset that every set of $n$ integers contains; Bosznay's note is in its reference list, and its bound recorded above contradicts the printed conjecture. Library home: Guy 2004.
Str67: , [ErSt70] Straus, E. G., Non-averaging sets, Proc. Sympos. Pure Math. (Amer. Math. Soc., 1967), and Erdős, P. and Straus, E. G., Non-averaging sets II, Combinatorial theory and its applications (Balatonfüred, 1969), Colloq. Math. Soc. János Bolyai 4, North-Holland (1970), 405--411: the origin papers as Erdős's surveys cite them; not held, and not among the site's keys.
OEIS: A389784, the maximum size of a non-averaging subset of $\{1,\ldots,n\}$ (: terms to $n=74$ , added October 2025, with the comment that up to $n=74$ some maximum set contains $n$ ).

Problem 186

Status

Proof claims

Discussion