---

Claim. The answer to Problem 785 is yes. The claimed result is Theorem 0.2 of Y.-G. Chen and J.-H. Fang, On a conjecture of Sárközy and Szemerédi: if $A,B\subseteq\mathbb N$ are infinite, $A+B$ contains every large integer and $\limsup_{x\to\infty}A(x)B(x)/x\le1$, then for every fixed $M>1$

$$A(x)B(x)-x\ge\bigl(\min\{A(x),B(x)\}\bigr)^M$$

for all sufficiently large $x$. The problem's hypothesis $A(x)B(x)\sim x$ gives $\limsup=1$, and $\min\{A(x),B(x)\}\to\infty$ for infinite sets, so $A(x)B(x)-x\to\infty$, the problem's statement, which Sárközy and Szemerédi had proved (their claim page). The theorem disproves the conjecture of Sárközy and Szemerédi that such complements exist with $A(x)B(x)-x=O(\min\{A(x),B(x)\})$, and, for the sparser set $A$ (the one with $A(2x)/A(x)\to1$, whose count is $\min\{A(x),B(x)\}$ for large $x$), it rules out $A(x)B(x)-x\ll A(x)^c$ for every constant $c>0$, the form the site's commentary records. The proof uses Narkiewicz's lemma that one of the two sets satisfies $A(2x)/A(x)\to1$ and an elementary double-counting inequality (Lemma 1.2) comparing representation counts of sums with those of differences. Ruzsa's later bound (Ruzsa's claim page) improves this theorem; Ruzsa writes that the proof is based on Chen and Fang's argument, with some parts improved. Library home chen_2015_conjecture_sarkozy_szemeredi (held; the statement follows the card's digest and the publisher's abstract; no proof check is recorded).

Depends on. Nothing in this wiki.

Acceptance. Refereed: Acta Arith. 169 (2015), no. 1, 47--58, doi:10.4064/aa169-1-3; the Crossref record gives only the year, so the page carries the first day of it. Reviewed: the site's curator, Thomas Bloom, labels the problem PROVED (LEAN) and credits this bound, as [ChFa15], in the problem page's commentary; the curator had no part in the result. The formal-conjectures statement file for the problem states the result as the variant erdos_785.variants.chen_fang without proof. No review by this project is recorded.