Problem 12

Let $A$ be an infinite set such that there are no distinct $a,b,c\in A$ such that $a\mid (b+c)$ and $b,c>a$ . Is there such an $A$ with

\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}>0?

Does there exist some absolute constant $c>0$ such that there are always infinitely many $N$ with

\lvert A\cap\{1,\ldots,N\}\rvert<N^{1-c}?

Is it true that

\sum_{n\in A}\frac{1}{n}<\infty?

Source: erdosproblems.com/12

Number theory

Wiki page

Status

Open

No claim settles this problem.

Open; the site's label is OPEN. The problem's three parts derive its standing: the first two, the liminf and density questions, are answered by pending claims, and the third, the reciprocal sum, has no standing claim. There are sets with property P and $|A\cap\{1,\ldots,N\}|\ge N/(\log N)^{O(\log\log\log N)}$ for all large $N$ , which answers the first question yes and the second no. The construction is credited to DeepMind's automated prover, was simplified and sharpened in the thread (7--9 April 2026) and is recorded in the commentary rewritten by the site's curator, Thomas Bloom, on 8 April 2026, while the problem's label is OPEN; formal proofs of the first two parts sit in a fork of the formal-conjectures collection at pinned commits (not built by this corpus). It is recorded as a pending partial claim on the DeepMind claim page (2026): the commentary credits the result but the label settles neither question, and the named-author preprint of May 2026 (revised June 2026) that reports the formal proofs, [TKS26], is unrefereed. Nat Sothanaphan's note of 8 April 2026, linked in the thread on 7 April and produced with GPT-5.4 Thinking, gives its own construction answering the same two questions and is recorded as a pending partial claim on his claim page (Sothanaphan, 2026). Before 2026 the results in hand were the density-zero theorem of Erdős and Sárközy (1970), their $p^2$ example with counting function $\gg N^{1/2}/\log N$ , the Elsholtz--Planitzer construction with $\gg N^{1/2}/((\log N)^{1/2}(\log\log N)^2(\log\log\log N)^2)$ (2017), and, for pairwise coprime sets only, Schoen's $\ll N^{2/3}$ and Baier's $\ll N^{2/3}/\log N$ infinitely often, refereed results recorded as accepted partial claims on Schoen's claim page (2001) and Baier's claim page (2004), which answer the second question for that subclass only. For the third question nothing is proved either way: every known construction has convergent reciprocal sum, and a comment in the thread explains why congruence constructions cannot reach divergence; the one proof claim on it, of 30 July 2026, is recorded as a rejected partial claim on the Ndikums' claim page (2026) and does not change the standing.

ErSa70: Erdős, P. and Sárközi, A., On the divisibility properties of sequences of integers. Proc. London Math. Soc. (3) 21 (1970), no. 1, 97--101; the definition and conjecture (1), p. 97; the Theorem, the best-possible construction, the conjectures and the $p^2$ example, p. 98. Library home: Erdős and Sárközi 1970.
ElPl17: Elsholtz, C. and Planitzer, S., On Erdős and Sárközy's sequences with Property P. Monatsh. Math. 182 (2017), no. 3, 565--575, DOI 10.1007/s00605-016-0995-9; arXiv:1609.07935v1 (26 September 2016; the journal text has not been compared with it). Library home: Elsholtz and Planitzer 2017.
Ba04: Baier, S., A note on P-sets. Integers 4 (2004), #A13, 6 pp. Library home: Baier 2004.
Sc01: Schoen, T., On a problem of Erdős and Sárközy. J. Combin. Theory Ser. A 94 (2001), no. 1, 191--195, DOI 10.1006/jcta.2000.3142; the definitions, p. 191; the recalled conjecture, pp. 191--192; the $p^2$ example, p. 192; the Theorem, p. 193; the Remarks, p. 195 (PDF pp. 1--5 of the publisher's open-archive file). Library home: Schoen 2001.
Er73: Erdős, P., Problems and results on combinatorial number theory. A Survey of Combinatorial Theory (Fort Collins, 1971), North-Holland (1973), 117--138; the passage on printed pp. 132--133. 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; printed pp. 302--303. Library home: Erdős 1975.
Er77c: Erdős, P., Problems and results on combinatorial number theory III. Number Theory Day (New York, 1976), Lecture Notes in Math. 626 (1977), 43--72; printed pp. 52--53. Library home: Erdos 1977.
Er80: Erdős, P., A survey of problems in combinatorial number theory. Ann. Discrete Math. 6 (1980), 89--115; printed p. 113. Library home: Erdos 1980.
Er92c: Erdős, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. (1992), 34--50; Section 4, printed p. 42. Library home: Erdős 1992.
Er95c: Erdős, P., Some problems in number theory. Octogon Math. Mag. (1995), 3--5. Not held; no open route found.
Er97: Erdős, P., Problems in number theory. New Zealand J. Math. (1997), 155--160. Not held; no open route found.
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 9, printed p. 230 (PDF p. 4 of the publisher's open-archive file): the three questions restated (the origin, below). Library home: Erdős 1997; result page Item 9.
Er97e: Erdős, P., Some of my favourite unsolved problems. Math. Japon. (1997), 527--537. Not held; no open route found.
Er98: Erdős, P., Some of my new and almost new problems and results in combinatorial number theory. Number Theory (Eger, 1996), de Gruyter (1998), 169--180. Not held (paywalled).
TKS26: Tsoukalas, G., Kovsharov, A., Shirobokov, S. and eighteen further authors, Advancing mathematics research with AI-driven formal proof search. arXiv:2605.22763 (v1 21 May 2026; v2 8 June 2026); Table 1 of Section 3 (v2) lists parts (i) and (ii) of this problem among the nine Erdős problems its agent resolved, and Appendix B.4 gives informal proofs of the first two questions.
So26: Sothanaphan, N., A compact block construction for parts 1 and 2 of Erdős Problem 12. Note dated 8 April 2026, 6 pp., produced with GPT-5.4 Thinking as its disclosure states, linked in the site's thread on 7 April 2026: drive.google.com; Theorems 5.1 and 5.2 and Remark 1.2. Recorded on its claim page (Sothanaphan, 2026).

Problem 12

Status

Proof claims

Discussion