The Binary Totient Series

Proposition 6.78 (The exact totient difference on an LCM progression). Put $H=H(t)$. For every $j\ge 0$, the arithmetic expression in the piecewise form given below equals ${\delta }_t(j)=\phi (2H+j)-\phi (H+j)$. For a divisor $j\mid H$, this assertion contains a useful product formula, not merely a change of notation. Set

Then

Here $j\ge 1$ because $H>0$, so both denominators are nonzero. The identity follows from $\phi (jx)=\phi (j)\phi (x)gcd(j,x)/\phi (gcd(j,x))$, which retains all primes shared by $j$ and $x$. If every prime dividing $j$ also divides $a$, then $g_1=g_2=1$, and the formula reduces to $\phi (j)(\phi (2a+1)-\phi (a+1))$. For example, at $H=j=2$ the two gcds are $g_1=2$ and $g_2=1$; the exact difference is $\phi (6)-\phi (4)=0$, whereas discarding the gcd factors would give $1$. For $j\nmid H$, that expression is the literal totient difference. Thus no coprimality assumption is imposed on the full expression.

Proposition 6.79 (A lower bound for the totient of a rough integer). Let $a\ge 8$, set $t=2^a$, and let $n>0$ be an integer all of whose prime factors exceed $t$. If $n<2^{2t}$, then $n$ has fewer than $t/4$ distinct prime factors and

If $n$ has $r$ distinct prime factors, then $n\ge t^r=2^{ar}$, so $ar<2t$ and $r<t/4$ because $a\ge 8$. For the second, use $\phi (n)/n=\prod _{p\mid n}(1-1/p)\ge 1-\sum _{p\mid n}1/p>3/4$. These are bounds for rough integers in the stated size range; they are not pointwise bounds for arbitrary totient values.

Proposition 6.80 (Positivity of the short-window differences). For $a\ge 8$ and $1\le j<2\cdot 2^a$,

The proof treats divisor offsets and the exceptional prime-power offsets separately, using multiplicativity and the rough-integer estimate of Proposition 6.79. No rationality hypothesis is used. Positivity of these finitely many coefficients contributes to the later sign theorem; a bound for the remaining infinite tail is still needed to obtain that theorem.

Proposition 6.81 (The accumulated sum is the discrepancy). For all $t,L\in \mathbb{N}$, the weighted diagonal sum is exactly

Thus its two-sided residue inequality is precisely $\mathcal{C}(H(t),H(t),L)$. The equality follows term by term from the definition of ${\delta }_t$. A separate restriction on $L$, when present, remains part of the hypothesis; this identity does not supply such a restricted-depth witness.

Proposition 6.82 (A global-to-local identity).

Thus a separation estimate for ${\mathrm{\Omega }}_a$ is an estimate for this integer translate of a multiple of $S$. The identity does not require other rational-approximation arguments to use this particular translate.

Proposition 6.83 (A rational approximation with an error bound). For all $a,q\in \mathbb{N}$, with $H=H_{2^a}$ and the finite ${\rho }_{a,q}$ defined above,

The triangle inequality transfers a separation estimate between the real tail and its rational approximation at the cost of this error. The bound tends to zero with $q$ for fixed $a$; no assertion of optimality is made.

Proposition 6.84 (Unconditional positivity). For $a\ge 8$, $J+(a+6)<2\cdot 2^a$:

with no irrationality hypothesis; the true, infinite, real translated tail difference is strictly positive throughout almost the entire short window, proved unconditionally from Prop. 6.80 plus a directed one-sided tail bound. Any argument about the sign of the actual orbit (not merely its residue mod $2^L$) must agree with this; specialised at $J=0$ this gives $0<{\mathrm{\Omega }}_a$.

Proposition 6.85 (The residue forced by integrality). Let $a,J,K\in \mathbb{N}$, $a\ge 8$, $H=H(2^a)$, and assume

If $R_{2H+J}-R_{H+J}\in \mathbb{Z}$, then

The later tail difference is a positive integer. Its negative is the representative near zero, while the least nonnegative residue lies near $2^K$. Positivity alone therefore does not prove nonintegrality; a separate estimate must exclude this upper interval.

Proposition 6.86 (The penultimate term of a partial divisibility pattern). Let $a,J,K,m\in \mathbb{N}$, $a\ge 8$, $H=H_{2^a}$ and $B=2H+J+K+2$. Suppose that

Then

