Erdős #1145 — two-set a_n/b_n→1 additive-basis generalization is OPEN; its own necessity clause is settled by Erdős #331 (Ruzsa's digit-parity construction, DISPROVED)

Statement

Erdős #1145 (Erdős–Sárközy). Let $A=\{1\le a_1<a_2<\cdots\}$ and $B=\{1\le b_1<b_2<\cdots\}$ be sets of positive integers with $a_n/b_n\to1$. If $A+B$ contains all sufficiently large positive integers, is it true that $$\limsup_{n\to\infty} (1_A * 1_B)(n) = \infty,$$ i.e. that the number of ways to write $n=a+b$ ($a\in A,b\in B$) is unbounded along some subsequence? [erdosproblems.com/1145, LaTeX source, fetched 2026-07-02]

This is stated on the site as **a stronger form of Erdős #28 — additive basis forces unbounded representations** (the classical case $B=A$: if $A+A\supseteq[N_0,\infty)$ then must $\limsup 1_A*1_A(n)=\infty$ — the Erdős–Turán 1941 additive-basis conjecture, itself still fully open with a \$500 prize), and is explicitly cross-linked to **erdos/331** (Ruzsa's related difference-equation question).

The #1145 page itself immediately notes the hypothesis $a_n/b_n\to1$ is *load-bearing*, not decorative: "Some condition relating $A$ and $B$ is necessary since, for example, if $A$ is the set of all integers with only even binary digits and $B$ is the set of all integers with only odd binary digits then $1_A*1_B(n)=1$ for all $n$." That sentence is the seed of this page: it is exactly the Ruzsa binary-digit-parity construction that is the star of the *genuinely solved* neighboring problem #331.

Facts

- Status of #1145 itself: OPEN. Ground-truth data/problems.yaml in github.com/teorth/erdosproblems (fetched 2026-07-02) records state: "open", no prize, tags additive combinatorics, additive basis, last updated 2026-01-23; a Lean formal *statement* (not proof) exists per the rendered page. So #1145 is not a solved problem — it is a live conjecture of Erdős and Sárközy that generalizes an already-70-year-open question. - #28 (Erdős–Turán, 1941), the special case $A=B$: also OPEN, \$500 prize. problems.yaml: state: "open". Erdős and Turán additionally conjectured the stronger $\limsup 1_A*1_A(n)/\log n>0$, and a further strengthening replacing "$A+A$ cofinite" by the weaker hypothesis $|A\cap[1,N]|\gg N^{1/2}$. Discussed as problem C9 in Guy, *Unsolved Problems in Number Theory* (2004). [erdosproblems.com/latex/28] - #40: also OPEN, \$500 prize, same "additive basis" cluster (problems.yaml, last update 2025-08-31) — a sibling strengthening in the same family, not otherwise detailed here. - #331 (Ruzsa), the closely related difference-equation question: DISPROVED, Lean-verified. problems.yaml: state: "disproved (Lean)", last update 2026-01-31. Statement: for $A,B\subseteq\mathbb N$ with $|A\cap\{1,\dots,N\}\gg N^{1/2}$ and $|B\cap\{1,\dots,N\}|\gg N^{1/2}$ for all large $N$, are there infinitely many solutions to $a_1-a_2=b_1-b_2\ne0$ ($a_1,a_2\in A$, $b_1,b_2\in B$)? Answer: no, by an explicit counterexample of Imre Ruzsa. [erdosproblems.com/latex/331] - The counterexample is one single construction that does double duty on both pages — it disproves #331's naive hypothesis *and* is cited on #1145 as the reason $a_n/b_n\to1$ can't simply be dropped from that conjecture. This is the "SOLVED problem (with its solution) that #1145 depends on" documented below: not a deep theorem, but a load-bearing *impossibility/necessity certificate* — the thing that tells you the hypotheses of #1145, #28, #40 are not free to weaken, and it is a genuinely reusable construction technique, not just a one-off trick. - A separate, older, and deeper solved ancestor in the same technical family (representation-function regularity of additive bases): the Erdős–Fuchs theorem (1956), resolving a companion 1941 Erdős–Turán conjecture: no infinite $A\subseteq\mathbb N$ can have partial sums of its representation function satisfy $\sum_{n\le N}(1_A*1_A)(n) = cN + o(N^{1/4}\log^{-1/2}N)$ for any constant $c>0$ — i.e. the *average* representation count of an additive basis can never be too smooth/linear. Erdős & Fuchs, *J. London Math. Soc.* 31 (1956), 67–73. [en.wikipedia.org/wiki/Erdős–Fuchs_theorem; planetmath.org/erdhosfuchstheorem] This is a different precise statement from #28/#1145 (average-smoothness vs. limsup-unboundedness) but the same theme — "representation functions of additive bases cannot behave too nicely" — and its analytic technique (generating function + Parseval/$L^2$ estimate on the unit circle) has since been extended to two-set/ordered representation functions, i.e. exactly #1145's $A,B$ setting: Y. Zhang & collaborators/others, "An Erdős–Fuchs Theorem for Ordered Representation Functions," *Ramanujan J.* (2020), arXiv:1911.12313 — proving an analogous smoothness-impossibility bound for $\sum_{n\le N}$ of the *ordered* two-set representation count. Sharpenings of the classical one-set theorem: Montgomery–Vaughan (the $\Omega(M^{1/4}\log^{-1/4}M)$ oscillation bound), Jurkat (via Hayashi, removing the log factor to $\Omega(N^{1/4})$), a near-matching upper bound of Ruzsa, and a simplified proof by D. J. Newman (1979). - No known unconditional progress on #1145's actual $\limsup=\infty$ question was found in this pass — the site's own comment thread (per the r.jina.ai rendered summary) records only that it "appears difficult" and has no solvers/collaborators listed as of the last site update (11 April 2026 per the rendered page footer).

