Mathlib v4.30 source proposition Nat.totient_dvd_of_dvd

Identifier: F:ml430-nat-totient-dvd-of-dvd-9622e44a
Proof route: kernel-lean
External status: proved
Axiom footprint: Empty

Recorded description

The proposition declared as `Nat.totient_dvd_of_dvd` in the pinned Mathlib v4.30 source.

Formal statement

∀ {a b : ℕ}, a ∣ b → a.totient ∣ b.totient

Dependencies

The graph shows direct ledger edges. Follow a node to open its artifact page.

1 direct dependencies 1 direct dependents

Evidence

kernel-Nat.totient_dvd_of_dvd

Kind: kernel-term
Status: checked

Supports: a | b -> totient a | totient b, with the whole rendered type pinned.

Checker command

test "$(cargo run -q -p axeyum-lean-kernel --example nat_theorem_inventory -- totient_dvd_of_dvd 2>/dev/null | tr '\t' ' ' | grep -Fc 'Nat.totient_dvd_of_dvd 3 ((x0 : AxNat) -> ((x1 : AxNat) -> ((x2 : AxNat.dvd x0 x1) -> AxNat.dvd (AxNat.totient x0) (AxNat.totient x1))))')" -ge 1

Evidence notes

The grep pins the WHOLE rendered type, including which side of the divisibility is which. Verified both directions with /usr/bin/grep -Fc explicitly (not the interactive-shell ugrep): the real name gives count 1; a fabricated name (`totient_dvd_of_dvd_nonexistent_xyz`) gives count 0, so `test ... -ge 1` fails as required. `nat_theorem_inventory` keeps only the LAST of several name arguments if more than one is passed (measured 2026-08-30), so exactly one name is passed here.

engine-Nat.totient_dvd_totient_mul

Kind: kernel-term
Status: checked

Supports: The fully general, hypothesis-free engine this theorem is built from: forall k a, totient a | totient (a*k), with no divisibility hypothesis at all.

Checker command

test "$(cargo run -q -p axeyum-lean-kernel --example nat_theorem_inventory -- totient_dvd_totient_mul 2>/dev/null | tr '\t' ' ' | grep -Fc 'Nat.totient_dvd_totient_mul 2 ((x0 : AxNat) -> ((x1 : AxNat) -> AxNat.dvd (AxNat.totient x1) (AxNat.totient (AxNat.mul x1 x0))))')" -ge 1

Evidence notes

The grep pins the WHOLE rendered type rather than just the name, because `totient_dvd_totient_mul` is a substring of the sibling `totient_dvd_totient_mul_prime` -- an unanchored name-only grep on this pair's inventory output matches BOTH lines (measured 2026-08-30). By well-founded induction on the cofactor k (Nat.lt), chaining Nat.totient_dvd_totient_mul_prime along a factorisation of k supplied one prime at a time by Nat.exists_prime_dvd. No factor multiset is ever named (ADR-0668). Built with Nat.zero_or_succ rather than the plain-Nat.rec cases_zero_succ combinator, because the well-founded induction hypothesis needs an actual equation linking the fixpoint's bound variable to its shape, which only zero_or_succ supplies.

instances-Nat.totient_dvd_of_dvd

Kind: exhaustive-enumeration
Status: checked

Supports: a | b -> totient a | totient b holds for every 1 <= a, b < 60; the hypothesis is load-bearing (fails at 2634 non-dividing pairs, smallest (3,1)).

Checker command

python3 scripts/tests/check-totient-dvd-chain-numerics.py

Evidence notes

Checks 1 and 2 of the new script; check 2N asserts the a|b hypothesis is genuinely load-bearing. Check 1 covers the underlying engine (Nat.totient_dvd_totient_mul) with NO hypothesis at all, over a=0..59, k=0..59, including the a=0 degenerate corner via an explicit `divides` helper (a=0 divides only b=0) rather than a buggy short-circuit that was caught and fixed while writing the script.

footprint-nat-prelude

Kind: exhaustive-enumeration
Status: checked

Supports: axiom_footprint: [] -- the Nat prelude's trusted surface is empty, which bounds this theorem.

Checker command

cargo run -q -p axeyum-lean-kernel --example nat_axiom_inventory -- --require-axiom-free nat

Evidence notes

`--require-axiom-free` exits non-zero when the named prelude's trusted surface (Axiom + Opaque + Quotient) is non-empty, and errors rather than passing silently for a prelude the run never built. Measured 2026-08-30: `nat: axiom=0 opaque=0 quotient=0 total_trusted=0`, exit 0.

Provenance

{
  "date": "2026-08-30",
  "established_by": "axeyum-lean-kernel nat_prelude::totient_dvd_chain (totient-dvd-chain lane)",
  "source": "statement was extracted from Mathlib v4.30.0 (statement-only, no proof value exposed); the proof here is constructed independently in this kernel via a prime-peeling well-founded induction over the cofactor, per ADR-0668 -- it does NOT reconstruct Mathlib's Euler-product proof, which this kernel cannot state (no List/Finset/product type for unique factorisation).",
  "prior_art": [
    {
      "who": "the Mathlib contributors",
      "what": "the theorem declaration `Nat.totient_dvd_of_dvd`",
      "where": "mathlib4 commit c5ea00351c28e24afc9f0f84379aa41082b1188f (v4.30.0)",
      "year": 2026,
      "attribution": "the proposition was read from the pinned statement-only inventory; the proof term and tactic trace were not consulted, and the proof actually built here uses a different route (prime-peeling induction, not the Euler product)."
    }
  ]
}