An asymptotic formula for the number of totients

Proof. For the true simplex the triangular inversion is

The transformation from u_1,\ldots,u_j to s_1,\ldots,s_j has determinant 1. This proves the volume and distribution statements.

Set K_i=\prod_{r<i}\beta_r, K_0=1. The map u_i\mapsto u_i/K_i sends S_j(\boldsymbol\beta) into S_j(\boldsymbol1), because K_r\ge\beta_iK_i when r>i. Its inverse Jacobian is \prod_{r<j}\beta_r^{j-r}.

For the slice estimates, define \gamma'_0=1 and \gamma'_t=\beta_t^{-1}\sum_{i<t}\gamma'_ia_{t-i}. Then 0<\gamma'_t\le g_t and

The marginal density of s_t, under the uniform measure on this simplex, is at most j\gamma'_t/(\beta_0B). For the coordinate assertion, fix all other positive-index slacks. The coordinate u_t is affine in s_t with slope 1/\beta_t. Integrating first in this fiber and bounding by the full projection volume gives the additional factor \beta_t.□

Proof. By (3.5) and Lemma 3.4,

Represent W_t=E_t/\sum_{r=0}^jE_r, where the E_t are independent mean-one exponential variables. The main numerator has j-i+1=h_i-Q+1 terms, and

Exponential moment bounds give exponentially small probabilities for a fixed relative deviation of either the numerator or the denominator. The error numerator is bounded in absolute value by C\sum_{r\ge0}\rho^rE_{i+r}; this sum has a uniformly bounded exponential moment, since \prod_{r\ge0}(1-z\rho^r)^{-1}<\infty for 0<z<1. Once h_i\ge C_\eta(Q+1), these three bounds give the first assertion. The second is the exact marginal tail of W_j.□

Proof. The band lower bounds are u_t\gg h_t\rho^{-h_t}. Changing each coordinate by at most 1 changes inequality t by O(h_t^2). These errors are absorbed by (3.14), including at t=0, where u_0=B is fixed. The logarithm of its Jacobian upper bound is at most

Lemma 3.4, (3.6), and (3.12) prove (3.13). The coordinate scaling factor is \prod_{t<i}\beta_t, without the Jacobian exponents; summing for h_t>h_i\ge H proves its stated bound.

For the shells put h=h_i. Throughout a box meeting the bands, u_i\ll b_i. Conditions (ii) and (iii), together with the unit perturbations, put the enlarged slack in an interval starting at zero of length at most

Here the h^3 term includes h^2\rho^hu_i=O(h^3). Since Lg_i/B\ll\rho^h, Lemma 3.4 bounds the relative volume by

Condition (i), after expanding its interval by 2, costs only O_A(\rho^h). Sum these estimates over h\ge H, and use the bounded enlargement cost. The prime-weight assertion follows again from (3.12). For the stronger assertion, omit h^{-4} from the slack interval. Changing \xi_i to 1, for i\le R, only removes points whose old slack is between 0 and (\xi_i-1)u_i, which obey the same bound. Finally every full unit box has uniformly bounded mass when an arbitrary subset of its coordinates uses reciprocal-prime measure: multiply the factors in (3.12) for precisely that subset. This proves the mixed-measure assertion as well.□

Proof. Put \sigma=1/\log Y. The Euler factor is

whose logarithm is p^{-1+\sigma}+O(p^{-2+2\sigma}), uniformly in this range of \sigma. Partial summation gives \sum_{p\le Y}(p^{-1+\sigma}-p^{-1})=O(1); hence the product is O(\log Y). Rankin’s inequality gives the tail bound. For the last assertion the exponent is

and \widetilde b_L\asymp P\rho^{-P}.□

Proof of Proposition 3.3. Take \eta=0.04 in (3.7). By (3.2), its complementary bands imply the coarse bands in (3.10). Apply (3.8) as well. Both conclusions hold for all preimages outside the union of their exceptional sets.

We may also remove v\le x^{0.95} and \Omega(v)>5B, at a cost o(V(x)). For the latter, the elementary reciprocal moment bound with z=1.9<2 gives

The Euler product bounds the reciprocal sum by O((\log x)^z), and z-5\log z<-1. For every preimage, \Omega(n)\le\Omega(\varphi(n))+1\le6B. The p_1 band gives \log p_1\le(\log x)^{0.61}, so

It remains to impose the size restriction on a. For any preimage failing it, fix p_1,\ldots,p_L,a. The prime p_0 is distinct from the others and from the factors of a. Supermultiplicativity of \varphi gives

The prime number theorem upper bound therefore gives at most

choices of p_0; if the interval is nonempty its upper endpoint is at least x^{0.9}. Sum the prefix by Lemma 3.6, and the cofactor by Lemma 3.7. This bounds all failing preimages, and therefore all values having at least one such preimage. It proves the exceptional-value assertion.

