Erdős problem #873 — wave 7q

Access date: 2026-07-27 UTC.

Outcome

I did not solve the full problem. I obtained three independently checkable outputs.

1. [a, elementary-rigorous] For every increasing

\(A\subseteq\mathbb N\), every integer \(k\geq2\), and every real \(X\geq2\), \[ \boxed{\quad F(A,X,k)\leq k\lceil\log _2X\rceil\bigl(1+X^{\Delta_k}\bigr),\qquad \Delta_k= \begin{cases} \dfrac{k+1}{4k},&k\ \text{odd},\\[4pt] \dfrac{k}{4(k-1)},&k\ \text{even}. \end{cases}\quad} \] In particular, \[ \Delta_5=\Delta_6=\frac3{10},\qquad \Delta_7=\Delta_8=\frac27,\qquad \Delta_{11}=\Delta_{12}=\frac3{11}. \] This is stronger at the displayed finite block lengths than all numerical exponents posted in the live discussion thread.

1. [a, elementary-rigorous] Since

\(\Delta_k\downarrow1/4\), the literal inequality on the live page is true for every \(\epsilon>1/4\). The proof below handles the page's strict inequality and all \(X>0\), not merely a big-\(O\) assertion for sufficiently large \(X\). This matches, but does not cross, the \(1/4\) threshold of the April 2026 discussion note.

1. [d, computational-only, exhaustive] If

\[ M_k(X):=\max_A F(A,X,k) \] for integral \(X\), then the exact values for \(X\in\{10,20,30,40,50\}\) and \(2\leq k\leq6\) are computed in Section 4. A finite-state longest-path proof gives the upper certificates, explicit sequences give the lower certificates, and a second brute-force implementation cross-checks every case with \(X\leq12\).

The full range \(0<\epsilon\leq1/4\) remains open. Section 5 isolates a uniform divisor-clustering lemma that would suffice and explains exactly why the present argument stops at \(1/4\).

Claim labels used throughout are:

• [a] elementary-rigorous;
• [b] rigorous modulo the named source or theorem;
• [c] plausible/structural-unverified;
• [d] computational-only.

0. Mandatory live-page gate

0.1 Browser retrieval and status

[b, live-source audit] I accessed the following rendered pages through the Bright Data residential browser, not datacenter curl and not the stale tracker YAML:

• problem 873;
• LaTeX-source view;
• discussion thread.

The live problem page reported:

• status OPEN;
• 0 claimed proofs for this problem;
• Currently working on this problem: None;
• Interested in collaborating: None;
• eight comments;
• no solved or falsified marker.

Thus the mandatory stop condition did not fire.

The discussion page's counter says eight comments. The rendered thread contains eight non-deleted posts and one deleted-post placeholder. In newest-first order, the mathematical content is:

• old-bielefelder points to Letendre's arXiv:2503.12146 and says it appears

to imply the result for \(\epsilon>1/4\);

• Terence Tao asks whether that paper actually concerns #873;
• old-bielefelder links a four-page ChatGPT-derived packing proof;
• Nat Sothanaphan says an automated “standard check” found no issue;
• Ritvik Nayak links a note claiming

\[ F(A,X,11)\ll X^{223/676}\log X,\qquad F(A,X,6)\ll X^{437/1320}\log X; \]

• aditya links claims of

\[ F(A,X,6)\ll X^{22/67}\log X,\qquad F(A,X,8)\ll X^{19/58}\log X; \]

• Nat Sothanaphan says a standard check found minor issues in that

write-up;

• an October 2025 post is deleted, followed by Thomas Bloom's warning

that he had not checked its mathematics and that it had an “AI-feel.”

The thread itself warns that comments are not verified. I therefore treat all of these as leads rather than ground truth.

0.2 Verbatim current statement

The live LaTeX view gives:

Let \(A=\{a_1<a_2<\cdots\}\subseteq \mathbb{N}\) and let \(F(A,X,k)\) count the number of \(i\) such that \[ > [a_i,a_{i+1},\ldots,a_{i+k-1}] < X, > \] where the left-hand side is the least common multiple. Is it true that, for every \(\epsilon >0\), there exists some \(k\) such that \[ > F(A,X,k)<X^\epsilon? > \]

I retain the statement's literal strict inequality and its lack of an “all sufficiently large \(X\)” qualifier.

0.3 Known result listed on the page

