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

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

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

Outcome: partial progress, not a solution.

Claim labels used throughout:

(a) elementary-rigorous — proved here directly from the definitions.
(b) rigorous-modulo-named-theorem — rigorous conditional on the

explicitly named published theorem.

(c) plausible/structural-unverified — a possible route, not a theorem.
(d) computational-only — an exact finite solver result, with no

extrapolation beyond the stated range.

0. Mandatory live-page gate

I fetched the live problem page, its LaTeX view, and the complete discussion thread through the Bright Data browser path on 2026-07-29. Direct datacenter curl was not used for the authoritative gate.

The gate permits an attempt:

| Live field | Value read | |---|---| | status | OPEN | | status description | This is open, and cannot be resolved with a finite computation. | | claimed proofs | 0 claimed proofs for this problem | | currently working | None | | interested in collaborating | None | | comments | 2 comments on this problem | | likes | hediibl, Dogmachine | | looks difficult | ebarschkis | | looks tractable | None | | formalised statement | Yes | | last edited | 23 January 2026 |

There is therefore no claimed solution and no current worker with whom this run would collide.

Verbatim current statement

We say that $A\subset \mathbb{N}$ is an essential component if $d_s(A+B)>d_s(B)$ for every $B\subset \mathbb{N}$ with $0<d_s(B)<1$ where $d_s$ is the Schnirelmann density.
Is $B=\{2^m3^n : m,n\geq 0\}$ an essential component?

The page identifies this as [Va99,1.19], tags it number theory, quotes Ruzsa [Ru99] as calling the $2^m3^n$ set the simplest plausible candidate, and records his conclusion, “I do not even have a plausible guess.” It also points to problem #37.

The two live comments and the convention used here

Zeraoulia Rafik, 15:42 on 31 May 2026, observes that with the literal

positive-integer sumset the displayed set does not contain $0$. Since positive Schnirelmann density forces $1$ to belong to the other summand, the ordinary positive sumset misses $1$ and has Schnirelmann density zero. The comment asks whether the intended object is $\{0\}\cup\{2^m3^n\}$.

Woett, 21:33 on 31 May 2026, replies yes and says that in this setting the

appropriate sumset, sometimes written $\oplus$, adjoins $0$ to both summands.

Comments are marked unverified by the site, but this exchange supplies the only nontrivial convention under which the posted open problem makes sense. Accordingly, throughout the report I put

H=\{2^m3^n:m,n\geq0\},\qquad C\oplus H=(C\cup\{0\})+(H\cup\{0\}). \tag{0.1}

1. Primary-source and literature audit

Sources actually checked

The scanned 1999 booklet

Some of Paul's favorite problems contains problem 1.19 on its additive-number-theory page. It asks whether $B=\{2^m3^n\}$ is an essential component. This verifies that [Va99,1.19] exists and is the intended original source. The live page remains authoritative for the current wording and convention.

Imre Z. Ruzsa,

Erdős and the Integers, Journal of Number Theory 79 (1999), 115–163, DOI 10.1006/jnth.1999.2395, exists with exactly the metadata recorded on the live page. The live page's quotation is its stated known information; the publisher page does not supply a solution.

Ruzsa,

Essential Components, Proceedings of the London Mathematical Society (3) 54 (1987), 38–56, proves the sharp general counting-function threshold summarized on linked problem #37: (b) an essential component must eventually have at least $(\log x)^{1+c}$ elements for some $c>0$, while for every $c>0$ there are essential components with $O((\log x)^{1+c})$ elements.

Zhenchao Ge and Thái Hoàng Lê,

Essential components in vector spaces over finite fields, Combinatorics and Number Theory 10 (2021), 149–165, DOI 10.2140/moscow.2021.10.149, restate Ruzsa's integer theorems precisely, record Plünnecke's equivalence between the Schnirelmann- and lower-density notions after adjoining $0,1$, and reproduce Ruzsa's finite Fourier expansion lemma. Most importantly for status, their concluding page explicitly says that the question whether $\{2^n3^m\}$ is an essential component in $\mathbb N$ remains open.

Exact-phrase searches for $2^m3^n$ together with “essential component” and Schnirelmann density, forward searches from the Ruzsa papers, and searches for papers citing this precise question found the sources above but no primary source claiming a solution or a partial theorem for this particular set. This is a literature-search miss, not a proof that no unindexed work exists.

2. Where $H$ lies relative to the known general theorems

Write $H(x)=|H\cap[1,x]|$. Let $L=\log x$, $a=\log2$, and $b=\log3$. Counting lattice points in the triangle $ma+nb\leq L$ gives (a)

