Unbounded logarithmic limsup in Erd\H{o}s problem 684

This paper, titled "Unbounded Logarithmic Limsup in Erdős Problem 684" by Ji Ho Bae, provides a definitive negative answer to a long-standing conjecture in combinatorial number theory. It proves that the function $f(n)$—the smallest $k$ such that the $k$-smooth part of $\binom{n}{k}$ exceeds $n^2$—cannot be bounded by $C \log n$ for any constant $C$.

Below is a detailed technical summary of the work.

---

1. The Problem: Erdős Problem 684

The paper addresses a problem posed by Paul Erdős regarding the prime factorization of binomial coefficients. For any $0 \leq k \leq n$, the binomial coefficient $\binom{n}{k}$ can be factored into:
$$\binom{n}{k} = u_k(n) v_k(n)$$
where $u_k(n)$ is the $k$-smooth part (all prime factors $\leq k$) and $v_k(n)$ is the part consisting of prime factors $> k$.

Erdős Problem 684 asks for the growth rate of the function $f(n)$, defined as the least $k$ such that $u_k(n) > n^2$. While it was widely conjectured that $f(n) \ll \log n$, Bae proves that:
$$\limsup_{n \to \infty} \frac{f(n)}{\log n} = \infty$$

2. Methodology: The Construction

The author employs a sophisticated "short-multiplier" construction to build integers $n$ where $u_k(n)$ remains small even for relatively large $k$.

A. Kummer’s Theorem and Carry-Free Residues

The core idea relies on Kummer’s Theorem, which relates the exponent of a prime $p$ dividing $\binom{n}{k}$ to the number of carries in the addition of $k$ and $n-k$ in base $p$.
The author constructs $n$ using a multiplier $t$ and the least common multiple $L_M = \text{lcm}(1, \dots, M)$:
$$n = t L_M - 1$$
By choosing $t$ carefully, the author ensures that for all primes $p \leq M$, the addition is "carry-free" at low prime-power levels. This keeps the $k$-smooth part $u_k(n)$ small. To prevent $u_k(n)$ from growing too large when $k > M$, the multiplier $t$ is forced to satisfy specific "upper-tail" residue conditions.

B. The QM-Box and Fourier Reduction

To prove such a multiplier $t$ exists, the problem is transformed into a sieve problem. The author introduces:

• The $Q_M$-box formulation: A way to parameterize the residue classes using $Q_M = M!/L_M$.
• Fourier Reduction: The existence of $t$ is converted into a requirement that a certain sum of Fourier coefficients is small.
• Exact Denominator Lemma: This is used to prune "low-denominator" modes in the Fourier expansion, allowing the author to focus only on the "high-denominator" top-band frequencies.

C. Dyadic Localization and the "Petal" Shell

The most technical part of the methodology involves localizing the problem to a "dyadic product-shell." The author focuses on integers $n$ that are products of a specific number of primes ($a$ primes) within a specific dyadic range $(M, CM]$. This is referred to as the "petal" structure.

3. Key Contributions and Analytic Input

The paper’s success hinges on bridging a combinatorial construction with deep analytic number theory.

• Timofeev’s Method: The author utilizes and localizes Timofeev’s large-$\Omega$ mean-in-progressions method. This method provides estimates for the distribution of integers with many prime factors in arithmetic progressions.
• Localized Dyadic Estimates: The author proves several new lemmas (notably Proposition 6 and Lemma 7) to adapt Timofeev's global results to a very thin, localized set: squarefree integers with a fixed number of prime factors in a specific dyadic interval.
• The Harmonic-Height Cap: The author proves that the "heights" (the values of the residues) are distributed such that they do not cluster in a way that would create unexpected carries, effectively "capping" the growth of the smooth part.

4. Results

The paper yields two primary mathematical results:

1. Existence of Counterexamples: For any fixed $C > 1$, there exist infinitely many $n$ such that $f(n) > (C - o(1)) \log n$.
2. Unboundedness: The ratio $\frac{f(n)}{\log n}$ is unbounded as $n \to \infty$.

5. Significance

This paper is significant for several reasons:

• Resolution of a Conjecture: It settles a specific, long-standing problem in the study of binomial coefficients and prime distributions.
• Methodological Innovation: The "short-multiplier" construction and the "QM-box" reduction represent a new toolkit for handling problems where one needs to control carries in multiple prime bases simultaneously.
• Refinement of Analytic Tools: The successful localization of Timofeev’s method demonstrates how global results about the distribution of $\Omega(n)$ can be "squeezed" into extremely thin arithmetic shells, a technique that may be applicable to other problems in probabilistic number theory.