[b, as stated by the live page] The page attributes the problem to Erdős and Szemerédi and states that, for every \(A\),

It also states that some \(A\) satisfies

for infinitely many \(X\), and adds that there may be such a sequence for every \(X\).

1. Primary-source and current-literature audit

1.1 Original source

[b] Paul Erdős, Some of my forgotten problems in number theory, Hardy–Ramanujan Journal 15 (1992), 34–50, exists. The journal PDF, printed pages 48–49, states this problem with Szemerédi and records the \(k=3\) upper and lower bounds appearing on the live page.

The optional source mode of the standalone verifier downloaded this PDF, located the relevant text, and obtained SHA-256 51faf4558eacab8e188efbcb028937f75dcb10d37865ab71ef1522df33361c72.

1.2 Letendre's actual theorem

[b] Patrick Letendre, Divisors of an Integer in a Short Interval, arXiv:2503.12146v1 (15 March 2025), exists. It defines

and its Proposition 1 proves, for \(0<\eta<\theta^2\), a bound of the shape

The paper does not mention \(F(A,X,k)\) or problem #873.

More importantly here, its Lemma 1 quotes the inequality

Section 2 below proves this inequality directly prime by prime, so the new bound does not rely on Letendre's proposition or its cited source.

The verifier's fresh download of the arXiv PDF had SHA-256

5417d762e42de27129a8f7d40ca5a3e1590484ff6cbee91e3ef9d71212a0ba88

and contained the title, Conjecture 2, Proposition 1, and the cited Corollaire 1.4.

1.3 April 2026 non-primary notes

[c as publication status; independently checked mathematics where used] The thread links A Note on the Erdős–Szemerédi LCM-Window Problem for Exponents Greater Than \(1/4\), labelled “Repaired version, 30 April 2026.” It derives the \(\epsilon>1/4\) range from Letendre's Proposition 1 by packing disjoint windows. I checked the four-page argument and found no obstruction to that partial conclusion. It is not a claimed full proof on the live page, and it explicitly stops at \(1/4\).

The linked Nayak PDF is a nine-page April 2026 note rather than an indexed paper. Its advertised exponents agree with the live comment. The elementary bound proved below dominates both of them:

Likewise it dominates the later linked numerical claims:

These four fraction identities are recomputed by the verifier.

1.4 Search result

[b, search audit] Exact-string searches for F(A,X,k), variants of “Erdős–Szemerédi LCM-window,” the original article's citations, and arXiv records found the original 1992 paper, Letendre's 2025 preprint, and the April 2026 web note. I found no additional primary paper claiming a solution or a bound for this exact problem. This is a report of the search, not a proof that no such literature exists.

I do not claim that the finite-\(k\) formula below is publication-level novel. It is a direct extraction from a prime-valuation inequality that is already present in Letendre's paper, but I did not find the formula in the sources above.

2. An elementary finite-\(k\) span inequality

2.1 Prime-valuation lemma

Lemma 2.1 [a]. Let \(d_1,\ldots,d_k\) be positive integers, let \(L=[d_1,\ldots,d_k]\), and let \(0\leq t\leq k\) be an integer. Then

Proof. Fix a prime \(p\), sort the valuations as

The \(p\)-adic valuation of the product of pairwise gcds is

Moreover,

Discarding terms with non-positive coefficient, the last expression is at most

This is precisely the required valuation inequality at \(p\). Applying it at every prime proves the lemma. \(\square\)

The verifier exhausts 23,582 instances of this valuation inequality for \(2\leq k\leq8\), \(0\leq t\leq k\), and sorted valuations in \(\{0,\ldots,5\}\). It also checks 21,000 deterministic random integer instances of the multiplicative inequality.

2.2 Consequence for \(k\) divisors in one interval

Lemma 2.2 [a]. Suppose

Then, for every integer \(0\leq t\leq k\),

Proof. Distinctness gives

Lemma 2.1 therefore implies, with \(C_k=k(k-1)/2\),

Use \(L<X\) and take the \(C_k\)-th root. \(\square\)

This one inequality includes both the usual “primal” and reciprocal-divisor span bounds. For example, \(t=1\) is the Vandermonde-type lower bound and \(t=k-1\) gives \(H\geq U^2/X\).

3. Packing the windows and optimizing exactly

3.1 Disjointness

