Coset partitions and their modulus
DefinitionBFFPyramidal_cosetPartitionA family of left cosets of subgroups , indexed by , is a coset partition of when every element of lies in exactly one of them; equivalently the cosets are pairwise disjoint and cover . These are the objects of the Herzog-Schönheim conjecture and, for , the exact covering systems of the integers.
Attached to a finite family of subgroups of a finite group is the modulus
the quantity in terms of which the multiplicity bound of Berger, Felzenbaum and Fraenkel is stated.
Formalization note. Membership in the coset is expressed as , and the partition condition is a ∃! over the index type, which encodes disjointness and covering at once. The family is an indexed family rather than a set of cosets, so repetitions among the remain visible; this matters because the conclusion of the main theorem counts indices, not distinct subgroups. The gcd is taken over Finset.univ of the index type Fin t, and the division is natural-number division (exact here, since the gcd divides ).
A further note on boundary behaviour: uniqueness is uniqueness of the index , so a family that repeats a coset (equal and equal at two different indices) does not satisfy the predicate, which is the intended reading of "partition". The index type is unconstrained, so it may be infinite; if it is empty the predicate is false rather than vacuously true, since is nonempty. For the modulus degenerates to , the gcd over an empty family being ; all statements that use it assume .
import Mathlib
namespace BFFPyramidal
/-- A family of left cosets `a i • K i`, indexed by `i : ι`, **partitions** the group `G`:
every element of `G` lies in exactly one of them. -/
def IsCosetPartition {G : Type*} [Group G] {ι : Type*}
(K : ι → Subgroup G) (a : ι → G) : Prop :=
∀ x : G, ∃! i : ι, (a i)⁻¹ * x ∈ K i
/-- The quantity `l = |G| / gcd (|K i| : i)` attached to a finite family of subgroups;
equation (4) of Berger–Felzenbaum–Fraenkel. -/
noncomputable def modulus {G : Type*} [Group G] [Finite G] {t : ℕ}
(K : Fin t → Subgroup G) : ℕ :=
Nat.card G / (Finset.univ.gcd fun i => Nat.card (K i))
end BFFPyramidal
Read-back
What the Lean code literally says, in plain math · claude-opus-5
Read-back
BFFPyramidal.IsCosetPartition
This is a definition (a predicate, i.e. a Prop-valued function), not a theorem. It takes:
- an implicit type (universe-polymorphic), together with an instance-implicit assumption that carries a group structure (no commutativity, no finiteness, no nontriviality assumed — the trivial group is allowed);
- an implicit index type (universe-polymorphic, with no finiteness, nonemptiness, or decidability assumption whatsoever — may be empty, finite, or infinite);
- an explicit family , i.e. a subgroup for each index (the are not assumed distinct, nor of finite index, nor proper, nor pairwise anything);
- an explicit family of group elements (no assumption on them; e.g. they may all be equal, or equal to the identity).
The predicate is declared to hold exactly when
Unfolding the "exists unique" quantifier literally, this says: for every there is an index with , and moreover for every index satisfying one has .
The membership condition is equivalent to , the left coset of by (the translating element multiplies on the left; the right-coset version is not what is written). So the predicate says: every element of lies in the left coset for exactly one index .
Two points about the exact strength of this, as written. First, uniqueness is uniqueness of the index, not of the coset: if but as subsets of (for instance if and , or simply if the family repeats), then every in that common coset has two admissible indices, and the predicate is false, even though the underlying family of sets does cover with pairwise disjoint-or-equal pieces. Second, the statement bundles covering and disjointness together: existence gives , and uniqueness gives for all .
Degenerate cases. If is empty, the condition fails, because is always nonempty (it contains ); so the predicate is false for the empty index type — it is not vacuously true. If is a singleton , the predicate reduces to , i.e. . If is the trivial group, the predicate holds precisely when is a singleton. No hypothesis in the definition is impossible to satisfy: the predicate is satisfiable (e.g. a singleton and ), and also refutable, so it is a genuine nontrivial condition.
BFFPyramidal.modulus
This is also a definition, not a theorem: a natural-number-valued (and declared noncomputable) quantity. It takes:
- an implicit type (universe-polymorphic), with instance-implicit assumptions that is a group and that is finite;
- an implicit natural number (any , including );
- an explicit family , i.e. subgroups of indexed by the canonical -element type (again with no assumption that they are distinct, proper, or nontrivial).
The value is defined to be
where and denote the cardinalities of the underlying sets of and of the subgroup (each read as its own type of elements; since is finite these are ordinary finite cardinalities, and always because a subgroup contains the identity), the is the greatest common divisor of the -element multiset of subgroup orders taken over all indices , and the division is natural-number (truncating) division.
Boundary and degenerate behaviour, spelled out because the arithmetic is total:
- If the index type is empty, the greatest common divisor of the empty family is by convention, and natural-number division by yields . So when ; nothing signals an error.
- If , then (each ), so the denominator is nonzero. Moreover each divides by Lagrange's theorem, hence the divides and the truncating division happens to be exact in this case — but exactness is a consequence of the finiteness instance plus Lagrange, not something asserted anywhere in the code.
- If some is the trivial subgroup then the is and . If all then .
- Since is assumed finite, , so the numerator is never the "junk" value that would take for an infinite group.
There is no hypothesis linking the two definitions: does not require that the cosets partition , does not mention any translating family , and imposes no relation among the (no covering, no disjointness, no distinctness, no ordering of orders). Neither declaration asserts any mathematical claim; together they only fix the meaning of the predicate "this indexed family of left cosets partitions " and of the number .
Confirmed by the mission captain (proposal self-audit).