betaFeedback

WorksMathematics

An exact formula for fork-free sets of integers and the irrationality of their density

Abstract

Let f(n)f(n) be the largest size of a subset of {1,…,n}\{1,\ldots,n\} in which no element divides two distinct other elements. We prove the exact formula f(n)=∑m≤n, (m,6)=1(R(n/m)−1B(n/m))f(n)=\sum_{m\le n,\,(m,6)=1}(R(n/m)-\mathbf{1}_{\mathcal B}(n/m)), where RR is the two-prime grid rank and B\mathcal B is an explicit union of intervals. A matching construction follows from a cutoff recursion whose finite certificates are checked in Lean. The limit c=lim⁡n→∞f(n)/n=0.67296565119948934747…c=\lim_{n\to\infty}f(n)/n=0.67296565119948934747\ldots is irrational. The proof uses rotation returns, a two-cutoff 22-adic nonvanishing argument, and a three-place Subspace Theorem. The linked Lean development verifies the exact formula, convergence, and irrationality.

Introduction

A set AA of positive integers is fork-free if there are no distinct a,b,c∈Aa,b,c\in A with a∣ba\mid b and a∣ca\mid c. Equivalently, every element of AA has at most one proper multiple in AA. Let

f(n)=max⁡{∣A∣:A⊆{1,…,n}, A fork-free}.f(n)=\max\{|A|:A\subseteq\{1,\ldots,n\},\ A\text{ fork-free}\}.

Every element of (n/3,n](n/3,n] has at most one proper multiple up to nn, namely its double, so f(n)≥⌈2n/3⌉f(n)\ge\lceil2n/3\rceil.

Erdős asked how large f(n)f(n) can be, and whether lim⁡n→∞f(n)/n\lim_{n\to\infty}f(n)/n exists and is irrational. See Problem B24 in Guy’s collection [14] and Problem 1062 in Bloom’s list [3]. Lebensold [15] proved that 0.6725n≤f(n)≤0.6736n0.6725n\le f(n)\le0.6736n for all large nn. Davis [6] recently showed that f(n)=cn+o(n)f(n)=cn+o(n) for an effectively computable constant cc, as a special case of a general theorem on forbidden subgraphs of divisor graphs, and left the irrationality of cc 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

E=(⋃j≥0[2⋅4j,4j+1))∩(⋃b≥0[2⋅3b,3b+1)),B=(⋃b≥0[10⋅3b,12⋅3b))∩(⋃j≥0[4j,544j)).(1)\begin{aligned} \mathcal{E} &= \left(\bigcup_{j\geq0}[2\cdot4^j,4^{j+1})\right)\cap\left(\bigcup_{b\geq0}[2\cdot3^b,3^{b+1})\right),\\ \mathcal{B} &= \left(\bigcup_{b\geq0}[10\cdot3^b,12\cdot3^b)\right)\cap\left(\bigcup_{j\geq0}[4^j,\tfrac{5}{4}4^j)\right). \tag*{(1)} \end{aligned}

and define, for real xx,

R(x)=1+⌊log⁡4x⌋+⌊log⁡3x⌋+1E(x)(x≥1),R(x)=0(x<1).(2)R(x)=1+\lfloor\log_4 x\rfloor+\lfloor\log_3 x\rfloor+\mathbf{1}_{\mathcal{E}}(x)\quad(x\geq1),\qquad R(x)=0\quad(x<1). \tag*{(2)}

The first intervals of B\mathcal{B} are [270,320)[270,320), [65610,78732)[65610,78732) and [16777216,19131876)[16777216,19131876).

Theorem 1.1 (Exact formula). For every positive integer nn,

f(n)=U(n):=∑1≤m≤n(m,6)=1(R(n/m)−1B(n/m)).(3)f(n)=U(n):=\sum_{\substack{1\leq m\leq n\\(m,6)=1}}\left(R(n/m)-\mathbf{1}_{\mathcal{B}}(n/m)\right). \tag*{(3)}

Moreover, a fork-free set of this size can be chosen inside (n/8,n](n/8,n].

Here R(x)R(x) is the largest size of a fork-free set of integers of the form 2a3b2^a3^b not exceeding xx (Theorem 2.2). The terms 1B\mathbf{1}_{\mathcal{B}} are forced losses between adjacent powers-of-five layers (Lemma 3.1). Formula (3) is evaluated quickly by summing the jumps of RR. For instance,

f(106)=672964,f(1012)=672965651200,f(1024)=672965651199489347471228.f(10^6)=672964,\qquad f(10^{12})=672965651200,\qquad f(10^{24})=672965651199489347471228.

Theorem 1.1 answers the first half of Erdős’s question, how large f(n)f(n) can be, in the strongest possible form. For the density, write [x]b=x/b⌊log⁡bx⌋∈[1,b)[x]_b=x/b^{\lfloor\log_b x\rfloor}\in[1,b) for the mantissa of x>0x>0 in base bb, and define integer step functions φ\varphi on [1,3)[1,3) and ψ\psi on [1,4)[1,4) by Table 1.

t∈[1,3)t \in[1,3)φ(t)\varphi(t)s∈[1,4)s \in[1,4)ψ(s)\psi(s)
[1,16/15)[1,16/15)78[1,4/3)[1,4/3)30
[16/15,10/9)[16/15,10/9)30[4/3,8/5)[4/3,8/5)35
[10/9,4/3)[10/9,4/3)−30-30[8/5,5/3)[8/5,5/3)29
[4/3,3/2)[4/3,3/2)30[5/3,2)[5/3,2)24
[3/2,2)[3/2,2)0[2,4)[2,4)−60-60
[2,8/3)[2,8/3)−60-60
[8/3,3)[8/3,3)−12-12

Table 1. The coefficient step functions.

Theorem 1.2 (Density). The limit c=lim⁡n→∞f(n)/nc=\lim_{n\to\infty}f(n)/n exists, and

c=1118+13(∫Edtt2−∫Bdtt2).(4)c=\frac{11}{18}+\frac{1}{3}\left(\int_{\mathcal{E}}\frac{dt}{t^2}-\int_{\mathcal{B}}\frac{dt}{t^2}\right). \tag*{(4)}

Equivalently,

180c=32+∑k≥0φ([4k]3)4k+∑k≥0ψ([3k]4)3k.(5)180c=32+\sum_{k\geq0}\frac{\varphi([4^k]_3)}{4^k}+\sum_{k\geq0}\frac{\psi([3^k]_4)}{3^k}. \tag*{(5)}

Numerically,

c=0.672965651199489347471227919852209644752814733132999025108932699233…c=0.672965651199489347471227919852209644752814733132999025108932699233\ldots.

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 cc is irrational.

Corollary 1.4. The ratio f(n)/nf(n)/n 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 m2a3bm2^a3^b with (m,6)=1(m,6)=1. Section 2 solves the extremal problem on the two-prime grid {2a3b≤x}\{2^a3^b \le x\} exactly: the answer is R(x)R(x), and the maximal configurations are rigid enough to be described. Summing over mm gives an upper bound, which Section 3 sharpens by forced losses between the classes mm and 5m5m. Section 4 constructs matching sets inside (n/8,n](n/8,n], where the only divisibility ratios between distinct elements are 2,3,…,72,3,\ldots,7. Ratios 2,3,4,62,3,4,6 are handled by explicit parity-restricted grid sets, and ratios 5,75,7 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 α=log⁡4/log⁡3\alpha=\log4/\log3. Along a sequence of unimodular brackets p/q<α<P/Qp/q<\alpha<P/Q, the number (4q−1)(3p−1)(180c−32)(4^q-1)(3^p-1)(180c-32) is an integer NN plus a lacunary sum of {2,3}\{2,3\}-units with bounded integer coefficients. Truncating this sum at two carefully chosen cutoffs, and comparing 2-adic valuations, shows that if cc were rational, one of the two truncation errors would be a nonzero linear form in at most 405 {2,3}\{2,3\}-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 f(n)≤U(n)f(n)\le U(n) and the proof of irrationality are ordinary mathematical proofs, presented below. The irrationality proof uses a known case of the pp-adic Subspace Theorem. The lower bound f(n)≥U(n)f(n)\ge U(n) depends on a finite computation with two parts: a table of exact states of the cutoff recursion below 2⋅772\cdot7^7, 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 pp, ∣⋅∣p|\cdot|_p is the pp-adic absolute value with ∣p∣p=p−1|p|_p=p^{-1}, vpv_p is the pp-adic valuation, and ∣⋅∣=∣⋅∣∞|\cdot|=|\cdot|_\infty. For x∈Qn∖{0}x\in\mathbb{Q}^n\setminus\{0\} the multiplicative, projective height is H(x)=∏vmax⁡i∣xi∣vH(x)=\prod_v\max_i|x_i|_v, the product over all places of Q\mathbb{Q}. For a primitive integer vector, H(x)=max⁡i∣xi∣H(x)=\max_i|x_i|. A {2,3}\{2,3\}-unit is a number 2a3b2^a3^b with a,b∈Za,b\in\mathbb{Z}, and a {2,3}\{2,3\}-integer is an element of Z[1/6]\mathbb{Z}[1/6]. We write {x}\{x\} for the fractional part and ∥x∥\|x\| for the distance to the nearest integer. Throughout, ⟨2,3⟩={2a3b:a,b≥0}\langle2,3\rangle=\{2^a3^b:a,b\ge0\}.

The two-prime grid

For real x>1x>1 let S(x)={2a3b<x:a,b≥0}S(x)=\{2^a3^b<x:a,b\ge0\}. We identify 2a3b2^a3^b with the lattice point (a,b)(a,b). Then divisibility is the coordinatewise order, and S(x)S(x) is a finite down-set. Put

a∗=⌊log⁡2x⌋,b∗=⌊log⁡3x⌋,δ=1[x≥2a∗3b∗].a^*=\lfloor\log_2x\rfloor,\qquad b^*=\lfloor\log_3x\rfloor,\qquad\delta=\mathbf{1}_{[x\ge2^{a^*}3^{b^*}]}.