Solution

What is actually solved here: Erdős #331, in the negative, via Ruzsa's binary-digit-parity ("even bits" / "odd bits") construction — and this is exactly the mechanism #1145 leans on to justify its own hypotheses.

The construction. Write every nonnegative integer $n$ in binary, $n=\sum_i \epsilon_i(n)2^i$ with $\epsilon_i(n)\in\{0,1\}$. Define $$A=\{n : \epsilon_i(n)=0 \text{ for all odd } i\}\ \ (\text{bits only at even positions}),\qquad B=\{n : \epsilon_i(n)=0 \text{ for all even } i\}\ \ (\text{bits only at odd positions}).$$ Because a bit of $A$-type support and a bit of $B$-type support never occupy the same binary position, ordinary integer addition of $a\in A$ and $b\in B$ is literally a bitwise OR with no carries — so the map $(a,b)\mapsto a+b$ is a bijection from $A\times B$ onto $\mathbb N$: *every* $n$ has a unique representation $n=a+b$, $a\in A,b\in B$. Hence $$1_A*1_B(n)=1\ \text{ for every } n\ge 0,$$ exactly the identity quoted (independently) on both #1145's and #331's LaTeX pages.

Why this disproves #331. $A$ and $B$ each have $\asymp\sqrt N$ elements below $N$ (roughly half of the $\log_2 N$ available bit-positions are "free" for each set, giving $2^{(\log_2 N)/2}\asymp\sqrt N$ choices), matching #331's hypothesis $|A\cap[1,N]|,|B\cap[1,N]|\gg N^{1/2}$. But the *additive energy* between $A$ and $B$ — the count of solutions to $a_1+b_1=a_2+b_2$ — is minimal: since every $n$ has exactly one $(a,b)$ preimage, the only solutions are the trivial ones $a_1=a_2,b_1=b_2$. Rewriting $a_1+b_1=a_2+b_2$ as $a_1-a_2=b_2-b_1$, this says there are no nontrivial solutions at all to $a_1-a_2=b_1-b_2\ne0$ — the opposite of what #331 conjectures ("infinitely many" such solutions). One clean unique-representation construction kills the conjecture outright; formalized and machine-checked in Lean per erdosproblems.com's "DISPROVED (LEAN)" tag.

Why this is the necessity certificate for #1145 (the transferable idea). The *same* $A,B$ pair is reused, unmodified, as a warning label on #1145: $A+B=\mathbb N\supseteq[\text{sufficiently large}]$ trivially (every $n\ge0$ is hit), yet $1_A*1_B(n)\equiv1$ is as bounded as a representation function can possibly be — $\limsup=1$, not $\infty$. So the naive statement of #1145 *without* the constraint $a_n/b_n\to1$ is false, by this exact construction. $A$ and $B$ here have wildly different growth rates in the fine-grained sense that matters ($a_n/b_n$ oscillates — $A$'s $n$-th element and $B$'s $n$-th element trade off which "half" of the bit-budget they get in a way that does not converge to a fixed ratio, since which positions are even/odd relative to a given magnitude range shifts $A$ and $B$ apart combinatorially even though both grow like $\Theta(\sqrt N)$ in bulk density). This is precisely why Erdős and Sárközy imposed the sharper *pointwise* condition $a_n/b_n\to1$ (rather than merely matching bulk growth rates $\asymp N^{1/2}$) — it is designed to rule out exactly this class of "digit-interleaving" perfect-partition counterexamples.

