\documentclass[11pt]{amsart}
\usepackage[letterpaper,margin=1in,headheight=14pt]{geometry}
\usepackage{amsmath,amssymb,mathtools,array}
\usepackage[hidelinks]{hyperref}
\emergencystretch=2em
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\one}{\mathbf{1}}
\newcommand{\grid}{\mathcal S}
\newcommand{\rect}{\mathcal R}
\newcommand{\eints}{\mathcal E}
\newcommand{\bints}{\mathcal B}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1\right\rceil}
\title[Fork-free sets and an irrational density]{An exact formula for fork-free sets of integers and the irrationality of their density}
\author{Liam Kruer}
\author{Jensen Kohlmeyer}
\date{September 21, 2026}
\subjclass[2020]{Primary 11B75, 11J72; Secondary 11J87, 05D05, 68V15, 68V20}
\keywords{Erd\H{o}s problem 1062, divisibility, fork-free sets, extremal density, irrationality, Subspace Theorem, rotation by log 4/log 3, Lean, formal verification}
\begin{document}
\begin{abstract}
A set of positive integers is fork-free if no element of the set divides two other elements of the set. Let $f(n)$ be the largest size of a fork-free subset of $\{1,\ldots,n\}$. Erd\H{o}s asked how large $f(n)$ can be, and whether $f(n)/n$ tends to an irrational limit. Lebensold proved $0.6725n\le f(n)\le0.6736n$ for large $n$, and Davis recently proved that $f(n)/n$ converges to an effectively computable constant. We prove the exact formula
\[
f(n)=\sum_{\substack{m\le n\\(m,6)=1}}\bigl(R(n/m)-\one_{\bints}(n/m)\bigr)\qquad(n\ge1),
\]
where $R(x)=1+\floor{\log_4 x}+\floor{\log_3 x}+\one_{\eints}(x)$ is the largest size of a fork-free set of integers $2^a3^b\le x$ for $x\ge1$, and $\eints,\bints$ are explicit unions of intervals. Consequently $f(n)/n\to c$ with
\[
180c=32+\sum_{k\ge0}\varphi([4^k]_3)4^{-k}+\sum_{k\ge0}\psi([3^k]_4)3^{-k}=121.13381\ldots,
\]
where $[x]_b\in[1,b)$ is the mantissa of $x$ in base $b$ and $\varphi,\psi$ are explicit integer step functions. Numerically $c=0.67296565119948934747\ldots$. We prove that $c$ is irrational, which answers Erd\H{o}s's question affirmatively. The proof of irrationality combines exact return identities for the rotation by $\log4/\log3$, a two-cutoff $2$-adic nonvanishing argument, and a three-place case of the $p$-adic Subspace Theorem. The lower bound in the exact formula rests on a finite computation. The whole argument, including the finite computation (replayed as checked certificates) and a self-contained proof of the required case of the Subspace Theorem, is formalized in a single Lean 4 file that proves the Formal Conjectures statement of Erd\H{o}s Problem 1062(ii) using only the standard axioms.
\end{abstract}
\maketitle
\section{Introduction}
A set $A$ of positive integers is fork-free if there are no distinct $a,b,c\in A$ with $a\mid b$ and $a\mid c$. Equivalently, every element of $A$ has at most one proper multiple in $A$. Let
\[
f(n)=\max\{|A|:A\subseteq\{1,\ldots,n\},\ A\text{ fork-free}\}.
\]
Every element of $(n/3,n]$ has at most one proper multiple up to $n$, namely its double, so $f(n)\ge\ceil{2n/3}$.
Erd\H{o}s asked how large $f(n)$ can be, and whether $\lim_{n\to\infty}f(n)/n$ exists and is irrational. See Problem B24 in Guy's collection~\cite{Guy} and Problem 1062 in Bloom's list~\cite{Bloom}. Lebensold~\cite{Lebensold} proved that $0.6725n\le f(n)\le0.6736n$ for all large $n$. Davis~\cite{Davis} recently showed that $f(n)=cn+o(n)$ for an effectively computable constant $c$, as a special case of a general theorem on forbidden subgraphs of divisor graphs, and left the irrationality of $c$ open. The irrationality question is also recorded in the Formal Conjectures project~\cite{Formal} as the Lean statement \texttt{Erdos1062.erdos\_1062.parts.ii}, and it is posed as a formal challenge on the conjectures.io platform~\cite{Conjectures}.
\subsection{Results}
All intervals below are closed on the left and open on the right. Put
\begin{equation}
\begin{aligned}
\eints&=\left(\bigcup_{j\ge0}[2\cdot4^j,4^{j+1})\right)
\cap\left(\bigcup_{b\ge0}[2\cdot3^b,3^{b+1})\right),\\
\bints&=\left(\bigcup_{b\ge0}[10\cdot3^b,12\cdot3^b)\right)
\cap\left(\bigcup_{j\ge0}\left[4^j,\tfrac54 4^j\right)\right),
\end{aligned}\label{eq:intervals}
\end{equation}
and define, for real $x$,
\begin{equation}
R(x)=1+\floor{\log_4 x}+\floor{\log_3 x}+\one_{\eints}(x)\quad(x\ge1),
\qquad R(x)=0\quad(x<1).\label{eq:R}
\end{equation}
The first intervals of $\bints$ are $[270,320)$, $[65610,78732)$ and $[16777216,19131876)$.
\begin{theorem}[Exact formula]\label{thm:exact}
For every positive integer $n$,
\begin{equation}
f(n)=U(n):=\sum_{\substack{1\le m\le n\\(m,6)=1}}\bigl(R(n/m)-\one_{\bints}(n/m)\bigr).\label{eq:exact}
\end{equation}
Moreover, a fork-free set of this size can be chosen inside $(n/8,n]$.
\end{theorem}
Here $R(x)$ is the largest size of a fork-free set of integers of the form $2^a3^b$ not exceeding $x$ (Theorem~\ref{thm:grid}). The terms $\one_{\bints}$ are forced losses between adjacent powers-of-five layers (Lemma~\ref{lem:forced}). Formula \eqref{eq:exact} is evaluated quickly by summing the jumps of $R$. For instance,
\[
f(10^6)=672964,\qquad
f(10^{12})=672965651200,\qquad
f(10^{24})=672965651199489347471228.
\]
Theorem~\ref{thm:exact} answers the first half of Erd\H{o}s's question, how large $f(n)$ can be, in the strongest possible form. For the density, write $[x]_b=x/b^{\floor{\log_b x}}\in[1,b)$ for the mantissa of $x>0$ in base $b$, and define integer step functions $\varphi$ on $[1,3)$ and $\psi$ on $[1,4)$ by Table~\ref{tab:steps}.
\begin{table}[tbp]
\caption{The coefficient step functions.}\label{tab:steps}
\centering
\begin{tabular}{@{}lrlr@{}}
\hline
$t\in[1,3)$ & $\varphi(t)$ & $s\in[1,4)$ & $\psi(s)$\\\hline
$[1,16/15)$ & $78$ & $[1,4/3)$ & $30$\\
$[16/15,10/9)$ & $30$ & $[4/3,8/5)$ & $35$\\
$[10/9,4/3)$ & $-30$ & $[8/5,5/3)$ & $29$\\
$[4/3,3/2)$ & $30$ & $[5/3,2)$ & $24$\\
$[3/2,2)$ & $0$ & $[2,4)$ & $-60$\\
$[2,8/3)$ & $-60$ & &\\
$[8/3,3)$ & $-12$ & &\\\hline
\end{tabular}
\end{table}
\begin{theorem}[Density]\label{thm:density}
The limit $c=\lim_{n\to\infty}f(n)/n$ exists, and
\begin{equation}
c=\frac{11}{18}+\frac13\left(\int_{\eints}\frac{dt}{t^2}-\int_{\bints}\frac{dt}{t^2}\right).\label{eq:integral}
\end{equation}
Equivalently,
\begin{equation}
180c=32+\sum_{k\ge0}\frac{\varphi([4^k]_3)}{4^k}+\sum_{k\ge0}\frac{\psi([3^k]_4)}{3^k}.\label{eq:series}
\end{equation}
Numerically,
\[
c=0.672965651199489347471227919852209644752814733132999025108932699233\ldots.
\]
\end{theorem}
The displayed digits were obtained twice, independently: from \eqref{eq:integral} by exact rational integration with a tail bound, and from \eqref{eq:series} by exact rational summation with a tail bound. The two enclosures agree.
\begin{theorem}[Irrationality]\label{thm:irrational}
The constant $c$ is irrational.
\end{theorem}
\begin{corollary}
The ratio $f(n)/n$ converges to an irrational number. In particular the Formal Conjectures statement \texttt{Erdos1062.erdos\_1062.parts.ii} holds with answer \texttt{True}.
\end{corollary}
\subsection{Outline of the proof}
Every positive integer is uniquely $m2^a3^b$ with $(m,6)=1$. Section~\ref{sec:grid} solves the extremal problem on the two-prime grid $\{2^a3^b\le x\}$ exactly: the answer is $R(x)$, and the maximal configurations are rigid enough to be described. Summing over $m$ gives an upper bound, which Section~\ref{sec:upper} sharpens by forced losses between the classes $m$ and $5m$. Section~\ref{sec:lower} constructs matching sets inside $(n/8,n]$, where the only divisibility ratios between distinct elements are $2,3,\ldots,7$. Ratios $2,3,4,6$ are handled by explicit parity-restricted grid sets, and ratios $5,7$ by a cutoff recursion. That the recursion never gets stuck is a finite statement, which we verify by computer. Section~\ref{sec:density} derives Theorem~\ref{thm:density}.
The proof of irrationality occupies Sections~\ref{sec:returns} and~\ref{sec:subspace}. The two series in \eqref{eq:series} are sampled along the rotation by $\alpha=\log4/\log3$. Along a sequence of unimodular brackets $p/q<\alpha
\cdots>b_r$. Put $a_0=-1$, $b_{r+1}=-1$, $w_i=a_i-a_{i-1}$, $h_i=b_i-b_{i+1}$, and $\rect_i=\{(a,b):a_{i-1}1$, and since $b\le b_ia_{i-1}$. For $i=1$, $a>a_0=-1$ holds automatically. Similarly $b>b_{i+1}$, so $w\in\rect_i$. Two comparable nonmaximal elements below $(a_i,b_i)$ would give a fork, so they form an antichain. This proves (i).
An antichain in a $w\times h$ box has distinct first and distinct second coordinates, so it has at most $\min(w,h)$ elements, and none if it must avoid the corner of a $1\times1$ box. This is the first inequality in (ii). The second inequality, and the statements about the cases of equality in (iii), follow by direct comparison: $g(w,h)=h+w/2$ exactly when $w=2$ and $h\in\{1,2\}$, and for $w=1$ one has $h+\tfrac12-g(1,h)=\tfrac12$ for $h\in\{1,2\}$ and $h-\tfrac32\ge\tfrac32$ for $h\ge3$. Identity \eqref{eq:rectbound} follows by summing $\sum_i h_i=b_1+1$ and $\sum_i w_i=a_r+1$. For (iv), a point of $\rect_i$ has smaller first coordinate and larger second coordinate than every point of $\rect_j$ for $j>i$. Thus points in different rectangles are incomparable, and within one rectangle only the corner lies above the other chosen points.
\end{proof}
\begin{theorem}\label{thm:grid}
For every real $x\ge1$, the largest fork-free subset of $\grid(x)$ has
\[
R(x)=\floor{a^*/2}+b^*+1+\one_{[a^*\text{ odd}]}\delta
=1+\floor{\log_4x}+\floor{\log_3x}+\one_{\eints}(x)
\]
elements.
\end{theorem}
\begin{proof}
The two expressions agree because $\floor{\log_4x}=\floor{a^*/2}$, $a^*$ is odd exactly when $x\in\bigcup_j[2\cdot4^j,4^{j+1})$, and $\delta=1$ exactly when $x\in\bigcup_b[2\cdot3^b,3^{b+1})$.
\emph{Upper bound.} Let $W$ be fork-free. Since $b_1\le b^*$ and $a_r\le a^*$, \eqref{eq:rectbound} gives $|W|\le b^*+1+(a^*+1)/2$. If $a^*$ is even, integrality gives $|W|\le b^*+1+a^*/2$. If $a^*$ is odd and $\delta=1$, the bound is already $\floor{a^*/2}+b^*+2$.
If $a^*$ is odd and $\delta=0$, equality would require $b_1=b^*$, $a_r=a^*$ and all $d_i=0$. Then $w_1=2$, so $a_1=1$ and $2\cdot3^{b^*}\in\grid(x)$, contradicting $\delta=0$. Hence $|W|\le b^*+(a^*+1)/2=\floor{a^*/2}+b^*+1$.
\emph{Constructions.} If $a^*=0$, then $\grid(x)=\{1\}$ and $R(x)=1$. If $a^*\ge2$ is even, take corners in the columns $a=0,2,\ldots,a^*$ at heights $\beta(a)=\floor{\log_3(x/2^a)}$. Since $3<4<9$, consecutive heights drop by $1$ or $2$, and $\beta(a^*)=0$. The first rectangle has width $1$ and height $h_1\in\{1,2\}$ and holds $h_1$ points. Every other rectangle has width $2$ and height $1$ or $2$ and holds $h_i+1$ points (Lemma~\ref{lem:rect}(iv)). The total is $\beta(0)+1+a^*/2=b^*+1+a^*/2$.
If $a^*$ is odd, use the columns $1,3,\ldots,a^*$. Now every rectangle has width $2$, and the first corner has height $\floor{\log_3(x/2)}=b^*-1+\delta$, so the total is $b^*+\delta+(a^*+1)/2$.
\end{proof}
\section{The upper bound}\label{sec:upper}
\begin{lemma}[Forced elements]\label{lem:forced}
Let $t\in\bints$, say $10\cdot3^b\le t<12\cdot3^b$ and $4^j\le t<\tfrac54 4^j$. Then every largest fork-free subset of $\grid(t)$ contains $2\cdot3^b$ and $4\cdot3^b$, and every largest fork-free subset of $\grid(t/5)$ contains $2\cdot3^b$. Consequently every fork-free subset of $\grid(t)\cup5\grid(t/5)$ has at most $R(t)+R(t/5)-1$ elements.
\end{lemma}
\begin{proof}
For $\grid(t)$ we have $a^*=2j$, $b^*=b+2$ and $\delta=0$, because $t<\tfrac54 4^j<2\cdot4^j$ and $9\cdot3^b\le t<18\cdot3^b$. Also $j\ge2$ since $t\ge10$. Thus $R(t)=j+b+3$. If $|W|=R(t)$, then \eqref{eq:rectbound} gives
\[
\sum_i d_i+(b+2-b_1)+\frac{2j-a_r}{2}=\frac12.
\]
Hence $b_1=b+2$. Since $t<2\cdot3^{b+2}$, the first corner is $(0,b+2)$, so $w_1=1$ and $d_1\ge\tfrac12$. Therefore $d_1=\tfrac12$, $a_r=2j$, and $d_i=0$ for $i\ge2$. In particular $r\ge2$, and $w_2=2$ gives $a_2=2$. As $h_1\in\{1,2\}$ we have $b_2\in\{b,b+1\}$. The bound $4\cdot3^{b_2}\le t<12\cdot3^b$ gives $b_2=b$, so $4\cdot3^b\in W$. The rectangle $\rect_2$ has width $2$, height $h_2\in\{1,2\}$ and holds $h_2+1$ points. If $h_2=1$ it is $\{(1,b),(2,b)\}$. If $h_2=2$, the only antichain of size two avoiding the corner is $\{(1,b),(2,b-1)\}$. Either way $2\cdot3^b\in W$.
For $u=t/5$ we have $2\cdot3^b\le u<\tfrac{12}5 3^b$ and $2^{2j-3}<4^j/5\le u<2^{2j-2}$, so $a^*=2j-3$, $b^*=b$, $\delta=1$ and $R(u)=j+b$. For a largest $W'$, equality holds in $|W'|\le b^*+1+(a^*+1)/2$, so every rectangle has width $2$ and the first corner is $(1,b)$, that is, $2\cdot3^b\in W'$. If a fork-free subset of $\grid(t)\cup5\grid(t/5)$ attained $R(t)+R(t/5)$, it would contain $2\cdot3^b$, $4\cdot3^b$ and $5\cdot2\cdot3^b$, and $2\cdot3^b$ would divide the other two.
\end{proof}
\begin{lemma}\label{lem:disjoint}
$\bints\cap5\bints=\varnothing$.
\end{lemma}
\begin{proof}
$\bints\subseteq G:=\bigcup_j[4^j,\tfrac54 4^j)$, and $5G=\bigcup_j[5\cdot4^j,\tfrac{25}4 4^j)$. The interval $[5\cdot4^j,\tfrac{25}4 4^j)$ starts exactly where $[4^{j+1},5\cdot4^j)$ ends and lies below $4^{j+2}$, so $G\cap5G=\varnothing$.
\end{proof}
\begin{proposition}\label{prop:upper}
For every positive integer $n$, $f(n)\le U(n)$.
\end{proposition}
\begin{proof}
Let $A\subseteq\{1,\ldots,n\}$ be fork-free. For $(m,6)=1$ the class $\{ms:s\in\grid(n/m)\}$ meets $A$ in a set of the form $mW_m$ with $W_m\subseteq\grid(n/m)$ fork-free, so $|A|\le\sum_m R(n/m)$ by Theorem~\ref{thm:grid}. Group the classes into chains $m=m_0 5^k$ with $(m_0,30)=1$. If $t=n/m\in\bints$, then $t\ge10$ and, after division by $m$, the part of $A$ in the classes $m$ and $5m$ is a fork-free subset of $\grid(t)\cup5\grid(t/5)$. Lemma~\ref{lem:forced} forces a loss of one element there. By Lemma~\ref{lem:disjoint}, $n/m$ and $n/(5m)$ are never both in $\bints$, so the pairs of classes used for different losses are disjoint and the losses add up.
\end{proof}
\section{The construction}\label{sec:lower}
\subsection{Parity-restricted grid sets}
Say that $2^a3^b$ has parity $a\bmod 2$. For $p\in\{0,1\}$ and real $z\ge0$ let
\begin{equation}
\begin{aligned}
W_p(z)={}&\{s\in\langle2,3\rangle:z/40$ define the target
\begin{equation}
k_\epsilon(u)=R(u)-\epsilon\one_\bints(5u).\label{eq:target}
\end{equation}
We define states $(p_\epsilon(u),z_\epsilon(u))\in\{0,1\}\times\Q_{\ge0}$ for rational $u>0$ by recursion. For $u<1$ the state is $(0,0)$. For $u\ge1$, let the two children be $(p_5,z_5)=(p_1(u/5),z_1(u/5))$ and $(p_7,z_7)=(p_\epsilon(u/7),z_\epsilon(u/7))$. For a trial parity $p$ whose level set for $k_\epsilon(u)$ is nonempty, put
\begin{equation}
\zeta_p=\max\left\{\frac34u,\lambda_p(k_\epsilon(u)),\gamma(p,p_5)z_5,\gamma(p,p_7)z_7\right\},
\qquad
\gamma(p,p')=\begin{cases}4,&p=p',\\6,&p\ne p'.\end{cases}\label{eq:zeta}
\end{equation}
The parity $p$ is available if that level set is nonempty and
\begin{equation}
\zeta_p\le u,\qquad \zeta_p<\mu_p(k_\epsilon(u)).\label{eq:available}
\end{equation}
Try first $p=a^*(u)\bmod2$, where $a^*(u)=\floor{\log_2u}$, and then the other parity. If some parity is available, the state is the first available parity $p$ together with $z_\epsilon(u)=\zeta_p$, and we say that the recursion succeeds at $(u,\epsilon)$.
\begin{lemma}\label{lem:construct}
Suppose the recursion succeeds at every rational $u\ge1$ for both values of $\epsilon$. Then $f(n)\ge U(n)$ for every $n$, with an extremal set inside $(n/8,n]$.
\end{lemma}
\begin{proof}
Write each integer uniquely as $ghs$ with $(g,210)=1$, $h$ a product of powers of $5$ and $7$, and $s\in\langle2,3\rangle$. For each pair $(g,h)$ with $gh\le n$, let $u=n/(gh)$ and $\epsilon=\one_{[5\mid h]}$, and select the fiber $ghW_{p_\epsilon(u)}(z_\epsilon(u))$. Let $A_n$ be the union of the fibers.
Since $\tfrac34u\le z_\epsilon(u)\le u$, the selected elements of the fiber lie in $(u/8,u]$ after division by $gh$, so $A_n\subseteq(n/8,n]$. If $x\mid y$ are distinct elements of $A_n$, then $y/x\in\{2,\ldots,7\}$. Ratios $2,3,4,6$ keep $(g,h)$ fixed, and each fiber is fork-free by Lemma~\ref{lem:parity}. A ratio $d\in\{5,7\}$ would mean that the same $s$ lies in the fiber $(g,h)$ and in its child fiber $(g,dh)$, whose argument is $u/d$ and whose type is $1$ for $d=5$ and $\epsilon$ for $d=7$. These are exactly the child states used in \eqref{eq:zeta}.
Let $p$ be the parent's parity and $p_d$ the child's. An element of the child of parity $1-p_d$ is at most $z_d/2\le u/(2d)\zeta_p/4\ge z_d$. If $p_d\ne p$, then $s>\zeta_p/6\ge z_d$. So no such $s$ exists. Hence every divisibility relation in $A_n$ lies inside a fiber, and $A_n$ is fork-free.
The fiber $(g,h)$ has $h_p(\zeta_p)=k_\epsilon(u)$ elements. Writing $m=gh$, the total is
\[
\sum_{\substack{m\le n\\(m,6)=1}}\left(R(n/m)-\one_{[5\mid m]}\one_\bints(5n/m)\right).
\]
In the second sum put $m=5m'$. Since every element of $\bints$ exceeds $5$, the range $m'\le n/5$ may be extended to $m'\le n$, giving exactly $U(n)$.
\end{proof}
Thus each forced loss of Section~\ref{sec:upper} is assigned to the upper of the two powers-of-five layers involved.
\subsection{The finite verification}
\begin{proposition}\label{prop:success}
The recursion succeeds at every rational $u\ge1$ for $\epsilon=0$ and $\epsilon=1$.
\end{proposition}
The proof has two computer-verified ingredients.
\emph{The base range.} Let $T_0=2\cdot7^7=1{,}647{,}086$. On $[1,T_0)$ the recursion was evaluated exactly. There are $109$ pieces for $\epsilon=0$ and $108$ for $\epsilon=1$. Each piece is a half-open interval with rational endpoints on which the state is a fixed parity and a cutoff $z=au+b$ with $a,b\in\Q$. The table is verified by refining it at every breakpoint into $306$ and $305$ intervals. On each interval one checks, with exact rational arithmetic, the target size, the four lower bounds in \eqref{eq:zeta}, the upper bounds in \eqref{eq:available}, which term of the maximum is active, and the priority rule. For pieces using the second parity, one also checks that the preferred parity is unavailable. The check covers all $u$ in the interval.
\emph{A finite closure.} Normalize the root argument $u$ to $1$. The powers of $4$ and $3$ below $u$ are encoded by the two parameters
\[
X=4^{\floor{\log_4u}}/u\in(1/4,1],\qquad
Y=3^{\floor{\log_3u}}/u\in(1/3,1],
\]
which the finite statement allows to vary independently. Its nodes are $\nu=(i,j)$ with $i,j\ge0$ and $i+j\le D$. The node $\nu$ has normalized argument $v_\nu=5^{-i}7^{-j}$, type $\epsilon_\nu=1$ if $i>0$ and $\epsilon_\nu=\epsilon$ if $i=0$, and children $(i+1,j)$ and $(i,j+1)$. At a node, let $L_4$ be the largest element of $X4^\Z$ not exceeding $v_\nu$, and $L_3$ the largest element of $Y3^\Z$ not exceeding $v_\nu$. Put $P=\one_{[v_\nu\ge2L_4]}$ and $\Delta=\one_{[v_\nu\ge2L_3]}$, and let $L'_4,L'_3$ be the analogous quantities at $5v_\nu$. The obstruction bit
\[
Q=\epsilon_\nu\one_{\left[5v_\nu<\frac54L'_4,\ \frac{10}9L'_3\le5v_\nu<\frac43L'_3\right]}
\]
encodes $\epsilon_\nu\one_\bints(5u_\nu)$, where $u_\nu=uv_\nu$. The errors $e_0=Q-P\Delta$ and $e_1=Q-(1-P)(1-\Delta)$ measure how many levels each parity must drop from its value at $v_\nu$. The most recent jumps of $h_0$ at or below $v_\nu$ are $(a,b)=(L_4,L_3)$. Those of $h_1$ are $a=2L_4$ or $L_4/2$ according as $P=1$ or $0$, and $b=2L_3$ or $\tfrac23L_3$ according as $\Delta=1$ or $0$. The window of parity $p$, which is the normalized set of admissible cutoffs, is
\begin{itemize}
\item empty if $e_p=-1$;
\item $[\max(a,b),v_\nu]$ if $e_p=0$;
\item $[\max(a/4,b),\max(a,b))$ if $e_p=1$ and $a>b$, and $[\max(a,b/3),\max(a,b))$ if $e_p=1$ and $a\le b$.
\end{itemize}
Each window endpoint is a rational-linear expression in $(X,Y)$ on each of finitely many explicitly described pieces.
\begin{lemma}[Closure]\label{lem:cutoff-check}
For $D=5$ and $\epsilon\in\{0,1\}$, the following system in the unknowns $X,Y$ and, for every node $\nu$, a parity $\pi_\nu$ and a cutoff $\zeta_\nu\in\Q$, is unsatisfiable.
\begin{itemize}
\item Each leaf ($i+j=D$) has $\zeta_\nu$ in the window of $\pi_\nu$ and $\zeta_\nu\ge\tfrac34v_\nu$.
\item Each node of depth $1,\ldots,D-1$ has the state produced by \eqref{eq:zeta}, \eqref{eq:available} and the priority rule from its children's states, and some parity is available there.
\item At the root, neither parity is available.
\end{itemize}
\end{lemma}
The system has two real parameters, $21$ nodes and Boolean choices, and all its coefficients are rational. No logarithms or floating-point numbers occur. For $D=7$ ($36$ nodes) the corresponding system was proved unsatisfiable independently by Z3~\cite{Z3} and by cvc5~\cite{cvc5}. For $D=3,4$ it is satisfiable. For $D=5$ it is unsatisfiable, and the refutation is replayed in the formal proof as a certificate checked by the Lean kernel (Section~\ref{sec:lean}).
\begin{proof}[Proof of Proposition~\ref{prop:success}]
Use strong induction on $\floor u$ for both values of $\epsilon$. Below $T_0$ we use the table. Let $u\ge T_0$. Every proper descendant has smaller integer part than $u$, so its state exists by induction. Every node of depth at most $7$ below $u$ has argument $u_\nu=u5^{-i}7^{-j}\ge T_0/7^7=2$, and $5u_\nu\ge10$. For such arguments the normalized powers, windows and obstruction bits above coincide with the actual ones. Here $h_p(z)=k_{\epsilon_\nu}(u_\nu)$ and $z\le u_\nu$ exactly when $z/u$ lies in the corresponding window.
Assume that neither parity is available at $(u,\epsilon)$. Take $X,Y$ as above, and for every node of depth at most $5$ let $\pi_\nu$ be the actual parity and $\zeta_\nu$ the actual cutoff divided by $u$, wherever the state is used. The leaves and internal nodes satisfy their constraints because the recursion succeeds at the smaller arguments $u_\nu\le u/5$, and the root fails by assumption. This contradicts Lemma~\ref{lem:cutoff-check}.
\end{proof}
With Proposition~\ref{prop:upper} and Lemma~\ref{lem:construct}, this proves Theorem~\ref{thm:exact}. Independently of the formal proof, an exhaustive search confirms \eqref{eq:exact} for $n\le40$.
\section{The density and the coefficient series}\label{sec:density}
\begin{proof}[Proof of \eqref{eq:integral}]
The function $R$ is nondecreasing and right-continuous. It jumps only at points of $\langle2,3\rangle$, and each jump $\Delta R(s)$ is $0$ or $1$, because adding one point to a grid raises the largest fork-free size by at most one. Let $N_6(y)=\#\{m\le y:(m,6)=1,\ m\ge1\}=y/3+O(1)$. Then
\[
\sum_{\substack{m\le n\\(m,6)=1}}R(n/m)
=\sum_{s\in\langle2,3\rangle}\Delta R(s)N_6(n/s).
\]
After division by $n$, the terms are dominated by $2/s$, and $\sum_{s\in\langle2,3\rangle}1/s=3$. Dominated convergence therefore gives the limit
\(\tfrac13\sum_s\Delta R(s)/s=\tfrac13\int_1^\infty R(t)t^{-2}\,dt\).
For the $\bints$-term, each interval $[\alpha,\beta)$ of $\bints$ contributes $N_6(n/\alpha)-N_6(n/\beta)$. The intervals beyond any cutoff $M$ contribute at most $n/M+1$ in total. Hence $n^{-1}\#\{m:(m,6)=1,\ n/m\in\bints,\ m\ge1\}\to\tfrac13\int_\bints t^{-2}\,dt$. Finally, by \eqref{eq:R} and
\(\int_1^\infty\floor{\log_b t}t^{-2}\,dt=\sum_{k\ge1}b^{-k}=1/(b-1)\),
\[
\frac13\int_1^\infty\frac{R(t)}{t^2}\,dt
=\frac13\left(1+\frac13+\frac12+\int_\eints\frac{dt}{t^2}\right)
=\frac{11}{18}+\frac13\int_\eints\frac{dt}{t^2}.
\]
\end{proof}
\begin{proof}[Proof of \eqref{eq:series}]
Write $\eints=E_4\cap E_3$ with $E_4=\bigcup_j[2\cdot4^j,4^{j+1})$ and $E_3=\bigcup_b[2\cdot3^b,3^{b+1})$, and $\bints=B_3\cap B_4$ with $B_3=\bigcup_b[10\cdot3^b,12\cdot3^b)$ and $B_4=\bigcup_j[4^j,\tfrac544^j)$. For such an intersection, $\int t^{-2}\,dt$ is the sum over the jump points $x$ of its indicator of $\pm1/x$, positive where the set is entered and negative where it is left. At an endpoint of one factor at which the other factor is constant, the indicator jumps exactly when the point lies in the other factor.
The endpoints of $E_4$ and $E_3$ coincide only at $x=2$, where both begin and $\eints$ jumps once. The endpoints of $B_3$ and $B_4$ never coincide. Hence
\begin{align*}
\int_\eints\frac{dt}{t^2}
&=\sum_{k\ge0}\left(\frac{\one_{E_3}(2\cdot4^k)}{2\cdot4^k}-\frac{\one_{E_3}(4^k)}{4^k}\right)
+\sum_{k\ge0}\left(\frac{\one_{E_4}(2\cdot3^k)}{2\cdot3^k}-\frac{\one_{E_4}(3^k)}{3^k}\right)-\frac12,\\
\int_\bints\frac{dt}{t^2}
&=\sum_{k\ge0}\left(\frac{\one_{B_3}(4^k)}{4^k}-\frac{\one_{B_3}(\tfrac544^k)}{\tfrac544^k}\right)
+\sum_{k\ge0}\left(\frac{\one_{B_4}(10\cdot3^k)}{10\cdot3^k}-\frac{\one_{B_4}(12\cdot3^k)}{12\cdot3^k}\right).
\end{align*}
Here the terms $\one_{E_3}(1)$ and $\one_{E_4}(1)$ vanish. Let $t=[4^k]_3$ and $s=[3^k]_4$. Elementary manipulation of mantissas gives
\begin{itemize}
\item $\one_{E_3}(2\cdot4^k)=\one_{[t<3/2]}$ and $\one_{E_3}(4^k)=\one_{[t\ge2]}$;
\item $\one_{B_3}(4^k)=\one_{[10/9\le t<4/3]}$;
\item $\one_{B_3}(\tfrac544^k)=\one_{[t<16/15\text{ or }t\ge8/3]}$ for $k\ge1$, while for $k=0$ the right side is $1$ but $5/4\notin B_3$;
\item $\one_{E_4}(2\cdot3^k)=\one_{[s<2]}$ and $\one_{E_4}(3^k)=\one_{[s\ge2]}$;
\item $\one_{B_4}(10\cdot3^k)=\one_{[8/5\le s<2]}$ and $\one_{B_4}(12\cdot3^k)=\one_{[4/3\le s<5/3]}$.
\end{itemize}
Multiplying by $60$ therefore gives $60(I-J)=\Sigma_4+\Sigma_3-30-48$, where $I,J$ are the two integrals and
\begin{align*}
\varphi(t)&=30\one_{[t<3/2]}-60\one_{[t\ge2]}-60\one_{[10/9\le t<4/3]}+48\one_{[t<16/15\text{ or }t\ge8/3]},\\
\psi(s)&=30\one_{[s<2]}-60\one_{[s\ge2]}-6\one_{[8/5\le s<2]}+5\one_{[4/3\le s<5/3]},
\end{align*}
which are the functions of Table~\ref{tab:steps}. Here $\Sigma_4=\sum_k\varphi([4^k]_3)4^{-k}$ and $\Sigma_3=\sum_k\psi([3^k]_4)3^{-k}$. Since $180\cdot 11/18=110$, we obtain $180c=110+60(I-J)=32+\Sigma_4+\Sigma_3$.
\end{proof}
\begin{remark}
The value $c=0.67296\ldots$ lies in Lebensold's interval $[0.6725,0.6736]$ and above the lower bound $c\ge0.6729$ reported by Davis.
\end{remark}
\section{Returns of the rotation and a small nonzero linear form}\label{sec:returns}
\subsection{Rotation coordinates and jumps}
Let $\alpha=\log4/\log3=\log_34$, which is irrational because no positive power of $4$ is a power of $3$. For $k\in\Z$ we have $[4^k]_3=3^{\{k\alpha\}}$ and $[3^k]_4=4^{\{k/\alpha\}}$. Let $\widetilde{\varphi}(x)=\varphi(3^{\{x\}})$ and $\widetilde{\psi}(y)=\psi(4^{\{y\}})$ be the corresponding $1$-periodic, right-continuous step functions. Their jumps on the circle, at the points $\theta$ listed through $3^\theta$ and $4^\theta$ respectively, are
\[
\begin{array}{c|rrrrrrr}
3^\theta&1&16/15&10/9&4/3&3/2&2&8/3\\
\text{jump of }\widetilde\varphi&+90&-48&-60&+60&-30&-60&+48
\end{array}
\]
and
\[
\begin{array}{c|rrrrr}
4^\theta&1&4/3&8/5&5/3&2\\
\text{jump of }\widetilde\psi&+90&+5&-6&-5&-84.
\end{array}
\]
Jump points related by the rotation are grouped into orbits. For $\widetilde\varphi$ we use the representatives $\theta_1,\ldots,\theta_4=\log_3(1,2,\tfrac95,\tfrac{10}9)$, with the logarithm applied coordinatewise. Then
\begin{align*}
\log_3\tfrac43&=\theta_1+\alpha-1,&\log_3\tfrac32&=\theta_2-\alpha+1,\\
\log_3\tfrac83&=\theta_2+\alpha-1,&\log_3\tfrac{16}{15}&=\theta_3+2\alpha-3.
\end{align*}
For $\widetilde\psi$ we use $\theta'_1,\ldots,\theta'_4=\log_4(1,2,\tfrac85,\tfrac54)$, with $\log_4\tfrac43=\theta'_1+1-1/\alpha$ and $\log_4\tfrac53=\theta'_4+1-1/\alpha$.
Weighting each jump by the power of $4$ (respectively $3$) corresponding to its orbit shift gives the orbit coefficients
\[
(C_1,C_2,C_3,C_4)=(105,-168,-3,-60),\qquad (D_1,D_2,D_3,D_4)=(105,-84,-6,-15).
\]
For example, $C_1=90+60/4$, $C_2=-30\cdot4-60+48/4$, $D_1=90+5\cdot3$ and $D_4=-5\cdot3$. Each list represents four distinct orbits for its own rotation. No two elements of either list of mantissas have ratio $4^a3^b$ with $a,b\in\Z$. The two lists share the representatives $1$ and $2$.
\subsection{Brackets}
\begin{lemma}\label{lem:brackets}
There are infinitely many quadruples of positive integers $(p,q,P,Q)$ with
\[
qP-pQ=1,\qquad q\le Q,\qquad \delta:=q\alpha-p>0,\qquad 0<\delta':=P-Q\alpha<\delta.
\]
Along them $Q\to\infty$ and $\delta\le1/Q\to0$. Put $L=P\log3$. Then $p\log3,q\log4L-\log3$. Moreover $\|m\alpha\|\ge\delta$ for $1\le mn\alpha-1$, so $(k'-k)\log3>L-2\log3\ge L/2$.
For (ii), otherwise $\pm\alpha$ or $0$ would be within $\delta$ of $\theta_i-\theta_j$ modulo $1$, for one of finitely many pairs. For $i\ne j$ this fails once $\delta$ is small, because the representatives lie in distinct orbits. For $i=j$ and $|k-k'|=1$, the irrationality of $\alpha$ gives the same exclusion.
For (iii), by (i) each family has at most three events in a window of length $1.01L$, so at most $48$ events are relevant. Among the $49$ disjoint candidate intervals
\[
[4L+\ell L/50,4L+\ell L/50+L/100],\qquad 1\le\ell\le49,
\]
at least one is free of them. The choice of $T_2$ is the same. For (iv), the omitted events have times at least $T+L/100$, spaced by $L/2$ within each family, and all coefficients satisfy $|d|\le168$. So the omitted part is at most
\[
16\cdot168\,e^{-T-L/100}(1-e^{-L/2})^{-1}\le e^{-T-L/200}
\]
for large $L$.
\end{proof}
\begin{proposition}[Two truncations differ]\label{prop:distinct}
For all sufficiently late brackets, $S(T_1)\ne S(T_2)$.
\end{proposition}
\begin{proof}
Write $S=D+G$, where $D$ collects the events with denominator $4^k$ and $G$ those with denominator $3^k$. Every $G(T)$ is $2$-adically integral. In $D(T)$, the two events of a visit $H_i(k)=1$ combine to a term with numerator $C_i(3^p-1)$ if both are retained, and $C_i3^p$ if only the earlier one, $3^p/4^k$, is retained. Note that $(v_2(C_1),v_2(C_2),v_2(C_3),v_2(C_4))=(0,3,0,2)$.
At $T_1<5L$, every retained dyadic event has $k\log4<5L+p\log3\le6L$, so either $D(T_1)=0$ or $v_2(D(T_1))\log2>-6L$. At $T_2$, Lemma~\ref{lem:brackets} gives a visit $k$ with $T_2-2L2Q\ge q+Q$. Let $k^*$ be the largest retained dyadic index. Then $k^*\log4>8L$, and by Lemma~\ref{lem:events}(ii) all other retained indices are at most $k^*-2$.
If the unshifted event at $k^*$ is retained, all retained indices have both events retained. Then $D(T_2)=(3^p-1)\sum C_i4^{-k}$, where the term with $k=k^*$ has strictly smallest valuation. Using $v_2(3^p-1)\log2\le p\log3\le L$ gives $v_2(D(T_2))\log2\le L+3\log2-k^*\log4<-6L$. Otherwise the $k^*$ term has numerator $C_i3^p$ and again has strictly smallest valuation, so $v_2(D(T_2))\log2\le3\log2-k^*\log4<-6L$. In both cases $D(T_2)-D(T_1)$ has valuation less than $-6L/\log2<0$. It cannot be cancelled by the $2$-adically integral number $G(T_2)-G(T_1)$.
\end{proof}
\begin{corollary}\label{cor:small}
Suppose $c\in\Q$, and put $z=180c-32$. For all sufficiently late brackets there are $T\in\{T_1,T_2\}$, an integer $m\le404$, $\{2,3\}$-units $u_1,\ldots,u_m\ge e^{-T}$ and coefficients $d_1,\ldots,d_m$ in the finite set $\{\pm z,\pm3,\pm6,\pm15,\pm60,\pm84,\pm105,\pm168\}$ such that
\[
E:=\sum_{i=1}^m d_i u_i-N
\quad\text{satisfies}\quad
0<|E|\le e^{-T-L/200}
\quad\text{and}\quad
H(N:u_1:\cdots:u_m)\le e^{27L}.
\]
\end{corollary}
\begin{proof}
Let $E(T)=(4^q-1)(3^p-1)z-N-S(T)$. By Proposition~\ref{prop:distinct}, $E(T_1)-E(T_2)=S(T_2)-S(T_1)\ne0$, so some $E(T)$ is nonzero, and by \eqref{eq:return} and Lemma~\ref{lem:events}(iv) it is at most $e^{-T-L/200}$ in absolute value.
Expanding the head gives the units $4^q3^p,4^q,3^p,1$ with coefficients $z,-z,-z,z$. The retained events contribute their units with the negatives of their coefficients. Each family has at most $2\cdot11+3$ retained events because the times lie in $[-L,11L)$ and are $L/2$-separated. Thus $m\le4+16\cdot25=404$. All denominators divide $4^{\floor{12L/\log4}}3^{\floor{12L/\log3}}\le e^{24L}$, and all coordinates, including $N$, are at most $366e^{2L}$ in absolute value. Hence $H(N:u_1:\cdots:u_m)\le366e^{26L}\le e^{27L}$ for large $L$.
\end{proof}
\section{A three-place Subspace Theorem and the proof of irrationality}\label{sec:subspace}
\subsection{The covering theorem}
\begin{theorem}\label{thm:subspace}
Let $d\ge2$, let $A\in\mathrm{GL}_d(\Q)$, and let $c_{v,i}$ ($v\in\{\infty,2,3\}$, $1\le i\le d$) be real numbers with $c_{2,i},c_{3,i}\le0$ and $\sum_{v,i}c_{v,i}<0$. There is a finite set of proper linear subspaces of $\Q^d$ such that, for every real $q\ge0$, every $x\in\Z^d$ with
\begin{equation}
|(Ax)_i|\le e^{c_{\infty,i}q},\qquad |x_i|_2\le e^{c_{2,i}q},\qquad
|x_i|_3\le e^{c_{3,i}q}\qquad(1\le i\le d)\label{eq:threeplace}
\end{equation}
lies in one of them.
\end{theorem}
\begin{remark}
Theorem~\ref{thm:subspace} is a special case of the $p$-adic Subspace Theorem of Schlickewei~\cite{Schlickewei}, which extends Schmidt's theorem~\cite{SchmidtNorm,SchmidtBook}. See also \cite{SchmidtDio,Bombieri,EvertseSchlickewei,EvertseFerretti}. Indeed, let $M=\max(0,\max_i c_{\infty,i})$ and $\rho=-\sum c_{v,i}$. If $M=0$ the solutions are bounded, hence finite in number. Otherwise, for $C\ge1$ sufficiently large we have $\max_i|x_i|\le Ce^{Mq}$, so the solutions of \eqref{eq:threeplace} with $\max_i|x_i|\ge C^2$ satisfy
\[
\prod_{v\in\{\infty,2,3\}}\prod_{i=1}^d |L_{v,i}(x)|_v
\le e^{-\rho q}\le\left(\max_i|x_i|\right)^{-\rho/(2M)},
\]
with $L_{\infty,i}(x)=(Ax)_i$ and $L_{2,i}(x)=L_{3,i}(x)=x_i$. This is the inequality of the Subspace Theorem.
\end{remark}
For a rational linear form $\ell(x)=\sum_i a_ix_i$ with $a_k\ne0$, put
\[
\Phi_{\ell,k}(x)=|\ell(x)|\prod_{i\ne k}|x_i|\prod_i |x_i|_2|x_i|_3.
\]
\begin{theorem}[One-form covering]\label{thm:oneform}
Let $n\ge2$, $\ell$ and $k$ be as above, and $\varepsilon>0$. There are finitely many nonzero $a^{(1)},\ldots,a^{(s)}\in\Q^n$ such that every nonzero $x\in\Z[1/6]^n$ with $\Phi_{\ell,k}(x)0$. There is $C>0$ such that for all $N\in\Z$, all positive $\{2,3\}$-units $u_1,\ldots,u_m$, and all $0e^{\gamma q}$, where $\gamma=\rho/(2d(d-1))$. A rounding lemma of Davenport type produces an integral basis $h_1,\ldots,h_d$ of $\Lambda_q$ with good local bounds such that all solutions lie in $\operatorname{span}(h_1,\ldots,h_k)$.
\item \emph{Compound reduction.} Passing to the $(d-k)$th compound matrix, the $\binom dk-1$ vectors complementary to the prefix satisfy a three-place system of the same shape, with a profile of negative sum. So it suffices to show that the hyperplanes they span take only finitely many values. A height-free recovery map returns from compound hyperplanes to the prefix subspaces.
\item \emph{Height dichotomy.} A hyperplane spanned by solutions at parameter $q$ either belongs to a finite exceptional family, indexed by support patterns, or has a normal vector of logarithmic height at least $\rho q/4-O(1)$. The proof uses only the elementary inequality $|z|\,|z|_2|z|_3\ge1$ for nonzero integers $z$.
\item \emph{Roth's lemma.} For $\beta=a/b\in\Q$ in lowest terms let $h(\beta)=\log\max(|a|,|b|)$, and let $\|P\|_1$ be the sum of the absolute values of the coefficients of $P$. If $0\ne P\in\Z[t_1,\ldots,t_m]$ has $\deg_{t_i}P\le r_i$, $r_{i+1}\le\theta r_i$ with $\theta=\eta^{2^{m-1}}$ and $0<\eta\le\tfrac12$, and $\log\|P\|_1+4mr_1\le\theta r_i h(\beta_i)$ for all $i$, then the index of $P$ at $\beta\in\Q^m$ with weights $r$ is at most $2m\eta$. The proof uses generalized Wronskians, as in \cite{Roth,Goel}, and is extended to products of rational hyperplanes.
\item \emph{Auxiliary polynomial.} Siegel's lemma, in the form available in Mathlib, together with an exact second-moment count of monomials, produces a nonzero integer multihomogeneous polynomial that is balanced with respect to the forms at all three places and has controlled coefficients.
\item \emph{Contradiction.} Suppose solutions spanned hyperplanes of heights growing linearly in $q$ along an unbounded set of parameters. Choose $m$ well-separated parameters and degrees $r_h\approx D/q_h$. Roth's lemma and a grid nonvanishing lemma yield an integer point at which a low-order derivative of the auxiliary polynomial is a nonzero integer. Its three local sizes multiply to less than $1$, which is impossible. With the dichotomy, only finitely many hyperplanes occur for each profile, and finitely many profiles suffice.
\item \emph{Assembly.} The recovery map gives finitely many prefix subspaces, and bounded parameters give finitely many integer points. This proves Theorem~\ref{thm:subspace}.
\end{enumerate}
The argument is ineffective. Thus Theorem~\ref{thm:irrational} provides no irrationality measure for $c$.
\section{The Lean formalization}\label{sec:lean}
\subsection{The statement}
The file \path{FormalConjectures/ErdosProblems/1062.lean} in Formal Conjectures~\cite{Formal} defines fork-freeness and the extremal function by
\begin{quote}\small\ttfamily
def ForkFree (A : Set $\N$) : Prop :=\\
\hspace*{1em}$\forall$a $\in$ A, (\{b | b $\in$ A \textbackslash{} \{a\} $\land$ a | b\} : Set $\N$).Subsingleton\\[.35em]
noncomputable def f (n : $\N$) : $\N$ :=\\
\hspace*{1em}open scoped Classical in\\
\hspace*{1em}Nat.findGreatest (fun k => $\exists$ A $\subseteq$ Set.Icc 1 n,\\
\hspace*{2em}ForkFree A $\land$ A.ncard = k) n
\end{quote}
and states the problem as
\begin{quote}\small\ttfamily
theorem erdos\_1062.parts.ii :\\
\hspace*{1em}($\exists$ l, Tendsto (fun n => (f n : $\R$) / n) atTop ($\mathcal N$ l)\\
\hspace*{2em}$\land$ Irrational l) $\leftrightarrow$ answer(sorry)
\end{quote}
The conjectures.io task~\cite{Conjectures} asks for a proof of this statement with the answer \texttt{True}, as the declaration \texttt{Bounty.target}. The original file ends with
\begin{verbatim}
theorem target : fcTypeOfName% "Erdos1062.erdos_1062.parts.ii" :=
target_of_integer_oneForm_cover
(integer_oneForm_cover_of_three_place
rational_three_place_subspace_cover)
\end{verbatim}
The development first shows that \texttt{Nat.findGreatest} computes the maximum size, and it never uses the imported open statement as a proof.
\subsection{Organization}
The file has 74,210 lines and 7,702 declarations. It is assembled from 368 components, each labelled in the source with the SHA-256 hash of the module it came from. Table~\ref{tab:components} shows how the components correspond to the sections of this paper.
\begin{table}[tbp]
\caption{Components of the formal proof.}\label{tab:components}
\centering
\small
\begin{tabular}{@{}>{\raggedright\arraybackslash}p{.33\linewidth}>{\raggedright\arraybackslash}p{.51\linewidth}r@{}}
\hline
Content & Representative components & Lines\\\hline
Grid theorem, upper bound, construction, recursion, bridge to the closure (\S\S\,2--4) &
\texttt{GridBridge}, \texttt{GlobalUpper}, \texttt{CutoffRecursion}, \texttt{ClosureInduction}, \texttt{GlobalExact} & 7,816\\
Base-range table and its checks (\S\,4) &
\texttt{BaseTableData}, \texttt{PolicyBaseIntervalsCompact} & 9,976\\
Closure certificate and its checkers (Lemma~\ref{lem:cutoff-check}) &
\texttt{PolicyBitsetRUP}, \texttt{PolicyLinearCertificate}, \texttt{ClosureInputReflection} & 32,649\\
Density, series, returns, nonvanishing, rigidity (\S\S\,5--7) &
\texttt{CoefficientSeries}, \texttt{ReturnDifferenceIdentity}, \texttt{ReturnTruncationNonzero}, \texttt{OneFormRigidity} & 8,469\\
Roth's lemma (\S\,7.4, step 6) &
\texttt{GeneralizedWronskian}, \texttt{IntegerRothTheorem} & 3,568\\
Theorem~\ref{thm:subspace} (\S\,7.4) &
\texttt{LatticeSuccessiveMinima}, \texttt{BalancedAuxiliaryPolynomial}, \texttt{RationalThreePlaceSubspaceTheorem} & 11,732\\\hline
\end{tabular}
\end{table}
\subsection{Certifying the finite computations}
The base-range table is stored as 217 affine pieces and checked on the 611 refined intervals. Each check is a closed proposition about rational numbers, settled by kernel evaluation (\texttt{decide +kernel}).
For the closure, the failure system in Lemma~\ref{lem:cutoff-check} is stated in Lean as an explicit proposition. A lemma derives it from the corresponding depth-seven hypothesis, and that hypothesis is proved, in turn, to follow from a failure of the actual recursion. Thus the correctness of the encoding itself is proved. The relevant declarations are \texttt{ClosureRawHypothesis5} and \texttt{closureRawHypothesis5\_of\_raw}.
The formula is a typed expression DAG over the rationals. A refutation found with Z3 was decomposed into four kinds of steps:
\begin{itemize}
\item Boolean circuit clauses defining the DAG's gates;
\item instances of 190 rewrite schemas, each proved once in Lean;
\item arithmetic lemmas, each justified by a sparse Farkas certificate with rational coefficients;
\item a propositional refutation of the resulting clause set in reverse unit propagation (RUP) form~\cite{GoldbergNovikov,DRAT}, produced with the SAT solver Glucose~\cite{Glucose}.
\end{itemize}
The arithmetic lemmas were reduced by a deletion-based minimal unsatisfiable subset search, and solver seeds were chosen to minimize the kernel cost of the whole certificate. Every checker is an ordinary Lean function with a soundness theorem, and every certificate check is closed by kernel evaluation. The depth-five closure has 21 nodes and 59 assertions, against 36 and 102 at depth seven. The smaller depth roughly halves the certificate, which was necessary to meet the time limit.
\subsection{Constraints of the challenge and verification}
For the pinned conjectures.io task, the submission is the body of a single file placed between a trusted header, which imports the Formal Conjectures statement and a small support library, and a trusted footer. The body may not contain imports, \texttt{set\_option}, attributes, instances, custom syntax, \texttt{native\_decide} or axioms. It must fit in 10 MiB, and building, exporting and replaying it must finish within the task's verification timeout of 3,600 seconds. The kernel may use only \texttt{propext}, \texttt{Quot.sound} and \texttt{Classical.choice}.
Because declaration attributes and instance commands are unavailable, the development passes the relevant lemmas and instances explicitly. Every proof except the final one is declared with \texttt{def} in place of \texttt{theorem}. Lean elaborates theorem bodies as parallel tasks. In our measurements each pending task reserved about 1 GiB of address space, which for thousands of declarations would exceed the checker's 64 GiB address-space limit. Definitions are elaborated sequentially.
The submitted body has 4,965,602 bytes and 752,155 tokens as counted by the challenge's static scanner, whose limit is $10^6$. Its SHA-256 hash begins \texttt{2ebc87b0}. We ran the verification pipeline locally with the toolchain pinned by the challenge (Lean 4.33.1). The build (\texttt{lake build}) took 1,647 s of wall time (1,872 s of CPU time, 11.8 GB resident memory). Exporting the challenge and the solution with \texttt{lean4export}~\cite{LeanExport} took 7 s and 51 s. Replaying the exported solution in a fresh kernel with the comparator~\cite{Comparator} took 1,362 s. The total is 3,067 s. The comparator confirmed that the target statement matches the challenge, and that the proof uses only the three permitted axioms. The file contains no \texttt{sorry}.
\subsection{Trusted base and public reproduction}
A reader who accepts the formal proof must trust the Lean kernel, the Formal Conjectures statement, the challenge's header and footer, and the exporter and comparator used for the challenge replay. The SMT and SAT solvers, the Python scripts that produced the tables and certificates, and all intermediate data are untrusted in this verification: their outputs are checked in the kernel.
The later public prize submission links the \href{https://github.com/JENW1N/complete-math-solutions/blob/ab42bf613bd773f78a0350c5869dcccfaab1faed/Solutions/Erdos1062Full.lean}{explicit finite-formula and limit wrapper}, with stated endpoint \texttt{Erdos1062Full.full\_scope}, and the corresponding \href{https://github.com/JENW1N/complete-math-solutions/blob/dbda7c6fd642ecebfe46dbd674e5e8c224850254/verification/erdos1062-full.json}{clean build and target axiom record}. The wrapper exposes the exact arithmetic identity for every natural $n$, including the empty sum for $n=0$, together with convergence and irrationality.
\section{Concluding remarks}
\begin{enumerate}
\item Theorem~\ref{thm:exact} shows that the extremal structure is governed by the two-prime grid and one family of forced conflicts between adjacent powers-of-five layers. The finite closure behind the lower bound is small at depth five, with 21 nodes and two real parameters. A short conceptual proof of Lemma~\ref{lem:cutoff-check} would make the theorem computer-free.
\item The irrationality proof never uses irrationality of the two series in \eqref{eq:series} separately, and it needs no assumption on the continued fraction of $\log4/\log3$. It uses the Subspace Theorem only for linear forms in $\{2,3\}$-integers, and no finiteness theorem for $S$-unit equations.
\item Davis's theorem~\cite{Davis} shows that the extremal densities for other finite families of forbidden divisibility configurations are computable as well. The method of this paper, namely exact grid analysis followed by returns of a rotation and the Subspace Theorem, may decide irrationality in some of those cases.
\end{enumerate}
\section*{Acknowledgements}
The mathematical arguments in this paper were developed with extensive assistance from AI systems, namely OpenAI's Codex and Anthropic's Claude. These systems were used to explore and check the arguments, to write the programs, solver encodings and certificate generators behind the finite verification, to write and optimize the Lean formalization, and to prepare this manuscript. The authors are responsible for all mathematical content. We thank the developers of Lean, Mathlib, Formal Conjectures and conjectures.io, whose infrastructure made the formal verification possible.
\begin{thebibliography}{26}
\bibitem{Glucose} G. Audemard and L. Simon, Predicting learnt clauses quality in modern SAT solvers, in: \emph{Proc. 21st International Joint Conference on Artificial Intelligence} (IJCAI 2009), 399--404.
\bibitem{cvc5} H. Barbosa et al., cvc5: a versatile and industrial-strength SMT solver, in: \emph{Tools and Algorithms for the Construction and Analysis of Systems} (TACAS 2022), Lecture Notes in Comput. Sci. 13243, Springer, 2022, 415--442.
\bibitem{Bloom} T. F. Bloom, \emph{Erd\H{o}s Problem \#1062}, \url{https://www.erdosproblems.com/1062}. Accessed 21 September 2026.
\bibitem{Bombieri} E. Bombieri and W. Gubler, \emph{Heights in Diophantine Geometry}, New Mathematical Monographs 4, Cambridge University Press, Cambridge, 2006.
\bibitem{Conjectures} Conjectures.io, \emph{Erd\H{o}s 1062 (parts ii)}, formalized task \texttt{fc-8432eac9-parts-ii-71df995464-formalized-v1}, \url{https://conjectures.io/problems/erdos1062-erdos-1062-parts-ii}. Accessed 21 September 2026.
\bibitem{Davis} D. Davis, Forbidden subgraphs in divisor graphs and an Erd\H{o}s divisibility problem, preprint, \href{https://arxiv.org/abs/2604.17613}{arXiv:2604.17613} (2026).
\bibitem{Z3} L. de Moura and N. Bj{\o}rner, Z3: an efficient SMT solver, in: \emph{Tools and Algorithms for the Construction and Analysis of Systems} (TACAS 2008), Lecture Notes in Comput. Sci. 4963, Springer, 2008, 337--340.
\bibitem{Lean} L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language, in: \emph{Automated Deduction -- CADE 28}, Lecture Notes in Comput. Sci. 12699, Springer, 2021, 625--635.
\bibitem{EvertseFerretti} J.-H. Evertse and R. G. Ferretti, A further improvement of the quantitative Subspace Theorem, \emph{Ann. of Math.} (2) 177 (2013), 513--590.
\bibitem{EvertseSchlickewei} J.-H. Evertse and H. P. Schlickewei, A quantitative version of the absolute subspace theorem, \emph{J. Reine Angew. Math.} 548 (2002), 21--127.
\bibitem{Formal} Google DeepMind, \emph{Formal Conjectures}, file \texttt{FormalConjectures/ErdosProblems/1062.lean}, \url{https://github.com/google-deepmind/formal-conjectures}. Accessed 21 September 2026.
\bibitem{Goel} S. Goel, R. Lunia and A. Ray, Diophantine approximation and the subspace theorem, preprint, \href{https://arxiv.org/abs/2502.00731}{arXiv:2502.00731} (2025).
\bibitem{GoldbergNovikov} E. Goldberg and Y. Novikov, Verification of proofs of unsatisfiability for CNF formulas, in: \emph{Design, Automation and Test in Europe Conference and Exhibition} (DATE 2003), IEEE, 2003, 886--891.
\bibitem{Guy} R. K. Guy, \emph{Unsolved Problems in Number Theory}, 3rd ed., Problem Books in Mathematics, Springer, New York, 2004.
\bibitem{Lebensold} K. Lebensold, A divisibility problem, \emph{Stud. Appl. Math.} 56 (1977), no.~3, 291--294.
\bibitem{LLL} A. K. Lenstra, H. W. Lenstra, Jr. and L. Lov\'asz, Factoring polynomials with rational coefficients, \emph{Math. Ann.} 261 (1982), 515--534.
\bibitem{Comparator} Lean FRO, \emph{comparator}, \url{https://github.com/leanprover/comparator}.
\bibitem{LeanExport} Lean FRO, \emph{lean4export}, \url{https://github.com/leanprover/lean4export}.
\bibitem{Mathlib} The mathlib Community, The Lean mathematical library, in: \emph{Proc. 9th ACM SIGPLAN International Conference on Certified Programs and Proofs} (CPP 2020), 2020, 367--381.
\bibitem{Roth} K. F. Roth, Rational approximations to algebraic numbers, \emph{Mathematika} 2 (1955), 1--20, corrigendum 168.
\bibitem{Schlickewei} H. P. Schlickewei, The $\mathfrak p$-adic Thue--Siegel--Roth--Schmidt theorem, \emph{Arch. Math.} (Basel) 29 (1977), 267--270.
\bibitem{SchmidtNorm} W. M. Schmidt, Norm form equations, \emph{Ann. of Math.} (2) 96 (1972), 526--551.
\bibitem{SchmidtBook} W. M. Schmidt, \emph{Diophantine Approximation}, Lecture Notes in Math. 785, Springer, Berlin, 1980.
\bibitem{SchmidtDio} W. M. Schmidt, \emph{Diophantine Approximations and Diophantine Equations}, Lecture Notes in Math. 1467, Springer, Berlin, 1991.
\bibitem{Slater} V. T. S\'os, On the distribution mod 1 of the sequence $n\alpha$, \emph{Ann. Univ. Sci. Budapest. E\"otv\"os Sect. Math.} 1 (1958), 127--134.
\bibitem{DRAT} N. Wetzler, M. J. H. Heule and W. A. Hunt, Jr., DRAT-trim: efficient checking and trimming using expressive clausal proofs, in: \emph{Theory and Applications of Satisfiability Testing} (SAT 2014), Lecture Notes in Comput. Sci. 8561, Springer, 2014, 422--429.
\end{thebibliography}
\end{document}