Define g(1,1)=1g(1,1)=1 and g(w,h)=1+min⁡(w,h)g(w,h)=1+\min(w,h) for all other positive integers w,hw,h.

Lemma 2.1 (Rectangle decomposition). Let W⊆S(x)W \subseteq S(x) be a nonempty fork-free set. Let its maximal elements be (a1,b1),…,(ar,br)(a_1,b_1),\ldots,(a_r,b_r) with a1<⋯<ara_1<\cdots<a_r and b1>⋯>brb_1>\cdots>b_r. Put a0=−1a_0=-1, br+1=−1b_{r+1}=-1, wi=ai−ai−1w_i=a_i-a_{i-1}, hi=bi−bi+1h_i=b_i-b_{i+1}, and Ri={(a,b):ai−1<a≤ai, bi+1<b≤bi}R_i=\{(a,b):a_{i-1}<a\leq a_i,\ b_{i+1}<b\leq b_i\}.

(i) W⊆⋃iRiW\subseteq\bigcup_i R_i, and W∩RiW\cap R_i consists of the corner (ai,bi)(a_i,b_i) together with an antichain not containing it.

(ii) ∣W∩Ri∣≤g(wi,hi)≤hi+wi/2|W\cap R_i|\leq g(w_i,h_i)\leq h_i+w_i/2.

(iii) The deficits di=hi+wi/2−∣W∩Ri∣d_i=h_i+w_i/2-|W\cap R_i| lie in 12Z≥0\frac{1}{2}\mathbb{Z}_{\geq0}, and

∣W∣=b1+1+ar+12−∑i=1rdi(6)|W|=b_1+1+\frac{a_r+1}{2}-\sum_{i=1}^{r}d_i \tag*{(6)}

Moreover di≥12d_i\geq\frac{1}{2} whenever wi=1w_i=1, with equality only if hi∈{1,2}h_i\in\{1,2\}. The equality di=0d_i=0 holds exactly when wi=2w_i=2, hi∈{1,2}h_i\in\{1,2\} and ∣W∩Ri∣=hi+1|W\cap R_i|=h_i+1.

(iv) Conversely, if (a1,b1),…,(ar,br)∈S(x)(a_1,b_1),\ldots,(a_r,b_r)\in S(x) form such an antichain and we choose in each RiR_i its corner and an antichain avoiding the corner, the union is fork-free.

Proof. Every element of WW lies below some maximal element. A nonmaximal w∈Ww\in W below two maximal elements would divide two other elements of WW, so it lies below exactly one, say (ai,bi)(a_i,b_i). Then w=(a,b)w=(a,b) is not below (ai−1,bi−1)(a_{i-1},b_{i-1}) when i>1i>1, and since b≤bi<bi−1b\leq b_i<b_{i-1} this forces a>ai−1a>a_{i-1}. For i=1i=1, a>a0=−1a>a_0=-1 holds automatically. Similarly b>bi+1b>b_{i+1}, so w∈Riw\in R_i. Two comparable nonmaximal elements below (ai,bi)(a_i,b_i) would give a fork, so they form an antichain. This proves (i).

An antichain in a w×hw\times h box has distinct first and distinct second coordinates, so it has at most min⁡(w,h)\min(w,h) elements, and none if it must avoid the corner of a 1×11\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/2g(w,h)=h+w/2 exactly when w=2w=2 and h∈{1,2}h\in\{1,2\}, and for w=1w=1 one has h+12−g(1,h)=12h+\frac{1}{2}-g(1,h)=\frac{1}{2} for h∈{1,2}h\in\{1,2\} and h−32≥32h-\frac{3}{2}\geq\frac{3}{2} for h≥3h\geq3. Identity (6) follows by summing ∑ihi=b1+1\sum_i h_i=b_1+1 and ∑iwi=ar+1\sum_i w_i=a_r+1. For (iv), a point of RiR_i has smaller first coordinate and larger second coordinate than every point of RjR_j for j>ij>i. 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 x≥1x\geq1, the largest fork-free subset of S(x)S(x) has

R(x)=⌊a∗/2⌋+b∗+1+1[a∗ odd]δ=1+⌊log⁡4x⌋+⌊log⁡3x⌋+1ε(x)R(x)=\lfloor a^*/2\rfloor+b^*+1+1_{[a^*\ \mathrm{odd}]}\delta=1+\lfloor\log_4x\rfloor+\lfloor\log_3x\rfloor+1\varepsilon(x)

elements.

Proof. The two expressions agree because ⌊log⁡4x⌋=⌊a∗/2⌋\lfloor\log_4x\rfloor=\lfloor a^*/2\rfloor, a∗a^* is odd exactly when x∈⋃j[2⋅4j,4j+1)x\in\bigcup_j[2\cdot4^j,4^{j+1}), and δ=1\delta=1 exactly when x∈⋃b[2⋅3b,3b+1)x\in\bigcup_b[2\cdot3^b,3^{b+1}).

Upper bound. Let WW be fork-free. Since b1≤b∗b_1\leq b^* and ar≤a∗a_r\leq a^*, (6) gives ∣W∣≤b∗+1+(a∗+1)/2|W|\leq b^*+1+(a^*+1)/2. If a∗a^* is even, integrality gives ∣W∣≤b∗+1+a∗/2|W|\leq b^*+1+a^*/2. If a∗a^* is odd and δ=1\delta=1, the bound is already ⌊a∗/2⌋+b∗+2\lfloor a^*/2\rfloor+b^*+2.

If a∗a^* is odd and δ=0\delta=0, equality would require b1=b∗b_1=b^*, ar=a∗a_r=a^* and all di=0d_i=0. Then w1=2w_1=2, so a1=1a_1=1 and 2⋅3b∗∈S(x)2\cdot3^{b^*}\in S(x), contradicting δ=0\delta=0. Hence ∣W∣≤b∗+(a∗+1)/2=⌊a∗/2⌋+b∗+1|W|\leq b^*+(a^*+1)/2=\lfloor a^*/2\rfloor+b^*+1.

Constructions. If a∗=0a^*=0, then S(x)={1}S(x)=\{1\} and R(x)=1R(x)=1. If a∗≥2a^*\geq2 is even, take corners in the columns a=0,2,…,a∗a=0,2,\ldots,a^* at heights β(a)=⌊log⁡3(x/2a)⌋\beta(a)=\lfloor\log_3(x/2^a)\rfloor. Since 3≤4≤93\leq4\leq9, consecutive heights drop by 11 or 22, and β(a∗)=0\beta(a^*)=0. The first rectangle has width 11 and height h1∈{1,2}h_1\in\{1,2\} and holds h1h_1 points. Every other rectangle has width 22 and height 11 or 22 and holds hi+1h_i+1 points (Lemma 2.1(iv)). The total is β(0)+1+a∗/2=b∗+1+a∗/2\beta(0)+1+a^*/2=b^*+1+a^*/2.

If a∗a^* is odd, use the columns 1,3,…,a∗1,3,\ldots,a^*. Now every rectangle has width 22, and the first corner has height ⌊log⁡3(x/2)⌋=b∗−1+δ\lfloor\log_3(x/2)\rfloor=b^*-1+\delta, so the total is b∗+δ+(a∗+1)/2b^*+\delta+(a^*+1)/2. □

:::

The upper bound

Lemma 3.1 (Forced elements). Let t∈Bt \in\mathcal{B}, say 10⋅3b≤t<12⋅3b10 \cdot3^{b} \le t < 12 \cdot3^{b} and 4j≤t<544j4^{j} \le t < \frac{5}{4}4^{j}. Then every largest fork-free subset of S(t)S(t) contains 2⋅3b2 \cdot3^{b} and 4⋅3b4 \cdot3^{b}, and every largest fork-free subset of S(t/5)S(t/5) contains 2⋅3b2 \cdot3^{b}. Consequently every fork-free subset of S(t)∪5S(t/5)S(t) \cup5S(t/5) has at most R(t)+R(t/5)−1R(t)+R(t/5)-1 elements.

Proof. For S(t)S(t) we have a∗=2ja^* = 2j, b∗=b+2b^* = b+2 and δ=0\delta= 0, because t<544j<2⋅4jt < \frac{5}{4}4^j < 2\cdot4^j and 9⋅3b≤t<18⋅3b9\cdot3^b \le t < 18\cdot3^b. Also j≥2j \ge2 since t≥10t \ge10. Thus R(t)=j+b+3R(t) = j+b+3. If ∣W∣=R(t)|W|=R(t), then (6) gives

∑idi+(b+2−b1)+2j−ar2=12.\sum_i d_i + (b+2-b_1) + \frac{2j-a_r}{2} = \frac{1}{2}.

Hence b1=b+2b_1=b+2. Since t<2⋅3b+2t<2\cdot3^{b+2}, the first corner is (0,b+2)(0,b+2), so w1=1w_1=1 and d1≥12d_1\ge\frac{1}{2}. Therefore d1=12d_1=\frac{1}{2}, ar=2ja_r=2j, and di=0d_i=0 for i≥2i\ge2. In particular r≥2r\ge2, and w2=2w_2=2 gives a2=2a_2=2. As h1∈{1,2}h_1\in\{1,2\} we have b2∈{b,b+1}b_2\in\{b,b+1\}. The bound 4⋅3b2≤t<12⋅3b4\cdot3^{b_2}\le t<12\cdot3^b gives b2=bb_2=b, so 4⋅3b∈W4\cdot3^b\in W. The rectangle R2R_2 has width 2, height h2∈{1,2}h_2\in\{1,2\} and holds h2+1h_2+1 points. If h2=1h_2=1 it is {(1,b),(2,b)}\{(1,b),(2,b)\}. If h2=2h_2=2, the only antichain of size two avoiding the corner is {(1,b),(2,b−1)}\{(1,b),(2,b-1)\}. Either way 2⋅3b∈W2\cdot3^b\in W.

