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

Erdős problem 951 — wave w024

Date: 2026-07-28 UTC

Executive result

The live-page gate passed: the problem is marked OPEN, there are 0 claimed proofs, and both “Currently working” and “Interested in collaborating” are None. The discussion contains finite counterexamples classified as partial results, but the formal proof-claim page says “No proof claims have been submitted yet.” Therefore this run proceeded.

The new progress is a nearly sharp determination of the three-generator extremum

m(3):=\inf\left\{\max(a,b,c): 1<a<b<c,\ \{a^i b^j c^k:i,j,k\geq0\}\text{ is 1-separated}\right\}.

The independently checked bounds are

\boxed{\,4.309405275<m(3)<4.3094055\,}.

The lower bound is elementary-rigorous. The upper bound is a computer-assisted existence certificate using only exact rational arithmetic and an explicit infinite-tail bound. It improves the live thread's listed rational upper bound \(m(3)\leq113/24=4.70833\ldots\).

By the page-listed extension lemma (also reproved below), the certified finite triple extends to an infinite sequence. Thus the literal live statement fails already at

x=4.3094055,\qquad \#\{a_i\leq x\}\geq3>2=\pi(x).

This does not answer the intended asymptotic variant (“for all sufficiently large \(x\)”).

0. Mandatory live-page check

The page and its discussion were fetched through the Bright Data browser path, not datacenter curl.

Live page: <https://www.erdosproblems.com/951>
Full discussion: <https://www.erdosproblems.com/forum/discuss/951>
Proof-claim tab: <https://www.erdosproblems.com/forum/thread/951/proof-claims>
Accessed: 2026-07-28
Page last edited: 2026-04-06
Status: OPEN
Comments: 22
Claimed proofs: 0
Proof-claim tab: no submitted proof claims
Currently working: None
Interested in collaborating: None

Verbatim current statement