The reusable technique, stated abstractly — call it digit-position-parity splitting: to build two (or more) sets with *prescribed, matching bulk density* but a *perfect (multiplicity-1) additive partition* of $\mathbb N$ (or of a residue class / interval), partition the base-$k$ (here $k=2$) digit *positions* of $n$ among the sets, and let each set consist of the integers whose support is confined to its assigned positions. Addition across sets is then carry-free and injective by construction, so the convolution $1_A*1_B*\cdots$ is forced to be *identically* the minimum possible value on the union of the sumsets. This is the standard "how to build a perfect / unique-representation additive basis" move (the same idea underlies classical unique-representation-basis constructions in additive number theory, e.g. Erdős–Sárközy–Sós-style constructions cited in the "unique representation bases" literature) and is the first thing to reach for when testing whether a proposed hypothesis in the #28/#40/#1145 family is actually strong enough to rule out a bounded-representation counterexample — i.e. exactly the role it already plays as the stated justification inside #1145's own problem text. Any attack on #1145 (or on weakenings of #28) should first check it survives this construction and its natural variants (base $k>2$ splits, unequal digit-position allocations, etc.) before attempting a real proof.

On the deeper, genuinely analytic ancestor (Erdős–Fuchs, 1956), for completeness. Where the digit-parity trick above is a combinatorial *construction* (useful for disproving over-strong hypotheses), the Erdős–Fuchs theorem is a genuinely hard *impossibility proof* about representation-function smoothness, proved via: form the generating function $f(x)=\sum_{a\in A}x^a$ on $|x|<1$; the partial-sum hypothesis $\sum_{n\le N}1_A{*}1_A(n)=cN+o(\cdot)$ translates via an Abelian argument to $f(x)^2\sim c/(1-x)$ as $x\to1^-$; a Parseval/$L^2$-mean-square estimate of $f$ on circles $|z|=r$ close to $1$, combined with the forced density $|A\cap[1,N]|\sim c'\sqrt N$ that $f(x)^2\sim c/(1-x)$ implies, produces a contradiction unless the error term is at least $\Omega(N^{1/4})$. That generating-function-plus-Parseval-on-the-circle method is the transferable analytic technique for the *whole* representation-function-regularity family (extended to two-set/ordered versions in arXiv:1911.12313, i.e. directly in #1145's $A,B$ setting) — the natural complementary tool to the combinatorial digit-splitting trick above: digit-splitting builds bounded-representation counterexamples; Parseval/generating-function estimates prove *when smoothness is provably impossible*, which is the shape of result #1145 itself is conjecturing (unboundedness) but which remains unproved for the $\limsup$ (as opposed to average-smoothness) formulation.

Related

- Erdős #28 — additive basis forces unbounded representations — the classical $A=B$ special case (Erdős–Turán 1941 additive-basis conjecture, \$500 prize); still fully OPEN; #1145 is stated on the site as a strengthening of it. - Erdős #40 — sharp density threshold for Erdős–Turán — sibling open strengthening in the same "additive basis" tag cluster; \$500 prize. - erdos/331 — Ruzsa's difference-equation question; DISPROVED (Lean-verified) by the exact binary-digit-parity construction documented above; explicitly cross-linked from #1145's own page. - Sidon sets / B_2 sets / Golomb rulers — neighboring additive-combinatorics theme (unique-representation constructions of this flavor are close cousins of Sidon-set / perfect-difference-set constructions already catalogued here). - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the existing wiki page nearest in spirit to the Parseval/$L^2$ half of the technique story (Erdős–Fuchs' analytic engine), for whoever picks up the "prove unboundedness" (rather than "construct a counterexample") side of this problem family. - concept/digit-position-parity-splitting *(new concept surfaced by this page — not yet written up separately)* — the general combinatorial device of partitioning base-$k$ digit positions among sets to force a perfect (multiplicity-1) additive partition; the technique that both disproves #331 and delimits #1145's hypotheses.