Erdoes #1145 - working report - Erdős Problem a Day

Erdős problem #1145 — live-page audit, reduction, and exact finite computation

Date of run: 2026-07-29 (UTC)

Outcome: partial progress, not a solution.

Claim labels used below:

(a) elementary-rigorous — proved here from definitions.
(b) rigorous-modulo-named-theorem — the deduction is rigorous if the

explicitly cited theorem is used.

(c) plausible/structural-unverified — a possible route or pattern, not a

theorem.

(d) computational-only — an exact finite statement established by the

exhaustive checker, with no claim outside its stated range.

0. Mandatory live-page gate

I fetched the live page through the Bright Data browser path (not datacenter curl) on 2026-07-29. I also opened the page's LaTeX view, bibliography popover, and full discussion thread.

The gate did not require a skip:

| Live field | Value read | |---|---| | status | OPEN | | claimed proofs | 0 claimed proofs for this problem | | currently working | None | | interested in collaborating | None | | likes | None | | looks difficult | ebarschkis | | looks tractable | None | | working on formalisation | None | | formalised statement | Yes | | last edited | 11 April 2026 |

Verbatim current statement

Let $A=\{1\leq a_1<a_2<\cdots\}$ and $B=\{1\leq b_1<b_2<\cdots\}$ be sets of integers with $a_n/b_n\to 1$.
If $A+B$ contains all sufficiently large positive integers then is it true that $\limsup 1_A\ast 1_B(n)=\infty$?

Here and below I write

r_{A,B}(t)=(1_A*1_B)(t) =\#\{(a,b)\in A\times B:a+b=t\}.

Other material on the live page

The page calls this a conjecture of Erdős and Sárközy. It records the counterexample without the condition relating $A$ and $B$: take $A$ to have nonzero binary digits only in even positions and $B$ only in odd positions; then $r_{A,B}(t)=1$ for every $t$ (after the usual nonnegative-integer normalisation). It says that #1145 is stronger than problem #28 and points to problem #331.

The bibliography popover identifies [Va99,1.17] as Some of Paul's favorite problems, a booklet produced for the Budapest conference “Paul Erdős and his mathematics” in July 1999.

I read all four comments:

On 28 January 2026 Felix Pernegger observed that, with the displayed

positive sets, $1\notin A+B$.

Thomas Bloom replied that the condition should say all sufficiently large

integers (or should allow $0$); the page was updated.

On 5 February 2026 Zach Hunter asked why $a_n/b_n\to1$ is needed.
Bloom replied with the even/odd binary-digit construction above, linked

#331, and recorded that the page was updated.

None is a proof claim or a current-worker marker.

1. Primary-source and literature audit

Sources actually checked

The scanned 1999 booklet is available

here. Problem 1.17 gives the Erdős–Sárközy formulation with $a_n/b_n\to1$, $g(n)=\#\{(i,j):n=a_i+b_j\}$, and the conjectural conclusion $\limsup g(n)=\infty$. The scan says $g(n)>0$ for all $n$; the live page's “all sufficiently large positive integers” is the authoritative corrected version.

Taking $B=A$ in #1145 gives the Erdős–Turán conjecture #28 because

$a_n/b_n=1$. The live #28 page was also fetched through Bright Data and was OPEN with zero claimed proofs and no current worker. The original paper is Erdős–Turán, On a Problem of Sidon in Additive Number Theory, and on some Related Problems, J. London Math. Soc. 16 (1941), 212–215, DOI 10.1112/jlms/s1-16.4.212. Thus a solution of #1145 would solve a famous still-open special case. (a) The implication #1145 $\Rightarrow$ #28 is immediate by setting $B=A$.

The live #331 page records Ruzsa's binary-digit counterexample and the

possible strengthened condition $A(x)\sim c_A\sqrt{x}$, $B(x)\sim c_B\sqrt{x}$. This is relevant to the difference-set obstruction discussed below, but it does not settle #1145.

Fang and Sándor,

On sets with sum and difference structure, arXiv:2205.06553, explicitly determine the pairs of nonnegative-integer sets satisfying $r_{A,B}(n)=1$ for every $n\geq0$. Their Theorem 1.1 is restated as Theorem A in Bárány–Fang–Sándor, arXiv:2301.04365: such pairs are alternating mixed-radix digit systems. (b) This is a classification of perfect complements, but its hypothesis is much stronger than an eventual bound $r_{A,B}\leq K$.

