Proof. For any squarefree \(l\) supported on the small primes, the simultaneous bad conditions specify one class of the progression coordinate modulo \(l\). Their count is \(J/l+O(1)\), with an absolute error independent of the step and the classes. Apply Lemma 3 at level \(J^{1/2}\). Its sieve parameter is \(v/2\), and the remainder sum is \[\ll J^{1/2}(1+\log J)^{C_2}\] for an absolute fixed \(C_2\). After division by \(JV_{\mathrm{sm}}(u)\), this is \[\ll J^{-1/2}(1+\log J)^{C_2}\log u.\] For all sufficiently large \(u\) this is at most \(e^{-c_1v}\) uniformly for \(v\ge v_0\), on decreasing \(c_1\) and increasing \(v_0\) if necessary. The relative fundamental-lemma error has the same form. This proves (10).

For (9), sieve only by primes at most \(u^\theta\), where \(0<\theta<1\) is fixed sufficiently small in terms of \(\eta\). At level \(J^{1/2}\) the sieve parameter is at least \(\eta/(2\theta)\) and can therefore be made larger than \(s_0\). The upper fundamental lemma gives \[N\ll JV_{\mathrm{sm}}(u^\theta)+J^{1/2}(1+\log J)^{C_2} \ll_\eta JV_{\mathrm{sm}}(u),\] using Mertens and \(J\ge u^\eta\). The same calculation covers either endpoint convention and nonintegral \(J\), since each intersection still has an \(O(1)\) endpoint error. ◻

Proof. The delay equation gives the integral identity \[ u\rho(u)=\int_{u-1}^{u}\rho(v)\,dv\qquad(u\ge1). \tag{25}\] For example, both sides agree at \(u=1\), and their derivatives agree where the delay equation applies. The identity and the delay equation give positivity and monotonicity: a first zero of \(\rho\) would contradict the positive integral of its immediately preceding values. Monotonicity gives the upper bound in (23). Integrating first over the lower half of each of two unit intervals gives \[\rho(u)\ge\frac{\rho(u-\tfrac12)}{2u} \ge\frac{\rho(u-1)}{4u(u-\tfrac12)} \ge\frac{\rho(u-1)}{4u^2}.\] The upper ratio bound also shows that \(\rho\) tends to zero faster than any exponential.

The negative logarithmic derivative is at least \(1\). If it is at least \(\lambda\) on a tail, then, on a later tail, \[\int_{u-1}^{u}\rho(v)\,dv \le \rho(u-1)\frac{1-e^{-\lambda}}{\lambda}.\] Equation (25) consequently improves the lower bound to \(\lambda/(1-e^{-\lambda})\). Iteration tends to infinity, since this map is strictly larger than its argument and has no finite positive fixed point. This proves (24).

