A Basis for the 2-Kernel of Euler's Totient

A nearby 2026 totient theorem has different coordinates.

Kaneko, Suzuki and Tachiya prove that if $f(n)$ is a nonnegative integer sequence of infinite support with $\sum_{n\le x}f(n)=O(x(\log x)^\delta)$, then, for every integer $t\ge2$, both $$\sum_{n\ge1}\frac{f(n)}{t^{\sigma(n)}} \qquad\text{and}\qquad \sum_{n\ge1}\frac{f(n)}{t^{\varphi(n)}}$$ are irrational [5]. This includes substantial families of totient-related series, but $\varphi(n)$ occurs in the . Problem #249 instead places $\varphi(n)$ in the coefficient of $2^{-n}$. The theorem therefore supplies a genuine adjacent result and a useful warning against a tempting misidentification; it does not settle or reduce the displayed problem.

Exact identities and representations.

Several neighbouring Dirichlet-convolution identities are rational and exactly computable. Writing $L(g):=\sum_{d\ge1}g(d)/(2^d-1)$, we have $\sum_{d\ge1}\mu(d)/(2^d-1)=\tfrac12$ () and $\sum_{d\ge1}\varphi(d)/(2^d-1)=2$ (). These belong to two distinct one-step Möbius-convolution chains: $$L(\mathbf 1)=E\ \longmapsto\ L(\mu)=\tfrac12, \qquad L(\varphi)=2 \ \longmapsto\ L(\varphi*\mu)=S.$$ Thus $S$ is one convolution step from the rational value $L(\varphi)=2$, not from $E$; the parallel chains show that this transformation need not preserve rationality. The squared-denominator representation $S=\tfrac12+\sum_{d\ge1}\mu(d)/(2^d-1)^2$ () converges fast enough to recompute the decimal above.

There is also an exact probabilistic reading, and it is more than a gloss. Let $X$ and $Y$ be independent fair-coin geometric waiting times on $\mathbb{N}_{>0}$. Then $$S=\tfrac12+\Pr[\gcd(X,Y)=1]$$ (), the probability being the visible-coprime-pair series $\sum_{\gcd(m,n)=1}2^{-(m+n)}$. That probability is related to a distribution over the Stern–Brocot tree in a completely explicit way. For positive coprime $(a,b)$ put $w_{a,b}=1/(2^{a+b}-1)$. These reduced-slope masses sum to exactly $1$ (), and at each node $(a,b)$ the cylinder mass $1/((2^a-1)(2^b-1))$ splits exactly into its stop mass and the masses of its two children (). The coprimality probability is not that total mass; rather, $$S-\tfrac12 =\sum_{\substack{a,b\ge1\\(a,b)=1}}2^{-(a+b)} =\sum_{\substack{a,b\ge1\\(a,b)=1}} \bigl(1-2^{-(a+b)}\bigr)w_{a,b}.$$ It is therefore the expectation of the conditional primitive-pair factor $1-2^{-(a+b)}$ under the self-similar reduced-slope probability law. What is missing is not structure; it is an arithmetic consequence of the structure.

Prior work

For an integer $k\ge2$, the of a sequence $c$ is $\{n\mapsto c(k^jn+r):j\ge0,\ 0\le r<k^j\}$, and $c$ is when the module generated by its $k$-kernel is finitely generated; both notions are due to Allouche and Shallit ([1]). Their Theorem 2.2 gives equivalent finite-kernel and matrix characterisations, and Theorem 3.1 proves closure under convolution  [1]; neither result controls the finite-level rank of a sequence that is not $k$-regular. Coons proved that $\varphi$ is not $k$-regular for any $k\ge2$ ([2], Theorem 3.2, pp. 348–349, in the published version; Theorem 3.3, pp. 8–9, in the preprint, which numbers its results on a single running counter). Bell and Smertnig reach a further negative conclusion, and by a different route rather than by strengthening that one: their Theorem 1.3 shows that a $k$-Mahler series with multiplicative coefficients has a $k$-regular coefficient sequence in an explicit closed form, and that the totient generating series is not $k$-Mahler for any $k\ge2$ follows directly from the closed form [4].

