Skip to content

Erdős Problem #249

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, irrationality.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

Documentary explanation. Editorial acceptance is determined by the protected V2 admissions ledger and the exact manuscript source hash. This article does not confer mathematical certification.

The question in plain language

Let \(\phi(n)\) be Euler's totient function: the number of integers from \(1\) through \(n\) that are coprime to \(n\). Erdős asks whether the real number

\[ S=\sum_{n\ge 1}\frac{\phi(n)}{2^n} \]

is irrational, meaning that there are no integers \(a\) and \(b\ne0\) with \(S=a/b\). The series converges absolutely because \(0\leq\phi(n)\leq n\) and

\[ \sum_{n\ge1}\frac{n}{2^n}=2. \]

The quantifier is over every positive integer \(n\), with the fixed denominator base \(2\). It is not a question about whether many partial sums are nonintegral, nor about the decimal expansion merely looking irregular. A rational number has an eventually periodic expansion in every integer base; the difficulty is proving enough global nonperiodicity for this particular coefficient sequence.

The formal-provider version writes the sum over \(n:\mathbb N\). Under the usual convention \(\phi(0)=0\), this is the same real number, but that reindexing is a normalization fact that should be proved in a formal development, not silently treated as the original wording. The formal declaration also leaves the proposition under answer(sorry).

A small example

The first ten totients are

\[ \bigl(\phi(1),\ldots,\phi(10)\bigr)=(1,1,2,2,4,2,6,4,6,4). \]

Exact rational arithmetic therefore gives

\[ \sum_{n=1}^{10}\frac{\phi(n)}{2^n}=\frac{87}{64}=1.359375. \]

This is a finite certificate, not an answer to the infinite question. If \(S_N\) denotes the sum through \(N\), then the elementary bound \(\phi(n)\le n\) gives

\[ 0<S-S_N\leq\sum_{n>N}\frac{n}{2^n}=\frac{N+2}{2^N}. \]

For a second, exact check, keep only the terms whose index is a power of two. Since \(\phi(2^m)=2^{m-1}\) for \(m\ge1\), the subseries is

\[ T=\sum_{m\ge1}\frac{\phi(2^m)}{2^{2^m}}=\sum_{m\ge1}2^{-(2^m-m+1)}. \]

Its first terms are \(1/4,1/8,1/64,1/8192\), at binary positions \(e_m=2^m-m+1\). These positions are strictly increasing because

\[ e_{m+1}-e_m=2^m-1>0. \]

There is exactly one binary \(1\) at each of these positions and no carrying between positions. The gaps tend to infinity. If \(T\) were rational, its binary expansion would be eventually periodic. An eventually periodic binary sequence with infinitely many occurrences of the digit \(1\) has bounded gaps between successive \(1\) digits, contradicting \(e_{m+1}-e_m\to\infty\). Thus this separate subseries is irrational. This elementary lemma is independently checked here; it is not a proof about \(S\), because the omitted positive terms can change binary digits through carries.

What is known

The original sources do not give a solution. P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory (1980), identify the problem on printed p. 61 and describe the irrationality as probably hopeless to prove at that time. P. Erdős, “On the irrationality of certain series: problems and results” (1988), pp. 102–109, repeats the question on p. 102 and says that its irrationality was probably unattackable by his methods. These are historical problem/status remarks, not theorem statements proving rationality or irrationality.

The maintained page currently still presents the problem as open, has no proof exposition and zero proof claims, and links the same two references. Its page history displays a 2025-10-20 version while the page metadata says it was last edited 28 September 2025; this is editorial-date drift, not a changed mathematical statement. The page also has later user comments that are explicitly unverified by the site. One records the valid-looking convolution identity

\[ S=\sum_{n\ge1}\frac{\mu(n)}{(2^n-1)^2}+\frac12, \]

which is a reformulation, not a denominator exclusion or irrationality proof. Another gives the powers-of-two lemma above. A September 2026 comment reports bounded-coefficient and tail-separation results, while explicitly leaving the original universal condition open and noting that its notes have not had independent mathematical review. These are useful leads and partial deductions, not classical solutions.

GCL's current state

The protected source packet is original issue #1518, whose authenticated comment RESULT/1 has disposition BOUNDED_TASK_DESIGNED. It records the exact positive-index statement, the \(n=0\) normalization, the two primary sources, and the finite example and subseries lemma. Its authority is source-audit evidence and a bounded research design; it is not a proof certificate, editorial acceptance, or current-literature completeness claim.

The protected catalogue entry at teorth/erdosproblems commit 5364087 says informal status open, formal status unformalized, and statement metadata formalized: yes, all last updated 2025-08-31. The current catalogue head 76848ed retains those fields. “Formalized” means that a statement has been encoded; it does not mean solved.

The pinned formal file at google-deepmind/formal-conjectures commit 85f8637 declares Irrational (∑' n : ℕ, (φ n) / (2 ^ n)) behind answer(sorry). The current head 817d8a7 changes module/public wrappers but not that open proposition. A separate provider issue #5037 reports formally proved neighbouring identities and a finite denominator exclusion, while stating that the open problem file remains sorry; no external Lean pointer is treated here as GCL certification.

What remains

The original task remains to decide whether \(S\notin\mathbb Q\). A finite computation, a tail bound, the convolution identity, an irrational subseries, or a large finite denominator exclusion does not supply that decision. In particular, irrationality of \(T\) does not pass to \(S=T+(S-T)\): an arbitrary real remainder can cancel the relevant digit pattern, even though all terms here are positive.

A useful bounded successor task is to formalize the subseries lemma with explicit hypotheses: prove \(\phi(2^m)=2^{m-1}\), prove the formula and strict growth of \(e_m\), and invoke the eventual-periodicity characterization for rational binary expansions. Its acceptance condition must explicitly say that it proves only \(T\notin\mathbb Q\). A stronger task would need a quantified tail or denominator argument that controls all indices, not just the sparse powers of two. Any such argument should be checked against carries, the \(n=0\) convention, and the exact ambient type of the formal sum.

The live comments and linked external notes may contain useful source-limited deductions, but their reported formal proofs, code, or Lean references require replay and scope comparison before they can support a claim about the original problem. No current source inspected here supplies that missing closure.

Sources and claim boundaries

The exact ten-term arithmetic and the lacunary lemma above are finite, independently reproducible deductions. The eventual-periodicity fact is standard; no deep lemma is presented as original GCL work. Classical source remarks, live unverified partial deductions, reported formal variants, and the still-open original proposition are deliberately kept separate. Any editorial acceptance is recorded separately in the protected admissions ledger; no claim of proof, priority, novelty, or formal certification is implied.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1518 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction