Problem 539

Let $h(n)$ be such that, for any set $A\subseteq \mathbb{N}$ of size $n$ , the set

\left\{ \frac{a}{(a,b)}: a,b\in A\right\}

has size at least $h(n)$ . Estimate $h(n)$ .

Source: erdosproblems.com/539

Additive combinatorics
Number theory

Wiki page

Status

Open

No claim settles this problem.

The site's label is OPEN. The refereed bounds are $n^{1/2}\ll h(n)\ll n^{2/3}$ : the lower bound is Erdős and Szemerédi's, by the pairing argument Granville and Roesler give on p. 2 of their paper, and the upper bound comes from the Freiman–Lev sets in two dimensions, which Granville and Roesler present (pp. 2--3) and record as their Theorem 2; the accepted partial claim Granville and Roesler 1999 records both, on the refereed publication alone. Erdős's 1973 announcement of the bounds (5.2) with Szemerédi has no claim page: it gives no proof and no reference, and its content is carried by the Granville–Roesler page, which credits it. Two further partial claims have pages. The exponent: Theorem A.1 of the arXiv preprint of July 2026 by Schmitt, Gehrunger, Dekoninck, Bérczi, Kreitner, Price and Holmes describing their system ProofCouncil, to which they attribute it, gives $h(n)\le e^{O(\sqrt{\log n})}n^{1/2}$ , hence $h(n)=n^{1/2+o(1)}$ ; the site's curator, Thomas Bloom, adopted the bound into the commentary on 15 June 2026 after sketching the construction himself, while the label stayed OPEN, and its claim page (Schmitt Gehrunger Dekoninck Berczi Kreitner Price Holmes, 2026) records it as a pending partial claim (not refereed; the adoption of a bound into the commentary of a problem the site labels OPEN is not an acceptance, and nothing is reviewed by this project). The lower bound: a Lean development of September 2026 states that $h(n)/\sqrt n\to\infty$ , read as neither built nor audited by this corpus, on Kitamura's claim page (2026) (claimed). The authors of the exponent result write that the exact order of $h(n)$ remains open within a subexponential factor, and this page reads the label OPEN the same way: the question asks for an estimate, and the order is not determined. No full claim exists, and the standing derives from the claim pages.

GrRo99: Granville, A. and Roesler, F., The set of differences of a given set. Amer. Math. Monthly 106 (1999), no. 4, 338--344, DOI 10.1080/00029890.1999.12005050. The Unsolved problem, its restatement and the lower bound $m^{1/2}$ , p. 2; Theorem 1, p. 2; the Freiman–Lev sets and Theorem 2, pp. 2--3; the page numbers are those of the authors' eight-page preprint, public at https://dms.umontreal.ca/~andrew/PDF/Roesler.pdf, whose labels the journal version may not share. Library home: Granville and Roesler 1999; result pages Granville and Roesler 1999, Unsolved problem (p. 2), Granville and Roesler 1999, Theorem 1, Granville and Roesler 1999, Theorem 2.
Er73: Erdős, P., Problems and results on combinatorial number theory. A Survey of Combinatorial Theory (Fort Collins 1971), North-Holland (1973), Chapter 12, 117--138; Section 5, printed pp. 124--125; the chapter is online at https://www.renyi.hu/~p_erdos/1973-21.pdf. Library home: Erdos 1973; result page Erdos 1973, Section 5, h(n).
SGD+26: Schmitt, J., Gehrunger, T., Dekoninck, J., Bérczi, G., Kreitner, U., Price, L. and Holmes, D., ProofCouncil: An LLM Agent for Solving Open Mathematical Problems. arXiv:2607.09474v1 (10 July 2026, 25 pages; the paper describes the authors' system ProofCouncil, which the site's commentary names). Appendix A, "Case Study: Erdős Problem 539", pp. 10--15: Theorem A.1, p. 11; the proof, pp. 11--14; the scope of its Lean development, p. 15. Not carded in the library.
HLP08: Holzman, R., Lev, V. F. and Pinchasi, R., Projecting difference sets on the positive orthant. Combin. Probab. Comput. 17 (2008), no. 5, 681--688. Not held; its fixed-dimension lower bounds are quoted from the thread and from [SGD+26]. - Freiman and Lev: the two-dimensional construction credited to them by [GrRo99] (pp. 2--3), which gives no reference for it; nothing of theirs is held. - The external Lean developments named by the formal-conjectures file: KitaKen1/erdos-539-formal-conjectures (commit of 11 August 2026) and KitaKen1/erdos-539-sqrt-disproof (commit of 5 September 2026), pinned on the claim pages; not library sources.

Problem 539

Status

Proof claims

Discussion