A separate line of work settles linear independence of totient values along affine progressions, and settles it more strongly than anything proved here. Martin [3] assumes only that $a_1,\dots,a_m$ are positive integers and that $a_ib_j\neq a_jb_i$ for $i\neq j$, and proves in his Theorem 1 that for every constant $C>0$ the simultaneous ratio gaps $$\frac{\varphi(a_1n+b_1)}{\varphi(a_2n+b_2)}>C,\quad\dots,\quad \frac{\varphi(a_{m-1}n+b_{m-1})}{\varphi(a_mn+b_m)}>C$$ hold on a set of positive lower density; he also notes that the hypotheses are symmetric in the forms, so every one of the $m!$ orderings occurs on such a set. Taking $C>\bigl(\sum_{i\neq t}|c_i|\bigr)/|c_t|$ after moving a channel with $c_t\neq0$ to the front shows at once that $$\bigl\{n\mapsto\varphi(a_in+b_i)\bigr\}_{i=1}^m$$ is linearly independent over $\mathbb{R}$, hence over $\mathbb{Q}$. His Corollary 4 carries Theorem 1 and its corollaries to $\sigma$. Every affine-totient independence statement used below is therefore a consequence of Martin’s theorem, and no originality is claimed for it. Martin does not state the exact finite-level rank, the explicit basis, or the complete relation normal form; the present section derives them by combining his theorem with the reductions below. Coons and Bell–Smertnig likewise do not state those finite-level conclusions.

Coons’s statement is about the union over all levels: no finite set of sections generates the rest. Bell and Smertnig’s is about a functional equation.

One consequence of Coons’s theorem should be recorded explicitly, because it bounds what the present section may claim. For a subgroup $M\subseteq\mathbb{Z}^{\mathbb{N}}$ of integer-valued sequences, finite generation over $\mathbb{Z}$ is to finite dimension of its $\mathbb{Q}$-span. One direction is immediate. For the other, choose $\mathbb{Q}$-independent $m_1,\dots,m_d\in M$ and evaluation points $n_1,\dots,n_d$ with $D:=\det[m_i(n_j)]\neq0$, necessarily a nonzero integer; for $x\in M$ Cramer’s rule applied to the integer system $x(n_j)=\sum_i a_im_i(n_j)$ places every $a_i$ in $\tfrac1D\mathbb{Z}$, so $M\subseteq\tfrac1D\bigl(\mathbb{Z} m_1+\dots+\mathbb{Z} m_d\bigr)$, and over the principal ideal domain $\mathbb{Z}$ a submodule of a finitely generated module is finitely generated. (The familiar obstruction, that $\mathbb{Z}[\tfrac12]$ has rank one without being finitely generated, cannot occur here: an integer-valued sequence bounds its own denominators through its values at small indices.)

Hence : it is equivalent to Coons’s non-$k$-regularity and follows from it. Only the finite-level statements are additional. Knowing that a span is not finitely generated says nothing about its dimension at a given truncation, nor about which relations hold there; what is added here is that the dimension through level $e$ is exactly $2^e+1$, that an explicit family is a basis, and that the two elementary reductions generate every relation. We found no prior source giving any of those three for $\varphi$; that is the outcome of a search, not a proof of non-existence, and no priority is claimed.

The evaluation-matrix argument of the next subsection is an independent and more constructive route to the same independence, which is why it is retained.

Parity-separated evaluation matrices

is proved by exhibiting a square matrix of values of the sections whose determinant is nonzero, and the linear algebra at its centre is simpler than the arithmetic construction that feeds it. We give the linear algebra first, then the arithmetic input it consumes.

Evaluate the sections at one point apiece to get a square matrix $M$, and suppose each column $j$ admits a fixed power $2^{d_j}$ dividing every entry of that column such that, after dividing the column through by it, the diagonal entry is odd and every off-diagonal entry is even; call such an $M$ a . The normalised matrix is then the identity modulo $2$; its determinant is odd, hence nonzero, and the sections are independent (). Producing evaluation points with exactly that parity pattern is what the arithmetic input is for, and it is the harder half. The Chinese remainder theorem together with Dirichlet’s theorem on primes in arithmetic progressions makes one of the evaluated affine values prime, which fixes the exact power of $2$ dividing the diagonal entry, while every other value receives a fresh prime divisor congruent to $1$ modulo a large power of two, which supplies the one extra factor of two that the off-diagonal entries need (). Even residues never enter, because the second reduction has already carried them to odd residues at lower levels ().

then needs only two further steps, and both are short. Linear independence is a property of finite subfamilies, so the level-$e$ statement, applied with $e$ above the largest level occurring in a given finite subset, already gives independence of the whole infinite family $\mathcal B$. And the two reductions carry every remaining section onto a rational multiple of a member of $\mathcal B$, so the spans agree. That the assembly is short is the point: the level-$e$ theorem was always the whole content, and stating its consequence as infinite-dimensionality understated it. The sharp form is a basis.

A prime-orbit sufficient condition.

The hypothesis for cofinally many primes $p$ at which the first tail-orbit exponential has real part strictly below $9/10$. Granting it, follows, and then . The $9/10$ hypothesis is weaker than the earlier $4/5$ hypothesis, but no instance of this cofinal hypothesis is proved. Section  states the sharper form in which this hypothesis is now available.

Finite Euler-factor identities.

The local coefficients are $$\eta(0)=1,\qquad \eta(1)=-2,\qquad \eta(2)=1,\qquad \eta(e)=0\quad(e\ge3),$$ the coefficients of $(1-X)^2$. For a prime $p$ and $e\ge0$, write $\sigma_p(e)=1+p+\cdots+p^e$. The two local Euler factors are $$1-\frac2p+\frac1{p^2}=\left(1-\frac1p\right)^2, \qquad 1-\frac2{p^2}+\frac1{p^4} =\left(1-\frac1{p^2}\right)^2$$ at and . On the prime-power divisor-sum row, $$\sigma_p(1)-2\sigma_p(0)=p-1$$ (), and for every $e\ge0$, $$\sigma_p(e+2)-2\sigma_p(e+1)+\sigma_p(e) =p^{e+1}(p-1)$$ (). For example, at $p=3$ the values $\sigma_3(0),\ldots,\sigma_3(3)=1,4,13,40$ give $4-2=2$ and $40-2\cdot13+4=18=3^2(3-1)$. Thus convolution with $\mu\ast\mu$ converts the prime-power divisor-sum row into the corresponding totient row at every finite stage. These are finite algebraic identities; no transcendence conclusion is attached to them.

Mixed differences of cyclotomic layers.

For a function $F:\{0,1\}^2\to\mathbb{Z}$, define $$\Delta F=F(1,1)-F(1,0)-F(0,1)+F(0,0)$$ (). If $F(i,j)=u(i)+v(j)$, then $\Delta F=0$ (). Conversely, among integer linear combinations of the four values of $F$ whose coefficients sum to zero along each row and each column, the pattern $(1,-1,-1,1)$ is forced up to scale (). For example, the table $$\begin{array}{c|cc} &0&1\\ \hline 0&9&13\\ 1&12&16 \end{array}$$ has mixed difference $16-12-13+9=0$; increasing only the lower-right entry by $5$ changes the mixed difference to $5$. The uniqueness statement is internal to this fixed $2\times2$ stencil. It does not assert invariance under larger stencils, nonlinear functionals, or another representation.

The formal development also records and . The two unproved hypotheses and their target conclusion are as follows. For $C:\mathbb{N}\to\mathbb{N}$ and $m,d\in\mathbb{N}$, put $$\begin{aligned} \operatorname{Layer}(C,m)\quad\Longleftrightarrow\quad& \exists Q_0\ \forall q\ge Q_0,\quad q\ \mathrm{prime}\Longrightarrow\\[-2pt] &\hspace{5em}1<C(mq)\ \text{ and }\ \gcd(C(mq),mq)=1. \end{aligned}$$ $$\begin{aligned} \operatorname{BoundedOrder}(C,m,d)\quad\Longleftrightarrow\quad& \forall q,p,\quad q,p\ \mathrm{prime},\ p\mid C(mq)\Longrightarrow\\[-2pt] &\hspace{3em}\exists k,\quad 1\le k\le d\ \text{ and }\ mq\mid p^k-1. \end{aligned}$$ $$\begin{aligned} \operatorname{FinitePrimeEscape}(C,m)\quad\Longleftrightarrow\quad& \forall\text{ finite sets }S\text{ of primes},\ \exists Q_0\ \ \forall q\ge Q_0,\\[-2pt] &\hspace{3em}q\ \mathrm{prime}\Longrightarrow \forall p\in S,\quad p\nmid C(mq). \end{aligned}$$ These are the linked predicates , , and . The bounded-order condition does not assert an exact multiplicative order; it asserts only the displayed divisibility for some $k\le d$.

The implication from bounded order to finite-prime escape is a size argument in the paper. If $m=0$, the bounded-order condition forces $C(0)=1$. If $m>0$, the assertion is immediate for $S=\varnothing$; otherwise choose $Q_0$ so that $mQ_0>\max_{p\in S}(p^d-1)$. For every prime $q\ge Q_0$, a divisor $p\in S$ of $C(mq)$ would give $mq\mid p^k-1$ for some $k\le d$, hence $mq\le p^k-1\le p^d-1$, a contradiction. The layer hypothesis separately ensures that the layers are nontrivial and coprime to their indices. Neither hypothesis is proved here; polynomial-resultant realisability and Archimedean growth are also not established.

Exact equivalent formulations

By , formulation  is equivalent to irrationality of $S$. It identifies an exact decidable witness family, but is not claimed to reduce the difficulty of Erdős #249. A finite list of successful certificates establishes the predicate only on its tested scales. Conversely, one pair $h>0$, $N$ with $R_{N+h}-R_N\in\mathbb{Z}$ already makes $S$ rational ().

The certificate is decidable at each $t$, and is kernel-checked at the $28$ listed scales between $t=1$ and $t=64$ (, ). The current pinned source strengthens that historical list to every $t\le82$, with no gaps (). The theorem through $t=82$ supplies no instance at $t=83$ and does not discharge the cofinal quantifier.

The cyclotomic form exposes more arithmetic structure. Write $C(n)=|\Phi_n(2)|$.

This is . For the binary layers, clean anchors satisfying every condition before the certificate are already supplied, and identifies formulation  with irrationality of $S$. The unknown is phase escape of the totient discrepancy modulo $2^L$, not large prime divisors or multiplicative order. The checked $p=331$ instances are finite models of this exact predicate; unbounded support alone does not imply it.

Stronger sufficient producer problems

This is the depth-locked predicate . It is stronger than the exact period-multiple characterisation because the certificate depth is forced to equal the period. A positive answer proves irrationality through ; a negative answer eliminates this route only.

This four-term problem is a producer-level decomposition beneath the direct fixed-full-block first-harmonic gap, not the external theorem interface itself. The constitutional outward question is the full-block constant-saving estimate for the first additive character of the totient window discrepancy; the supplier-fibre split is one exact way to try to produce that estimate. Failure of this decomposition would retire only this producer, not the full-block socket and not Erdős Problem #249.

To make the question self-contained, put $$\omega_N=\exp\!\left(2\pi i\, \frac{D_{h,N,L}\operatorname{mod} 2^L}{2^L}\right),\qquad X\le N<2X.$$ At the pivot argument $N+L-s+1$, call $N$ a supplier when this integer factors as $mp$, where $p$ is its largest prime factor, $0<m\le\sqrt X/2$, and $p>2\sqrt X$. Suppliers are good when $\eta m\le\varphi(m)$ and bad otherwise; non-suppliers form the remaining set. Writing $t=L-s+1$, the canonical fibre with cofactor $m$ is exactly the image of the primes in $$X+t\le mp<2X+t$$ under the injective map $p\mapsto mp-t$ (, , ). This exact bijection does not imply that the supplier prime is isolated from every other argument in the window. At $X=16$, $L=20$, $s=1$, $m=2$, and $N=18$, the pivot is $38=2\cdot19$, while the same prime $19$ divides the distinct argument $N+1=19$ (). For a supplier write $z_N$ for its explicit totient pivot phase, $w_N=\omega_N/z_N$, and $\bar z_m$ for the mean of $z_N$ on the fibre with cofactor $m$. Define $$\begin{aligned} \mathcal C&=\sum_{N\ {\mathrm{good}}}w_N(z_N-\bar z_m),& \mathcal M&=\sum_{N\ {\mathrm{good}}}w_N\bar z_m,\\ \mathcal B&=\sum_{N\ {\mathrm{bad}}}\omega_N,& \mathcal U&=\sum_{N\ {\mathrm{nonsupplier}}}\omega_N. \end{aligned}$$ The exact identity is $\sum_{X\le N<2X}\omega_N=\mathcal C+\mathcal M+\mathcal B+\mathcal U$, and Problem  asks precisely for $$\operatorname{Re}\mathcal C\le\frac{14}{25}X,\qquad |\mathcal M|\le\frac1{100}X,\qquad |\mathcal B|\le\frac1{100}X,\qquad |\mathcal U|\le\frac8{25}X.$$ The decomposition is , and the four budgets imply irrationality by . An obstruction showing that available first- and second-moment information cannot force this modulo-$2^L$ small-ball estimate would also decisively close the present harmonic route.

Structural and Diophantine routes

Rationality of $S$ would produce exactly such an integral tempered orbit, while the checked transport theorem forces its rank to be at least $2^e-1$ at every level. Thus a positive answer proves irrationality. A negative answer should ideally construct a control recurrence with the same integrality and decay architecture and near-maximal dyadic rank; infinite dimension of the totient $2$-kernel alone is not enough.

For a separate denominator-compression route, define the Möbius–Mersenne ladder $$\Theta_r=\sum_{d\ge1}\frac{\mu(d)}{(2^d-1)^r}, \qquad \Theta_2=S-\frac12.$$ The positive rank-one family has already been excluded at a quantitative scale: every admissible monomial quotient, and every positive finite average of them, exceeds $\Theta_2$ by more than $1/480$ (, ).

Ordinary convergence of rational approximants is insufficient; the scaled error is the Diophantine quantity. The words “genuinely coupled” exclude the positive rank-one and positive direct-sum mechanisms already separated from $\Theta_2$ by the uniform gap.

Independent extension

This subsection previously posed the odd-prime kernel dimension as an open problem. It is now a theorem, and for every integer base rather than for odd primes only. The statement below combines Lean-checked arithmetic, spanning, and conditional-rank layers with a paper-level independence argument. Lean proves the zero-residue relation () and the exact division-free composite-base reduction (). It also proves unique quotient/nonzero-digit coordinates for each admissible fixed-level residue and that the resulting finite index has cardinality $k^e+1$. The new conditional layer proves that the canonical family spans the complete truncation and that its linear independence implies exact rank $k^e+1$. These are respectively span_allBaseTotientKernelThroughLevelFamily_eq_canonical and finrank_allBaseTotientKernelThroughLevelFamily_eq_of_linearIndependent in Erdos249257/TotientKernelConditional.lean; their immutable source links are added after the module lands in the paper’s pinned snapshot. The antecedent of the second statement is explicit and is not discharged in Lean. The paper obtains it from Martin’s external positive-density theorem through the elementary linear-independence consequence recorded above.

The checked composite-base statement is deliberately cross-multiplied by $\varphi(\gcd(k,u))$; the displayed scalar is the equivalent paper-level normalisation after exact division. Lean also checks that this scalar is nonzero and gives the exact one-step functional reduction allBaseTotientKernelSeq_mul_residue_step in Erdos249257/TotientKernelConditional.lean. Thus the zero channel, arithmetic reduction, finite-index/cardinality, spanning, and conditional-rank layers have kernel receipts. Martin remains the external authority for the linear-independence input and hence for the unconditional basis and rank conclusion of Theorem .

The selection condition is $k\nmid r$, not $\gcd(k,r)=1$; for composite $k$ a basis residue may share prime factors with $k$. Independence is obtained by restricting to $n=km+1$, where the surviving channels become the affine forms $L_0(m)=km+1$ and $L_{j,r}(m)=k^{j+1}m+(k^j+r)$ with $k\nmid r$. These have positive slopes and satisfy $a_ib_j\neq a_jb_i$, so Martin’s Theorem 1 [3] applies through the linear-independence consequence recorded in the prior-work subsection. The two zero-residue channels are proportional on that progression and are separated afterwards by evaluating at $n=k$, using $\varphi(k^2)=k\varphi(k)$ and $\varphi(k)<k$.

