Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Greatest prime factor, divisor closure, and the totient measure

Definition
BFFPyramidal_arithmetic

by burkh4rt · Sep 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricscoset-partitionsgroup-theoryherzog-schonheim

Three arithmetic notions used in the multiplicity bound.

For a natural number mmm, the greatest prime factor P(m)P(m)P(m) is the largest prime dividing mmm, with the convention P(0)=P(1)=0P(0) = P(1) = 0P(0)=P(1)=0 (the supremum of an empty set of primes). This is the function written PPP in Berger–Felzenbaum–Fraenkel; the least prime factor, written ppp there and appearing in the definition of a pyramidal group, is a different function (Mathlib's Nat.minFac).

For a finite set RRR of positive integers, the divisor closure is

D(R)  =  { d:d∣m for some m∈R },D(∅)=∅.D(R) \;=\; \{\, d : d \mid m \text{ for some } m \in R \,\}, \qquad D(\emptyset) = \emptyset .D(R)={d:d∣m for some m∈R},D(∅)=∅.

The totient measure of a finite set SSS of naturals is

μ(S)  =  ∑m∈Sφ(m),\mu(S) \;=\; \sum_{m \in S} \varphi(m),μ(S)=m∈S∑​φ(m),

the measure determined by μ({m})=φ(m)\mu(\{m\}) = \varphi(m)μ({m})=φ(m), where φ\varphiφ is Euler's totient function. The two interact through Gauss's identity ∑d∣mφ(d)=m\sum_{d \mid m}\varphi(d) = m∑d∣m​φ(d)=m, which says precisely that μ(D({m}))=m\mu(D(\{m\})) = mμ(D({m}))=m.

Formalization note. DDD and μ\muμ are Finset operations: Finset.biUnion of Nat.divisors, and a Finset.sum of Nat.totient. Since Nat.divisors 0 = ∅, a member 000 of RRR contributes nothing, whereas in the source every ddd divides 000; the two readings agree on sets of positive integers, which is the only case used here, the members of RRR being orders of subgroups. Because D(R)D(R)D(R) is a set, equal orders are collapsed — μ(D(R))\mu(D(R))μ(D(R)) depends on the set of orders, not on their multiplicities.

Definition code
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
Source
Berger--Felzenbaum--Fraenkel 1987, Remark on the multiplicity of a partition of a group into cosets, Fund. Math. 128 (1987) 139-144, https://doi.org/10.4064/fm-128-3-139-144, p. 139 (the function PPP) and p. 141, eqs. (9)-(10), with eq. (13) Gauss's identity
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 mmm,

P(m)  =  sup⁡{ q:q∈primeFactors⁡(m) },P(m) \;=\; \sup\{\,q : q \in \operatorname{primeFactors}(m)\,\},P(m)=sup{q:q∈primeFactors(m)},

where primeFactors⁡(m)\operatorname{primeFactors}(m)primeFactors(m) is Mathlib's finite set of primes dividing mmm, and the supremum is taken in N\mathbb{N}N over the identity function on that finite set, with the convention that the supremum of the empty finite set is 000 (the bottom element of N\mathbb{N}N). So for m≥2m \ge 2m≥2, P(m)P(m)P(m) is the largest prime dividing mmm; and in the two boundary cases the set of prime factors is empty, giving

P(0)=0,P(1)=0.P(0) = 0, \qquad P(1) = 0.P(0)=0,P(1)=0.

(Mathlib's primeFactors⁡(0)=∅\operatorname{primeFactors}(0) = \varnothingprimeFactors(0)=∅, so 000 is treated as having no prime factors even though every prime divides 000.) The value is always a natural number; no subtraction or division occurs.

2. Divisor closure. For a finite set R⊆NR \subseteq \mathbb{N}R⊆N,

D(R)  =  ⋃m∈Rdivisors⁡(m),D(R) \;=\; \bigcup_{m \in R} \operatorname{divisors}(m),D(R)=m∈R⋃​divisors(m),

a finite set of natural numbers, where divisors⁡(m)\operatorname{divisors}(m)divisors(m) is Mathlib's finite set of positive divisors of mmm. Boundary behaviour: D(∅)=∅D(\varnothing) = \varnothingD(∅)=∅; and since divisors⁡(0)=∅\operatorname{divisors}(0) = \varnothingdivisors(0)=∅ in Mathlib, the element 0∈R0 \in R0∈R contributes nothing to the union (i.e. 000 is not treated as being divisible by everything, and 000 itself never appears in D(R)D(R)D(R)). Also divisors⁡(1)={1}\operatorname{divisors}(1) = \{1\}divisors(1)={1}. Note the union ranges over m∈Rm \in Rm∈R only, so D(R)D(R)D(R) consists exactly of those d≥1d \ge 1d≥1 such that d∣md \mid md∣m for some m∈Rm \in Rm∈R with m≥1m \ge 1m≥1; membership of RRR itself in D(R)D(R)D(R) holds only for the positive members of RRR. 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 S⊆NS \subseteq \mathbb{N}S⊆N,

μ(S)  =  ∑m∈Sφ(m),\mu(S) \;=\; \sum_{m \in S} \varphi(m),μ(S)=m∈S∑​φ(m),

a natural number, where φ\varphiφ is Mathlib's Euler totient. The sum is over the distinct elements of the finite set SSS (no multiplicities). Boundary values: μ(∅)=0\mu(\varnothing) = 0μ(∅)=0; φ(0)=0\varphi(0) = 0φ(0)=0 in Mathlib, so an element 0∈S0 \in S0∈S contributes nothing; φ(1)=1\varphi(1) = 1φ(1)=1. 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 μ(D({m}))=m\mu(D(\{m\})) = mμ(D({m}))=m mentioned in a comment is not stated or proved anywhere here, nor is any claim about PPP. 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.

Human review
  • Endorsed by Shuze Chen · Sep 13, 2026

  • Endorsed by burkh4rt · Sep 13, 2026

    Confirmed by the mission captain (proposal self-audit).

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