WorksMathematics
An exact formula for fork-free sets of integers and the irrationality of their density
Abstract
Let be the largest size of a subset of in which no element divides two distinct other elements. We prove the exact formula , where is the two-prime grid rank and is an explicit union of intervals. A matching construction follows from a cutoff recursion whose finite certificates are checked in Lean. The limit is irrational. The proof uses rotation returns, a two-cutoff -adic nonvanishing argument, and a three-place Subspace Theorem. The linked Lean development verifies the exact formula, convergence, and irrationality.
Introduction
A set of positive integers is fork-free if there are no distinct with and . Equivalently, every element of has at most one proper multiple in . Let
Every element of has at most one proper multiple up to , namely its double, so .
Erdős asked how large can be, and whether exists and is irrational. See Problem B24 in Guy’s collection [14] and Problem 1062 in Bloom’s list [3]. Lebensold [15] proved that for all large . Davis [6] recently showed that for an effectively computable constant , as a special case of a general theorem on forbidden subgraphs of divisor graphs, and left the irrationality of open. The irrationality question is also recorded in the Formal Conjectures project [11] as the Lean statement Erdos1062.erdos_1062.parts.ii, and it is posed as a formal challenge on the conjectures.io platform [5].
Results
All intervals below are closed on the left and open on the right. Put
and define, for real ,
The first intervals of are , and .
Theorem 1.1 (Exact formula). For every positive integer ,
Moreover, a fork-free set of this size can be chosen inside .
Here is the largest size of a fork-free set of integers of the form not exceeding (Theorem 2.2). The terms are forced losses between adjacent powers-of-five layers (Lemma 3.1). Formula (3) is evaluated quickly by summing the jumps of . For instance,
Theorem 1.1 answers the first half of Erdős’s question, how large can be, in the strongest possible form. For the density, write for the mantissa of in base , and define integer step functions on and on by Table 1.
| 78 | 30 | ||
| 30 | 35 | ||
| 29 | |||
| 30 | 24 | ||
| 0 | |||
Table 1. The coefficient step functions.
Theorem 1.2 (Density). The limit exists, and
Equivalently,
Numerically,
.
The displayed digits were obtained twice, independently: from (4) by exact rational integration with a tail bound, and from (5) by exact rational summation with a tail bound. The two enclosures agree.
Theorem 1.3 (Irrationality). The constant is irrational.
Corollary 1.4. The ratio converges to an irrational number. In particular the Formal Conjectures statement Erdos1062.erdos_1062.parts.ii holds with answer True.
Outline of the proof
Every positive integer is uniquely with . Section 2 solves the extremal problem on the two-prime grid exactly: the answer is , and the maximal configurations are rigid enough to be described. Summing over gives an upper bound, which Section 3 sharpens by forced losses between the classes and . Section 4 constructs matching sets inside , where the only divisibility ratios between distinct elements are . Ratios are handled by explicit parity-restricted grid sets, and ratios by a cutoff recursion. That the recursion never gets stuck is a finite statement, which we verify by computer. Section 5 derives Theorem 1.2.
The proof of irrationality occupies Sections 6 and 7. The two series in (5) are sampled along the rotation by . Along a sequence of unimodular brackets , the number is an integer plus a lacunary sum of -units with bounded integer coefficients. Truncating this sum at two carefully chosen cutoffs, and comparing 2-adic valuations, shows that if were rational, one of the two truncation errors would be a nonzero linear form in at most 405 -integers that is exponentially small compared with its height. A three-place case of the Subspace Theorem of Schmidt and Schlickewei, applied through a coordinate-elimination induction, rules this out.
Status of the computations and of the formalization
The upper bound and the proof of irrationality are ordinary mathematical proofs, presented below. The irrationality proof uses a known case of the -adic Subspace Theorem. The lower bound depends on a finite computation with two parts: a table of exact states of the cutoff recursion below , and the unsatisfiability of an explicit quantifier-free formula in linear rational arithmetic (Lemma 4.4).
We have formalized the entire argument in Lean 4 [8] with Mathlib [19]. The single Lean file proves the Formal Conjectures statement, for the answer True, and depends only on the axioms propext, Quot.sound and Classical.choice. The finite computations enter the formal proof as certificates that are checked by the Lean kernel, so no external solver is trusted. The formalization does not cite the Subspace Theorem. It contains a complete proof of the special case we need (Theorem 7.1), following the classical method of Roth and Schmidt. Section 8 describes the development and its verification.
Notation
For a prime , is the -adic absolute value with , is the -adic valuation, and . For the multiplicative, projective height is , the product over all places of . For a primitive integer vector, . A -unit is a number with , and a -integer is an element of . We write for the fractional part and for the distance to the nearest integer. Throughout, .
The two-prime grid
For real let . We identify with the lattice point . Then divisibility is the coordinatewise order, and is a finite down-set. Put
Define and for all other positive integers .
Lemma 2.1 (Rectangle decomposition). Let be a nonempty fork-free set. Let its maximal elements be with and . Put , , , , and .
(i) , and consists of the corner together with an antichain not containing it.
(ii) .
(iii) The deficits lie in , and
Moreover whenever , with equality only if . The equality holds exactly when , and .
(iv) Conversely, if form such an antichain and we choose in each its corner and an antichain avoiding the corner, the union is fork-free.
Proof. Every element of lies below some maximal element. A nonmaximal below two maximal elements would divide two other elements of , so it lies below exactly one, say . Then is not below when , and since this forces . For , holds automatically. Similarly , so . Two comparable nonmaximal elements below would give a fork, so they form an antichain. This proves (i).
An antichain in a box has distinct first and distinct second coordinates, so it has at most elements, and none if it must avoid the corner of a 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: exactly when and , and for one has for and for . Identity (6) follows by summing and . For (iv), a point of has smaller first coordinate and larger second coordinate than every point of for . Thus points in different rectangles are incomparable, and within one rectangle only the corner lies above the other chosen points. □
Theorem 2.2. For every real , the largest fork-free subset of has
elements.
Proof. The two expressions agree because , is odd exactly when , and exactly when .
Upper bound. Let be fork-free. Since and , (6) gives . If is even, integrality gives . If is odd and , the bound is already .
If is odd and , equality would require , and all . Then , so and , contradicting . Hence .
Constructions. If , then and . If is even, take corners in the columns at heights . Since , consecutive heights drop by or , and . The first rectangle has width and height and holds points. Every other rectangle has width and height or and holds points (Lemma 2.1(iv)). The total is .
If is odd, use the columns . Now every rectangle has width , and the first corner has height , so the total is . □
:::
The upper bound
Lemma 3.1 (Forced elements). Let , say and . Then every largest fork-free subset of contains and , and every largest fork-free subset of contains . Consequently every fork-free subset of has at most elements.
Proof. For we have , and , because and . Also since . Thus . If , then (6) gives
Hence . Since , the first corner is , so and . Therefore , , and for . In particular , and gives . As we have . The bound gives , so . The rectangle has width 2, height and holds points. If it is . If , the only antichain of size two avoiding the corner is . Either way .
For we have and , so , , and . For a largest , equality holds in , so every rectangle has width 2 and the first corner is , that is, . If a fork-free subset of attained , it would contain , and , and would divide the other two.
:::
Lemma 3.2. .
Proof. , and . The interval starts exactly where ends and lies below , so .
Proposition 3.3. For every positive integer , .
Proof. Let be fork-free. For the class meets in a set of the form with fork-free, so by Theorem 2.2. Group the classes into chains with . If , then and, after division by , the part of in the classes and is a fork-free subset of . Lemma 3.1 forces a loss of one element there. By Lemma 3.2, and are never both in , so the pairs of classes used for different losses are disjoint and the losses add up.
The construction
Parity-restricted grid sets
Say that has parity . For and real let
Lemma 4.1. The set is fork-free and contained in . Its size is
with for and for . Moreover .
Proof. An element of parity exceeds . Among its proper multiples in up to , only and are possible, and has parity but exceeds . Its only possible selected proper multiple is . An element of parity lies in . Its double lies in , has parity and is selected. The multiples , exceed and have parity , while , , , exceed . Thus every element has at most one selected proper multiple.
For the count with , for each with , exactly one power satisfies . For each with , exactly one power of satisfies . For , for each with , exactly one satisfies . For each with , exactly one satisfies . Finally, comparing with (2), and, for , , so the maximum is .
Each is a nondecreasing step function, so for every integer the level set is a possibly empty interval .
The cutoff recursion
For and define the target
We define states for rational by recursion. For the state is . For , let the two children be and . For a trial parity whose level set for is nonempty, put
The parity is available if that level set is nonempty and
Try first , where , and then the other parity. If some parity is available, the state is the first available parity together with , and we say that the recursion succeeds at .
Lemma 4.2. Suppose the recursion succeeds at every rational for both values of . Then for every , with an extremal set inside .
Proof. Write each integer uniquely as with , a product of powers of and , and . For each pair with , let and , and select the fiber . Let be the union of the fibers.
Since , the selected elements of the fiber lie in after division by , so . If are distinct elements of , then . Ratios keep fixed, and each fiber is fork-free by Lemma 4.1. A ratio would mean that the same lies in the fiber and in its child fiber , whose argument is and whose type is for and for . These are exactly the child states used in (9).
Let be the parent’s parity and the child’s. An element of the child of parity is at most , too small for the parent. An element of the child of parity satisfies . If , then . If , then . So no such exists. Hence every divisibility relation in lies inside a fiber, and is fork-free.
The fiber has elements. Writing , the total is
In the second sum put . Since every element of exceeds , the range may be extended to , giving exactly .
Thus each forced loss of § 3 is assigned to the upper of the two powers-of-five layers involved.
The finite verification
Proposition 4.3. The recursion succeeds at every rational for and .
The proof has two computer-verified ingredients.
The base range. Let . On the recursion was evaluated exactly. There are 109 pieces for and 108 for . Each piece is a half-open interval with rational endpoints on which the state is a fixed parity and a cutoff with . 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 (9), the upper bounds in (10), 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 in the interval.
A finite closure. Normalize the root argument to 1. The powers of 4 and 3 below are encoded by the two parameters
which the finite statement allows to vary independently. Its nodes are with and . The node has normalized argument , type if and if , and children and . At a node, let be the largest element of not exceeding , and the largest element of not exceeding . Put and , and let be the analogous quantities at . The obstruction bit
encodes , where . The errors and measure how many levels each parity must drop from its value at . The most recent jumps of at or below are . Those of are or according as or 0, and or according as or 0. The window of parity , which is the normalized set of admissible cutoffs, is
empty if ;
if ;
if and , and if and .
Each window endpoint is a rational-linear expression in on each of finitely many explicitly described pieces.
Lemma 4.4 (Closure). For and , the following system in the unknowns and, for every node , a parity and a cutoff , is unsatisfiable.
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 (36 nodes) the corresponding system was proved unsatisfiable independently by Z3 [7] and by cvc5 [2]. For it is satisfiable. For it is unsatisfiable, and the refutation is replayed in the formal proof as a certificate checked by the Lean kernel (§ 8).
Proof of Proposition 4.3. Use strong induction on for both values of . Below we use the table. Let . Every proper descendant has smaller integer part than , so its state exists by induction. Every node of depth at most 7 below has argument , and . For such arguments the normalized powers, windows and obstruction bits above coincide with the actual ones. Here and exactly when lies in the corresponding window.
Assume that neither parity is available at . Take as above, and for every node of depth at most 5 let be the actual parity and the actual cutoff divided by , wherever the state is used. The leaves and internal nodes satisfy their constraints because the recursion succeeds at the smaller arguments , and the root fails by assumption. This contradicts Lemma 4.4. □
With Proposition 3.3 and Lemma 4.2, this proves Theorem 1.1. Independently of the formal proof, an exhaustive search confirms (3) for .
The density and the coefficient series
Proof of (4). The function is nondecreasing and right-continuous. It jumps only at points of , and each jump is 0 or 1, because adding one point to a grid raises the largest fork-free size by at most one. Let . Then
After division by , the terms are dominated by , and . Dominated convergence therefore gives the limit . For the -term, each interval of contributes . The intervals beyond any cutoff contribute at most in total. Hence . Finally, by (2) and
□
Proof of (5). Write with and , and with and . For such an intersection, is the sum over the jump points of its indicator of , 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 and coincide only at , where both begin and jumps once. The endpoints of and never coincide. Hence
Here the terms and vanish. Let and . Elementary manipulation of mantissas gives
and ;
;
for , while for the right side is 1 but ;
and ;
and .
Multiplying by 60 therefore gives , where are the two integrals and
which are the functions of Table 1. Here and . Since , we obtain .
Remark 5.1. The value lies in Lebensold’s interval and above the lower bound reported by Davis.
Returns of the rotation and a small nonzero linear form
Rotation coordinates and jumps
Let , which is irrational because no positive power of 4 is a power of 3. For we have and . Let and be the corresponding 1-periodic, right-continuous step functions. Their jumps on the circle, at the points listed through and respectively, are
| 1 | 2 | ||||||
| jump of |
Table 3.
and
| 1 | 2 | ||||
| jump of |
Table 4.
Jump points related by the rotation are grouped into orbits. For we use the representatives , with the logarithm applied coordinatewise. Then
For we use , with and .
Weighting each jump by the power of 4 (respectively 3) corresponding to its orbit shift gives the orbit coefficients
For example, , , and . Each list represents four distinct orbits for its own rotation. No two elements of either list of mantissas have ratio with . The two lists share the representatives 1 and 2.
Brackets
Lemma 6.1. There are infinitely many quadruples of positive integers with
Along them and . Put . Then and . Moreover for , and every block of consecutive integers contains one with , for every .
Proof. Run the mediant (Stern–Brocot) process for starting from . Each bracket satisfies , and the identity holds. When the right endpoint is replaced by the mediant, becomes and decreases by . Thus at the end of every maximal run of right replacements we have and . Since is irrational, there are infinitely many such runs, and . The inequalities involving follow from , and . Given and , write with , which is possible because . Then . Since and , either , or and are nonzero with opposite signs. In both cases . The last assertion is the three-distance theorem: the points for in a block of consecutive integers cut the circle into gaps of lengths and only [25]. In this case the cyclic successor on the indices adds modulo , stepping by if the index increases by and by if it decreases by . The successor is one cycle because , and the step lengths sum to . Thus every half-open arc of length contains a point. □
The return identity
For a bounded integer sequence , a base and ,
Let and . Since and , we have and . So the differences in (11) are small forward and backward rotations, respectively. Define the visit indicators
Thus when the step from to crosses , and when the step from to crosses , with the endpoints as specified by the indicators. Counting crossings of jump points, and shifting indices within orbits, gives
Always and . For every other fixed , the number (respectively ) is not an integer, so the corresponding and are zero for all sufficiently late brackets. Inserting these expansions into (11), and regrouping the finitely many boundary terms, proves the following.
Proposition 6.2 (Return identity). Let
For all sufficiently late brackets,
The constant comes from the backward visit at index zero, whose step crosses the jump of at . The forward convention excludes the corresponding forward visit, since .
Events and two cutoffs
Expanding the right side of (12) writes it as a sum of events , each consisting of an integer coefficient and a -unit with time . A visit produces the events and , with times and . A visit produces and , with times and . There are sixteen event families, given by four unit types times four orbits. For a real , let be the sum of over the events with time .
Lemma 6.3. For all sufficiently late brackets:
:::`
(i) Within each family, distinct event times differ by at least .
(ii) Distinct visits , with , satisfy .
(iii) There are cutoffs and such that no event time lies in .
(iv) For , the right side of (12) differs from by at most .
Proof. For (i), two visits to the same arc of length satisfy , so by Lemma 6.1, and . The backward families are similar. The inequality gives a positive integer for sufficiently small with . Hence and , so .
For (ii), otherwise or would be within of modulo , for one of finitely many pairs. For this fails once is small, because the representatives lie in distinct orbits. For and , the irrationality of gives the same exclusion.
For (iii), by (i) each family has at most three events in a window of length , so at most 48 events are relevant. Among the 49 disjoint candidate intervals
at least one is free of them. The choice of is the same. For (iv), the omitted events have times at least , spaced by within each family, and all coefficients satisfy . So the omitted part is at most
for large .
Two truncations differ
Proposition 6.4 (Two truncations differ). For all sufficiently late brackets, .
Proof. Write , where collects the events with denominator and those with denominator . Every is 2-adically integral. In , the two events of a visit combine to a term with numerator if both are retained, and if only the earlier one, , is retained. Note that .
At , every retained dyadic event has , so either or . At , Lemma 6.1 gives a visit with . Its events are retained. Indeed, the open interval for has length . Let be the largest retained dyadic index. Then , and by Lemma 6.3(ii) all other retained indices are at most .
If the unshifted event at is retained, all retained indices have both events retained. Then
where the term with has strictly smallest valuation. Using , gives . Otherwise the term has numerator and again has strictly smallest valuation, so . In both cases has valuation less than . It cannot be cancelled by the 2-adically integral number .
Corollary 6.5. Suppose , and put . For all sufficiently late brackets there are , an integer , -units and coefficients in the finite set such that
Proof. Let . By Proposition 6.4, , so some is nonzero, and by (12) and Lemma 6.3(iv) it is at most in absolute value.
:::`
Expanding the head gives the units , , , with coefficients , , , . The retained events contribute their units with the negatives of their coefficients. Each family has at most retained events because the times lie in and are -separated. Thus . All denominators divide , and all coordinates, including , are at most in absolute value. Hence for large .
A three-place Subspace Theorem and the proof of irrationality
The covering theorem
Theorem 7.1. Let , let , and let (, ) be real numbers with and . There is a finite set of proper linear subspaces of such that, for every real , every with
lies in one of them.
Remark 7.2. Theorem 7.1 is a special case of the -adic Subspace Theorem of Schlickewei [21], which extends Schmidt’s theorem [22, 23]. See also [24, 4, 10, 9]. Indeed, let and . If the solutions are bounded, hence finite in number. Otherwise, for sufficiently large we have , so the solutions of (13) with satisfy
with and . This is the inequality of the Subspace Theorem.
For a rational linear form with , put
Theorem 7.3 (One-form covering). Let , and be as above, and . There are finitely many nonzero such that every nonzero with satisfies for some .
Proof. Multiplying by changes neither nor , so we may assume . Dividing by its gcd multiplies by , where is the part of prime to , and preserves . So we may assume primitive. Vectors with a zero coordinate, or with , lie in coordinate hyperplanes or in , and primitive vectors of bounded height are finitely many.
For the rest put . The logarithms of the local factors, divided by , lie in a bounded range and sum to less than . For the infinite place, the nonzero rational form value is bounded below by the reciprocal of a fixed common denominator of its coefficients and bounded above by a constant times . At and , a nonzero integer coordinate has -adic absolute value between and . Rounding the normalized logarithms up to mesh gives one of finitely many profiles , each with and , such that satisfies (13) for the matrix obtained from the identity by replacing row with . Apply Theorem 7.1 to each profile, and replace each proper subspace by a hyperplane containing it.
Rigidity of small linear forms
Proposition 7.4. Let , and . There is such that for all , all positive -units , and all ,
The same holds for pure forms , with .
Proof. Use induction on , first for pure forms and then for mixed forms. For a pure form with , , and for a mixed form with no units, . For a pure form with and , pick with . By the product formula for units, so . If , then . Otherwise, by Theorem 7.3, lies on one of finitely many hyperplanes . Solving for a coordinate with writes as a pure form in the remaining units with one of finitely many coefficient vectors. The value is unchanged and the height of the shorter vector is at most , so the induction hypothesis applies.
For a mixed form, take as the distinguished coordinate. If , we are in the pure case. Otherwise , which gives the bound off the exceptional hyperplanes. On a hyperplane , if , eliminate and obtain a pure form in the same units. If , eliminate a unit and obtain a mixed form with units. Finitely many coefficient vectors occur, and is the minimum of the resulting positive constants. □
Proof of Theorem 1.3
Proof. Suppose . By Corollary 6.5 and the pigeonhole principle, there are an infinite sequence of brackets with , a fixed , and a fixed coefficient vector , for which and . Apply Proposition 7.4 with and . This is allowed because every unit is at least . Since ,
so for all in an unbounded set. This is impossible. Hence is irrational. □
On the proof of Theorem 7.1 in the formalization
The formalization proves Theorem 7.1 from scratch, along the classical route of Roth and Schmidt as organized by Evertse and Ferretti [9] and in the exposition of Goel, Lunia and Ray [12]. Restricting to rational coefficients and to coordinate forms at 2 and 3 avoids number fields and adelic geometry. The main steps are the following.
Lattice model. Let and . The solutions of (13) are the points of the lattice in the box . The finite places thus enter only through divisibility.
Successive minima. For every full-rank lattice the Euclidean successive minima satisfy . The upper bound comes from a non-algorithmic reduced basis in the spirit of Lenstra–Lenstra–Lovász [16].
A gap and Davenport’s lemma. For large with a nonzero solution, the covolume forces an index with , where . A rounding lemma of Davenport type produces an integral basis of with good local bounds such that all solutions lie in .
Compound reduction. Passing to the th compound matrix, the 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.
Height dichotomy. A hyperplane spanned by solutions at parameter either belongs to a finite exceptional family, indexed by support patterns, or has a normal vector of logarithmic height at least . The proof uses only the elementary inequality for nonzero integers .
(6) Roth’s lemma. For in lowest terms let , and let be the sum of the absolute values of the coefficients of . If has , with and , and for all , then the index of at with weights is at most . The proof uses generalized Wronskians, as in [20, 12], and is extended to products of rational hyperplanes.
(7) 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.
(8) Contradiction. Suppose solutions spanned hyperplanes of heights growing linearly in along an unbounded set of parameters. Choose well-separated parameters and degrees . 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.
(9) Assembly. The recovery map gives finitely many prefix subspaces, and bounded parameters give finitely many integer points. This proves Theorem 7.1.
The argument is ineffective. Thus Theorem 1.3 provides no irrationality measure for .
The Lean formalization
The statement
The file FormalConjectures/ErdosProblems/1062.lean in Formal Conjectures [11] defines fork-freeness and the extremal function by
def ForkFree (A : Set ℕ) : Prop :=
∀a ∈ A, ({b | b ∈ A \ {a} ∧ a ∣ b} : Set ℕ).Subsingleton
noncomputable def f (n : ℕ) : ℕ :=
open scoped Classical in
Nat.findGreatest (fun k => ∃ A ⊆ Set.Icc 1 n,
ForkFree A ∧ A.ncard = k) n
and states the problem as
theorem erdos_1062.parts.ii :
(∃ l, Tendsto (fun n => (f n : ℝ) / n) atTop (𝓝 l)
∧ Irrational l) ↔ answer(sorry)
The conjectures.io task [5] asks for a proof of this statement with the answer True, as the declaration Bounty.target. The original file ends with
theorem target : fcTypeOfName% "Erdos1062.erdos_1062.parts.ii" :=
target_of_integer_oneForm_cover
(integer_oneForm_cover_of_three_place
rational_three_place_subspace_cover)
The development first shows that Nat.findGreatest computes the maximum size, and it never uses the imported open statement as a proof.
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 2 shows how the components correspond to the sections of this paper.
| Content | Representative components | Lines |
| Grid theorem, upper bound, construction, recursion, bridge to the closure (§§ § 2–§ 4) | GridBridge, GlobalUpper, CutoffRecursion, ClosureInduction, GlobalExact | 7,816 |
| Base-range table and its checks (§ 4) | BaseTableData, PolicyBaseIntervalsCompact | 9,976 |
| Closure certificate and its checkers (Lemma 4.4) | PolicyBitsetRUP, PolicyLinearCertificate, ClosureInputReflection | 32,649 |
| Density, series, returns, nonvanishing, rigidity (§§ § 5–§ 7) | CoefficientSeries, ReturnDifferenceIdentity, ReturnTruncationNonzero, OneFormRigidity | 8,469 |
| Roth’s lemma (§ 7.4, step 6) | GeneralizedWronskian, IntegerRothTheorem | 3,568 |
| Theorem 7.1 (§ 7.4) | LatticeSuccessiveMinima, BalancedAuxiliaryPolynomial, RationalThreePlaceSubspaceTheorem | 11,732 |
Table 2. Components of the formal proof.
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 (decide +kernel).
For the closure, the failure system in Lemma 4.4 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 ClosureRawHypothesis5 and 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:
Boolean circuit clauses defining the DAG’s gates;
instances of 190 rewrite schemas, each proved once in Lean;
arithmetic lemmas, each justified by a sparse Farkas certificate with rational coefficients;
a propositional refutation of the resulting clause set in reverse unit propagation (RUP) form [13, 26], produced with the SAT solver Glucose [1].
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.
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, set_option, attributes, instances, custom syntax, 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 propext, Quot.sound and 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 def in place of 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 was 4,965,602 bytes and 752,155 tokens as counted by the challenge’s static scanner, whose limit is . Its SHA-256 hash begins 2ebc87b0. We ran the verification pipeline locally with the toolchain pinned by the challenge (Lean 4.33.1). The build (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 lean4export [18] took 7 s and 51 s. Replaying the exported solution in a fresh kernel with the comparator [17] 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 sorry.
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 explicit finite-formula and limit wrapper, with stated endpoint Erdos1062Full.full_scope, and the corresponding clean build and target axiom record. The wrapper exposes the exact arithmetic identity for every natural , including the empty sum for , together with convergence and irrationality.
Concluding remarks
(1) Theorem 1.1 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 4.4 would make the theorem computer-free.
(2) The irrationality proof never uses irrationality of the two series in (5) separately, and it needs no assumption on the continued fraction of . It uses the Subspace Theorem only for linear forms in -integers, and no finiteness theorem for -unit equations.
(3) Davis’s theorem [6] 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.
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.
References
- [1]G. Audemard and L. Simon, Predicting learnt clauses quality in modern SAT solvers, in: Proc. 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), 399–404.
- [2]H. Barbosa et al., cvc5: a versatile and industrial-strength SMT solver, in: Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2022), Lecture Notes in Comput. Sci. 13243, Springer, 2022, 415–442.
- [3]T. F. Bloom, Erdős Problem #1062, https://www.erdosproblems.com/1062. Accessed 21 September 2026.
- [4]E. Bombieri and W. Gubler, Heights in Diophantine Geometry, New Mathematical Monographs 4, Cambridge University Press, Cambridge, 2006.
- [5]Conjectures.io, Erdős 1062 (parts ii), formalized task fc-8432eac9-71df995464-formalized-v1, https://conjectures.io/problems/erdos1062-erdos-1062-parts-ii. Accessed 21 September 2026.
- [6]D. Davis, Forbidden subgraphs in divisor graphs and an Erdős divisibility problem, preprint, arXiv:2604.17613 (2026).
- [7]L. de Moura and N. Bjørner, Z3: an efficient SMT solver, in: Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2008), Lecture Notes in Comput. Sci. 4963, Springer, 2008, 337–340.DOI
- [8]L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language, in: Automated Deduction – CADE 28, Lecture Notes in Comput. Sci. 12699, Springer, 2021, 625–635.DOI
- [9]J.-H. Evertse and R. G. Ferretti, A further improvement of the quantitative Subspace Theorem, Ann. of Math. (2) 177 (2013), 513–590.arxiv.org/abs/1008.2340
- [10]J.-H. Evertse and H. P. Schlickewei, A quantitative version of the absolute subspace theorem, J. Reine Angew. Math. 548 (2002), 21–127.DOI
- [11]Google DeepMind, Formal Conjectures, file FormalConjectures/ErdosProblems/1062.lean, https://github.com/google-deepmind/formal-conjectures. Accessed 21 September 2026.
- [12]S. Goel, R. Lunia and A. Ray, Diophantine approximation and the subspace theorem, preprint, arXiv:2502.00731 (2025).DOI
- [13]E. Goldberg and Y. Novikov, Verification of proofs of unsatisfiability for CNF formulas, in: Design, Automation and Test in Europe Conference and Exhibition (DATE 2003), IEEE, 2003, 886–891.
- [14]R. K. Guy, Unsolved Problems in Number Theory, 3rd ed., Problem Books in Mathematics, Springer, New York, 2004.
- [15]K. Lebensold, A divisibility problem, Stud. Appl. Math. 56 (1977), no. 3, 291–294.DOI
- [16]A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515–534.
- [17]Lean FRO, comparator, https://github.com/leanprover/comparator.
- [18]Lean FRO, lean4export, https://github.com/leanprover/lean4export.
- [19]The mathlib Community, The Lean mathematical library, in: Proc. 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), 2020, 367–381.
- [20]K. F. Roth, Rational approximations to algebraic numbers, Mathematika 2 (1955), 1–20, corrigendum 168.
- [21]H. P. Schlickewei, The p-adic Thue–Siegel–Roth–Schmidt theorem, Arch. Math. (Basel) 29 (1977), 267–270.
- [22]W. M. Schmidt, Norm form equations, Ann. of Math. (2) 96 (1972), 526–551.DOI
- [23]W. M. Schmidt, Diophantine Approximation, Lecture Notes in Math. 785, Springer, Berlin, 1980.
- [24]W. M. Schmidt, Diophantine Approximations and Diophantine Equations, Lecture Notes in Math. 1467, Springer, Berlin, 1991.DOI
- [25]V. T. Sós, On the distribution mod 1 of the sequence nα, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 1 (1958), 127–134.
- [26]N. Wetzler, M. J. H. Heule and W. A. Hunt, Jr., DRAT-trim: efficient checking and trimming using expressive clausal proofs, in: Theory and Applications of Satisfiability Testing (SAT 2014), Lecture Notes in Comput. Sci. 8561, Springer, 2014, 422–429.DOI