At $k=2$ this recovers the dyadic rank theorem of Section ; at $k=\ell$ an odd prime it gives the case first posed here. Neither Coons’s non-$k$-regularity theorem nor the Bell–Smertnig Mahler classification supplies a finite-level rank, a basis, or the relations, so Theorem  is not a consequence of either. A targeted literature search located no source stating the exact rank, the basis, or the normal form; that is a search result and not a novelty claim, and the statement remains subject to specialist review.

A proof of formulation  gives irrationality of $S$ by . Its negation settles #249 in the opposite direction: it supplies a positive-shift integral tail difference, which forces rationality. By contrast, failure of the sufficient producer bounds would rule out only their respective routes.

Logical status and analytic input

1. Irrationality of $S$ (). No proof is claimed.

2. The lcm-diagonal and clean cyclotomic-anchor statements are exact equivalent formulations of : they convert irrationality into the existence of an unbounded family of finite tail-difference certificates. Finite instances are checked — every $t\le82$, including the historical $28$-scale bank of Section  — and the unbounded family is not. The equivalences fix the exact missing quantifier but do not make that quantifier easier to prove. is a finite instance of a family, the gap certificates of , which reach irrationality by a one-way implication; the two families should not be counted together.

3. Full-depth period-multiple escape and the four first-harmonic pivot bounds are stronger sufficient producers; they, and the prime-orbit gap the pivot bounds refine, are unproved. Failure of either would refute only that route.

4. Carry-rank compression and genuinely coupled denominator compression are separate contradiction targets. No required upper bound or coupled approximant family is proved.

5. The $k$-kernel rank statement of Theorem  is independent of the irrationality problem and settles nothing about it. Its zero-residue, composite-base arithmetic, finite-index/cardinality, and spanning layers are Lean-checked. Lean also checks the exact-rank theorem under an explicit linear-independence hypothesis. That hypothesis remains a paper deduction from Martin’s Theorem 1; Martin’s theorem is not formalised. No source was located for the rank, basis, or normal form themselves; that search result is not a priority verdict.

The correlation source that fits the normalised totient most directly is Balasubramanian–Giri–Srivastav [7], not a direct transfer of the Tao–Teräväinen method. Write $$g(n)=\frac{\varphi(n)}n =\sum_{d\mid n}\frac{\mu(d)}d=(f*1)(n), \qquad f(d)=\frac{\mu(d)}d\in\mathcal A_1 ,$$ the class $\mathcal A_1$ being the coefficient class in which the theorem cited next is stated. Theorem 2.2 of the arXiv version of [7] gives, uniformly for $|h|\le x/2$, an explicit asymptotic for $\sum g(n)g(n-h)$ with error $O(\log^2x)$; Remark 2.4 gives its Euler product, For each fixed $h$, the weighted partial-summation formula immediately following Corollary 2.8 permits $Q(n)=n(n-h)$, restoring the two linear factors needed to return from $g(n)g(n-h)$ to $\varphi(n)\varphi(n-h)$ with an explicitly propagated error. That displayed weighted formula is not itself stated uniformly in $h$ and starts its main integral at $1$, not $H$; retaining uniformity and the lower endpoint would require applying partial summation directly to Theorem 2.2. No later claim here relies on an unproved uniform weighted version.

Tao–Teräväinen’s quantitative correlation theorem (, Theorem 3.1) assumes either quantitative equidistribution together with an exact small-prime condition, or non-pretentiousness. Here $g(p)=1-1/p$, so the stated small-prime condition does not hold, while $\sum_p(1-g(p))/p=\sum_p1/p^2<\infty$, so $g$ is pretentious to the constant function. Their theorem therefore does not apply unchanged. The Balasubramanian–Giri–Srivastav theorem supplies the missing first- and second-moment input in the correct divisor-convolution class, but it does supply the residue small-ball or phase anti-concentration estimate needed to turn those moments into a certificate. That modulo-$2^L$ step is the precise remaining analytic gap; no irrationality conclusion is drawn from the correlation asymptotic alone.