Integral Relations among Totient Sections

Will Cook

Introduction

Splitting the totient sequence into its even and odd subsequences, then splitting once more, gives seven sequences:

φ (n); φ (2 n), φ (2 n + 1); φ (4 n), φ (4 n + 1), φ (4 n + 2), φ (4 n + 3) .

The identities

φ (4 n) = 2 φ (2 n), φ (4 n + 2) = φ (2 n + 1)

leave five independent sequences. Thus every identity among the seven comes from these two substitutions. More precisely, an integral relation is a unique integral combination of the two displayed relations. We will prove the same statement at every depth and in every integer base.

For an integer $k \geq 2$ , the totient sections are the sequences $n \mapsto φ (k^{j} n + r)$ , where $j \geq 0$ and $0 \leq r < k^{j}$ . Throughout, $n$ ranges over $N = {0, 1, 2, \dots}$ and $φ (0) = 0$ . To describe relations we retain a separate index for each pair $(j, r)$ , even when two pairs give the same sequence. For example, $φ (4 n + 2)$ and $φ (2 n + 1)$ are equal sequences but occupy different positions in the list above.

The sections form the $k$ -kernel of the totient sequence. A sequence is $k$ -regular when the $Z$ -module generated by its $k$ -kernel is finitely generated [1]. Coons proved that the totient sequence is not $k$ -regular for any $k \geq 2$ [2]. Here we determine those modules at each finite level, including their integral relations. The theorem gives the basis and the substitutions; Corollary 3.1 explains how to recover every relation from them. Level zero contains only $φ (n)$ and has dimension one.

Theorem 1.1 (A basis through each finite level). Let $k \geq 2$ and $e \geq 1$ be integers, write $F_{j, r}^{(k)} (n) = φ (k^{j} n + r)$ , and put

V_{k, e} = {span}_{Q} {F_{j, r}^{(k)} : 0 \leq j \leq e, 0 \leq r < k^{j}} .

Then $\dim_{Q} V_{k, e} = k^{e} + 1$ , and

B_{k, e} = {F_{0, 0}^{(k)}, F_{1, 0}^{(k)}} \cup {F_{j, r}^{(k)} : 1 \leq j \leq e, 1 \leq r < k^{j}, k ∤ r}

is a basis. Every omitted section reduces to a basis element by an explicit scalar: $F_{j, 0}^{(k)} = k^{j - 1} F_{1, 0}^{(k)}$ for $j \geq 1$ , and if $r = k^{t} u$ with $t = max {s : k^{s} ∣ r} \geq 1$ and $k ∤ u$ , then

F_{j, r}^{(k)} = C_{k} (t, u) F_{j - t, u}^{(k)}, C_{k} (t, u) = k^{t} \prod_{\begin{matrix} p ∣ k \\ p ∤ u \end{matrix}} (1 - \frac{1}{p}) .

The condition $k ∤ r$ allows residues with $gcd (k, r) > 1$ . For instance, $r = 1$ and $r = 2$ are both retained in base six, and the reductions involving them are

φ (36 n + 6) = 2 φ (6 n + 1), φ (36 n + 12) = 4 φ (6 n + 2) .

The factor $2$ is already present in $6 n + 2$ but not in $6 n + 1$ ; only newly introduced prime divisors contribute factors $1 - 1 / p$ . Thus one removes whole factors of $k$ from the residue, not every common prime factor. Repeated prime factors of $k$ cause no exception.

Martin’s 2006 theorem on simultaneous totient inequalities already implies independence for every finite family of pairwise nonproportional affine forms with positive integral slopes [4]. Its conclusion is stronger than the independence used here. The point of the present description is the explicit reduction of the sections and the integral relation basis in Corollary 3.1. We also give a direct proof that constructs a nonsingular evaluation matrix. It uses the CRT–Dirichlet separation argument in Yazdani’s proof of Theorem 2, credited there to Shallit [12]. The step that needs care is to keep the progression for the selected affine form reduced while imposing prime divisors on all the others.

The proof in Section 2 separates scalar reduction from independence. Section 3 recovers the integral relations, starting in base six. Section 4 uses prime isolation for bounded functions of totient residues. The series

S = \sum_{n \geq 1} \frac{φ (n)}{2^{n}}

has unbounded coefficients. Its irrationality, asked in Erdős Problem #249 [10], remains open. The coefficient basis supplies no irrationality conclusion for this value. Appendix A gives further coefficient consequences; Appendices B and C collect the tail identities, comparison sequences and still-unproved cancellation estimates relevant to $S$ . Their longer proofs are in The Binary Totient Series.

Proof of the basis theorem

Scalar reductions

The product formula reduces every omitted section to an integer multiple of a retained one. For a zero residue, $k n$ and $k^{j} n$ have the same prime divisors when $n > 0$ . Hence $φ (k^{j} n) = k^{j - 1} φ (k n)$ ; both sides vanish at $n = 0$ . For an omitted positive residue $r = k^{t} u$ with $t \geq 1$ and $k ∤ u$ , we have $t < j$ because $0 < r < k^{j}$ . Put $m = k^{j - t} n + u$ . A prime $p ∣ k$ divides $m$ exactly when it divides $u$ . The product formula for $φ (k^{t} m) / φ (m)$ therefore contributes $k^{t}$ and one factor $1 - 1 / p$ for each prime $p ∣ k$ absent from $u$ . The multiplier is an integer: its denominator is a product of distinct primes dividing $k$ , and therefore divides $k^{t}$ . This gives $C_{k} (t, u)$ and proves that the stated family spans $V_{k, e}$ .

Affine independence

Independence follows from Martin’s theorem. For any ordering of pairwise nonproportional affine forms and any $C > 0$ , it gives a set of positive lower density on which each successive totient ratio exceeds $C$ . In a proposed nonzero relation, place a nonzero coefficient $c_{1}$ first and take $C > max (1, \sum_{i > 1} | c_{i} | / | c_{1} |)$ . The first term then dominates the sum of all remaining terms in absolute value, a contradiction [4]. This also proves independence after any finite prefix is deleted.

