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

Erdős problem #693 — wave w009

Accessed and computed on 2026-07-28 (UTC).

Claim labels

Every substantive mathematical claim below is labelled as requested:

[a] elementary-rigorous: proved directly here;
[b] rigorous-modulo-named-theorem: the named published/standard theorem is the only imported input;
[c] plausible/structural-unverified: heuristic or unproved;
[d] computational-only: exhaustive machine evidence, not a uniform theorem.

Bibliographic statements labelled [source-checked] were checked against the linked primary source, not inferred from a search snippet.

0. Mandatory live-page check

The live page was fetched through the Bright Data cloud-browser route, not with datacenter curl. A full-page screenshot and document.body.innerText were inspected.

Verbatim live statement

Let $k\geq 2$ and $n$ be sufficiently large depending on $k$. Let $A=\{a_1<a_2<\cdots\}$ be the set of those integers in $[n,n^k]$ which have a divisor in $(n,2n)$. Estimate \[ > \max_i a_{i+1}-a_i. > \] Is this $\leq(\log n)^{O(1)}$?

Live-page audit:

| Field | Live value | |---|---| | Status | OPEN | | Citation | [Er79e] | | Direct known-results text | none; the page only says “See also [446]” | | Comments | 0 | | Claimed proofs | 0 | | Interested in collaborating | None | | Currently working | None | | “Looks difficult” / “looks tractable” | None / None | | Formalisation markers | all None; no formal statement | | Related OEIS | A391118, marked “possible” | | Like marker | Alfaiz |

Thus no stop condition fired. In particular, the strict interval $(n,2n)$, not $(n,2n]$, is used in every proof and computation below.

Live source: Erdős Problems #693.

1. Literature and status check

[source-checked] Erdős posed the question in *Some unconventional problems

in number theory*, Astérisque 61 (1979), pp. 73–82. The question occurs on printed p. 78 and uses the strict inequalities $n<d<2n$. NUMDAM article and scan.

[source-checked] The related problem #446 concerns the asymptotic density

$\epsilon(n,2n)$ of the set of multiples. Ford proved \[ \epsilon(n,2n)\asymp \frac{1}{(\log n)^\delta(\log\log n)^{3/2}}, \qquad \delta=1-\frac{1+\log\log 2}{\log 2}=0.086071\ldots . \] This is Corollary 2 of Kevin Ford, The distribution of integers with a divisor in a given interval, Annals of Mathematics 168 (2008), 367–433. Primary paper. This determines average density, not maximal local gaps. [b]

[source-checked] Gérald Tenenbaum revisited the problem in 2013. He called

it a “deep open question” and wrote, for the endpoint-modified set $M((n,2n])$, \[ M_n(x)=\epsilon_n x+R_n(x),\qquad a_{i+1}-a_i= \frac{1-R_n(a_{i+1})+R_n(a_i)}{\epsilon_n}. \] He therefore isolates short differences of $R_n$, not its average or its global size, as the issue. See p. 18 of Some of Erdős’ unconventional problems in number theory, thirty-four years later, Bolyai Society Mathematical Studies 25 (2013), 651–681, DOI 10.1007/978-3-642-39286-3_23, author PDF. The endpoint change affects the multiples set by at most the progression $2n\mathbb N$, of density $1/(2n)$, so it does not change Ford's density order; it can matter for individual finite gaps. [a+b]

[source-checked] Ford's 2008 Theorem 2 does give a short-interval

asymptotic, but only for interval length $\Delta\geq x/\log^{10}z$. At $x\asymp n^k$ this is vastly longer than a power of $\log n$, so it does not answer #693. [b]

[source-checked] Nearby recent work does not have the required restricted

set. Kowalski–Kuperberg exactly determine the gaps in the full $N\times N$ multiplication table, not the products with one factor in $(n,2n)$; see The gaps in the multiplication table (primary PDF, originating as arXiv:2405.02651). Chan's July 2026 paper studies counts of consecutive pairs in full tables and certain multiplication rectangles, not uniform maximal gaps in this dyadic divisor set; see the journal abstract.

[source-checked] OEIS A391118, created 2025-12-28, is exactly the

$k=2$, strict-endpoint sequence. On the access date it lists only $3\leq n\leq83$. OEIS A391118.