For u=t/5u=t/5 we have 2⋅3b≤u<1253b2\cdot3^b\le u<\frac{12}{5}3^b and 22j−3<4j/5≤u<22j−22^{2j-3}<4^j/5\le u<2^{2j-2}, so a∗=2j−3a^*=2j-3, b∗=bb^*=b, δ=1\delta=1 and R(u)=j+bR(u)=j+b. For a largest W′W', equality holds in ∣W′∣≤b∗+1+(a∗+1)/2|W'|\le b^*+1+(a^*+1)/2, so every rectangle has width 2 and the first corner is (1,b)(1,b), that is, 2⋅3b∈W′2\cdot3^b\in W'. If a fork-free subset of S(t)∪5S(t/5)S(t)\cup5S(t/5) attained R(t)+R(t/5)R(t)+R(t/5), it would contain 2⋅3b2\cdot3^b, 4⋅3b4\cdot3^b and 5⋅2⋅3b5\cdot2\cdot3^b, and 2⋅3b2\cdot3^b would divide the other two.

:::

Lemma 3.2. B∩5B=∅\mathcal{B}\cap5\mathcal{B}=\varnothing.

Proof. B⊆G:=⋃j[4j,544j)\mathcal{B}\subseteq G:=\bigcup_j[4^j,\frac{5}{4}4^j), and 5G=⋃j[5⋅4j,2544j)5G=\bigcup_j[5\cdot4^j,\frac{25}{4}4^j). The interval [5⋅4j,2544j)[5\cdot4^j,\frac{25}{4}4^j) starts exactly where [4j+1,5⋅4j)[4^{j+1},5\cdot4^j) ends and lies below 4j+24^{j+2}, so G∩5G=∅G\cap5G=\varnothing.

Proposition 3.3. For every positive integer nn, f(n)≤U(n)f(n)\le U(n).

Proof. Let A⊆{1,…,n}A\subseteq\{1,\ldots,n\} be fork-free. For (m,6)=1(m,6)=1 the class {ms:s∈S(n/m)}\{ms:s\in S(n/m)\} meets AA in a set of the form mWmmW_m with Wm⊆S(n/m)W_m\subseteq S(n/m) fork-free, so ∣A∣≤∑mR(n/m)|A|\le\sum_m R(n/m) by Theorem 2.2. Group the classes into chains m=m05km=m_0 5^k with (m0,30)=1(m_0,30)=1. If t=n/m∈Bt=n/m\in\mathcal{B}, then t≥10t\ge10 and, after division by mm, the part of AA in the classes mm and 5m5m is a fork-free subset of S(t)∪5S(t/5)S(t)\cup5S(t/5). Lemma 3.1 forces a loss of one element there. By Lemma 3.2, n/mn/m and n/(5m)n/(5m) are never both in B\mathcal{B}, so the pairs of classes used for different losses are disjoint and the losses add up.

The construction

Parity-restricted grid sets

Say that 2a3b2^a3^b has parity a mod 2a\bmod2. For p∈{0,1}p\in\{0,1\} and real z≥0z\ge0 let

Wp(z)={s∈⟨2,3⟩:z/4<s≤z, s of parity p}∪{s∈⟨2,3⟩:z/6<s≤z/2, s of parity 1−p}.(7)W_p(z)=\{s\in\langle2,3\rangle:z/4<s\le z,\ s\text{ of parity }p\} \cup\{s\in\langle2,3\rangle:z/6<s\le z/2,\ s\text{ of parity }1-p\}. \tag*{(7)}

Lemma 4.1. The set Wp(z)W_p(z) is fork-free and contained in (z/6,z](z/6,z]. Its size is

h0(z)=⌊log⁡4z⌋+⌊log⁡3z⌋+1(z≥1),h_0(z)=\lfloor\log_4 z\rfloor+\lfloor\log_3 z\rfloor+1 \qquad(z\ge1),
h1(z)=⌊log⁡4(z/2)⌋+⌊log⁡3(z/2)⌋+2(z≥2),h_1(z)=\lfloor\log_4(z/2)\rfloor+\lfloor\log_3(z/2)\rfloor+2 \qquad(z\ge2),

with h0(z)=0h_0(z)=0 for z<1z<1 and h1(z)=0h_1(z)=0 for z<2z<2. Moreover R(z)=max⁡(h0(z),h1(z))R(z)=\max(h_0(z),h_1(z)).

Proof. An element ss of parity pp exceeds z/4z/4. Among its proper multiples in ⟨2,3⟩\langle2,3\rangle up to zz, only 2s2s and 3s3s are possible, and 2s2s has parity 1−p1-p but exceeds z/2z/2. Its only possible selected proper multiple is 3s3s. An element ss of parity 1−p1-p lies in (z/6,z/2](z/6,z/2]. Its double lies in (z/3,z](z/3,z], has parity pp and is selected. The multiples 3s3s, 4s4s exceed z/2z/2 and have parity 1−p1-p, while 6s6s, 8s8s, 9s9s, 12s12s exceed zz. Thus every element has at most one selected proper multiple.

For the count with p=0p=0, for each bb with 3b≤z3^b\le z, exactly one power 4i≥14^i\ge1 satisfies 4i3b∈(z/4,z]4^i3^b\in(z/4,z]. For each ii with 4i+1≤z4^{i+1}\le z, exactly one power of 33 satisfies 2⋅4i⋅3b∈(z/6,z/2]2\cdot4^i\cdot3^b\in(z/6,z/2]. For p=1p=1, for each bb with 3b≤z/23^b\le z/2, exactly one ii satisfies 2⋅4i3b∈(z/4,z]2\cdot4^i3^b\in(z/4,z]. For each ii with 4i≤z/24^i\le z/2, exactly one bb satisfies 4i3b∈(z/6,z/2]4^i3^b\in(z/6,z/2]. Finally, comparing with (2), h0=R−1εh_0=R-1_{\varepsilon} and, for z≥1z\ge1, h1=R−1[a∗ even]1[δ=0]h_1=R-1_{[a^*\ \mathrm{even}]}1_{[\delta=0]}, so the maximum is RR.

Each hph_p is a nondecreasing step function, so for every integer kk the level set {z≥0:hp(z)=k}\{z\ge0:h_p(z)=k\} is a possibly empty interval [λp(k),μp(k))[\lambda_p(k),\mu_p(k)).

The cutoff recursion

For ε∈{0,1}\varepsilon\in\{0,1\} and u>0u>0 define the target

kε(u)=R(u)−ε1B(5u).(8)k_\varepsilon(u)=R(u)-\varepsilon1_{\mathcal{B}}(5u). \tag*{(8)}

We define states (pε(u),zε(u))∈{0,1}×Q≥0(p_\varepsilon(u),z_\varepsilon(u))\in\{0,1\}\times\mathbb{Q}_{\ge0} for rational u>0u>0 by recursion. For u<1u<1 the state is (0,0)(0,0). For u≥1u\ge1, let the two children be (p5,z5)=(p1(u/5),z1(u/5))(p_5,z_5)=(p_1(u/5),z_1(u/5)) and (p7,z7)=(pε(u/7),zε(u/7))(p_7,z_7)=(p_\varepsilon(u/7),z_\varepsilon(u/7)). For a trial parity pp whose level set for kε(u)k_\varepsilon(u) is nonempty, put