The direct proof isolates one column in each evaluation row. Let $L_{i} (n) = a_{i} n + b_{i}$ for $1 \leq i \leq s$ , where $a_{i} > 0$ and $a_{i} b_{j} - a_{j} b_{i} \neq 0$ for $i \neq j$ . Shift $n$ so that all $b_{i}$ are positive; the cross determinants do not change. Write $L_{i} = g_{i} A_{i}$ , where $g_{i} = gcd (a_{i}, b_{i})$ and $A_{i}$ is primitive. We make $A_{i}$ , not $L_{i}$ , prime: $L_{i}$ may have the fixed divisor $g_{i} > 1$ . We seek a prime $ℓ$ and points $n_{1}, \dots, n_{s}$ for which

\begin{matrix} (1) & E = (φ (L_{j} (n_{i})))_{1 \leq i, j \leq s} \equiv (\begin{matrix} φ (g_{1}) & 0 & \dots & 0 \\ 0 & φ (g_{2}) & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & φ (g_{s}) \end{matrix}) (\mod ℓ), ℓ ∤ \prod_{i} φ (g_{i}) . \end{matrix}

Since $det E ≢ 0 (\mod ℓ)$ , $E$ is invertible over $Q$ . A rational relation gives $E c = 0$ , hence $c = 0$ . We now construct the rows.

For $j \neq i$ , a prime divisor $q_{i j} \equiv 1 (\mod ℓ)$ of $L_{j} (n_{i})$ makes $ℓ ∣ q_{i j} - 1 ∣ φ (L_{j} (n_{i}))$ . For the diagonal entry, we instead make $A_{i} (n_{i})$ prime and congruent to $2$ modulo $ℓ$ . Choose an odd $ℓ$ dividing none of the slopes $a_{i}$ , the products $g_{i} φ (g_{i})$ or the nonzero cross determinants. For each fixed $i$ , Dirichlet’s theorem supplies distinct primes $q_{i j} \equiv 1 (\mod ℓ)$ ( $j \neq i$ ) outside the same finite exceptional set. Impose

A_{i} (n) \equiv 2 (\mod ℓ), L_{j} (n) \equiv 0 (\mod q_{i j}) (j \neq i) .

Each congruence is soluble because its slope is coprime to its modulus. CRT combines them into $n = n_{0} + R u$ , where $R = ℓ \prod_{j \neq i} q_{i j}$ .

CRT supplies the congruences, but not yet a prime value. Dirichlet applies to the progression of values of $A_{i}$ , namely

A_{i} (n_{0} + R u) = A_{i} (n_{0}) + (a_{i} / g_{i}) R u .

Its initial value must be coprime to its step. The step has only three kinds of prime factors: those of $a_{i} / g_{i}$ , excluded by primitivity; $ℓ$ , excluded by the residue $2$ ; and the imposed $q_{i j}$ . Such a $q_{i j}$ cannot divide $A_{i} (n_{0})$ : it would then divide both $L_{i} (n_{0})$ and $L_{j} (n_{0})$ , hence

a_{i} L_{j} (n_{0}) - a_{j} L_{i} (n_{0}) = a_{i} b_{j} - a_{j} b_{i},

contrary to its choice. This is where nonproportionality is used: the nonzero cross determinant lets us keep each imposed divisor away from the selected form. We may now choose $p = A_{i} (n_{i})$ prime, as large as needed, and in particular with $p ∤ g_{i}$ . Then

φ (L_{i} (n_{i})) = φ (g_{i}) (p - 1) \equiv φ (g_{i}) ≢ 0 (\mod ℓ),

while all the other entries of row $i$ vanish modulo $ℓ$ . We choose the rows separately, applying Dirichlet’s theorem once more for each selected form $A_{i}$ . Thus no simultaneous primality assertion is required. The construction proves (1) with every $n_{i}$ beyond any prescribed threshold.

The two zero-residue sections

The arguments $n, k n$ are proportional; their totient sequences are not. We first merge their coefficients on $n = k m + 1$ , where $φ (k n) = φ (k) φ (n)$ , then separate them using a different ratio. On this progression the positive-residue sections have arguments

k^{j + 1} m + k^{j} + r (k ∤ r),

together with $k m + 1$ . These are pairwise nonproportional: equality of two intercept-to-slope ratios would give $r / k^{j} = r^{'} / k^{j^{'}}$ , which for $j^{'} > j$ forces $k ∣ r^{'}$ . No positive-residue form is proportional to $k m + 1$ . If $A, B$ multiply $φ (n), φ (k n)$ , affine independence therefore leaves $A + B φ (k) = 0$ and eliminates every other coefficient. At $n = k$ , however, the ratio is $k$ , giving $A + B k = 0$ . Since $φ (k) < k$ , these two equations separate the remaining coefficients: $A = B = 0$ . Finally,

| B_{k, e} | = 2 + \sum_{j = 1}^{e} (k^{j} - k^{j - 1}) = k^{e} + 1,

which completes the proof of Theorem 1.1. For independence on a tail, use a sufficiently large power of $k$ in the last evaluation.

Integral relations

Independence turns identities into coordinate calculations. In base six at level two, the $43$ indexed sections reduce to $37$ retained ones: $F_{0, 0}, F_{1, 0}$ , the five $F_{1, r}$ ( $1 \leq r \leq 5$ ), and the $30$ sections $F_{2, r}$ with $1 \leq r < 36$ and $6 ∤ r$ . The omitted sections satisfy

\begin{aligned} F_{2, 0} & = 6 F_{1, 0}, & F_{2, 6} & = 2 F_{1, 1}, & F_{2, 12} & = 4 F_{1, 2}, \\ F_{2, 18} & = 3 F_{1, 3}, & F_{2, 24} & = 4 F_{1, 4}, & F_{2, 30} & = 2 F_{1, 5} . \end{aligned}

The formal symbols $E_{j, r}$ remain independent even when their sequences $F_{j, r}$ coincide. The substitution $F_{2, 12} = 4 F_{1, 2}$ corresponds to the decomposition