Indeed, $B\ge 4$ and $B<2^m$ force $m\ge 3$. The penultimate divisibility, positivity, and the bound ${\delta }_{2^a}(J+K-1)<B<2^m$ leave $2^{m-1}$ as its only possible value. Thus the modulus lies in the strict interval $B<2^m<2B$; there is at most one possible power of two. The value fixed at $2^{m-1}$ is the penultimate difference. The terminal difference ${\delta }_{2^a}(J+K)$ instead satisfies the separate upper bound in the hypotheses. These restrictions are necessary for the specified pattern; the proposition does not construct such patterns at arbitrarily large $a$.

Proposition 6.87 (An equivalent test using two residue bits). For every $h,N\in \mathbb{N}$, existence of a certificate at some depth is equivalent to the following explicit condition:

The last interval says that the two leading bits are $01$ or $10$. The proof uses the first successful certificate of depth $L$ and may take $b=\lfloor {\log }_2(N+h+L+2)\rfloor +1$. Since $b$ depends on that unknown $L$, the equivalence is not an a priori bound on the search depth. The proof uses the finite tail recurrence and its size bound; it supplies no totient-specific assertion that a witness exists.

Proposition 6.88 (The factor in a second difference). Let $a\ge 4$ and $j\ge 1$ be integers with $j^2\le 2^a$, and put $H_a=H(2^a)=\mathrm{lcm}(1,\dots ,2^a)$. Then

To see the factor, set $A=H_a/j$. The square bound ensures that $j\mid H_a$ and that every prime divisor $p$ of $j$ also divides $A$: indeed, $pj\le j^2\le 2^a$ implies $pj\mid H_a$. Consequently $gcd(j,qA+1)=1$ for $q=1,2,3$, and the displayed difference equals

Also $2j\le 2^a$, so $2j\mid H_a$ and $A\ge 2$ is even. The three arguments $qA+1$ are therefore odd and greater than two, and all three totients are even. This proves the extra factor of two. The divisibility is a lower bound, not an exact valuation at each LCM height. The different family in Observation 6.108 does not satisfy these LCM and square-window hypotheses, so it does not establish sharpness within this restricted family.

Proposition 6.89 (Carry displacement and tail integrality). For a positive integer $v$ and an integral totient carry $u$ with $u(N)/2^N\to 0$,

The recurrence and the limit identify $u(N)=v{R}_N$, so the difference is $v(R_{N+k}-R_N)$. This tests divisibility of a carry difference and gives no dimension bound for the carry sections. For another coefficient sequence, the same argument applies once its carry is identified with its scaled tail under the corresponding recurrence and limit.

Proposition 6.90 (A consequence of rationality and its limitation). If $S\in \mathbb{Q}$, there are a positive integer $v$ and an integer carry sequence $u$, with $u(N)/2^N\to 0$, whose retained sections through every level $e$ have rational rank at least $2^e-1$. At the same time, those sections are uniformly eventually periodic modulo $v$. Periodicity after reduction modulo $v$ is a statement in a finite quotient; it is not a rank upper bound over $\mathbb{Q}$. Proposition 6.76 gives the lower bound, while the rational comparison sequence explains why a general rank upper bound cannot be deduced from these recurrence assumptions alone.

Proposition 6.91 (A totient difference congruent to two modulo four). For every positive integer $h$ and every $B\in \mathbb{N}$, there is a prime $p>B$ such that

To construct $p$, set $H=4h$, choose a prime $r>H$ with $r\equiv 1(\mathrm{mod}4)$, and use Dirichlet’s theorem in the progression $p\equiv 3r-H(\mathrm{mod}4r)$. This progression is reduced: its residue is odd and is $-H\not\equiv 0(\mathrm{mod}r)$. Then $p\equiv 3(\mathrm{mod}4)$, so $\phi (p)=p-1\equiv 2(\mathrm{mod}4)$, whereas $r\mid p+H$ gives $4\mid \phi (p+H)$. Subtracting gives the stated congruence. This supplies the arithmetic congruence at arbitrarily large primes; the additional finite exclusion in Proposition 6.70 remains a separate hypothesis.

Proposition 6.92 (A prescribed residue after a long divisibility block). Let $K\ge 2$ and $H>K$ be integers. For every $B\in \mathbb{N}$ there is a prime $p>max(B,H+K)$ such that

The construction uses $2K-1$ distinct auxiliary primes congruent to $1(\mathrm{mod}{2}^K)$: one for $p+H$, and two for each of the $K-1$ preceding positions. Choose them larger than $max(H+K,2^K)$. For the first prime impose $p\equiv -H$; for the pair at position $j$ impose $p\equiv j$ and $p\equiv j-H$, respectively. These nonzero residues, together with the displayed odd residue modulo $2^K$, combine by the Chinese remainder theorem into a reduced progression. Dirichlet’s theorem then supplies arbitrarily large prime values of $p$. Each auxiliary prime contributes the required factor $2^K$ to the corresponding totient.

