A Resolution of Erdős Problem 731 under Dyadic Regularity
Eric Li
math.NT
Jun 27, 2026 · v2
TL;DR
The main results are fully formalized in Lean 4 over Mathlib, including a from-scratch PNT proof via Newman's argument, developed with Harmonic's Aristotle.
Abstract
We resolve Erdős Problem 731 under the explicit dyadic-regularity formalization of "reasonable." Let $A(n)$ be the least positive integer not dividing $\binom{2n}{n}$. On dyadic intervals $X\le n<2X$, put $L=\log(2X)$ and $F_X=\sqrt{2}(\log 2)^{1/4}L^{1/4}\exp\sqrt{(\log 2)L}$. Uniformly for $1\le z\le Z(X)=o(L^{1/4})$, we prove $\mathbb{P}_X(A(n)\le F_X\exp(-z))\asymp \exp(-2z)$ and $\mathbb{P}_X(A(n)>F_X\exp(z))\ll \exp(-2z)$. Consequently $\log A(n)=\sqrt{(\log 2)\log n}+\frac{1}{4}\log\log n+O_{\mathrm{dens}}(1)$. We also prove dyadic nonconcentration: no scalar center on a large dyadic block, and hence no dyadically regular deterministic scale $f$, can satisfy $A(n)/f(n)\to 1$ in natural density. The proof retains the exact least-common-multiple divisibility condition and replaces heuristic cross-base independence by a moving-base restricted-digit variance theorem. The resolution proved here has been formally verified in Lean.
Problem
Erdős Problem 731 asks for a reasonable deterministic scale f(n) such that A(n), the least positive integer not dividing the central binomial coefficient C(2n,n), satisfies A(n) f(n) for almost all n. Prior results, stated without proof details, gave only exp((log n)^{1/2±ε}) bounds.
Approach
A(n) is shown to be a prime power, and the event A(n)>y is characterized exactly via divisibility of lcm(1..y) into C(2n,n), using Kummer carries. A moving-base restricted-digit variance theorem with smooth Fourier minorants on prime strips replaces heuristic cross-base independence and yields mesoscopic tail bounds on dyadic intervals. The results are formalized in Lean 4 (v4.28.0) over Mathlib, with the formalization developed using Aristotle (Harmonic).
Results
log A(n) = sqrt((log 2) log n) + (1/4) log log n + O(1) in natural density, with two-sided exp(-2z) tail bounds, and no dyadically regular f can satisfy A(n)/f(n) → 1 in density. The Lean theorems are hypothesis-free and depend only on Lean's standard axioms.