x_{1, 2} E_{1, 2} + x_{2, 12} E_{2, 12} = (x_{1, 2} + 4 x_{2, 12}) E_{1, 2} + x_{2, 12} (E_{2, 12} - 4 E_{1, 2}) .

The retained coefficient becomes $x_{1, 2} + 4 x_{2, 12}$ ; the relation coefficient is the original $x_{2, 12}$ . After all six substitutions, the evaluated sequence vanishes exactly when the $37$ retained coefficients vanish. In that case, the relation coordinates are the six original omitted coefficients. In the opening binary example the relation vectors are $E_{2, 0} - 2 E_{1, 0}$ and $E_{2, 2} - E_{1, 1}$ .

Corollary 3.1 (Integral coordinates and all integral relations). Let $k \geq 2$ and $e \geq 1$ . The retained family is a $Z$ -basis of the module generated by the sections through level $e$ . Index the sections by their level and residue, retaining distinct indices even when they define equal sequences. For each omitted index $i$ , write the scalar reduction as $F_{i} = a_{i} F_{j (i)}$ , where $j (i)$ is retained and $a_{i}$ is a nonnegative integer. In the free abelian group with one generator $E_{i}$ for each of these indices, the vectors

R_{i} = E_{i} - a_{i} E_{j (i)} (i omitted)

form a $Z$ -basis of the kernel of evaluation $E_{i} \mapsto F_{i}$ . In particular, every integral relation has a unique integral expression in these elementary relations, and their rank is $\sum_{j = 1}^{e - 1} k^{j}$ .

Proof. Since $\prod_{p ∣ k, p ∤ u} p$ divides $k$ , every scalar $C_{k} (t, u)$ is an integer. The retained family therefore spans the section module over $Z$ , and its rational independence makes it a $Z$ -basis.

For any vector $x = \sum_{i} x_{i} E_{i}$ , substitute $E_{i} = R_{i} + a_{i} E_{j (i)}$ at each omitted index and collect terms:

x = \sum_{j retained} (x_{j} + \sum_{\begin{matrix} i omitted \\ j (i) = j \end{matrix}} a_{i} x_{i}) E_{j} + \sum_{i omitted} x_{i} R_{i} .

The first sum gives the retained coordinates of the evaluated sequence; the second evaluates to zero. Thus $x$ is a relation exactly when the first sum vanishes, in which case $x = \sum_{i omitted} x_{i} R_{i}$ . This expression is unique: at omitted index $i$ , the coefficient of $\sum_{h} c_{h} R_{h}$ is $c_{i}$ itself. Each substitution has a unit coefficient at its own omitted index, so the entire calculation takes place over $Z$ , without division. Counting omitted indices gives $(1 + k + \dots + k^{e}) - (k^{e} + 1) = \sum_{j = 1}^{e - 1} k^{j}$ . ◻

The section-generated module need not contain every integer-valued sequence in its rational span: for $k = 2$ , $e \geq 2$ , the sequence $φ (4 n + 3) / 2$ is integer-valued but has retained coordinate $1 / 2$ . This failure of saturation concerns the image of evaluation; the integral relation basis describes the kernel.

In the same base-six example, evaluation gives a second test. Order the retained columns as above, with residues increasing within each level, and evaluate at $n = 0, \dots, 36$ to obtain a $37 \times 37$ matrix. Its determinant is $17$ modulo $101$ , so it is nonsingular over $Q$ . Consequently a retained combination is zero if and only if all $37$ of its integer evaluations are zero. Here reduction modulo $101$ certifies the matrix, not the equality of a proposed combination: $101 F_{2, 2}$ would vanish modulo $101$ at every input, although its integer value at $n = 0$ is $101$ . The script scripts/totient_kernel_normal_form.py calculates the coordinates and the first nonzero evaluation using integer arithmetic.

Bounded functions of totient residues

The same separation method now isolates a coefficient between long zero blocks. For bounded integer coefficients, rationality puts scaled tails in a fixed lattice: the right block forces a tail to zero, and the left leaves a nonzero tail of magnitude below the lattice spacing. Residues below are least nonnegative representatives, not necessarily binary digits.

Theorem 4.1 (Series of totient residues). For every $m \geq 3$ ,

\sum_{n \geq 1} \frac{φ (n) mod m}{2^{n}} \notin Q .

For $k \geq 1$ and $f : Z / 2^{k} Z \to Q$ , the series $\sum_{n \geq 1} f (φ (n) mod 2^{k}) 2^{- n}$ is rational exactly when $f$ is constant on the even residue classes. If that constant is $c$ , its value is $3 f (1) / 4 + c / 4$ .

Only $f (1)$ and the even classes are visible to the series: $φ (1) = φ (2) = 1$ and all later totients are even. This explains the rational case, including the value $3 / 4$ modulo two. The irrational case rests on the pattern

\underset{L terms}{\underset{⏟}{0, \dots, 0}}, a_{N} \neq 0, \underset{L terms}{\underset{⏟}{0, \dots, 0}} .

The coefficients outside the window may have either sign; only their uniform bound matters.

Lemma 4.2 (An isolated nonzero coefficient between long zero blocks). Let $a_{n} \in Z$ satisfy $| a_{n} | \leq C$ . Suppose that for arbitrarily large $L$ there is $N > L$ such that $a_{N} \neq 0$ and $a_{N + t} = 0$ for $0 < | t | \leq L$ . Then $\sum_{n \geq 1} a_{n} 2^{- n}$ is irrational.

Proof. Suppose that the sum has denominator $q \geq 1$ . Multiplying it by $2^{j}$ and removing its finite integer prefix shows that every scaled tail $T_{j} = \sum_{t \geq 1} a_{j + t} 2^{- t}$ belongs to $q^{- 1} Z$ . Choose a pattern with $C 2^{- L} < 1 / q$ . The block on the right gives

| T_{N} | \leq C \sum_{t > L} 2^{- t} = C 2^{- L} < 1 / q .

The only element of $q^{- 1} Z$ in this interval is zero, so $T_{N} = 0$ . The right block has removed the unknown tail exactly. Starting before the left block now leaves only the nonzero centre, rescaled:

T_{N - L - 1} = a_{N} 2^{- L - 1}, 0 < | T_{N - L - 1} | \leq C 2^{- L - 1} < 1 / q,

contradicting $T_{N - L - 1} \in q^{- 1} Z$ . ◻

For example, the indicator of the squares satisfies the lemma. An eventually periodic sequence with infinitely many nonzero terms does not have isolated coefficients at arbitrarily large distances. The uniform bound $C$ is essential to this argument.

Proof of Theorem 4.1. We prescribe a prime at the centre and a different divisor at each neighbour. Fix a unit $s (\mod m)$ and an integer $L \geq 1$ , and choose distinct primes $q_{t} \equiv 1 (\mod m)$ , all exceeding $L$ , for $0 < | t | \leq L$ . The congruences

p \equiv s (\mod m), p \equiv - t (\mod q_{t}) (0 < | t | \leq L)

define a reduced progression, since $s$ is a unit modulo $m$ and $0 < | t | < q_{t}$ . CRT and Dirichlet’s theorem therefore allow us to choose an arbitrarily large prime $p > L + 1$ on this progression, with $m ∣ φ (p + t)$ at every neighbour and $φ (p) \equiv s - 1 (\mod m)$ at the centre.

For a rational-valued function $f$ on the residue classes, subtract $f (0)$ and multiply by a common denominator of its values. Since $\sum_{n \geq 1} 2^{- n} = 1$ , these operations preserve whether the sum is rational. If $f (s - 1) \neq f (0)$ , the resulting bounded integer sequence has an isolated nonzero coefficient for every $L$ , so the lemma applies. For the least-residue map, $s = - 1$ gives the nonzero centre $m - 2$ when $m \geq 3$ . For $m = 2^{k}$ , the possible centres $s - 1$ run through every even class. Thus any failure of constancy on those classes supplies a centre with $f (s - 1) \neq f (0)$ . Conversely, constancy makes every term after $n = 2$ equal $c$ , giving $3 f (1) / 4 + c / 4$ . ◻

The dyadic modulus matters to the classification. Modulo $6$ , for example, prime centres of this form see only $s - 1 \in {0, 4}$ , not the even class $2$ . The least-residue assertion needs just one nonzero centre; classification of an arbitrary function needs all relevant classes.

The first assertion is also an application of Erdős’s sparse-series criterion [6], and of Kaneko, Suzuki and Tachiya [7]. The residues are bounded and nonnegative, and the prime construction above makes their support infinite. The nonzero residues occur on a set of density zero: an integer in that set has no prime divisor $p \equiv 1 (\mod m)$ . Wong gave the case in which the base equals the modulus [5]. The isolated-coefficient argument above also treats signed values of $f - f (0)$ , for which those nonnegative sparse-series criteria need an additional spacing hypothesis. The extension to other bases treats every integer $t \geq 2$ and proves rational linear independence of $1$ and $\sum_{n} (φ (n) mod m) t^{- d n}$ , $d \geq 1$ .

Further consequences for the sections

Every finite set of dyadic sections lies in a single finite level. Theorem 1.1 therefore also determines the full kernel; “span” and “relation” here still mean finite linear combinations.

Corollary A.1 (Dyadic basis). The family

{φ_{0, 0}, φ_{1, 0}} \cup {φ_{j, r} : j \geq 1, 0 < r < 2^{j}, r odd}, φ_{j, r} (n) = φ (2^{j} n + r),

is a basis for the rational span of the full dyadic kernel. Every rational relation is generated by the scalar reductions. The complete level-zero truncation has dimension one.

Proof. Each finite subset of this family is contained in some $B_{2, e}$ . Theorem 1.1 gives independence, and its reductions give spanning. At level zero the sole section $φ (n)$ is nonzero, since $φ (1) = 1$ . ◻

The affine argument also permits periodic coefficients by restriction to their common residue classes.

Corollary A.2 (Periodic coefficients). Let $L_{1}, \dots, L_{s}$ be pairwise nonproportional affine forms with integer coefficients and positive slopes. If $w_{1}, \dots, w_{s}$ are rational-valued periodic sequences, then

\sum_{i} w_{i} (n) φ (L_{i} (n)) = 0 for all sufficiently large n ⟹ w_{i} (n) = 0 for every i, n .

Proof. We choose a common period $Q$ and restrict to $n = r + Q t$ . The coefficients are now the constants $w_{i} (r)$ , and the cross determinants are $Q (a_{i} b_{j} - a_{j} b_{i}) \neq 0$ . By shifting $t$ beyond the given threshold we can apply affine independence, obtaining $w_{i} (r) = 0$ for every $i$ . We repeat this for each residue $r$ ; periodicity then gives the conclusion even at the indices preceding the threshold. ◻

Proportional forms are excluded for a reason: the identity $φ (4 n + 2) = φ (2 n + 1)$ would otherwise contradict the conclusion. Martin’s theorem gives the same corollary on each progression [4].

Coons proves nonregularity using the poles of $ζ (s - 1) / ζ (s)$ [2]. The ranks above recover it: finite rational kernel dimension would embed the integral kernel module by evaluations in $Z^{d}$ , making it finitely generated; the converse is immediate (compare [3]). Allouche, Shallit and Yassawi survey the earlier separation method [13].

The generating function $F_{φ} (z) = \sum_{n \geq 1} φ (n) z^{n}$ therefore satisfies no $k$ -Mahler equation $\sum_{i = 0}^{d} P_{i} (z) F_{φ} (z^{k^{i}}) = 0$ with $P_{i} \in Q [z]$ , $P_{0} \neq 0$ . Indeed, $φ (n) \leq n$ gives logarithmic height at most $\log n$ , and the height theorem of Adamczewski, Bell and Smertnig would make such a series $k$ -regular [16]. Bell and Smertnig’s multiplicative classification gives the same conclusion [14]. Bell, Bruin and Coons treat related algebraic and $D$ -finite series (those satisfying polynomial-coefficient linear differential equations) [15]. These are statements about the function, not its value at $1 / 2$ .