Let $1<a_1<\cdots$ be a sequence of real numbers such that\[\left\lvert \prod_i a_i^{k_i}-\prod_j a_j^{\ell_j}\right\rvert \geq 1\]for every distinct pair of non-negative finitely supported integer tuples $k_i,\ell_j\geq 0$. Is it true that\[\#\{ a_i \leq x\} \leq \pi(x)?\]

Page-listed results and relevant comments

The main page says:

Erdős attributed the question to an audience member at Queens College,

perhaps S. Shapiro.

Erdős later asked whether equality characterizes the ordinary primes.
The \(a_i\) are Beurling generalized primes and their monomials are the

generalized integers.

The intended quantifier on \(x\) is unclear. The page explicitly says the

“all \(x\)” version has finite counterexamples and any finite prefix can be extended greedily; it lists an \(x=10\) counterexample.

I read all 22 comments. The mathematically relevant content is:

Terence Tao (2025-09-07) records

\[ \prod_i(1-a_i^{-s})^{-1}\leq\zeta(s),\quad s>1, \] and notes that this gives Mertens-type information but not a prime-number- theorem-strength bound.

The January 2026 Barreto–Price note gives five log-algebraic generators below

10 and a measure-theoretic extension step. The initial discussion called it a disproof of one formulation; subsequent comments explicitly restricted it to a finite-\(x\) partial result.

Sothanaphan's rational triple

\[ 101/42,\quad367/103,\quad113/24 \] is claimed to generate a fully 1-separated semigroup, certified using Matveev/de Weger/LLL plus a finite exact check.

Tao proposed a probabilistic log-box method. Sothanaphan's follow-up note

certifies \(m(n)<p_n\) for \(3\leq n\leq7\), giving finite failures just below \(5,7,11,13,17\).

Bloom's comments emphasize that none of these produces failures for

infinitely many large \(x\); that is the formulation the site continues to regard as open.

Two comments mention the elementary integer-generator special case.

Some historical comments used words such as “disprove” while the construction was being assessed. The current authoritative state is nevertheless OPEN, with zero formal proof claims and the finite results classified as partial. No current-worker marker is present.

1. Primary-source and literature audit

Original Erdős sources

All three cited originals were downloaded from the Rényi Erdős archive and their relevant pages inspected.

P. Erdős, Some applications of graph theory to number theory (1969),

p. 82: <https://www.renyi.hu/~p_erdos/1969-14.pdf>. This gives the finite real-number formulation and asks whether the maximum number of generators is \(\pi(n)\).

P. Erdős, Problems and results on combinatorial number theory III (1977),

p. 68: <https://www.renyi.hu/~p_erdos/1977-27.pdf>. This states the infinite-sequence formulation, attributes it to the Queens College audience member, and says it had apparently not previously been considered.

P. Erdős, A survey of problems in combinatorial number theory (1980),

pp. 103–104: <https://www.renyi.hu/~p_erdos/1980-03.pdf>. This repeats the problem, attributes it to H. N. Shapiro, asks whether equality occurs only for the ordinary primes, and notes the earlier 1969 formulation.

Thus the “all \(x\)” reading is not an invention of the tracker: it is natural from both the 1969 finite extremal question and the unqualified inequalities in 1977/1980. The modern site retains OPEN status because the asymptotic intent is plausible and the known counterexamples are finite-prefix phenomena.

Search outcome

Exact-phrase searches for the 1-separation condition, “free multiplicative semigroup”, and Beurling generalized integers found no accepted paper resolving the asymptotic problem. Representative primary literature that was checked:

H. G. Diamond, When do Beurling generalized integers have a density?,

J. reine angew. Math. 295 (1977), 22–39, <https://doi.org/10.1515/crll.1977.295.22>.

G. Debruyne and J. Vindas, *On General Prime Number Theorems with

Remainder*, arXiv:1601.05324, <https://arxiv.org/abs/1601.05324>.

F. Broucke and G. Debruyne, *On zero-density estimates and the PNT in short

intervals for Beurling generalized numbers*, arXiv:2211.08716, <https://arxiv.org/abs/2211.08716>.

F. Broucke, G. Debruyne, and Sz. Révész, *Some examples of well-behaved

Beurling number systems*, arXiv:2309.01567, <https://arxiv.org/abs/2309.01567>.

These papers study density hypotheses or quantitative asymptotics for the generalized-integer counting function. Mere 1-separation gives only \(N(x)\leq x+O(1)\), not an asymptotic \(N(x)=Ax+o(x)\), so their stated hypotheses do not settle this problem.

The three public 2026 notes linked from the live discussion were also downloaded and read:

Barreto–Price \(x=10\) note:

<https://drive.google.com/file/d/1CRBMOMCTdAuuVp8Wqace1AQ_dpK9BeTV/view>

Sothanaphan rational \(n=3\) note:

<https://drive.google.com/file/d/1gykR98vV0FiWwUl_S9SLy33vb9loN8-P/view>

Sothanaphan probabilistic \(3\leq n\leq7\) note:

<https://drive.google.com/file/d/1SIATgVENtE5696MERLjesEmKgNWh5wFK/view>

The last note's supplied program stops its infinite tail when one term falls below a tolerance but does not itself add a proved bound for the omitted infinite remainder. It also uses high-precision mpmath values plus a safety epsilon rather than directed interval rounding. Neither issue appears fatal given its large margins, but the checker in this run repairs both: all proof decisions are exact rational comparisons, and the infinite remainder is explicitly majorized.

No claim of literature completeness is made. The honest search result is that the exact separation-only condition led back to the Erdős page and the 2026 notes, while the peer-reviewed Beurling literature found uses stronger counting-function hypotheses.

2. New elementary lower bound for \(m(3)\)

Classification: (a) elementary-rigorous.

Let \(1<a<b<c\), and suppose every two distinct monomials in \(a,b,c\) differ by at least 1. If \(c\geq4.31\), the desired lower bound is immediate, so assume \(c<4.31<5\).

Comparing \(1,a,b,c\) gives

a\geq2,\qquad b\geq a+1,\qquad c\geq b+1\geq a+2.

Compare \(a^2\) and \(c\). If \(c\geq a^2+1\), then \(c\geq5\), impossible. Consequently

a^2\geq c+1. \tag{2.1}

Combining (2.1) with \(c\geq a+2\) gives \(a^2\geq a+3\), hence \(a>2.3\) and \(c>4.3\).

Three more pairs have forced orientations throughout \(4.3<c<4.31\).

Pair \(b^2,ac\)

If \(ac\geq b^2+1\), then

c\geq\frac{b^2+1}{a} \geq\frac{(a+1)^2+1}{a} =a+2+\frac2a\geq5,

where the last inequality follows from \(a+2/a-3=(a-1)(a-2)/a\geq0\). Therefore

b^2\geq ac+1. \tag{2.2}

Pair \(c^2,a^2b\)

Since \(a\leq c-2\) and \(b\leq c-1\),

a^2b\leq(c-2)^2(c-1)<c^2+1

on \([4.3,4.31]\). For the strict inequality, set

\[ D(c)=c^2+1-(c-2)^2(c-1). \]

Here \(D\) is decreasing on this interval and \(D(4.31)=1.913609>0\). Separation therefore forces

c^2\geq a^2b+1. \tag{2.3}

Pair \(a^7,c^4\)

By (2.1), \(a^7\geq(c+1)^{7/2}\). The function

g(c)=c^4-(c+1)^{7/2}

is increasing on \([4.3,4.31]\), and an exact squared rational comparison gives \(g(4.31)<1\) (numerically \(0.06217\ldots\)). Hence the orientation \(c^4\geq a^7+1\) is impossible, and

a^7\geq c^4+1. \tag{2.4}

One-variable reduction

Define

A(c)=(c^4+1)^{1/7}

and

\[ F(c)=(c^2-1)^2-cA(c)^5-A(c)^4. \]

Equation (2.4) gives \(a\geq A(c)\). Equations (2.2) and (2.3) give

\sqrt{ac+1}\leq b\leq\frac{c^2-1}{a^2},

(c^2-1)^2-a^4(ac+1)\geq0. \tag{2.5}

The left side of (2.5) is strictly decreasing in \(a>0\). Since \(a\geq A(c)\), (2.5) implies \(F(c)\geq0\).

On \(4.3\leq c\leq4.31\), one has \(2.3<A(c)<2.31\), and

F'(c)=4c(c^2-1)-A^5-\frac{4c^3}{7} \left(\frac{5c}{A^2}+\frac4{A^3}\right)>33.6383.

Thus \(F\) is strictly increasing. Exact rational seventh-root enclosures in the checker give

F(4.309405275)<-1.4299\cdot10^{-8}<0

and

F(4.309405276)>2.3122\cdot10^{-8}>0.

Let \(c_0\) be the unique zero. Every admissible triple has \(c\geq c_0\), and

\[ 4.309405275<c_0<4.309405276. \]

This proves the lower half of the announced bracket.

3. New exact box certificate for the upper bound

Classification: (a) for the probabilistic reduction; (d) computational-only for the finite exact enumeration.

Take the exact finite decimals

\begin{aligned} \alpha_1&=2.305174662366577,\\ \alpha_2&=3.306649716094454,\\ \alpha_3&=4.309405446418346 \end{aligned}

and log-radius

r=4\cdot10^{-12}.

Let

J=\prod_{i=1}^3[\log\alpha_i-r,\log\alpha_i+r]

with the uniform probability measure. For \(u=(u_1,u_2,u_3)\in \mathbb N_0^3\), write

X_u(\beta)=\exp(u\cdot\beta).

The checker proves, using rational Taylor bounds rather than numerical logs,

\log\alpha_1-r>0.83,\quad \log\alpha_2-r>1.19,\quad \log\alpha_3-r>1.46. \tag{3.1}

Deterministic range

If two products have additive gap below 1 and the smaller log-height is below 50, the larger log-height is less than

50+\log2<51.

By (3.1), both exponent vectors lie in the finite safe superset

\mathcal K= \{u\in\mathbb N_0^3:0.83u_1+1.19u_2+1.46u_3\leq51\}.

The exact enumeration has

|\mathcal K|=16953.

For each \(u\), its value throughout \(J\) is enclosed by exact rationals:

X_u(J)\subseteq \left[ \frac{\alpha_1^{u_1}\alpha_2^{u_2}\alpha_3^{u_3}} {U(r\lVert u\rVert_1)}, \alpha_1^{u_1}\alpha_2^{u_2}\alpha_3^{u_3} U(r\lVert u\rVert_1) \right],

where \(U(q)>e^q\) is a rational Taylor sum plus a geometric remainder. Sorting these rational intervals and checking adjacent gaps gives

\min\text{ certified gap} =1.000000084789539259\ldots>1.

The minimizing interval pair is

u=(0,0,4),\qquad v=(7,0,0),

namely the \(c^4,a^7\) comparison that also drives the lower bound.

Infinite tail

For distinct \(u,v\), let \(E_{u,v}\) be the event \(|X_u-X_v|<1\). If the smaller log-height lies in \([t,t+1)\), then

|(u-v)\cdot\beta|\leq e^{-t}.

Conditioning on a coordinate where \(u-v\neq0\) gives the slab bound

\Pr(E_{u,v})\leq e^{-t}/r.

Both exponent vectors have log-height below \(t+2\), so their number is at most

N(t+2)= \prod_{q\in\{0.83,1.19,1.46\}} \left(\left\lfloor\frac{t+2}{q}\right\rfloor+1\right).

Therefore

\Pr(\text{some collision above height 50}) \leq \sum_{t=50}^{\infty}N(t+2)^2\frac{e^{-t}}r. \tag{3.2}

The checker proves \(e^{-1}<46/125=0.368\) from the first eight Taylor terms for \(e\). It sums the resulting rational majorant through \(t=199\) and bounds the rest geometrically:

\begin{aligned} \text{finite part}&<0.835979489056085575,\\ \text{remainder}&<10^{-50},\\ \text{right side of (3.2)}&<1. \end{aligned}

Thus a positive-measure subset of \(J\) has no collision at any height. There exists a fully 1-separated three-generator semigroup in this box. The checker also proves that every point of the box is strictly increasing and has

\[ a_3<4.3094055. \]

Consequently

\[ m(3)<4.3094055. \]

The certificate proves existence in an explicit rationally described box; it does not identify a single good point of that box. This distinction is important.

4. Extension to an infinite sequence

Classification: (a) elementary-rigorous.

For completeness, here is the extension argument rather than merely invoking the page's statement.

Let \(M\) be a 1-separated semigroup generated by fixed \(a_1,\ldots,a_n>1\). Its counting function satisfies

\#\{s\in M:s\leq X\}=O((1+\log X)^n),

and, for every fixed \(m\),

\sum_{s\in M}\frac{(1+\log s)^m}{s}<\infty.

For \(R>\max(a_n,2)\), consider \(x\in[R,2R]\). For \(s,t\in M\) and \(d\geq1\), forbid

F_{s,t,d}=\{x:|sx^d-t|<1\}.

Since \(sx^d\) has derivative at least \(dsR^{d-1}\),

\operatorname{meas}(F_{s,t,d}) \leq\frac{2}{dsR^{d-1}}.

If this set is nonempty, then \(t\leq s(2R)^d+1\). Summing with the two estimates above gives

\operatorname{meas}\left(\bigcup_{s,t,d}F_{s,t,d}\right) =O((\log R)^n)=o(R).

For large \(R\), choose \(x\) outside the forbidden union. If \(x^ks\neq x^\ell t\), equal exponents reduce to the separation in \(M\); unequal exponents reduce, after factoring the smaller power, to one of the forbidden inequalities. Hence adjoining \(x\) preserves 1-separation. Iterating produces an infinite increasing sequence, and \(R\) may be chosen above any prescribed cutoff.

Applying this to the good triple from Section 3 gives an infinite sequence with three generators below \(4.3094055\). Since \(\pi(4.3094055)=2\), it is a counterexample to the literal live statement.

5. Reproduction

Standalone checker:

runs/erdos951_wavew024_reverify.py

It uses only the Python standard library. Every proof decision is made with fractions.Fraction and integer comparisons; decimal rendering is display only.

Command:

python runs/erdos951_wavew024_reverify.py

Observed output:

LOWER BARRIER
  exact lower bound for F' on [4.3,4.31]: 33.638352611383
  F(4.309405275) < -0.000000014299129267 < 0
  F(4.309405276) > 0.000000023122569012 > 0
  hence 4.309405275 < c_0 < 4.309405276
BOX
  third generator is always < 4.3094055
  certified upper endpoint: 4.309405446435583621
SMALL REGIME
  safe exponent-vector superset size: 16953
  minimum certified interval gap: 1.000000084789539259
  witness exponents: (0, 0, 4) -> (7, 0, 0)
TAIL
  finite part (t=50,...,199): 0.835979489056085575
  rigorous infinite remainder: < 1e-50
  total bad-event probability upper bound: 0.835979489056085575 < 1
RESULT
  exact checks passed
  4.309405275 < m(3) < 4.3094055

Checker SHA-256 at report time:

9947f4f6a36d1dcbeda021881b6a0b010a0996b90941c3edc2dd9a47024cbb04

6. What remains

The asymptotic version needs a uniform infinite construction or obstruction. The exact missing step is not another finite-prefix certificate: one must either

construct an infinite 1-separated system with

\(\#\{a_i\leq x\}>\pi(x)\) for arbitrarily large \(x\), or

prove an eventual counting bound from 1-separation alone.

The extension lemma is deliberately sparse and gives no control on the density or location of later generators. Therefore it cannot turn a finite violation into infinitely many violations.

Merely scaling the existing \(n\)-generator computations is also not the uniformity step. The archived \(n=7\) run checked 5,861,885 exponent vectors and reports about 844 seconds and 212 MB. At \(n=8\), a comparable simplex already suggests roughly \(10^7\)–\(2\cdot10^7\) vectors, approximately 0.5–1 core-hour and several hundred MB for one certificate with the current implementation, before candidate search. This was not run because it exceeds the few-CPU-minute budget, and even a successful \(n=8\) certificate would remain a finite partial result.

PARTIAL: Exact rational verification proves 4.309405275 < m(3) < 4.3094055 and hence a literal finite-x counterexample below 4.3094055; the asymptotic Erdős/Shapiro question remains open.

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