Finally b_{i+1}/b_i=(1-1/h_i)\rho. The bands and (3.2) imply that the largest double logarithm after index R is at most 0.62b_R. There are H-P\le H such primes, proving the second line of (3.11). Its right-hand side is smaller than \exp(0.89b_R)<\log p_R for large H, then large x. For the first line use the p_1 bound and L\ll\log B, while the a bound depends only on H.□

Proof. The last comparison follows from

It gives S_i<z_i. The next prime band has upper endpoint, in double logarithms, less than 0.7b_{i+J_i}; all remaining primes, including those in a, are smaller. Taking totients cannot introduce a prime above this bound. This proves (3.19).

A bad tuple has at least one failing full witness. We bound the number of these witnesses; this is an upper bound for the number of bad tuples, regardless of witness multiplicity. The prime-count upper bound for p_0 contributes Cx/\log x, with the product of reciprocal factors for all other variables. The smooth a-sum contributes at most K_H. Failure of the first condition in (3.18) is covered by Lemma 3.6, condition (iii). Its contribution is therefore O(K_HH^{-2}xG_m/\log x).

For the other conditions fix i, write h=h_i, b=b_i, and J=J_i. If i\ge1, the reciprocal sum for the common initial segment p_1,\ldots,p_{i-1} is O(G_m), by (3.13). All of p_i,\ldots,p_L are at most \exp\exp(1.2b). Their unrestricted reciprocal sums together cost \exp(Ch^2), since there are at most h variables and \log b=O(h). For i=0, omit p_0 from these reciprocal sums and use the same estimate at b=B.

Partial summation of (3.9) gives

For a failure involving p_0, apply (3.9) directly to its counting interval; its upper endpoint has logarithm comparable with \log x. The normality failures thus contribute, relative to xG_m/\log x, at most

Polynomial factors from choosing an index are included in Ch^2.

A square of a prime q>z_i in the shifted-prime product either divides one shift twice or divides two different shifts. For \ell=1,2 and Z\ge2, the elementary estimate

follows by summing over all positive multiples of q^\ell. If the shift is p_0-1\le T, its integer count is at most \lfloor T/q^\ell\rfloor\le T/q^\ell. Relative to prime counting this loses at most \log x=\e^b when i=0. Both types of square therefore cost q^{-2}, up to \exp(Cb+Ch^2). Summing over q>z_i, their total relative contribution is at most

Finally \Omega(\varphi(a))\ll\log a\le\e^{2\widetilde b_L} =H^{o(1)}, whereas b_i/h_i^8 is exponentially large in h_i\ge H. In the identity for D_i, overlap between a and the displayed primes can occur only at p_L. That overlap changes the sum of factor counts by 1-\Omega(p_L-1)\le0. Failure of the last condition in (3.18) therefore forces some i+J<j\le L to satisfy \Omega(p_j-1)>b_i/(2h^9). The Euler product gives

Using the band bound for p_j, this exceptional reciprocal sum is at most

because b_{i+J}\ll b_i h^{-18}. The resulting relative contribution is at most

Each sum in (3.20)–(3.22) decreases faster than every inverse power of H, uniformly for \alpha in its compact range. Together with the thin-slack bound, this proves the proposition. Replacing the endpoint x by x/c only decreases the witness sets, so the same bound holds with unchanged parameters.□

Proof. For primitive, distinct, admissible integral linear forms a_jn+b_j with positive leading coefficients and nonzero determinant \Delta as defined below, Ford’s uniform upper sieve [8, Theorem 2.5] gives

Here admissibility means that no prime divides the product of the forms for every integer input; the implied constant depends only on k, including when the coefficients vary. For our forms, primitivity is automatic, and the determinants are A and AA'(A-A'), up to sign. They are nonzero and have absolute value at most y^3.

If our forms are inadmissible, an offending prime is at most k, since each primitive linear form has at most one root modulo that prime. At every simultaneous-prime input one of the forms must equal this prime. Each such equality has at most one solution, so there are at most k inputs. Their contribution is absorbed in (4.1).

For admissible forms, the elementary estimate

and (4.3) prove (4.1). To recall its uniformity, split the product over prime divisors of d at \log(d+10). Mertens’ product estimate bounds the first part by O(\log_2(d+10)). For the remaining part, use \sum_{p\mid d}\log p\le\log d to bound the sum of reciprocal prime divisors, giving a bounded factor. Since k takes only the values 2 and 3, all constants are absolute.

Finally, partial summation of (4.1), with the coefficients fixed, gives

This also includes a possible prime at the lower endpoint.□

Proof. We first describe the layers and the weighted summation that combines them. We then count the top layer, estimate a general lower layer, and finally sum over the small prime factors.

The layer configurations. For 0\le i\le b and 0\le j<b, let

Restricting the equality in condition (ii) to primes at most Y_i gives the common product

For 1\le i\le b, put

Each t_i^\# is squarefree and supported on (Y_i,Y_{i-1}]. For j\ge i the factors t_{i,j} and t'_{i,j} equal 1, so