The section operators $T_{i} g (n) = g (k n + i)$ satisfy

T_{i} F_{j, r} = F_{j + 1, k^{j} i + r}, V_{k, e + 1} = V_{k, e} + \sum_{i = 0}^{k - 1} T_{i} V_{k, e} .

Every residue at level $j + 1$ has the form $k^{j} i + r$ , giving the second identity. A positive retained residue stays retained. For the zero-residue generators, reduce $T_{i} F_{0, 0} = F_{1, i}$ and $T_{i} F_{1, 0} = F_{2, k i}$ as before. Each image is a positive integer multiple of a basis element, but rank growth prevents a finite invariant truncation. Consequently the growth formula using the joint spectral radius for regular sequences [3] does not apply.

The binary totient series

The bounded-pulse argument in Theorem 4.1 uses a tail bound independent of the pulse’s position. For $S$ , the bound $0 \leq φ (n) \leq n$ ensures convergence, but forcing $2^{L} ∣ φ (N + L)$ with $N + L > 1$ requires $2^{L} \leq N + L - 1$ . The tail bound $(N + L + 2) 2^{- L}$ then exceeds $1$ . This is a failure of the estimate, not a lower bound on the tail: the window lies too far out for this bound to help. Instead, we test differences of scaled tails by finite sums.

Put $R_{N} = \sum_{j \geq 1} φ (N + j) 2^{- j}$ and $Δ_{h} (N) = R_{N + h} - R_{N}$ . Subtracting the finite-prefix identities for $2^{N + h} S$ and $2^{N} S$ gives

\begin{matrix} (2) & Δ_{h} (N) \equiv 2^{N} (2^{h} - 1) S (\mod Z) . \end{matrix}

If $S = a / (2^{c} v)$ , with $v$ odd, then $Δ_{h} (N)$ is integral for $N \geq c$ and $h = φ (v)$ . The tails are then periodic modulo integers, not necessarily equal. To disprove rationality it therefore suffices to find a nonintegral difference beyond every threshold for each positive $h$ .

For $h, N, L \in N$ , define the integer

D_{h, N, L} = \sum_{j = 0}^{L - 1} (φ (N + h + 1 + j) - φ (N + 1 + j)) 2^{L - 1 - j}, B = N + h + L + 2.

Since $0 \leq R_{M} \leq M + 2$ , we have

\begin{matrix} (3) & 2^{L} Δ_{h} (N) - D_{h, N, L} = R_{N + h + L} - R_{N + L}, | 2^{L} Δ_{h} (N) - D_{h, N, L} | \leq B . \end{matrix}

Both tails lie in $[0, B]$ , so their difference has magnitude at most $B$ , not $2 B$ . The interval centred at $D_{h, N, L} / 2^{L}$ with radius $B / 2^{L}$ avoids every integer precisely when

\begin{matrix} (4) & B < D_{h, N, L} mod 2^{L} < 2^{L} - B . \end{matrix}

This proves $Δ_{h} (N) \notin Z$ and, by (2), excludes every reduced denominator dividing $2^{N} (2^{h} - 1)$ . For example, $D_{1, 12, 16} = - 143140$ has residue $53468$ modulo $2^{16}$ , and $B = 31$ , so it excludes denominators dividing $2^{12}$ . In ordinary coordinates the same certificate reads

Δ_{1} (12) \in [\frac{- 143171}{65536}, \frac{- 143109}{65536}] \subset (- 3, - 2) .

For fixed $h, N$ , the test is complete: if $δ = dist (Δ_{h} (N), Z) > 0$ , then $2^{L} δ > 2 B$ for all large $L$ , since $B$ grows linearly. Together with (3), this gives (4). A failed test proves no integrality; its interval may be too wide. Depth detects a given nonintegral difference, but does not supply one for each $h$ beyond every threshold.

Equivalent residue conditions

We write $K (h, N, L)$ for (4).

Theorem B.1 (Propagation of one nonintegral tail difference). Fix $d \geq 1$ and $N \geq 0$ . If $Δ_{d} (N) \notin Z$ , then every sufficiently late pair ${t, t + 1}$ contains an $m$ such that $K (m d, N, m d)$ holds. Consequently

\exists t \geq 1 : K (t d, N, t d) ⟺ Δ_{d} (N) \notin Z .

Requiring this for every $d \geq 1, N \geq 0$ is equivalent to $S \notin Q$ .

Completeness fixes $h, N$ and varies $L$ ; here $L = h = t d$ . A failed test puts $Δ_{t d} (N)$ within $2 (N + 2 t d + 2) 2^{- t d}$ of $Z$ . This bound tends to zero. The recurrence $Δ_{(t + 1) d} (N) \equiv 2^{d} Δ_{t d} (N) + Δ_{d} (N) (\mod Z)$ would transfer two consecutive errors to the fixed nonintegral $Δ_{d} (N)$ . Its positive distance from $Z$ therefore rules out consecutive failures for large $t$ . The companion proof gives the estimates. The final assertion still quantifies over every $d, N$ , not one pair.

For a hypothetical denominator $2^{c} v$ , a second test uses the modulus $M = (2^{H} - 1) / v$ , where $H$ is a positive multiple of $φ (v)$ . Write $B_{H, c} = \sum_{j = 0}^{H - 1} φ (c + 1 + j) 2^{H - 1 - j}$ .

Equivalent formulation B.2 (A residue test modulo a divisor of $2^{H} - 1$ ). The series $S$ is irrational if and only if, for every $c \geq 0$ and odd $v \geq 1$ , some positive multiple $H$ of $φ (v)$ satisfies

\begin{matrix} (5) & c + H + 1 < (- B_{H, c}) mod M < M - (c + H + 1) . \end{matrix}

