ERDŐS/DAILY ▸

← back to the ledger

ERDőS #873 · PARTIAL

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.

2. [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.

3. [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:

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:

The live problem page reported:

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:

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

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

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

write-up;

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

> 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) \]

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\),

\[ F(A,X,3)\ll X^{1/3}\log X. \]

It also states that some \(A\) satisfies

\[ F(A,X,3)\gg X^{1/3}\log X \]

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

\[ D_n(Y,H)=\#\{d\mid n:Y\leq d\leq Y+H\} \]

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

shape

\[ D_n(n^\theta,n^{\theta^2-\eta}) \ll \frac{\theta(1-\theta)}{\eta} +\frac1{\theta(1-\theta)}. \]

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

More importantly here, its Lemma 1 quotes the inequality

\[ [d_1,\ldots,d_k]^{t(t+1)/2} \prod_{rSection 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:

\[ \frac{437}{1320}-\frac3{10}=\frac{41}{1320}>0,\qquad \frac{223}{676}-\frac3{11}=\frac{425}{7436}>0. \]

Likewise it dominates the later linked numerical claims:

\[ \frac{22}{67}-\frac3{10}=\frac{19}{670}>0,\qquad \frac{19}{58}-\frac27=\frac{17}{406}>0. \]

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

\[ L^{T_t}\prod_{1\leq rProof. Fix a prime \(p\), sort the valuations as

\[ 0\leq x_1\leq\cdots\leq x_k=M. \]

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

\[ \sum_{rMoreover,

\[ t\sum_{j=1}^k x_j-\sum_{j=1}^k(k-j)x_j =\sum_{j=1}^k(t-k+j)x_j. \]

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

most

\[ (1+2+\cdots+t)M=T_tM. \]

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

\[ U\leq d_1<\cdotsThen, for every integer \(0\leq t\leq k\),

\[ \boxed{\quad H\geq U^{\,2t/(k-1)} X^{-t(t+1)/(k(k-1))}. \quad} \tag{2.1} \]

Proof. Distinctness gives

\[ (d_r,d_s)\leq |d_s-d_r|\leq H. \]

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

\[ L^{T_t}H^{C_k}\geq U^{kt}. \]

Use \(L

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 \[ a_{i+k-1}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

\[ U\leq a_i<2U. \]

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

\[ 1+\frac Uh \tag{3.1} \]

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

3.2 Exact exponent

Put

\[ \alpha=\frac{\log U}{\log X}\in[0,1]. \]

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

\[ b_{k,t}(\alpha) =\frac{2kt\alpha-t(t+1)}{k(k-1)}. \]

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

\[ \psi_k(\alpha) :=\alpha-\max_{0\leq t\leq k}b_{k,t}(\alpha). \tag{3.2} \]

Exact optimization [a]. Since

\[ b_{k,t+1}(\alpha)-b_{k,t}(\alpha) =\frac{2k\alpha-2(t+1)}{k(k-1)}, \]

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]\),

\[ \psi_k(\alpha) =\alpha\left(1-\frac{2m}{k-1}\right) \frac{m(m+1)}{k(k-1)}. \tag{3.3} \]

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

\[ \max_{0\leq\alpha\leq1}\psi_k(\alpha) =\frac{k+1}{4k}. \]

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

\[ \max_{0\leq\alpha\leq1}\psi_k(\alpha) =\frac{k}{4(k-1)}. \]

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\),

\[ F(A,X,k)\leq k\lceil\log_2X\rceil\bigl(1+X^{\Delta_k}\bigr). \]

Proof. A good start has \(a_i

\(\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:

| \(k\) | \(2\) | \(3,4\) | \(5,6\) | \(7,8\) | \(9,10\) | \(11,12\) |

|---:|---:|---:|---:|---:|---:|---:|

| \(\Delta_k\) | \(1/2\) | \(1/3\) | \(3/10\) | \(2/7\) | \(5/18\) | \(3/11\) |

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

\[ k>\frac1{4\epsilon-1}. \]

Then

\[ \Delta_k=\frac14+\frac1{4k}<\epsilon. \]

Theorem 3.1 gives

\[ F(A,X,k)\ll_k X^{\Delta_k}\log Xfor every \(X\geq X_0(k,\epsilon)\).

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

\[ K\geq\max\{k,\lceil X_0\rceil\}. \]

A good \(K\)-window would contain a good first \(k\)-window, so

\(F(A,X,K)\leq F(A,X,k)\). If \(0

\(\mathbb N\) gives

\[ a_{i+K-1}\geq i+K-1\geq K\geq X_0>X, \]

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

\[ M_k(X)=\max_A F(A,X,k), \]

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

\[ s=(s_1,\ldots,s_{k-1}) \]

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

\[ D(s_2,\ldots,s_{k-1},x) \leftarrow \max\left( D(s_2,\ldots,s_{k-1},x),\ D(s)+\mathbf1_{[s_1,\ldots,s_{k-1},x]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

\[ \Theta\!\binom{X-1}{k} \quad\text{transitions and}\quad O\!\binom{X-1}{k-1} \quad\text{states}. \]

4.3 Verified table

[d, exhaustive computation] The standalone program recomputed:

| \(X\) | \(M_2(X)\) | \(M_3(X)\) | \(M_4(X)\) | \(M_5(X)\) | \(M_6(X)\) |

|---:|---:|---:|---:|---:|---:|

| 10 | 3 | 2 | 1 | 0 | 0 |

| 20 | 6 | 4 | 3 | 2 | 1 |

| 30 | 7 | 6 | 5 | 4 | 3 |

| 40 | 9 | 7 | 6 | 5 | 4 |

| 50 | 10 | 8 | 7 | 6 | 5 |

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

\[ (1,2,3,4,5,6,8,12,16,24,48) \]

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

\[ (1,2,3,4,6,8,12,16,24,48) \]

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

\[ \Delta_k= \begin{cases} \frac14+\frac1{4k},&k\text{ odd},\\[3pt] \frac14+\frac1{4(k-1)},&k\text{ even}. \end{cases} \]

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

\[ D_n(Y,H)=\#\{d\mid n:Y\leq d\leq Y+H\}. \]

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\),

\[ D_n(n^\theta,n^{\theta-\rho})\leq C(\lambda,\rho). \tag{5.1} \]

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

\[ \max\left\{\lambda,\rho,\frac{\lambda}{1-\lambda}\right\} <\epsilon, \]

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

\(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-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).

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