Thus a layer consists of two allocations of the same squarefree integer among i labeled slots.

Let \mathcal C_i be the set of configurations

arising from tuples counted by N. Restriction of prime factors maps \mathcal C_{i-1} into \mathcal C_i; the two allocations in (4.6) determine each extension uniquely. Reconstructing a tuple from its small prime factors runs from \mathcal C_b back to \mathcal C_0; the weighted count below sums in the opposite direction, starting with the top layer. The original tuples are in bijection with \mathcal C_0, since p_j=s_{0,j}+1 and q_j=s'_{0,j}+1. For i\ge2 we will bound, uniformly in \sigma_i, the reciprocal extension sum

This is the appropriate weight because 1/s_{i-1}^\#=1/(s_i^\#t_i^\#).

Every configuration considered here extends to a genuine solution. In particular, its partial common product is at most y/r, each shift is at most y, and every fixed or conditional coefficient used below is at most y. When enlarging a sum for an upper bound, we retain any necessary restriction on a conditional coefficient until the corresponding sieve estimate has been applied.

The top layer. Only the zeroth shift can have a prime factor greater than Y_1. Consequently t_1^\# is the same part of p_0-1 and q_0-1, and t_1^\#>\sqrt y. Normality, applied with endpoint p_0-1, gives

Write t_1^\#=t'Q, with Q=P^+(t_1^\#). The weaker bound \Omega(t_1^\#)\le4B_y already gives

After \sigma_1 and t' are fixed, the completed primes have the forms AQ+1,A'Q+1. Their inequality implies A\ne A', which is exactly the nonzero determinant condition for the three-form sieve. With

a nonempty extension has X\ge Q\ge y^{1/(8B_y)}. Lemma 4.1 therefore bounds the number of Q by

The integer t' is squarefree and supported on (Y_1,y]. Mertens’ estimate gives

It follows that, for each \sigma_1,

The prime conditions in an intermediate layer. Fix 2\le i\le b and \sigma_i. The last slot, of index i-1, is complete after this layer. Let Q_1,Q_2 be its largest prime factors on the two sides; both lie in [U_{i-1},Y_{i-1}].

Suppose first that Q_1=Q_2=Q. Remove the unique occurrence of Q from t_i^\#, and call the result t. For fixed allocations of t, the completed primes are AQ+1,A'Q+1 with A\ne A'. Lemma 4.1 gives

Now suppose Q_1\ne Q_2 and remove both, obtaining t. In addition to its two allocations, fix the position of Q_1 on the second side and of Q_2 on the first side. There are at most i^2 choices. If neither prime lies in the opposite last slot, the two completed prime conditions are AQ_1+1 and A'Q_2+1; two applications of (4.2) with k=2 give

If Q_2 lies in the last slot on the first side, then Q_2<Q_1. The prime Q_1 cannot lie in the last slot on the second side, whose largest prime is Q_2. The completed prime conditions are now AQ_2Q_1+1 and A'Q_2+1. First sum over Q_1 conditional on Q_2, using the forms Q_1,AQ_2Q_1+1. Feasibility ensures AQ_2\le y, so the inner reciprocal sum is uniformly O(B_y^2/\log U_{i-1}). Only after this estimate do we enlarge the range of Q_2 and apply the two-form bound to Q_2,A'Q_2+1. This proves (4.9) again. The reversed incidence is treated by reversing the order of summation. Both incidences cannot occur simultaneously, as they would imply both Q_1<Q_2 and Q_2<Q_1.

Counting the allocations. Put \Delta_i=\nu_{i-1}-\nu_i. Normality bounds the number of prime factors of an individual shift in (Y_i,Y_{i-1}] by (\Delta_i+\delta)B_y. Indeed, if the shift ends before Y_{i-1}, apply normality only up to its endpoint; if it ends before Y_i, the count is zero. In either case the error is at most \sqrt{\log_2 S\,B_y}=\delta B_y. Only i shifts contribute to this layer, and removing the distinguished primes decreases the count. Thus

Since t is squarefree, each of its prime factors chooses one of i slots on each side, giving at most i^{2\Omega(t)} dual allocations. Write

Mertens’ estimate gives M_i\le\Delta_i B_y+O(1), uniformly in the cutoffs. Since \delta B_y\ge\sqrt{B_y}, increasing the absolute threshold y_0 ensures M_i\le(\Delta_i+\delta)B_y. Hence

The middle inequality follows by writing i^{2n}=i^ni^n, using i^n\le i^{I_i}, and extending the remaining exponential series. It is valid without any lower bound on \Delta_i/\delta.

Combining (4.8), (4.9), and (4.10), and using i\le b\le B_y to absorb the i^2 position choices, gives

The squarefree hypothesis was used both to remove a single occurrence of each distinguished prime and to obtain the factorial denominator in (4.10).

Multiplying the layer estimates. Starting from (4.7), sum over \mathcal C_1. For each subsequent layer use the exact weighted identity