The identity $B_{H, c} = M (v R_{c}) - Δ_{H} (c)$ puts $B_{H, c}$ within $c + H + 1$ of $M (v R_{c})$ . If $S = a / (2^{c} v)$ , then $v R_{c} \in Z$ , so the residue lies near an endpoint. For irrational $S$ , the fixed number $v R_{c}$ has positive distance from $Z$ . The distance of $M (v R_{c})$ from $M Z$ grows exponentially, while the error bound and excluded margins grow linearly. The proof and residue recurrence give the bounds. The required residues have not been shown to exist for every choice of the parameters in either test. A separate Farey-interval calculation at depth $240$ excludes $S = a / q$ for $0 < q \leq Q_{0} \approx 7.96 \times 10^{34}$ .

Comparison sequences

Rationality and linear coefficient growth still permit exponential carry rank. There is an integer sequence $c$ with $0 \leq c (n) \leq n$ , unchanged odd totients and $| c (n) - φ (n) | \leq 2$ at even indices, for which $\sum c (n) 2^{- n} = 5 / 4$ . Its carry is the integer sequence

u_{N} = 4 \sum_{j \geq 1} c (N + j) 2^{- j} = 5 \cdot 2^{N} - 4 \sum_{n = 1}^{N} c (n) 2^{N - n} .

Its recurrence is $2 u_{N - 1} - u_{N} = 4 c (N)$ for $N \geq 1$ . For $j \geq 1$ and odd $0 < r < 2^{j}$ , this gives

4 φ (2^{j} n + r) = 2 u_{2^{j} n + r - 1} - u_{2^{j} n + r} .

Thus the $2^{e} - 1$ independent odd-residue totient sections lie in the span of the carry sections through level $e$ . This explains how the rank lower bound survives even though the sum is rational. The construction and its limitations explain why it fails the exact prime-dilation laws of $φ$ . The same section retains the cofinal LCM-diagonal criterion, its endpoint sign conditions and the limits of finite integer combinations of shifts.

The signed interpolation argument tests whether preserving specified analytic data fixes the value. For each integer $β \geq 2$ , sparse even-index corrections realise every value in an interval about $\sum φ (n) β^{- n}$ , with a prescribed prefix and all odd coefficients fixed. Errors are bounded by any prescribed positive $f (n) \to \infty$ ; their support has upper Banach density zero. On each fixed arithmetic progression the Dirichlet-series difference is entire. At roots of unity the generating-function difference extends smoothly radially, with any prescribed finite collection of radial derivatives zero. This preserves Dirichlet singularities, not regular parts or zeros; a finite jet is not the full radial germ. The proof is not formalised in Lean and estimates no cancellation for the unchanged totient sequence.

Rational approximation imposes a different requirement. The identity

Θ_{2} := \sum_{d \geq 1} \frac{μ (d)}{(2^{d} - 1)^{2}} = S - \frac{1}{2}

was posted by Amiram Eldar, together with its coprimality interpretation, on 15 March 2026 [8], and by Steve Fan on 16 May 2026 [9]. Consider the rational quotients

Q (e, Y) = \frac{(\sum_{d \leq Y} μ (d) / (2^{d} - 1)^{e + 2})^{2}}{\sum_{d \leq Y} μ (d) / (2^{d} - 1)^{2 e + 2}} .

Theorem B.3 (A lower bound for the rank-one quotients). For $e \geq 1$ and $Y \geq 4$ , the denominator of $Q (e, Y)$ is positive, and the unique minimiser is $(e, Y) = (1, 5)$ . Every admissible quotient and every nonempty finite positive weighted average of such quotients satisfies

Q - Θ_{2} > \frac{21}{320} .

The uniform bound $Q - Θ_{2} > 1 / 15$ is false already at $(1, 5)$ .

The proof first makes the denominator uniformly positive. A geometric bound handles all $e \geq 2$ ; at $e = 1$ , seven-term prefixes leave only $Y = 4, 5, 6$ to compare directly. The averaging assertion concerns averages of the quotients themselves. It leaves open signed combinations, quotients formed after combining the sums, and higher-rank kernels. For a denominator-clearing irrationality argument, a sufficient target is $0 < q_{j} | Θ_{2} - p_{j} / q_{j} | \to 0$ , with $p_{j} / q_{j}$ in lowest terms. Indeed, if $Θ_{2} = a / b$ , any nonzero difference satisfies $q_{j} | a / b - p_{j} / q_{j} | = | a q_{j} - b p_{j} | / b \geq 1 / b$ . Convergence alone gives no such contradiction.

An exponential-sum question

To prove irrationality, it suffices to show that for every $h \geq 1$ and every $X_{0}$ , some integers $X \geq max (X_{0}, 1)$ and $L \geq h$ satisfy

\begin{matrix} (6) & 16 (2 X + h + L + 2) \leq 2^{L}, Re \sum_{N = X}^{2 X - 1} \exp (2 π i D_{h, N, L} / 2^{L}) \leq \frac{9}{10} X . \end{matrix}

The phases cannot all cluster near $1$ . If every residue failed (4), each $D_{h, N, L} / 2^{L}$ would be within $1 / 16$ of an integer. Each exponential would then have real part at least $\cos (π / 8) > 9 / 10$ . Thus some $N$ satisfies (4). For a hypothetical rational value, choosing its period and a sufficiently late block contradicts (2).

To separate counting from cancellation, single out one totient in each window. Fix $h, s \geq 1$ , $L \geq s + h$ , $X \geq 1$ and $0 < η < 1$ , and put $t = L - s + 1$ and $E_{N} = \exp (2 π i D_{h, N, L} / 2^{L})$ . For $X \leq N < 2 X$ , let $p_{N}$ be the largest prime factor of $N + t$ and $m_{N} = (N + t) / p_{N}$ . Define

\begin{aligned} A & = {N \in [X, 2 X) : m_{N} \leq ⌊ \sqrt{X} / 2 ⌋, p_{N} > 2 ⌊ \sqrt{X} ⌋}, \\ G & = {N \in A : φ (m_{N}) \geq η m_{N}} . \end{aligned}

All indices are integers. On $A$ , $p_{N} > m_{N}$ , hence $φ (N + t) = φ (m_{N}) (p_{N} - 1)$ . Since $h < t \leq L$ , this term occurs in both tails, with net coefficient $2^{- (t - h)} - 2^{- t} = (2^{h} - 1) / 2^{t}$ . Write