Ruzsa,

Exact additive complements, arXiv:1510.00812, studies a different use of “exact”: additive complements with $A(x)B(x)/x\to1$. The paper verifies and cites the Sárközy–Szemerédi theorem that then $A(x)B(x)-x\to\infty$. This machinery cannot be invoked from $a_n/b_n\to1$; Section 3 gives an explicit reason.

Exact-phrase searches for the displayed $a_n/b_n$ condition, the two-sequence representation function, and the Erdős–Sárközy attribution found the live problem and the related complement literature above, but no primary paper claiming a solution or a partial result specifically for #1145. This is a search miss, not a claim that no such paper exists.

2. A rigorous reduction to the critical quadratic regime

The following gives a concrete restriction on every possible bounded-representation counterexample.

Proposition (critical quadratic window)

Suppose $A+B$ contains every integer at least $N_0$ and $a_m/b_m\to1$.

(a) For every sufficiently large $m$,

\[ \min(a_m,b_m)\leq (m-1)^2+N_0, \] and hence \[ a_m,b_m\leq (1+o(1))m^2. \tag{2.1} \]

(a) For every $m$,

\[ \max_{t\leq a_m+b_m}r_{A,B}(t) \ \geq\ \frac{m^2}{a_m+b_m+1}. \tag{2.2} \] Consequently, if $a_m=o(m^2)$ along any infinite subsequence, then $\limsup_t r_{A,B}(t)=\infty$.

(a) More quantitatively, if $r_{A,B}(t)\leq K$ for all sufficiently

large $t$, where $K<\infty$, then \[ \left(\frac1{2K}-o(1)\right)m^2 \leq a_m,b_m \leq (1+o(1))m^2. \tag{2.3} \] In particular both counting functions are of order $\sqrt{x}$: $A(x),B(x)=\Theta_K(\sqrt{x})$.

Proof

Put $c_m=\min(a_m,b_m)$. Every $t\in[N_0,c_m-1]$ has a representation $t=a_i+b_j$. Because $t<a_m$ and $t<b_m$, necessarily $i,j\leq m-1$. There are only $(m-1)^2$ such ordered prefix pairs, while the interval has $c_m-N_0$ integers. This proves

c_m-N_0\leq(m-1)^2.

Since $\max(a_m,b_m)/c_m\to1$, (2.1) follows.

The $m^2$ pairs $(a_i,b_j)$, $1\leq i,j\leq m$, all have sums in $[2,a_m+b_m]$. Pigeonhole gives (2.2). If its right side tends to infinity on a subsequence, the maximizing sums must also tend to infinity (each fixed sum has only finitely many representations), proving the stated consequence.

Finally choose $T$ so that $r_{A,B}(t)\leq K$ for $t\geq T$, and put $C=\sum_{t<T}r_{A,B}(t)<\infty$. Counting the same $m^2$ prefix pairs,

m^2\leq C+K(a_m+b_m+1).

Thus $a_m+b_m\geq K^{-1}m^2-O(1)$. The ratio hypothesis makes each summand $(1/2+o(1))(a_m+b_m)$, which proves the lower half of (2.3); (2.1) gives the upper half. Inverting these two-sided quadratic bounds gives $A(x),B(x)=\Theta_K(\sqrt{x})$. $\square$

This is a genuine reduction: all subquadratic candidate constructions are eliminated without using the covering hypothesis in the multiplicity estimate, while coverage eliminates superquadratic growth. What remains is the critical $a_m,b_m=\Theta(m^2)$ regime.

3. Why termwise matching does not give matching counting functions

A tempting next step is to infer $A(x)\sim B(x)$ from $a_n/b_n\to1$, then apply complement results phrased in terms of counting functions. That inference is false even at quadratic scale.

For $k\geq1$ and $2^{k-1}\leq n\leq2^k-1$, define (a)

\begin{aligned} b_n&=4^k+(n-2^{k-1}),\\ a_n&=4^k+2^{k-1}+(n-2^{k-1}). \end{aligned} \tag{3.1}

Both sequences are strictly increasing. In block $k$,

1\leq\frac{a_n}{b_n} \leq1+2^{-k-1},

so $a_n/b_n\to1$. Also

n^2\leq a_n,b_n\leq6n^2,

so this is already in the critical quadratic window.