Directly from the delay equations and the initial conditions, \[ F(s)-f(s)=c_0(s),\qquad F(s)+f(s)=A\omega_{\rm Bu}(s)\qquad(s\ge1). \tag{26}\] Here the continuous Buchstab function is determined by \(s\omega_{\rm Bu}(s)=1\) on \([1,2]\) and \((s\omega_{\rm Bu}(s))'=\omega_{\rm Bu}(s-1)\) above \(2\); its limit is stated in Section 2. For the first equality, the equation for \(s(F-f)\) is the negative delay equation for \(A\rho(s-1)\); for the second, it is the Buchstab equation with initial value \(A/s\). We next prove the individual positivity and future integrals; these do not follow merely by taking the difference in (26).

To prove these properties, we use an auxiliary absorbing chain. This chain establishes positivity of the deficits; the harmonic-path chain will instead be defined from the derivative weights below. For \(s\ge2\), give the auxiliary chain transition density \[ \frac{c_0(t)}{s c_0(s)}\,\mathbf 1_{\{t\ge s-1\}}\,dt, \tag{27}\] and absorb it on reaching \([1,2)\). Its normalization is \[\int_{s-1}^{\infty}c_0(t)\,dt =A\int_{s-2}^{\infty}\frac{\rho(v)}{v+1}\,dv =A\rho(s-1)=s c_0(s).\] The integration at infinity is justified by the decay already proved. The excess of the next state above \(s-1\) has tail \[\frac{\rho(s-1+h)}{\rho(s-1)}\qquad(h\ge0).\] For large \(s\), (24) bounds this tail by \(e^{-\lambda h}\), with \(\lambda\) as large as desired. For \(\lambda>1\), therefore, \[\mathbb E(e^{s_{\rm next}}\mid s) \le e^{s-1}\frac{\lambda}{\lambda-1}.\] Taking \(\lambda=2\) makes this a strict contraction of \(V(s)=e^s\), with factor \(2/e<1\), outside a fixed compact. Stopped drift implies almost sure return to that compact. From any state in the compact, successive draws in \([s-1,s-1+1/4]\) reach \([1,2)\) within a bounded number of steps, with probability bounded below independently of the initial state in the compact. The densities in these intervals have a positive compact lower bound. Repeating the attempt after each return proves almost sure absorption.

Alternate labels \(a,c\) at every draw. At the terminal state \(t\) assign fractions \(1/c_0(t)\) and \(1-1/c_0(t)\) to the two labels, respectively. Since \(c_0(t)=A/t\) on \([1,2)\), both terminal fractions lie in a fixed compact subinterval of \((0,1)\). The expected terminal fraction, multiplied by \(c_0(s)\), defines positive functions \(a^\circ(s),c^\circ(s)\) with \[a^\circ+c^\circ=c_0,\qquad a^\circ,c^\circ\asymp c_0,\] and terminal values \(a^\circ=1,\ c^\circ=c_0-1\) on \([1,2)\). The first-step equations give \[s a^\circ(s)=\int_{s-1}^{\infty}c^\circ(t)\,dt,\qquad s c^\circ(s)=\int_{s-1}^{\infty}a^\circ(t)\,dt \qquad(s\ge2).\] In particular these functions are continuous from the right at \(2\).

Set \(U=(2+c^\circ-a^\circ)/A\). The last two equations imply \((sU(s))'=U(s-1)\) above \(2\), in integrated form, while \(sU(s)=1\) on \([1,2)\). Also \(U(s)\to 2/A=e^{-\gamma}\), because \(a^\circ,c^\circ\) are bounded by \(c_0\). There can be no jump at \(2\) relative to the continuous Buchstab solution. Indeed, a jump \(\delta\) in \(sU(s)\) there would give a difference \(\delta H(s)\), where \(H(s)=1/s\) on \([2,3]\) and \((sH(s))'=H(s-1)\) thereafter. The bound \(H\ge1/3\) on \([2,3]\) persists by induction: if it holds up to an integer \(n\ge3\), then for \(n\le s\le n+1\), \[sH(s)=nH(n)+\int_n^s H(v-1)\,dv\ge n/3+(s-n)/3.\] For either sign of \(\delta\ne0\), this contradicts \(U(s)-\omega_{\rm Bu}(s)\to0\), using the independently proved Buchstab limit in Lemma 42. Thus \(U=\omega_{\rm Bu}\). Together with \(a^\circ+c^\circ=c_0\) and (26), this identifies \(a^\circ=a,\ c^\circ=c\), proving (20) and both future integrals for \(s\ge2\).

Finally \(c(s)=A/s-1\) and \(a=1\) below \(2\). The equation at \(s=2\) gives \(\int_1^\infty a=A-2\); hence for \(1\le s\le2\), \[\int_{s-1}^{\infty}a(t)\,dt=2-s+A-2=A-s=s c(s).\] This proves the remaining range of (22). ◻

Proof. On the ordinary ranges the delay equations give \[ \phi_\mathrm e(s)=s\bigl(a(s)+c(s-1)\bigr),\qquad \phi_\mathrm o(s)=s\bigl(c(s)+a(s-1)\bigr). \tag{30}\] The second expression uses \(a=1\) on \([0,1]\). On the extensions, the explicit formulas are \[\phi_\mathrm e(s)=A\left(\frac{s}{s-1}-\log(s-1)\right),\qquad \phi_\mathrm o(s)=A\quad(0.95\le s\le3).\] These formulas and Lemma 7 prove positivity. Differentiation gives \[\begin{align*} \phi_\mathrm e'(s)&=-\frac{s}{(s-1)^2}\phi_\mathrm o(s-1) &&(s\ge1.98),\tag{31}\\ \phi_\mathrm o'(s)&=-\frac{s}{(s-1)^2}\phi_\mathrm e(s-1) &&(s>3), \tag{32}\end{align*}\] at points of differentiability; the odd weight is constant below \(3\). Equation (30) and (20) give (29), and in particular both weights vanish at infinity. Integrating (31) and (32) backwards from infinity gives (28). For the even extension, the lower endpoint lies below \(1\), where the explicitly constant odd weight gives exactly the displayed continuation. For odd \(s\le3\), the lower endpoint is \(2\), so the integral is constant, as required.

On a tail, (23) and (29) give \[\frac{\phi_{i'}(s-1)}{\phi_i(s)}=O(s^2).\] The derivative formulas then bound the absolute logarithmic derivatives by a polynomial (in fact \(O(s)\) on a tail). On the remaining compact ranges the explicit positive functions and their piecewise derivatives give fixed bounds. The weights are locally absolutely continuous by (28); integrating the logarithmic derivative gives the stated Lipschitz bound. Finally the same comparison gives a positive constant times \[\frac{\rho(s-3)}{s\rho(s-2)} =\frac{s-2}{s}\left(-\frac{\rho'(s-2)}{\rho(s-2)}\right)\] as a lower bound for either negative logarithmic derivative on a tail. Apply (24). ◻

Proof. For sufficiently large current \(s\), the excess of the next state over \(s-1\) has tail \[\mathbb P(s_{\rm next}\ge s-1+h\mid i,s) =\frac{\phi_i(s+h)}{\phi_i(s)}\qquad(h\ge0).\] Here the support minimum is \(s-1\) for either type, and the identity follows from (28). Lemma 8 makes this tail at most \(e^{-\lambda h}\), with any fixed large \(\lambda\), outside a sufficiently large compact. Thus \(V(i,s)=e^s\) satisfies \[\mathbb E(V(i_{\rm next},s_{\rm next})\mid i,s) \le \kappa V(i,s)+C,\qquad \kappa<1,\] and the constant term can be omitted outside a larger compact. On the compact, finiteness and uniform boundedness of the expectation follow from the superexponential tails of the weights.

Choose a compact set \(C_0\) and \(\alpha>1\) such that \(\mathbb E(V_{\rm next}\mid i,s)\le V(i,s)/\alpha\) outside \(C_0\). Stopping the nonnegative supermartingale \(\alpha^{n\wedge\sigma}V(i_{n\wedge\sigma},s_{n\wedge\sigma})\), where \(\sigma\) is the first entrance to \(C_0\), gives \[\mathbb E_{i,s}\alpha^\sigma\le V(i,s)\] for starts outside \(C_0\), by Fatou’s lemma. In particular the entrance time is almost surely finite.

From \(C_0\) there are an integer \(m\) and a probability \(p>0\) such that regeneration is reached within \(m\) steps with probability at least \(p\), uniformly in the starting state. To see this, whenever \(s>3\) choose the next state in the interval of width \(1/4\) immediately above its support minimum; this lowers the state by at least \(3/4\). An even state with \(s\le3\) then draws into the regenerating odd range on the same choice. All prescribed intervals lie in a fixed compact and have uniformly positive transition probabilities.

Run such an \(m\)-step attempt, and on failure wait for the next entrance to \(C_0\) before retrying. Let \(D\) be the duration of one failed attempt together with this return. The stopped estimate and the uniform bound on the \(V\)-moment after the \(m\) attempted steps show that, for some \(\alpha_1>1\), \[\sup_{(i,s)\in C_0}\mathbb E_{i,s} [\alpha_1^D\mathbf 1_{\{\text{failure}\}}]<\infty.\] For \(0<\theta<1\), Hölder’s inequality bounds the same expression with \(\alpha_1^\theta\) by \[\left(\sup_{C_0}\mathbb E[ \alpha_1^D\mathbf 1_{\{\text{failure}\}}]\right)^\theta (1-p)^{1-\theta}.\] For sufficiently small \(\theta>0\) this is less than \(1\). Summing over successive failed attempts proves an exponential moment for the hitting time of regeneration from \(C_0\), and then from (36). The same reasoning applies to a return after a regenerating start: its outgoing common draw has a bounded \(V\)-moment.

The common outgoing law proves independence and identical distribution of the complete cycles. During a cycle all odd states are at least \(1\), and all even states are at least \(2\), so each \(g(s_j)\le\log2\). Thus the exponential moment of \(\tau\) supplies an exponential moment of \(G\) for a sufficiently small parameter. The terminal odd state lies in \([1,3]\), so its last decrement alone is at least \(g(3)>0\).

For nonarithmeticity, consider a two-step return whose even state \(t\) lies in a fixed subinterval of \((2,3)\) and whose next odd state \(u\) lies strictly between \(t-1\) and \(3\). There is a two-dimensional region of such pairs on which the joint density is positive. On that region \(G=g(t)+g(u)\) varies continuously and has a nonzero derivative in \(u\). Its distribution therefore has a nonzero absolutely continuous component, and cannot be supported on an arithmetic lattice. ◻

Proof. For a new even state \(t\ge2\), cancellation of the old derivative weight in the incoming integral gives \[\int_1^{t+1}(1-s^{-2})\,ds=\frac{t^2}{t+1}.\] Multiplication by \(W_0(t)\phi_\mathrm e(t)\) yields \(\pi_\mathrm e(t)\). For a new odd state \(t\ge1\), the corresponding integral is \(\int_2^{t+1}ds=t-1\), which yields \((1-t^{-2})\phi_\mathrm o(t)\). These identities prove invariance. Finiteness follows from (29). On \([1,3]\), \(\phi_\mathrm o=A\), so \(\beta=A[s+s^{-1}]_1^3=4A/3\).

For completeness, normalize the raw measure to a stationary probability measure \(\mu=\pi/M\), where \(M=\sum_i\int\pi_i\). Start the chain with law \(\mu\). For a bounded measurable state function \(Q\), partition \(Q(i_n,s_n)\) according to the last regenerating time strictly before \(n\). If it is \(n-k\), \(1\le k\le n\), the common outgoing law shows that this term has expectation \[\mu(\text{regenerating states})\, \mathbb E[Q(i_k,s_k)\mathbf 1_{\{\tau\ge k\}}],\] where the expectation on the right starts just after a regeneration. The remaining event is that there was no regenerating time among \(0,\ldots,n-1\); its probability tends to zero by Lemma 9 and dominated convergence over \(\mu\). Stationarity and then \(n\to\infty\) give \[\mu(Q)=\frac{\beta}{M} \mathbb E\sum_{j=1}^{\tau}Q(i_j,s_j).\] This proves (38) for bounded nonnegative \(Q\), and truncation proves it in general. The argument does not require an aperiodic discrete-time chain; the alternating types cause no difficulty.

Since \(g(s)\le1/s\), (30) gives \[M_g\le \int_2^\infty a(s)\,ds+ 2\int_1^\infty c(s)\,ds+ \int_0^\infty a(s)\,ds.\] The future integrals at \(s=2\) give \(\int_1^\infty c=2\) and \(\int_1^\infty a=A-2\). As \(a=1\) on \([0,2]\), the three displayed contributions are \(A-3,\ 4,\ A-1\). Their sum is \(2A=4e^\gamma\). Strict positivity is immediate from the positive even density and \(g>0\). Taking \(Q(i,s)=g(s)\) in (38) identifies \(\mathbb EG\). ◻

Proof. First start immediately before the outgoing draw of a regeneration, and exclude that starting state from the sum. Write a complete cycle as \((i_j,s_j)_{1\le j\le\tau}\), and set \(S_j=\sum_{k=1}^j g(s_k)\) within the cycle. Its response to the test is \[ H_0(v)=\mathbb E\sum_{j=1}^{\tau}F_{i_j}(v-S_j,s_j). \tag{41}\] If the log-gap support of the test is contained in \([a,b]\), then \(H_0(v)=0\) for \(v<a\), since \(S_j\ge0\). Also \(S_j\le j\log2\), so for \(v>b\), \[|H_0(v)|\le \|F\|_\infty \mathbb E\!\left[\tau\, \mathbf 1_{\{\tau\ge(v-b)/\log2\}}\right].\] The exponential moment in Lemma 9 gives an exponentially decreasing upper bound as \(v\to\infty\).

The function \(H_0\) is continuous, including for the permitted indicator tests. To verify this, condition on the history before the \(j\)-th draw and on the event \(j\le\tau\), which is determined before that draw. The next state \(t=s_j\) has a density. Writing \(D=e^{v-S_{j-1}}>0\), its gap is \[e^{v-S_j}=\frac{Dt}{t+1}.\] Equality at a fixed positive gap edge therefore specifies at most one value of \(t\); equality at a fixed state edge does likewise. For the arrival boundary, \[t=e^{v-S_j}/\ell \quad\Longleftrightarrow\quad t+1=D/\ell.\] Thus each boundary has conditional probability zero. For any fixed number of cycle steps dominated convergence gives continuity. The remaining steps are uniformly bounded in expectation by \(\|F\|_\infty\mathbb E[\tau\mathbf 1_{\{\tau>N\}}]\), which tends to zero. This proves continuity of \(H_0\). Continuity, the vanishing left tail, and the exponential right envelope show that \(H_0\) is directly Riemann integrable.

Let \(U_G\) be the renewal measure of successive complete-cycle decrements, including the boundary at zero: \[U_G=\sum_{k\ge0}\mathcal L(G_1+\cdots+G_k).\] The expectation of the complete future test from a regeneration is \[ R_F(v)=\int_{[0,\infty)}H_0(v-y)\,U_G(dy). \tag{42}\] By Lemma 9, \(G\) is nonarithmetic and has finite positive mean. The key renewal theorem (8) therefore gives \[R_F(v)\longrightarrow \frac1{\mathbb EG}\int_\mathbb RH_0(u)\,du.\] Fubini is justified by the bounded test, its compact log-gap support, and \(\mathbb E\tau<\infty\). Translating the log-gap integral within each cycle and applying (38) gives \[\int_\mathbb RH_0(u)\,du =\mathbb E\sum_{j=1}^{\tau}\int_\mathbb RF_{i_j}(u,s_j)\,du =\frac1\beta\sum_i\int\!\!\int F_i(u,s)\pi_i(s)\,ds\,du.\] Since \(\mathbb EG=M_g/\beta\), this is the limit in (40).

We record a boundedness fact needed to restore the initial segment. Every complete cycle has decrement at least \(g(3)>0\). Consequently any interval of fixed length contains a bounded number of cycle boundaries on each sample path, and \[ \sup_{y\in\mathbb R}U_G([y,y+h])\le 1+\left\lfloor\frac{h}{g(3)}\right\rfloor \qquad(h>0). \tag{43}\] The compact bound and the exponential envelope for \(H_0\), summed over unit intervals, show from (42) that \(\sup_v|R_F(v)|<\infty\).

Now let \(\tau_0\) be the first regenerating time from an allowed even start, and \(D_0=T_{\tau_0}\). All initial per-step decrements are bounded by \(c_*=\log(1+1/0.98)\). Lemma 9 gives a uniform exponential moment for \(\tau_0\), hence a uniformly tight, indeed exponentially bounded, family of \(D_0\)’s. The portion of the test through time \(\tau_0\) tends to zero uniformly as \(v\to\infty\): a contribution requires \(c_*\tau_0\ge v-b\), and its absolute size is at most \(\|F\|_\infty(\tau_0+1)\). Conditional on the initial history, the future after that state has expectation \(R_F(v-D_0)\). It is the same function \(R_F\) for every history, because the outgoing regenerating law is common. For a fixed \(M\), convergence of \(R_F(y)\) as \(y\to\infty\) is uniform over \(y=v-d,\ 0\le d\le M\). Uniform tightness of \(D_0\) and boundedness of \(R_F\) then give the claimed uniform limit. ◻

Proof. For a regenerating start, condition on the internal states and decrements of one fresh cycle. Its beginning is a renewal boundary independent of that cycle. Tonelli’s theorem gives \[\mathbb E\sum_{n\ge1}Q(i_n,s_n)\mathbf 1_{\{T_n\in[v,v+h]\}} = \mathbb E\sum_{j=1}^{\tau}Q(i_j,s_j) U_G([v-S_j,v+h-S_j]).\] Apply (43) and then (38). This argument permits arbitrary nonnegative \(Q\): it never assumes independence of a state’s value and its internal decrement.

We next compare the initial even start to regeneration. If its ratio is \(s_0\), the density after two draws, on \(t\ge2\), is \[ p_{s_0,2}(t)= \frac{W_0(t)\phi_\mathrm e(t)}{\phi_\mathrm e(s_0)} \int_{s_0-1}^{t+1}W_0(u)\,du. \tag{46}\] Starting at regeneration, the density after three draws is \[ p_{{\rm reg},3}(t)= \frac{W_0(t)\phi_\mathrm e(t)}A \int_1^{t+1}W_0(u) \int_2^{u+1}W_0(y)\,dy\,du \qquad(t\ge2). \tag{47}\] These formulas follow by canceling the intermediate derivative weights in the successive kernels. For \(u\ge2\), the inner integral in (47) is at least \(\int_2^3W_0(y)\,dy>0\). Since \(t+1\ge3\), it follows that \[\int_1^{t+1}W_0(u)\int_2^{u+1}W_0(y)\,dy\,du \gg \int_2^{t+1}W_0(u)\,du \gg \int_{s_0-1}^{t+1}W_0(u)\,du,\] uniformly for \(s_0\in[1.99,2.3]\). The last comparison uses the bounded integral over \([0.99,2]\) and the positive lower bound for \(\int_2^{t+1}W_0\). The starting denominator \(\phi_\mathrm e(s_0)\) also has a positive compact lower bound. Thus \[ p_{s_0,2}(t)\le C p_{{\rm reg},3}(t)\qquad(t\ge2). \tag{48}\]

To use this marginal comparison, the correlated elapsed decrement must be removed explicitly. Let \(I=[v,v+h]\), \(C_2=2c_*\), and \(C_3=3\log2\). The initial two decrements sum to at most \(C_2\), so an event in \(I\) at time \(n\ge2\) has, measured from state \(2\), a future decrement in \[I_2=[v-C_2,v+h].\] Condition on that state, discard the initial decrement by this enlargement, and apply (48). For a path started at regeneration, its first three decrements sum to at most \(C_3\); a future decrement in \(I_2\) measured from state \(3\) therefore gives a total decrement in \[[v-C_2,v+h+C_3].\] The resulting expectation is bounded by a constant times the regenerating occupation sum in this enlarged band, which is covered by (44). This proves the bound from even starts, including their state at time \(2\), without imposing independence on the initial state and elapsed decrement.

At step \(1\), the density is \[\frac{W_0(s)\phi_\mathrm o(s)}{\phi_\mathrm e(s_0)} \mathbf 1_{\{s\ge s_0-1\}}.\] Both \(W_0(s)\) for \(s\ge0.99\) and \(1/\phi_\mathrm e(s_0)\) on the allowed starts are bounded. This proves the asserted first-step estimate.

The condition \(R\le r_n\le eR\) is a band of length \(1\) in \(T_n\). For \(n\ge2\), use the preceding result with \[Q(i,s)=\frac{\mathbf 1_{\{s<eR/\ell\}}}{\phi_i(s)}.\] The ratios of invariant to derivative densities are \(1\) for the even states and \(1-s^{-2}\le1\) for the odd states. Their integrals up to \(eR/\ell\) are \(O(R+1)\). The first-step density gives the same bound by direct integration. Finally \(\phi_\mathrm e(s_0)\) has a positive compact lower bound, so the starting state’s possible contribution is \(O(1)\). ◻

Proof. Mark a complete regeneration cycle if its first draw lies in \([2.09,2.13]\). The common outgoing kernel gives a fixed probability \[p=\frac1A\int_{2.09}^{2.13}W_0(t)\phi_\mathrm e(t)\,dt \in(0,1).\] The complete cycle objects, consisting of their state sequences and their decrements, are iid. Consequently the spacings \(W\) between successive marked cycle beginnings are iid: each consists of one cycle conditioned on being marked, followed by a geometric number of cycles conditioned on being unmarked. More explicitly, the number \(N\) of intervening unmarked cycles has \(\mathbb P(N=m)=(1-p)^m p\), \(m\ge0\); conditional on these marks, the cycle objects are independent with their respective conditional laws. The next marked cycle is excluded from the preceding spacing and begins the next such block. This proves independence of the spacings, even though a mark depends on its own cycle. It also gives \[\mathbb EW= \mathbb E(G\mid\text{marked}) +\frac{1-p}{p}\mathbb E(G\mid\text{unmarked}) =\frac{\mathbb EG}{p}<\infty.\] Furthermore \(W\ge g(3)>0\).

From an allowed initial start, the delay \(D\) to the first marked beginning consists of the initial segment to regeneration and a geometric number of unmarked complete cycles. The first segment has uniformly bounded mean by Lemma 9; the latter sum has finite mean by the preceding conditional-cycle description. Thus \(D\) is uniformly tight over the allowed initial states. The spacings after that beginning are independent of the delay.

We give the required wide-interval bound using only \(\mathbb EW<\infty\). Let \(U_W\) be the renewal measure for the marked spacings, with an initial renewal at zero. The lower bound on \(W\) gives a uniform bound \(C\) for its mass in any interval of length one. For \(q\ge0\), if there is no marked renewal in \([q,q+H]\), some renewal at or before \(q\) has its next spacing overshoot \(q+H\). Independence of a renewal time and its next spacing therefore gives \[\mathbb P(\text{no renewal in }[q,q+H]) \le\int_{[0,q]}\mathbb P(W>q+H-t)\,U_W(dt) \le C\sum_{j\ge0}\mathbb P(W>H+j).\] Changing one endpoint in the unit-interval partition only changes the harmless absolute constant or shifts \(H\) by \(1\). The last quantity tends to zero as \(H\to\infty\), since \(W\) has finite mean. It is uniform in \(q\). For the delayed process, condition on \(D\le v\) and apply the same bound with \(q=v-D\). The additional error \(\mathbb P(D>v)\) tends uniformly to zero as \(v\to\infty\).

Apply this with \[v=\log(r_{\rm in}/b_1),\qquad H=\log\bigl(b_1/(10b_0)\bigr).\] Choose \(H\) sufficiently large in terms of \(\varepsilon\), equivalently choose \(b_1/b_0\) sufficiently large, and then let \(r_{\rm in}\to\infty\). A marked beginning in this log-decrement interval has pre-draw gap \(r\in[10b_0,b_1]\). For its marked draw \(t\in[2.09,2.13]\), \[\frac{10b_0}{3.13}\le x=\frac r{t+1} \le\frac{b_1}{3.09}.\] This lies inside \([2b_0,b_1/2]\), and the arriving ratio is \(t\). The new gap satisfies \[r'=\frac{rt}{t+1}\ge 10b_0\frac{2.09}{3.09}>6b_0.\] Gaps strictly decrease along the path, so the last assertion follows. ◻

Proof. The absolute next deviation in (63) is nondecreasing as a function of \(x\). Thus partial summation on an exponent interval with lower endpoint \(u\geq2\) bounds the error in replacing \[\sum\frac1p\frac{g_{i'}(r/x(p)-1)}{x(p)} \quad\hbox{by}\quad \int\frac{g_{i'}(r/x-1)}{x^2}\,dx\] by \(O(E(u)D/u)\), where \(D\) is the maximum absolute next deviation on that interval. To justify the variation bound despite the additional factor \(1/x\), use the product-variation inequality: the total variation is at most a constant times \(D/u\). By (62), replacing the products introduces endpoint errors of the same kind and a sum error at most \(O((\log B)E(u)D)\). These estimates apply to subintervals as well, and their continuous contributions cancel by (64).

At a state of ratio \(s\), all the absolute parent, boundary, and next deviations under discussion are \(O(\phi_i(s))\). For example, \[a(s)\leq\phi_\mathrm e(s)/s,\qquad c(s-1)\leq\phi_\mathrm e(s)/s,\] and the analogous inequalities follow from \(\phi_\mathrm o(s)=s(c(s)+a(s-1))\) on its normal range. Monotonicity bounds the later arguments by these earliest ones. The bounded extensions at the initial states obey the same inequalities with an absolute constant. An omitted lower deviation is just \(1\) in absolute value, which occurs where the relevant upper derivative weight is bounded away from zero.

First restrict to histories with all ratios at most \(S=(\log B)^2\). If \(b\leq(\log B)^4\), then \(r\leq(\log B)^6\), and the preceding partial summation bounds imply, for some fixed \(C\), \[ \frac{r^2|R_i^{(w)}(r,b)|}{\phi_i(s)} \ll(\log B)^C E(2). \tag{66}\] This is smaller than every negative power of \(\log B\).

If \(b>(\log B)^4\), split the exponent interval at \(\sqrt b\). Above this point \(E(\sqrt b)\) is smaller than every \(B^{-A}\): indeed \(\sqrt{\sqrt b\log w}\gg(\log B)^{3/2}\). Below it every relevant next ratio is at least \(s\sqrt b-1\), and the boundary ratio is at least \(s\sqrt b\). The Dickman bounds from Lemma 8, together with the backward-ratio bounds there, show that these deviations divided by \(\phi_i(s)\) are smaller than every \(B^{-A}\), uniformly for \(s\leq S\). One can see the uniformity by comparing the arguments to \(s\): their separation is at least a constant times \((\log B)^2\), while the derivative weights have exponentially decreasing ratios beyond any fixed compact set. Any fixed polynomial losses are absorbed. Since \(r=O(B)\) along a path, the same assertion holds after multiplication by \(r^2\).

Apply (53) and sum over at most \(N=O((\log B)^3)\) steps. The starting factor \(\phi_\mathrm e(s_{\mathrm{st}})/r_{\mathrm{st}}^2\) is \(O(B^{-2})\), and (66) and its large-cutoff counterpart show that the low-state contribution to (65) is \(o(B^{-2})\).

It remains to bound histories having a ratio above \(S\). The crude bound for every residual is \(O(\log B)\), since all deviations in its definition are bounded and the total harmonic prime sum is \(O(\log B)\). We claim the sharper bound \[ |R_i^{(w)}(r,b)|=O_A(B^{-A})\qquad(r\geq S/2) \tag{67}\] without a ratio restriction. In the preceding error estimates split instead at \(Q=(\log B)\sqrt{\log\log B}\). For \(x\geq Q\), the PNT saving has exponent at least a constant times \((\log B)(\log\log B)^{1/4}\), and hence beats every \(B^{-A}\). For \(x\leq Q\), each relevant argument \(r/x\) or \(r/x-1\) is at least a constant times \(\log B/\sqrt{\log\log B}\). The Dickman bound \(\rho(v)\leq\exp(-v\log v+O(v))\) makes its deviation smaller than every \(B^{-A}\). The endpoint errors fall into the same alternatives. This proves (67).

The total prefix weight is \(O(B)\), so (67) deals with the high-history prefixes whose terminal gaps are at least \(S/2\). A high ancestor on the \(x>2\) tree has gap greater than \(2S\). Any remaining prefix with terminal gap below \(S/2\) has reduced that ancestor’s gap by more than half. The factorial-tail argument in Lemma 16, multiplied by the crude \(O(\log B)\) residual bound, deals with those prefixes. This completes the proof. ◻

Proof. On a fixed compact gap interval the admitted polynomial has bounded length, because every exponent exceeds \(1\). For each such length, Lemma 15 gives convergence of the ordered prime sum to its harmonic integral. Ties, moving upper endpoints, and admission equalities are confined to sets of continuous measure zero. The same argument works along any convergent sequence of gap parameters. The continuous integrals depend continuously on those parameters by dominated convergence, so compactness yields uniform convergence. Also \(V(2)\to1/2\) by (62).

For decay, compare the cutoff polynomial with the full product \(V(2)\). At a first omitted lower leaf after \(m\) boundary exponents, all of which are at most \(2\), the failure of admission requires \(m>(r-4)/2\). The total discrepancy is bounded by the sum of the weights of such first omissions times their exact subsequent survivor product, which is at most \(1\). Thus it is bounded by \[\sum_{m>(r-4)/2}\frac{T_2^m}{m!},\qquad T_2=\sum_{w<p\leq w^2}\frac1p=\log2+o(1).\] This is \(O(\exp(-c r\log(r+2)))\). The continuous full product is \(\exp(-\int_1^2 dx/x)=1/2\), and its first-omission decomposition has the same bound. Finally the benchmark deviations \(a(r/2)\) and \(c(r/2)\) have the required decay by Lemma 7. Combining these comparisons proves (70). ◻

Proof. The parameter definitions imply \[r_0=2B-a_\star+2-\frac{2\log L}{\log w}+o(1) =2B-a_\star+o(1).\] Since \(f'_{\mathrm{ext}}(2)=e^\gamma\), (62) gives \[\frac{B^2V(B)f_{\mathrm{ext}}(r_0/B)}{e^\gamma} \longrightarrow-a_\star.\] Equations (71), [eq:ref-correction-limit], and (72) give the limit in (78). Finally \(M_g\leq4e^\gamma\) by (39). The elementary bound \(\gamma\leq\sum_{j=1}^6j^{-1}-\log6<0.66\) implies \(e^\gamma<1.95\). Together with \(a_\star=0.01\) and (77), this yields \[-a_\star+\frac{2I}{M_g} >-0.01+\frac{0.28}{4(1.95)}>0.02.\] The eventual positive constant \(c_L\) follows. ◻

Proof. In the continuous model the benchmark is \(f(r/b)/b\) and the quadrature residual is identically zero by (64). Its correction is the sum of the boundary anomalies \(\delta_i\) along the standard paths above \(2\), with parity signs. The continuous version of (34) supplies the starting factor \(\phi_\mathrm e(r/b)/r^2\ll b^{-2}\), uniformly for \(r/b\in[2,2.22]\). The expected sum of the absolute remaining reward \(R^2|\delta_i(R)|/\phi_i(s)\) is bounded uniformly in the start. To verify this, use bounded compact-gap visits on a fixed compact range and, outside it, sum the unit logarithmic gap bands from Lemma 12. After canceling \(\phi_i\), a band \(R\leq r'\leq eR\) costs at most a fixed polynomial in \(R\) times \(\exp(-cR\log(R+2))\), by (70); the resulting series converges. The empty prefix and the explicitly bounded first step satisfy the same estimate. This proves (79).

For fixed \(b\in[b_0,b_1]\) and the indicated ratios, the starting gap is bounded and the ordered reference polynomial has uniformly bounded length. Lemma 15 therefore gives uniform convergence of the discrete polynomial to \(Q_\mathrm e\): along any convergent parameter sequence, tie, cutoff, and admission boundaries have continuous measure zero, and dominated convergence applies to each bounded-length integral. Compactness makes this uniform on the whole window. Endpoint inclusion or exclusion makes no difference to the limit. Finally (62) gives \(V(b)\to1/b\) uniformly there. Divide the continuous estimate by \(1/b\), and transfer it to the primes, to obtain (80). ◻

Proof. Choose \(K_*\) so that Lemma 5 gives \(|N_e/\mu_e-1|<\varepsilon/2\) whenever \(\log_w J_e\ge K_*\). Along the given branch the numbers \(v_j\) decrease strictly, by more than one at each step. Let \(i\) be the first index for which \(v_i<K_*\). This index exists because \(r_d\le K\), and it is not the first index: \(v_1\ge\log_wY-B\to\infty\).

Every nonroot included lower node of cutoff \(b\) has both \(r\ge2b\) and \(r\ge b+2\), by (13). Its odd child of exponent \(x\le b\) consequently has \(r_{\rm child}\ge x\) and \(r_{\rm child}\ge2\). An included even child has \(r_{\rm child}\ge \mathcal H(x)\ge2x\). Thus at the crossing index \(i\), regardless of its parity, \[x_i\le r_i=v_i+2-a_\star<K_*+2, \qquad v_{i-1}=v_i+x_i<2K_*+2.\] All included nodes have \(v_j\ge a_\star\). It follows that there are fewer than \(H_e\) edges from the crossing parent to \(d\), and each of them has parent \(v\le2K_*+3\), exponent at most \(2K_*+3\), and child \(v\ge a_\star\).

Put \(e_e=N_e/\mu_e-1\). For each edge of prime \(u\), \[e_{d'u}-e_{d'} =\frac{N_{d'u}-N_{d'}/u}{\mu_{d'}/u}.\] The error at the crossing parent has absolute value less than \(\varepsilon/2\), whereas the final error has absolute value greater than \(\varepsilon\). Telescoping and the triangle inequality show that one of the fewer than \(H_e\) differences has absolute value greater than \(\varepsilon/(2H_e)>\delta\). ◻

Proof. We first establish the exclusions leading to (88). The compact-history estimate in Proposition 19 permits each geometric exception to be estimated in the tilted prime chain, at a cost at most \(C_KB^{-2}\) times its occurrence probability. Histories with a ratio exceeding \(S_*=(\log B)^2\) cost \(O_A(B^{-A})\) in the original measure, by Lemma 16. On the remaining histories, Proposition 17 compares the prime chain with the continuous chain up to \[N_*=O((\log B)^3)\] steps. Its failure probability tends to zero, and its matched states satisfy \(|s-\widetilde s|\le h_0\) and \(|\log(r/\widetilde r)|\ll N_*h_0\), with \(h_0\) smaller than every fixed negative power of \(\log B\). These errors remain negligible in all polynomially many opportunities below. We work with the continuous comparison where useful, retaining the indicated slack when returning to prime paths.

Proof. The single-point survival probability is \(V_0\). For a nonzero spacing \(h\), the pair probability divided by \(V_0^2\) equals \[ 2\mathbf 1_{2\mid h} \prod_{2<t\le w}\left(1-\frac1{(t-1)^2}\right) \prod_{\substack{2<t\le w\\t\mid h}} \left(1+\frac1{t-2}\right). \tag{142}\] At \(t\mid h\) the two positions have one forbidden residue between them; at \(t\nmid h\) they have two. This proves the formula, including the parity factor.

Expand the last product in (142) over odd squarefree \(l\), with coefficients \[\lambda_l=\prod_{t\mid l}\frac1{t-2}.\] For each fixed \(l\), the triangular average of \(2\mathbf 1_{2l\mid h}\) is \[\sum_{1\le h<J}\frac{2(J-h)}{J^2}\,2\mathbf 1_{2l\mid h} \longrightarrow\frac1l.\] The same average is \(O(1/l)\) for every \(l,J\). Moreover, \[\sum_{\substack{l\ge1\\l\ {\rm odd\ and\ squarefree}}}\frac{\lambda_l}{l} =\prod_{t>2}\left(1+\frac1{t(t-2)}\right)<\infty.\] Dominated convergence applies even though the available primes increase with \(w\). The limiting triangular average of (142) is 1, because \[\prod_{t>2}\left(1-\frac1{(t-1)^2}\right) \prod_{t>2}\left(1+\frac1{t(t-2)}\right)=1.\] The convergence is uniform for \(J\ge w^\delta\): first truncate the convergent divisor series at fixed \(l\), and then use \(J\to\infty\) uniformly in this range. The diagonal contribution to \(\mathbb ES^2/(JV_0)^2\) is \(1/(JV_0)=o(1)\), by Mertens’ theorem. This proves the independent-model assertion.

For the stable version, sum the assumed pair upper bounds and the single-point bounds to obtain \[\int S^2\,d\mu\le (1+O(\zeta)+o(1))(JV_0)^2.\] Use also the lower bound for \(\int S\,d\mu\) and the upper bound for \(\mu(\Omega)\) in the identity \[\int(S-JV_0)^2\,d\mu =\int S^2\,d\mu-2JV_0\int S\,d\mu+(JV_0)^2\mu(\Omega).\] This gives the stated result without normalizing \(\mu\). ◻

Proof. It is enough to impose the aligned hit at every \(p\) hypothetically and bound (138). The primes dividing \(H\) may be discarded: there are \(O(1)\) of them in \(\mathcal P\), since \(H\le R\mathcal Z^{11}\), and their fraction tends to zero. For \(H\le R^{4/5}\), Brun–Titchmarsh controls each residue pattern after we fix \(m_0\): the possible primes lie in a progression of modulus \(HT_0T_1\). The condition that \(T\) is large then gives a long enough interval in \(m_0\) for its small-prime conditions to have the required first and second moments. For larger \(H\), we instead count integer pairs \((p,m_0)\) on a modular hyperbola and then sieve the \(p\)-coordinate. This gives domination by the uniform distribution on all small-prime patterns. In both ranges the target is a small exceptional fraction among all primes of the isolated bin.

Proof. Every actual included bad endpoint under consideration has a witness from the bounded candidate set, by [lem:edge-witness,prop:regular-boxes]. For each candidate, 29 costs at most a prescribed \(\sigma\) fraction of its full harmonic box and supplies a fixed list of at most \(F\) rationals. Both \(F\) and the list definition are independent of the choice of the isolated prime.

To apply 32, fix all the other prime choices and one rational on this list. Then \(H,C_0,T\) are fixed as \(p\) varies. If the structured-parent condition is possible in this slice, (131) holds throughout the fixed slice. When \(T>w^{C_s}\), the proposition bounds all bad aligning \(p\)’s, and hence also those that supply the particular witness. Since the isolated bin has multiplicity one, its prime choice is independent of all the other bin choices in full-box measure. The weights \(1/p\) vary by a bounded factor within this bin, uniformly for sufficiently small \(\xi\). Therefore the count bound \(\sigma_2n_p\) converts to at most \(C\sigma_2\) of its harmonic measure, with fixed \(C\).

Union over the list and over the at most \(H_e\) candidates bounds the discarded fraction of each full box by \[H_e(\sigma+CF\sigma_2).\] The total enlarged-box mass is at most \(C'_K B^{-2}\), where \(C'_K\) is independent of sufficiently small \(\xi\), by 26. First choose \(\sigma\) sufficiently small; this fixes \(F\). Then choose \(\sigma_2\) sufficiently small in terms of \(F\) and \(\rho\), and finally choose \(C_s\) from 32. This makes the discarded mass at most \(\rho B^{-2}\), without multiplying by the number of boxes. For every remaining bad endpoint, some structured rational has \(T\le w^{C_s}\), which is (153).

The bound on \(H\) controls the nonaligned factors. Each nonaligned prime factor of \(q_f\) divides \(q_{f,E}\le w^{C_s}\), so it is at most \(w^{C_s}\). The isolated prime already aligns by the structured-parent conclusion; its exponent tends to infinity, and in particular exceeds \(C_s\). This proves the alignment assertion. The bound on \(|C_0|/R\) controls the numerator of the rational on a scale common to all boxes. We have \(b\le q_f\), \(q_{f,A}\le q_f\), \(R\le p\), and \(pq_f=d\le Y\), since these are included endpoints with \(J_d>1\). Consequently, \[|A|\le Dq_f+|C_0|q_{f,A} \le w^{C_s}q_f(1+R) \le 2Yw^{C_s}.\] This implies the second inequality of (154) for large \(z\); the first follows directly from (153). ◻

Proof. For \(t\in E\), let \(V_t\) be independent nonnegative integer-valued random variables with probabilities \[\mathbb P(V_t=0)=\frac{t-2}{t-1},\qquad \mathbb P(V_t=j)=t^{-j}\quad(j\ge1).\] These masses sum to one, and the probability that \(\prod_{t\in E}t^{V_t}=d_0\) is exactly \(W_E(d_0)/d_0\). This interpretation includes \(t=2\): the mass at zero is then zero and \(\sum_{j\ge1}2^{-j}=1\). In particular the zero factors in (163) cause no exception to the probability interpretation.

Let \(U_t\) instead have the ordinary geometric probabilities \(\mathbb P(U_t=j)=(1-1/t)t^{-j}\) for \(j\ge0\). For \(j\ge1\), \[\mathbb P(V_t\ge j)=\frac{t^{1-j}}{t-1} \ge t^{-j}=\mathbb P(U_t\ge j).\] Couple \(U_t,V_t\) monotonically, independently over \(t\). Their mean difference is \[\mathbb E(V_t-U_t) =\frac{t}{(t-1)^2}-\frac1{t-1} =\frac1{(t-1)^2}.\] It follows that the excess log-product \(Z_E=\sum_{t\in E}(V_t-U_t)\log t\) has uniformly bounded mean, since \(\sum_t\log t/(t-1)^2<\infty\). Extend the independent ordinary variables to all primes \(t<P\). Then \[\prod_{t\in E}t^{U_t}\le\prod_{t<P}t^{U_t}.\] The latter product has mass \(V_{\rm all}(P)/n\) at every integer \(n\) composed of primes below \(P\). Every \(n\le P^{.94}\) has this property, so \[\mathbb P\left(\prod_{t<P}t^{U_t}\le P^{.94}\right) =V_{\rm all}(P)\sum_{n\le P^{.94}}\frac1n =e^{-\gamma}(.94+o(1)).\] By Markov’s inequality, \(\mathbb P(Z_E>.01\log P)=O(1/\log P)\), uniformly in \(E\). Outside this exception the preceding event implies \(\prod_{t\in E}t^{V_t}\le P^{.95}\). Subtracting the exceptional probability proves (164); no independence between these last two events is required. ◻

Proof of 36. Every prime in the search bin eventually exceeds both \(D\) and \(P\). The alignment of the prime factors of \(q'\) implies \((D,q')=1\); hence \((D,pq')=1\) for every \(p\in\mathcal P\). The hypothetical hit condition and integrality of \(n\) are therefore equivalent to \[ Dn-A=pq'm, \qquad 1\le\frac{A+pq'm}{D}\le Y, \qquad pq'm\equiv-A\pmod D. \tag{165}\] We count a subfamily of these integers in which \(m\) has one prime factor exceeding \(P\). Averaging over \(p\) then imposes the remaining avoidance conditions.

Proof. We first explain exactly which prime is averaged. Partition the stopped nodes by their ordered bin labels, their tag position, and all prime choices other than the tag prime \(p\). In a nonempty group, let \(A/D\) be the owner of its tag bin. Then \(p\) ranges over the entire subset of that bin aligning to \(A/D\).

To justify this assertion, replace \(p\) by any other aligning prime in the bin. All earlier choices remain fixed, so no earlier tag appears. At the designated position the new prime aligns to the same owner; hence the tag position and tag rational remain unchanged. Every subsequent all-prefix alignment test has the same truth value, since the other primes are fixed and the replacement aligns. The representative tests, lengths, and bin multiplicities depend only on the labels. Admission is preserved by (157), and the tag-bin multiplicity one prevents a change in prime ordering or a collision with another factor. These observations apply to each earlier prefix as well, so no earlier stop is introduced. This proves the assertion about the entire aligning subset.

In this group put \(q'=d/p\). The last prime \(P\) is a factor of \(q'\) and is fixed. All primes of \(q'\) are at least \(P\), and they align to \(A/D\). First allow all primes \(p\) in the tag bin, assigning to \(p\) the hypothetical hit class aligned to \(A/D\). These hypothetical choices need not be actual stops; their local counts are auxiliary. Let \(\mathcal P\) denote this tag bin, and use the hypothetical counts \(T_p\) of 36. On its aligning subset, \(T_p=S_{pq'}(x(P))\).

For all choices of \(p\) in the tag bin, put \(b=x(P)\) and use the gap \(r_{pq'}=\log_w(Y/(pq'))-a_\star+2\). Thus \[\log_PJ_p=\frac{r_{pq'}}b+\frac{a_\star-2}{b}.\] The bin labels and representative safety tests are fixed, so the movement bound applies also to these hypothetical choices. By (159), after enlarging \(b_0\) if necessary, all of them satisfy (160). The search bin is disjoint from the prime factors of \(q'\) because the tag bin has multiplicity one. All hypotheses of 36 therefore hold.

For sufficiently large \(z\), the actual cutoff lies in the fixed interval \([b_0-1,b_1]\). Applying 24 on this interval, together with the product identity \(V_{\rm all}(P)=V_0V(b)\), gives \[\frac{\mu_{pq'}P_\mathrm e(r_{pq'},b)}{J_pV_{\rm all}(P)} \le f(r_{pq'}/b)+O(1/b)+o(1).\] The constants are uniform for the fixed enlarged window \([b_0-1,b_1]\) and for the ratio window in (159). On that ratio window, the near-\(2\) formula and monotonicity of \(f\) give \[f(r_{pq'}/b)\le f(2.18) <\frac{2(1.95)(.166)}{2.18}<.30.\] Here \(e^\gamma<1.95\) follows, for example, from \(\gamma\le\sum_{j=1}^6j^{-1}-\log6<.66\), and \(\log(1.18)<.166\) follows from \(\log(1+u)\le u-u^2/2+u^3/3\) at \(u=.18\). Thus first choosing \(b_0\) large and subsequently taking \(z\) large gives \[ \mu_{pq'}P_\mathrm e(r_{pq'},b)\le .33 J_pV_{\rm all}(P) \tag{174}\] uniformly over the group and over its hypothetical choices.

Apply (161) to the full tag bin. Let \(\mathcal G\) be the aligning subset in the tag bin. Its complement contains at most an \(\eta\) fraction of the bin primes. Since the \(J_p\)’s vary by at most \(1+\xi\) within the whole bin, for \(\xi\le1\) we have \[\sum_{p\notin\mathcal G}T_p \le 2C_U\eta V_{\rm all}(P) \sum_{p\ \mathrm{in\ bin}}J_p.\] Fix an absolute \(\eta_0<1/2\) so small that \(2C_U\eta_0<.05\). For \(0<\eta\le\eta_0\), subtracting this bound from (161) and using (174) gives \[\begin{split} \sum_{p\in\mathcal G}S_{pq'}(x(P)) &=\sum_{p\in\mathcal G}T_p\\ &\ge .34V_{\rm all}(P)\sum_{p\ \mathrm{in\ bin}}J_p\\ &\ge\sum_{p\in\mathcal G}\mu_{pq'}P_\mathrm e(r_{pq'},b). \end{split}\] The last inequality uses \(.34>.33\) and positivity of \(J_p\); it does not require a distribution hypothesis for the survivors inside the owner subset. Every stopped node belongs to exactly one of the groups considered. Summing the group inequalities proves 38. ◻

Proof. For a hard endpoint, 33 gives a rational on one of its candidate lists that satisfies (155) and aligns to every path factor of exponent greater than \(C_s\). We need two facts about this path: its tag must be this rational, and it must have an earlier even visit in the stop window. We establish the tag statement in the full-box product measure, and the visit statement in the unconditioned path process. Their exceptional masses will then be added.

Proof of Theorem 2. By Proposition 22, there is an absolute \(c_L>0\) such that \[ P_\mathrm e(r_0,B)\ge\frac{c_L}{B^2} \tag{177}\] for all sufficiently large \(z\). Let \(C_{\rm abs}\) be an absolute constant such that \[\left|N_d/\mu_d-1\right|\le C_{\rm abs}\] at every included node; this follows from (14).

For nodes with large gap, the relative error in (14) is \(O(e^{-cr_d})\) after a fixed lower threshold on \(r_d\). The tail estimate in Proposition 19 permits us to choose a fixed \(K\) so large that \[ \sum_{\substack{d\text{ included}\\r_d>K}} |N_d-\mu_d| \le\frac{c_L}{8}\frac{YV_0}{B^2} \tag{178}\] eventually. Standard paths contain the included paths, so the nonnegative tail estimate applies. This choice depends only on the fixed reference margin and the absolute small-prime error constants.

The same proposition gives a constant \(C_K\) for the total harmonic mass of nodes with \(r_d\le K\). Choose \(\varepsilon>0\) such that \(\varepsilon C_K<c_L/8\). The compact nodes with relative error at most \(\varepsilon\) then contribute at most \[ \sum_{\substack{d\text{ included}\\r_d\le K\\ |N_d/\mu_d-1|\le\varepsilon}} |N_d-\mu_d| \le\frac{c_L}{8}\frac{YV_0}{B^2}. \tag{179}\]

It remains to deal with compact nodes having relative error greater than \(\varepsilon\). Fix a target \(\beta>0\) so small that \[ C_{\rm abs}\beta<\frac{c_L}{8}. \tag{180}\] We claim that the stopped tree can be chosen so that the retained bad compact nodes have total harmonic mass at most \(\beta/B^2\). The following choices give this claim without requiring any constant to be chosen again at an earlier stage.

First use Lemma 25 to fix a larger threshold \(K_*\), a positive edge-discrepancy threshold, and a fixed maximum number \(H_e\) of candidate positions. Choose the adjustable regularity exceptions in Proposition 26 small enough to cost less than a prescribed small fraction of \(\beta/B^2\). This fixes the path-length bound and the isolated-prime interval. For the moment leave the exception for near-threshold even prefixes to the eventual choice of bin width.

The enlarged regular boxes have total harmonic mass at most \(C'_K/B^2\), with \(C'_K\) independent of sufficiently small fixed \(\xi\). Choose the exception fraction \(\sigma\) in Proposition 29 sufficiently small that \[H_eC'_K\sigma\] is less than another prescribed small fraction of \(\beta\). The inverse proposition now fixes a positive alignment fraction and a list bound \(F\), independently of the eventual sufficiently small fixed width. Each list is attached to its entire candidate box.

Next choose the variance exception fraction in Proposition 32 small enough relative to \(H_e\), \(C'_K\), \(F\) and \(\beta\). A prime-count fraction in the isolated bin converts to a harmonic fraction at a bounded absolute cost. After this conversion and the finite unions over candidates and list elements, the total variance exception costs another prescribed small fraction of \(\beta/B^2\). The variance proposition fixes a constant \(C_s\). Corollary 33 then shows that all remaining bad compact endpoints have a hard rational satisfying the global eligibility bounds and alignment of every factor with exponent greater than \(C_s\).

Choose the absolute owner threshold \(\eta\) required by Proposition 38. Choose \(b_0\) sufficiently large in terms of \(C_s\) and \(K\) and for the local reference and prime estimates in that proposition. Finally choose \(b_1/b_0\) sufficiently large that Proposition 39 bounds the hard endpoints that remain outside stopped subtrees by the remaining allocated small fraction of \(\beta/B^2\). This uses the marked-visit estimate with a prescribed failure probability, as well as the vanishing owner and wrong-tag exceptions for the fixed candidate lists.

All constants except the bin width have now been fixed. Choose a fixed \(\xi>0\) sufficiently small for the interval-freezing errors, candidate-size slack, representative stopping margins and all earlier small-width requirements. In particular, the near-threshold exception, of cost \(O(\Delta)+o(1)\) in the compact-history probability measure with \(\Delta=2C_{\rm len}\xi\), can be made as small as the error budget requires. Then take \(z\) sufficiently large for every preceding fixed choice. Asymptotic bounds whose thresholds depend on \(\xi\) are used only at this final stage.

The sum of all these finitely many allocated costs is at most \(\beta/B^2\), proving the claim. More explicitly, after removing the regularity exceptions, every retained bad endpoint has a witnessing edge. Outside the inverse exceptions it has an alignment in the fixed list. Outside the variance exceptions it is hard. Outside the hard-stopping exceptions it lies in a stopped subtree and is therefore not retained. This exhausts the cases. Fractional exceptions are summed using \(H_eC'_K/B^2\), not the number of boxes.

The claim and (180) show that retained bad compact nodes contribute at most \((c_L/8)YV_0/B^2\) in absolute error. Together with (178) and (179), this gives \[ \sum_{d\in\mathcal T}|N_d-\mu_d| \le\frac{3c_L}{8}\frac{YV_0}{B^2} \tag{181}\] for the retained expanded nodes of the chosen stopped tree. Proposition 38 gives \[\sum_{d\in\mathcal S} \bigl(S_d(b_d)-\mu_dP_\mathrm e(r_d,b_d)\bigr)\ge0.\] Apply (17), Lemma 6 and (177). We obtain \[S_1(B)\ge\left(1-\frac38\right)c_L\frac{YV_0}{B^2} \ge\frac{c_L}{2}\frac{YV_0}{B^2}.\] Every constant is independent of the prescribed residue classes. This proves Theorem 2. ◻

Proof of Theorem 1. By Theorem 2 and Mertens’ formula, there is an absolute \(c_0>0\) such that, for every sufficiently large real \(z\), every assignment of one forbidden class at each prime \(p\le z\) leaves at least \[ c_0\frac{Y\log w}{L^2} \tag{182}\] integers in \([1,Y]\). Indeed, \(V_0/B^2\sim e^{-\gamma}\log w/L^2\).

Let \(k\) be sufficiently large, put \(\ell=\log k\) and \(M=\log\log k\), and take \[ z=A_0\frac{k\log k}{\log\log k}, \tag{183}\] where the absolute constant \(A_0>1\) will be fixed below, before \(k\) tends to infinity. With the parameters of (2), \[ L\sim\ell,\qquad \log w\sim M,\qquad Y\sim A_0^2\frac{k^2}{M^2},\qquad X:=\frac Yz\sim A_0\frac{k}{\ell M},\qquad \log X\sim\ell. \tag{184}\] In particular \(z\to\infty\) and \(X\to\infty\) for every such fixed \(A_0\).

Let \(n\) be any positive integer with \(\omega(n)\le k\), and let the given interval of \(Y\) consecutive integers begin at an arbitrary integer \(a\). Represent its integers as \(a+j-1\), \(1\le j\le Y\). For each prime \(p\mid n\) with \(p\le z\), prescribe the forbidden class \[j\equiv1-a\pmod p.\] At the other primes \(p\le z\), prescribe any class. The estimate (182) counts integers that avoid every divisor prime at most \(z\), together with these additional restrictions.

Fix a prime divisor \(q>z\) of \(n\). Its divisibility class has at most \(1+Y/q\le1+X\) representatives in the coordinate interval. Enclose them in a progression segment whose coordinate length is \(\lceil X\rceil+2\). Fix a sufficiently small absolute \(\theta>0\) and sieve this segment by primes at most \(X^\theta\). This cutoff is below \(z\) for large \(k\), the step \(q\) is invertible modulo every sieve prime, and the integers already counted in (182) avoid its prescribed class there. Lemma 5 and Mertens’ formula therefore give \[ \#\{\text{these survivors divisible by }q\} \le C_1\left(1+\frac X{\log X}\right) \tag{185}\] for an absolute \(C_1\), uniform in \(q\), \(A_0\), the classes, and the translation once the displayed length conditions hold. More explicitly, the enclosing coordinate length is comparable to \(X\) and at least \((X^\theta)^{1/(2\theta)}\) for large \(X\), so the fixed exponent upper bound in Lemma 5 applies. Enclosing a shorter or empty progression only increases the count; in particular the argument also covers \(q>Y\).

There are at most \(k\) such further divisor primes. For each fixed \(A_0\), (184) gives \[ \frac{k(1+X/\log X)}{Y\log w/L^2} =\frac1{A_0}+o(1). \tag{186}\] For the second term in the numerator, the quotient is \(kL^2/(z\log X\log w)\to1/A_0\); the term \(k\) is negligible since \(Y\log w/L^2\asymp_{A_0}k^2/(\ell^2M)\). Choose once and for all \(A_0>2C_1/c_0\). Equations (185) and (186) then show that fewer than the number in (182) are removed, for all sufficiently large \(k\). At least one integer in the original interval is therefore coprime to \(n\).

This argument is uniform in the prime divisors of \(n\) and in every integer \(a\), including negative starting points and intervals containing zero. Prime multiplicities do not enter. The length estimate in (184), with \(A_0\) now absolute, gives \[h(k)\ll\frac{k^2}{(\log\log k)^2} \ll\frac{k^2}{(\log\log(3k))^2}\] for all sufficiently large \(k\), since \(\log\log(3k)/\log\log k\to1\).

To include the remaining finitely many values of \(k\), suppose \(n\) has \(r\le k\) distinct prime divisors. Inclusion–exclusion gives at least \[m\prod_{p\mid n}\left(1-\frac1p\right)-2^r \ge\frac m{k+1}-2^k\] coprime integers in every interval of \(m\) consecutive integers. For the product bound, order the distinct primes as \(p_1<\cdots<p_r\) and use \(p_j\ge j+1\) to obtain \(\prod_{j=1}^r(1-1/p_j)\ge1/(r+1)\). This also covers \(r=0\) with the empty product equal to one. The integer \(m_k=(k+1)2^k+1\) consequently bounds \(h(k)\) for each remaining \(k\). The maximum of \[\frac{m_k(\log\log(3k))^2}{k^2}\] over this finite set, together with the constant already obtained for large \(k\), supplies one absolute constant \(C\) such that \(h(k)\le Ck^2/(\log\log(3k))^2\) for every integer \(k\ge1\). ◻

Proof. Successive integration on unit intervals constructs a unique positive continuous function, locally absolutely continuous and with bounded one-sided derivatives on each such interval. For \(u>2\) its equation gives, almost everywhere, \[ u\omega'(u)=\omega(u-1)-\omega(u) =-\int_{u-1}^{u}\omega'(v)\,dv. \tag{205}\] Put \(M_n=\mathop{\rm ess\,sup}_{n<u<n+1}|\omega'(u)|\). These quantities are finite by the construction, and \(M_1\le1\). For every integer \(n\ge2\), (205) implies \[M_n\le\frac1n\max(M_{n-1},M_n).\] If \(M_n>M_{n-1}\) this inequality forces \(M_n=0\), a contradiction; otherwise it gives \(M_n\le M_{n-1}/n\). Thus \(M_n\le1/n!\). In particular \(\omega'\) is integrable on \([1,\infty)\), so \(\omega\) is bounded and has a finite limit, say \(\ell\).

It remains to determine \(\ell\). For \(t>0\) define \[W(t)=\int_1^\infty\omega(u)e^{-tu}\,du.\] Boundedness justifies differentiation and integration by parts. The derivative of \(u\omega(u)\) is zero on \((1,2)\); integrating it on \([1,\infty)\), including the boundary value at \(1\), gives \[-e^{-t}-tW'(t) =\int_2^\infty\omega(u-1)e^{-tu}\,du =e^{-t}W(t).\] Since \(W(t)\to0\) as \(t\to\infty\), solving this differential equation yields \[ 1+W(t)=\exp\!\left(\int_t^\infty\frac{e^{-s}}s\,ds\right). \tag{206}\] The constant in this formula can be evaluated without a Tauberian argument. Integration by parts shows that \[\int_t^\infty\frac{e^{-s}}s\,ds+\log t =(1-e^{-t})\log t+\int_t^\infty e^{-s}\log s\,ds.\] Moreover, \[ \int_0^\infty e^{-s}\log s\,ds=-\gamma. \tag{207}\] For an elementary verification, substitution \(s=nv\) and integration of the geometric sum give \[\int_0^n(1-s/n)^n\log s\,ds =\frac{n}{n+1}\bigl(\log n-H_{n+1}\bigr).\] Indeed, \[\int_0^1(1-v)^n\log v\,dv =-\frac1{n+1}\int_0^1\frac{1-(1-v)^{n+1}}v\,dv =-\frac{H_{n+1}}{n+1}.\] The integrands in the first identity, extended by zero for \(s>n\), are bounded in absolute value by \(e^{-s}|\log s|\). Dominated convergence proves (207). Consequently (206) gives \(tW(t)\to e^{-\gamma}\) as \(t\downarrow0\). On the other hand, substituting \(v=tu\) and using bounded convergence gives \[tW(t)=\int_t^\infty\omega(v/t)e^{-v}\,dv\longrightarrow\ell.\] This identifies \(\ell=e^{-\gamma}\). ◻

Proof. Shifting the frequencies multiplies their sum by a complex number of modulus one. We may therefore write \(T(x)=\sum_{j=0}^{J-1}b_j e(jx)\) and \(f(x)=|T(x)|^2\). Let \(I_r\) be the arc of length \(\delta\) centred at \(x_r\). Their interiors are disjoint. For \(t\in I_r\), the fundamental theorem of calculus along that arc gives \[f(x_r)\le f(t)+\int_{I_r}|f'(x)|\,dx.\] Average over \(t\in I_r\) and sum over \(r\) to obtain \[\sum_r f(x_r) \le\delta^{-1}\int_0^1|T(x)|^2\,dx +\int_0^1|f'(x)|\,dx.\] Since \(|f'|\le2|T'||T|\), Cauchy–Schwarz and Parseval give \[\int_0^1|f'(x)|\,dx \le2\|T'\|_2\|T\|_2 \le4\pi(J-1)\sum_{j=0}^{J-1}|b_j|^2.\] This proves the asserted estimate. Distinct reduced fractions modulo one with denominators at most \(Q\) have circular distance at least \(Q^{-2}\): subtracting two such fractions, or subtracting an integer from their difference, leaves a nonzero integer numerator over the product of their denominators. Apply the estimate with \(\delta=Q^{-2}\). When there is just one fraction, the same arc argument applies directly. ◻

Proof. First choose linear coordinates in which the coefficients of \(Y^m\) in \(F\) and \(Y^n\) in \(G\) are nonzero constants. Such coordinates exist: choose the direction of the \(Y\)-axis outside the zeros of the two highest homogeneous parts. Each part excludes only finitely many directions in the projective line. Scaling the polynomials makes these leading coefficients one.

Put \(K=\mathbb C(X)\). The two polynomials are coprime in \(K[Y]\). Indeed, clearing denominators in a common factor and removing common factors of its coefficients would give a common polynomial factor in \(\mathbb C[X,Y]\). This is the elementary Gauss lemma: the product of two polynomials whose coefficients have no common divisor again has coefficients with no common divisor, as follows by reduction modulo any irreducible divisor in \(\mathbb C[X]\).

Consider the linear map over \(K\) \[ (A,B)\longmapsto AF+BG, \qquad \deg_Y A<n,\quad\deg_Y B<m, \tag{208}\] with target the polynomials of \(Y\)-degree less than \(m+n\). It is injective: from \(AF=-BG\) and coprimality, \(F\) divides \(B\), forcing \(B=0\) and then \(A=0\). Its matrix in monomial bases is the Sylvester matrix. Its determinant \(R(X)\) is a nonzero polynomial. If \((x,y)\) is a common zero, every polynomial in the image of the specialized map at \(X=x\) vanishes at \(Y=y\). That image is a proper subspace, so \(R(x)=0\). There are finitely many such \(x\), and each fiber contains finitely many points because \(F(x,Y)\) is monic of degree \(m\). Thus the common zero set is finite.

Now choose linear coordinates once more so that the \(X\)-coordinates of those finitely many points are distinct and both leading coefficients in \(Y\) remain nonzero constants. The first condition excludes the finitely many directions joining pairs of common zeros; the second excludes the directions on which either highest homogeneous part vanishes. A direction satisfying both exists. Repeat the construction of \(R\) in these coordinates.

We claim that \(\deg R\le mn\). Write \[F=\sum_{k=0}^{m}f_k(X)Y^k,\qquad G=\sum_{k=0}^{n}g_k(X)Y^k, \qquad \deg f_k\le m-k,\quad\deg g_k\le n-k.\] View the rows of the Sylvester matrix as the coefficients of \(Y^iF\) for \(0\le i<n\) and \(Y^jG\) for \(0\le j<m\); label its columns by \(Y^k\), \(0\le k<m+n\). An entry from row \(Y^iF\) and column \(Y^k\) has degree at most \(m+i-k\); an entry from row \(Y^jG\) has degree at most \(n+j-k\). Every nonzero term of the determinant uses each row and column once, so its degree is at most \[\sum_{i=0}^{n-1}(m+i)+\sum_{j=0}^{m-1}(n+j) -\sum_{k=0}^{m+n-1}k=mn.\] Every common zero gives a distinct root of the nonzero polynomial \(R\). This proves the bound. ◻

Proof. Write the progression as \(a+qj\), with \(j\) in the real interval \[(x-a)/q<j\le(x+H-a)/q\] of length \(J\). Fix an absolute \(s\ge s_0\) sufficiently large that \(\theta=1/(2s)<1/2\), and put \(v=J^\theta\) and \(D=J^{1/2}=v^s\). For every prime \(p\le v\) not dividing \(q\), divisibility of \(a+qj\) by \(p\) specifies exactly one forbidden class of \(j\) modulo \(p\). For a squarefree product \(l\) of these primes, the Chinese remainder theorem therefore gives the intersection count \[J/l+O(1),\] with an absolute error independent of \(x,a,q,l\). Apply Lemma 3 with \(X=J\) and \(g(p)=1/p\) on this prime set. If \(N\) counts the surviving coordinates, it gives \[ N\ll J\prod_{\substack{p\le v\\p\nmid q}}(1-1/p) +D(1+\log D)^{C_2} \tag{209}\] for an absolute constant \(C_2\). To justify the remainder explicitly, let \(C_1\) be the divisor-weight exponent in (5) and choose an integer \(k\ge2^{C_1}\). On squarefree \(l\), \(\tau(l)^{C_1}\le\tau_k(l)\), where \(\tau_k(l)\) counts ordered factorizations of \(l\) into \(k\) positive integers. Summing by the first \(k-1\) factors gives \[\sum_{l\le D}\tau_k(l) \le D\left(\sum_{d\le D}\frac1d\right)^{k-1} \le D(1+\log D)^{k-1}.\] In particular, the remainder in (209) has no dependence on \(q\).

Mertens’ formula gives, for large \(J\), \[\prod_{\substack{p\le v\\p\nmid q}}(1-1/p) =\prod_{p\le v}(1-1/p) \prod_{\substack{p\mid q\\p\le v}}(1-1/p)^{-1} \ll\frac1{\log v}\frac q{\varphi(q)} \ll\frac1{\log J}\frac q{\varphi(q)}.\] Every prime in the progression that exceeds \(v\) is among the survivors. The primes at most \(v\) contribute at most \(v\) further points, regardless of \(q\). Thus the desired prime count is at most \[N+v\ll \frac{Jq}{\varphi(q)\log J} +J^{1/2}(1+\log J)^{C_2}+J^\theta.\] The last two terms are \(O(J/\log J)\) for all sufficiently large \(J\), uniformly in \(q\). Since \(q/\varphi(q)\ge1\), they are absorbed by the first term. Substituting \(J=H/q\) completes the proof. ◻