The Binary Totient Series

Proposition 6.16 (The prefix-tail identity). For every $N\in \mathbb{N}$,

Thus $R_N$ and $2^{N}S$ have the same fractional part. Subtracting the identities at $N+h$ and $N$ gives the tail-difference congruence used in the irrationality criterion.

Proposition 6.18 (A certificate implies nonintegrality). For all $h,N,L\in \mathbb{N}$,

The scaled truncation error satisfies $|2^L(R_{N+h}-R_N)-D(h,N,L)|\le N+h+L+2$. If the tail difference were integral, $D(h,N,L)$ would therefore lie within that distance of a multiple of $2^L$, contrary to the two strict residue inequalities.

Proposition 6.21 (The Farey gap lemma). Let $a,b,c,d,r,s\in \mathbb{Z}$, with $b,d>0$ and $bc-ad=1$. If

then $b+d\le s$. The two cross-products $rb-as$ and $cs-rd$ are positive integers, and

In particular, a rational $r/s$ strictly between the Farey neighbours $a/b$ and $c/d$, with positive denominator, has denominator at least $b+d$.

Proposition 6.22 (An irrationality criterion from rational approximations). Let $x\in \mathbb{R}$ and let $u_k=p_k/q_k\in \mathbb{Q}$ be in lowest terms, with $q_k>0$. If $u_k\ne x$ for every sufficiently large $k$ and $q_k|x-u_k|\to 0$, then $x$ is irrational. Indeed, if $x=a/b$ with $a\in \mathbb{Z}$ and $b\ge 1$, a nonzero integer numerator gives $q_k|x-u_k|=|a{q}_k-b{p}_k|/b\ge 1/b$, a contradiction. This elementary criterion requires both nonvanishing and the scaled error estimate. Convergence $u_k\to x$ alone is insufficient, and the approximants need not be continued-fraction convergents.

Proposition 6.23 (An irrationality criterion from near integers). Let $\xi \in \mathbb{R}$. Suppose that for every integer $q\ge 1$ there are integers $m,z$ with

Then $\xi$ is irrational: if $\xi =a/b$ with $b\ge 1$, every nonzero such difference is at least $1/b$. Restricting the multiplier to powers $m=b_0^n$ of a fixed integer base $b_0\ge 2$ gives a sufficient special case, not a hypothesis satisfied by every irrational number. The strict lower bound excludes exact integer hits; the upper bound must be available for arbitrarily large $q$.

For a binary example, form a number by concatenating the blocks $10$ at square indices $k\ge 1$ and $01$ at the other indices. Its binary expansion is not eventually periodic, since the block sequence has increasingly long gaps between the square indices, so the number is irrational. There are no three consecutive equal digits. Every fractional part after a binary shift therefore lies in $[1/8,7/8]$, and the multiples $2^n\xi$ do not approach the integers. This verifies that the restriction to base powers is genuinely stronger. This example is an ordinary mathematical argument, not an additional claim about the linked formalisation.

Proposition 6.24 (A nonsingular evaluation matrix gives independence). Let $I$ be a finite index set and let $f_j:\mathbb{N}\to \mathbb{Q}$ for $j\in I$. If there are evaluation points $n_i\in \mathbb{N}$ such that

then the family $(f_j{)}_{j\in I}$ is linearly independent over $\mathbb{Q}$. A relation among the functions, evaluated at the $n_i$, gives a vector in the kernel of this nonsingular matrix, so all coefficients vanish. Finiteness is required to form the displayed determinant. In the totient application the arithmetic work is to construct these evaluation points; the implication itself is ordinary linear algebra.

Proposition 6.25 (The gap between distinct rational numbers). If $a/b<c/d$ are reduced rational numbers with $b,d>0$, then

The numerator $bc-ad$ is a positive integer. Thus an upper bound on a positive rational error gives a lower bound on the product of the reduced denominators. A large denominator in an unreduced displayed expression need not be the reduced denominator appearing in this conclusion.

Proposition 6.26 (The Möbius identity for $S$). The absolutely convergent series satisfy

For the first rearrangement use $\phi (n)=\sum _{d\mid n}\mu (d)n/d$. For the second use $2^d=(2^d-1)+1$ and the classical identity $\sum _{d\ge 1}\mu (d)/(2^d-1)=1/2$. These are identities of values, not transfers of irrationality from a Lambert series with a different weight.