x_k=4^k+2^{k-1}-1

one has exactly

B(x_k)=2^k-1,\qquad A(x_k)=2^{k-1}-1,

and therefore $B(x_k)/A(x_k)\to2$, not $1$.

This example is not an additive complement and is not a counterexample to #1145. Its role is precise: the quantile hypothesis by itself does not supply the counting-function lemma needed to enter Ruzsa's $A(x)B(x)/x\to1$ theory. Under a hypothetical bound $r_{A,B}\leq K$, the definitions yield only

x-O(1)\leq A(x)B(x)\leq 2Kx+O(1),

because coverage supplies the lower bound and all pairs with $a,b\leq x$ have sums at most $2x$. No limit $A(x)B(x)/x\to1$ follows.

The checker rebuilds (3.1) through block $12$; at the last threshold it finds

A(x)=2047,\quad B(x)=4095,\quad B(x)/A(x)=4095/2047.

4. The standard fixed-base digit construction cannot work

The live page's counterexample without $a_n/b_n\to1$ is one member of a larger family. The following excludes that entire fixed-base family.

Lemma (fixed-base digit obstruction)

Fix $q\geq2$, and partition the nonnegative digit positions into two infinite sets

S=\{s_0<s_1<\cdots\},\qquad T=\{t_0<t_1<\cdots\}.

Let $A_S$ consist of the nonnegative integers whose base-$q$ digits outside $S$ vanish, and define $B_T$ analogously. Then $\mathbb N_0=A_S\oplus B_T$, but the increasing enumerations $\alpha_n,\beta_n$ (starting with rank $0$) do not satisfy $\alpha_n/\beta_n\to1$. In fact, for every $j$,

\alpha_{q^j}=q^{s_j},\qquad \beta_{q^j}=q^{t_j},

and hence

\max\!\left(\frac{\alpha_{q^j}}{\beta_{q^j}}, \frac{\beta_{q^j}}{\alpha_{q^j}}\right)\geq q. \tag{4.1}

Proof (a). Splitting the base-$q$ digits gives a unique sum representation. If the base-$q$ digits of a rank $n$ are moved from positions $0,1,\ldots$ to $s_0,s_1,\ldots$, the resulting values are still in increasing order: a new leading selected digit outweighs all smaller selected positions. Thus rank $q^j$ is exactly $q^{s_j}$; similarly it is $q^{t_j}$ on the other side. Since a partition has $s_j\neq t_j$, (4.1) follows. $\square$

Adding fixed constants to make both sets positive does not alter this subsequence obstruction. The checker tests the decisive ranks for all 18,824 balanced partitions of the first $2k$ positions with $q=2,3,4,5$ and $1\leq k\leq7$, and independently convolves complete small digit systems.

This does not exclude general alternating mixed-radix systems, still less general bounded-multiplicity complements.

5. Exact finite computation for the balanced $K=1$ model

The most rigid finite proxy for a perfect complement is an ordered pair $(U,V)$ satisfying

U\oplus V=\{0,1,\ldots,m^2-1\},\qquad |U|=|V|=m. \tag{5.1}

Write

U=\{u_0<\cdots<u_{m-1}\},\qquad V=\{v_0<\cdots<v_{m-1}\},

and define the upper-half rank distortion

D(U,V)= \max_{\lceil m/2\rceil\leq i<m} \max\!\left(\frac{u_i}{v_i},\frac{v_i}{u_i}\right), \qquad D_m=\min_{(U,V)\text{ satisfying (5.1)}}D(U,V). \tag{5.2}

The standalone program exhausts every ordered pair in (5.1), not merely mixed-radix examples. The exact result is:

| $m$ | ordered pairs (5.1) | sharp $D_m$ | |---:|---:|---:| | 2 | 2 | 2 | | 3 | 2 | 3 | | 4 | 6 | 2 | | 5 | 2 | 5 | | 6 | 14 | 2 | | 7 | 2 | 7 | | 8 | 20 | 2 | | 9 | 6 | 3 | | 10 | 14 | 2 | | 11 | 2 | 11 | | 12 | 84 | 2 | | 13 | 2 | 13 | | 14 | 14 | 2 | | 15 | 14 | 3 | | 16 | 70 | 2 | | 17 | 2 | 17 | | 18 | 84 | 2 | | 19 | 2 | 19 | | 20 | 84 | 2 | | 21 | 14 | 3 | | 22 | 14 | 2 | | 23 | 2 | 23 | | 24 | 460 | 2 | | 25 | 6 | 5 | | 26 | 14 | 2 | | 27 | 20 | 3 | | 28 | 84 | 2 | | 29 | 2 | 29 | | 30 | 230 | 2 |

