Erdős problem #684 — wave 6j

Access date: 2026-07-27 UTC.

Outcome

The problem is not closed here. I obtained three verifiable outputs:

1. [A: elementary-rigorous] A specific Fourier estimate used in Ji Ho

Bae's April 2026 preprint arXiv:2604.23784 is false. In the notation of that paper, Lemma 18 claims that the normalized \(L^1\)-mass of the top-band full-conductor modes is \(O_C(p^{-1-\eta_C})\). For the paper's own local set, the single mode \(a=1\) is at least \(1/(16p)\) along an infinite family. Thus the preprint does not currently prove its claimed \(\limsup f(n)/\log n=\infty\). This does not disprove that conclusion; it breaks the supplied proof.

1. [A: elementary-rigorous] For the useful seed

\(L_M=\operatorname{lcm}(1,\ldots,M)\), I give a closed formula for every \(p\)-adic valuation of \(\binom{L_M-1}{k}\) when \(k\leq M\). It reduces testing \(f(L_M-1)>M\) to one explicit product of local residues.

1. [D: computational-only] A from-scratch, doubly checked computation

gives the exact isolated value \[ f(\operatorname{lcm}(1,\ldots,150)-1)=924. \] Here \[ \operatorname{lcm}(1,\ldots,150)-1 =4963595372164418730243844250278933730416682962970482173955823999 \] and \[ \frac{924}{\log n}=6.300071969293612\ldots. \] The same checker recomputes the complete record table through \(n=100000\).

Claim labels used below are:

• [A] elementary-rigorous;
• [B] rigorous modulo the explicitly named theorem(s);
• [C] plausible or structural but unverified;
• [D] computational-only.

0. Mandatory live-page gate

I fetched the rendered live page through the Bright Data residential browser, expanded the discussion thread, and then selected “Show 1 more comments” so that all 27 comments were visible. I did not use the stale YAML as a statement source.

Live-page state:

• status: OPEN;
• claimed proofs: 0;
• “Currently working on this problem”: None;
• “Interested in collaborating”: None;
• page last edited: 01 April 2026;
• comments displayed: 27.

Therefore the mandatory stop condition did not fire.

Verbatim live statement

The site's LaTeX-source view at <https://www.erdosproblems.com/latex/684> gives:

For \(0\leq k\leq n\) write \[ > \binom{n}{k} = uv > \] where the only primes dividing \(u\) are in \([2,k]\) and the only primes dividing \(v\) are in \((k,n]\).

Let \(f(n)\) be the smallest \(k\) such that \(u>n^2\). Give bounds for \(f(n)\).

The natural precise definition used below is

with \(f(n)=0\) in finite tables if no such \(k\) exists.

Results and activity listed on the live page

The page itself lists the following.

• [B] Mahler's theorem: for fixed \(\epsilon,k,\ell\), the

\(\ell\)-smooth part \(a\) of \((n+1)\cdots(n+k)\) is \(<n^{1+\epsilon}\) for all sufficiently large \(n\). It implies \(f(n)\to\infty\), but ineffectively.

• [B] Tang and ChatGPT:

\[ f(n)\leq n^{30/43+o(1)}. \] The same method gives \(n^{2/3+o(1)}\) under RH or the Density Hypothesis.

• [C] The Sothanaphan–ChatGPT heuristic predicts

\(f(n)\sim2\log n\) for at least most \(n\).

• [B] Alexeev–Putterman–Sawhney–Sellke–Valiant (APSSV):

\[ f(n)\leq \left(\frac{24}{\pi^2-6}+o(1)\right)(\log n)^2 \leq 6.20219(\log n)^2, \] and there are arbitrarily large \(n\) with \(f(n)\geq(1/2-o(1))\log n\).

• The page also asks about the analogous threshold \(f(n,k)\) obtained by

varying the smoothness cutoff for one fixed binomial coefficient.

The mathematical content of the 27 comments, after expanding the entire thread, is as follows.

• [D, comment only] Tomás Oliveira e Silva reports an exhaustive

computation for every \(n\leq e^{30.1}\), with binned plots and a modest excess of prime values of \(f(n)\). No checker or raw table was attached in the rendered comment, so I did not independently certify this very large computation.

• [C] A 27 April comment links Bae's “Unbounded logarithmic limsup”

preprint. Section 4 below gives a concrete disproof of one lemma in that proof.

• [B] Tao explains the APSSV method: if

