Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Coset partitions and their modulus

Definition
BFFPyramidal_cosetPartition

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

combinatoricscoset-partitionsgroup-theoryherzog-schonheim

A family of left cosets aiKia_iK_iai​Ki​ of subgroups Ki≤GK_i \le GKi​≤G, indexed by iii, is a coset partition of GGG when every element of GGG lies in exactly one of them; equivalently the cosets are pairwise disjoint and cover GGG. These are the objects of the Herzog-Schönheim conjecture and, for G=ZG = \mathbb{Z}G=Z, the exact covering systems of the integers.

Attached to a finite family K1,…,KtK_1,\dots,K_tK1​,…,Kt​ of subgroups of a finite group GGG is the modulus

l  =  ∣G∣gcd⁡ ⁣(∣K1∣,…,∣Kt∣),l \;=\; \frac{|G|}{\gcd\!\left(|K_1|,\dots,|K_t|\right)},l=gcd(∣K1​∣,…,∣Kt​∣)∣G∣​,

the quantity in terms of which the multiplicity bound of Berger, Felzenbaum and Fraenkel is stated.

Formalization note. Membership in the coset aiKia_i K_iai​Ki​ is expressed as (ai)−1x∈Ki(a_i)^{-1}x \in K_i(ai​)−1x∈Ki​, 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 KiK_iKi​ 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 ∣G∣|G|∣G∣).