z_{N} = \exp (\frac{2 π i (2^{h} - 1) φ (m_{N}) (p_{N} - 1)}{2^{t}}), w_{N} = E_{N} / z_{N},

and let ${\bar{z}}_{m}$ be the average over the indices in $A$ with cofactor $m$ , or zero for an empty set. For fixed $m$ , the exponent of $z_{N}$ is affine in $p_{N}$ ; $w_{N}$ contains the other totients.

Consider the four bounds

\begin{matrix} (7) & \begin{aligned} Re \sum_{N \in G} w_{N} (z_{N} - {\bar{z}}_{m_{N}}) & \leq \frac{14}{25} X, \\ | \sum_{N \in G} w_{N} {\bar{z}}_{m_{N}} | & \leq \frac{1}{100} X, \\ | \sum_{N \in A ∖ G} E_{N} | & \leq \frac{1}{100} X, \\ | \sum_{\begin{matrix} X \leq N < 2 X \\ N \notin A \end{matrix}} E_{N} | & \leq \frac{8}{25} X . \end{aligned} \end{matrix}

These are an exact partition: outside $G$ use the last two sums; on $G$ write $w_{N} z_{N} = w_{N} (z_{N} - {\bar{z}}_{m_{N}}) + w_{N} {\bar{z}}_{m_{N}}$ . The bounds add to $(14 / 25 + 1 / 100 + 1 / 100 + 8 / 25) X = 9 X / 10$ .

The last three bounds are available at a common depth. Take the least $L \geq s + h$ satisfying the size inequality in (6). The smooth-number and small-cofactor estimates give the last two bounds for all large $X$ when $0 < η < 1 / (300 \log 4)$ . The elementary excluded-cofactor estimate is $(3 η \log 4 + o (1)) X$ ; it needs no prime number theorem. With the prime number theorem as input, the group-mean estimate gives the second bound for $s = 26$ , $η = 1 / 1000$ at this depth and all large $X$ . The first bound remains open.

Small group means control the second sum by the triangle inequality because $| w_{N} | = 1$ . They do not control the first: subtracting ${\bar{z}}_{m}$ cancels an unweighted group sum, not one with varying $w_{N}$ . No independence is assumed. For example, $z = (1, - 1)$ has mean zero, but the weights $w = (1, - 1)$ make $\sum w_{N} (z_{N} - \bar{z}) = 2$ . This illustrates the distinction, not the behaviour of the totient phases. A real-part bound does not control the imaginary part or give the $21 X / 25$ norm bound.

Problem C.1 (Four estimates for the first-harmonic sum). For each $h \geq 1$ , do there exist $s \geq 1$ and $0 < η < 1$ such that, for every $X_{0}$ , there are $X, L$ with

max (X_{0}, 1) \leq X, h \leq L - s, 16 (2 X + h + L + 2) \leq 2^{L},

for which those four bounds hold?

Fix $s, η$ after $h$ but before $X_{0}$ ; all four estimates must hold on the same block. At $s = 26$ , $η = 1 / 1000$ and the least admissible $L$ , it suffices to prove the first bound for arbitrarily large $X$ : the other three hold eventually on those same blocks.

A weaker sufficient condition needs no group-mean input. Since $| G | > 67 X / 100$ for large $X$ , the open bound $Re \sum_{N \in G} E_{N} \leq 603 X / 1000$ would put the average on $G$ below $9 / 10$ : $603 / 1000 = (9 / 10) (67 / 100)$ . Some good index would pass the test. This requires an average on $G$ for each $h$ on arbitrarily large blocks, not a bound on the full block. The ordinary comparison argument gives larger first harmonics at all sufficiently large admissible scales, distinguishing its rational sequences from the cancellation required of $φ$ .

Balasubramanian, Giri and Srivastav give correlation estimates applicable to $φ (n) / n$ , uniformly for $| h | \leq x / 2$ [11]. Their correlation is a product of two normalised totient values. Here the modulus grows with $L$ , and $w_{N}$ is an exponential of the other, overlapping totient contributions. The cited shift uniformity does not supply this weighted exponential estimate.

Verification and reproducibility

The declaration guide links the formal sources for this paper. Complete proofs of three cited results appear in Appendix A of the companion paper. The displayed arguments, including signed interpolation, require ordinary mathematical review; the recorded Lean and Comparator checks cover their specified declarations and source versions. No new formal run or independent review was performed for this revision.

References