\(n\bmod p\geq p-A\), then \(p\mid(n+1)\cdots(n+A)\). Counting these exceptional primes loses a factor \(\log n\), leading naturally to the \((\log n)^2\) bound. Tao suggests that averaging over \(n\) should remove most of this loss.

• [C/B as stated in the linked note] Sothanaphan reports an

almost-all upper bound \[ f(n)\leq\left(\frac4{1-\gamma}+o(1)\right)\log n =(9.461\ldots+o(1))\log n. \]

• [B] Tang's original note proves \(n^{12/17+\epsilon}\); comments

explain that Guth–Maynard's \(17/30\) short-interval exponent upgrades the same calculation to \(30/43\). Bloom and Tao report checking that argument. They also note that this route is capped near exponent \(1/2\).

• [C] The heuristic computation in the comments writes the large-prime

part as a carry sum, predicts \(\log v=k\log(n/k)+o(k)\), and hence predicts a crossing at \(k\sim2\log n\). Follow-up numerics suggested possible limiting lower and upper ratios near \(1\) and \(8\), with a random-walk value \(7.88\ldots\) proposed for the latter. These are explicitly heuristics, not theorems.

• [C, incomplete] An attempted \(O(\log n\log\log n)\) proof reduces

to an unproved equidistribution assertion for \(\{n/p\}\). Bloom and Sothanaphan point out that the assertion is not justified and is not expected pointwise.

• The remaining comments discuss provenance and auditing of the

AI-assisted arguments. The page warns that comments are not verified for correctness.

1. Primary-source literature audit

I searched exact-title and exact-statement variants, arXiv, the original Erdős archive, and the sources linked by the live page. The following are the relevant primary sources I found.

Original source

[A: citation verification] The original problem occurs in Paul Erdős, “Some unconventional problems in number theory,” Acta Mathematica Academiae Scientiarum Hungaricae 33 (1979), 71–80. The scan is <https://combinatorica.hu/~p_erdos/1979-23.pdf>. On the printed pages 76–77 Erdős defines \(A(n)\) as the least \(k\) for which the small-prime part exceeds \(n^2\), says Mahler implies \(A(n)\to\infty\), and asks how fast. SHA-256 of the downloaded PDF:

a4703a104adcbbde0ed605c9ff81379adee8b7ceda3714ea455b5b68ae720dfd

This also catches a bibliographic problem in Bae's preprint: its reference label points instead to a different 1994 journal item. The 1979 Acta paper above is the source used by the live page, APSSV, Tang, and Li.

Tang and the short-interval input

[B] Quanyu Tang, “A note on Erdős problem 684,” is present at <https://github.com/QuanyuTang/erdos-problem-684-note>. Its Theorem 1.2 is \(f(n)\leq n^{12/17+\epsilon}\). SHA-256 of the checked PDF:

9ee917877b45efa74d37e0abeab77268a37d777305c1dd0c99393af225b8b1bb

[B] Guth and Maynard, arXiv:2405.20552v2, explicitly obtain prime asymptotics in intervals of length \(x^{17/30+o(1)}\). Tang's general exponent conversion is

substituting \(\theta=17/30\) gives \(\alpha=30/43\). Substituting the RH/Density-Hypothesis value \(\theta=1/2\) gives \(2/3\).

APSSV

[B: modulo PNT] Alexeev, Putterman, Sawhney, Sellke, and Valiant, arXiv:2603.29961v2, exists and its Theorem 2.1 says exactly

and constructs \(n_j\) for which

The lower seed is

and \(\log M_K=2K+o(K)\). I checked the full source proof and independently recomputed its Kummer identities and constant. SHA-256 of the arXiv source archive:

9dbacb1d6a7585d5ac2a4a0cb05de080a3e6b2a47bdbae1ab6fde3553fdc2737

Two papers newer than the page's 1 April edit

1. [C as a conclusion; proof refuted below] Ji Ho Bae,

arXiv:2604.23784, claims \[ \limsup_{n\to\infty}\frac{f(n)}{\log n}=\infty. \] The identifier, author, and manuscript are real. The proof is not valid as written because Lemma 18 is false. Source-archive SHA-256:

   5165eed9da06a972c826c7c006b11e51b27dd3637ed2a1be009745783ab3850b
   