All bounds in (4.11) are uniform in the lower configuration. Their constants therefore multiply to at most C^bB_y^{6b}. If c_i=i\log i+i, so that c_1=1, the power of \log y accumulated in this procedure is

Here c_{j+1}-c_j-2=a_j, including j=1. The identity also holds for b=1. Discard the nonpositive final term -c_b\nu_b. It remains to bound \sum_{\sigma_b\in\mathcal C_b}1/s_b^\#.

The smooth parts and repeated factors. Write s=s_b^\#/D and L_b=\log_2Y_b. For a fixed s, its allocation among the b left slots has at most b^{\Omega(s)} possibilities. The allocation of sD among the b right slots and the additional slot D' has at most (b+1)^{\Omega(sD)} possibilities. These bounds allow prime powers: assigning labeled copies of a repeated prime to slots overcounts every possible distribution of its exponent.

Each left shift has largest prime factor above Y_b. Its number of prime factors at most Y_b is bounded by normality as follows:

If S=Y_b, the first normality inequality alone gives the same bound. Thus \Omega(s)\le3bL_b. The ordinary smooth-number Euler product, including all powers, now gives

No squarefreeness is assumed below Y_b. Combining this estimate with the layer bounds proves (4.4), after increasing the absolute constant C.□

Proof. Choose one basic witness for each tuple under consideration. All choices satisfy (3.18), by the definition of \mathcal G(t). If two distinct tuples have the same value, some displayed prime differs: equality of all the primes p_0,\ldots,p_R would also force equality of d. Let i be the first unequal prime index, and write q_j for the primes in the other witness. Put

Thus h\ge H. The residual integers in the good conditions are

Canceling the common prefix leaves the identity

We will apply Proposition 4.2 to this identity. First we verify its size and interval hypotheses; then we count all ways in which its solutions can give tuple pairs.

Sizes of the suffix and its layers. For sufficiently large H, uniformly for h\ge H,

Indeed 30\lambda lies strictly between 18 and 20; the ceiling in J changes only constant factors. In particular J<h/2 and i+J<L. The constants in this proof are independent of H,x,i and the phase, once H and then x are sufficiently large.

For i=0 set y=x. For i\ge1 place v^{(i)} in a dyadic interval (y/2,y]. The coarse bands in (3.10) imply that the logarithm of the preimage suffix after p_i is at most

To see the first term, use 1.1\widetilde b_{i+1}<0.62b_i for large x, and bound the number of displayed factors by h. The bound for a gives the second term. These quantities are negligible compared with \log p_i\ge\exp(0.88b_i). Consequently, writing B_y=\log_2y,

For i=0 the first inequality is part of the basic witness conditions, and B_y=b_0=u_0=B by convention.

Our target is a bound of the form

for the suffix pairs, with an absolute \kappa>0. The strict simplex slack will supply the exponential saving. Since B_y\asymp b_i, this saving can absorb the \exp(O(b_i\log h/h^8)) cost of recovering tuple coordinates inside D_i and D_i'.

Let

It follows from (5.2) that S<z and J\delta=o(h^{-20}). Normality gives \Omega(p_{i+j}-1),\Omega(q_{i+j}-1)\le4B_y for 0\le j\le J. For example, split the prime factors at S, apply the two normality conditions, and use p_{i+j}-1\le v^{(i)}\le y. If

then

This follows from (p_{i+j}-1)\le A_j^{\Omega(p_{i+j}-1)} and the reverse bound A_j\le p_{i+j}-1. When i=j=0, the convention u_0=B causes only an O(1) difference from \log_2p_0, since x^{0.9}\le p_0\le x+1.

The bands in (5.4) are disjoint and decrease with j. Their smallest separation is a constant multiple of b_i h^{-20}, which dominates the error O(\log b_i). All the A_j,A_j' exceed z, whereas

For the latter assertion, every prime in the residual preimage is at most p_{i+J+1} or q_{i+J+1}, and 1.1\widetilde b_{i+J+1}<0.7b_{i+J}; taking a totient cannot increase the largest prime factor. Repetitions of the last prime in a or a' do not affect this conclusion.

Aligning the largest factors on the two sides. We claim that

