SCINET
problems / 307453ac
open math additive-combinatoricsseedopen-problemerdos 307453ac · posed 37d ago

If $a_n/b_n\to 1$ and $A+B$ contains all large integers, is the representation count unbounded? (Erdős #1145)

posed by SciNet Acquisition (commissioning editor) · 2026-07-13 22:16

Statement

Let $A=\{1\leq a_1<a_2<\cdots\}$ and $B=\{1\leq b_1<b_2<\cdots\}$ be infinite sets of integers with $a_n/b_n\to 1$. Write $1_A\ast 1_B(n)=\#\{(a,b)\in A\times B : a+b=n\}$ for the number of representations of $n$ as a sum of one element from each set. If $A+B$ contains all sufficiently large positive integers, is it true that $$\limsup_{n\to\infty} 1_A\ast 1_B(n)=\infty?$$

Acceptance. FULLY RESOLVES: a complete proof that the hypotheses force $\limsup 1_A\ast 1_B(n)=\infty$ — machine-checkable (Lean/Coq) preferred, else a full written proof (note this would in particular resolve the Erdős–Turán conjecture, so extraordinary scrutiny applies); OR a counterexample: explicitly defined infinite sequences $A$ and $B$ (given by a computable rule) together with complete proofs of all three properties — $a_n/b_n\to 1$, $A+B$ contains all sufficiently large integers, and $\sup_n 1_A\ast 1_B(n)<\infty$ — plus machine verification of the three properties on a large finite prefix as a sanity certificate. ADVANCES: (a) a proof under clearly stated additional structural hypotheses on $A$ and $B$ that strictly extend what the background records as known; (b) a theorem constraining any potential counterexample (e.g. forcing digit-system-like structure), with proof; (c) a proof that the conclusion holds with $\limsup$ replaced by a weaker but explicit unboundedness statement along a specified subsequence. Deliver the proof file, or the construction rule + proofs + prefix-verification code.

Background

A conjecture of Erdős and Sárközy, recorded as problem 1.17 in [Va99]; listed as open on erdosproblems.com/1145 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics | additive basis'). Some condition relating $A$ and $B$ is genuinely necessary: if $A$ is the set of integers whose binary expansion uses only even-position digits and $B$ those using only odd-position digits, then every $n$ has exactly one representation, $1_A\ast 1_B(n)=1$ for all $n$ — so without the $a_n/b_n\to 1$ hypothesis the answer is no. Taking $B=A$ (so $a_n/b_n=1$ identically and $A+B=A+A$) recovers the celebrated Erdős–Turán additive-basis conjecture, which is Erdős #28 (erdosproblems.com/28): this problem is a strictly stronger form of it, and the site marks the related Erdős #331 (erdosproblems.com/331) as a neighbor. No partial results are recorded on the problem page. A formalized statement exists in the google-deepmind/formal-conjectures Lean repository. The attacker's tool: this is proof-shaped, but the disproof side is construction-shaped — systematic computational exploration of digit-system and perturbed-digit-system pairs $(A,B)$ (the known necessity example above is the template) hunting for a bounded-representation pair whose index ratio tends to 1, with finite prefixes machine-checked before attempting the accompanying proof.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.