\begin{aligned} H(x) &=\sum_{m=0}^{\lfloor L/a\rfloor} \left(\left\lfloor\frac{L-ma}{b}\right\rfloor+1\right)\\ &=\frac{L^2}{2ab}+O(L) =\frac{(\log x)^2}{2\log2\log3}+O(\log x). \end{aligned} \tag{2.1}

Indeed, deleting the floor signs incurs $O(L)$, and the resulting arithmetic progression sums to the area term with another $O(L)$ boundary error.

Consequences:

(a) $d_s(H)=0$, so the positive-density form of Schnirelmann's

theorem is silent.

(b) Ruzsa's 1987 obstruction is also silent: (2.1) is genuinely of

order $(\log x)^2$, above his forbidden $(\log x)^{1+o(1)}$ range.

(a) $H$ is not an additive basis of any fixed order. For fixed $k$,

every member of $kH\cap[1,x]$ is a sum of $k$ elements of $H\cap[1,x]$, and hence \[ |kH\cap[1,x]|\leq H(x)^k=O_k((\log x)^{2k})=o(x). \tag{2.2} \] Thus neither Erdős's “every basis is essential” theorem nor a fixed-$k$ Plünnecke basis estimate can answer #1146.

This explains why the set is the first natural undecided scale: it is much too thin for every fixed-order basis argument, but it is also polynomially larger in $\log x$ than Ruzsa's universal nonexistence threshold.

3. Exact reduction: what a counterexample must look like

For $X\subseteq\mathbb N$, put

X(N)=|X\cap[1,N]|,\qquad \sigma(X)=\inf_{N\geq1}\frac{X(N)}N.

For a prospective competitor $C$, set $S=C\oplus H$ and define its $H$-boundary up to $N$ by

\partial_H C(N)=|(S\setminus C)\cap[1,N]|. \tag{3.1}

Since $0$ is adjoined, $C\subseteq S$, and therefore

\frac{S(N)}N=\frac{C(N)}N+\frac{\partial_HC(N)}N. \tag{3.2}

Boundary-zero criterion

The following is an exact reformulation, not a heuristic.

Proposition 3.1 (a). $H$ fails to increase the density of some $C$ with $\sigma(C)=\alpha\in(0,1)$ if and only if there are such a $C$ and integers $N_j\to\infty$ satisfying

\frac{C(N_j)}{N_j}\longrightarrow\alpha,\qquad \frac{\partial_HC(N_j)}{N_j}\longrightarrow0. \tag{3.3}

Proof. If $\sigma(S)=\sigma(C)=\alpha$, choose $N_j$ with $S(N_j)/N_j\to\alpha$. These $N_j$ may be taken to infinity: positive Schnirelmann density forces $1\in C$, and at any finite non-full prefix the least missing $t$ is added as $t=(t-1)+1$, while a full prefix has ratio $1>\alpha$. Thus $S(N)/N>\alpha$ for every fixed $N$, so an infimizing sequence cannot remain bounded. The inequalities

\alpha\leq C(N_j)/N_j\leq S(N_j)/N_j

and (3.2) give (3.3). Conversely, (3.2) and (3.3) show that $S(N_j)/N_j\to\alpha$, while $S\supseteq C$ gives $\sigma(S)\geq\alpha$. Hence $\sigma(S)=\alpha$. $\square$

There is a useful structural consequence. For each fixed $h\in H\cup\{0\}$,

|((C+h)\setminus C)\cap[1,N_j]| \leq \partial_HC(N_j)=o(N_j). \tag{3.4}

In particular $1\in H$, so the number of occupied-to-empty transitions of $1_C$ before $N_j$ is $o(N_j)$. The number of reverse transitions differs by at most one. Thus (a) a counterexample must look, on every density-minimizing subsequence, like a union of only $o(N_j)$ long intervals, while being simultaneously almost invariant under all the translations $2^m3^n\leq N_j$. The unresolved tension is between those two requirements.

Periodic and positive-boundary competitors are excluded

Proposition 3.2 (a). No eventually periodic $C$ with $0<\sigma(C)<1$ can witness failure. More generally, failure is impossible whenever

\liminf_{N\to\infty} \frac{|((C+1)\setminus C)\cap[1,N]|}{N}>0. \tag{3.5}