ζp=max⁡{34u,λp(kε(u)),γ(p,p5)z5,γ(p,p7)z7},γ(p,p′)={4,p=p′,6,p≠p′.(9)\zeta_p=\max\left\{\frac{3}{4}u,\lambda_p(k_\varepsilon(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} \tag*{(9)}

The parity pp is available if that level set is nonempty and

ζp≤u,ζp<μp(kε(u)).(10)\zeta_p\le u,\qquad\zeta_p<\mu_p(k_\varepsilon(u)). \tag*{(10)}

Try first p=a∗(u) mod 2p=a^*(u)\bmod2, where a∗(u)=⌊log⁡2u⌋a^*(u)=\lfloor\log_2u\rfloor, and then the other parity. If some parity is available, the state is the first available parity pp together with zε(u)=ζpz_\varepsilon(u)=\zeta_p, and we say that the recursion succeeds at (u,ε)(u,\varepsilon).

Lemma 4.2. Suppose the recursion succeeds at every rational u≥1u\ge1 for both values of ε\varepsilon. Then f(n)≥U(n)f(n)\ge U(n) for every nn, with an extremal set inside (n/8,n](n/8,n].

Proof. Write each integer uniquely as ghsghs with (g,210)=1(g,210)=1, hh a product of powers of 55 and 77, and s∈⟨2,3⟩s\in\langle2,3\rangle. For each pair (g,h)(g,h) with gh≤ngh\le n, let u=n/(gh)u=n/(gh) and ε=1[5∣h]\varepsilon=1_{[5\mid h]}, and select the fiber ghWpε(u)(zε(u))ghW_{p_\varepsilon(u)}(z_\varepsilon(u)). Let AnA_n be the union of the fibers.

Since 34u≤zε(u)≤u\frac{3}{4}u\le z_\varepsilon(u)\le u, the selected elements of the fiber lie in (u/8,u](u/8,u] after division by ghgh, so An⊆(n/8,n]A_n\subseteq(n/8,n]. If x∣yx\mid y are distinct elements of AnA_n, then y/x∈{2,…,7}y/x\in\{2,\ldots,7\}. Ratios 2,3,4,62,3,4,6 keep (g,h)(g,h) fixed, and each fiber is fork-free by Lemma 4.1. A ratio d∈{5,7}d\in\{5,7\} would mean that the same ss lies in the fiber (g,h)(g,h) and in its child fiber (g,dh)(g,dh), whose argument is u/du/d and whose type is 11 for d=5d=5 and ε\varepsilon for d=7d=7. These are exactly the child states used in (9).

Let pp be the parent’s parity and pdp_d the child’s. An element of the child of parity 1−pd1-p_d is at most zd/2≤u/(2d)<u/8z_d/2\le u/(2d)<u/8, too small for the parent. An element ss of the child of parity pdp_d satisfies s≤zds\le z_d. If pd=pp_d=p, then s>ζp/4≥zds>\zeta_p/4\ge z_d. If pd≠pp_d\ne p, then s>ζp/6≥zds>\zeta_p/6\ge z_d. So no such ss exists. Hence every divisibility relation in AnA_n lies inside a fiber, and AnA_n is fork-free.

The fiber (g,h)(g,h) has hp(ζp)=kε(u)h_p(\zeta_p)=k_\varepsilon(u) elements. Writing m=ghm=gh, the total is

∑m≤n(m,6)=1(R(n/m)−1[5∣m]1B(5n/m)).\sum_{\substack{m\le n\\(m,6)=1}}\left(R(n/m)-1_{[5\mid m]}1_{\mathcal{B}}(5n/m)\right).

In the second sum put m=5m′m=5m'. Since every element of B\mathcal{B} exceeds 55, the range m′≤n/5m'\le n/5 may be extended to m′≤nm'\le n, giving exactly U(n)U(n).

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 u≥1u \ge1 for ϵ=0\epsilon= 0 and ϵ=1\epsilon= 1.

The proof has two computer-verified ingredients.

The base range. Let T0=2⋅77=1,647,086T_0 = 2 \cdot7^7 = 1,647,086. On [1,T0)[1,T_0) the recursion was evaluated exactly. There are 109 pieces for ϵ=0\epsilon= 0 and 108 for ϵ=1\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+bz = au + b with a,b∈Qa,b \in\mathbb{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 (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 uu in the interval.

A finite closure. Normalize the root argument uu to 1. The powers of 4 and 3 below uu are encoded by the two parameters

X=4⌊log⁡4u⌋/u∈(1/4,1],Y=3⌊log⁡3u⌋/u∈(1/3,1],X = 4^{\lfloor\log_4 u \rfloor}/u \in(1/4,1], \qquad Y = 3^{\lfloor\log_3 u \rfloor}/u \in(1/3,1],

which the finite statement allows to vary independently. Its nodes are ν=(i,j)\nu= (i,j) with i,j≥0i,j \ge0 and i+j≤Di+j \le D. The node ν\nu has normalized argument vν=5−i7−jv_\nu= 5^{-i}7^{-j}, type ϵν=1\epsilon_\nu= 1 if i>0i > 0 and ϵν=ϵ\epsilon_\nu= \epsilon if i=0i = 0, and children (i+1,j)(i+1,j) and (i,j+1)(i,j+1). At a node, let L4L_4 be the largest element of X4ZX4^{\mathbb{Z}} not exceeding vνv_\nu, and L3L_3 the largest element of Y3ZY3^{\mathbb{Z}} not exceeding vνv_\nu. Put P=1[vν≥2L4]P = 1_{[v_\nu\ge2L_4]} and Δ=1[vν≥2L3]\Delta= 1_{[v_\nu\ge2L_3]}, and let L4′,L3′L'_4,L'_3 be the analogous quantities at 5vν5v_\nu. The obstruction bit

Q=ϵν1[5vν<54L4′, 109L3′<5vν<43L3′]Q = \epsilon_\nu1_{[5v_\nu< \frac{5}{4}L'_4,\ \frac{10}{9}L'_3 < 5v_\nu< \frac{4}{3}L'_3]}

encodes ϵν1B(5uν)\epsilon_\nu1_B(5u_\nu), where uν=uvνu_\nu= uv_\nu. The errors e0=Q−PΔe_0 = Q-P\Delta and e1=Q−(1−P)(1−Δ)e_1 = Q-(1-P)(1-\Delta) measure how many levels each parity must drop from its value at vνv_\nu. The most recent jumps of h0h_0 at or below vνv_\nu are (a,b)=(L4,L3)(a,b) = (L_4,L_3). Those of h1h_1 are a=2L4a = 2L_4 or L4/2L_4/2 according as P=1P = 1 or 0, and b=2L3b = 2L_3 or 23L3\frac{2}{3}L_3 according as Δ=1\Delta= 1 or 0. The window of parity pp, which is the normalized set of admissible cutoffs, is

  • empty if ep=−1e_p = -1;

  • [max⁡(a,b),vν][\max(a,b),v_\nu] if ep=0e_p = 0;

  • [max⁡(a/4,b),max⁡(a,b))[\max(a/4,b),\max(a,b)) if ep=1e_p = 1 and a>ba>b, and [max⁡(a,b/3),max⁡(a,b))[\max(a,b/3),\max(a,b)) if ep=1e_p = 1 and a≤ba \le b.

Each window endpoint is a rational-linear expression in (X,Y)(X,Y) on each of finitely many explicitly described pieces.

Lemma 4.4 (Closure). For D=5D = 5 and ϵ∈{0,1}\epsilon\in\{0,1\}, the following system in the unknowns X,YX,Y and, for every node ν\nu, a parity πν\pi_\nu and a cutoff ζν∈Q\zeta_\nu\in\mathbb{Q}, is unsatisfiable.

  • Each leaf (i+j=D)(i+j=D) has ζν\zeta_\nu in the window of πν\pi_\nu and ζν≥34vν\zeta_\nu\ge\frac{3}{4}v_\nu.

  • Each node of depth 1,…,D−11,\ldots,D-1 has the state produced by (9), (10) and the priority rule from its children’s data, and some parity is available there.

  • At the root, neither parity is available.

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=7D = 7 (36 nodes) the corresponding system was proved unsatisfiable independently by Z3 [7] and by cvc5 [2]. For D=3,4D = 3,4 it is satisfiable. For D=5D = 5 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 ⌊u⌋\lfloor u \rfloor for both values of ϵ\epsilon. Below T0T_0 we use the table. Let u≥T0u \ge T_0. Every proper descendant has smaller integer part than uu, so its state exists by induction. Every node of depth at most 7 below uu has argument uν=u5−i7−j≥T0/77=2u_\nu= u5^{-i}7^{-j} \ge T_0/7^7 = 2, and 5uν≥105u_\nu\ge10. For such arguments the normalized powers, windows and obstruction bits above coincide with the actual ones. Here hp(z)=kϵν(uν)h_p(z)=k_{\epsilon\nu}(u_\nu) and z≤uνz\leq u_\nu exactly when z/uz/u lies in the corresponding window.

Assume that neither parity is available at (u,ϵ)(u,\epsilon). Take X,YX,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 uu, wherever the state is used. The leaves and internal nodes satisfy their constraints because the recursion succeeds at the smaller arguments uν≤u/5u_\nu\leq u/5, 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 n≤40n\leq40.

The density and the coefficient series

Proof of (4). The function RR is nondecreasing and right-continuous. It jumps only at points of ⟨2,3⟩\langle2,3\rangle, and each jump ΔR(s)\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 N6(y)=#{m≤y:(m,6)=1, m≥1}=y/3+O(1)N_6(y)=\#\{m\leq y:(m,6)=1,\ m\geq1\}=y/3+O(1). Then

∑m≤n(m,6)=1R(n/m)=∑s∈⟨2,3⟩ΔR(s)N6(n/s).\sum_{\substack{m\leq n\\(m,6)=1}}R(n/m)=\sum_{s\in\langle2,3\rangle}\Delta R(s)N_6(n/s).

After division by nn, the terms are dominated by 2/s2/s, and ∑s∈⟨2,3⟩1/s=3\sum_{s\in\langle2,3\rangle}1/s=3. Dominated convergence therefore gives the limit 13∑sΔR(s)/s=13∫1∞R(t)t−2 dt\frac{1}{3}\sum_s\Delta R(s)/s=\frac{1}{3}\int_1^\infty R(t)t^{-2}\,dt. For the B\mathcal{B}-term, each interval [α,β)[\alpha,\beta) of B\mathcal{B} contributes N6(n/α)−N6(n/β)N_6(n/\alpha)-N_6(n/\beta). The intervals beyond any cutoff MM contribute at most n/M+1n/M+1 in total. Hence n−1#{m:(m,6)=1, n/m∈B, m≥1}→13∫Bt−2 dtn^{-1}\#\{m:(m,6)=1,\ n/m\in\mathcal{B},\ m\geq1\}\to\frac{1}{3}\int_{\mathcal{B}}t^{-2}\,dt. Finally, by (2) and

∫1∞⌊log⁡bt⌋t−2 dt=∑k≥1b−k=1/(b−1),\int_1^\infty\lfloor\log_b t\rfloor t^{-2}\,dt=\sum_{k\geq1}b^{-k}=1/(b-1),
13∫1∞R(t)t2 dt=13(1+13+12+∫Edtt2)=1118+13∫Edtt2.\frac{1}{3}\int_1^\infty\frac{R(t)}{t^2}\,dt=\frac{1}{3}\left(1+\frac{1}{3}+\frac{1}{2}+\int_{\mathcal{E}}\frac{dt}{t^2}\right)=\frac{11}{18}+\frac{1}{3}\int_{\mathcal{E}}\frac{dt}{t^2}.

□

Proof of (5). Write E=E4∩E3\mathcal{E}=E_4\cap E_3 with E4=⋃j[2⋅4j,4j+1)E_4=\bigcup_j[2\cdot4^j,4^{j+1}) and E3=⋃b[2⋅3b,3b+1)E_3=\bigcup_b[2\cdot3^b,3^{b+1}), and B=B3∩B4\mathcal{B}=B_3\cap B_4 with B3=⋃b[10⋅3b,12⋅3b)B_3=\bigcup_b[10\cdot3^b,12\cdot3^b) and B4=⋃j[4j,544j)B_4=\bigcup_j[4^j,\frac{5}{4}4^j). For such an intersection, ∫t−2 dt\int t^{-2}\,dt is the sum over the jump points xx of its indicator of ±1/x\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 E4E_4 and E3E_3 coincide only at x=2x=2, where both begin and E\mathcal{E} jumps once. The endpoints of B3B_3 and B4B_4 never coincide. Hence

∫Edtt2=∑k≥0(1E3(2⋅4k)2⋅4k−1E3(4k)4k)+∑k≥0(1E4(2⋅3k)2⋅3k−1E4(3k)3k)−12,\int_{\mathcal{E}}\frac{dt}{t^2}=\sum_{k\geq0}\left(\frac{\mathbf{1}_{E_3}(2\cdot4^k)}{2\cdot4^k}-\frac{\mathbf{1}_{E_3}(4^k)}{4^k}\right)+\sum_{k\geq0}\left(\frac{\mathbf{1}_{E_4}(2\cdot3^k)}{2\cdot3^k}-\frac{\mathbf{1}_{E_4}(3^k)}{3^k}\right)-\frac{1}{2},
∫Bdtt2=∑k≥0(1B3(4k)4k−1B3(544k)544k)+∑k≥0(1B4(10⋅3k)10⋅3k−1B4(12⋅3k)12⋅3k).\int_{\mathcal{B}}\frac{dt}{t^2}=\sum_{k\geq0}\left(\frac{\mathbf{1}_{B_3}(4^k)}{4^k}-\frac{\mathbf{1}_{B_3}(\frac{5}{4}4^k)}{\frac{5}{4}4^k}\right)+\sum_{k\geq0}\left(\frac{\mathbf{1}_{B_4}(10\cdot3^k)}{10\cdot3^k}-\frac{\mathbf{1}_{B_4}(12\cdot3^k)}{12\cdot3^k}\right).

Here the terms 1E3(1)\mathbf{1}_{E_3}(1) and 1E4(1)\mathbf{1}_{E_4}(1) vanish. Let t=[4k]3t=[4^k]_3 and s=[3k]4s=[3^k]_4. Elementary manipulation of mantissas gives

  • 1E3(2⋅4k)=1[t<3/2]\mathbf{1}_{E_3}(2\cdot4^k)=\mathbf{1}_{[t<3/2]} and 1E3(4k)=1[t≥2]\mathbf{1}_{E_3}(4^k)=\mathbf{1}_{[t\geq2]};

  • 1B3(4k)=1[10/9≤t<4/3]\mathbf{1}_{B_3}(4^k)=\mathbf{1}_{[10/9\leq t<4/3]};

  • 1B3(544k)=1[t<16/15 or t≥8/3]\mathbf{1}_{B_3}(\frac{5}{4}4^k)=\mathbf{1}_{[t<16/15\ \text{or}\ t\geq8/3]} for k≥1k\geq1, while for k=0k=0 the right side is 1 but 5/4∉B35/4\notin B_3;

  • 1E4(2⋅3k)=1[s<2]\mathbf{1}_{E_4}(2\cdot3^k)=\mathbf{1}_{[s<2]} and 1E4(3k)=1[s≥2]\mathbf{1}_{E_4}(3^k)=\mathbf{1}_{[s\geq2]};

  • 1B4(10⋅3k)=1[8/5≤s<2]\mathbf{1}_{B_4}(10\cdot3^k)=\mathbf{1}_{[8/5\leq s<2]} and 1B4(12⋅3k)=1[4/3≤s<5/3]\mathbf{1}_{B_4}(12\cdot3^k)=\mathbf{1}_{[4/3\leq s<5/3]}.

Multiplying by 60 therefore gives 60(I−J)=Σ4+Σ3−30−4860(I-J)=\Sigma_4+\Sigma_3-30-48, where I,JI,J are the two integrals and

φ(t)=301[t<3/2]−601[t≥2]−601[10/9≤t<4/3]+481[t<16/15 or t≥8/3],ψ(s)=301[s<2]−601[s≥2]−61[8/5≤s<2]+51[4/3≤s<5/3],\begin{aligned} \varphi(t)&=30\mathbf{1}_{[t<3/2]}-60\mathbf{1}_{[t\geq2]}-60\mathbf{1}_{[10/9\leq t<4/3]}+48\mathbf{1}_{[t<16/15\text{ or }t\geq8/3]},\\ \psi(s)&=30\mathbf{1}_{[s<2]}-60\mathbf{1}_{[s\geq2]}-6\mathbf{1}_{[8/5\leq s<2]}+5\mathbf{1}_{[4/3\leq s<5/3]}, \end{aligned}

which are the functions of Table 1. Here Σ4=∑kφ([4k]3)4−k\Sigma_4=\sum_k\varphi([4^k]_3)4^{-k} and Σ3=∑kψ([3k]4)3−k\Sigma_3=\sum_k\psi([3^k]_4)3^{-k}. Since 180⋅11/18=110180\cdot11/18=110, we obtain 180c=110+60(I−J)=32+Σ4+Σ3180c=110+60(I-J)=32+\Sigma_4+\Sigma_3.

Remark 5.1. The value c=0.67296…c=0.67296\ldots lies in Lebensold’s interval [0.6725,0.6736][0.6725,0.6736] and above the lower bound c≥0.6729c\geq0.6729 reported by Davis.

Returns of the rotation and a small nonzero linear form

Rotation coordinates and jumps

Let α=log⁡4/log⁡3=log⁡34\alpha=\log4/\log3=\log_3 4, which is irrational because no positive power of 4 is a power of 3. For k∈Zk\in\mathbb{Z} we have [4k]3=3{kα}[4^k]_3=3^{\{k\alpha\}} and [3k]4=4{k/α}[3^k]_4=4^{\{k/\alpha\}}. Let φ~(x)=φ(3{x})\widetilde{\varphi}(x)=\varphi(3^{\{x\}}) and ψ~(y)=ψ(4{y})\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θ3^\theta and 4θ4^\theta respectively, are

3θ3^\theta116/1516/1510/910/94/34/33/23/228/38/3
jump of φ~\widetilde{\varphi}+90+90−48-48−60-60+60+60−30-30−60-60+48+48

Table 3.

and

4θ4^\theta14/34/38/58/55/35/32
jump of ψ~\widetilde{\psi}+90+90+5+5−6-6−5-5−84-84

Table 4.

Jump points related by the rotation are grouped into orbits. For φ~\widetilde{\varphi} we use the representatives θ1,…,θ4=log⁡3(1,2,9/5,10/9)\theta_1,\ldots,\theta_4=\log_3(1,2,9/5,10/9), with the logarithm applied coordinatewise. Then

log⁡343=θ1+α−1,log⁡332=θ2−α+1,\log_3\frac{4}{3}=\theta_1+\alpha-1,\qquad\log_3\frac{3}{2}=\theta_2-\alpha+1,
log⁡383=θ2+α−1,log⁡31615=θ3+2α−3.\log_3\frac{8}{3}=\theta_2+\alpha-1,\qquad\log_3\frac{16}{15}=\theta_3+2\alpha-3.

For ψ~\widetilde{\psi} we use θ1′,…,θ4′=log⁡4(1,2,8/5,5/4)\theta'_1,\ldots,\theta'_4=\log_4(1,2,8/5,5/4), with log⁡4(4/3)=θ1′+1−1/α\log_4(4/3)=\theta'_1+1-1/\alpha and log⁡4(5/3)=θ4′+1−1/α\log_4(5/3)=\theta'_4+1-1/\alpha.

Weighting each jump by the power of 4 (respectively 3) corresponding to its orbit shift gives the orbit coefficients

(C1,C2,C3,C4)=(105,−168,−3,−60),(D1,D2,D3,D4)=(105,−84,−6,−15).(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, C1=90+60/4C_1=90+60/4, C2=−30⋅4−60+48/4C_2=-30\cdot4-60+48/4, D1=90+5⋅3D_1=90+5\cdot3 and D4=−5⋅3D_4=-5\cdot3. Each list represents four distinct orbits for its own rotation. No two elements of either list of mantissas have ratio 4a3b4^a3^b with a,b∈Za,b\in\mathbb{Z}. The two lists share the representatives 1 and 2.

Brackets

Lemma 6.1. There are infinitely many quadruples of positive integers (p,q,P,Q)(p,q,P,Q) with

qP−pQ=1,q≤Q,δ:=qα−p>0,0<δ′:=P−Qα<δ.qP-pQ=1,\qquad q\leq Q,\qquad\delta:=q\alpha-p>0,\qquad0<\delta':=P-Q\alpha<\delta.

Along them Q→∞Q\to\infty and δ≤1/Q→0\delta\leq1/Q\to0. Put L=Plog⁡3L=P\log3. Then plog⁡3,qlog⁡4<Lp\log3,q\log4<L and Qlog⁡4>L−log⁡3Q\log4>L-\log3. Moreover ∥mα∥≥δ\lVert m\alpha\rVert\geq\delta for 1≤m<Q1\leq m<Q, and every block of q+Qq+Q consecutive integers kk contains one with {kα−θ}∈[1−δ,1)\{k\alpha-\theta\}\in[1-\delta,1), for every θ∈R\theta\in\mathbb{R}.

Proof. Run the mediant (Stern–Brocot) process for α\alpha starting from 1/1<α<2/11/1<\alpha<2/1. Each bracket p/q<α<P/Qp/q<\alpha<P/Q satisfies qP−pQ=1qP-pQ=1, and the identity qδ′+Qδ=qP−pQ=1q\delta'+Q\delta=qP-pQ=1 holds. When the right endpoint is replaced by the mediant, QQ becomes q+Q≥qq+Q\geq q and δ′\delta' decreases by δ\delta. Thus at the end of every maximal run of right replacements we have q≤Qq\leq Q and 0<δ′<δ0<\delta'<\delta. Since α\alpha is irrational, there are infinitely many such runs, and Qδ≤1Q\delta\leq1. The inequalities involving LL follow from p/q<P/Qp/q<P/Q, Qα<P<Qα+1Q\alpha<P<Q\alpha+1 and q≤Qq\leq Q. Given 1≤m<Q1 \le m < Q and n∈Zn \in\mathbb{Z}, write (m,n)=x(q,p)+y(Q,P)(m,n)=x(q,p)+y(Q,P) with x,y∈Zx,y \in\mathbb{Z}, which is possible because qP−pQ=1qP-pQ=1. Then mα−n=xδ−yδ′m\alpha-n=x\delta-y\delta'. Since 0<m<Q0<m<Q and q≤Qq \le Q, either y=0<xy=0<x, or xx and yy are nonzero with opposite signs. In both cases ∣xδ−yδ′∣≥δ|x\delta-y\delta'| \ge\delta. The last assertion is the three-distance theorem: the q+Qq+Q points {kα}\{k\alpha\} for kk in a block of consecutive integers cut the circle into gaps of lengths δ\delta and δ′\delta' only [25]. In this case the cyclic successor on the indices 0,…,q+Q−10,\ldots,q+Q-1 adds qq modulo q+Qq+Q, stepping by δ\delta if the index increases by qq and by δ′\delta' if it decreases by QQ. The successor is one cycle because gcd⁡(q,Q)=1\gcd(q,Q)=1, and the step lengths sum to Qδ+qδ′=1Q\delta+q\delta'=1. Thus every half-open arc of length δ\delta contains a point. □

The return identity

For a bounded integer sequence (ck)(c_k), a base β∈{3,4}\beta\in\{3,4\} and m≥0m \ge0,

(βm−1)∑k≥0ckβk=∑k<mckβm−k+∑k≥0ck+m−ckβk.(11)(\beta^m-1)\sum_{k\ge0}\frac{c_k}{\beta^k} =\sum_{k<m}c_k\beta^{m-k}+\sum_{k\ge0}\frac{c_{k+m}-c_k}{\beta^k}. \tag*{(11)}

Let φk=φ([4k]3)\varphi_k=\varphi([4^k]_3) and ψk=ψ([3k]4)\psi_k=\psi([3^k]_4). Since qα=p+δq\alpha=p+\delta and p/α=q−δ/αp/\alpha=q-\delta/\alpha, we have φk+q=φ~(kα+δ)\varphi_{k+q}=\widetilde{\varphi}(k\alpha+\delta) and ψk+p=ψ~(k/α−δ/α)\psi_{k+p}=\widetilde{\psi}(k/\alpha-\delta/\alpha). So the differences in (11) are small forward and backward rotations, respectively. Define the visit indicators

Hi(k)=1{kα−θi}≥1−δ,Ki(k)=1{k/α−θi′}<δ/α(k∈Z).H_i(k)=\mathbf{1}_{\{k\alpha-\theta_i\}\ge1-\delta},\qquad K_i(k)=\mathbf{1}_{\{k/\alpha-\theta_i'\}<\delta/\alpha}\qquad(k\in\mathbb{Z}).

Thus Hi(k)=1H_i(k)=1 when the step from kαk\alpha to kα+δk\alpha+\delta crosses θi\theta_i, and Ki(k)=1K_i(k)=1 when the step from k/αk/\alpha to k/α−δ/αk/\alpha-\delta/\alpha crosses θi′\theta_i', with the endpoints as specified by the indicators. Counting crossings of jump points, and shifting indices within orbits, gives

φk+q−φk=90H1(k)+60H1(k−1)−30H2(k+1)−60H2(k)+48H2(k−1)−48H3(k−2)−60H4(k),ψk+p−ψk=−90K1(k)−5K1(k+1)+84K2(k)+6K3(k)+5K4(k+1).\begin{aligned} \varphi_{k+q}-\varphi_k={}&90H_1(k)+60H_1(k-1)-30H_2(k+1)-60H_2(k)\\ &+48H_2(k-1)-48H_3(k-2)-60H_4(k),\\ \psi_{k+p}-\psi_k={}&-90K_1(k)-5K_1(k+1)+84K_2(k)+6K_3(k)+5K_4(k+1). \end{aligned}

Always H1(0)=0H_1(0)=0 and K1(0)=1K_1(0)=1. For every other fixed (i,k)(i,k), the number kα−θik\alpha-\theta_i (respectively k/α−θi′k/\alpha-\theta_i') is not an integer, so the corresponding Hi(k)H_i(k) and Ki(k)K_i(k) 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

Aq=∑k<qφk4q−k,Bp=∑k<pψk3p−k,N=(3p−1)Aq+(4q−1)(Bp−90)∈Z.A_q=\sum_{k<q}\varphi_k4^{q-k},\qquad B_p=\sum_{k<p}\psi_k3^{p-k},\qquad N=(3^p-1)A_q+(4^q-1)(B_p-90)\in\mathbb{Z}.

For all sufficiently late brackets,

(4q−1)(3p−1)(180c−32)−N=(3p−1)∑i=14Ci∑k≥1Hi(k)4k−(4q−1)∑i=14Di∑k≥1Ki(k)3k.(12)\begin{aligned} (4^q-1)(3^p-1)(180c-32)-N ={}&(3^p-1)\sum_{i=1}^{4}C_i\sum_{k\ge1}\frac{H_i(k)}{4^k}\\ &-(4^q-1)\sum_{i=1}^{4}D_i\sum_{k\ge1}\frac{K_i(k)}{3^k}. \tag*{(12)} \end{aligned}

The constant −90-90 comes from the backward visit K1(0)=1K_1(0)=1 at index zero, whose step crosses the jump +90+90 of ψ~\widetilde{\psi} at 00. The forward convention excludes the corresponding forward visit, since H1(0)=0H_1(0)=0.

Events and two cutoffs

Expanding the right side of (12) writes it as a sum of events (d,u)(d,u), each consisting of an integer coefficient dd and a {2,3}\{2,3\}-unit u=e−τu=e^{-\tau} with time τ\tau. A visit Hi(k)=1H_i(k)=1 produces the events (Ci,3p/4k)(C_i,3^p/4^k) and (−Ci,4−k)(-C_i,4^{-k}), with times klog⁡4−plog⁡3k\log4-p\log3 and klog⁡4k\log4. A visit Ki(k)=1K_i(k)=1 produces (−Di,4q/3k)(-D_i,4^q/3^k) and (Di,3−k)(D_i,3^{-k}), with times klog⁡3−qlog⁡4k\log3-q\log4 and klog⁡3k\log3. There are sixteen event families, given by four unit types times four orbits. For a real TT, let S(T)S(T) be the sum of dud u over the events with time τ<T\tau<T.

Lemma 6.3. For all sufficiently late brackets:

:::`

  1. (i) Within each family, distinct event times differ by at least L/2L/2.

  2. (ii) Distinct visits Hi(k)=Hj(k′)=1H_i(k)=H_j(k')=1, with (i,k)≠(j,k′)(i,k)\ne(j,k'), satisfy ∣k−k′∣≥2|k-k'|\ge2.

  3. (iii) There are cutoffs 4L<T1<5L4L<T_1<5L and 10L<T2<11L10L<T_2<11L such that no event time lies in [Tj,Tj+L/100][T_j,T_j+L/100].

  4. (iv) For T∈{T1,T2}T\in\{T_1,T_2\}, the right side of (12) differs from S(T)S(T) by at most e−T−L/200e^{-T-L/200}.

Proof. For (i), two visits k<k′k<k' to the same arc of length δ\delta satisfy ∥(k′−k)α∥<δ\|(k'-k)\alpha\|<\delta, so k′−k≥Qk'-k\ge Q by Lemma 6.1, and Qlog⁡4≥L/2Q\log4\ge L/2. The backward families are similar. The inequality ∥(k′−k)/α∥<δ/α\|(k'-k)/\alpha\|<\delta/\alpha gives a positive integer nn for sufficiently small δ\delta with ∣(k′−k)−nα∣<δ|(k'-k)-n\alpha|<\delta. Hence n≥Qn\ge Q and k′−k>nα−1k'-k>n\alpha-1, so (k′−k)log⁡3>L−2log⁡3≥L/2(k'-k)\log3>L-2\log3\ge L/2.

For (ii), otherwise ±α\pm\alpha or 00 would be within δ\delta of θi−θj\theta_i-\theta_j modulo 11, for one of finitely many pairs. For i≠ji\ne j this fails once δ\delta is small, because the representatives lie in distinct orbits. For i=ji=j and ∣k−k′∣=1|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.01L1.01L, so at most 48 events are relevant. Among the 49 disjoint candidate intervals

[4L+ℓL/50,4L+ℓL/50+L/100],1≤ℓ≤49,[4L+\ell L/50,4L+\ell L/50+L/100],\qquad1\le\ell\le49,

at least one is free of them. The choice of T2T_2 is the same. For (iv), the omitted events have times at least T+L/100T+L/100, spaced by L/2L/2 within each family, and all coefficients satisfy ∣d∣≤168|d|\le168. So the omitted part is at most

16⋅168e−T−L/100(1−e−L/2)−1≤e−T−L/20016\cdot168e^{-T-L/100}(1-e^{-L/2})^{-1}\le e^{-T-L/200}

for large LL.

Two truncations differ

Proposition 6.4 (Two truncations differ). For all sufficiently late brackets, S(T1)≠S(T2)S(T_1)\ne S(T_2).

Proof. Write S=D+GS=D+G, where DD collects the events with denominator 4k4^k and GG those with denominator 3k3^k. Every G(T)G(T) is 2-adically integral. In D(T)D(T), the two events of a visit Hi(k)=1H_i(k)=1 combine to a term with numerator Ci(3p−1)C_i(3^p-1) if both are retained, and Ci3pC_i3^p if only the earlier one, 3p/4k3^p/4^k, is retained. Note that (v2(C1),v2(C2),v2(C3),v2(C4))=(0,3,0,2)(v_2(C_1),v_2(C_2),v_2(C_3),v_2(C_4))=(0,3,0,2).

At T1<5LT_1<5L, every retained dyadic event has klog⁡4<5L+plog⁡3≤6Lk\log4<5L+p\log3\le6L, so either D(T1)=0D(T_1)=0 or v2(D(T1))log⁡2>−6Lv_2(D(T_1))\log2>-6L. At T2T_2, Lemma 6.1 gives a visit kk with T2−2L<klog⁡4<T2T_2-2L<k\log4<T_2. Its events are retained. Indeed, the open interval for kk has length 2L/log⁡4>2Q≥q+Q2L/\log4>2Q\ge q+Q. Let k∗k^* be the largest retained dyadic index. Then k∗log⁡4>8Lk^*\log4>8L, and by Lemma 6.3(ii) all other retained indices are at most k∗−2k^*-2.

If the unshifted event at k∗k^* is retained, all retained indices have both events retained. Then

D(T2)=(3p−1)∑Ci4−k,D(T_2)=(3^p-1)\sum C_i4^{-k},

where the term with k=k∗k=k^* has strictly smallest valuation. Using v2(3p−1)log⁡2≤plog⁡3≤Lv_2(3^p-1)\log2\le p\log3\le L, gives v2(D(T2))log⁡2≤L+3log⁡2−k∗log⁡4<−6Lv_2(D(T_2))\log2\le L+3\log2-k^*\log4<-6L. Otherwise the k∗k^* term has numerator Ci3pC_i3^p and again has strictly smallest valuation, so v2(D(T2))log⁡2≤3log⁡2−k∗log⁡4<−6Lv_2(D(T_2))\log2\le3\log2-k^*\log4<-6L. In both cases D(T2)−D(T1)D(T_2)-D(T_1) has valuation less than −6L/log⁡2<0-6L/\log2<0. It cannot be cancelled by the 2-adically integral number G(T2)−G(T1)G(T_2)-G(T_1).

Corollary 6.5. Suppose c∈Qc\in\mathbb{Q}, and put z=180c−32z=180c-32. For all sufficiently late brackets there are T∈{T1,T2}T\in\{T_1,T_2\}, an integer m≤404m\le404, {2,3}\{2,3\}-units u1,…,um≥e−Tu_1,\ldots,u_m\ge e^{-T} and coefficients d1,…,dmd_1,\ldots,d_m in the finite set {±z,±3,±6,±15,±60,±84,±105,±168}\{\pm z,\pm3,\pm6,\pm15,\pm60,\pm84,\pm105,\pm168\} such that

E:=∑i=1mdiui−Nsatisfies0<∣E∣≤e−T−L/200andH(N:u1:⋯:um)≤e27L.E:=\sum_{i=1}^{m}d_i u_i-N\qquad\text{satisfies}\qquad0<|E|\le e^{-T-L/200}\qquad\text{and}\qquad H(N:u_1:\cdots:u_m)\le e^{27L}.

Proof. Let E(T)=(4q−1)(3p−1)z−N−S(T)E(T)=(4^q-1)(3^p-1)z-N-S(T). By Proposition 6.4, E(T1)−E(T2)=S(T2)−S(T1)≠0E(T_1)-E(T_2)=S(T_2)-S(T_1)\ne0, so some E(T)E(T) is nonzero, and by (12) and Lemma 6.3(iv) it is at most e−T−L/200e^{-T-L/200} in absolute value.

:::`

Expanding the head gives the units 4q34q^3, 4q4q, 3p3^p, 11 with coefficients zz, −z-z, −z-z, zz. The retained events contribute their units with the negatives of their coefficients. Each family has at most 2⋅11+32\cdot11+3 retained events because the times lie in [−L,11L)[-L,11L) and are L/2L/2-separated. Thus m≤4+16⋅25=404m\leq4+16\cdot25=404. All denominators divide 4⌊12L/log⁡4⌋3⌊12L/log⁡3⌋≤e24L4\lfloor12L/\log4\rfloor^3\lfloor12L/\log3\rfloor\leq e^{24L}, and all coordinates, including NN, are at most 366e2L366e^{2L} in absolute value. Hence H(N:u1:⋯:um)≤366e26L≤e27LH(N:u_1:\cdots:u_m)\leq366e^{26L}\leq e^{27L} for large LL.

A three-place Subspace Theorem and the proof of irrationality

The covering theorem

Theorem 7.1. Let d≥2d\geq2, let A∈GLd(Q)A\in\mathrm{GL}_d(\mathbb{Q}), and let cv,ic_{v,i} (v∈{∞,2,3}v\in\{\infty,2,3\}, 1≤i≤d1\leq i\leq d) be real numbers with c2,i,c3,i≤0c_{2,i},c_{3,i}\leq0 and ∑v,icv,i<0\sum_{v,i}c_{v,i}<0. There is a finite set of proper linear subspaces of Qd\mathbb{Q}^d such that, for every real q≥0q\geq0, every x∈Zdx\in\mathbb{Z}^d with

∣(Ax)i∣≤ec∞,iq,∣xi∣2≤ec2,iq,∣xi∣3≤ec3,iq(1≤i≤d)(13)|(Ax)_i|\leq e^{c_{\infty,i}q},\qquad|x_i|_2\leq e^{c_{2,i}q},\qquad|x_i|_3\leq e^{c_{3,i}q}\qquad(1\leq i\leq d) \tag*{(13)}

lies in one of them.

Remark 7.2. Theorem 7.1 is a special case of the pp-adic Subspace Theorem of Schlickewei [21], which extends Schmidt’s theorem [22, 23]. See also [24, 4, 10, 9]. Indeed, let M=max⁡(0,max⁡ic∞,i)M=\max(0,\max_i c_{\infty,i}) and ρ=−∑cv,i\rho=-\sum c_{v,i}. If M=0M=0 the solutions are bounded, hence finite in number. Otherwise, for C≥1C\geq1 sufficiently large we have max⁡i∣xi∣≤CeMq\max_i|x_i|\leq Ce^{Mq}, so the solutions of (13) with max⁡i∣xi∣≥C2\max_i|x_i|\geq C^2 satisfy

∏v∈{∞,2,3}∏i=1d∣Lv,i(x)∣v≤e−ρq≤(max⁡i∣xi∣)−ρ/(2M),\prod_{v\in\{\infty,2,3\}}\prod_{i=1}^{d}|L_{v,i}(x)|_v\leq e^{-\rho q}\leq\left(\max_i|x_i|\right)^{-\rho/(2M)},

with L∞,i(x)=(Ax)iL_{\infty,i}(x)=(Ax)_i and L2,i(x)=L3,i(x)=xiL_{2,i}(x)=L_{3,i}(x)=x_i. This is the inequality of the Subspace Theorem.

For a rational linear form ℓ(x)=∑aixi\ell(x)=\sum a_ix_i with ak≠0a_k\neq0, put

Φℓ,k(x)=∣ℓ(x)∣∏i≠k∣xi∣∏i∣xi∣2∣xi∣3.\Phi_{\ell,k}(x)=|\ell(x)|\prod_{i\neq k}|x_i|\prod_i|x_i|_2|x_i|_3.

Theorem 7.3 (One-form covering). Let n≥2n\geq2, ℓ\ell and kk be as above, and ε>0\varepsilon>0. There are finitely many nonzero a(1),…,a(s)∈Qna^{(1)},\ldots,a^{(s)}\in\mathbb{Q}^n such that every nonzero x∈Z[1/6]nx\in\mathbb{Z}[1/6]^n with Φℓ,k(x)<H(x)−ε\Phi_{\ell,k}(x)<H(x)^{-\varepsilon} satisfies a(j)⋅x=0a^{(j)}\cdot x=0 for some jj.

Proof. Multiplying xx by 2a3b2^a3^b changes neither Φℓ,k\Phi_{\ell,k} nor HH, so we may assume x∈Znx\in\mathbb{Z}^n. Dividing xx by its gcd gg multiplies Φℓ,k\Phi_{\ell,k} by g0−n≤1g_0^{-n}\leq1, where g0g_0 is the part of gg prime to 66, and preserves HH. So we may assume xx primitive. Vectors with a zero coordinate, or with ℓ(x)=0\ell(x)=0, lie in coordinate hyperplanes or in ker⁡ℓ\ker\ell, and primitive vectors of bounded height are finitely many.

For the rest put q=log⁡H(x)q=\log H(x). The logarithms of the 3n3n local factors, divided by qq, lie in a bounded range and sum to less than −ε-\varepsilon. 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 H(x)H(x). At 22 and 33, a nonzero integer coordinate has pp-adic absolute value between H(x)−1H(x)^{-1} and 11. Rounding the normalized logarithms up to mesh ε/(6n)\varepsilon/(6n) gives one of finitely many profiles cc, each with ∑c≤−ε/2\sum c\leq-\varepsilon/2 and c2,i,c3,i≤0c_{2,i},c_{3,i}\leq0, such that xx satisfies (13) for the matrix AA obtained from the identity by replacing row kk with (a1,…,an)(a_1,\ldots,a_n). 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 m≥1m\geq1, d∈Qmd\in\mathbb{Q}^m and ε>0\varepsilon>0. There is C>0C>0 such that for all N∈ZN\in\mathbb{Z}, all positive {2,3}\{2,3\}-units u1,…,umu_1,\ldots,u_m, and all 0<t≤min⁡(1,u1,…,um)0<t\leq\min(1,u_1,\ldots,u_m),

E=∑i=1mdiui−N≠0⟹∣E∣≥CtH(N:u1:⋯:um)−ε.E=\sum_{i=1}^{m}d_i u_i-N\neq0\quad\Longrightarrow\quad|E|\geq CtH(N:u_1:\cdots:u_m)^{-\varepsilon}.

The same holds for pure forms E=∑diuiE = \sum d_i u_i, with H(u1:⋯:um)H(u_1 : \cdots: u_m).

Proof. Use induction on mm, first for pure forms and then for mixed forms. For a pure form with m=1m = 1, ∣E∣=∣d1∣u1≥∣d1∣t|E| = |d_1|u_1 \ge|d_1|t, and for a mixed form with no units, ∣E∣=∣N∣≥1|E| = |N| \ge1. For a pure form with m≥2m \ge2 and E≠0E \ne0, pick kk with dk≠0d_k \ne0. By the product formula ∣u∣1∣u∣2∣u∣3=1|u|_1|u|_2|u|_3 = 1 for units, so Φ(u)=∣E∣/uk\Phi(u) = |E|/u_k. If Φ(u)≥H(u)−ε\Phi(u) \ge H(u)^{-\varepsilon}, then ∣E∣≥ukH(u)−ε≥tH(u)−ε|E| \ge u_kH(u)^{-\varepsilon} \ge tH(u)^{-\varepsilon}. Otherwise, by Theorem 7.3, uu lies on one of finitely many hyperplanes a⋅u=0a \cdot u = 0. Solving for a coordinate with ai0≠0a_{i_0} \ne0 writes EE as a pure form in the remaining m−1m - 1 units with one of finitely many coefficient vectors. The value EE is unchanged and the height of the shorter vector is at most H(u)H(u), so the induction hypothesis applies.

For a mixed form, take NN as the distinguished coordinate. If N=0N = 0, we are in the pure case. Otherwise Φ(N,u)=∣E∣∣N∣2∣N∣3≤∣E∣\Phi(N,u) = |E||N|_2|N|_3 \le|E|, which gives the bound off the exceptional hyperplanes. On a hyperplane a0N+∑aiui=0a_0N + \sum a_i u_i = 0, if a0≠0a_0 \ne0, eliminate NN and obtain a pure form in the same units. If a0=0a_0 = 0, eliminate a unit and obtain a mixed form with m−1m - 1 units. Finitely many coefficient vectors occur, and CC is the minimum of the resulting positive constants. □

Proof of Theorem 1.3

Proof. Suppose c∈Qc \in\mathbb{Q}. By Corollary 6.5 and the pigeonhole principle, there are an infinite sequence of brackets with L→∞L \to\infty, a fixed m≤404m \le404, and a fixed coefficient vector dd, for which 0<∣E∣≤e−T−L/2000 < |E| \le e^{-T-L/200} and H(N:u)≤e27LH(N : u) \le e^{27L}. Apply Proposition 7.4 with ε=ε0=1/10800\varepsilon= \varepsilon_0 = 1/10800 and t=e−Tt = e^{-T}. This is allowed because every unit is at least e−Te^{-T}. Since 27ε0=1/40027\varepsilon_0 = 1/400,

Ce−T−L/400≤Ce−TH(N:u)−ε0≤∣E∣≤e−T−L/200,Ce^{-T-L/400} \le Ce^{-T}H(N : u)^{-\varepsilon_0} \le|E| \le e^{-T-L/200},

so C≤e−L/400C \le e^{-L/400} for all LL in an unbounded set. This is impossible. Hence cc 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.

  1. Lattice model. Let ui=⌈−c2,iq/log⁡2⌉u_i = \lceil-c_{2,i}q/\log2 \rceil and vi=⌈−c3,iq/log⁡3⌉v_i = \lceil-c_{3,i}q/\log3 \rceil. The solutions of (13) are the points of the lattice Λq=diag⁡(2ui3vi)Zd\Lambda_q = \operatorname{diag}(2^{u_i}3^{v_i})\mathbb{Z}^d in the box ∥diag⁡(e−c∞,iq)Ax∥∞≤1\left\| \operatorname{diag}(e^{-c_{\infty,i}q})Ax \right\|_\infty\le1. The finite places thus enter only through divisibility.

  1. Successive minima. For every full-rank lattice Γ⊂Rn\Gamma\subset\mathbb{R}^n the Euclidean successive minima satisfy covol⁡(Γ)/n!≤∏iλi≤(2/3)n(n−1)/2covol⁡(Γ)\operatorname{covol}(\Gamma)/n! \le\prod_i \lambda_i \le(2/\sqrt{3})^{n(n-1)/2}\operatorname{covol}(\Gamma). The upper bound comes from a non-algorithmic reduced basis in the spirit of Lenstra–Lenstra–Lovász [16].

  1. A gap and Davenport’s lemma. For large qq with a nonzero solution, the covolume forces an index kk with λk+1/λk>eγq\lambda_{k+1}/\lambda_k > e^{\gamma q}, where γ=ρ/(2d(d−1))\gamma= \rho/(2d(d-1)). A rounding lemma of Davenport type produces an integral basis h1,…,hdh_1,\ldots,h_d of Λq\Lambda_q with good local bounds such that all solutions lie in span⁡(h1,…,hk)\operatorname{span}(h_1,\ldots,h_k).

  1. Compound reduction. Passing to the (d−k)(d-k)th compound matrix, the (dk)−1\binom{d}{k} - 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.

  1. Height dichotomy. A hyperplane spanned by solutions at parameter qq either belongs to a finite exceptional family, indexed by support patterns, or has a normal vector of logarithmic height at least ρq/4−O(1)\rho q/4 - O(1). The proof uses only the elementary inequality ∣z∣1∣z∣2∣z∣3≥1|z|_1|z|_2|z|_3 \ge1 for nonzero integers zz.

(6) Roth’s lemma. For β=a/b∈Q\beta= a/b \in\mathbb{Q} in lowest terms let h(β)=log⁡max⁡(∣a∣,∣b∣)h(\beta) = \log\max(\lvert a\rvert, \lvert b\rvert), and let ∥P∥1\lVert P\rVert_{1} be the sum of the absolute values of the coefficients of PP. If 0≠P∈Z[t1,…,tm]0 \ne P \in\mathbb{Z}[t_{1}, \ldots, t_{m}] has deg⁡tiP≤ri\deg_{t_i} P \le r_i, ri+1≤θrir_{i+1} \le\theta r_i with θ=η2m−1\theta= \eta^{2^{m-1}} and 0<η≤120 < \eta\le\frac{1}{2}, and log⁡∥P∥1+4mr1≤θrih(βi)\log\lVert P\rVert_{1} + 4mr_1 \le\theta r_i h(\beta_i) for all ii, then the index of PP at β∈Qm\beta\in\mathbb{Q}^{m} with weights rr is at most 2mη2m\eta. 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 qq along an unbounded set of parameters. Choose mm well-separated parameters and degrees rh≈D/qhr_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.

(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 cc.

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.

ContentRepresentative componentsLines
Grid theorem, upper bound, construction, recursion, bridge to the closure (§§ § 2–§ 4)GridBridge, GlobalUpper, CutoffRecursion, ClosureInduction, GlobalExact7,816
Base-range table and its checks (§ 4)BaseTableData, PolicyBaseIntervalsCompact9,976
Closure certificate and its checkers (Lemma 4.4)PolicyBitsetRUP, PolicyLinearCertificate, ClosureInputReflection32,649
Density, series, returns, nonvanishing, rigidity (§§ § 5–§ 7)CoefficientSeries, ReturnDifferenceIdentity, ReturnTruncationNonzero, OneFormRigidity8,469
Roth’s lemma (§ 7.4, step 6)GeneralizedWronskian, IntegerRothTheorem3,568
Theorem 7.1 (§ 7.4)LatticeSuccessiveMinima, BalancedAuxiliaryPolynomial, RationalThreePlaceSubspaceTheorem11,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 10610^{6}. 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 nn, including the empty sum for n=0n = 0, 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 log⁡4/log⁡3\log4 / \log3. It uses the Subspace Theorem only for linear forms in {2,3}\{2, 3\}-integers, and no finiteness theorem for SS-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. [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. [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. [3]T. F. Bloom, Erdős Problem #1062, https://www.erdosproblems.com/1062. Accessed 21 September 2026.
  4. [4]E. Bombieri and W. Gubler, Heights in Diophantine Geometry, New Mathematical Monographs 4, Cambridge University Press, Cambridge, 2006.
  5. [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. [6]D. Davis, Forbidden subgraphs in divisor graphs and an Erdős divisibility problem, preprint, arXiv:2604.17613 (2026).
  7. [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. [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. [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. [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. [11]Google DeepMind, Formal Conjectures, file FormalConjectures/ErdosProblems/1062.lean, https://github.com/google-deepmind/formal-conjectures. Accessed 21 September 2026.
  12. [12]S. Goel, R. Lunia and A. Ray, Diophantine approximation and the subspace theorem, preprint, arXiv:2502.00731 (2025).DOI
  13. [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. [14]R. K. Guy, Unsolved Problems in Number Theory, 3rd ed., Problem Books in Mathematics, Springer, New York, 2004.
  15. [15]K. Lebensold, A divisibility problem, Stud. Appl. Math. 56 (1977), no. 3, 291–294.DOI
  16. [16]A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515–534.
  17. [17]Lean FRO, comparator, https://github.com/leanprover/comparator.
  18. [18]Lean FRO, lean4export, https://github.com/leanprover/lean4export.
  19. [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. [20]K. F. Roth, Rational approximations to algebraic numbers, Mathematika 2 (1955), 1–20, corrigendum 168.
  21. [21]H. P. Schlickewei, The p-adic Thue–Siegel–Roth–Schmidt theorem, Arch. Math. (Basel) 29 (1977), 267–270.
  22. [22]W. M. Schmidt, Norm form equations, Ann. of Math. (2) 96 (1972), 526–551.DOI
  23. [23]W. M. Schmidt, Diophantine Approximation, Lecture Notes in Math. 785, Springer, Berlin, 1980.
  24. [24]W. M. Schmidt, Diophantine Approximations and Diophantine Equations, Lecture Notes in Math. 1467, Springer, Berlin, 1991.DOI
  25. [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. [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

Paper details

vlnc:W_byzrtnav
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Codex, Anthropic’s Claude

View statement
Looking for related papers…
Contents