Fix \(k\) and one residue class of start indices modulo \(k\). If \(i<j\) lie in that class, then \(j\geq i+k\), hence

Thus the numerical intervals \([a_i,a_{i+k-1}]\) belonging to that residue class are pairwise disjoint.

Now restrict their left endpoints to a dyadic range

If all corresponding spans are at least \(h\), consecutive left endpoints are \(h\)-separated inside an interval of length \(U\). There are therefore at most

such starts in the fixed residue class. This is entirely elementary.

3.2 Exact exponent

Put

For a good window, apply (2.1) to its \(k\) entries and use all \(t\in\{0,\ldots,k\}\). The exponent of \(X\) in the lower span bound is

Equations (2.1) and (3.1) bound the packing exponent by

Exact optimization [a]. Since

the maximizing integer is \(t=\lfloor k\alpha\rfloor\), with the obvious tie when \(k\alpha\) is integral. On \(\alpha\in[m/k,(m+1)/k]\),

If \(k=2r+1\), the central cell \(m=r\) has slope zero and gives

If \(k=2r\), the slopes change sign at \(\alpha=1/2\), where

These are the claimed values \(\Delta_k\). The verifier recomputes this piecewise-linear maximum with exact rational arithmetic for every \(2\leq k\leq100\).

3.3 Global theorem

Theorem 3.1 [a]. For every \(X\geq2\),

Proof. A good start has \(a_i<X\), so there are at most \(\lceil\log_2X\rceil\) relevant dyadic ranges. In each range, (3.2)–(3.3) give \(U/h\leq X^{\Delta_k}\). Equation (3.1) applies in each of the \(k\) residue classes. Summing proves the displayed bound. \(\square\)

Some exact exponents are:

3.4 Literal \(\epsilon>1/4\) consequence

Corollary 3.2 [a]. The live-page inequality is true for every \(\epsilon>1/4\), for every \(X>0\).

Proof. Choose an odd \(k\) with

Then

Theorem 3.1 gives

for every \(X\geq X_0(k,\epsilon)\).

To cover the literal finite range, replace \(k\) by an integer

A good \(K\)-window would contain a good first \(k\)-window, so \(F(A,X,K)\leq F(A,X,k)\). If \(0<X<X_0\), strict increase in \(\mathbb N\) gives

so \(F(A,X,K)=0\). This proves the strict inequality for all \(X>0\).

\(\square\)

4. Exact finite extremal computation

4.1 Finite reduction

For integral \(X\), define

where the maximum is over all infinite increasing \(A\subseteq\mathbb N\).

Finite reduction [a]. No good window can contain an entry at least \(X\). Hence only the chosen subset of \(\{1,\ldots,X-1\}\) matters. Conversely, any such finite subset can be extended by \(X,X+1,\ldots\); the extension creates no additional good window. Thus \(M_k(X)\) is the maximum local score over all subsets of \(\{1,\ldots,X-1\}\).

4.2 Exact dynamic program

[a, algorithm correctness] A state

records the last \(k-1\) selected values. Let \(D(s)\) be the largest score of an increasing selected prefix ending in \(s\). For every \(x>s_{k-1}\), the transition is

Every transition increases the last coordinate, so this is a directed acyclic graph. Initializing every state at score zero permits the selected sequence to start anywhere. Induction in the last coordinate proves that (4.1) considers every subset and returns the exact maximum.

The algorithm uses

4.3 Verified table

[d, exhaustive computation] The standalone program recomputed:

For example, at \(X=50\),

certifies \(M_2(50)\geq10\), while

certifies the four entries \(8,7,6,5\) for \(k=3,4,5,6\). The verifier checks a witness for every one of the 25 cells, not only these examples.

As an implementation-independent check, a second routine enumerates all \(2^{X-1}\) subsets and agrees with the dynamic program in all 38 applicable pairs \(2\leq X\leq12\), \(2\leq k\leq5\).

5. Exact wall and a sufficient missing lemma

5.1 Why the present machinery stops

[a, method barrier] The optimized exponent is

It tends to \(1/4\) from above and never crosses it. At the critical scale \(U=X^{1/2}\), Lemma 2.2 forces only a span of order \(X^{1/4-O(1/k)}\); packing those intervals inside a range of length \(X^{1/2}\) leaves \(X^{1/4+O(1/k)}\) possible starts.

