Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Totient-window discrepancy and period-avoidance certificate

Definition
Erdos249257_TotientTailPeriodKiller

by willcook · Sep 24, 2026 · Mathlib c5ea003 (Lean v4.30.0)

definitionerdos-257

This bundle defines an integer totient-window discrepancy, a decidable certificate requiring its residue modulo 2^L to avoid an explicit neighborhood of zero, and the certificate’s decidability instance.

Definition code
import Mathlib.Algebra.BigOperators.Field
import Mathlib.Analysis.SpecificLimits.Normed
import Mathlib.Data.Nat.Factorization.Basic
import Mathlib.Data.Nat.Totient
import Mathlib.FieldTheory.Finite.Basic
import Mathlib.NumberTheory.Real.Irrational
import Mathlib.Tactic.FieldSimp
import Mathlib.Tactic.GCongr
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.NormNum
import Mathlib.Tactic.Positivity

/-!
# The totient-tail period killer: attacking #249 through the period, not the digits

Every earlier wave asked the Erdős–Borwein question of `S = ∑ φ(n)/2ⁿ`: force a
long block of zero binary digits.  Wave 20 measured why that fails — the
totient's 2-adic staircase affords `√(2·log₂ N)` silent positions where the
proof engine needs `log₂ N`.  This file changes the TARGET.  Rationality of `S`
is equivalent to *eventual periodicity* of its binary expansion, and
periodicity is a statement about the local totient tail

  `R_N = ∑_{j≥1} φ(N+j)/2ʲ`,      because `2^N·S = Φ_N + R_N` with `Φ_N ∈ ℕ`.

If `S = P/Q` then for `h` with `oddPart Q ∣ 2ʰ - 1` and every `N ≥ v₂(Q)`,

  `R_{N+h} - R_N ∈ ℤ`   —   the **tail-period law**.

Killing a period is a FINITE, decidable act.  With the window discrepancy

  `A_{h,N,L} = ∑_{j=0}^{L-1} (φ(N+h+1+j) - φ(N+1+j))·2^{L-1-j}`

we get `R_{N+h} - R_N = A/2^L + E`, `|E| ≤ (N+h+L+2)/2^L`, so whenever the
residue `A mod 2^L` lands outside the radius-`(N+h+L+2)` neighbourhood of `0`,
the difference is provably NOT an integer (`tail_diff_notMem_int_of_certifiedKill`).
The forbidden zone has width `O(N)` inside a modulus `2^L ≈ N³`: the old proof
had to HIT a measure-zero target, this one only has to MISS a vanishing one.

The reduction is complete (`irrational_totient_series_of_certificate_supply`):
a supply of certified kills — for every period `h` and every threshold `N₀`
some certified `(N ≥ N₀, L)` — proves #249.  As a first unconditional deposit,
`certifiedKill_all_small` machine-checks kills for every `h ≤ 8` at `N = 12`,
`L = 16`, so `S` is not a rational whose denominator divides `2¹²·(2ʰ-1)` for
any `h ≤ 8` (`totient_series_ne_rat_of_den_dvd`).

Everything here is elementary: `φ(n) ≤ n`, geometric tails, and integer
window arithmetic.  No q-Padé, no Stern–Brocot, no unformalised citations.
-/

namespace Erdos249257
namespace TotientTailPeriodKiller

open Finset





/-- The window discrepancy `A_{h,N,L} = ∑_{j=0}^{L-1} (φ(N+h+1+j) - φ(N+1+j))·2^{L-1-j}`:
the depth-`L` truncation of `2^L·(R_{N+h} - R_N)`. -/
def windowDiscrepancy (h N L : ℕ) : ℤ :=
  ∑ j ∈ Finset.range L,
    ((Nat.totient (N + h + 1 + j) : ℤ) - (Nat.totient (N + 1 + j) : ℤ)) * 2 ^ (L - 1 - j)

/-- The decidable period-killer certificate: the residue of `A_{h,N,L}` modulo `2^L`
avoids the radius-`(N+h+L+2)` neighbourhood of `0`. -/
def certifiedKill (h N L : ℕ) : Prop :=
  (N + h + L + 2 : ℤ) < windowDiscrepancy h N L % 2 ^ L ∧
    windowDiscrepancy h N L % 2 ^ L < 2 ^ L - (N + h + L + 2)



instance (h N L : ℕ) : Decidable (certifiedKill h N L) :=
  inferInstanceAs (Decidable (_ ∧ _))

/-! ## Geometric-linear summability spine -/













/-! ## The shift identity: `2^N · S = Φ_N + R_N` -/



/-! ## Truncation: partial window plus bounded tail -/







/-! ## Certificate soundness: a good residue kills integrality -/





/-! ## Rationality forces the tail-period law -/





/-! ## The reduction, and the first unconditional deposits -/









end TotientTailPeriodKiller
end Erdos249257
Source
Lean source (Apache-2.0): https://github.com/wcook04/plectis-erdos-lean/blob/c93c2e4dd86a2e317e0cb650ea244fee1afd59c2/Erdos249257/TotientTailPeriodKiller.lean#L1-L422 Related paper by Will Cook (CC-BY-4.0): https://github.com/wcook04/plectis-erdos/blob/6917e15ec4abc2623512254da93221e446eeb707/paper/257/erdos-257-mersenne-support-subseries.tex#L1-L75 Paper's authorship and AI-use disclosure: https://github.com/wcook04/plectis-erdos/blob/6917e15ec4abc2623512254da93221e446eeb707/paper/paper-house-style.sty#L180-L188 Erdős's earlier reciprocal-summable criterion is credited in the paper: https://github.com/wcook04/plectis-erdos/blob/6917e15ec4abc2623512254da93221e446eeb707/paper/257/erdos-257-mersenne-support-subseries.tex#L104-L110

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me