\documentclass[11pt]{amsart} \usepackage[letterpaper,margin=1in]{geometry} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage{amsmath,amssymb,mathtools} \usepackage{microtype} \usepackage{booktabs,array} \usepackage{enumitem} \usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref} \hypersetup{pdftitle={The sharp asymptotic for distinct multiples in an interval: a Lean formalization},pdfauthor={Will Howe; Grant Huffman; Jensen Kohlmeyer; Liam Kruer},pdfsubject={Erdos problem 710; a complete formalization in Lean 4}} \numberwithin{equation}{section} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\N}{\mathbb N} \newcommand{\R}{\mathbb R} \newcommand{\E}{\mathbb E} \newcommand{\Prob}{\mathbb P} \newcommand{\ind}{\mathbf 1} \newcommand{\cstar}{c_*} \newcommand{\eps}{\varepsilon} \newcommand{\dd}{\,\mathrm d} \newcommand{\abs}[1]{\left|#1\right|} \DeclareMathOperator{\supp}{supp} \setlist[enumerate]{label=\textup{(\roman*)},leftmargin=2em,itemsep=2pt,topsep=4pt} \setlength{\emergencystretch}{1.5em} \title[Formalizing Erd\H{o}s problem 710]{The sharp asymptotic for distinct multiples in an interval: a Lean formalization} \author[W. Howe]{Will Howe} \author[G. Huffman]{Grant Huffman} \author[J. Kohlmeyer]{Jensen Kohlmeyer} \author[L. Kruer]{Liam Kruer} \date{November 2, 2026} \subjclass[2020]{11N37, 05D15, 68V15} \keywords{distinct multiples, divisibility matching, prime number theorem, weighted counting, Lean, formal verification} \thanks{Email addresses: \href{mailto:howew@purdue.edu}{\nolinkurl{howew@purdue.edu}} (Will Howe), \href{mailto:huffma97@purdue.edu}{\nolinkurl{huffma97@purdue.edu}} (Grant Huffman), \href{mailto:jenwin@purdue.edu}{\nolinkurl{jenwin@purdue.edu}} (Jensen Kohlmeyer), \href{mailto:kruerl@purdue.edu}{\nolinkurl{kruerl@purdue.edu}} (Liam Kruer).} \begin{document} \begin{abstract} Let $f(n)$ be the least nonnegative integer $h$ for which the open interval $(n,n+h)$ contains distinct integers $a_1,\ldots,a_n$ satisfying $i\mid a_i$. We give a complete Lean~4 formalization of the asymptotic formula \[ f(n)\sim\frac{\sqrt2}{e}\,n\sqrt{\log n}. \] This formula was previously announced by Turturean. The lower bound uses completely multiplicative weights, an exact convolution over powers of $2$ and $3$, and two inverse-exponential profiles. For the upper bound, we construct fractional matching weights from finite histograms of prime valuations. Explicit oscillation and stability estimates transfer the continuous transport identities to the integer divisibility graph, including the smallest sources. The companion development proves both bounds for all sufficiently large integers and checks their correspondence with the original open-interval minimum. Its complete theorem has been replayed, together with its imported declarations, by Lean's kernel from an empty environment. \end{abstract} \maketitle \section{Introduction} Choosing a multiple of each positive integer just beyond $n$ is individually easy. Requiring all of the chosen multiples to be distinct produces a global matching problem. Erd\H{o}s and Pomerance studied this phenomenon in \cite{EP}; the diagonal asymptotic is recorded as Erd\H{o}s problem~710 \cite{E92,Bloom}. For $n\in\N$, define $f(n)$ to be the least $h\in\N$ such that there is an injection $a:\{1,\ldots,n\}\to\N$ with \begin{equation}\label{eq:original} n0$. The argument proves a leading asymptotic and does not assert an effective threshold or a second-order term. \subsection*{AI assistance} OpenAI Codex assisted with mathematical proof development, Lean code, and the preparation of this manuscript. The verification claims below refer to the recorded compiler and kernel checks. They are not a claim of independent human refereeing or of acceptance by a journal or prize committee. \section{The finite matching reductions} Let $M(n)$ be the least right endpoint $T$ for which distinct multiples of $1,\ldots,n$ can be selected from $(n,T]\cap\N$. The two conventions satisfy the exact identity \begin{equation}\label{eq:endpoint} f(n)=M(n)-n+1\qquad(n\ge1). \end{equation} Indeed, the integers in $(n,T]$ are precisely those in $(n,n+(T-n+1))$. Consequently, a matching with right endpoint $T=\lfloor cS\rfloor$ gives $\limsup f(n)/S\le c$. We use two familiar consequences of finite matching theory. They are included to specify the precise inequalities transferred to Lean. \begin{lemma}[Weighted obstruction]\label{lem:obstruction} Suppose $U_i\ge0$ and $V_m\ge0$ are weights on $1\le i\le n$ and $n0$ and a prime $p>3$, put \begin{equation}\label{eq:bp} b_y(p)=\max\left\{0,\frac{1-\sqrt{p/y}}{1+\sqrt{p/y}}\right\}. \end{equation} Assign weight $1$ to the primes $2$ and $3$, and extend completely multiplicatively to positive integers: \[ \rho_y(m)=\prod_{\substack{p^a\parallel m\\p>3}} b_y(p)^a. \] In particular, prime powers retain their full multiplicities. \begin{lemma}\label{lem:cofactor} For every positive integer $qT/y}, \qquad V_m=\rho_y(m)H(m/T)\quad(m\le T). \end{equation} If $i\mid m\le T$ and $i>T/y$, write $m=iq$. Then $q0$, \begin{equation}\label{eq:lattice-increment} \Psi(t+s)-\Psi(t)=\frac{ts}{AD} +\frac{s^2+(A+D)s}{2AD}+o(L) \end{equation} uniformly for $c_1L\le t\le c_2L$ and $|s|\le C\log L$. \end{lemma} \begin{proof} Let $N=\lfloor t/A\rfloor$. Exact summation gives \[ \Psi(t)=(N+1)\left(\frac tD+1\right) -\frac{A}{2D}N(N+1) -\sum_{a=0}^{N}\left\{\frac tD-a\frac AD\right\}. \] The number $A/D$ is irrational, since a rational relation would give an equality between nontrivial powers of $2$ and $3$. For an irrational rotation, the average of the fractional-part function tends uniformly in the initial phase to $1/2$. One proves this first for Fourier characters by the finite geometric-series formula, then for continuous periodic functions by uniform approximation, and finally for fractional parts by continuous upper and lower approximations near the jump. Hence the last sum is $(N+1)/2+o(N)$ uniformly in the phase. Expanding $N=t/A+O(1)$ proves \eqref{eq:lattice}. The remainder divided by $t$ is uniformly small once $t$ exceeds a fixed threshold. Both $t$ and $t+s$ lie in a fixed positive multiple of $L$ for large $L$. Subtracting the two expansions therefore gives \eqref{eq:lattice-increment}, uniformly on the stated range. \end{proof} We also use the elementary bound \begin{equation}\label{eq:lattice-global} 0\le\Psi(t)\le(1+t/A)(1+t/D)\qquad(t\ge0). \end{equation} \section{An exact probabilistic convolution} Every positive integer has a unique representation $2^a3^b r$ with $(r,6)=1$. Consequently, for $X>0$, \begin{equation}\label{eq:arithmetic-convolution} F_y(X):=\sum_{m\le X}\rho_y(m) =\sum_{\substack{r\le X\\(r,6)=1}}\rho_y(r)\Psi(\log(X/r)). \end{equation} This is an exact counting identity. For each prime $30$, and $\theta>\beta/2$, then there is $c>0$ such that \begin{equation}\label{eq:tail} \Prob(U>\theta L)\le e^{-c\sqrt L} \end{equation} for all sufficiently large $L$. \end{lemma} \begin{proof} For $p\le y$, \[ \frac{b_y(p)}{1-b_y(p)}=\frac{\sqrt{y/p}-1}{2}. \] The prime number theorem, with partial summation, gives \[ \sum_{p\le y}\frac{\log p}{\sqrt p}\sim2\sqrt y, \qquad \sum_{p\le y}\log p\sim y. \] Removing $2$ and $3$ changes the resulting expression by $O(\sqrt y)$, so \[ \E U=\frac{\sqrt y}{2}\sum_{30$. For $y=\beta L$, define \begin{equation}\label{eq:main-weight} W=W_{\beta,\theta}(L) :=\frac{Z_y}{AD}\E\bigl[(L-U)\ind_{U\le\theta L}\bigr]. \end{equation} Then $W>0$ for large $L$, $W\asymp Z_yL$, and \begin{equation}\label{eq:uniform-count} F_y(e^{L+s})-F_y(e^L)=sW+o(W) \qquad(|s|\le C\log L) \end{equation} uniformly in $s$. \end{proposition} \begin{proof} On $U\le\theta L$, the variable $t=L-U$ lies in $[(1-\theta)L,L]$. Apply \eqref{eq:lattice-increment} inside \eqref{eq:prob-convolution}. The linear term has expectation $sW/Z_y$; the quadratic and remaining linear terms are $O((\log L)^2)=o(L)$. The uniform remainder is $o(L)$. On the exceptional event, the two lattice counts are at most $O(L^2)$ by \eqref{eq:lattice-global}, while \eqref{eq:tail} makes their expected contribution $o(L)$. Multiplication by $Z_y$ proves the asserted error. Finally, $(1-\theta)L\le L-U\le L$ on the main event and that event has probability tending to one. Thus $W$ is bounded above and below by positive constant multiples of $Z_yL$. \end{proof} \section{The lower bound} The two profile losses can be evaluated exactly: \begin{equation}\label{eq:profile-losses} \int_0^\infty u(e^{-s})\dd s=\frac32, \qquad \int_0^\infty v(e^{-s})\dd s=\frac12. \end{equation} Indeed, \eqref{eq:inverse-profiles} gives $s=-\log u+1-u$ on the left and $s=-\log v-1+v$ on the right, reducing the integrals to $\int_0^1(1+u)\dd u$ and $\int_0^1(1-v)\dd v$. Fix $0<\kappa<\cstar$ and choose \begin{equation}\label{eq:beta-choice} \kappa^2e^2<\beta<2,\qquad \beta/2<\theta<1. \end{equation} Let $T=\lfloor\kappa S\rfloor$, $y=\beta L$, and \begin{equation}\label{eq:windows} a=\log(T/n),\qquad b=\log(ny/T). \end{equation} Both windows are positive and $O(\log L)$, and \begin{equation}\label{eq:window-difference} b-a\longrightarrow\log(\beta/\kappa^2)>2. \end{equation} \begin{lemma}\label{lem:profile-comparison} With the weights in \eqref{eq:lower-weights}, \begin{equation}\label{eq:weight-totals} \sum_{i\le n}U_i\ge W\left(b-\frac32-o(1)\right), \qquad \sum_{n0$, \begin{equation}\label{eq:penalty} \frac{m}{(1+2m)v}\le\frac m2+P(v), \qquad P(v):=\frac{\max(\sqrt2-\sqrt v,0)^2}{4v}. \end{equation} For $0<\ell\le2\le V$, \begin{equation}\label{eq:penalty-integral} \int_\ell^V P(v)\dd v =\frac12\log(2/\ell)-\frac32+\sqrt{2\ell}-\frac\ell4. \end{equation} \end{lemma} \begin{proof} For $v\ge2$, the left side of \eqref{eq:penalty} is at most $m/2$. For $v<2$, maximizing $m/((1+2m)v)-m/2$ over $m\ge0$ gives $1+2m=\sqrt{2/v}$ and maximum $P(v)$; equivalently, clearing denominators proves the inequality by a square. On $(0,2)$, \[ P(v)=\frac1{2v}-\frac{\sqrt2}{2\sqrt v}+\frac14. \] Integrating and using $P=0$ above $2$ gives \eqref{eq:penalty-integral}. \end{proof} Fix $c>\cstar$. Choose $b>0$ small, $B>1$, $0<\tau<1$, and $w>0$ so that \begin{equation}\label{eq:strict-budget} \tau^{-1}\left(\frac B2+\frac12\log\frac2{b^2} -\frac32+\sqrt2b-\frac{b^2}4\right) <\log(c/b)-4w, \end{equation} and $b<\min(1,c/2)$. Such choices exist: at $B=\tau=1$ the expression in parentheses is $\log(\cstar/b)+\sqrt2b-b^2/4$, which is strictly less than $\log(c/b)$ for small $b$. The strict inequality persists after a small increase of $B$, a small decrease of $\tau$, and a sufficiently small positive choice of $w$. \section{Transport on a finite prime histogram} Choose $s_0>0$ small enough that $V:=c/s_0>2$. Let \begin{equation}\label{eq:grid} v_k=b^2+kh\quad(0\le k\le N),\qquad Nh=V-b^2. \end{equation} The mesh $h>0$ will be fixed sufficiently small before $n$ is allowed to grow. Write $\nu_p(j)$ for the exponent of the prime $p$ in $j$. For an integer $j\ge1$, define its logarithmic prime masses and histogram densities by \begin{equation}\label{eq:histogram} \mu_k(j)=\sum_{v_kL-\log s_0-\log b+4w. \end{equation} Let $K_w(t)=\max(w-|t|,0)/w^2$, so that $K_w\ge0$, its support is $[-w,w]$, and its integral is $1$. Set $\sigma_0=\log s_0-2w$, and for $v\in(v_k,v_{k+1}]$ define \begin{equation}\label{eq:kernel} G_m(v,\sigma)=\frac{C_k}{v} K_w\left(\sigma-\sigma_0-S_k+D_k\log(v/v_k)\right). \end{equation} Values at bin endpoints are assigned consistently to the half-open bins. When estimating a single bin, we use the continuous extension of its displayed formula to that bin's two endpoints; changing endpoint values does not change any of the integrals. \begin{samepage} \begin{proposition}\label{prop:transport} The kernel \eqref{eq:kernel} has the following properties: \begin{enumerate} \item If $\log s_0\le\sigma\le-\log b+w$, then \[ \sum_k\int_{v_k}^{v_{k+1}}(1+m_k)G_m(v,\sigma)\dd v=1. \] \item For every $\vartheta\in\R$, \[ \sum_k\int_{v_k}^{v_{k+1}}m_kG_m(v,\vartheta-\log v)\dd v\le\tau. \] \item If $G_m(v,\sigma)\ne0$, then \begin{equation}\label{eq:support} \log b+w<\sigma+\log v<\log c-w. \end{equation} \end{enumerate} \end{proposition} \end{samepage} \begin{proof} Set $x=\log v$. In the row integral the coefficient becomes $C_k(1+m_k)=D_k$, while the kernel argument has slope $D_k$ in $x$. The integral on a bin is therefore the integral of $K_w$ from $\sigma-\sigma_0-S_k$ to $\sigma-\sigma_0-S_{k+1}$. These intervals telescope. By \eqref{eq:tail-span}, their union covers $[-w,w]$ on the indicated source range. For a column, the argument has slope $D_k-1$. The identity $m_kC_k=\tau(1-D_k)$ makes the bin integral $\tau$ times an integral of $K_w$. The endpoint map \[ x\longmapsto x+S_k-D_k(x-\log v_k) \] has slope $1-D_k\ge0$ and joins continuously across the bins. The column integrals consequently telescope to $\tau$ times the integral of $K_w$ on an interval, which is at most $\tau$. This also handles bins with $m_k=0$, where the column contribution vanishes. The same monotone endpoint map takes values between $\log(b^2)+S_0$ and $\log V$. A nonzero kernel value differs from the corresponding map value, after adding $\sigma_0$, by less than $w$. Using \eqref{eq:tail-span} and $V=c/s_0$ proves \eqref{eq:support}. \end{proof} \section{Uniform discretization and one-prime stability} Set $\ell=b^2$. On every bin, uniformly over all nonnegative histograms, the kernel is bounded by $1/(\ell w)$. Both functions $v\mapsto G_m(v,\sigma)$ and $v\mapsto G_m(v,\vartheta-\log v)$ have oscillation at most \begin{equation}\label{eq:oscillation} Kh,\qquad K=\frac1{\ell^2w^2}+\frac1{\ell^2w}. \end{equation} To see this, use the $1/w^2$ Lipschitz bound for $K_w$, $|\log v-\log u|\le|v-u|/\ell$, and $0\le C_k,D_k\le1$. For the column argument, $|D_k-1|\le1$ provides the same estimate. \begin{lemma}[Finite quadrature]\label{lem:quadrature} Let $g$ have oscillation at most $\eps$ about its left-endpoint value on an interval of length $h$. Let nonnegative atomic weights in that interval have total mass $M$. For $q\ge0$, \begin{equation}\label{eq:quadrature} \left|\sum_r a_rg(x_r)-q\int g(v)\dd v\right| \le\eps(M+qh)+|M-qh|\,|g(v_{\rm left})|. \end{equation} \end{lemma} \begin{proof} Subtract $g(v_{\rm left})$ from both the finite sum and the integral. Their two errors are bounded by $\eps M$ and $\eps qh$; the constant terms differ by $(M-qh)g(v_{\rm left})$. \end{proof} Let \[ P_k(L)=\sum_{v_kL1$ with $\gamma\tau<1$. Next choose $s_0>0$ small enough, and then the fixed mesh $h$ small enough, that \begin{equation}\label{eq:strict-margins} \gamma\bigl(1-2Kh(Nh+B)\bigr)>1, \qquad \gamma(\tau+2KhB)+\frac{2\gamma s_0}{c}<1. \end{equation} This is possible because $Nh=V-b^2$ remains fixed while $h\downarrow0$. All parameters are now fixed independently of $n$. Put \begin{equation}\label{eq:integer-parameters} T=\lfloor cS\rfloor,\quad q=\lfloor b\sqrt L\rfloor, \quad I=\frac{s_0S}{L}. \end{equation} For large $n$, $q\ge1$, $VL\le T$, $2nqn/q$ are assigned the distinct targets $qi$, which lie in $(n,nq]$. It remains to match $i\le n/q$ into $(nq,T]$. For the regular sources $I\cstar$ admits a matching with right endpoint $\lfloor cS\rfloor$ for all sufficiently large $n$. Therefore \begin{equation}\label{eq:limsup} \limsup_{n\to\infty}\frac{f(n)}S\le\cstar. \end{equation} Combining \eqref{eq:liminf} and \eqref{eq:limsup} proves Theorem~\ref{thm:main}. \section{Formalization and verification}\label{sec:formalization} Theorem~\ref{thm:main} is formalized in Lean~4 as the unconditional declaration \texttt{Erdos710.erdos\_710}. Its statement uses the exact open-interval minimum in \eqref{eq:original} and the limit along all natural numbers. Both bounds have complete proofs, with no \texttt{sorry}, \texttt{admit}, or additional mathematical assumptions. The development has passed a fresh kernel replay. Source revisions and reproducibility details are recorded in Appendix~\ref{app:reproducibility}. \appendix \section{Reproducibility of the Lean formalization}\label{app:reproducibility} The companion development is identified by commit \begin{center}\small\ttfamily 7844854432654d58bfbf6f39c4fdac3da2d736ed. \end{center} It was rebuilt in isolation with Lean~4.35.0-rc3 and Mathlib~\cite{Mathlib} at revision \begin{center}\small\ttfamily c55e6e786f49471c72fbddbec5415808896aec1e. \end{center} The prime number theorem is provided by the attributed source slice of \cite{PNT}, at revision \begin{center}\small\ttfamily c39a751132c88b6e8080b74c74023fd95b3d8be0. \end{center} The finite matching definition indexes the divisors $1,\ldots,n$ by \texttt{Fin n}, with divisor \texttt{i.val + 1}. The minimum is defined using \texttt{Nat.find} and its existence follows from the quadratic construction in Section~1. The development proves its equality with the \texttt{sInf} definition in the Formal Conjectures project~\cite{FC}. The final statement is \begin{quote}\small\ttfamily Erdos710.erdos\_710 : Erdos710.SourceAsymptoticFormula. \end{quote} It has no hypotheses and asserts the asymptotic equivalence of the original minimum with $(\sqrt2/\exp(1))n\sqrt{\log n}$. The recorded verification rebuilt 86 Lean source modules and passed 493 explicit theorem axiom audits. A fresh kernel replay checked every local and imported declaration in the dependency closure of the final theorem from an empty environment. Its only axioms are \texttt{propext}, \texttt{Classical.choice}, and \texttt{Quot.sound}, the standard Lean foundations. The replay uses the kernel bundled with the pinned Lean version. The repository documentation supplies the build instructions and the correspondence between source modules and the proof above. \begin{thebibliography}{9} \bibitem{Bloom} T. F. Bloom, \emph{Erd\H{o}s problem 710}, Erd\H{o}s Problems, \url{https://www.erdosproblems.com/710}, accessed November 2, 2026. \bibitem{E92} P. Erd\H{o}s, \emph{Some of my forgotten problems in number theory}, Hardy--Ramanujan Journal \textbf{15} (1992), 34--50. \url{https://doi.org/10.46298/hrj.1992.125}. \bibitem{EP} P. Erd\H{o}s and C. Pomerance, \emph{Matching the natural numbers up to $n$ with distinct multiples in another interval}, Indagationes Mathematicae (Proceedings) \textbf{83} (1980), no.~2, 147--161. \url{https://doi.org/10.1016/1385-7258(80)90018-9}. \bibitem{FC} The Formal Conjectures Authors, \emph{Formal Conjectures}, definitions of Erd\H{o}s Problems 710 and 711. Source blobs: \texttt{e65522825737943cf4de3b41fa00e101288af6f3} (710); \texttt{d0170ecd49a0621d4f3e951de1d0ec9690dab6a5} (711). \url{https://github.com/google-deepmind/formal-conjectures}. \bibitem{Hall} P. Hall, \emph{On representatives of subsets}, Journal of the London Mathematical Society \textbf{s1-10} (1935), no.~1, 26--30. \url{https://doi.org/10.1112/jlms/s1-10.37.26}. \bibitem{Mathlib} The Mathlib Community, \emph{Mathlib}, Lean mathematical library. The revision used is specified in Appendix~\ref{app:reproducibility}. \url{https://github.com/leanprover-community/mathlib4}. \bibitem{PNT} A. Kontorovich and contributors, \emph{PrimeNumberTheoremAnd}. The revision used is specified in Appendix~\ref{app:reproducibility}. \url{https://github.com/AlexKontorovich/PrimeNumberTheoremAnd}. \bibitem{Turturean} D. Turturean, \emph{An asymptotic formula for distinct multiples in an interval}, manuscript, version compiled November 1, 2026 (25 pages). \href{https://www.erdosproblems.com/forum/thread/710/proof-claims\#proof-claim-344}{Public announcement, September 23, 2026}; \href{https://www.overleaf.com/read/jvdyzbbmbvcf}{manuscript}. \end{thebibliography} \end{document}