I searched the exact wording, the discrepancy notation from Tenenbaum, citations to the 1979 and 2013 papers, divisor-in-short-interval literature, and recent multiplication-table-gap papers. I found no primary source claiming a solution or a polylogarithmic maximal-gap bound for this exact problem. This is a report of the search, not a proof that no such source exists.

2. Exact reformulation

Put

D_n=\{n+1,n+2,\ldots,2n-1\},\qquad \mathcal A_n=\bigcup_{d\in D_n}d\mathbb N,

and let $G_k(n)$ be the largest internal consecutive gap of $\mathcal A_n\cap[n,n^k]$. Then

\mathcal A_n\cap[n,n^k] =\{qd:n<d<2n,\ q\geq1,\ qd\leq n^k\}. \tag{2.1}

This is the finite multiplication-rectangle description used by the checker. [a]

Define the representation-counting floor sum

F_n(X)=\sum_{d=n+1}^{2n-1}\left\lfloor\frac Xd\right\rfloor . \tag{2.2}

For integers $X,H\geq0$,

F_n(X+H)-F_n(X) =\sum_{d=n+1}^{2n-1} \left(\left\lfloor\frac{X+H}{d}\right\rfloor -\left\lfloor\frac Xd\right\rfloor\right). \tag{2.3}

Consequently,

F_n(X+H)-F_n(X)>0 \quad\Longleftrightarrow\quad (X,X+H]\cap\mathcal A_n\ne\varnothing . \tag{2.4}

Multiplicity in $F_n$ is harmless because only positivity is used. [a]

Let

S_n=\sum_{d=n+1}^{2n-1}\frac1d,\qquad \psi(u)=\{u\}-\frac12,\qquad \Psi_n(X)=\sum_{d=n+1}^{2n-1}\psi(X/d).

Since $\lfloor u\rfloor=u-\psi(u)-1/2$, (2.3) becomes the exact identity

F_n(X+H)-F_n(X) =H S_n-\{\Psi_n(X+H)-\Psi_n(X)\}. \tag{2.5}

Also

S_n\geq\frac{n-1}{2n}\geq\frac13\qquad(n\geq3). \tag{2.6}

Equations (2.4)–(2.5) isolate the required local, one-sided discrepancy increment exactly. [a]

3. A rigorous sublinear bound for $k=2$

Theorem

\boxed{G_2(n)\ll n^{2/3}.} \tag{3.1}

This result is [b] rigorous modulo the standard Erdős–Turán inequality and van der Corput second-derivative estimate, both stated in the proof. I did not find (3.1) explicitly recorded in the sources above, but do not claim novelty.

Low part: a direct next multiple

Let $2n\leq X\leq n^2$, put

q=\left\lfloor\frac Xn\right\rfloor,\qquad d=\left\lfloor\frac Xq\right\rfloor+1.

Then $2\leq q\leq n$,

n<d<2n,\qquad X<qd\leq X+q. \tag{3.2}

Indeed $qn\leq X<(q+1)n$, so $d\geq n+1$, while $d\leq n+\lceil n/q\rceil\leq2n-1$. Thus, whenever $X\leq n^{5/3}$, the next member of the unrestricted multiples set is at distance at most

q\leq X/n\leq n^{2/3}. \tag{3.3}

The initial block $n+1,\ldots,2n-1$ is consecutive, and its next guaranteed member $2(n+1)$ is only 3 later. For an internal gap, if the constructed multiple lies beyond $n^2$, the presumed next endpoint would lie still farther and hence would not exist. This proves the required bound below $n^{5/3}$. [a]

High part: a dyadic sawtooth estimate

For $n^{5/3}\leq X\leq n^2$, claim

\Psi_n(X)\ll n^{2/3}. \tag{3.4}

The Erdős–Turán Fourier inequality says that for points $x_j$ and an integer $J\geq1$,