Thus the first $K-1$ totient differences in the window starting at $p-K$ vanish modulo $2^K$, while the last is $2^{K-1}$ modulo $2^K$. Consequently

If $R_{N+H}-R_N\in \mathbb{Z}$ for every $N\ge N_0$, choose such a prime with $p\ge N_0+K$. Iterating the carry recurrence from $p-K$ then gives

The initial integer is multiplied by $2^K$ and disappears only after reduction modulo $2^K$. This does not bound its higher quotient. The condition $H>K$ is part of the construction; it does not provide arbitrarily large $K$ for one fixed shift $H$.

Proposition 6.93 (A Möbius-inversion formula for the tail).

For $N\in \mathbb{N}$ and $d\ge 1$, let $r_d(N)=d-(Nmodd)$ and $q_d(N)=\lfloor N/d\rfloor +1$. Thus $r_d(N)$ is the distance to the next strictly larger multiple of $d$, so $1\le r_d(N)\le d$. Möbius inversion gives

Indeed, substitute $\phi (n)=\sum _{d\mid n}\mu (d)n/d$ and group by $d$. Its multiples after $N$ have quotients $q_d(N)+\ell$ and forward distances $r_d(N)+d\ell$, for $\ell \ge 0$; summing the two geometric series gives the formula. Absolute convergence justifies the regrouping, since the sum of the absolute divisor contributions at $n$ is at most $\sum _{d\mid n}n/d\le n^2$, and $\sum _{n>N}{n}^2{2}^{N-n}<\mathrm{\infty }$. This identity is available for later transformations; it does not assert that every Möbius or Lambert-series argument must use it.

Proposition 6.94 (Explicit finite examples). The finite certificates $\mathcal{C}(H_{16},H_{16},23)$ and $\mathcal{C}(H_{64},H_{64},93)$ imply ${\mathrm{\Omega }}_4,{\mathrm{\Omega }}_6\notin \mathbb{Z}$. Both satisfy the short-window restriction, since $23<32$ and $93<128$. They are the certificates at $t=16$ and $t=64$ in the diagonal table of Section 5.7. These are two explicit instances of the desired condition, not the start of a proved induction or a claim that no other finite instances can be checked.

Proposition 6.95 (The necessary depth). Every certificate $\mathcal{C}(h,N,L)$ satisfies

The two endpoint margins must fit inside an interval of length $2^L$. In particular, successful depths grow at least logarithmically with $N+h$. This is a necessary lower bound, not an upper bound for the first successful depth. The later two-bit reformulation applies at its stated modulus and does not reverse this implication.

Proposition 6.96 (Rationality gives an eventual tail period). Suppose $S=a/(2^{c}v)$ in lowest terms, where $a\in \mathbb{Z}$, $c\ge 0$ and $v\ge 1$ is odd. Take $h=\phi (v)$, including $h=1$ when $v=1$. Euler’s theorem gives $v\mid 2^h-1$, so

The identity relating $S$ to its scaled tails therefore gives $R_{N+h}-R_N\in \mathbb{Z}$ for every $N\ge c$. These are explicit witnesses for the eventual period asserted in Proposition 6.71. To use the finite residue test against a hypothetical rational value, one must obtain a nonintegral difference for its period at an index beyond its preperiod. Soundness proves that the quantified certificate condition rules out rationality. Conversely, the prefix-tail identity makes every positive-shift tail difference nonintegral when $S$ is irrational, and pointwise completeness (Theorem 6.19) then supplies a depth. Proposition 6.81 only identifies the weighted diagonal sum with $D$; it is not the completeness argument and supplies no depth bound.

Proposition 6.97 (Tail integrality on an LCM grid). If $S\in \mathbb{Q}$, there is $t_1\in \mathbb{N}$ such that for all $t\ge t_1$, $q\ge 1$ and $m\ge 0$,

The threshold may depend on the hypothetical rational value. A certificate at one fixed scale therefore gives a finite denominator exclusion, not irrationality. Proposition 6.73 requires certificates at arbitrarily large scales, so that one lies beyond the threshold supplied by any such rational value.

Proposition 6.98 (Independence of the retained dyadic family). For every $e\ge 0$, the auxiliary canonical dyadic family has $2^e+1$ indexed sections, and these sections are linearly independent over $\mathbb{Q}$. The CRT–Dirichlet argument is explained in Section 10.8. For $e\ge 1$ the family is a basis for all sections through level $e$. At $e=0$ the auxiliary family still contains both $\phi (n)$ and $\phi (2n)$, so it is not the actual level-zero truncation, whose dimension is one. No rationality hypothesis on $S$ is used.