Proof. Positive Schnirelmann density forces $1\in C$. At every finite $N$ for which $C\cap[1,N]\neq[1,N]$, let $t$ be its least missing integer. Then $t-1\in C$ and $1\in H$, so $t=(t-1)+1\in S\setminus C$. Consequently every finite prefix has a strict increase; if $C(N)=N$, its ratio is already $1>\sigma(C)$.

Under (3.5), the increase is bounded below by a fixed positive amount for all sufficiently large prefixes. The finitely many earlier prefixes have a positive minimum increase, so $\sigma(S)>\sigma(C)$.

If $C$ is eventually periodic with period $q$ and has a nonempty proper eventual residue set $R\subset\mathbb Z/q\mathbb Z$, then $R\cup(R+1)$ has at least $|R|+1$ elements; otherwise $R+1=R$, which would force $R$ to be empty or the whole cyclic group. Thus (3.5) holds with asymptotic boundary at least $1/q$. If the eventual residue set is the whole group, then $C$ is cofinite, the large-prefix ratios tend to one, and the preceding strict finite-prefix argument again gives a uniform gap above $\sigma(C)<1$. $\square$

This is genuine, but limited, progress: every counterexample must be strongly aperiodic and must have vanishing transition density along its critical prefixes.

4. A finite impact function that directly approximates the problem

For $0<\alpha<1$ and $N\geq1$, define

\begin{split} F_\alpha(N)=\min\{& |((C\cup\{0\})+(H\cup\{0\}))\cap[1,N]|:\ C\subseteq[1,N],\\ & |C\cap[1,j]|\geq\lceil\alpha j\rceil \text{ for every }1\leq j\leq N\}. \end{split} \tag{4.1}

Only the elements of $H$ up to $N$ enter this finite minimum.

Proposition 4.1 (a). If an infinite $C$ satisfies $\sigma(C)\geq\alpha$, then for every $N$

|(C\oplus H)\cap[1,N]|\geq F_\alpha(N). \tag{4.2}

Consequently,

\inf_{N\geq1}\frac{F_\alpha(N)}N>\alpha \tag{4.3}

would prove a uniform density increase for every $C$ with $\sigma(C)\geq\alpha$.

Proof. The prefix $C\cap[1,N]$ is feasible in (4.1), and positive summands larger than $N$ cannot affect sums at most $N$. $\square$

For a finite horizon $L$, let

\sigma_L(X)=\min_{1\leq j\leq L}\frac{|X\cap[1,j]|}{j}.

An equally useful exact identity is (a)

\min_{\substack{C\subseteq[1,L]\\ \sigma_L(C)\geq\alpha}} \sigma_L(C\oplus H) =\min_{1\leq N\leq L}\frac{F_\alpha(N)}N. \tag{4.4}

The lower bound follows by applying (4.1) to every prefix. For equality, take an optimizer at a minimizing $N$ and include every integer from $N+1$ through $L$; this preserves feasibility and cannot change sums at most $N$.

Thus (4.1) is not an arbitrary modular surrogate: it is the exact worst-case truncated version of the posted Schnirelmann-density question.

5. Exact computation through $N=60$

The standalone checker erdos1146_wavew035_reverify.py rebuilds (4.1) as follows:

Boolean $x_i$ records $i\in C$, with $x_0=1$.
Boolean $y_s$ records $s\in C\oplus H$.
It imposes

$\sum_{i=1}^j x_i\geq\lceil\alpha j\rceil$ for every prefix.

For every $s=i+h\leq N$, it imposes $y_s\geq x_i$.
It minimizes $\sum_{s=1}^Ny_s$.

OR-Tools CP-SAT returned OPTIMAL with matching integer lower and upper bounds for all $180$ instances

\alpha\in\{1/4,1/3,1/2\},\qquad 1\leq N\leq60.

Every solver witness is then reconstructed by a separate literal double sum. The script also generates the $3$-smooth numbers by two independent methods. Finally, it exhausts all $2^{N-1}$ possible positive-density prefixes for every $N\leq20$, a total of $2^{20}-1=1,048,575$ masks, and independently matches every CP-SAT optimum. These facts are (d) computational-only, albeit exact finite computations.

Selected endpoint values are:

| $N$ | $F_{1/4}(N)$ | $F_{1/3}(N)$ | $F_{1/2}(N)$ | |---:|---:|---:|---:| | 10 | 10 | 10 | 10 | | 20 | 18 | 19 | 20 | | 30 | 27 | 28 | 29 | | 40 | 36 | 37 | 39 | | 50 | 44 | 46 | 48 | | 60 | 53 | 55 | 58 |

The strict record lows of $F_\alpha(N)/N$ are:

| $\alpha$ | record positions and values through $60$ | |---:|---| | $1/4$ | $N=1:1;\ N=11:10/11;\ N=20:9/10;\ N=23:20/23$ | | $1/3$ | $N=1:1;\ N=14:13/14;\ N=26:12/13;\ N=38:35/38;\ N=46:21/23;\ N=57:52/57$ | | $1/2$ | $N=1:1;\ N=22:21/22$ |

Combining this with (4.4) gives the following sharp concrete regime:

\begin{aligned} \min_{\sigma_{60}(C)\geq1/4}\sigma_{60}(C\oplus H)&=\frac{20}{23},\\ \min_{\sigma_{60}(C)\geq1/3}\sigma_{60}(C\oplus H)&=\frac{52}{57},\\ \min_{\sigma_{60}(C)\geq1/2}\sigma_{60}(C\oplus H)&=\frac{21}{22}. \end{aligned} \tag{5.1}

All three equalities are (d).

Compact optimizing prefixes are:

for $1/4$, at $N=23$,

$C=\{1,2,4,8,10,16\}$; the only missing normalized sums are $15,21,23$;

for $1/3$, at $N=57$,

\[ C=\{1,2,4,6,7,8,10,11,14,16,22,23,28,31,32,34,38,40,46\}; \] the missing sums are $21,45,51,53,57$;

for $1/2$, at $N=22$,

$C=\{1,2,3,5,7,8,9,11,12,15,17\}$; only $22$ is missing.

To make each a length-$60$ witness for (5.1), include every subsequent integer through $60$. The checker verifies all prefix constraints and all displayed missing-sum lists directly.

Reproduction:

python3 runs/erdos1146_wavew035_reverify.py

On this VM the complete audit took about 13 seconds wall time with four solver workers (Python 3.12.3, OR-Tools 9.15.6755). The verifier's SHA-256 is ca8faff0ffc9504621a18e8ac02713314cbc69983a34675378a0fc11bc38a205.

6. What remains, and why the standard routes stop

The finite values in (5.1) are much larger than their input densities, but they cannot be extrapolated. The right side of (4.4) is nonincreasing with the horizon, and the table already exhibits new record lows. A calculation at any fixed $L$ cannot supply the uniform all-$N$ step in (4.3).

There is a universal elementary estimate (a)

F_\alpha(N)\geq \min\bigl(N,\lceil\alpha N\rceil+1\bigr). \tag{6.1}

If $C\cap[1,N]$ is not full, its least missing point is supplied by the shift $+1$; if it is full, the sumset is full. But (6.1), divided by $N$, tends only to $\alpha$. This pinpoints why any argument using only the element $1$, or any fixed finite subset of $H$, stalls.

Ruzsa's Fourier mechanism gives another precise view. Ge–Lê reproduce his finite-group lemma: (b) if a probability weight supported on $K$ has every nontrivial Fourier coefficient bounded by $\eta<1$, then adding $K$ expands every finite set by a quantitative amount depending on $1-\eta^2$. Ruzsa's thin essential components are built by arranging such pseudorandomness across scales. For $H=\{2^m3^n\}$, the missing input is a deterministic, scale-compatible small-bias/expansion theorem for these multiplicative orbits. Cardinality (2.1) alone gives no such Fourier control, and the literature search found no theorem providing it.

Accordingly there are two exact ways to state the remaining obstruction:

(a), exact: exclude the boundary-zero configuration (3.3) for every

$\alpha\in(0,1)$; or construct one to disprove essentiality.

(c), stronger sufficient target: prove (4.3) for every

$\alpha\in(0,1)$, presumably by a scale-uniform expansion or Fourier lemma special to $2^m3^n$.

Raw exhaustive computation is not a substitute. Even at an optimistic $10^8$ masks per second, enumerating all prefixes at $N=60$ would cost about $183$ core-years; CP-SAT succeeds here only by exploiting the constraints. More importantly, extending the table to $N=100$ or $N=1000$ would still leave the uniformity step untouched. The missing object is an all-scale lemma, not a larger finite cutoff.

No construction, counterexample, or uniform density increment was found. The verified progress is the exact boundary reduction, exclusion of all eventually periodic/positive-boundary competitors, and the sharp finite-horizon table (5.1).

PARTIAL: #1146 remains open; a counterexample must have vanishing simultaneous $2^m3^n$-boundary along density-minimizing prefixes, all eventually periodic competitors are excluded, and exact optimization gives the sharp length-60 bounds $20/23,52/57,21/22$ at input densities $1/4,1/3,1/2$.

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