\left|\sum_j\psi(x_j)\right| \ll \frac{\#\{j\}}J+ \sum_{1\leq h\leq J}\frac1h \left|\sum_j e(hx_j)\right|, \quad e(u)=e^{2\pi i u}. \tag{3.5}

For $f(t)=hX/t$ on $n<t<2n$,

|f''(t)|\asymp \frac{hX}{n^3}.

The van der Corput second-derivative estimate

\sum_{n<d<2n}e(f(d)) \ll n\lambda^{1/2}+\lambda^{-1/2} \quad\text{when }|f''|\asymp\lambda \tag{3.6}

therefore yields

\left|\sum_{n<d<2n}e(hX/d)\right| \ll \sqrt{\frac{hX}{n}}+ \sqrt{\frac{n^3}{hX}}. \tag{3.7}

Choose $J=\lfloor nX^{-1/3}\rfloor$. Substitution in (3.5), using $\sum_{h\leq J}h^{-1/2}\ll\sqrt J$ and $\sum_{h\leq J}h^{-3/2}\ll1$, gives

\begin{aligned} |\Psi_n(X)| &\ll \frac nJ+ \sqrt{\frac Xn}\sum_{h\leq J}h^{-1/2} \sqrt{\frac{n^3}{X}}\sum_{h\leq J}h^{-3/2}\\ &\ll X^{1/3}+\sqrt{\frac{n^3}{X}} \ll n^{2/3}, \end{aligned}

which proves (3.4). [b]

Now let $a<b\leq n^2$ be consecutive members of $\mathcal A_n$, with $a\geq n^{5/3}$. If $b-a>Cn^{2/3}$, take an integer $H\asymp Cn^{2/3}$ with $a+H<b$. By (2.5), (2.6), and (3.4),

F_n(a+H)-F_n(a) =H S_n+O(n^{2/3})>0

for a sufficiently large absolute $C$. Equation (2.4) then puts a member of $\mathcal A_n$ strictly between $a$ and $b$, a contradiction. Together with (3.3), this proves (3.1). [b]

This is genuinely sublinear but still much larger than a polylogarithm.

4. Exact finite computation

The standalone checker is erdos693_wavew009_verify.py.

For each $d=n+1,\ldots,2n-1$, it marks exactly the byte positions

d,2d,3d,\ldots,\left\lfloor n^k/d\right\rfloor d.

Thus a byte is marked if and only if its index satisfies the live statement. Sorting the marked indices and taking adjacent differences computes $G_k(n)$ without factoring or sampling. [a, algorithm correctness]

The core marking code is:

limit = n**k
represented = bytearray(limit + 1)
for d in range(n + 1, 2*n):
    count = (limit - d) // d + 1
    represented[d:limit + 1:d] = b"\x01" * count
indices = np.flatnonzero(np.frombuffer(represented, dtype=np.uint8))
differences = np.diff(indices)

An independent small-case path enumerates every factor pair $(q,m/q)$ for every $m$, tests the strict interval, and agrees with the marker for:

$k=2,\ 3\leq n\leq83$;
$k=3,\ 3\leq n\leq25$;
$k=4,\ 3\leq n\leq12$.

The $k=2$ values agree term-for-term with every currently listed term of OEIS A391118. [d]

Exhaustive sharp bounds in concrete regimes

The SHA-256 input is the ASCII string of comma-separated values $G_k(3),G_k(4),\ldots,G_k(N)$, with no trailing comma.

| $k$ | exhaustive $n$-range | sharp maximum in range | all $n$ attaining it | first certified endpoints | SHA-256 | |---:|---:|---:|---|---|---| | 2 | $3\ldots2000$ | 30 | 811–848, 1699, 1811–1863 | $495520,495550$ at $n=811$ | 4c3ce446efd1f56f2685b98102d4005ca63722e52469edcfeeab827f370d9632 | | 3 | $3\ldots300$ | 31 | 272 | $5207165,5207196$ | e6d15218b5723a808b1361ffb9bc45a17915cc0c8089c4f0d98d1895a43f13e3 | | 4 | $3\ldots100$ | 27 | 85, 92, 95–98 | $25744965,25744992$ at $n=85$ | 023741da38d440bb77f3a53db54a9dcd551ca814b94f3df3c7653a5a0cf2c47c |

All three rows are [d] computational-only. They are exact finite certificates, not evidence of a uniform bound in $n$.

For the first maximum in each row, a separate factor-pair pass found:

| $(k,n)$ | left endpoint target divisors | right endpoint target divisors | every strict interior integer | |---|---|---|---| | (2,811) | 815, 1304, 1520 | 850, 901, 935, 1166, 1325 | no target divisor | | (3,272) | 515 | 293 | no target divisor | | (4,85) | 149 | 91, 96, 98, 104, 112, 147, 156, 168 | no target divisor |

These are [d] independently recomputed certificates.

For reference, the successive record increases for $k=2$ are:

| first $n$ | record gap | first endpoints | |---:|---:|---:| | 3 | 3 | 5, 8 | | 7 | 4 | 40, 44 | | 11 | 5 | 85, 90 | | 12 | 6 | 120, 126 | | 21 | 8 | 352, 360 | | 41 | 9 | 1431, 1440 | | 43 | 10 | 770, 780 | | 69 | 12 | 4200, 4212 | | 89 | 13 | 5782, 5795 | | 97 | 15 | 7755, 7770 | | 173 | 16 | 17120, 17136 | | 197 | 17 | 14365, 14382 | | 221 | 18 | 14364, 14382 | | 277 | 20 | 66470, 66490 | | 426 | 22 | 180648, 180670 | | 453 | 25 | 159904, 159929 | | 713 | 29 | 495521, 495550 | | 811 | 30 | 495520, 495550 |

This table is [d].

Reproduction log

On Python 3.12.3 with NumPy 2.4.4:

$ python -u runs/erdos693_wavew009_verify.py --full
structural identities: PASS
factor-pair cross-check k=2, n=3..83: PASS
factor-pair cross-check k=3, n=3..25: PASS
factor-pair cross-check k=4, n=3..12: PASS
OEIS A391118 n=3..83: exact match
certificate k=2, n=811: gap 30 ...: PASS
certificate k=3, n=272: gap 31 ...: PASS
certificate k=4, n=85: gap 27 ...: PASS
FULL k=2, n=3..2000: ... sha256=4c3ce4...9632: PASS
FULL k=3, n=3..300:  ... sha256=e6d152...13e3: PASS
FULL k=4, n=3..100:  ... sha256=023741...c47c: PASS
ALL REQUESTED CHECKS PASSED

Measured sweep times were 28.5 s, 27.3 s, and 32.1 s, respectively. [d]

5. Exact remaining obstruction

From (2.5), a sufficient uniform polylogarithmic result would be the following one-sided shrinking-target estimate: for some absolute $C$, with $H=(\log n)^C$,

\Psi_n(X+H)-\Psi_n(X)<H S_n \tag{5.1}

for every relevant $X\leq n^k-H$ (or just for $X=a_i$, as in Tenenbaum's reduction). By (2.4), (5.1) says exactly that the next interval contains a target multiple. [a, reduction]

The proof in §3 controls each $\Psi_n(X)$ only by $O(n^{2/3})$ in the $X\leq n^2$ regime. For polylogarithmic $H$, the main term $H S_n\asymp H$ is swamped by that error. Ford's density theorem controls an average over long ranges; his cited short-interval theorem still requires length essentially $x/\log^{10}n$. Neither supplies (5.1). [b]

There is also a useful warning against dropping the polynomial cutoff. Let

L_n=\operatorname{lcm}(n+1,n+2,\ldots,2n-1).

Every $d\in D_n$ divides $L_n$. If $1\leq t\leq n$ and some $d\in D_n$ divided $L_n+t$, then $d\mid t$, impossible because $0<t<d$. Hence the unrestricted periodic multiples set has a gap of at least $n+1$ immediately after $L_n$. [a] On the other hand, the prime number theorem gives

\log L_n\geq\sum_{n<p<2n}\log p\sim n,

so $L_n>n^k$ for every fixed $k$ and all sufficiently large $n$. Thus this easy large gap occurs exponentially too late to refute #693. [b, modulo PNT]

Finally, a finite sweep cannot address the required uniformity. The present $k=2$ algorithm has empirical cubic total cost in the endpoint $N$: scaling the measured 28.5 s at $N=2000$ predicts about 1.0 core-hour for all $n\leq10^4$, and about 990 core-hours for all $n\leq10^5$, before the large index arrays become the dominant memory problem. At a representative $\$0.05$ per core-hour this is roughly $\$0.05$ and $\$50$, respectively, excluding high-memory premiums. These are extrapolations for this simple verifier, not lower bounds for better algorithms. [c+d]

The exact missing ingredient is therefore (5.1), or another argument proving the same local non-emptiness, uniformly on the polynomial range. Density, global discrepancy, and additional finite computation do not provide that uniformity.

PARTIAL: For the strict live-page problem, $G_2(n)\ll n^{2/3}$ follows from standard Erdős–Turán/van der Corput bounds, the exact remaining one-sided discrepancy condition is isolated, and exhaustive independently checked maxima are certified for $k=2,n\leq2000$, $k=3,n\leq300$, and $k=4,n\leq100$; the polylogarithmic bound remains open.

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