The Binary Totient Series

Will Cook

Long paper

The Binary Totient Series

Erdős #249 By Will Cook July 2026; revised 1 October 2026 Authorship, AI use and citation

PDFOpen the PDF, 163 pages TeXLaTeX source Source on GitHub Problem page

Summary. The dyadic totient sections through level $e \geq 1$ have an explicit rational basis of size $2^{e} + 1$ . Truncating a scaled tail difference produces an integer whose residue certifies nonintegrality when its distances from both endpoints of the residue interval exceed an explicit error bound. The record develops the resulting finite denominator exclusions, equivalent residue criteria, and sufficient exponential-sum estimates. Rational comparison sequences identify the limitations of particular size, parity, rank, and finite-prefix arguments. The short paper supplies the all-base basis theorem; here each conditional result carries the arithmetic hypothesis still needed to apply it. Those hypotheses are not established in the form required to prove irrationality of S=∑ $φ (n) 2^{- n}$ .

This paper covers a claim-bounded problem-specific reasoning surface for Erdős #249: selected checked premises, finite certificates, closed routes, surviving obligations, and their exact evidence bands.

It does not establish the validity of claims tagged Lean, which belongs to the cited kernel-checked source, or a solution to Erdős #249, which remains open.

Start here, by the editorial route

In this paper

Totient sections and tail differences

Put $φ (0) = 0$ and $N = {0, 1, 2, \dots}$ . At base two, $φ (4 n) = 2 φ (2 n)$ and $φ (4 n + 2) = φ (2 n + 1)$ leave five independent sequences among the seven sections through level two. More generally, the sections through level $e \geq 1$ have the basis $φ (n)$ , $φ (2 n)$ and $φ (2^{j} n + r)$ with $1 \leq j \leq e$ and odd $0 < r < 2^{j}$ , of size $2^{e} + 1$ . The all-base theorem in the short paper gives rank $k^{e} + 1$ and integral coordinates. Its retained positive residues satisfy $k ∤ r$ ; coprimality with $k$ is unnecessary.

The coefficient relations are finite linear identities. The series question asks whether a particular infinite weighted sum can be rational. Put

S := \sum_{n \geq 1} \frac{φ (n)}{2^{n}} = \frac{1}{2} + \frac{1}{4} + \frac{2}{8} + \frac{2}{16} + \frac{4}{32} + \dots = 1.3676308019850223 \dots

The series converges absolutely because $φ (n) \leq n$ . Erdős Problem #249 asks whether $S$ is irrational, which remains open. The comparisons below test proposed passages from coefficient structure to the value of this sum. Each retains specified properties while making the corresponding sum rational. It therefore defeats an argument using only those properties, not every argument that might also use the arithmetic of the totient.

Throughout, a cofinal condition means that a witness exists beyond each threshold. It need not hold at every sufficiently large index. Each comparison sequence is used only for the properties it preserves; agreement with a fixed totient prefix, for example, imposes no multiplicativity condition on the continuation.

Remark 1.1 (Earlier coefficient results). Erdős and Graham record the irrationality question for $S$ [10]. An integer sequence is $k$ -regular when the $Z$ -module generated by its sections $n \mapsto c (k^{j} n + r)$ , $j \geq 0$ and $0 \leq r < k^{j}$ , is finitely generated. Coons proved that $φ$ is not $k$ -regular for any $k \geq 2$ [2]. Martin’s Theorem 1 implies that the functions $n \mapsto φ (a_{i} n + b_{i})$ are linearly independent for pairwise nonproportional affine forms with positive integer slopes [4]. The exact ranks in §10.8, together with the all-base normal form in the short paper, identify the retained sections and every relation among them. The independence itself is not claimed as new. The CRT–Dirichlet separation method is already present in Yazdani’s Theorem 2 and proof, which explicitly credit Shallit [30]; our evaluation matrix uses one such separation for each column. Yazdani also proves non-automaticity of $φ (n) mod m$ for every $m \geq 3$ in every base [30]. Allouche, Shallit and Yassawi give a survey account [31].

