Multiplicity of a coset partition of a pyramidal group
ProvedBFFPyramidal.multiplicity_boundMain theorem (Berger-Felzenbaum-Fraenkel). Let be a pyramidal group and suppose the cosets , , with and , partition . If , then at least
of the subgroups have the same order, where
is the greatest prime factor and is Euler's totient function.
Since for , this proves the conjectures of Herzog-Schönheim and of Burshtein for pyramidal groups; the authors had previously established the Herzog-Schönheim conjecture for finite nilpotent groups, which form a subclass.
Formalization note. The conclusion is stated as the existence of an order such that the number of indices with is at least ; counting indices (not distinct subgroups) is the faithful reading, since several may coincide. The floor is natural-number division. The hypothesis is necessary: for the partition is itself, , and the bound degenerates.
import Mathlib import Definitions.Def_BFFPyramidal_pyramidal import Definitions.Def_BFFPyramidal_arithmetic import Definitions.Def_BFFPyramidal_cosetPartition
namespace BFFPyramidal
theorem multiplicity_bound {G : Type*} [Group G] [Finite G] (hG : IsPyramidal G)
{t : ℕ} (ht : 1 < t) (K : Fin t → Subgroup G) (a : Fin t → G)
(hpart : IsCosetPartition K a) :
∃ m : ℕ, (maxPrimeFac (modulus K) * Nat.totient (modulus K)) / modulus K + 1
≤ (Finset.univ.filter fun i => Nat.card (K i) = m).card := by
sorry
end BFFPyramidal
Read-back
What the Lean code literally says, in plain math · claude-opus-5
Read-back:
BFFPyramidal.multiplicity_boundShape of the declaration. The statement quantifies, in this order, over: a type in an arbitrary universe (implicit, inferred from later arguments); an instance-implicit group structure on ; an instance-implicit witness that is finite; an explicit hypothesis asserting is pyramidal in the custom sense unfolded below; an implicit natural number ; an explicit hypothesis (strict, so ; and are excluded); an explicit family of subgroups indexed by ; an explicit family of group elements indexed by the same finite index set; and an explicit hypothesis that the left cosets partition . The conclusion is an existential over a natural number .
Unfolding "pyramidal" (). The hypothesis says: there exist a natural number and a function — a total function on all of , so its values at indices are unconstrained — such that
and for every with (strictly), both
where the index used is Mathlib's relative index of in (the index of in , which under the stated containment is the ordinary index ), is the cardinality of the subgroup as a type, and is the least prime factor of with the conventions and . Descent is not required to be strict; in particular is allowed, in which case the two boundary conditions force and there are no step conditions, so the trivial group is pyramidal. No normality, solvability, or supersolvability is asserted or assumed.
Unfolding "coset partition" (). The hypothesis says: for every there is a unique index with , i.e. every element of lies in exactly one of the left cosets . The indices are distinct even when the cosets coincide as sets, so uniqueness of forbids repeating the same coset twice; the subgroups themselves may repeat.
Unfolding the modulus. Write
where and are the cardinalities of and of each subgroup, and the gcd is taken over the whole finite index set (for this set is nonempty; had been the empty gcd would be and the division would be the junk value ). The division is truncating natural-number division; since each divides , the quotient here is in fact exact and . This is the quantity called the modulus.
Unfolding the greatest prime factor. denotes the supremum of the finite set of prime factors of , taken in with the empty supremum equal to ; hence , and otherwise is the largest prime dividing .
The conclusion. There exists a natural number (unconstrained: need not be positive, prime, a divisor of , or the order of any ) such that
where is Euler's totient (, ), the division is truncating natural-number division, the is added after truncation, and the right-hand side is the number of indices whose subgroup has cardinality exactly . The inequality is non-strict, and its left-hand side does not depend on .
Degenerate and boundary behaviour. The left-hand side is always at least . It equals exactly whenever — for instance when (then , , so the left side is ), and more generally whenever the truncated quotient vanishes. In all such cases the conclusion asserts only that some natural number is the order of at least one of the subgroups , which holds because the index set is nonempty (); choosing suffices. Also for , so the truncated quotient never exceeds , and the left-hand side is bounded above by . Because is finite, every , so the choice always yields count . The auxiliary definitions
divisorClosure(the divisor closure of a finite set of naturals) andmuMeasure(the totient-sum measure) from the imported arithmetic file do not appear in the statement. The proof issorry(the theorem is stated but not proved in this artifact).Hypothesis usage as visible in the statement. The conclusion mentions only , , and the cardinalities of and the ; the elements occur only inside , and (pyramidality) constrains only . Whether or is needed for the inequality is not determined by the statement itself; both are assumed.
Confirmed by the mission captain (proposal self-audit).