Proposition 6.99 (The exact range of the stated Farey-gap inequality). Let $V$ be the totient residue at $(N,K)=(1,240)$ defined in Section 5.3. For every integer $q$ satisfying

one has

The first failure occurs at

obtained from the stated Farey mediant. Thus the range is exact for this particular inequality. It is not an optimality claim among all denominator-exclusion tests. The preceding range gives the exclusion in Proposition 6.100, approximately $7.96\times {10}^{34}$.

Proposition 6.100 (The resulting denominator exclusion). For every reduced fraction $a/q$, with $a\in \mathbb{Z}$ and $q\ge 1$,

This is an unconditional finite denominator exclusion. It does not assume certificates at arbitrarily large scales, as required by Proposition 6.71. Conversely, excluding this finite range does not rule out rational values with larger reduced denominators.

Proposition 6.101 (Two general irrationality criteria). Let $x\in \mathbb{R}$. One sufficient condition is a sequence of reduced fractions $u_j=a_j/q_j$, $q_j\ge 1$, with $u_j\ne x$ for all sufficiently large $j$ and

Another is that, for every integer $Q\ge 1$, there exist $m,z\in \mathbb{Z}$ such that

Indeed, if $x=a/b$ is reduced with $b>0$, every nonzero error in the first condition is at least $1/(b{q}_j)$, and every nonzero error in the second is at least $1/b$. The strict lower bounds exclude exact rational hits. Requiring $m=b_0^n$ for a fixed integer base $b_0\ge 2$ is a stronger sufficient condition, not a reformulation valid for every irrational number. The binary example in Proposition 6.23 explains this distinction.

Proposition 6.102 (Lambert identities involving $S$). For $L(f)=\sum _{n\ge 1}f(n)/(2^n-1)$, the identities are $L(\mu )=1/2$, $L(\phi )=2$, $L(1)=E$ and $L(\phi \ast \mu )=S$. The last identity rewrites the same unknown value; it does not deduce its irrationality from that of $E$. The value $L(\mathrm{Id})=\sum _{m\ge 1}\sigma (m)/2^m$ is transcendental by Nesterenko [13]. These examples show that Lambert-series form alone does not determine arithmetic status. The individual comparisons are in Proposition 6.43 and its table.

Proposition 6.103 (A general rational gap bound). If $a/b<c/d$ are reduced fractions with $b,d>0$, then

since $bc-ad$ is a positive integer. In particular, if $S=a/b$ and $p_N/q_N<S$ is a reduced rational approximation with positive error at most ${\epsilon }_N$, then

These lower bounds tend to infinity precisely when $q_N{\epsilon }_N\to 0$; a subsequence with this property is enough to contradict a fixed $b$. A tail bound by itself does not imply this. For example, the ordinary dyadic prefix has denominator dividing $2^N$ and tail at most $(N+2)2^{-N}$. Using only these two bounds yields $b\ge 1/(N+2)$, which is vacuous. The rational-spacing lemma can convert sharper error and denominator information into an exclusion; it does not automatically improve the Farey bound in Proposition 6.99.

Proposition 6.104 (Diagonal certificates through $82$). The current aggregate establishes

where $Pt$ is the diagonal certificate predicate in Proposition 6.72. The earlier aggregate covered 28 explicit cases through $64$, including $1,2,3,4,5,7,8,9,11,13,16,17$; the later theorem fills the gaps and extends the range through $82$. Each instance reduces to exact finite arithmetic with the displayed totient values, using the prime-power factorisations and Lucas primality certificates in the source. This proves neither $P83$ nor infinitely many instances, and therefore does not establish the quantified conditions in Propositions 6.71, 6.72 and 6.73.

Proposition 6.105 (A coprime-pair expression for $S$). For $n\ge 0$, the number of integer pairs $a\ge 1$, $b\ge 0$ with $a+b=n$ and $gcd(a,b)=1$ is $\phi (n)$, with $\phi (0)=0$. Indeed, $b=n-a$ and $gcd(a,n-a)=gcd(a,n)$. The boundary case $n=1$ contributes $(a,b)=(1,0)$; it disappears when both coordinates are required to be positive. Consequently,

For independent random variables $X,Y$ with $Pr(X=n)=Pr(Y=n)=2^{-n}$, $n\ge 1$, the left side is $Pr(gcd(X,Y)=1)$. Thus $S-1/2$ has a coprimality-probability interpretation. This identity does not supply an estimate for the binary digits or tail residues used elsewhere in the paper.