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

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