J.-P. Allouche and J. Shallit, The ring of $k$ -regular sequences, Theoret. Comput. Sci. 98 (1992), no. 2, 163–197, doi:10.1016/0304-3975(92)90001-V.
M. Coons, (Non)Automaticity of number theoretic functions, J. Théor. Nombres Bordeaux 22 (2010), no. 2, 339–352, doi:10.5802/jtnb.718. Theorem 3.2, p. 348.
M. Coons, Regular sequences and the joint spectral radius, Internat. J. Found. Comput. Sci. 28 (2017), no. 2, 135–140, doi:10.1142/S0129054117500095; arXiv:1511.07535v1. Theorem 1, Proposition 4, Corollary 7 and Appendix A are cited with the arXiv v1 numbering.
G. Martin, Simultaneous inequalities among values of the Euler phi-function, arXiv:math/0603053v1, 2006. Theorem 1, pp. 1–2.
Erick Wong, answer 1211557 to An infinite sum based on the mod-parity of Euler’s totient function, Mathematics Stack Exchange, 29 March 2015, accessed 15 September 2026.
P. Erdős, On the irrationality of certain series, Indag. Math. 19 (1957), 212–219. Lemmas 1 and 4, pp. 213–218.
H. Kaneko, Y. Suzuki and Y. Tachiya, Refinements of Erdős’s irrationality criterion for certain sparse infinite series, arXiv:2601.20743v1. Theorem 3, p. 5.
A. Eldar, comment and formula added to OEIS A256936 (revisions 28 and 31), 15 March 2026, https://oeis.org/history?seq=A256936, accessed 16 September 2026.
S. Fan, comment on Erdős Problem #249, 16 May 2026, 19:01, Erdős Problems discussion thread, accessed 16 September 2026.
P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, Monographies de L’Enseignement Mathématique 28, 1980, p. 61.
R. Balasubramanian, S. Giri and P. Srivastav, On correlations of certain multiplicative functions, J. Number Theory 174 (2017), 221–238, doi:10.1016/j.jnt.2016.10.001; arXiv:1511.02221v3. Theorem 2.2 is cited with the arXiv v3 pagination, p. 2.
S. Yazdani, Multiplicative functions and $k$ -automatic sequences, J. Théor. Nombres Bordeaux 13 (2001), no. 2, 651–658, https://www.numdam.org/item/JTNB_2001__13_2_651_0/. Theorem 2 and its proof, pp. 652–653; Corollary 4, p. 654.
J.-P. Allouche, J. Shallit and R. Yassawi, How to prove that a sequence is not automatic, Exposition. Math. 40 (2022), no. 1, 1–22, doi:10.1016/j.exmath.2021.08.001; arXiv:2104.13072v1. Theorem and example numbering follows the arXiv v1 (2021).
J. Bell and D. Smertnig, Mahler series with multiplicative coefficient sequences, arXiv:2603.23456v1, 24 March 2026, preprint. Theorem 1.3, p. 2; Lemma 3.3, p. 9.
J. P. Bell, N. Bruin and M. Coons, Transcendence of generating functions whose coefficients are multiplicative, Trans. Amer. Math. Soc. 364 (2012), no. 2, 933–959, doi:10.1090/S0002-9947-2011-05479-6; arXiv:1003.2221v2. Theorems 1.5–1.6 are cited with the arXiv v2 pagination, p. 2.
B. Adamczewski, J. Bell and D. Smertnig, A height gap theorem for coefficients of Mahler functions, J. Eur. Math. Soc. 25 (2023), no. 7, 2525–2571, doi:10.4171/JEMS/1244. Theorem 1.2(b), p. 2528; logarithmic height in Section 1.1.1, p. 2527.

[ref-1] J.-P. Allouche and J. Shallit, The ring of $k$ -regular sequences, Theoret. Comput. Sci. 98 (1992), no. 2, 163–197, doi:10.1016/0304-3975(92)90001-V.

[ref-2] M. Coons, (Non)Automaticity of number theoretic functions, J. Théor. Nombres Bordeaux 22 (2010), no. 2, 339–352, doi:10.5802/jtnb.718. Theorem 3.2, p. 348.

[ref-3] M. Coons, Regular sequences and the joint spectral radius, Internat. J. Found. Comput. Sci. 28 (2017), no. 2, 135–140, doi:10.1142/S0129054117500095; arXiv:1511.07535v1. Theorem 1, Proposition 4, Corollary 7 and Appendix A are cited with the arXiv v1 numbering.

[ref-4] G. Martin, Simultaneous inequalities among values of the Euler phi-function, arXiv:math/0603053v1, 2006. Theorem 1, pp. 1–2.

[ref-5] Erick Wong, answer 1211557 to An infinite sum based on the mod-parity of Euler’s totient function, Mathematics Stack Exchange, 29 March 2015, accessed 15 September 2026.

[ref-6] P. Erdős, On the irrationality of certain series, Indag. Math. 19 (1957), 212–219. Lemmas 1 and 4, pp. 213–218.

[ref-7] H. Kaneko, Y. Suzuki and Y. Tachiya, Refinements of Erdős’s irrationality criterion for certain sparse infinite series, arXiv:2601.20743v1. Theorem 3, p. 5.

[ref-8] A. Eldar, comment and formula added to OEIS A256936 (revisions 28 and 31), 15 March 2026, https://oeis.org/history?seq=A256936, accessed 16 September 2026.

[ref-9] S. Fan, comment on Erdős Problem #249, 16 May 2026, 19:01, Erdős Problems discussion thread, accessed 16 September 2026.

[ref-10] P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, Monographies de L’Enseignement Mathématique 28, 1980, p. 61.

[ref-11] R. Balasubramanian, S. Giri and P. Srivastav, On correlations of certain multiplicative functions, J. Number Theory 174 (2017), 221–238, doi:10.1016/j.jnt.2016.10.001; arXiv:1511.02221v3. Theorem 2.2 is cited with the arXiv v3 pagination, p. 2.

[ref-12] S. Yazdani, Multiplicative functions and $k$ -automatic sequences, J. Théor. Nombres Bordeaux 13 (2001), no. 2, 651–658, https://www.numdam.org/item/JTNB_2001__13_2_651_0/. Theorem 2 and its proof, pp. 652–653; Corollary 4, p. 654.

[ref-13] J.-P. Allouche, J. Shallit and R. Yassawi, How to prove that a sequence is not automatic, Exposition. Math. 40 (2022), no. 1, 1–22, doi:10.1016/j.exmath.2021.08.001; arXiv:2104.13072v1. Theorem and example numbering follows the arXiv v1 (2021).

[ref-14] J. Bell and D. Smertnig, Mahler series with multiplicative coefficient sequences, arXiv:2603.23456v1, 24 March 2026, preprint. Theorem 1.3, p. 2; Lemma 3.3, p. 9.

[ref-15] J. P. Bell, N. Bruin and M. Coons, Transcendence of generating functions whose coefficients are multiplicative, Trans. Amer. Math. Soc. 364 (2012), no. 2, 933–959, doi:10.1090/S0002-9947-2011-05479-6; arXiv:1003.2221v2. Theorems 1.5–1.6 are cited with the arXiv v2 pagination, p. 2.

[ref-16] B. Adamczewski, J. Bell and D. Smertnig, A height gap theorem for coefficients of Mahler functions, J. Eur. Math. Soc. 25 (2023), no. 7, 2525–2571, doi:10.4171/JEMS/1244. Theorem 1.2(b), p. 2528; logarithmic height in Section 1.1.1, p. 2527.