Thus, (d) for every $2\leq m\leq30$, the sharp value $D_m$ is the least prime factor of $m$. This last compact pattern is only a finite observation; it is not asserted for $m>30$.

For example, an optimal $m=12$ witness is

\begin{aligned} U={}&(0,1,2,3,4,5,72,73,74,75,76,77),\\ V={}&(0,6,12,18,24,30,36,42,48,54,60,66), \end{aligned}

with $D(U,V)=2$. An optimal $m=9$ witness is

\begin{aligned} U={}&(0,1,2,9,10,11,18,19,20),\\ V={}&(0,3,6,27,30,33,54,57,60), \end{aligned}

with $D(U,V)=3$.

Why the enumeration is exhaustive

Maintain sets containing $0$ whose already formed sums in $[0,m^2-1]$ are unique, and let $n$ be the least uncovered integer. In any completion, $n$ must be inserted into $U$ or into $V$. Indeed, if $n=u+v$ with $0<u,v<n$, then both elements were inserted earlier and $n$ would already be covered. The search therefore branches on exactly those two possibilities and rejects a branch when a new sum collides. Induction on the least uncovered integer proves completeness and absence of duplicates. (a)

At a leaf, the checker recomputes the full convolution from scratch and requires exactly one copy of every integer in the interval. A separate, combinations-based brute force tests all 207,818 candidate set-pairs for $m=2,3,4$ and obtains exactly the same complete solution sets. (d)

This finite result is relevant to the most obvious balanced, unique-representation obstruction, but it does not imply #1145: the infinite problem permits an initial exceptional interval, arbitrary finite $K$, unequal finite prefix counts, and no exact interval factorisation at a prescribed scale.

6. Reproduction

The standalone checker is runs/erdos1145_wavew034_reverify.py. It uses only the Python 3.12 standard library.

Run:

python runs/erdos1145_wavew034_reverify.py

Observed on this VM:

independent brute-force set pairs checked: 207818
fixed-base partitions checked: 18824
quadratic block endpoint: A(x)=2047, B(x)=4095, B(x)/A(x)=4095/2047
finite counting pairs checked: 8434
ALL CHECKS PASSED in 8.041s

The script SHA-256 is 9de6e85929a11219d70cc0fb3ee7a85cc5022e95dd6bd1e8bbb8659d898a6a5d.

7. Exact remaining wall

The reduction leaves this sharply delimited case:

For a fixed $K$, can cofinite coverage, $r_{A,B}\leq K$ eventually, $a_m,b_m=\Theta_K(m^2)$, and $a_m/b_m\to1$ coexist?

For $K=1$, uniqueness says that the positive difference sets of the two tails cannot meet: an equality

a_i-a_j=b_\ell-b_k>0

produces the collision $a_j+b_\ell=a_i+b_k$. (a) The binary digit construction achieves disjoint differences but fails the quantile condition by Section 4. The missing ingredient is a uniform stability or collision lemma saying that cofinite coverage at quadratic scale forces sufficiently many exact common differences (and, for general $K$, enough aligned collisions to exceed $K$) when corresponding quantiles are multiplicatively close. No checked source above supplies such a lemma. (c)

The exact $K=1$ recursion exploits uniqueness and is tiny through $m=30$. A naive search for arbitrary balanced $m=10$ prefixes in $[0,99]$, even after fixing $0$ in both sets, has

\binom{99}{9}^2 =2{,}996{,}468{,}134{,}777{,}160{,}882{,}574{,}736

candidate pairs. At an unrealistically sustained $10^8$ candidates per second this is about $8.3\times10^{12}$ core-hours. SAT/CP pruning could probe small $K$ and small horizons, but no finite horizon by itself gives the uniformity needed for the infinite conjecture. I therefore did not run a heavier search.

PARTIAL: Proved the critical quadratic-window reduction and excluded every fixed-base digit complement; exhaustively computed the sharp balanced perfect-complement tail distortion for all 2<=m<=30, but the uniform bounded-multiplicity quadratic case remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger