Greatest prime factor, divisor closure, and the totient measure
DefinitionBFFPyramidal_arithmeticThree arithmetic notions used in the multiplicity bound.
For a natural number , the greatest prime factor is the largest prime dividing , with the convention (the supremum of an empty set of primes). This is the function written in Berger–Felzenbaum–Fraenkel; the least prime factor, written there and appearing in the definition of a pyramidal group, is a different function (Mathlib's Nat.minFac).
For a finite set of positive integers, the divisor closure is
The totient measure of a finite set of naturals is
the measure determined by , where is Euler's totient function. The two interact through Gauss's identity , which says precisely that .
Formalization note. and are Finset operations: Finset.biUnion of Nat.divisors, and a Finset.sum of Nat.totient. Since Nat.divisors 0 = ∅, a member of contributes nothing, whereas in the source every divides ; the two readings agree on sets of positive integers, which is the only case used here, the members of being orders of subgroups. Because is a set, equal orders are collapsed — depends on the set of orders, not on their multiplicities.
import Mathlib
namespace BFFPyramidal
/-- The greatest prime factor `P m` of a natural number `m`, as the supremum of its set of
prime factors. Since that set is empty for `m = 0` and `m = 1`, the convention here is
`P 0 = P 1 = 0`.
Note that this is the *greatest* prime factor, written `P` in Berger–Felzenbaum–Fraenkel; the
*least* prime factor, written `p` there, is Mathlib's `Nat.minFac` and is what the definition of
a pyramidal group uses. -/
def maxPrimeFac (m : ℕ) : ℕ := m.primeFactors.sup id
/-- The **divisor closure** `D R = {d : d ∣ m for some m ∈ R}` of a finite set of naturals;
equation (10) of Berger–Felzenbaum–Fraenkel, with `D ∅ = ∅`.
Caveat on the boundary: Mathlib's `Nat.divisors 0 = ∅`, so a member `0` of `R` contributes
nothing, whereas in the source every `d` divides `0`. The two readings agree on sets of
*positive* integers, which is the only case in which `D` is used here — in the applications the
members of `R` are orders of subgroups. -/
def divisorClosure (R : Finset ℕ) : Finset ℕ := R.biUnion Nat.divisors
/-- The measure `μ S = ∑_{m ∈ S} φ m` determined by `μ {m} = φ m`, where `φ` is Euler's totient;
equation (9) of Berger–Felzenbaum–Fraenkel. Gauss's identity `∑_{d ∣ m} φ d = m` says exactly
that `μ (D {m}) = m`. -/
def muMeasure (S : Finset ℕ) : ℕ := ∑ m ∈ S, Nat.totient m
end BFFPyramidal
Read-back
What the Lean code literally says, in plain math · claude-opus-5
Read-back — Def_BFFPyramidal_arithmetic.lean
This file contains no theorems: it asserts nothing. It declares three total, computable functions inside a namespace BFFPyramidal, importing all of Mathlib. Each takes exactly one explicit argument, no implicit arguments, and no typeclass (instance-implicit) assumptions; there are no hypotheses of any kind, no positivity or finiteness side conditions, and no quantifiers beyond the single explicit argument of each definition. Consequently every definition is defined on all inputs of its argument type, including the degenerate ones, and the values at those degenerate inputs are whatever the formulas below produce — there is no side condition excluding them. The doc-comments attached to the definitions are prose only and carry no logical force; below I describe only what the code computes.
1. Greatest prime factor. For a natural number ,
where is Mathlib's finite set of primes dividing , and the supremum is taken in over the identity function on that finite set, with the convention that the supremum of the empty finite set is (the bottom element of ). So for , is the largest prime dividing ; and in the two boundary cases the set of prime factors is empty, giving
(Mathlib's , so is treated as having no prime factors even though every prime divides .) The value is always a natural number; no subtraction or division occurs.
2. Divisor closure. For a finite set ,
a finite set of natural numbers, where is Mathlib's finite set of positive divisors of . Boundary behaviour: ; and since in Mathlib, the element contributes nothing to the union (i.e. is not treated as being divisible by everything, and itself never appears in ). Also . Note the union ranges over only, so consists exactly of those such that for some with ; membership of itself in holds only for the positive members of . The definition is stated for a Finset ℕ, so no finiteness hypothesis is needed — finiteness is built into the type.
3. The totient measure. For a finite set ,
a natural number, where is Mathlib's Euler totient. The sum is over the distinct elements of the finite set (no multiplicities). Boundary values: ; in Mathlib, so an element contributes nothing; . No subtraction or division appears, so no truncation issues arise.
Nothing in the file relates these three definitions to one another: in particular the identity mentioned in a comment is not stated or proved anywhere here, nor is any claim about . All three definitions are unconditional, and no definition is used by another (they are mutually independent). The only imported file is all of Mathlib; there are no sibling-file dependencies.
Confirmed by the mission captain (proposal self-audit).