1. **[B: modulo PNT, the Mertens–von Mangoldt estimate, and standard

probability inequalities]** Eric Li, arXiv:2606.08216, proves the density-one result \[ f_c(n)=\left(\frac{c}{1-\gamma}+o(1)\right)\log n \quad\text{for almost all }n. \] Thus for the threshold in #684, \[ f(n)=\left(\frac2{1-\gamma}+o(1)\right)\log n =(4.730544237\ldots+o(1))\log n \] for almost all \(n\). This is not a pointwise result and does not settle the worst case. Its exact complete-residue mean identity is \[ m(k)= \sum_{p\leq k}\log p\sum_{a\geq1}\frac{[k]_{p^a}}{p^a} = k\sum_{p\leq k}\frac{\log p}{p-1}-\log(k!) =(1-\gamma)k+o(k). \] The paper also proves a centered Gaussian fluctuation theorem. I read the complete source and found no break in the normal-order proof; unlike Bae's argument, its finite-period fourth-moment reduction can be checked directly. Source-archive SHA-256:

   5d0f3888ad0d8017fd8af67f07320d27f302dd577d25e511f3db648c1bc9c341
   

No other exact-match primary paper specifically about problem 684 appeared in the searches. OEIS A392019 exists, but as of access it contains only the initial terms through \(n=73\).

2. Exact carry formula

For a prime \(p\), Legendre's formula gives the elementary identity

where \([x]_q\) is the least nonnegative residue. [A] The second equality follows by writing \(n=qN+r\), \(k=qK+s\); the floor difference is one exactly when \(s>r\). All sums are finite.

The checker implements both lines of (2.1) separately and compares them on 272,974 small cases and on every \(p\leq k\leq924\) used in the large certificate.

3. A closed reduction for the \(L_M-1\) seed

Let

For \(p\leq M\), define

Proposition

[A] For every \(p\leq k\leq M\),

Consequently \(u(L_M-1,k)\) is nondecreasing for \(0\leq k\leq M\), and

Proof

Put \(n=L-1\). At every level \(a\leq\alpha_p\),

so (2.1) has no carry.

At a higher level write \(a=\alpha_p+b\), \(b\geq1\), and put

Because \(p^{\alpha_p+1}>M\geq k\), one has \([k]_{p^{\alpha_p+b}}=k\), while

Thus a carry occurs exactly when

Every \(s_b\) is congruent to \(r_p\pmod p\). If \(r_p>h\), there are no such \(b\). If \(r_p\leq h<p\), then \(s_b\leq h\) is equivalent to \(s_b=r_p\), which is equivalent to

The number of such \(b\) is exactly \(\nu_p(U_p-r_p)\), proving (3.1). The indicator in (3.1) can only switch from zero to one as \(k\) increases, and new primes only add factors, proving monotonicity and (3.2).

The standalone checker compares (3.1) to Legendre's formula in 3,627 cases for \(M=30,50,150\).

What this reduction isolates

An asymptotic improvement of the APSSV lower constant from \(1/2\) to \(1\) would follow if one could prove for infinitely many \(M\) that

The obstruction is now exact: it is the simultaneous \(p\)-adic closeness of \(U_p=L_M/p^{\alpha_p}\) to its first base-\(p\) digit \(r_p\). The computation below verifies (3.3) for the displayed \(M=150\), but it gives no uniformity in \(M\), so I do not promote it to an asymptotic theorem.

4. A false lemma in the claimed unbounded-limsup proof

Bae's Lemma 18 (“Non-prefix Fourier tails”) asserts, for a top-band prime \(M<p\leq K\), that

for some \(\eta_C>0\). The Fourier transform in the paper is normalized by \(p^{-2}\), so the displayed ratio equals the absolute unnormalized exponential sum divided by \(|A_p|\).

I now give a counterexample using exactly the paper's definitions.

Take

for any prime \(p\geq17\). The paper's required choice of \(\theta\) is valid because

Here \(\alpha_p=0\), \(\beta_p=2\), \(B_p=2\), and the local set is

where

Let

Then \(A_p=B\setminus E\).

Write \(e(x)=\exp(2\pi ix)\). At the full-conductor mode \(a=1\), the complete residue classes in \(B\) cancel:

Therefore

The set \(E\) contains \(\lceil3p/4\rceil,\ldots,p-1\), so

Every phase in (4.3) has argument between \(0\) and \(4\pi/p\). Using \(\pi<22/7\) and \(\cos x\geq1-x^2/2\), for \(p\geq17\) its real part is greater than \(1/2\). Hence

Since \(|A_p|\leq p^2\),

The left side of (4.1) contains the \(a=1\) term, while \(p^{-1}/16\) is not \(O(p^{-1-\eta_C})\) along the infinitely many primes. This proves that Lemma 18 is false.

The checker also evaluates (4.3) numerically as a corroboration:

The rational lower bound (4.4), not the floating-point table, is the disproof. The preprint uses Lemma 18 to discard every mode with a full-conductor coordinate before its final Fourier assembly. Since that discard is invalid, its Proposition 1 (the short-multiplier sieve) and hence its unbounded-limsup corollary are not established. A future repair would need cancellation in the global Fourier sum after the metric kernel is included; a local absolute \(L^1\) estimate of the asserted strength is impossible.

5. Exact computation

The standalone checker is runs/erdos684_wave6j_reverify.py. Run:

python runs/erdos684_wave6j_reverify.py

It uses only the Python standard library and took 11.7 seconds on this VM. No comparison deciding \(u(n,k)>n^2\) uses floating point.

Independent algorithms

For the special 64-digit input, every valuation is computed twice:

def valuation_kummer(n, k, p):
    q, value = p, 0
    while q <= n:
        value += (n % q < k % q)
        q *= p
    return value

def valuation_legendre(n, k, p):
    q, value = p, 0
    while q <= n:
        value += n // q - k // q - (n-k) // q
        q *= p
    return value

The actual file includes overflow-safe loop guards. It checks every \(2\leq k\leq924\), multiplies exact Python integers \(\prod_{p\leq k}p^{\nu_p}\), and finds:

• for every \(k\leq923\), \(u(n,k)\leq n^2\);
• the largest pre-crossing \(u\) occurs at \(k=902\), where the exact

ratio satisfies \(n^2/u=15.438698677\ldots\);

• at \(k=924\), \(u/n^2=8280.830136477\ldots>1\).

Thus [D]

The factorization of the crossing value \(u(n,924)\), recomputed by both routes, is

For the range \(n\leq100000\), the checker uses a second algorithm. It updates

by factoring the numerator and denominator with a smallest-prime-factor sieve, maintains all valuations, and maintains only the factors whose primes are at most the current \(k\). It cross-checks the prefix \(n\leq240\) against the Kummer implementation.

The inputs with no crossing in this range are exactly

The successive records of \(f(n)\) through \(100000\) are:

This small table is far below the \(e^{30.1}\) computation reported in the comments; its purpose is reproducibility and cross-validation. The structured \(L_{150}-1\) example has \(\log n=146.665\ldots\), so it lies well beyond that exhaustive interval.

6. Exact remaining wall

The pointwise state supported by verified sources is

Li's theorem determines the density-one scale \((2/(1-\gamma))\log n\), but does not control the exceptional integers.

There are now two precise possible fronts.

1. Upper-bound front. APSSV's argument bounds the number of primes

\(p\asymp Y\) for which \(n\bmod p\) lies in the last \(A\) residues by using \(p\mid(n+1)\cdots(n+A)\). With \(Y\asymp(\log n)^2\) this supplies enough primes. Reaching \(Y\asymp\log n\) pointwise requires removing that \(\log n\) loss, or finding a different source of many carry primes. The direct equidistribution assertion for \(\{n/p\}\) at this polylogarithmic scale is exactly the unsupported step identified in the older comment attempt.

1. Lower-bound front. For the unmultiplied LCM seed, (3.3) is an exact

sufficient and necessary inequality for \(f(L_M-1)>M\). Proving it for infinitely many \(M\) would already double the published asymptotic lower constant. Bae's proposed multiplier would yield much more, but its Fourier proof needs a replacement for the false Lemma 18. Merely increasing a finite search cannot supply the required infinitude or uniformity.

The known exhaustive computation through \(e^{30.1}\) has about \(1.18\times10^{13}\) inputs and is already vastly beyond what should be repeated on this VM. A comparable fresh exhaustive run would be a multi-core-day/HPC task even with a highly optimized recurrence, while it still could not resolve either uniform asymptotic issue. I therefore did not launch it.

PARTIAL: proved an exact LCM-seed valuation reduction, certified f(lcm(1..150)-1)=924 and the n<=100000 record table, and found a rigorous counterexample to the Fourier-tail lemma underlying arXiv:2604.23784's claimed unbounded limsup; the verified worst-case gap remains logarithmic versus log-squared.