Proposition 6.28 (The squared-Lambert identity). Let $w:\mathbb{N}\to \mathbb{R}$ satisfy $|w(d)|\le d$ for $d\ge 1$, and let $0\le r<1$. Then

Expand $(x/(1-x){)}^2=\sum _{j\ge 1}(j-1)x^j$ and group terms by $n=dj$. Absolute convergence follows from the bound on $w$ and geometric decay. The cases $w=\mu$, $w=1$ and $w=\phi$ give the next three series; the same algebra applies to each, but their arithmetic values differ.

Proposition 6.30 (Weight one and divisor sums). $\sum _{d:{\mathbb{N}}^{+}}^{\prime }1/(2^d-1{)}^2=\sum _{n:{\mathbb{N}}^{+}}^{\prime }(\sigma (n)-\tau (n))\cdot (1/2{)}^n={\zeta }_q(2)-{\zeta }_q(1)$ at $q=1/2$. The displayed identity is formalised. Irrationality of its value follows from the cited linear independence result of Postelmans and Van Assche, as explained in Proposition 5.17; that literature result is not formalised here. Replacing the weight $1$ by $\mu$ changes the value to that of Definition 6.29. Observation 6.32 compares the two choices of weight.

Proposition 6.31 (Totient weight and gcd moments).

where $P=\phi \ast \mathrm{Id}$ (Pillai’s gcd-sum function). It also equals $\mathbb{E}[gcd(X,Y)]$ when $X,Y$ are independent and $\mathbb{P}(X=n)=\mathbb{P}(Y=n)=2^{-n}$ for $n\ge 1$; see Proposition 5.18. This is a different weighted series. Its rationality is not settled by the identities proved here.

Proposition 6.33 (The weight of pairs divisible by a fixed integer). Let $X,Y$ be independent random variables with $\mathbb{P}(X=n)=\mathbb{P}(Y=n)=2^{-n}$ for $n\ge 1$. For every $d\ge 1$,

This follows by multiplying the two geometric sums $\sum _{k\ge 1}{2}^{-dk}=1/(2^d-1)$. It explains the squared denominator in the preceding Möbius identity.

Proposition 6.34 (The sum over coprime directions). The sum over positive coprime pairs satisfies

To see the normalisation, write every pair of positive integers uniquely as $(ka,kb)$ with $gcd(a,b)=1$, and sum $2^{-k(a+b)}$ over $k\ge 1$. The total is $(\sum _{n\ge 1}{2}^{-n}{)}^2=1$. This base-two normalisation is used in Proposition 6.35.

Proposition 6.35 (A Stern–Brocot recursion with stopping). For positive integers $a,b$, put

Then

Multiplication by the common denominator proves the identity. At the root $(1,1)$, the three terms on the right are each $1/3$, and $M(1,1)=1$.

The first term is a mass retained at the current node, not passed to either child. Thus the probabilistic interpretation is a branching process with stopping: after division by $M(a,b)$, the stopping and two transition probabilities are, respectively,

They sum to one. The stopping probability is at least $1/3$, which gives the next proposition’s geometric error bound. Also $M(a,b)=\mathbb{P}(a\mid X)\mathbb{P}(b\mid Y)$ for the independent geometric variables used above. The identity does not describe a conservative mass split between the two children alone.

Proposition 6.36 (Convergence with an explicit error). In the splitting identity of Proposition 6.35, the sum of the two child terms is at most $2/3$ of the parent term. If $M_d(a,b)$ is the sum of the contributions removed during the first $d$ levels, then

In particular, $M_d(a,b)\to M(a,b)$. This convergence statement is separate from identifying the limit with a sum over any independently defined infinite set of descendants; no additional identification is asserted here.

Proposition 6.37 (A numerator polynomial and its coefficients). For squarefree $r\ge 1$, the polynomial defined above has coefficients

For $k<r$, extracting the coefficient gives $\sum _{d\mid gcd(r,k)}\mu (d)r/d$; the usual divisor formula for $\phi$ evaluates this sum. All coefficients in the range $0\le k<r$ are positive. Thus a signed sum of geometric polynomials has an explicit positive-coefficient expression. The squarefree hypothesis is retained as in the cited formal statements.

Proposition 6.38 (Evaluation at two). For squarefree $r\ge 1$, evaluation of $P_r$ at two gives the integer

Each quotient is an integer because $d\mid r$. The formal definition sums over subsets of the prime divisors of $r$; for squarefree $r$ these are exactly its divisors. This identifies the polynomial calculation with the numerator used in $b_r$.

