Introduction
Splitting the totient sequence into its even and odd subsequences,
then splitting once more, gives seven sequences:
𝜑(𝑛);𝜑(2𝑛), 𝜑(2𝑛+1);𝜑(4𝑛), 𝜑(4𝑛+1), 𝜑(4𝑛+2), 𝜑(4𝑛+3).
The identities
𝜑(4𝑛)=2𝜑(2𝑛),𝜑(4𝑛+2)=𝜑(2𝑛+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 𝑘 ≥2, the
totient sections are the sequences 𝑛 ↦𝜑(𝑘𝑗𝑛 +𝑟), where 𝑗 ≥0 and 0 ≤𝑟 <𝑘𝑗. Throughout, 𝑛 ranges over ℕ ={0,1,2,…} and 𝜑(0) =0. To describe relations we
retain a separate index for each pair (𝑗,𝑟), even when two pairs give the same
sequence. For example, 𝜑(4𝑛 +2) and 𝜑(2𝑛 +1) are equal sequences but
occupy different positions in the list above.
The sections form the 𝑘-kernel
of the totient sequence. A sequence is 𝑘-regular when the ℤ-module generated by its 𝑘-kernel is finitely generated [1]. Coons proved
that the totient sequence is not 𝑘-regular for any 𝑘 ≥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 𝜑(𝑛) and has dimension one.
Theorem 1.1 (A basis through each finite level).
Let 𝑘 ≥2 and 𝑒 ≥1 be integers, write 𝐹(𝑘)𝑗,𝑟(𝑛) =𝜑(𝑘𝑗𝑛 +𝑟), and put
𝑉𝑘,𝑒=spanℚ{𝐹(𝑘)𝑗,𝑟:0≤𝑗≤𝑒, 0≤𝑟<𝑘𝑗}.
Then dimℚ𝑉𝑘,𝑒 =𝑘𝑒 +1, and
B𝑘,𝑒={𝐹(𝑘)0,0,𝐹(𝑘)1,0}∪{𝐹(𝑘)𝑗,𝑟:1≤𝑗≤𝑒, 1≤𝑟<𝑘𝑗, 𝑘∤𝑟}
is a basis. Every omitted section reduces to a basis
element by an explicit scalar: 𝐹(𝑘)𝑗,0 =𝑘𝑗−1𝐹(𝑘)1,0 for
𝑗 ≥1, and if 𝑟 =𝑘𝑡𝑢 with 𝑡 =max{𝑠 :𝑘𝑠 ∣𝑟} ≥1 and 𝑘 ∤𝑢, then
𝐹(𝑘)𝑗,𝑟=𝐶𝑘(𝑡,𝑢)𝐹(𝑘)𝑗−𝑡,𝑢,𝐶𝑘(𝑡,𝑢)=𝑘𝑡∏𝑝∣𝑘𝑝∤𝑢(1−1𝑝).
The condition 𝑘 ∤𝑟 allows
residues with gcd(𝑘,𝑟) >1. For
instance, 𝑟 =1 and 𝑟 =2 are both retained in base six, and
the reductions involving them are
𝜑(36𝑛+6)=2𝜑(6𝑛+1),𝜑(36𝑛+12)=4𝜑(6𝑛+2).
The factor 2 is already present in 6𝑛 +2 but not in 6𝑛 +1; only newly introduced prime
divisors contribute factors 1 −1/𝑝.
Thus one removes whole factors of 𝑘
from the residue, not every common prime factor. Repeated prime factors
of 𝑘 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
𝑆=∑𝑛≥1𝜑(𝑛)2𝑛
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 𝑆. 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, 𝑘𝑛 and 𝑘𝑗𝑛 have the same prime divisors when
𝑛 >0. Hence 𝜑(𝑘𝑗𝑛) =𝑘𝑗−1𝜑(𝑘𝑛); both
sides vanish at 𝑛 =0. For an omitted
positive residue 𝑟 =𝑘𝑡𝑢 with 𝑡 ≥1 and 𝑘 ∤𝑢, we have 𝑡 <𝑗 because 0 <𝑟 <𝑘𝑗. Put 𝑚 =𝑘𝑗−𝑡𝑛 +𝑢. A prime 𝑝 ∣𝑘 divides 𝑚 exactly when it divides 𝑢. The product formula for 𝜑(𝑘𝑡𝑚)/𝜑(𝑚) therefore
contributes 𝑘𝑡 and one factor
1 −1/𝑝 for each prime 𝑝 ∣𝑘 absent from 𝑢. The multiplier is an integer: its
denominator is a product of distinct primes dividing 𝑘, and therefore divides 𝑘𝑡. This gives 𝐶𝑘(𝑡,𝑢) and proves that the stated
family spans 𝑉𝑘,𝑒.
Affine independence
Independence follows from Martin’s theorem. For any ordering of
pairwise nonproportional affine forms and any 𝐶 >0, it gives a set of positive lower
density on which each successive totient ratio exceeds 𝐶. In a proposed nonzero relation, place
a nonzero coefficient 𝑐1 first and
take 𝐶 >max(1,∑𝑖>1|𝑐𝑖|/|𝑐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
𝐿𝑖(𝑛) =𝑎𝑖𝑛 +𝑏𝑖 for 1 ≤𝑖 ≤𝑠, where 𝑎𝑖 >0 and 𝑎𝑖𝑏𝑗 −𝑎𝑗𝑏𝑖 ≠0 for 𝑖 ≠𝑗. Shift 𝑛 so that all 𝑏𝑖 are positive; the cross determinants
do not change. Write 𝐿𝑖 =𝑔𝑖𝐴𝑖,
where 𝑔𝑖 =gcd(𝑎𝑖,𝑏𝑖) and 𝐴𝑖 is primitive. We make 𝐴𝑖, not 𝐿𝑖, prime: 𝐿𝑖 may have the fixed divisor 𝑔𝑖 >1. We seek a prime ℓ and points 𝑛1,…,𝑛𝑠 for which
𝐸=(𝜑(𝐿𝑗(𝑛𝑖)))1≤𝑖,𝑗≤𝑠≡⎛⎜
⎜
⎜
⎜⎝𝜑(𝑔1)0⋯00𝜑(𝑔2)⋯0⋮⋮⋱⋮00⋯𝜑(𝑔𝑠)⎞⎟
⎟
⎟
⎟⎠(modℓ),ℓ∤∏𝑖𝜑(𝑔𝑖).(1)
Since det𝐸 ≢0(modℓ), 𝐸
is invertible over ℚ. A rational
relation gives 𝐸𝑐 =0, hence 𝑐 =0. We now construct the rows.
For 𝑗 ≠𝑖, a prime divisor
𝑞𝑖𝑗 ≡1(modℓ) of 𝐿𝑗(𝑛𝑖) makes ℓ ∣𝑞𝑖𝑗 −1 ∣𝜑(𝐿𝑗(𝑛𝑖)).
For the diagonal entry, we instead make 𝐴𝑖(𝑛𝑖) prime and congruent to 2 modulo ℓ. Choose an odd ℓ dividing none of the slopes 𝑎𝑖, the products 𝑔𝑖𝜑(𝑔𝑖) or the nonzero cross
determinants. For each fixed 𝑖,
Dirichlet’s theorem supplies distinct primes 𝑞𝑖𝑗 ≡1(modℓ) (𝑗 ≠𝑖) outside the same finite
exceptional set. Impose
𝐴𝑖(𝑛)≡2(modℓ),𝐿𝑗(𝑛)≡0(mod𝑞𝑖𝑗)(𝑗≠𝑖).
Each congruence is
soluble because its slope is coprime to its modulus. CRT combines them
into 𝑛 =𝑛0 +𝑅𝑢, where 𝑅 =ℓ∏𝑗≠𝑖𝑞𝑖𝑗.
CRT supplies the congruences, but not yet a prime value. Dirichlet
applies to the progression of values of 𝐴𝑖, namely
𝐴𝑖(𝑛0+𝑅𝑢)=𝐴𝑖(𝑛0)+(𝑎𝑖/𝑔𝑖)𝑅𝑢.
Its
initial value must be coprime to its step. The step has only three kinds
of prime factors: those of 𝑎𝑖/𝑔𝑖,
excluded by primitivity; ℓ,
excluded by the residue 2; and the
imposed 𝑞𝑖𝑗. Such a 𝑞𝑖𝑗 cannot divide 𝐴𝑖(𝑛0): it would then divide both 𝐿𝑖(𝑛0) and 𝐿𝑗(𝑛0), hence
𝑎𝑖𝐿𝑗(𝑛0)−𝑎𝑗𝐿𝑖(𝑛0)=𝑎𝑖𝑏𝑗−𝑎𝑗𝑏𝑖,
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 𝑝 =𝐴𝑖(𝑛𝑖) prime, as large as needed, and
in particular with 𝑝 ∤𝑔𝑖. Then
𝜑(𝐿𝑖(𝑛𝑖))=𝜑(𝑔𝑖)(𝑝−1)≡𝜑(𝑔𝑖)≢0(modℓ),
while all the
other entries of row 𝑖 vanish
modulo ℓ. We choose the rows
separately, applying Dirichlet’s theorem once more for each selected
form 𝐴𝑖. Thus no simultaneous
primality assertion is required. The construction proves (1) with every
𝑛𝑖 beyond any prescribed
threshold.
The two zero-residue sections
The arguments 𝑛,𝑘𝑛 are
proportional; their totient sequences are not. We first merge their
coefficients on 𝑛 =𝑘𝑚 +1, where 𝜑(𝑘𝑛) =𝜑(𝑘)𝜑(𝑛), then
separate them using a different ratio. On this progression the
positive-residue sections have arguments
𝑘𝑗+1𝑚+𝑘𝑗+𝑟(𝑘∤𝑟),
together
with 𝑘𝑚 +1. These are pairwise
nonproportional: equality of two intercept-to-slope ratios would give
𝑟/𝑘𝑗 =𝑟′/𝑘𝑗′, which for
𝑗′ >𝑗 forces 𝑘 ∣𝑟′. No positive-residue form is
proportional to 𝑘𝑚 +1. If 𝐴,𝐵 multiply 𝜑(𝑛),𝜑(𝑘𝑛), affine
independence therefore leaves 𝐴 +𝐵𝜑(𝑘) =0 and eliminates every
other coefficient. At 𝑛 =𝑘, however,
the ratio is 𝑘, giving 𝐴 +𝐵𝑘 =0. Since 𝜑(𝑘) <𝑘, these two equations
separate the remaining coefficients: 𝐴 =𝐵 =0. Finally,
|B𝑘,𝑒|=2+𝑒∑𝑗=1(𝑘𝑗−𝑘𝑗−1)=𝑘𝑒+1,
which completes the
proof of Theorem 1.1. For independence
on a tail, use a sufficiently large power of 𝑘 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: 𝐹0,0,𝐹1,0, the five
𝐹1,𝑟 (1 ≤𝑟 ≤5), and the 30 sections 𝐹2,𝑟 with 1 ≤𝑟 <36 and 6 ∤𝑟. The omitted sections satisfy
𝐹2,0=6𝐹1,0,𝐹2,6=2𝐹1,1,𝐹2,12=4𝐹1,2,𝐹2,18=3𝐹1,3,𝐹2,24=4𝐹1,4,𝐹2,30=2𝐹1,5.
The formal symbols 𝐸𝑗,𝑟 remain independent even when
their sequences 𝐹𝑗,𝑟 coincide.
The substitution 𝐹2,12 =4𝐹1,2
corresponds to the decomposition
𝑥1,2𝐸1,2+𝑥2,12𝐸2,12=(𝑥1,2+4𝑥2,12)𝐸1,2+𝑥2,12(𝐸2,12−4𝐸1,2).
The retained coefficient
becomes 𝑥1,2 +4𝑥2,12; the
relation coefficient is the original 𝑥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
𝐸2,0 −2𝐸1,0 and 𝐸2,2 −𝐸1,1.
Proof. Since ∏𝑝∣𝑘,𝑝∤𝑢𝑝 divides 𝑘,
every scalar 𝐶𝑘(𝑡,𝑢) is an
integer. The retained family therefore spans the section module over
ℤ, and its rational independence
makes it a ℤ-basis.
For any vector 𝑥 =∑𝑖𝑥𝑖𝐸𝑖,
substitute 𝐸𝑖 =𝑅𝑖 +𝑎𝑖𝐸𝑗(𝑖) at
each omitted index and collect terms:
𝑥=∑𝑗 retained⎛⎜
⎜
⎜⎝𝑥𝑗+∑𝑖 omitted𝑗(𝑖)=𝑗𝑎𝑖𝑥𝑖⎞⎟
⎟
⎟⎠𝐸𝑗+∑𝑖 omitted𝑥𝑖𝑅𝑖.
The first sum gives the
retained coordinates of the evaluated sequence; the second evaluates to
zero. Thus 𝑥 is a relation exactly
when the first sum vanishes, in which case 𝑥 =∑𝑖 omitted𝑥𝑖𝑅𝑖. This
expression is unique: at omitted index 𝑖, the coefficient of ∑ℎ𝑐ℎ𝑅ℎ is 𝑐𝑖 itself. Each substitution has a unit
coefficient at its own omitted index, so the entire calculation takes
place over ℤ, without division.
Counting omitted indices gives (1 +𝑘 +⋯ +𝑘𝑒) −(𝑘𝑒 +1) =∑𝑒−1𝑗=1𝑘𝑗. ◻
The section-generated module need not contain every
integer-valued sequence in its rational span: for 𝑘 =2, 𝑒 ≥2, the sequence 𝜑(4𝑛 +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 𝑛 =0,…,36 to obtain a 37 ×37 matrix. Its determinant is
17 modulo 101, so it is nonsingular over ℚ. 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𝐹2,2 would vanish modulo 101 at every input, although its integer
value at 𝑛 =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 𝑚 ≥3,
∑𝑛≥1𝜑(𝑛)mod𝑚2𝑛∉ℚ.
For 𝑘 ≥1
and 𝑓 :ℤ/2𝑘ℤ →ℚ, the series
∑𝑛≥1𝑓(𝜑(𝑛)mod2𝑘)2−𝑛
is rational exactly when 𝑓 is
constant on the even residue classes. If that constant is 𝑐, its value is 3𝑓(1)/4 +𝑐/4.
Only 𝑓(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
0,…,0⏟𝐿 terms,𝑎𝑁≠0,0,…,0⏟𝐿 terms.
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 𝑎𝑛 ∈ℤ satisfy |𝑎𝑛| ≤𝐶. Suppose that for arbitrarily
large 𝐿 there is 𝑁 >𝐿 such that 𝑎𝑁 ≠0 and 𝑎𝑁+𝑡 =0 for 0 <|𝑡| ≤𝐿. Then ∑𝑛≥1𝑎𝑛2−𝑛 is
irrational.
Proof. Suppose that the sum has denominator 𝑞 ≥1. Multiplying it by 2𝑗 and removing its finite integer
prefix shows that every scaled tail 𝑇𝑗 =∑𝑡≥1𝑎𝑗+𝑡2−𝑡 belongs to
𝑞−1ℤ. Choose a pattern with
𝐶2−𝐿 <1/𝑞. The block on the
right gives
|𝑇𝑁|≤𝐶∑𝑡>𝐿2−𝑡=𝐶2−𝐿<1/𝑞.
The only element of 𝑞−1ℤ in this interval is zero, so
𝑇𝑁 =0. The right block has removed
the unknown tail exactly. Starting before the left block now leaves only
the nonzero centre, rescaled:
𝑇𝑁−𝐿−1=𝑎𝑁2−𝐿−1,0<|𝑇𝑁−𝐿−1|≤𝐶2−𝐿−1<1/𝑞,
contradicting 𝑇𝑁−𝐿−1 ∈𝑞−1ℤ. ◻
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 𝐶 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 𝑠(mod𝑚) and
an integer 𝐿 ≥1, and choose
distinct primes 𝑞𝑡 ≡1(mod𝑚),
all exceeding 𝐿, for 0 <|𝑡| ≤𝐿. The congruences
𝑝≡𝑠(mod𝑚),𝑝≡−𝑡(mod𝑞𝑡)(0<|𝑡|≤𝐿)
define a reduced
progression, since 𝑠 is a unit
modulo 𝑚 and 0 <|𝑡| <𝑞𝑡. CRT and Dirichlet’s
theorem therefore allow us to choose an arbitrarily large prime 𝑝 >𝐿 +1 on this progression, with 𝑚 ∣𝜑(𝑝 +𝑡) at every neighbour and
𝜑(𝑝) ≡𝑠 −1(mod𝑚) at the
centre.
For a rational-valued function 𝑓
on the residue classes, subtract 𝑓(0) and multiply by a common denominator
of its values. Since ∑𝑛≥12−𝑛 =1, these operations
preserve whether the sum is rational. If 𝑓(𝑠 −1) ≠𝑓(0), the resulting bounded
integer sequence has an isolated nonzero coefficient for every 𝐿, so the lemma applies. For the
least-residue map, 𝑠 = −1 gives the
nonzero centre 𝑚 −2 when 𝑚 ≥3. For 𝑚 =2𝑘, the possible centres 𝑠 −1 run through every even
class. Thus any failure of constancy on those classes supplies a centre
with 𝑓(𝑠 −1) ≠𝑓(0). Conversely,
constancy makes every term after 𝑛 =2 equal 𝑐, giving 3𝑓(1)/4 +𝑐/4. ◻
The dyadic modulus matters to the classification. Modulo 6, for example, prime centres of this
form see only 𝑠 −1 ∈{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 𝑝 ≡1(mod𝑚). Wong gave the case in which the base equals the
modulus [5]. The
isolated-coefficient argument above also treats signed values of 𝑓 −𝑓(0), for which those nonnegative
sparse-series criteria need an additional spacing hypothesis. The extension
to other bases treats every integer 𝑡 ≥2 and proves rational linear
independence of 1 and ∑𝑛(𝜑(𝑛)mod𝑚)𝑡−𝑑𝑛, 𝑑 ≥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}∪{𝜑𝑗,𝑟:𝑗≥1, 0<𝑟<2𝑗, 𝑟 odd},𝜑𝑗,𝑟(𝑛)=𝜑(2𝑗𝑛+𝑟),
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 B2,𝑒.
Theorem 1.1 gives
independence, and its reductions give spanning. At level zero the sole
section 𝜑(𝑛) 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 𝐿1,…,𝐿𝑠 be pairwise
nonproportional affine forms with integer coefficients and positive
slopes. If 𝑤1,…,𝑤𝑠 are
rational-valued periodic sequences, then
∑𝑖𝑤𝑖(𝑛)𝜑(𝐿𝑖(𝑛))=0for all sufficiently large 𝑛⟹𝑤𝑖(𝑛)=0for every 𝑖,𝑛.
Proof. We choose a common period 𝑄 and restrict to 𝑛 =𝑟 +𝑄𝑡. The coefficients are now the
constants 𝑤𝑖(𝑟), and the cross
determinants are 𝑄(𝑎𝑖𝑏𝑗 −𝑎𝑗𝑏𝑖) ≠0. By shifting 𝑡
beyond the given threshold we can apply affine independence, obtaining
𝑤𝑖(𝑟) =0 for every 𝑖. We repeat this for each residue 𝑟; periodicity then gives the conclusion
even at the indices preceding the threshold. ◻
Proportional forms are excluded for a reason: the identity 𝜑(4𝑛 +2) =𝜑(2𝑛 +1) would
otherwise contradict the conclusion. Martin’s theorem gives the same
corollary on each progression [4].
Coons proves nonregularity using the poles of 𝜁(𝑠 −1)/𝜁(𝑠) [2]. The ranks above recover it:
finite rational kernel dimension would embed the integral kernel module
by evaluations in ℤ𝑑, making it
finitely generated; the converse is immediate (compare [3]). Allouche, Shallit and
Yassawi survey the earlier separation method [13].
The generating function 𝐹𝜑(𝑧) =∑𝑛≥1𝜑(𝑛)𝑧𝑛
therefore satisfies no 𝑘-Mahler
equation ∑𝑑𝑖=0𝑃𝑖(𝑧)𝐹𝜑(𝑧𝑘𝑖) =0
with 𝑃𝑖 ∈ℚ[𝑧], 𝑃0 ≠0. Indeed, 𝜑(𝑛) ≤𝑛 gives logarithmic height
at most log𝑛, and the height
theorem of Adamczewski, Bell and Smertnig would make such a series 𝑘-regular [16]. Bell and Smertnig’s
multiplicative classification gives the same conclusion [14]. Bell, Bruin and
Coons treat related algebraic and 𝐷-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 𝑇𝑖𝑔(𝑛) =𝑔(𝑘𝑛 +𝑖) satisfy
𝑇𝑖𝐹𝑗,𝑟=𝐹𝑗+1,𝑘𝑗𝑖+𝑟,𝑉𝑘,𝑒+1=𝑉𝑘,𝑒+𝑘−1∑𝑖=0𝑇𝑖𝑉𝑘,𝑒.
Every residue at
level 𝑗 +1 has the form 𝑘𝑗𝑖 +𝑟, giving the second identity. A
positive retained residue stays retained. For the zero-residue
generators, reduce 𝑇𝑖𝐹0,0 =𝐹1,𝑖 and 𝑇𝑖𝐹1,0 =𝐹2,𝑘𝑖 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 𝑆, the bound 0 ≤𝜑(𝑛) ≤𝑛 ensures convergence,
but forcing 2𝐿 ∣𝜑(𝑁 +𝐿)
with 𝑁 +𝐿 >1 requires 2𝐿 ≤𝑁 +𝐿 −1. The tail bound (𝑁 +𝐿 +2)2−𝐿 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 𝑅𝑁 =∑𝑗≥1𝜑(𝑁 +𝑗)2−𝑗 and
Δℎ(𝑁) =𝑅𝑁+ℎ −𝑅𝑁.
Subtracting the finite-prefix identities for 2𝑁+ℎ𝑆 and 2𝑁𝑆 gives
Δℎ(𝑁)≡2𝑁(2ℎ−1)𝑆(modℤ).(2)
If 𝑆 =𝑎/(2𝑐𝑣), with 𝑣 odd, then Δℎ(𝑁) is integral for 𝑁 ≥𝑐 and ℎ =𝜑(𝑣). 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 ℎ.
For ℎ,𝑁,𝐿 ∈ℕ, define the
integer
𝐷ℎ,𝑁,𝐿=𝐿−1∑𝑗=0(𝜑(𝑁+ℎ+1+𝑗)−𝜑(𝑁+1+𝑗))2𝐿−1−𝑗,𝐵=𝑁+ℎ+𝐿+2.
Since 0 ≤𝑅𝑀 ≤𝑀 +2, we have
2𝐿Δℎ(𝑁)−𝐷ℎ,𝑁,𝐿=𝑅𝑁+ℎ+𝐿−𝑅𝑁+𝐿,|2𝐿Δℎ(𝑁)−𝐷ℎ,𝑁,𝐿|≤𝐵.(3)
Both tails lie in [0,𝐵], so their difference has magnitude
at most 𝐵, not 2𝐵. The interval centred at 𝐷ℎ,𝑁,𝐿/2𝐿 with radius 𝐵/2𝐿 avoids every integer precisely when
𝐵<𝐷ℎ,𝑁,𝐿mod2𝐿<2𝐿−𝐵.(4)
This proves Δℎ(𝑁) ∉ℤ and, by (2), excludes every
reduced denominator dividing 2𝑁(2ℎ −1). For example, 𝐷1,12,16 = −143140 has residue 53468 modulo 216, and 𝐵 =31, so it excludes denominators
dividing 212. In ordinary
coordinates the same certificate reads
Δ1(12)∈[−14317165536,−14310965536]⊂(−3,−2).
For fixed ℎ,𝑁, the test is
complete: if 𝛿 =dist(Δℎ(𝑁),ℤ) >0,
then 2𝐿𝛿 >2𝐵 for all large
𝐿, since 𝐵 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 ℎ beyond every threshold.
Equivalent residue conditions
We write 𝐾(ℎ,𝑁,𝐿) for (4).
Theorem B.1 (Propagation of one nonintegral tail
difference). Fix 𝑑 ≥1 and
𝑁 ≥0. If Δ𝑑(𝑁) ∉ℤ, then every
sufficiently late pair {𝑡,𝑡 +1}
contains an 𝑚 such that 𝐾(𝑚𝑑,𝑁,𝑚𝑑) holds. Consequently
∃𝑡≥1: 𝐾(𝑡𝑑,𝑁,𝑡𝑑)⟺Δ𝑑(𝑁)∉ℤ.
Requiring
this for every 𝑑 ≥1,𝑁 ≥0 is
equivalent to 𝑆 ∉ℚ.
Completeness fixes ℎ,𝑁 and
varies 𝐿; here 𝐿 =ℎ =𝑡𝑑. A failed test puts Δ𝑡𝑑(𝑁) within 2(𝑁 +2𝑡𝑑 +2)2−𝑡𝑑 of ℤ. This bound tends to zero. The
recurrence Δ(𝑡+1)𝑑(𝑁) ≡2𝑑Δ𝑡𝑑(𝑁) +Δ𝑑(𝑁)(modℤ)
would transfer two consecutive errors to the fixed nonintegral Δ𝑑(𝑁). Its positive distance from
ℤ therefore rules out consecutive
failures for large 𝑡. The companion
proof gives the estimates. The final assertion still quantifies over
every 𝑑,𝑁, not one pair.
For a hypothetical denominator 2𝑐𝑣, a second test uses the modulus
𝑀 =(2𝐻 −1)/𝑣, where 𝐻 is a positive multiple of 𝜑(𝑣). Write 𝐵𝐻,𝑐 =∑𝐻−1𝑗=0𝜑(𝑐 +1 +𝑗)2𝐻−1−𝑗.
The identity 𝐵𝐻,𝑐 =𝑀(𝑣𝑅𝑐) −Δ𝐻(𝑐) puts 𝐵𝐻,𝑐 within 𝑐 +𝐻 +1 of 𝑀(𝑣𝑅𝑐). If 𝑆 =𝑎/(2𝑐𝑣), then 𝑣𝑅𝑐 ∈ℤ, so the residue lies near an
endpoint. For irrational 𝑆, the
fixed number 𝑣𝑅𝑐 has positive
distance from ℤ. The distance of
𝑀(𝑣𝑅𝑐) from 𝑀ℤ 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 𝑆 =𝑎/𝑞 for 0 <𝑞 ≤𝑄0 ≈7.96 ×1034.
Comparison sequences
Rationality and linear coefficient growth still permit exponential
carry rank. There is an integer sequence 𝑐 with 0 ≤𝑐(𝑛) ≤𝑛, unchanged odd totients and |𝑐(𝑛) −𝜑(𝑛)| ≤2 at even indices,
for which ∑𝑐(𝑛)2−𝑛 =5/4. Its
carry is the integer sequence
𝑢𝑁=4∑𝑗≥1𝑐(𝑁+𝑗)2−𝑗=5⋅2𝑁−4𝑁∑𝑛=1𝑐(𝑛)2𝑁−𝑛.
Its recurrence is
2𝑢𝑁−1 −𝑢𝑁 =4𝑐(𝑁) for 𝑁 ≥1. For 𝑗 ≥1 and odd 0 <𝑟 <2𝑗, this gives
4𝜑(2𝑗𝑛+𝑟)=2𝑢2𝑗𝑛+𝑟−1−𝑢2𝑗𝑛+𝑟.
Thus the 2𝑒 −1 independent
odd-residue totient sections lie in the span of the carry sections
through level 𝑒. 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 𝛽 ≥2, sparse even-index corrections
realise every value in an interval about ∑𝜑(𝑛)𝛽−𝑛, with a
prescribed prefix and all odd coefficients fixed. Errors are bounded by
any prescribed positive 𝑓(𝑛) →∞; 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:=∑𝑑≥1𝜇(𝑑)(2𝑑−1)2=𝑆−12
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
𝑄(𝑒,𝑌)=(∑𝑑≤𝑌𝜇(𝑑)/(2𝑑−1)𝑒+2)2∑𝑑≤𝑌𝜇(𝑑)/(2𝑑−1)2𝑒+2.
Theorem B.3 (A lower bound for the rank-one
quotients). For 𝑒 ≥1 and
𝑌 ≥4, the denominator of 𝑄(𝑒,𝑌) is positive, and the unique
minimiser is (𝑒,𝑌) =(1,5). Every
admissible quotient and every nonempty finite positive weighted average
of such quotients satisfies
𝑄−Θ2>21320.
The
uniform bound 𝑄 −Θ2 >1/15 is
false already at (1,5).
The proof
first makes the denominator uniformly positive. A geometric bound
handles all 𝑒 ≥2; at 𝑒 =1, seven-term prefixes leave only 𝑌 =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 <𝑞𝑗|Θ2 −𝑝𝑗/𝑞𝑗| →0, with
𝑝𝑗/𝑞𝑗 in lowest terms. Indeed, if
Θ2 =𝑎/𝑏, any nonzero
difference satisfies 𝑞𝑗|𝑎/𝑏 −𝑝𝑗/𝑞𝑗| =|𝑎𝑞𝑗 −𝑏𝑝𝑗|/𝑏 ≥1/𝑏. Convergence alone gives no such
contradiction.
An exponential-sum question
To prove irrationality, it suffices to show that for every ℎ ≥1 and every 𝑋0, some integers 𝑋 ≥max(𝑋0,1) and 𝐿 ≥ℎ satisfy
16(2𝑋+ℎ+𝐿+2)≤2𝐿,Re2𝑋−1∑𝑁=𝑋exp(2𝜋𝑖𝐷ℎ,𝑁,𝐿/2𝐿)≤910𝑋.(6)
The phases cannot all cluster near 1. If every residue failed (4), each 𝐷ℎ,𝑁,𝐿/2𝐿 would be within 1/16 of an integer. Each exponential
would then have real part at least cos(𝜋/8) >9/10. Thus some 𝑁 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 ℎ,𝑠 ≥1, 𝐿 ≥𝑠 +ℎ, 𝑋 ≥1 and 0 <𝜂 <1, and put 𝑡 =𝐿 −𝑠 +1 and 𝐸𝑁 =exp(2𝜋𝑖𝐷ℎ,𝑁,𝐿/2𝐿). For 𝑋 ≤𝑁 <2𝑋, let 𝑝𝑁 be the largest prime factor of 𝑁 +𝑡 and 𝑚𝑁 =(𝑁 +𝑡)/𝑝𝑁. Define
A={𝑁∈[𝑋,2𝑋):𝑚𝑁≤⌊√𝑋/2⌋, 𝑝𝑁>2⌊√𝑋⌋},G={𝑁∈A:𝜑(𝑚𝑁)≥𝜂𝑚𝑁}.
All indices are integers. On A, 𝑝𝑁 >𝑚𝑁, hence 𝜑(𝑁 +𝑡) =𝜑(𝑚𝑁)(𝑝𝑁 −1). Since
ℎ <𝑡 ≤𝐿, this term occurs in
both tails, with net coefficient 2−(𝑡−ℎ) −2−𝑡 =(2ℎ −1)/2𝑡. Write
𝑧𝑁=exp(2𝜋𝑖(2ℎ−1)𝜑(𝑚𝑁)(𝑝𝑁−1)2𝑡),𝑤𝑁=𝐸𝑁/𝑧𝑁,
and let ¯𝑧𝑚 be the average over the indices in A with cofactor 𝑚, or zero for an empty set. For fixed
𝑚, the exponent of 𝑧𝑁 is affine in 𝑝𝑁; 𝑤𝑁 contains the other totients.
Consider the four bounds
Re∑𝑁∈G𝑤𝑁(𝑧𝑁−¯𝑧𝑚𝑁)≤1425𝑋,|
|
|
|
|∑𝑁∈G𝑤𝑁¯𝑧𝑚𝑁|
|
|
|
|≤1100𝑋,|
|
|
|
|∑𝑁∈A∖G𝐸𝑁|
|
|
|
|≤1100𝑋,|
|
|
|
|
|∑𝑋≤𝑁<2𝑋𝑁∉A𝐸𝑁|
|
|
|
|
|≤825𝑋.(7)
These are an exact partition: outside G use the last two sums; on
G write 𝑤𝑁𝑧𝑁 =𝑤𝑁(𝑧𝑁 −¯𝑧𝑚𝑁) +𝑤𝑁¯𝑧𝑚𝑁. The bounds add to (14/25 +1/100 +1/100 +8/25)𝑋 =9𝑋/10.
The last three bounds are available at a common depth. Take the least
𝐿 ≥𝑠 +ℎ satisfying the size
inequality in (6). The smooth-number
and small-cofactor estimates give the last two bounds for all large
𝑋 when 0 <𝜂 <1/(300log4). The elementary
excluded-cofactor estimate is (3𝜂log4 +𝑜(1))𝑋; it needs no prime
number theorem. With the prime number theorem as input, the group-mean
estimate gives the second bound for 𝑠 =26, 𝜂 =1/1000 at this depth and all large
𝑋. The first bound remains
open.
Small group means control the second sum by the triangle inequality
because |𝑤𝑁| =1. They do not
control the first: subtracting ¯𝑧𝑚 cancels an unweighted group sum, not one with
varying 𝑤𝑁. No independence is
assumed. For example, 𝑧 =(1, −1) has
mean zero, but the weights 𝑤 =(1, −1)
make ∑𝑤𝑁(𝑧𝑁 −¯𝑧) =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𝑋/25 norm bound.
Problem C.1 (Four estimates for the first-harmonic
sum). For each ℎ ≥1, do there
exist 𝑠 ≥1 and 0 <𝜂 <1 such that, for every 𝑋0, there are 𝑋,𝐿 with
max(𝑋0,1)≤𝑋,ℎ≤𝐿−𝑠,16(2𝑋+ℎ+𝐿+2)≤2𝐿,
for which those four bounds hold?
Fix 𝑠,𝜂 after ℎ but before 𝑋0; all four estimates must hold on the
same block. At 𝑠 =26, 𝜂 =1/1000 and the least admissible
𝐿, it suffices to prove the first
bound for arbitrarily large 𝑋: the
other three hold eventually on those same blocks.
A weaker sufficient condition needs no group-mean input. Since |G| >67𝑋/100 for large 𝑋, the open bound Re∑𝑁∈G𝐸𝑁 ≤603𝑋/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 ℎ 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 𝜑(𝑛)/𝑛,
uniformly for |ℎ| ≤𝑥/2 [11]. Their correlation is a
product of two normalised totient values. Here the modulus grows with
𝐿, and 𝑤𝑁 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 𝑘-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 𝑘-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.
Plectis