Unbounded logarithmic limsup in Erdős Problem 684 via shifted carry scheduling

Abstract

For 1 ≤ k ≤ n, let u(n,k) be the part of the binomial coefficient binom(n,k) supported on primes at most k, and let f(n) be the least k for which u(n,k) > n^2. Erdős Problem 684 asks for bounds on f(n). We prove limsup_{n→∞} (f(n)/log n)(log log log n/log log n) ≥ 1/2. In particular, limsup_{n→∞} f(n)/log n = ∞, so no uniform estimate f(n) = O(log n) is possible. The proof constructs integers n = tL_M - h - 1, where L_M = lcm(1,...,M). Product-cell coding gives simultaneous two-sided approximations to tL_M modulo every prime in (M,K]. The shift by h folds both signs into a common one-sided carry region. Low-level carries are bounded coherently, while a truncated CRT argument and exponential weighting control the high-power tail. An elementary anchored-fibre lemma then selects a multiplier satisfying both requirements. Together, these ingredients prove the stated bound unconditionally. Together with the known general O((log n)^2) upper bound, this answers Erdős's original request for bounds. Determining the exact extremal order is a separate problem.