Proposition 6.39 (Decomposition by the radical). For $H\ge 1$ and $r\ge 1$,

The first equality follows from the definition of ${\beta }_H$; the second is ordinary reduction of an integer fraction. Multiplication by $H/\mathrm{rad}(H)$ can cause further cancellation. No coprimality assumption is included in either identity.

Proposition 6.40 (A cyclotomic congruence). Let $r$ be squarefree and $m\mid r$. In $\mathbb{Z}[X]$,

where $J_2(n)=n^2\prod _{p\mid n}(1-p^{-2})$ is the second Jordan totient. Evaluation at two gives

Proposition 6.41 (Adjoining a prime: new divisors). Let $r\ge 1$, let $p\nmid r$ be prime, and let $m\mid r$. Then

Proposition 6.42 (Adjoining a prime: existing divisors). Let $r$ be squarefree, let $p\nmid r$ be prime, and let $m\mid r$. For the existing divisors $m$, the corresponding identity is

Proposition 6.43 (Lambert-series identities). For an arithmetic function $f$ for which the sums converge absolutely, write $L(f)=\sum _{n\ge 1}f(n)/(2^n-1)$. Expanding each geometric series gives

In particular, if $\alpha =\phi \ast \mu$, then $\alpha \ast 1=\phi$ and $L(\alpha )=S$. The table distinguishes this value from four other Lambert-series values. The identity changes the coefficients and the form of the denominator; it does not transfer an irrationality theorem for one weight to another.

Proposition 6.45 (An affine combination annihilates the specified divisor terms). Let $H\ge 1$ and $d\mid H$, with $d>0$. The $d$th term in the Möbius expansion of $R_{mH}$ is $\mu (d)K_d(mH)$, where

This is affine in $m$. Consequently, for any finite family of real coefficients $c_i$ and nonnegative integers $m_i$ with $\sum _i{c}_i=\sum _i{c}_i{m}_i=0$, one has $\sum _i{c}_i{K}_d(m_{i}H)=0$.

For the four multipliers $(1,3,5,15)$ and coefficients $(4,-3,-2,1)$,

The zeroth and first moments are zero, while the second is ${15}^2-3\cdot 3^2-2\cdot 5^2+4=152$. Equivalently, $XY-3X-2Y+4$ takes the values $0,0,152$ at $(1,1),(3,5),(9,25)$. This explains the coefficients: they cancel the affine contribution of each divisor of $H$, without cancelling a general quadratic function of the multiplier.

For a finite truncation of depth $L\ge 0$, write

The difference between $2^L(R_{15H}-3R_{3H}-2R_{5H}+4R_H)$ and $U$ has absolute value at most $19H+5L+5$. Indeed, the error equals

and both parenthesised terms lie between $0$ and $19H+5L+5$ by $0\le R_n\le n+1$ for $n\ge 1$. Thus

is sufficient for this four-tail combination to be nonintegral. The bound is derived from these tail enclosures; no optimality for the actual totient tails is asserted. Obtaining such certificates at the required unbounded family of LCM heights remains unproved, as in Theorems 6.60 and 6.52.

Proposition 6.46 (The error under composite dilation). For $A\subseteq \mathbb{N}$ and $n\ge 1$, let $d_A(n)=\mathrm{\#}\{d\ge 1:d\mid n,d\in A\}$. If $a\in A$ and $a,x\ge 1$, then

Indeed, partition the divisors of $ax$ into those already dividing $x$, the possible new divisor $a$, and all other new divisors. If every element of $A$ is prime, the last set is empty, since a prime dividing $ax$ but not $x$ must equal the prime $a$. For composite $a$ it can be nonempty: at $A=\mathbb{N}$, $a=6$, $x=1$, the other new divisors are $2$ and $3$.

This is an unweighted counting identity. The associated Lambert series satisfies

For the totient series the required divisor-convolution weight is instead $\alpha =\phi \ast \mu$, since $\alpha \ast 1=\phi$, as in Proposition 6.43. Weighting all divisors by $\phi$ would give $\sum _{d\mid n}\phi (d)=n$, not $\phi (n)$; already at $n=2$ these values are $2$ and $1$. A weighted version must retain the weights of the new divisors, so it cannot be obtained by substituting $A=\mathbb{N}$ in this unweighted formula. Also $\alpha (p)=p-2$ for primes $p$, so $\alpha$ is unbounded and is not a periodic weight.