A further note on boundary behaviour: uniqueness is uniqueness of the index iii, so a family that repeats a coset (equal KiK_iKi​ and equal aia_iai​ 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 GGG is nonempty. For t=0t = 0t=0 the modulus degenerates to 000, the gcd over an empty family being 000; all statements that use it assume t>1t > 1t>1.

Definition code
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
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. 140 (statement of the Herzog-Schönheim conjecture) and p. 139, eq. (4) (the quantity lll)
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 GGG (universe-polymorphic), together with an instance-implicit assumption that GGG carries a group structure (no commutativity, no finiteness, no nontriviality assumed — the trivial group is allowed);
  • an implicit index type ι\iotaι (universe-polymorphic, with no finiteness, nonemptiness, or decidability assumption whatsoever — ι\iotaι may be empty, finite, or infinite);
  • an explicit family K:ι→Subgroup(G)K : \iota \to \mathrm{Subgroup}(G)K:ι→Subgroup(G), i.e. a subgroup Ki≤GK_i \le GKi​≤G for each index iii (the KiK_iKi​ are not assumed distinct, nor of finite index, nor proper, nor pairwise anything);
  • an explicit family a:ι→Ga : \iota \to Ga:ι→G of group elements (no assumption on them; e.g. they may all be equal, or equal to the identity).

The predicate IsCosetPartition(K,a)\mathrm{IsCosetPartition}(K, a)IsCosetPartition(K,a) is declared to hold exactly when

∀ x∈G, ∃! i∈ι, ai−1x∈Ki.\forall\, x \in G,\ \exists!\, i \in \iota,\ a_i^{-1} x \in K_i .∀x∈G, ∃!i∈ι, ai−1​x∈Ki​.

Unfolding the "exists unique" quantifier literally, this says: for every x∈Gx \in Gx∈G there is an index i∈ιi \in \iotai∈ι with ai−1x∈Kia_i^{-1}x \in K_iai−1​x∈Ki​, and moreover for every index j∈ιj \in \iotaj∈ι satisfying aj−1x∈Kja_j^{-1}x \in K_jaj−1​x∈Kj​ one has j=ij = ij=i.

The membership condition ai−1x∈Kia_i^{-1}x \in K_iai−1​x∈Ki​ is equivalent to x∈aiKix \in a_i K_ix∈ai​Ki​, the left coset of KiK_iKi​ by aia_iai​ (the translating element multiplies on the left; the right-coset version xai−1∈Kix a_i^{-1} \in K_ixai−1​∈Ki​ is not what is written). So the predicate says: every element of GGG lies in the left coset aiKia_i K_iai​Ki​ for exactly one index iii.

Two points about the exact strength of this, as written. First, uniqueness is uniqueness of the index, not of the coset: if i≠ji \ne ji=j but aiKi=ajKja_i K_i = a_j K_jai​Ki​=aj​Kj​ as subsets of GGG (for instance if Ki=KjK_i = K_jKi​=Kj​ and ai=aja_i = a_jai​=aj​, or simply if the family repeats), then every xxx in that common coset has two admissible indices, and the predicate is false, even though the underlying family of sets does cover GGG with pairwise disjoint-or-equal pieces. Second, the statement bundles covering and disjointness together: existence gives ⋃iaiKi=G\bigcup_{i} a_i K_i = G⋃i​ai​Ki​=G, and uniqueness gives aiKi∩ajKj=∅a_i K_i \cap a_j K_j = \varnothingai​Ki​∩aj​Kj​=∅ for all i≠ji \ne ji=j.

Degenerate cases. If ι\iotaι is empty, the condition ∀x,∃!i,…\forall x,\exists! i,\dots∀x,∃!i,… fails, because GGG is always nonempty (it contains 111); so the predicate is false for the empty index type — it is not vacuously true. If ι\iotaι is a singleton {i0}\{i_0\}{i0​}, the predicate reduces to ai0Ki0=Ga_{i_0}K_{i_0} = Gai0​​Ki0​​=G, i.e. Ki0=GK_{i_0} = GKi0​​=G. If GGG is the trivial group, the predicate holds precisely when ι\iotaι is a singleton. No hypothesis in the definition is impossible to satisfy: the predicate is satisfiable (e.g. ι\iotaι a singleton and Ki0=GK_{i_0} = GKi0​​=G), 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 GGG (universe-polymorphic), with instance-implicit assumptions that GGG is a group and that GGG is finite;
  • an implicit natural number ttt (any t≥0t \ge 0t≥0, including t=0t = 0t=0);
  • an explicit family K:{0,1,…,t−1}→Subgroup(G)K : \{0,1,\dots,t-1\} \to \mathrm{Subgroup}(G)K:{0,1,…,t−1}→Subgroup(G), i.e. subgroups K0,…,Kt−1K_0,\dots,K_{t-1}K0​,…,Kt−1​ of GGG indexed by the canonical ttt-element type (again with no assumption that they are distinct, proper, or nontrivial).

The value is defined to be

modulus(K)  =  ⌊∣G∣gcd⁡(∣K0∣, ∣K1∣,…,∣Kt−1∣)⌋,\mathrm{modulus}(K) \;=\; \left\lfloor \frac{|G|}{\gcd\big(|K_0|,\,|K_1|,\dots,|K_{t-1}|\big)} \right\rfloor,modulus(K)=⌊gcd(∣K0​∣,∣K1​∣,…,∣Kt−1​∣)∣G∣​⌋,

where ∣G∣|G|∣G∣ and ∣Ki∣|K_i|∣Ki​∣ denote the cardinalities of the underlying sets of GGG and of the subgroup KiK_iKi​ (each KiK_iKi​ read as its own type of elements; since GGG is finite these are ordinary finite cardinalities, and ∣Ki∣≥1|K_i| \ge 1∣Ki​∣≥1 always because a subgroup contains the identity), the gcd⁡\gcdgcd is the greatest common divisor of the ttt-element multiset of subgroup orders taken over all indices i∈{0,…,t−1}i \in \{0,\dots,t-1\}i∈{0,…,t−1}, and the division is natural-number (truncating) division.

Boundary and degenerate behaviour, spelled out because the arithmetic is total:

  • If t=0t = 0t=0 the index type is empty, the greatest common divisor of the empty family is 000 by convention, and natural-number division by 000 yields 000. So modulus(K)=0\mathrm{modulus}(K) = 0modulus(K)=0 when t=0t = 0t=0; nothing signals an error.
  • If t≥1t \ge 1t≥1, then gcd⁡≥1\gcd \ge 1gcd≥1 (each ∣Ki∣≥1|K_i| \ge 1∣Ki​∣≥1), so the denominator is nonzero. Moreover each ∣Ki∣|K_i|∣Ki​∣ divides ∣G∣|G|∣G∣ by Lagrange's theorem, hence the gcd⁡\gcdgcd divides ∣G∣|G|∣G∣ 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 KiK_iKi​ is the trivial subgroup then the gcd⁡\gcdgcd is 111 and modulus(K)=∣G∣\mathrm{modulus}(K) = |G|modulus(K)=∣G∣. If all Ki=GK_i = GKi​=G then modulus(K)=1\mathrm{modulus}(K) = 1modulus(K)=1.
  • Since GGG is assumed finite, ∣G∣≥1|G| \ge 1∣G∣≥1, so the numerator is never the "junk" value 000 that ∣G∣|G|∣G∣ would take for an infinite group.

There is no hypothesis linking the two definitions: modulus\mathrm{modulus}modulus does not require that the cosets aiKia_i K_iai​Ki​ partition GGG, does not mention any translating family aaa, and imposes no relation among the KiK_iKi​ (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 GGG" and of the number ∣G∣/gcd⁡i∣Ki∣|G|/\gcd_i |K_i|∣G∣/gcdi​∣Ki​∣.

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