This is an exact obstruction to the family of inequalities (2.1) plus one-window span packing. It is not an obstruction to the original problem. Crossing \(1/4\) requires either stronger divisor-cluster information for a single LCM or a global compatibility/counting argument between many windows.

5.2 A concrete sufficient lemma

For \(n\geq2\), write

Uniform short-divisor-cluster lemma [c, unproved]. For every \(0<\rho<\lambda<1/2\), there is \(C(\lambda,\rho)\) such that, uniformly for every \(n\geq2\) and \(\lambda\leq\theta\leq1-\lambda\),

This is a uniform-in-\(\theta\) version of the direction suggested by Letendre's Conjecture 2. Letendre's proved Proposition 1 has \(\theta^2-\rho\) in place of \(\theta-\rho\), which is exactly the loss that produces \(1/4\).

Implication (5.1) \(\Rightarrow\) #873 [a]. Fix a target \(\epsilon>0\), choose \(\lambda,\rho>0\) so that

and take \(k>C(\lambda,\rho)\).

For a good window, let \(L\) be its LCM, \(u\) its first entry, and write \(u=L^\theta\).

• If \(\theta<\lambda\), then \(u<X^\lambda\), giving at most

\(O(X^\lambda)\) starts.

• If \(\lambda\leq\theta\leq1-\lambda\), (5.1) forces the span to be at

least \[ L^{\theta-\rho}=uL^{-\rho}>uX^{-\rho}. \] Dyadic packing gives \(O(X^\rho)\) starts per scale.

• If \(\theta>1-\lambda\), two divisors \(d<e\) of \(L\) satisfy

\[ e-d=L\left(\frac1s-\frac1r\right)\geq\frac{d^2}{L} \] after writing \(d=L/r,e=L/s\). Thus a \(k\)-divisor window has span \(\gg_k u^{(1-2\lambda)/(1-\lambda)}\), and packing gives \(O_k(X^{\lambda/(1-\lambda)})\) starts per scale.

Summing the dyadic scales gives a power strictly below \(X^\epsilon\); the finite-\(X\) enlargement from Corollary 3.2 then gives the page's literal inequality. Hence (5.1), not another finite optimization of (2.1), is a precise sufficient missing theorem.

No finite computation can certify (5.1)'s uniform quantifiers. Extending the exact table is also combinatorially expensive: already \(X=100,k=6\) has \(\binom{99}{6}=1,120,529,256\) transitions and \(\binom{99}{5}=71,523,144\) states. I did not run that calculation.

6. Reproduction

The standalone verifier is erdos873_wave7q_reverify.py. It uses only the Python standard library for all mathematical checks:

python runs/erdos873_wave7q_reverify.py

The completed run reported:

valuation inequalities checked: 23582
integer LCM/GCD inequalities checked: 21000
Delta_k (k=2..12): 2:1/2, 3:1/3, 4:1/3, 5:3/10, 6:3/10, 7:2/7, 8:2/7, 9:5/18, 10:5/18, 11:3/11, 12:3/11
DP/brute-force cross-check cells: 38
reported exact-table cells recomputed: 25
ALL CHECKS PASSED

The measured default run took 27.18 seconds and 158,116 KiB peak RSS on this VM. The optional fresh-source audit downloads and text-checks the two primary sources and the two April 2026 linked notes:

python runs/erdos873_wave7q_reverify.py --sources

That run also passed. In addition to the two primary-source hashes recorded in Section 1, it obtained

00976e0d544578853c1e72f90a56d74323e8d6d08e1d3e586c1583acd42323d5

for the Althofer note and

27c51928d5c510be5772bdfabf0fecf1eb027700b746b92d5fed98a1b5fead04

for the Nayak note.

Finally, the live gate and all quoted thread exponents can be fetched again through the installed Bright Data browser path:

python runs/erdos873_wave7q_reverify.py --live-page

That mode also completed with live-page Bright Data checks: passed.

PARTIAL: Proved the elementary uniform bound \(F(A,X,k)\ll_k X^{\Delta_k}\log X\) with explicit \(\Delta_k\downarrow1/4\), upgraded it to the literal live-page inequality for every \(\epsilon>1/4\), and exactly computed \(M_k(X)\) for \(X\in\{10,20,30,40,50\}\), \(2\leq k\leq6\); the range \(0<\epsilon\leq1/4\) remains open behind the uniform divisor-clustering lemma (5.1).