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.
2. [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.
3. [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
\[ u(n,k):=\prod_{p\leq k}p^{\nu_p\binom nk},\qquad f(n):=\min\{0\leq k\leq n:u(n,k)>n^2\}, \]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\). It implies \(f(n)\to\infty\), but ineffectively. \[
f(n)\leq n^{30/43+o(1)}.
\] The same method gives \(n^{2/3+o(1)}\) under RH or the Density Hypothesis. \(f(n)\sim2\log n\) for at least most \(n\). \[
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\). varying the smoothness cutoff for one fixed binomial coefficient. The mathematical content of the 27 comments, after expanding the entire thread, is as follows. 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. preprint. Section 4 below gives a concrete disproof of one lemma in that proof. \(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. almost-all upper bound \[
f(n)\leq\left(\frac4{1-\gamma}+o(1)\right)\log n
=(9.461\ldots+o(1))\log n.
\] 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\). 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. to an unproved equidistribution assertion for \(\{n/p\}\). Bloom and Sothanaphan point out that the assertion is not justified and is not expected pointwise. AI-assisted arguments. The page warns that comments are not verified for correctness. 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. [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: 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. [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: [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\). [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: 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:
1. Primary-source literature audit
Original source
a4703a104adcbbde0ed605c9ff81379adee8b7ceda3714ea455b5b68ae720dfd
Tang and the short-interval input
9ee917877b45efa74d37e0abeab77268a37d777305c1dd0c99393af225b8b1bb
APSSV
9dbacb1d6a7585d5ac2a4a0cb05de080a3e6b2a47bdbae1ab6fde3553fdc2737
Two papers newer than the page's 1 April edit
5165eed9da06a972c826c7c006b11e51b27dd3637ed2a1be009745783ab3850b
2. **[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
\[ \begin{aligned} \nu_p\binom nk &=\sum_{a\geq1} \left( \left\lfloor\frac n{p^a}\right\rfloor -\left\lfloor\frac k{p^a}\right\rfloor -\left\lfloor\frac{n-k}{p^a}\right\rfloor \right)\\ &=\sum_{a\geq1} \mathbf 1_{[n]_{p^a}<[k]_{p^a}}, \end{aligned} \tag{2.1} \]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
\[ L=L_M=\operatorname{lcm}(1,\ldots,M). \]For \(p\leq M\), define
\[ \alpha_p=\lfloor\log_pM\rfloor,\qquad U_p=\frac{L}{p^{\alpha_p}},\qquad r_p=[U_p]_p\in\{1,\ldots,p-1\}. \]Proposition
[A] For every \(p\leq k\leq M\),
\[ \boxed{ \nu_p\binom{L_M-1}{k} = \mathbf 1_{\displaystyle r_p\leq \left\lfloor k/p^{\alpha_p}\right\rfloor} \ \nu_p(U_p-r_p). } \tag{3.1} \]Consequently \(u(L_M-1,k)\) is nondecreasing for \(0\leq k\leq M\), and
\[ f(L_M-1)>M \quad\Longleftrightarrow\quad \prod_{\substack{p\leq M\\ r_p\leq\lfloor M/p^{\alpha_p}\rfloor}} p^{\nu_p(U_p-r_p)} \leq (L_M-1)^2. \tag{3.2} \]Proof
Put \(n=L-1\). At every level \(a\leq\alpha_p\),
\[ [n]_{p^a}=p^a-1, \]so (2.1) has no carry.
At a higher level write \(a=\alpha_p+b\), \(b\geq1\), and put
\[ s_b=[U_p]_{p^b}. \]Because \(p^{\alpha_p+1}>M\geq k\), one has
\([k]_{p^{\alpha_p+b}}=k\), while
\[ [n]_{p^{\alpha_p+b}}=p^{\alpha_p}s_b-1. \]Thus a carry occurs exactly when
\[ s_b\leq h,\qquad h:=\left\lfloor\frac{k}{p^{\alpha_p}}\right\rfloorsuch \(b\). If \(r_p\leq h \(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\). 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. Bae's Lemma 18 (“Non-prefix Fourier tails”) asserts, for a top-band prime \(M 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 LetWhat this reduction isolates
4. A false lemma in the claimed unbounded-limsup proof
Write \(e(x)=\exp(2\pi ix)\). At the full-conductor mode \(a=1\),
the complete residue classes in \(B\) cancel:
\[ \begin{aligned} \sum_{y\in B}e(-y/p^2) &=\sum_{r\in R}e(-r/p^2) \sum_{j=0}^{p-1}e(-j/p)\\ &=0. \end{aligned} \]Therefore
\[ \left|\sum_{y\in A_p}e(-y/p^2)\right| = \left|\sum_{y\in E}e(-y/p^2)\right|. \tag{4.3} \]The set \(E\) contains
\(\lceil3p/4\rceil,\ldots,p-1\), so
\[ |E|\geq\frac{p-3}{4}. \]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
\[ \left|\sum_{y\in E}e(-y/p^2)\right| \geq\frac{|E|}{2} \geq\frac p{16}. \]Since \(|A_p|\leq p^2\),
\[ \frac{|\widehat{1_{A_p}}(1)|}{|A_p|/p^2} = \frac{\left|\sum_{y\in A_p}e(-y/p^2)\right|}{|A_p|} \geq\frac1{16p}. \tag{4.4} \]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:
| \(p\) | \(|E|\) | \(|A_p|\) | normalized \(a=1\) coefficient | \(p\) times coefficient |
|---:|---:|---:|---:|---:|
| 17 | 8 | 77 | 0.102390816065 | 1.74064387311 |
| 31 | 14 | 234 | 0.0595420353582 | 1.84580309611 |
| 101 | 50 | 2576 | 0.0194005563851 | 1.95945619490 |
| 503 | 250 | 63128 | 0.00396012931177 | 1.99194504382 |
| 1009 | 504 | 254773 | 0.00197822183322 | 1.99602582972 |
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]
\[ f(4963595372164418730243844250278933730416682962970482173955823999) =924. \]The factorization of the crossing value \(u(n,924)\), recomputed by both
routes, is
\[ \begin{aligned} &2^4\,3^3\,5\,7\,13\,23\,31\,41\,43\,47\,67\,79\,157\,163\,167\,191\, 197\,233\,241\,251\,257\,271\,283\,311\,313\,317\,331\,337\\ &{}\quad\cdot349\,359\,367\,421\,463\,467\,479\,487\,491\,499\,503\,509\, 521\,523\,541\,547\,557\,563\,571\,577\,587\,593\,619\,631\,647\,769\, 773\,809. \end{aligned} \]For the range \(n\leq100000\), the checker uses a second algorithm. It
updates
\[ \binom nk=\binom n{k-1}\frac{n-k+1}{k} \]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
\[ 1,2,3,4,5,6,7,8,9,11,12,13,14,15,17,19,20,23. \]The successive records of \(f(n)\) through \(100000\) are:
| \(n\) | \(f(n)\) | \(n\) | \(f(n)\) |
|---:|---:|---:|---:|
| 10 | 7 | 16 | 11 |
| 18 | 13 | 24 | 17 |
| 31 | 19 | 47 | 23 |
| 74 | 24 | 167 | 25 |
| 215 | 29 | 219 | 31 |
| 284 | 33 | 439 | 35 |
| 474 | 38 | 566 | 39 |
| 797 | 43 | 1322 | 48 |
| 2105 | 49 | 2804 | 51 |
| 3967 | 55 | 4198 | 59 |
| 4549 | 67 | 12119 | 73 |
| 20327 | 74 | 55383 | 75 |
| 56573 | 76 | 64712 | 79 |
| 76463 | 81 | 95444 | 85 |
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
\[ (1/2-o(1))\log n \ \leq\ f(n)\ \text{along an infinite sequence}, \qquad f(n)\ll(\log n)^2\ \text{for all large }n. \]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.
2. 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.