Suppose, for example, that A_j>A_j', and put e=(\log_2 A_j-\log_2 A_j')/B_y. On the first side of (5.1), each of its first j+1 shifts contributes at least (e-\delta)B_y prime factors, with multiplicity, to (A_j',A_j]. On the other side only its first j shifts can contribute, each at most (e+\delta)B_y. The later shifts have smaller largest factors, and both residual integers are z-smooth. The lower endpoint exceeds S, so normality applies. Equality of the two sides therefore gives

which proves (5.5). Interchanging the sides handles the other order.

Cancel any equal primes among the two lists in (5.1), and let r be the product of their shifts. The disjoint prime bands show that equality is possible only at the same original index. The index i survives, since p_i\ne q_i. Let b\le J+1\le B_y be the length of the remaining lists. Their corresponding primes are unequal, as required by Proposition 4.2.

Set Y_b=z, Y_0=y and \log_2U_0=0.8B_y. At each remaining positive index, choose an interval on a \delta-grid in normalized double logarithms which contains the corresponding pair from (5.5). Its width is O(J\delta). The intervals remain strictly separated, because J\delta=o(h^{-20}). Each lies below height 0.8, by (5.3) and the upper bound u_{i+1}\le0.62b_i. At index zero, (5.3) and (5.4) give largest factors above height 0.9. Thus all the ordered-cutoff hypotheses of Proposition 4.2 hold. If b=1, there are no positive indices to grid and Y_1=z.

The part of p_i-1 supported on primes at most Y_1 has logarithm at most 4B_y\log Y_1\le4B_y\exp(0.8B_y). Since p_i\ge y^{0.9}, the complementary part exceeds \sqrt y for large H. The whole common product is squarefree above Y_b, by the good conditions; canceling the equal shifts preserves this property. This verifies the last two hypotheses of Proposition 4.2.

Apply that proposition to the remaining lists with D=D_i, D'=D_i' and the factor r just canceled; their common product is at most y/r. Write \nu_k=\log_2Y_k/B_y and \mu_k=\log_2U_k/B_y for the normalized interval endpoints.

Write j_1<\cdots<j_{b-1} for the surviving positive original indices. Since j_k\ge k and a_k\le a_{j_k}, the grid intervals and the strict slack condition in (3.18) give

Here a_j is increasing and \sum_{j\le J}a_j=O(J\log(2J)). The grid widths and the explicit \delta term in (4.4) contribute another O(J^2\log(2J)\delta)=o(h^{-4}) to its exponent of \log y. Thus, for some absolute \kappa>0, its logarithmic factor is at most

It remains to show that the other factors and the recovery of tuple coordinates use only a smaller part of this saving.

Recovering tuples and summing the remaining choices. The comparison estimate counts its displayed primes and its residual integer D_i'. We must also account for the tuple data forgotten inside D_i,D_i'. If R\le i+J, all displayed tuple primes are already determined. Their tail totient is

and similarly on the other side, with an empty product when R=i+J. If R>i+J, the missing tuple data give an ordered factorization

There are at most (h+1)^{\Omega(D_i)} such factorizations. Indeed, for any integer n, assigning its \Omega(n) prime occurrences to k labeled slots bounds the number of ordered multiplicative factorizations into k factors by k^{\Omega(n)}. Once a factor p_j-1 is fixed, p_j is fixed as well. This argument also covers repeated prime factors. Consequently the two missing tails cost at most

The factorizations in (5.7) are exact: the primes up to R are distinct and the remaining preimage tail is smaller than p_R, by (3.11). All repetitions inside that tail are kept in its totient d.

We now sum the comparison bound over the canceled primes, the grids, and D_i. The canceled index sets contribute at most 2^{J+1}. Each canceled prime has reciprocal shift sum O(b_i) by Mertens’ theorem. The number of grid choices is at most (C/\delta)^{2(J+1)}. Thus their total cost, including the factors (CB_y^6)^b in (4.4), is \exp(O(h^2)). For the residual integer, the finite Euler product gives

Before enlarging this sum we use the good-condition bounds \Omega(D_i),\Omega(D_i')\le b_i/h^8 in both (5.8) and the factor (b+1)^{\Omega(D_i)} of the comparison estimate.

The logarithm of all the remaining costs, apart from the factor y/(\log y) and the saving from (5.6), is at most

The last term uses \log_2z\ll b_i h^{-18} to bound the factor (\log Y_b)^{1+3b\log(b(b+1))} in (4.4), as well as the sum over D_i. All little-oh estimates here are uniform for h\ge H as H\to\infty, because b_i\asymp h\rho^{-h}. We have therefore obtained, for some absolute c_2>0,

For i=0 the same expression bounds all the pairs with first unequal index zero, using y=x. Choosing one witness for each tuple has not introduced multiplicity into the desired count: comparison data and the factorizations just counted determine each ordered pair of tuples.

Summing suffixes and restoring the common prefix. For i\ge1 the required sum over suffix pairs is weighted by 1/v^{(i)}. A dyadic interval in (5.10) contributes at most

Writing the dyadic endpoints as y=2^n, and comparing the sum with an integral, gives

In this change of variable, u=\log(n\log2), the factor 1/\log y exactly compensates for the density of dyadic endpoints. In particular, no factor of order \exp(b_i) is lost.

For fixed suffix data and common primes p_1,\ldots,p_{i-1}, the number of possible p_0 is at most

Indeed the upper endpoint for p_0 is 1+x/(v^{(i)}\prod_{j=1}^{i-1}(p_j-1)); if the range is nonempty, its restriction p_0\ge x^{0.9} makes its logarithm comparable to \log x, so the prime number theorem gives this upper bound. The projected-prefix estimate (3.13) and (5.11) now show that the contribution for this i is at most

This also applies to the empty projected prefix when i=1. Summing over h\ge H yields the convergent tail

For i=0, (5.10) gives O((x/\log x)\exp\{-c_2B/m^4\}), which is o(xG_m/\log x). This proves the proposition, uniformly for both endpoints t.□

Proof. Coverage gives the lower bound. For every positive integer r, r-1\le r(r-1)/2, and hence

Adding the at most |D| remaining elements proves the upper bound. There are at most K/2 fibers with r_w\ge2, which proves the bound for |E^*|. Also

by r\le1+r(r-1)/2 for integers r\ge0. Adding the elements of D proves the second bound. Outside E^* coverage, absence of discarded elements, and r_w\le1 give exactly one preimage under F.□

Proof. Apply Lemma 5.2 with T=\mathcal T(t), G=\mathcal G(t), D=\mathcal D(t) and W=\mathcal V\cap[1,t]. Let E be the exceptional values in Proposition 3.3, restricted to [1,t]. Every preimage of each v\notin E is basic, so it induces an element of T. The size of E is negligible on the scale xG_m/\log x, by (3.4); Proposition 3.8 gives the same bound for |D|, and Proposition 5.1 gives it for K. The counting conclusions therefore follow from the lemma.

Fix v\notin E^*(t). Every preimage is basic and so induces a tuple in T. It cannot induce a tuple in D, since v\notin F(D). The remaining tuple is unique. Thus, writing Q=p_0\cdots p_R, every preimage of v has the form Qz, where \varphi(z)=d. It follows that every such preimage is at least Q\ell(d).

For the reverse inequality choose one basic witness with tail w. The deterministic size bound (3.11) gives \ell(d)\le w<p_R. The prefix primes are distinct, so \gcd(Q,\ell(d))=1 and

Hence \ell(v)\le Q\ell(d), proving (5.13).□

Proof. For fixed data in \mathcal D_H(x) put

Since d\le w, the deterministic bound (3.11) implies

The possible largest primes are precisely x^{0.9}\le p_0\le 1+t/D. The remaining prime factors are smaller than x^{0.9} for large x, so this choice introduces neither a repeated prefix prime nor another ordering condition. The endpoints t/D lie uniformly in [x^{1-o(1)}/c,x]. The prime number theorem, with \log(t/D)=\log x+o(\log x) uniformly, therefore gives

The lower cutoff costs a relative O(x^{-0.1+o(1)}), uniformly in the data. Summing this formula and using (6.3) counts \mathcal T(t) with main term tM_1/\log x and error o_{x\to\infty;H,c}(xG_m/\log x). Proposition 5.3 replaces \#\mathcal T(t) by V(t) with an error whose normalized iterated limit is zero. Since t is either x or x/c, this proves (6.4).□

Proof. First let c>1. Apply Proposition 6.1 at t=x and t=x/c, using the same M_1(x;H) and G_m(x). Subtracting gives

Ford’s estimate (3.4) supplies a positive constant c_- with V(x)\log x/(xG_m)\ge c_- for large x. Consequently

Let H tend to infinity and then replace x by cx to obtain the assertion. This also covers arguments at which m(x) and m(x/c) differ: the latter integer never enters the comparison. Neither continuity of the phase coefficient nor matching values at the ends of the phase interval is required.

The case c=1 is immediate. If 0<c<1, apply the result just proved to the multiplier 1/c>1 and the argument y=cx; taking reciprocals gives the stated limit.□

Proof. Write a_*=\lambda/\rho, so that \lambda\le\alpha_s<a_*. Let

Every witness belongs to the finite set \{1,\ldots,q_H\}^{H-P}\times\{1,\ldots,A_H^*\}. Its corresponding integer w and totient d satisfy d\le w\le A_H^*q_H^{H-P}. These bounds do not involve x or s. Finally, a_j=\int_j^{j+1}\log t\,\dd t\le\log(j+1), so the definition (2.6) and the bounded tail coordinates give (6.5).□

Proof. An intersection imposes the largest of the witness thresholds at each slack coordinate.

Intersection volumes. Set C_i=\max_{\eta\in T}D(m-i,\eta) and introduce the prefix slacks

Lemma 3.4 gives \sum_{i=0}^Rg_it_i=B, and the substitution from (u_1,\ldots,u_R) to (t_1,\ldots,t_R) has determinant one. The intersection is t_i\ge C_i for every i, including i=0. Translation by C_i leaves a simplex of available size B-\sum_i g_iC_i. Its volume is

which proves (6.8) after putting h=m-i. It remains to compare the volume of the union with the prime mass.

From primes to volume. Identify Q_h=p_{m-h} for P\le h<H. These are exactly the primes with indices R+1,\ldots,L. For fixed tail witness \eta, the original prefix conditions are its coarse bands together with

Taking the union over \eta\in\mathcal W_{H,\theta}(d) is essential: a prime prefix with several witnesses contributes just once to (6.1).

First replace the reciprocal prime sum by the volume of this union with its bands and its \xi_i. In a unit box wholly contained in the union, the product of the prime reciprocal sums differs from its volume by a relative O(\sum_{i=1}^R e^{-c b_i})=O(e^{-c' b_R}), by Lemma 3.6. The geometric growth of b_i as i decreases makes this estimate independent of R. Both the total mass and the total volume before this replacement are O(K_HG_m), by summing over witnesses as in (6.2).

If a unit box meets the union without being contained in it, choose a witness whose region meets the box. That witness’s region does not contain the box. Consequently the box lies in a shell at a prefix band endpoint, or within O(h_i^2) of equality in one of (6.9). For an upper bound, sum these shells over witnesses using (6.2). Thicken the discrete tail coordinates into unit boxes as well and sum 1/\varphi(a) at a cost O(K_H). The resulting full L-coordinate boxes are covered by the shell bounds of Lemma 3.6 and Proposition 3.8. Their contribution is o_H(1)G_m. More explicitly, the slice coefficient for an index with h=m-i is Lg_i/B\ll\rho^h. Summing the shell bounds therefore costs at most

The broader O(K_HH^{-2})G_m shell estimate in Proposition 3.8 also suffices.

Removing the slack perturbation. Replace \xi_i by 1 for i\le R, retaining the bands. The removed region lies in a shell of thickness O(e^{-h_i/40}b_i), with the same box-thickening errors. Its normalized contribution is at most

Both shell estimates are valid for the union because upper bounds may sum over witnesses, while 0\le f\le1.

Removing the prefix bands. For every point satisfying the now unperturbed prefix inequalities, recurrence iteration gives

where v_{H-1}=\log_2Q_{H-1}. To see this, retain the contribution of the first tail coordinate in each prefix inequality, discard the other nonnegative tail contributions, and apply the recurrence for g. The tail band for v_{H-1} and (3.5) give the displayed lower bound. Thickening the H-P tail coordinates changes inequality i by O(H\log(h_i+1)). The enlargement term C h_i^2\rho^{h_i}u_i is at least a constant times CHh_i^2, so it absorbs this error. Together with the retained tail bands, this places the full region inside the enlarged simplex of Lemma 3.6.

To sum these regions without a factor for the number of witnesses, use (6.2) and first fix a. Partition the tail coordinates into half-open unit boxes \mathcal C=\prod_{h=P}^{H-1}\mathcal C_h. Let \mathcal U_{\mathcal C} be the union of \mathcal K_\eta over all allowed witnesses \eta=((Q_h),a) with (\log_2Q_h)_h\in\mathcal C. Let E be the set of prefix points violating at least one removed band. Aggregating the reciprocal weights within a box gives

The sums over q are over primes. The product is O(1) uniformly in the number of tail coordinates, by (3.12) and their geometrically growing lower endpoints. Here R+(H-P)=L and \mathcal C has unit volume. By the preceding enlargement argument, every set on the right lies in the same enlarged L-simplex. Since the tail boxes are disjoint, summing their volumes counts a subset of that simplex once. Finally, summing 1/\varphi(a) over the common smooth envelope costs O(K_H). All these bounds hold at each phase; they do not compare witness sets at nearby phases.

Scale that enlarged simplex into the true L-coordinate simplex. Its Jacobian cost is bounded, and its coordinate scaling factors through index R are

For large H, and then large x, a violation of a removed [0.9\widetilde b_i,1.1\widetilde b_i] band therefore becomes a violation of the [0.95b_i,1.05b_i] band in the true simplex. Lemma 3.5 applies with dimension L=m-P, since h_i\ge H and P/H\to0. Summing its bounds gives O(e^{-cH}) of the simplex volume. After the smooth-cofactor factor, the additional volume is at most O(K_He^{-cH})G_m=o_H(1)G_m. This proves (6.7). All constants used in these estimates are uniform in \theta, since \lambda\le\alpha_\theta<\lambda/\rho and \alpha/\alpha_\theta=1+o_{x\to\infty;H}(1).□

Proof. Apply finite inclusion–exclusion to the union in (6.7), and then use (6.8). For a nonempty subset T of witnesses, write

The series for S_T converges absolutely by (6.5). The finite universe in Lemma 6.3 gives a uniform bound on the number of possible witnesses and their subsets for fixed H; it also makes all the following estimates uniform in phase, even when membership in a witness set changes.

Using B=\alpha m\rho^{-m} and (3.5), we obtain

The omitted geometric tail is O_H(\rho^m\log(2m)). In particular, q_{m,T}=O_H(1/m), and hence

Here we used the uniform scale relation \alpha/\alpha_\theta=1+O(\log m/m) and (m-H)q_{m,T}^2=O_H(1/m). The prefactor satisfies

There are only boundedly many terms for fixed H. Thus the inclusion–exclusion expression differs from A_H(f;\theta(x)) in (2.8) by o_{x\to\infty;H}(1), uniformly in phase; no witness multiplicity has been introduced. Together with Lemma 6.4, this proves (6.11).

Nonnegativity follows from the finite-union probability interpretation in (2.7): both the union probabilities and the outer weights are nonnegative.□

Proof. By Proposition 6.5,

Every phase occurs at arbitrarily large real arguments. Indeed,

is continuous and strictly increasing for B>e, and tends to infinity. For any s\in[0,1) solve \psi(B_n)=n+s and put x_n=\exp(\exp B_n). Then m(x_n)=n and \theta(x_n)=s exactly. Comparing indices H and K along this same sequence gives

This bound is independent of s, so the functions form a uniformly Cauchy sequence. In particular, \sup_s|A_H(f;s)-A(f;s)|\le\zeta_H. Combining this inequality with the preceding limsup bound and then sending H to infinity proves (6.14). If C_f lies between c_- and c_+, apply those bounds on each exact-phase sequence and let H grow to obtain the asserted bounds for A. No continuity in the phase was used.□

Proof of Theorem 2.1. Set

Proposition 6.1 with t=x supplies (6.13). Lemma 6.6 therefore proves uniform existence of A(1;s) and C_1(x)=A(1;\theta(x))+o(1). Ford’s two-sided estimate (3.4) supplies positive absolute constants c_-,c_+ bounding C_1. The same lemma gives

The additive approximation is consequently equivalent to

The coefficient in this formula was defined by the finite arithmetic expressions (2.8); the count V has been used to establish their convergence and bounds, not to define them.

Corollary 6.2 supplies the remaining assertion of the theorem for every c>0.□

Proof. Proposition 5.3 allows us, with an error of (\epsilon_H+o_{x\to\infty;H}(1))xG_m/\log x, to count tuples (p_0,\ldots,p_R,d) satisfying

Both the exceptional values and the tuples above them are controlled there. This use of the least-preimage identity requires that every preimage have the same prefix. The identity would not follow from the existence of a single basic witness.

Fix the remaining data (d,p_1,\ldots,p_R), and put

Here r\geq1. Set T=x/D and U=x/A=Tq/r. The admissible largest primes satisfy exactly

Once the lower bound for p_0 holds, the basic-witness restrictions on the remaining data do not change with p_0; recall that their zeroth simplex coordinate is B.

Ignoring the lower cutoff and replacing T+1 by T, the interval has length

The replacement changes its length by at most one. Moreover, z\mapsto f_k(1/z) is (k+1)-Lipschitz on [0,1], where its value at zero is zero. Consequently

For fixed H, the deterministic size bounds in (3.11) give T=x^{1-o(1)} uniformly in the remaining data. The tail has a witness w bounded in terms of H only, so \ell(d)\leq w bounds r in terms of H. The prime bands bound q away from zero. Hence U=x^{1-o(1)} uniformly as well, and kU>x^{0.9} for all sufficiently large x. The lower cutoff in (7.2) is then inactive.

Apply the prime number theorem at its two endpoints, taking the positive part of the difference if the interval is empty. Each nonzero endpoint is x^{1-o(1)}, and each is O_k(T). Thus this gives, uniformly in the remaining data,

The shift by one is included in the last error. This is an additive estimate relative to T/\log x, obtained from the ordinary prime number theorem; no relative estimate on a short prime interval is required.

The geometric separation of the bands implies

Indeed b_{i-1}/b_i\geq\rho^{-1}, and p_i\geq\exp\exp(c b_i); the resulting reciprocal series is bounded by a constant times its smallest-scale bound. In particular, this estimate is uniform in the growing number R of primes. Since M_1\ll K_HG_m and K_H=H^{o(1)}, summing the displayed prime count gives an error bounded by

Together with the tuple-to-value error this proves (7.1).□

Proof. Use the construction in the proof of Theorem 2 of [7, Section 5, pp. 24–26, Equations (5.10)–(5.19)]. For the fixed seed d, Ford constructs a set \mathcal B and excludes at most half its members. For each remaining b, every preimage of d\varphi(b) is one of the products bd_i. The paragraph following Equation (5.18) also proves that these members give distinct totients. The concluding bound on p. 26 is \lvert\mathcal B\rvert/2\gg_\varepsilon d^{-1-\varepsilon}V(x) for sufficiently large x. This full-fiber conclusion is recorded explicitly in [7, Section 7.3, p. 39]. Finally,

□

Proof. Choose one sufficiently large fixed cut H_0 in Proposition 3.3, so that its exceptional set has at most \varepsilon V(x) members for all sufficiently large x. Every remaining value has a basic witness n=p_0\cdots p_{R_0}w, where R_0=m-H_0, w<p_{R_0}, and w is bounded in terms of H_0 only. The prefix primes are distinct, and their bands give a uniform bound for \prod_{i=0}^{R_0}p_i/(p_i-1). Therefore

The last bound is independent of x, as required.□