Problem 13

Let $A\subseteq \{1,\ldots,N\}$ be such that there are no $a,b,c\in A$ such that $a\mid(b+c)$ and $a<\min(b,c)$ . Is it true that $\lvert A\rvert\leq N/3+O(1)$ ?

Source: erdosproblems.com/13

Number theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED (LEAN). Bedert's Theorem 1 (2023) gives an absolute constant $C$ with $|A|\le N/3+C$ for every $N$ and every $A\subseteq\{1,\ldots,N\}$ with property P, and his Theorem 2 gives $|A|\le\lceil N/3\rceil$ for all sufficiently large $N$ , sharp for the set $\{\lfloor2N/3\rfloor+1,\ldots,N\}$ . The status-defining source is an arXiv preprint (v1, 17 January 2023); Thomas Bloom, the site's curator, accepted it as the resolution, naming Bedert's paper in the commentary as the proof that the answer is yes, the formal-conjectures collection marks the statement research solved, and an outside Lean proof of the $N/3+C$ statement, not built here, is linked from the claim page. The claim page Bedert 2023 records the acceptance with this preprint qualification. The site's (LEAN) suffix is a catalog label explained under Formalization and the Lean label below.

Be23: Bedert, B., On a problem of Erdős and Sárközy about sequences with no term dividing the sum of two larger terms. arXiv:2301.07065v1 (17 January 2023), 43 pp.; Definition 1, p. 1; Theorems 1 and 2, p. 2. No journal version found. Library home: Bedert 2023.
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; conjecture (1), p. 97, and the $[\tfrac13x]+1$ example with Szemerédi's remark, p. 98. Library home: Erdős and Sárközi 1970.
Er92c: Erdős, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. (1992), 34--50; Section 4, printed p. 42: the conjecture $k<[x/3]+1$ , printed without a prize, and the $r$ -fold version. Library home: Erdős 1992.
Er73: Erdős, P., Problems and results on combinatorial number theory (1973), 117--138; printed p. 133: "Probably $\max k=x/3+\mathrm o(1)$ " [sic], read as $O(1)$ since $\max k$ is an integer. Library home: Erdos 1973.
Er75b: Erdős, P., Problems and results in combinatorial number theory (1975), 295--310; printed p. 303: " $n\le[\tfrac X3]+1$ . The $n+1$ integers $2n,2n+1,\ldots,3n$ show that our conjecture, if true, is best possible", with Szemerédi's partial result. Library home: Erdős 1975.
Er77c: Erdős, P., Problems and results on combinatorial number theory III (1977), 43--72; printed p. 53: "Then $k\le[\tfrac x3]+1$ . Equality, say, if $x=3n$ and the $a$ 's are the integers $2n,2n+1,\ldots,3n$ ". 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: "The conjecture $k\le[\tfrac13x]+1$ is still open". Library home: Erdos 1980.
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): "Let $a_1<a_2<\cdots<a_k\le m$ be such that no $a_i$ divides the sum of two larger $a$ 's. Is it true that $\max k\le m/3+0(1)$ [sic]? The integers $2m/3<a_i\le m$ show that our conjecture is the best possible if it is true." No prize is printed. Library home: Erdős 1997; result page Item 9.
Er95c: , [Er97], [Er97e], [Er98]: Erdős's problem papers of 1995--1998 cited by the site; not held (see Problem 12 for the entries).

Problem 13

Status

Proof claims

Discussion