To test rationality, we remove the finite prefix, which becomes an integer after multiplication by $2^{N}$ . Write $2^{N} S = Φ_{N} + R_{N}$ with $Φ_{N} := \sum_{n = 1}^{N} φ (n) 2^{N - n} \in N$ and $R_{N} := \sum_{j \geq 0} φ (N + 1 + j) / 2^{j + 1} \in [0, \infty)$ (Erdos249257.TotientTailPeriodKiller.totientTail, two_pow_mul_totient_series_eq). If $S = a / (2^{c} v)$ with $c \geq 0$ and $v \geq 1$ odd, Euler’s theorem gives $h = φ (v) > 0$ and $N_{0} = c$ such that $R_{N + h} - R_{N} \in Z$ for every $N \geq N_{0}$ (Erdos249257.TotientTailPeriodKiller.eventual_period_of_not_irrational). Indeed,

R_{N + h} - R_{N} \equiv 2^{N} (2^{h} - 1) S (\mod) Z,

and the right side is integral for those choices.

Thus it suffices, for every positive shift $h$ , to find arbitrarily large $N$ for which $R_{N + h} - R_{N}$ is not an integer. A finite test is obtained by truncating this difference. Throughout, $a mod m$ denotes the least nonnegative residue, and an unqualified index in a sum is a nonnegative integer. For $h, N, L \in N$ , write

D (h, N, L) := \sum_{j < L} (φ (N + h + 1 + j) - φ (N + 1 + j)) 2^{L - 1 - j} \in Z,

the depth- $L$ truncation of $2^{L} (R_{N + h} - R_{N})$ , and

C (h, N, L) :⟺ (N + h + L + 2) < D (h, N, L) mod 2^{L} < 2^{L} - (N + h + L + 2),

a decidable condition (Erdos249257.TotientTailPeriodKiller.windowDiscrepancy, Erdos249257.TotientTailPeriodKiller.certifiedKill).

The omitted tails satisfy the exact identity

2^{L} (R_{N + h} - R_{N}) - D (h, N, L) = R_{N + h + L} - R_{N + L} .

Both tails are nonnegative, so their difference is bounded in absolute value by the larger bound $B = N + h + L + 2$ , not the sum of their bounds. The two strict inequalities in $C (h, N, L)$ keep the resulting error interval away from every multiple of $2^{L}$ ; hence $R_{N + h} - R_{N} \notin Z$ . Conversely, a fixed noninteger difference has a fixed positive distance $δ$ from $Z$ . Since $2^{L} δ > 2 B$ eventually, some depth detects it. Completeness concerns detection of an existing difference, not existence of the differences required below (Erdos249257.TotientTailPeriodKiller.exists_certifiedKill_iff_tail_diff_notMem_int). The resulting quantified condition is the following.

Definition 1.2 (The quantified residue condition).

Sep :⟺ \forall h \geq 1 \forall N_{0} \exists N \geq N_{0} \exists L, C (h, N, L) .

$Sep ⟺ S \notin Q$ (irrational_totient_series_iff_certificate_supply). The equivalence identifies the missing quantified input; it supplies no certificate by itself.

One successful $(h, N, L)$ excludes reduced denominators dividing $2^{N} (2^{h} - 1)$ . To exclude an arbitrary rational value, its odd denominator first determines a shift and its power of two determines a threshold; only then may we choose the witness $N, L$ . This is the order in $Sep$ . The depth must grow with $N$ , since success requires $2 (N + h + L + 2) < 2^{L}$ . A large enough depth makes the interval test possible, but does not make the actual residue lie inside it. A failed test at one depth likewise does not prove integrality. Erdos249257.TotientTailPeriodKiller.certifiedKill_depth_floor

Unconditional results

Reduced coefficients

About this paper

Authorship and AI use. Will Cook built and directed the research infrastructure and maintains the public release. He reviewed claims when he could. AI agents did most of the research and drafting. Cook did not independently verify every claim.

Cite and contact. Cite this paper by its title, author and date above, with its PDF; cite the earlier sources it uses for a mathematical result. For software, use the release citation and give the commit used. Contact Will with questions or corrections.

Prefer the manuscript?

PDFOpen the PDF, 163 pages TeXOpen the LaTeX source Problem page

Equations typeset from the exact TeX. Rendered from the LaTeX manuscript source with file fingerprint sha256:2be13b340f9dafc4. Its file fingerprint matched the published source record, so the PDF above, the LaTeX, and this page are one manuscript. Redeploying the site regenerates this page from whatever the public repository holds at that moment.